This paper explores a novel way to benchmark black-box optimization algorithms by creating "in-between" problems. By using affine combinations (weighted averages) of standard benchmark functions, the authors provide a more granular look at how algorithm performance shifts as landscape properties—like ruggedness or global structure—gradually change.
TL;DR
The authors propose using affine combinations of standard BBOB benchmark functions to create a continuous spectrum of test problems. This approach reveals that algorithm performance doesn't always transition smoothly between problem types and can unmask hidden structural biases in popular optimizers.
What Problem Does This Paper Address?
In the world of numerical optimization, we rely heavily on benchmark suites like the Black-Box Optimization Benchmark (BBOB). These suites consist of discrete functions (e.g., a smooth "Sphere" vs. a highly rugged "Rastrigin"). However, real-world problems rarely fall neatly into these categories.
The gap here is twofold:
- Discrete Benchmarking: We only see performance on "islands" of problem types, missing the "sea" of transitions between them.
- Hidden Biases: Some algorithms perform well on specific benchmarks not because they are superior optimizers, but because they have "structural biases"—for example, they might be hard-coded to search more effectively near the origin $(0,0,...)$, which is where many benchmark optima are located.
Methods
The researchers use affine combinations to bridge these gaps. They define a new function $C$ as a weighted logarithmic mean of two base BBOB functions ($F_1$ and $F_2$):
$$C(x) = \exp(\alpha \log(F_1(x)) + (1-\alpha) \log(F_2(x)))$$
By varying the weight $\alpha$ from 0 to 1, they can smoothly morph one landscape into another.
To evaluate this, they benchmarked five common algorithms:
- PSO (Particle Swarm Optimization)
- DE (Differential Evolution)
- Cobyla (a linear approximation method)
- EMNA (Estimation of Multivariate Normal Algorithm)
- CMA-ES (Covariance Matrix Adaptation Evolution Strategy), including both diagonal and modular variants.
They used the ECDF (Empirical Cumulative Distribution Function) and the AUC (Area Under the Curve) to measure how quickly and reliably algorithms reached target precision levels.
Datasets
The study utilizes the BBOB noiseless suite, which contains 24 fundamental optimization problems. The authors generated new datasets by pairing these 24 functions with each other (and specifically with the $F_1$ Sphere model) across 21 different values of $\alpha$.
Key Insights and Ideas
- Emergent Difficulty: You might assume that a 50/50 mix of an easy and a hard function results in a medium-difficulty problem. The paper shows this isn't always true. Some combinations are significantly harder than either parent function because the conflicting landscape features (e.g., deceptive global structure vs. local ruggedness) negate the search strategies of the algorithms.
- The "Ranking Flip": Algorithm rankings are highly sensitive to $\alpha$. As shown in Figure 5, Cobyla dominates when the landscape is nearly a sphere ($\alpha \approx 0$), but as soon as a small amount of complexity is added, CMA-ES or DE take the lead.
- Visualizing the Morph: Figure 1 illustrates how the global structure of a sphere can be gradually "polluted" by the local optima of a more complex function, providing a visual intuition for why search becomes harder.
- Unmasking Bias: The authors found that Diagonal CMA-ES performed exceptionally well on some problems only when the optimum was at a specific distance from the origin. By shifting optima in their affine combinations, they proved that this "superiority" was actually a result of initialization bias.
Key Results
- Performance Bifurcation: Figure 6 shows that at certain "tipping point" values of $\alpha$, an algorithm's performance becomes highly unstable—solving some instances instantly while failing others entirely. This suggests that standard benchmarking on single instances can be very misleading.
- Algorithm Specialization: The ranking heatmap (Figure 5) provides a clear "map" of algorithm strengths. Cobyla is the specialist for near-spherical landscapes, while DE proves more robust than CMA-ES on highly multimodal landscapes where $\alpha$ is large.
Limitations and Future Work
- Objective Scaling: Different BBOB functions have wildly different output scales (e.g., one might range from 0 to 100, another from 0 to $10^7$). Even with logarithmic weighting, the function with the larger scale can "drown out" the other.
- Instance Generation: The results are sensitive to how BBOB creates "instances" (rotations and translations). The authors suggest that future work needs a more robust way to generate instances that don't introduce their own biases.
- Automated Selection: A promising next step is using this diverse data to train Algorithm Selection Models—AI that can look at a problem's features and automatically pick the best optimizer from a portfolio.
Summary updated