Inferring Future Landscapes: Sampling the Local Optima Level.

Area of Science:

• Computational Intelligence
• Operations Research
• Machine Learning

Background:

• Local Optima Networks (LONs) analysis is vital for heuristic design in optimization.
• Traditional LON research requires complete fitness landscape enumeration, limiting scalability to real-world problems.
• Efficient LON sampling algorithms are essential for analyzing large-scale optimization problems.

Purpose of the Study:

• To investigate LON construction algorithms for the Quadratic Assignment Problem (QAP).
• To utilize machine learning for predicting heuristic search performance based on estimated LON features.
• To evaluate the effectiveness of sampled LONs compared to enumerated ones for search prediction.

Main Methods:

• Studied LON construction algorithms specifically for the Quadratic Assignment Problem (QAP).
• Employed machine learning, specifically random forest regression, to predict search performance using estimated LON features.
• Combined features from LONs generated by different algorithms for enhanced predictive modeling ('super-sampling').

Main Results:

• LON construction algorithms generate fitness landscape features that explain almost all search variance in QAP.
• Sampled LONs demonstrate a stronger correlation with search performance than enumerated LONs.
• A 'super-sampling' model combining features from multiple LON algorithms predicted tabu search success with 99% variance explained.

Conclusions:

• Sampled LON features are highly effective predictors of heuristic search performance, outperforming traditional enumeration.
• Combining features from diverse LON sampling algorithms ('super-sampling') significantly enhances prediction accuracy.
• Different LON algorithms offer complementary strengths, suggesting combined approaches for robust heuristic design and analysis.