Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance
This work addresses the challenge of predicting search algorithm effectiveness for combinatorial optimization problems like QAP, but it is incremental as it builds on existing tools without introducing a new method.
The paper tackled the problem of forecasting heuristic search algorithm performance by combining Local Optima Networks and Elementary Landscapes theory, analyzing 600 generated instances of the Quadratic Assignment Problem and revealing links between network measures, autocorrelation measures, and algorithm performance.
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.