Fitness landscape analysis and memetic algorithms for the quadratic assignment problem
IEEE Transactions on Evolutionary ComputationPublished 1 January 2000
Bernd Freisleben, P. Merz
Citations429
SJR quartileQ1
SJR score3.50
SNIP3.12
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
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.
Abstract
In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. 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 (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.
Keywords
Computer Science
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.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Ant system: optimization by a colony of cooperating agents
11,908 Citations1996Marco Dorigo, Vittorio Maniezzo +1 more
International Journal of BiochemistryThe origins of order; self organization and selection in evolution
6,753 Citations1994
Thank you very much for downloading the origins of order self organization and selection in evolution, which many people have look hundreds of times for their favorite readings like this, but end up in infectious downloads.
Ant colony optimization: a new meta-heuristic
2,126 Citations2003Marco Dorigo, Gianni A. Di
This work defines the Ant Colony Optimization (ACO) meta-heuristic by defining these algorithms in a common framework by defining the foraging behavior of ant colonies as a meta- heuristic.
IEEE Transactions on Evolutionary ComputationParameter control in evolutionary algorithms
1,913 Citations1999A. E. Eiben, Robert Hinterding +1 more
This paper revision the terminology, which is unclear and confusing, thereby providing a classification of such control mechanisms, and surveys various forms of control which have been studied by the evolutionary computation community in recent years.
Medical Entomology and ZoologyOn Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms
1,514 Citations1989Pablo Moscato
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.
international conference on Genetic algorithmsA study of permutation crossover operators on the traveling salesman problem
892 Citations1987I. M. Oliver, David J. Smith +1 more
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.
INFORMS Journal on ComputingThe Reactive Tabu Search
806 Citations1994Roberto Battiti, Giampietro Tecchiolli
An algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search, and it is shown that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant.
IEEE Transactions on Knowledge and Data EngineeringThe ant system applied to the quadratic assignment problem
745 Citations1999Vittorio Maniezzo, A. Colorni
A distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies is described and its use for the quadratic assignment problem is proposed.
Journal of the Operational Research SocietyAnt colonies for the quadratic assignment problem
676 Citations1999L. M. Gambardella, Éeric D. Taillard +1 more
Experimental results show that HAS-QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS–QAP performance is less competitive on random, regular and unstructured problems.
Biological CyberneticsCorrelated and uncorrelated fitness landscapes and how to tell the difference
547 Citations1990Ed Weinberger
A framework for the mathematical treatment of multi-peaked “fitness landscapes”, including an explicit mathematical model, is suggested, which might be useful in the “tuning” of combinatorial optimization algorithms, and in modelling in the experimental sciences.
RePEc: Research Papers in EconomicsFitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms
471 Citations1995Terry Jones, Stephanie Forrest
The FDC measure is a consequence of an investigation into the connection between GAs and heuristic search and can be used to correctly classify easy deceptive problems and easy and difficult non-deceptive problems as difficult.
INFORMS Journal on ComputingTabu Search Applied to the Quadratic Assignment Problem
461 Citations1990Jadranka Skorin‐Kapov
This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP), and suggests that good tabu list sizes increase with dimension of 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.
European Journal of Operational ResearchAn improved annealing scheme for the QAP
406 Citations1990David T. Connolly
The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort.
Lecture notes in computer scienceParallel genetic algorithms, population genetics and combinatorial optimization
369 Citations1991Heinz Mühlenbein
This paper has applied ASPARAGOS to an important combinatorial optimization problem, the quadratic assignment problem, and found a new optimum for the largest published problem.
European Journal of Operational ResearchA thermodynamically motivated simulation procedure for combinatorial optimization problems
346 Citations1984Rainer E. Burkard, Franz Rendl
Suboptimal solutions differing 1–2% from the best known solutions are obtained by a simple program in short time by starting this program several times with different starting values all known minimal objective function values were reached.
INFORMS journal on computingExact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
340 Citations1999Vittorio Maniezzo
Two new techniques for solving the Quadratic Assignment Problem are introduced, one of which is a heuristic technique, defined in accordance with the Ant System metaphor, and includes as a distinctive feature the use of a new lower bound at each constructive step.
European Journal of Operational ResearchQAPLIB-A quadratic assignment problem library
333 Citations1991Rainer E. Burkard, Stefan E. Karisch +1 more
A library of problem instances for the quadratic assignment problem is given and the examples are listed y authors in alphabetical order.
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.
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
280 Citations2002Bernd Freisleben, P. Merz
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP) and the results indicate that it is possible to arrive at high quality solutions in reasonable time.
Journal of the Operational Research SocietyHospital Layout as a Quadratic Assignment Problem
276 Citations1977Alwalid N. Elshafei
This paper presents a heuristic procedure to solve the problem of locating hospital departments so as to minimize the total distance travelled by patients, and comments on the computational experience with the heuristic.
ACO algorithms for the quadratic assignment problem
264 Citations1999Thomas Stützle, Marco Dorigo
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).
Lecture notes in computer scienceGenetic local search algorithms for the traveling salesman problem
220 Citations1991Nico L. J. Ulder, Emile Aarts +3 more
Experimental approaches to Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting.
Annals of Operations ResearchLandscapes, operators and heuristic search
203 Citations1999Colin R. Reeves
The work is developed by investigating the question of how landscapes change under different search operators in the case of the n/m/P/Cmax flowshop problem, and proposing a statistical randomisation test to provide anumerical assessment of the landscape.
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).
Lecture notes in computer scienceNew genetic local search operators for the traveling salesman problem
168 Citations1996Bernd Freisleben, Peter Merz
An approach is presented to incorporate problem specific knowledge into a genetic algorithm which is used to compute near-optimum solutions to traveling salesman problems (TSP).
A comparison of memetic algorithms, tabu search, and ant colonies for the quadratic assignment problem
155 Citations2003P. Merz, Bernd Freisleben
A comparison of the proposed memetic algorithm with some of the currently best alternative approaches-reactive tabu search, robusttabu search and the fast ant colony system-demonstrates that the MA outperforms its competitors on all studied problem instances of practical interest.
Evolutionary ComputationFitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning
145 Citations2000Peter Merz, Bernd Freisleben
It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly, however, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.
A Genetic Local Search Approach to the Quadratic Assignment Problem.
137 Citations1997Peter Merz, Bernd Freisleben
The results indicate that the proposed genetic local search approach to the quadratic assignment problem (QAP) is able to arrive at high quality solutions in a relatively short time limit: for the largest publicly known problem instance, a new best solution could be found.
Fitness landscapes and memetic algorithm design
123 Citations1999Peter Merz, Bernd Freisleben
The Max-Min ANT System and Local Search for Combinatorial Optimization Problems
121 Citations1999Thomas Stützle, Holger H. Hoos
The computational results show that this algorithm can be used to efficiently find near-optimal solutions to hard combinatorial optimization problems and that it is one of the best methods for the solution of structured quadratic assignment problems.
Management ScienceThe Facilities Layout Problem in Perspective
108 Citations1966Thomas E. Vollmann, Elwood S. Buffa
Each layout problem is made unique by its particular assumptions, constraints, limitations, and the intrinsic activity of the components; a guide to establishing this uniqueness and to selecting appropriate tool3 for analysis is presented.
A scatter search based approach for the quadratic assignment problem
96 Citations2002Van‐Dat Cung, Thierry Mautor +2 more
The authors propose a scatter search approach to the QAP problem and the basic method is extended with intensification and diversification stages and they present a procedure to generate good scattered initial solutions.
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.
Discrete Applied MathematicsGenetic local search in combinatorial optimization
91 Citations1994Antoon Kolen, Erwin Pesch
The most common application of genetic algorithms to combinatorial optimization problems has been restricted to the traveling salesman problem, but some ideas to address this problem are reviewed and some new results are presented.
IEEE Transactions on Neural NetworksSolving the quadratic assignment problem with clues from nature
90 Citations1994Volker Nissen
The combinatorial variant of ES presented here performs very well on the given test problems as compared with the standard 2-Opt heuristic and results with simulated annealing and tabu search.
Computers & Operations ResearchExtensions of a tabu search adaptation to the quadratic assignment problem
89 Citations1994Jadranka Skorin‐Kapov
The adaptation of tabu search to the Quadratic Assignment Problem (QAP) is refined by incorporating knowledge about permutations yielding good objective function values into the solution process, which allows the possibility to restrict search in the solution space by fixing those parts of permutations that are common in good quality solutions.
Lecture notes in computer scienceScheduling by genetic local search with multi-step crossover
87 Citations1996Takeshi Yamada, Ryohei Nakano
Using job-shop scheduling problem benchmarks, MSXF was evaluated in a GA framework as a high-level crossover working on the critical path of a schedule and showed promising performance for the proposed method.
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.
Lecture notes in computer scienceMemetic algorithms and the fitness landscape of the graph bi-partitioning problem
78 Citations1998Peter Merz, Bernd Freisleben
The experimental results obtained for non-geometric graphs show that the proposed memetic algorithm (MA) is superior to any other heuristic known to us, and for the geometric graphs considered, only the initialization phase of the MA is required to find (near) optimum solutions.
Computational Optimization and ApplicationsGenerating quadratic assignment test problems with known optimal permutations
66 Citations1992Yong Li, Pãnos M. Pardalos
Computational results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP and show the superiority of the new test-problem generators proposed.
European Journal of Operational ResearchAlgodesk: An experimental comparison of eight evolutionary heuristics applied to the Quadratic Assignment Problem
64 Citations1995Vittorio Maniezzo, Marco Dorigo +1 more
This work compares the effectiveness of eight evolutionary heuristic algorithms applied to the Quadratic Assignment Problem (QAP), reputedly one of the most difficult combinatorial optimization problems.
Theoretical Computer ScienceAutocorrelation coefficient for the graph bipartitioning problem
52 Citations1998Éric Angel, V. Zissimopoulos
The aim of this paper is to theoretically justify some results reported by Johnson et al. (1989, 1991) in their extended empirical study concerning simulated annealing and the graph bipartitioning problem, and to sharply tune the best landscape among the two reported in that study.
Theoretical Computer ScienceOn the landscape ruggedness of the quadratic assignment problem
48 Citations2001Éric Angel, Vassilis Zissimopoulos
It is derived that the landscape of the QAP is rather at, and so the ruggedness coeecient gives a theoretical justiication of the eeectiveness of local search based heuristics for this problem.
OR SpectrumA modification of threshold accepting and its application to the quadratic assignment problem
42 Citations1995Volker Nissen, Henrik J. Paul
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.
On the effectiveness of evolutionary search in high-dimensional NK-landscapes
35 Citations2002P. Merz, Bernd Freisleben
The results show that compared to genetic local search algorithms, the performance of standard genetic algorithms employing crossover or mutation significantly decreases with increasing problem size, and with increasing K, crossover based algorithms are in both cases outperformed by mutation based algorithms.
Genetic Engineering and Design Problems
33 Citations1997John S. Gero, Vladimir Kazakov +1 more
This chapter describes an extension of genetic algorithms which utilizes a set of ideas borrowed from the practice of genetic engineering of natural organisms and shows how it can be constructed and implemented computationally and how it enhances the efficiency of the genetic algorithm’s computational process.
Neural NetworksConstrained neural approaches to quadratic assignment problems
32 Citations1998Shin Ishii, Masa-aki Sato
Europhysics Letters (EPL)Local minima in the graph bipartitioning problem
15 Citations1996Barbel Krakhofer, Peter F. Stadler