An improved hybrid genetic algorithm: new results for the quadratic assignment problem
Knowledge-Based SystemsPublished 2 April 2004
Alfonsas Misevičius
Citations114
SJR quartileQ1
SJR score1.93
SNIP2.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The results obtained from the numerous experiments on different QAP instances from the instances library QAPLIB show that the proposed algorithm appears to be superior to other modem heuristic approaches that are among the best algorithms for the QAP.
Abstract
In this paper, we propose an improved hybrid genetic algorithm (IHGA). It uses a robust local improvement procedure as well as an effective restart mechanism that is based on so-called 'shift mutations'. IHGA has been applied to the well-known combinatorial optimization problem, the quadratic assignment problem (QAP). The results obtained from the experiments on different QAP instances show that the proposed algorithm appears to be superior to other approaches that are among the best algorithms for the QAP. The high efficiency of our algorithm is also corroborated by the fact that new record-breaking solutions were obtained for a number of large real-life instances.
Keywords
Computer ScienceEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
Computers & Operations ResearchVariable neighborhood search
4,147 Citations1997Nenad Mladenović, Pierre Hansen
This chapter presents the basic schemes of VNS and some of its extensions, and presents five families of applications in which VNS has proven to be very successful.
International series in management science/operations research/International series in operations research & management scienceHandbook of Metaheuristics
3,396 Citations2003Fred Glover, Gary Kochenberger
This book discusses Metaheuristic Class Libraries, Hyper-Heuristics, and Parallel Strategies for Meta-Heuristics as well as other topics related to Meta-Heuristics, which have had an important role in the development of search technology.
New Ideas In Optimization
2,135 Citations1999David Corne, Marco Dorigo +5 more
The techniques treated in this text represent research as elucidated by the leaders in the field and are applied to real problems, such as hilllclimbing, simulated annealing, and tabu search.
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
Journal of the ACMP-Complete Approximation Problems
1,715 Citations1976Sartaj Sahni, Teofilo F. Gonzalez
For P- complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete.
Handbook of Combinatorial Optimization
1,218 Citations1999Ding‐Zhu Du, Pãnos M. Pardalos
Foundations of genetic algorithmsThe CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination
1,042 Citations1991Larry J. Eshelman
CHC is described and analyzed, a nontraditional genetic algorithm which combines a conservative selection strategy that always preserves the best individuals found so far with a radical (highly disruptive) recombination operator that produces offspring that are maximally different from both parents.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
Journal of Global OptimizationQAPLIB – A Quadratic Assignment Problem Library
655 Citations1997Rainer E. Burkard, Stefan E. Karisch +1 more
A collection of electronically available data instances for the Quadratic Assignment Problem are described, indicating whether or not the problem is solved to optimality and the best known bounds for the problem are supplied.
Journal of the Operational Research SocietyA Genetic Algorithm for the Set Covering Problem
535 Citations1996K. S. Al-Sultan, Mohammed F. Hussain +1 more
A new algorithm is proposed for solving the set covering problem which is based on the genetic technique, and preliminary results are encouraging, and are better than the existing heuristics for the problem.
IEEE Transactions on Evolutionary ComputationFitness landscape analysis and memetic algorithms for the quadratic assignment problem
429 Citations2000Bernd Freisleben, P. Merz
It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search.
Journal of Computational PhysicsRecord Breaking Optimization Results Using the Ruin and Recreate Principle
397 Citations2000Gerhard Schrimpf, Johannes J. Schneider +2 more
A new optimization principle is presented that is particularly suited for more complex optimization problems (“discontinuous” ones, problems with hard-to-find admissible solutions, Problems with complex objectives or many constraints).
Journal of the Operational Research SocietyMeta-Heuristics Theory and Applications
379 Citations1997Ibrahim H. Osman, J P Kelly
This volume is drawn from the first conference on Meta-Heuristics and contains 41 papers on the state-of-the-art in heuristic theory and applications.
Computers & Operations ResearchA greedy genetic algorithm for the quadratic assignment problem
366 Citations2000Ravindra K. Ahuja, James B. Orlin +1 more
The overall performance of the GA for the QAP improves by using greedy methods but not their overuse, and the use of several possible enhancements to GAs are investigated and illustrated using the Quadratic Assignment Problem, one of the hardest nut in the field of combinatorial optimization.
IEEE Transactions on ComputersGenetic algorithm and graph partitioning
340 Citations1996Thang Nguyen Bui, Byung Ro Moon
Experimental tests on graph problems with published solutions showed that the new genetic algorithms performed comparable to or better than the multistart Kernighan-Lin algorithm and the simulated annealing algorithm.
Computers & Operations ResearchA genetic approach to the quadratic assignment problem
330 Citations1995David M. Tate, Alice E. Smith
This paper presents computational results which show that this genetic algorithm approach to QAP finds solutions competitive with those of the best previously-known heuristics, and argues that genetic algorithms provide a particularly robust method for QAP and its more complex extensions.
Location ScienceComparison of iterative searches for the quadratic assignment problem
323 Citations1995Éric D. Taillard
This paper compares some of the most efficient heuristic methods for the quadratic assignment problem and shows that no one method is better than all the others.
Journal of HeuristicsA Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions
292 Citations2000Rachid Chelouah, Patrick Siarry
A new algorithm called Continuous Genetic Algorithm (CGA) is proposed for the global optimization of multiminima functions, which takes care over the choice of the initial population and locates the most promising area of the solution space, and continues the search through an “intensification” inside this area.
Genetic local search for the TSP: new results
237 Citations2002P. Merz, Bernd Freisleben
The previously proposed genetic local search algorithms for the symmetric and asymmetric traveling salesman problem are revisited and potential improvements are identified.
DIMACS series in discrete mathematics and theoretical computer scienceGenetic hybrids for the quadratic assignment problem
231 Citations1994Charles Fleurent, Jacques A. Ferland
A new hybrid procedure that combines genetic operators to existing heuristics is proposed to solve the Quadratic Assignment Problem (QAP).
Mathematical programming studiesComputer-aided layout design
191 Citations1978Jakob Krarup, Peter Pruzan
Within the general problem area of location problems, the layout planning problem or facilities location problem has for years attracted the attention of building planners (architects, industrial engineers, and operations researchers).
INFORMS journal on computingA New Genetic Algorithm for the Quadratic Assignment Problem
180 Citations2003Zvi Drezner
A special merging rule for creating an offspring that exploits the special structure of the quadratic assignment problem is designed and a new type of a tabu search, which is applied on the offspring before consideration for inclusion in the population is designed.
The Quadratic Assignment Problem
170 Citations1998Rainer E. Burkard, Eranda Çela +2 more
Computational Optimization and ApplicationsA Tabu Search Algorithm for the Quadratic Assignment Problem
131 Citations2005Alfonsas Misevičius
A new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP), with an efficient use of mutations applied to the best solutions found so far.
Mathematical Methods of Operations ResearchEntwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
96 Citations1977Rainer E. Burkard, J. Offermann
For improving the keyboard of a typewriter a quadratic assignment problem is set up and solved suboptimally and improvements of 7%–10% compared with the international standard keyboard are given.
Computational Optimization and ApplicationsEfficient Genetic Algorithms Using Simple Genes Exchange Local Search Policy for the Quadratic Assignment Problem
94 Citations2000M.H. Lim, Y. Yuan +1 more
An approach for solving the quadratic assignment problem (QAP) that is based on genetic algorithms (GA) and it is proposed that the local search should involve simple procedure of genome reordering that should not be too complex.
European Journal of Operational ResearchOptimizing simulated annealing schedules with genetic programming
87 Citations1996Andreas Bölte, Ulrich W. Thonemann
This work replaces this manual search by Genetic Programming, a method based on natural evolution, by optimizing the annealing schedule for a well-known combinatorial optimization problem, the Quadratic Assignment Problem.
SUPSI ARISAdaptive memories for the Quadratic Assignment Problems
85 Citations1997Éric D. Taillard, Luca Maria Gambardella
The paper proposes, compares and analyses different memory- based meta-heuristics for the quadratic assignment problem (QAP), including FANT and GDH, which are new while two others are among the best for structured QAP instances.
Naval Research Logistics (NRL)Using hybrid metaheuristics for the one‐way and two‐way network design problem
55 Citations2002Zvi Drezner, Saı̈d Salhi
Both the simulated annealing and the genetic algorithms propose innovative approaches and these innovative ideas can be used in the implementation of these heuristic algorithms for other problems as well.
Knowledge-Based SystemsGenetic algorithm hybridized with ruin and recreate procedure: application to the quadratic assignment problem
52 Citations2003Alfonsas Misevičius
This paper has applied this new hybrid strategy to the well-known combinatorial optimization problem, the quadratic assignment problem (QAP), and shows that the proposed algorithm belongs to the best heuristics for the QAP.
SUPSI ARISFANT: Fast ant system
41 Citations1998Éric D. Taillard
A new point of view of ant systems that is more general than previous ones is presented, identifying artificial ants with processes that cooperate through a shared memory and a Queen process that co-ordinates the Ant processes.
Journal of HeuristicsA Hybrid Genetic Algorithm for the Single Machine Scheduling Problem
40 Citations1999David M. Miller, Hui-Chuan Chen +2 more
A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP), which incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area.
MetaheuristicsGenetic and Local Search Algorithms as Robust and Simple Optimization Tools
19 Citations1996Mutsunori Yagiura, Toshihide Ibaraki
The results indicate that the performance of GA is not sensitive about crossovers if implemented with mutations, simple implementation of MLS is usually competitive with (or even better than) GA, and GRASP type modification of MLS improves its performance to some extent.