Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance

Francisco Chicano¹, Fabio Daolio², Gabriela Ochoa³, Sébastien Vérel⁴, Marco Tomassini², and Enrique Alba¹

¹E.T.S. Ingeniería Informática, University of Málaga, Spain

²Information Systems Department, University of Lausanne, Lausanne, Switzerland

³Inst. of Computing Sciences and Mathematics, University of Stirling, Scotland, UK

⁴INRIA Lille - Nord Europe and University of Nice Sophia-Antipolis, France

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.

LNCS 7492, p. 337 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012