MA-BBOB: A Problem Generator for Black-Box Optimization Using Affine Combinations and Shifts

ACM Transactions on Evolutionary Learning and Optimization, vol. 5, pp. 1–19

Abstract

Choosing a set of benchmark problems is often a key component of any empirical evaluation of iterative optimization heuristics. In continuous, single-objective optimization, several sets of problems have become widespread, including the well-established BBOB suite. While this suite is designed to enable rigorous benchmarking, it is also commonly used for testing methods such as algorithm selection, which the suite was never designed around. We present the MA-BBOB function generator, which uses the BBOB suite as component functions in an affine combination. In this work, we describe the full procedure to create these affine combinations and highlight the tradeoffs of several design decisions, specifically the choice to place the optimum uniformly at random in the domain. We then illustrate how this generator can be used to gain more low-level insight into the function landscapes through the use of exploratory landscape analysis. Finally, we show a potential use-case of MA-BBOB in generating a wide set of training and testing data for algorithm selectors. Using this setup, we show that the basic scheme of using a set of landscape features to predict the best algorithm does not lead to optimal results, and that an algorithm selector trained purely on the BBOB functions generalizes poorly to the affine combinations.

Authors 4

1. Diederick Vermetten Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   LIACS - Leiden Institute of Advanced Computer Science [Leiden] (Niels Bohrweg 1 2333 CA Leiden - Netherlands)

2. Furong Ye Aachen

   Leiden University · Chinese Academy of Sciences · Institute of Software

   Affiliation as printed

   Institute of Software, Chinese Academy of Science, Beijing, China

   LIACS - Leiden Institute of Advanced Computer Science [Leiden] (Niels Bohrweg 1 2333 CA Leiden - Netherlands)

3. Thomas Bäck Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, Leiden, The Netherlands

   LIACS - Leiden Institute of Advanced Computer Science [Leiden] (Niels Bohrweg 1 2333 CA Leiden - Netherlands)

4. Carola Doerr

   Centre National de la Recherche Scientifique · Sorbonne Université · LIP6

   Affiliation as printed

   Sorbonne Université, CNRS, LIP6, Paris, France