Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
198
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.