Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

In this paper, a fitness landscape analysis for several instances of the qu adratic assignment problem (QAP) Is performed, and the results are used to classify problem instances according to their hardness for local search heu ristics 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 distanc e correlation analysis. It is shown that epistasis, as expressed by the dom inance of the flow and distance matrices of a QAP instance, the landscape r uggedness in terms of the correlation length of a landscape, and the correl ation between fitness and distance of local optima in the landscape togethe r are useful for predicting the performance of memetic algorithms-evolution ary algorithms incorporating local search-to a certain extent. Thus, based on these properties, a favorable choice of recombination and/or mutation op erators can be found. Experiments comparing three different evolutionary op erators for a memetic algorithm are presented. It is shown in experiments t hat a memetic algorithm using our recently proposed information-p reserving recombination operator for the QAP is able to outperform five of its compe titors, two variants of tabu search, two ant-colony algorithms, and simulat ed annealing, on all tested instances of practical interest on a set of pro blem instances with a problem size of up to 256.