Comparing Results of 31 Algorithms from the Black-Box Optimization Benchmarking BBOB-2009

Nikolaus Hansen, Xin Yao, Raymond Ros, Steffen Finck, Petr Pošík, Anne Auger, Comparing Results, Inria Saclay, Tao Team2010

TL;DR

This paper presents the results of the Black-Box Optimization Benchmarking (BBOB-2009) for 31 different algorithms tested on 24 noiseless, continuous optimization problems. It reveals that algorithm performance is highly sensitive to factors like dimensionality, function complexity (unimodal vs. multimodal), and the available computational budget, offering valuable insights for algorithm selection in real-world scenarios.

What Problem Does This Paper Address?

In many real-world applications, optimizing a function is challenging because we only have access to function evaluations (a "black-box") and cannot inspect its internal structure (e.g., gradients). Choosing the right optimization algorithm for such problems is difficult, as performance can vary drastically depending on the problem's characteristics. The BBOB-2009 workshop aimed to systematically benchmark a diverse set of algorithms on a standardized suite of problems to understand these dependencies and provide empirical evidence for algorithm selection. This paper specifically focuses on the results for noiseless, continuous optimization problems.

Methods

The core of this work is a large-scale empirical study. Thirty-one different algorithms, ranging from classic methods like Nelder-Mead and BFGS to modern evolutionary algorithms and particle swarm optimizers, were tested. The benchmark suite consisted of 24 noiseless, real-parameter optimization functions. A key aspect of the methodology was the definition of "runtime" not just as the time to find a solution, but the time to reach a specific target precision (defined as the difference between the function value found and the true optimum). To account for the stochastic nature of many algorithms, they simulated a "virtually restarted" algorithm, where multiple runs were combined to estimate the expected runtime. Performance was analyzed across various dimensions (2D, 5D, 10D, 20D, 40D), different target precision levels, and subgroups of functions (unimodal, multimodal, ill-conditioned, etc.).

Datasets

The "datasets" in this context are the 24 noiseless, real-parameter optimization functions used in the BBOB-2009 benchmark suite. These functions are designed to represent a variety of challenges in continuous optimization, including unimodality, multimodality, ill-conditioning, and non-smoothness. The paper does not introduce new benchmark functions but rather uses a well-established set for rigorous comparison.

Key Insights and Ideas

  • No Single Best Algorithm: The most striking insight is that there is no universally superior algorithm. Performance is highly context-dependent.
  • Dimensionality is a Major Hurdle: As the dimensionality of the search space increases, the difficulty of optimization increases dramatically for most algorithms. What works well in 2D can become intractable in 40D.
  • Function Characteristics Matter: Multimodal and non-smooth functions are significantly harder to optimize than unimodal ones, leading to a wider spread in algorithm performance.
  • Budget is Crucial: The available computational budget (number of function evaluations) heavily influences which algorithm is considered "best." Algorithms that are fast for small budgets might not scale well, and vice-versa.
  • Convergence Graphs Tell a Story: The paper demonstrates how empirical cumulative distribution functions (ECDFs) of runtime can effectively visualize algorithm performance across a range of problems and budgets, revealing subtle differences and strengths.

Key Results

  • In low dimensions (2D), algorithms like Nelder-Mead (Doe variant) showed strong performance.
  • For small budgets, algorithms like NEWUOA, MCS, and GLOBAL were competitive.
  • As budgets and dimensions increased, CMA-ES variants (BIPOP-CMA-ES, IPOP-SEP-CMA-ES) and AMALGAM-IDEA variants emerged as top performers, especially on more challenging functions.
  • Even the best algorithms struggled with multimodal functions, solving only about 50% of problems within a significant budget (10^5 D evaluations) to a precision of 10^-6.
  • The paper provides detailed plots showing the proportion of problems solved within a given budget for each algorithm, allowing for direct comparison.

Limitations and Future Work

  • Noiseless Assumption: This study focuses on noiseless functions. Real-world problems often have noisy evaluations, which can significantly alter algorithm performance and require different strategies.
  • Specific Benchmark Set: While comprehensive, the BBOB-2009 suite represents a specific set of challenges. Performance on these functions may not perfectly translate to all possible real-world optimization problems.
  • Future Work: The authors suggest that these results can serve as a guideline for choosing algorithms for unknown black-box optimization problems. Future work could extend this analysis to noisy scenarios, different types of constraints, or larger-scale problems. The insights gained also pave the way for developing more robust and adaptive optimization algorithms.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@misc{hansen2010comparing,
  author = {Nikolaus Hansen and Xin Yao and Raymond Ros and Steffen Finck and Petr Pošík and Nikolaus Hansen and Anne Auger and Raymond Ros and Steffen Finck and Petr Posik and Comparing Results and Nikolaus Hansen and Inria Saclay and Tao Team and Anne Auger and Raymond Ros and Steffen Finck and Petr Pošík},
  title = {{Comparing Results of 31 Algorithms from the Black-Box Optimization Benchmarking BBOB-2009}},
  year = {2010},
}
Figure