Local optima networks, landscape autocorrelation and heuristic search performance

Citation

Chicano F, Daolio F, Ochoa G, Verel S, Tomassini M & Alba E (2012) Local optima networks, landscape autocorrelation and heuristic search performance. In: Coello CC, Cutello V, Deb K K, Forrest S, Nicosia G & Pavone M (eds.) Parallel Problem Solving from Nature - PPSN XII: 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part II. Lecture Notes in Computer Science, 7492. PPSN 2012 - 12th International Conference on Parallel Problem Solving from Nature, Taormina, Italy, 01.09.2012-05.09.2012. Berlin Heidelberg: Springer, pp. 337-347. http://link.springer.com/chapter/10.1007/978-3-642-32964-7_34#; https://doi.org/10.1007/978-3-642-32964-7_34

Abstract
Recent developments in fitness landscape analysis include the study of Local Optima Networks (LON) and applications of the Elementary Landscapes theory. This paper represents a first step at combining these two tools to explore their ability to forecast the performance of search algorithms. We base our analysis on the Quadratic Assignment Problem (QAP) and conduct a large statistical study over 600 generated instances of different types. Our results reveal interesting links between the network measures, the autocorrelation measures and the performance of heuristic search algorithms.