A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem

Date

2016-06-01

Author

Dokeroglu, Tansel
Coşar, Ahmet

Metadata

Show full item record

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

Item Usage Stats

150
views

0
downloads

Hyper-heuristics introduce novel approaches for solving challenging combinatorial optimization problems by operating over a set of low level (meta)-heuristics. This is achieved by an evolutionary selection mechanism that controls and combines the strengths of the low level (meta) -heuristics. In this study, we propose a high-performance MultiStart Hyper-heuristic algorithm (MSH-QAP) on the grid for the solution of the Quadratic Assignment Problem (QAP). MSH-QAP algorithm makes use of state-of:the-art (meta)-heuristics, Simulated Annealing (SA), Robust Tabu Search (RTS), Ant Colony Optimization (FAnt), and Breakout Local Search (BLS) that have been reported among the best performing algorithms for the solution of difficult QAP instances in standard benchmark libraries. In the first phase of the algorithm, the most appropriate(meta)-heuristic with its near-optimal parameter settings is selected by using a genetic algorithm optimization layer that uses a self-adaptive parameter setting method for the given. problem instance. In the second phase, if an optimal solution cannot be found, selected best performing (meta) heuristic (with its finely adjusted parameter settings) is executed on the grid using parallel processing and performing several multistarts in order to increase the quality of the discovered solution. MSH-QAP algorithm is tested on 134 problem instances of the QAPLIB benchmark and is shown to be able to solve 122 of the instances exactly. The overall deviation for the problem instances is obtained as 0.013% on the average.

Subject Keywords

Hyper-heuristics, Assignment, Simulated annealing, Tabu search, Ant colony, Breakout local search

URI

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

Journal

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

DOI

https://doi.org/10.1016/j.engappai.2016.02.004

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem Aksan, Yagmur; Dokeroglu, Tansel; Coşar, Ahmet (2017-01-01) The Quadratic Assignment Problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems. Circuit-layout design, transportation/traffic engineering, and assigning gates to airplanes are some of the interesting applications of the QAP. In this study, we introduce an enhanced version of a recent local search heuristic, Breakout Local Search Algorithm (BLS), by using the Levenshtein Distance metric for checking the similarity of the new starting points to previously explored QAP permut...
A reformulation of the ant colony optimization algorithm for large scale structural optimization Hasançebi, Oğuzhan; Saka, M.p. (2011-01-01) This study intends to improve performance of ant colony optimization (ACO) method for structural optimization problems particularly with many design variables or when design variables are chosen from large discrete sets. The algorithm developed with ACO method employs the so-called pheromone scaling approach to overcome entrapment of the search in a poor local optimum and thus to recover efficiency of the method for large-scale optimization problems. Besides, a new formulation is proposed for the local upda...
A NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2018-01-01) We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation define...
A new multiobjective simulated annealing algorithm Tekinalp, Ozan (Springer Science and Business Media LLC, 2007-09-01) A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions,...
A NEW HEURISTIC APPROACH FOR THE MULTIITEM DYNAMIC LOT-SIZING PROBLEM KIRCA, O; KOKTEN, M (Elsevier BV, 1994-06-09) In this paper a framework for a new heuristic approach for solving the single level multi-item capacitated dynamic lot sizing problem is presented. The approach uses an iterative item-by-item strategy for generating solutions to the problem. In each iteration a set of items are scheduled over the planning horizon and the procedure terminates when all items are scheduled. An algorithm that implements this approach is developed in which in each iteration a single item is selected and scheduled over the planni...

Citation Formats

T. Dokeroglu and A. Coşar, “A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem,” ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, pp. 10–25, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31417.