Abstract
The Black Box Optimization Benchmarking (BBOB) set provides a diverse problem set for continuous optimization benchmarking. At its core lie 24 functions, which are randomly transformed to generate an infinite set of instances. We think this has two benefits: it discourages over adaptation to the benchmark by generating some diversity and it encourages algorithm designs that are invariant to transformations. Using Exploratory Landscape Analysis (ELA) features, one can show that the BBOB functions are not representative of all possible functions. Muñoz and Smith-Miles [15] show that one can generate space-filling test functions using genetic programming. Here we propose a different approach that, while not generating a space-filling function set, is much cheaper. We take affine recombinations of pairs of BBOB functions and use these as additional benchmark functions. This has the advantage that it is trivial to implement, and many of the properties of the resulting functions can easily be derived. Using dimensionality reduction techniques, we show that these new functions “fill the gaps” between the original benchmark functions in the ELA feature space. We therefore believe this is a useful tool since it allows one to span the desired ELA-region from a few well-chosen prototype functions.
Supported by German Federal Ministry of Education and Research in the funding program Forschung an Fachhochschulen under the grant number 13FH007IB6 and German Federal Ministry for Economic Affairs and Climate Action in the funding program Zentrales Innovationsprogramm Mittelstand under the grant number KK5074401BM0.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dietrich, K., Mersmann, O.: Changing function landscape of two dimensional recombinations (2022). https://doi.org/10.5281/zenodo.6456367
Dietrich, K., Mersmann, O.: Exploratory Landscape Analysis Feature Data of Recombinations and noiseless BBOB Instances, pp. 1–15 (2022). https://doi.org/10.5281/zenodo.6456361
Doerr, C., Wang, H., Ye, F., van Rijn, S., Bäck, T.: IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics arxiv.org/abs/1810.05281, October 2018
Hansen, N., Auger, A., Ros, R., Mersmann, O., Tušar, T., Brockhoff, D.: COCO: a platform for comparing continuous optimizers in a black-box setting. Optim. Methods Softw. 36(1), 114–144 (2021). https://doi.org/10.1080/10556788.2020.1808977
Hansen, N., Finck, S., Ros, R., Auger, A.: Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829, Inria (2009). https://hal.inria.fr/inria-00362633
Hooker, J.: Testing heuristics: we have it all wrong. J. Heuristics 1(1), 33–42 (1995). https://doi.org/10.1007/BF02430364
Kerschke, P., Preuss, M., Wessing, S., Trautmann, H.: Detecting funnel structures by means of exploratory landscape analysis. In: GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference, pp. 265–272 (2015). https://doi.org/10.1145/2739480.2754642
Kerschke, P., Trautmann, H.: Comprehensive feature-based landscape analysis of continuous and constrained optimization problems using the R-package Flacco. In: Bauer, N., Ickstadt, K., Lübke, K., Szepannek, G., Trautmann, H., Vichi, M. (eds.) Applications in Statistical Computing. SCDAKO, pp. 93–123. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25147-5_7
Liao, T., Molina, D., Stützle, T.: Performance evaluation of automatically tuned continuous optimizers on different benchmark sets. Appl. Soft Comput. J. 27, 490–503 (2015). https://doi.org/10.1016/J.ASOC.2014.11.006
Lunacek, M., Whitley, D.: The dispersion metric and the CMA evolution strategy. In: GECCO 2006 - Genetic and Evolutionary Computation Conference, vol. 1, pp. 477–484 (2006). https://doi.org/10.1145/1143997.1144085
Marín, J.: How landscape ruggedness influences the performance of real-coded algorithms: a comparative study. Soft Comput. 16, 683–698 (2012). https://doi.org/10.1007/s00500-011-0781-5
Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 829–836 (2011). https://doi.org/10.1145/2001576.2001690
Muñoz, M.A., Kirley, M., Halgamuge, S.K.: Exploratory landscape analysis of continuous space optimization problems using information content. IEEE Trans. Evol. Comput. 19, 74–87 (2015). https://doi.org/10.1109/TEVC.2014.2302006
Muñoz, M.A., Smith-Miles, K.: Performance analysis of continuous black-box optimization algorithms via footprints in instance space. Evol. Comput. 25, 529–554 (2017). https://doi.org/10.1162/EVCO_a_00194
Muñoz, M.A., Smith-Miles, K.: Generating new space-filling test instances for continuous black-box optimization. Evol. Comput. 28, 379–404 (2020). https://doi.org/10.1162/EVCO_A_00262
Owen, A.B.: Scrambling sobol’ and Niederreiter-Xing points. J. Complex. 14(4), 466–489 (1998). https://doi.org/10.1006/jcom.1998.0487
Renau, Q., Doerr, C., Dreo, J., Doerr, B.: Exploratory landscape analysis is strongly sensitive to the sampling strategy. In: Bäck, T., et al. (eds.) PPSN 2020, Part II. LNCS, vol. 12270, pp. 139–153. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58115-2_10
Renau, Q., Dreo, J., Doerr, C., Doerr, B.: Towards explainable exploratory landscape analysis: extreme feature selection for classifying BBOB functions. In: Castillo, P.A., Jiménez Laredo, J.L. (eds.) EvoApplications 2021. LNCS, vol. 12694, pp. 17–33. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-72699-7_2
Santner, T.J., Williams, B.J., Notz, W.I.: The Design and Analysis of Computer Experiments. Springer, New York (2003). https://doi.org/10.1007/978-1-4757-3799-8
Seo, D.I., Moon, B.R.: An information-theoretic analysis on the interactions of variables in combinatorial optimization problems. Evol. Comput. 15, 169–198 (2007). https://doi.org/10.1162/EVCO.2007.15.2.169
Sobol’, I.M.: On the distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7, 86–112 (1967). https://doi.org/10.1016/0041-5553(67)90144-9
Škvorc, U., Eftimov, T., Korošec, P.: Transfer learning analysis of multi-class classification for landscape-aware algorithm selection. Mathematics 10(3) (2022). https://doi.org/10.3390/math10030432
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dietrich, K., Mersmann, O. (2022). Increasing the Diversity of Benchmark Function Sets Through Affine Recombination. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tušar, T. (eds) Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022. Lecture Notes in Computer Science, vol 13398. Springer, Cham. https://doi.org/10.1007/978-3-031-14714-2_41
Download citation
DOI: https://doi.org/10.1007/978-3-031-14714-2_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-14713-5
Online ISBN: 978-3-031-14714-2
eBook Packages: Computer ScienceComputer Science (R0)