Fitness landscape analysis and memetic algorithms for the quadratic assignment problem
Authors:
- B. FreislebenBFB. Freisleben
Top Cited Papers
- 1 November 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 4 (4) , 337-352
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
This publication has 45 references indexed in Scilit:
- On the landscape ruggedness of the quadratic assignment problemTheoretical Computer Science, 2001
- Parameter control in evolutionary algorithmsIEEE Transactions on Evolutionary Computation, 1999
- Autocorrelation coefficient for the graph bipartitioning problemTheoretical Computer Science, 1998
- Local minima in the graph bipartitioning problemEurophysics Letters, 1996
- Landscapes and their correlation functionsJournal of Mathematical Chemistry, 1996
- A modification of threshold accepting and its application to the quadratic assignment problemOR Spectrum, 1995
- Entwurf von Schreibmaschinentastaturen mittels quadratischer ZuordnungsproblemeMathematical Methods of Operations Research, 1977
- Hospital Layout as a Quadratic Assignment ProblemJournal of the Operational Research Society, 1977
- Campus building arrangement using topazTransportation Research, 1972
- The Backboard Wiring Problem: A Placement AlgorithmSIAM Review, 1961