Evaluating Real-World Generalizability of Algorithm Selection Models

Technical Summary: Evaluating Real-World Generalizability of Algorithm Selection Models

Problem Statement
Algorithm Selection (AS) aims to automatically identify the most suitable optimization algorithm for a specific problem instance by leveraging measurable problem characteristics (landscape features) and historical performance data. While AS models have been extensively developed and evaluated on controlled synthetic benchmark suites (such as BBOB and CEC), their ability to generalize to real-world optimization landscapes remains largely unverified. Existing literature suggests that synthetic benchmarks often lack the structural complexity, noise patterns, and domain-specific constraints inherent in practical problems. Consequently, models trained on synthetic data may overfit to specific landscape distributions and fail when applied to realistic, domain-specific tasks. This study addresses the critical gap in understanding how well AS models transfer between synthetic academic benchmarks and real-world problem sets.

Methodology
The study employs a systematic cross-benchmark evaluation framework involving four distinct problem sources:

1. Synthetic Benchmarks: The Black-Box Optimization Benchmarking (BBOB) suite and the IEEE CEC real-parameter single-objective benchmark series.
2. Real-World Benchmarks: A set of robotics trajectory optimization problems (ROB) and Unmanned Aerial Vehicle (UAV) path-planning problems.

The experimental setup includes an algorithm portfolio of eight population-based single-objective optimization methods (including AGSK, DE, PSO, LSHADE, and others). The authors evaluate performance across dimensions 6, 12, 18, 24, and 30.

Feature Extraction and Preprocessing:
The study utilizes Exploratory Landscape Analysis (ELA) features derived from the flacco package (62 features per instance). To investigate the impact of data representation on generalization, the authors test various preprocessing strategies:

• Scaling: None, y-scaling (objective function only), and x-y-scaling (decision variables and objective function).
• Sampling: Full sample (10,000 points) versus downsampled (50d points).

Modeling and Evaluation:
A Random Forest (RF) regressor is trained to predict the normalized precision score of each algorithm for a given problem instance. The AS performance is measured by the difference between the predicted best algorithm's score and the true best algorithm's score, compared against a "dummy" baseline that predicts the mean performance of the best solver observed in the training set. The evaluation follows a strict cross-benchmark protocol: models are trained on one benchmark and tested on all four, as well as in a merged-benchmark setting. Additionally, a crossmatch test is employed to quantify the statistical similarity of ELA feature distributions between benchmark pairs.

Key Results

• Limited Generalization: In most cross-benchmark scenarios, particularly in lower dimensions (6d), AS models trained on synthetic benchmarks (BBOB/CEC) fail to outperform the dummy baseline when tested on real-world problems (ROB/UAV), and vice versa.
• Dimensionality Effects: While some sporadic positive transfer was observed (e.g., CEC to UAV without scaling in 6d, or CEC to UAV in 12d), generalization remained inconsistent. In higher dimensions (24d, 30d), improvements over the baseline were modest (0.1–0.2) and highly dependent on specific source-target pairs and preprocessing choices.
• The "Single-Best Solver" Overfitting Phenomenon: The analysis of prediction frequencies revealed a significant cause for poor generalization. When a training benchmark is dominated by a single best-performing algorithm (e.g., EBOwithCMAR on BBOB or APGSK_IMODE on UAV), the AS model tends to overfit by consistently predicting that same algorithm. This behavior effectively mimics the dummy baseline, resulting in no measurable gain in selection accuracy.
• Feature Space Disparity: The crossmatch test statistics confirmed that synthetic and real-world benchmarks occupy largely distinct regions of the ELA feature space. While BBOB and CEC showed substantial overlap, benchmarks involving robotics and UAV problems exhibited minimal similarity to synthetic suites, especially in higher dimensions. Preprocessing steps like scaling and downsampling increased feature-space overlap but did not consistently translate to improved AS performance.

Significance and Claims
The paper claims that strong performance on standard synthetic benchmarks does not guarantee robustness or transferability to real-world optimization problems. The study highlights that the structural differences between synthetic and real-world landscapes fundamentally limit cross-benchmark generalization.

The authors conclude that current AS approaches are often insufficient for practical deployment without addressing the distributional shift between training and target domains. They suggest that future development should shift toward:

1. Enriching benchmark collections with diverse, realistic problem instances.
2. Developing feature representations that better capture transferable problem characteristics.
3. Designing AS models explicitly aimed at cross-domain generalization rather than optimizing for specific benchmark performance.

The work underscores the necessity of moving beyond controlled synthetic settings to evaluate and develop AS systems capable of handling the heterogeneity and complexity of real-world optimization tasks.