Identifying Features of Fitness Landscapes and Relating Them to Problem Difficulty

Area of Science:

• Operations Research
• Computer Science
• Computational Intelligence

Background:

• Heuristic solvers often optimize complex combinatorial problems without indicating result quality.
• Predictive diagnostic optimization (PDO) was introduced to characterize fitness landscapes during optimization.
• Existing PDO scalars show some reliability in describing problem difficulty.

Purpose of the Study:

• To investigate additional scalars for assessing problem difficulty during optimization.
• To analyze these scalars in conjunction with known landscape descriptors.
• To evaluate their correlation with optimization outcome quality.

Main Methods:

• Exploratory factor analysis was applied to four distinct landscapes.
• Landscapes were derived from different search operators on quadratic assignment problem instances.
• Multiple landscape descriptors and newly recorded scalars were analyzed.

Main Results:

• Extracted factors, representing landscape features, showed weak correlations with optimizer result quality.
• Prediction error from predictive diagnostic optimization demonstrated a strong correlation with result quality.
• Fitness distance correlation of local optima exhibited a medium correlation with result quality.

Conclusions:

• While factors derived from landscape descriptors have limited predictive power for difficulty.
• The prediction error of predictive diagnostic optimization is a reliable indicator of problem difficulty.
• Fitness distance correlation also offers moderate insights into problem difficulty.