Using Affine Combinations of BBOB Problems for Performance Assessment

Diederick Vermetten, Furong Ye, Carola DoerrarXiv 2023 · arXiv

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:

  1. Discrete Benchmarking: We only see performance on "islands" of problem types, missing the "sea" of transitions between them.
  2. 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.
Figure 1: Evolution of the landscape (log-scaled function-values) of the affine combination between F21 (𝛼= 1) and F1 (𝛼= 0), instance 1 for both functions, for varying 𝛼. The red circle highlights the location of the global optimum.
  • 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.
Figure 6: ERT per instance for three algorithms on the affine combinations between F10 (𝛼= 1) and F1 (𝛼= 0), for selected values of 𝛼. Each dot corresponds to the ERT calculated based on 5 runs on 1 instance, for a total of 10 instances.
  • 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.
Ranking of top algorithms across different function combinations and alpha values

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

Abstract

Benchmarking plays a major role in the development and analysis of optimization algorithms. As such, the way in which the used benchmark problems are defined significantly affects the insights that can be gained from any given benchmark study. One way to easily extend the range of available benchmark functions is through affine combinations between pairs of functions. From the perspective of landscape analysis, these function combinations smoothly transition between the two base functions. In this work, we show how these affine function combinations can be used to analyze the behavior of optimization algorithms. In particular, we highlight that by varying the weighting between the combined problems, we can gain insights into the effects of added global structure on the performance of optimization algorithms. By analyzing performance trajectories on more function combinations, we also show that aspects such as the scaling of objective functions and placement of the optimum can greatly impact how these results are interpreted.
BibTeX
@misc{vermetten2023using,
  author = {Diederick Vermetten and Furong Ye and Carola Doerr},
  title = {{Using Affine Combinations of BBOB Problems for Performance Assessment}},
  year = {2023},
  eprint = {2303.04573},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.04573},
}

Loading related content...

Figure