Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem

Date

2016-09-01

Author

Arin, Arif
Rabadi, Ghaith

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

183
views

0
downloads

Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path Relinking is introduced to replace the local search in the improvement phase of Meta-RaPS (Meta Heuristic for Randomized Priority Search) which is currently classified as a memoryless metaheuristic. The new algorithm is tested using the 0-1 multidimensional knapsack problem, and it is observed that it could solve even the largest benchmark problems in significantly less time while maintaining solution quality compared to other algorithms in the literature.

Subject Keywords

Software

URI

https://hdl.handle.net/11511/65367

Journal

APPLIED SOFT COMPUTING

DOI

https://doi.org/10.1016/j.asoc.2016.05.016

Collections

Department of Business Administration, Article

Suggestions

OpenMETU
Core

Improving search result clustering by integrating semantic information from Wikipedia Çallı, Çağatay; Üçoluk, Göktürk; Şehitoğlu, Onur Tolga; Department of Computer Engineering (2010) Suffix Tree Clustering (STC) is a search result clustering (SRC) algorithm focused on generating overlapping clusters with meaningful labels in linear time. It showed the feasibility of SRC but in time, subsequent studies introduced description-first algorithms that generate better labels and achieve higher precision. Still, STC remained as the fastest SRC algorithm and there appeared studies concerned with different problems of STC. In this thesis, semantic relations between cluster labels and documents ar...
Analysis Pattern of Sanliurfa Harran Plain in UML and its Implementation in Geodatabase Çubuk, Ulaş; Usul, Nurünnisa; Department of Geodetic and Geographical Information Technologies (2004) An emerging trend in GIS is the adoption of object oriented concepts for both logical and physical design phases. Extensive research has been conducted on logical design of GIS and several conceptual models have been proposed. Classical data models like the relational data model have proven to be insufficient for the conceptual modeling of spatial data. Therefore among other object oriented modeling tools, a new modeling language, Unified Modeling Language (UML) has also become a popular modeling tool in th...
Systematic component-oriented development with axiomatic design Toğay, Cengiz; Doğru, Ali Hikmet; Department of Computer Engineering (2008) In this research, component oriented development is supported with design guidance by extending the Axiomatic Design Theory for component orientation, and utilizing domain engineering and ontology mechanisms. Guidance is offered in the form of suggesting missing components and discovering incompatibilities among the candidate elements of software development, corresponding to different phases such as requirement analysis, design, and implementation. A mature domain concept is developed suggesting the availa...
Model-based code generation for HLA federates Adak, Mehmet; Topcu, Okan; Oğuztüzün, Mehmet Halit S. (Wiley, 2010-02-01) This paper addresses the problem of automated code generation for a High Level Architecture compliant federate application given its behavior model. The behavior model is a part of the architectural model of a federation that the federate can participate in. The federate behavior model is based on Live Sequence Charts, adopted as the behavioral specification formalism in the Federation Architecture Metamodel (FAMM). FAMM serves as a formal language for describing federation architectures. An objective is to...
Comparative evaluation of command distribution via DDS and CORBA in a software reference architecture Duran, Mustafa Berk; Bilgen, Semih; Department of Electrical and Electronics Engineering (2014) Communication between modules in distributed system architectures plays a crucial role in proper system operation. Therefore, selection of the method for the communication of software running on di erent platforms becomes important. Two of the alternatives for data distribution are the Common Object Request Broker Architecture (CORBA) and Data-Distribution Service (DDS). In this study, e ects of the selection on the Overall software quality and performance are investigated for real-time embedded systems dev...

Citation Formats

A. Arin and G. Rabadi, “Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem,” APPLIED SOFT COMPUTING, pp. 317–327, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65367.