Abstract
One of the most challenging problems in evolutionary computation is to select from its family of diverse solvers one that performs well on a given problem. This algorithm selection problem is complicated by the fact that different phases of the optimization process require different search behavior. While this can partly be controlled by the algorithm itself, there exist large differences between algorithm performance. It can therefore be beneficial to swap the configuration or even the entire algorithm during the run. Long deemed impractical, recent advances in Machine Learning and in exploratory landscape analysis give hope that this dynamic algorithm configuration (dynAC) can eventually be solved by automatically trained configuration schedules. With this work we aim at promoting research on dynAC, by introducing a simpler variant that focuses only on switching between different algorithms, not configurations. Using the rich data from the Black Box Optimization Benchmark (BBOB) platform, we show that even single-switch dynamic Algorithm selection (dynAS) can potentially result in significant performance gains. We also discuss key challenges in dynAS, and argue that the BBOB-framework can become a useful tool in overcoming these.
Introduction
In numerical black-box optimization, identifying the optimal solver for a specific problem is a fundamental challenge. Traditionally, the "Algorithm Selection Problem" seeks to find a single best algorithm for a given task. However, optimization is a dynamic process: early stages often require exploratory behavior to locate promising regions, while later stages require exploitative behavior for high-precision convergence. Because a single algorithm is rarely optimal for both phases, static selection acts as a performance bottleneck.
This study investigates Dynamic Algorithm Selection (dynAS), specifically a "single-switch" model. In this scenario, an optimization run begins with Algorithm $A_1$ and transitions to Algorithm $A_2$ once a predefined target precision is reached. By leveraging historical data, we demonstrate that even this simplified dynamic approach can yield substantial performance improvements.
Methodology and Data
The research utilizes data from the Black-Box Optimization Benchmark (BBOB), part of the COCO framework, encompassing 182 algorithms submitted over the last decade. The analysis covers 24 noiseless benchmark functions across dimensions ranging from 2D to 40D.
To quantify the potential of dynamic selection, we compare three theoretical benchmarks:
- Single Best Solver (SBS): The best-performing algorithm on average across all problems.
- Virtual Best Static Solver (VBS_static): The optimal single algorithm for a specific function-dimension pair.
- Virtual Best Dynamic Solver (VBS_dyn): The optimal combination of two algorithms and a single switch point for a specific function-dimension pair.
Key Results
The analysis reveals a significant performance "gold mine" in dynamic switching. Across the entire suite of functions and dimensions, the dynamic approach (VBS_dyn) achieved a median speedup of 1.49x over the best static solvers (VBS_static).
As illustrated in Figure 2, the VBS_dyn (dashed line) consistently maintains a lower Expected Running Time (ERT) than the VBS_static (solid line) across nearly all function IDs. The gains are particularly pronounced in complex, multi-modal functions (F15–F24). For instance, in Function 19 (Grievank-Rosenbrock), the dynamic combination achieved a speedup of 40.5x over the best static solver.
Insights into Algorithm Roles
The study identifies specialized roles for different solvers:
- Starters vs. Finishers: Algorithms like HMLSL excel as "starters" due to rapid initial convergence, while CMA-ES variants are superior "finishers" for high-precision refinement.
- Asymmetric Impact: The choice of the starting algorithm ($A_1$) is generally more critical than the choice of $A_2$. A poor initial explorer can prevent a finisher from ever reaching its effective range.
- Portfolio Efficiency: Significant gains are possible even with a small portfolio of just five representative algorithms (e.g., Nelder-Doerr, DE-Auto, HMLSL), proving that dynAS is practical without requiring an exhaustive library of solvers.
Challenges and Future Directions
While the theoretical potential is clear, several hurdles remain for real-world implementation:
- The Warm-Start Problem: Transitioning between algorithms requires transferring internal states (e.g., populations or covariance matrices) without wasting function evaluations.
- Automated Switch Detection: In practice, the distance to the optimum is unknown. Future systems must trigger switches based on observable "landscape features" or internal algorithm metrics.
- Stochasticity: The inherent randomness of optimization means switch points must be robust to variance across different runs.
Conclusion
Dynamic algorithm selection offers a path to significantly surpass the performance limits of static solvers. By framing dynAS as a stepping stone toward full Dynamic Algorithm Configuration (dynAC), this work provides a roadmap for leveraging existing benchmark data to build more adaptive and efficient optimization systems.
Summary updated