More Web Proxy on the site http://driver.im/

research-article

Towards dynamic algorithm selection for numerical black-box optimization: investigating BBOB as a use case

Authors:

Diederick Vermetten,

Carola DoerrAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 654 - 662

https://doi.org/10.1145/3377930.3390189

Published: 26 June 2020 Publication History

Abstract

One of the most challenging problems in evolutionary computation is to select from its family of diverse solvers one that performs well on a given problem. This algorithm selection problem is complicated by the fact that different phases of the optimization process require different search behavior. While this can partly be controlled by the algorithm itself, there exist large differences between algorithm performance. It can therefore be beneficial to swap the configuration or even the entire algorithm during the run. Long deemed impractical, recent advances in Machine Learning and in exploratory landscape analysis give hope that this dynamic algorithm configuration (dynAC) can eventually be solved by automatically trained configuration schedules. With this work we aim at promoting research on dynAC, by introducing a simpler variant that focuses only on switching between different algorithms, not configurations. Using the rich data from the Black Box Optimization Benchmark (BBOB) platform, we show that even single-switch dynamic Algorithm selection (dynAS) can potentially result in significant performance gains. We also discuss key challenges in dynAS, and argue that the BBOB-framework can become a useful tool in overcoming these.

References

[1]

Anne Auger, Dimo Brockhoff, Nikolaus Hansen, Tea Tušar, and Konstantinos Varelas. 2020. Data from BBOB-workshops and competitions on 24 noiseless functions. https://coco.gforge.inria.fr/doku.php?id=algorithms-bbob.

[2]

Anne Auger and Nikolaus Hansen. 2005. A restart CMA evolution strategy with increasing population size. In Proc. of Congress on Evolutionary Computation (CEC'05). 1769--1776.

[3]

Nacim Belkhir, Johann Dréo, Pierre Savéant, and Marc Schoenauer. 2017. Per instance algorithm configuration of CMA-ES with limited budget. In Proc. of Genetic and Evolutionary Computation (GECCO'17). ACM, 681--688.

Digital Library

[4]

André Biedenkapp, H. Furkan Bozkurt, Frank Hutter, and Marius Lindauer. 2019. Towards White-box Benchmarks for Algorithm Control. CoRR abs/1906.07644 (2019). arXiv:1906.07644 http://arxiv.org/abs/1906.07644

[5]

Ilhem Boussaïd, Julien Lepagnot, and Patrick Siarry. 2013. A survey on optimization metaheuristics. Information Sciences 237 (2013), 82--117.

Digital Library

[6]

Edmund K. Burke, Michel Gendreau, Matthew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. 2013. Hyper-heuristics: a survey of the state of the art. JORS 64, 12 (2013), 1695--1724.

[7]

Luc Devroye. 1972. The compound random search. Ph.D. dissertation, Purdue Univ., West Lafayette, IN.

[8]

Benjamin Doerr, Mahmoud Fouz, Martin Schmidt, and Magnus Wahlström. 2009. BBOB: Nelder-Mead with resize and halfruns. In Proc. of Genetic and Evolutionary Computation (GECCO'09), Franz Rothlauf (Ed.). ACM, 2239--2246.

Digital Library

[9]

Carola Doerr, Hao Wang, Furong Ye, Sander van Rijn, and Thomas Bäck. 2018. IOHprofiler: A Benchmarking and Profiling Tool for Iterative Optimization Heuristics. arXiv e-prints:1810.05281 (Oct. 2018). arXiv:1810.05281 https://arxiv.org/abs/1810.05281 The BBOB datasets from [1] are available in the web-based interface of IOHanalyzer at http://iohprofiler.liacs.nl/.

[10]

Agoston Endre Eiben, Robert Hinterding, and Zbigniew Michalewicz. 1999. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3 (1999), 124--141.

Digital Library

[11]

Alexandre Fréchette, Lars Kotthoff, Tomasz P. Michalak, Talal Rahwan, Holger H. Hoos, and Kevin Leyton-Brown. 2016. Using the Shapley Value to Analyze Algorithm Portfolios. In Proc. of the AAAI Conference on Artificial Intelligence. AAAI Press, 3397--3403. http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12495

[12]

Nikolaus Hansen, Anne Auger, Dimo Brockhoff, Dejan Tušar, and Tea Tušar. 2016. COCO: Performance Assessment. arXiv:1605.03560 [cs] (May 2016). http://arxiv.org/abs/1605.03560 arXiv: 1605.03560.

[13]

Nikolaus Hansen, Anne Auger, Raymond Ros, Steffen Finck, and Petr Pošík. 2010. Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In Proc. of Genetic and Evolutionary Computation (GECCO'10). ACM, 1689--1696.

Digital Library

[14]

Nikolaus Hansen and Andreas Ostermeier. 1996. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In CEC. 312--317.

[15]

Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9, 2 (2001), 159--195.

Digital Library

[16]

Anja Janković and Carola Doerr. 2019. Adaptive landscape analysis. In Proc. of Genetic and Evolutionary Computation (GECCO'19). ACM, 2032--2035.

Digital Library

[17]

Pascal Kerschke and Heike Trautmann. 2017. Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning. arXiv preprint arXiv:1711.08921 (2017).

[18]

P. Kerschke and H. Trautmann. 2019. Automated Algorithm Selection on Continuous Black-Box Problems by Combining Exploratory Landscape Analysis and Machine Learning. Evolutionary Computation 27, 1 (2019), 99--127.

Digital Library

[19]

Benjamin Lacroix and John McCall. 2019. Limitations of Benchmark Sets and Landscape Features for Algorithm Selection and Performance Prediction. In Proc. of Genetic and Evolutionary Computation (GECCO'19). Association for Computing Machinery, New York, NY, USA, 261--262.

Digital Library

[20]

Fernando G. Lobo, Cláudio F. Lima, and Zbigniew Michalewicz (Eds.). 2007. Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, Vol. 54. Springer.

Digital Library

[21]

Marco Locatelli and Fabio Schoen. 1999. Random Linkage: a family of acceptance/rejection algorithms for global optimisation. Mathematical Programming 85, 2 (1999).

[22]

Ilya Loshchilov, Marc Schoenauer, and Michele Sèbag. 2013. Bi-Population CMA-ES Agorithms with Surrogate Models and Line Searches. In Proc. of Genetic and Evolutionary Computation (GECCO'13). Association for Computing Machinery, New York, NY, USA, 1177--1184.

Digital Library

[23]

Katherine Mary Malan and Irene Moser. 2019. Constraint Handling Guided by Landscape Analysis in Combinatorial and Continuous Search Spaces. Evolutionary Computation 27, 2 (2019), 267--289.

Digital Library

[24]

Jorge Maturana, Álvaro Fialho, Frédéric Saubion, Marc Schoenauer, Frédéric Lardeux, and Michèle Sebag. 2012. Adaptive Operator Selection and Management in Evolutionary Algorithms. In Autonomous Search, Youssef Hamadi, Eric Monfroy, and Frédéric Saubion (Eds.). Springer, 161--189.

[25]

Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In Proc. of Genetic and Evolutionary Computation (GECCO'11). ACM, 829--836.

Digital Library

[26]

Mario A. Muñoz, Michael Kirley, and Saman K. Halgamuge. 2015. Exploratory Landscape Analysis of Continuous Space Optimization Problems Using Information Content. IEEE Trans. Evolutionary Computation 19, 1 (2015), 74--87.

Digital Library

[27]

Mario A. Muñoz and Kate Amanda Smith-Miles. 2017. Performance Analysis of Continuous Black-Box Optimization Algorithms via Footprints in Instance Space. Evolutionary Computation 25, 4 (2017).

Digital Library

[28]

Mario A Muñoz, Yuan Sun, Michael Kirley, and Saman K Halgamuge. 2015. Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges. Information Sciences 317 (2015), 224--245.

Digital Library

[29]

Mario Andrés Muñoz Acosta, Michael Kirley, and Kate Smith-Miles. 2018. Reliability of Exploratory Landscape Analysis. (06 2018).

[30]

László Pál. 2013. Benchmarking a hybrid multi level single linkagealgorithm on the bbob noiseless testbed. In Proc. of Genetic and Evolutionary Computation (GECCO'15). 1145--1152.

[31]

Erik Pitzer and Michael Affenzeller. 2012. A Comprehensive Survey on Fitness Landscape Analysis. Springer Berlin Heidelberg, Berlin, Heidelberg, 161--191.

[32]

Ingo Rechenberg. 1973. Evolutionsstrategie. Friedrich Fromman Verlag (Günther Holzboog KG), Stuttgart.

[33]

Michael A. Schumer and Kenneth Steiglitz. 1968. Adaptive step size random search. IEEE Trans. Automat. Control 13 (1968), 270--276.

[34]

Chris Thornton, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. 2013. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. In ACM SIGKDD. ACM, 847--855.

[35]

Sander van Rijn, Carola Doerr, and Thomas Bäck. 2018. Towards an Adaptive CMA-ES Configurator. In PPSN (Lecture Notes in Computer Science), Vol. 11101. Springer, 54--65.

[36]

Sander van Rijn, Hao Wang, Matthijs van Leeuwen, and Thomas Bäck. 2016. Evolving the structure of Evolution Strategies. In SSCI. 1--8.

[37]

Diederick Vermetten, Sander van Rijn, Thomas Bäck, and Carola Doerr. 2019. Online selection of CMA-ES variants. In Proc. of Genetic and Evolutionary Computation (GECCO'19). ACM, 951--959.

Digital Library

[38]

Diederick Vermetten, Hao Wang, Thomas Bäck, and Carola Doerr. 2020. Github repository with Project Data. (2020). https://github.com/Dvermetten/BBOB_DynAS.

[39]

Diederick Vermetten, Hao Wang, Carola Doerr, and Thomas Bäck. 2020. Integrated vs. Sequential Approaches for Selecting and Tuning CMA-ES Variants. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'20). ACM.

Digital Library

[40]

Costas Voglis, Grigoris S. Piperagkas, Konstantinos E. Parsopoulos, Dimitris G. Papageorgiou, and Isaac E. Lagaris. 2012. MEMPSODE: an empirical assessment of local search algorithm impact on a memetic algorithm using noiseless testbed. In Proc. of Genetic and Evolutionary Computation (GECCO'12), Terence Soule and Jason H. Moore (Eds.). ACM, 245--252.

Digital Library

[41]

Costas Voglis, Grigoris S. Piperagkas, Konstantinos E. Parsopoulos, Dimitris G. Papageorgiou, and Isaac E. Lagaris. 2012. MEMPSODE: comparing particle swarm optimization and differential evolution within a hybrid memetic global optimization framework. In Proc. of Genetic and Evolutionary Computation (GECCO'12), Terence Soule and Jason H. Moore (Eds.). ACM, 253--260.

Digital Library

[42]

Lin Xu, Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2012. Evaluating Component Solver Contributions to Portfolio-Based Algorithm Selectors. In Proc. of Theory and Applications of Satisfiability Testing (SAT'12) (Lecture Notes in Computer Science), Vol. 7317. Springer, 228--241.

Digital Library

Cited By

Vermetten DDoerr CWang HKononova ABäck TLi XHandl J(2024)Large-Scale Benchmarking of Metaphor-Based Optimization HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654122(41-49)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654122
Xu TChen HHe JLi XHandl J(2024)Accelerate Evolution Strategy by Proximal Policy OptimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654090(1064-1072)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654090
Korošec PEftimov T(2024)Opt2Vec - A continuous optimization problem representation based on the algorithm's behavior: a case study on problem classificationInformation Sciences10.1016/j.ins.2024.121134(121134)Online publication date: Jul-2024
https://doi.org/10.1016/j.ins.2024.121134
Show More Cited By

Index Terms

Towards dynamic algorithm selection for numerical black-box optimization: investigating BBOB as a use case
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Bio-inspired optimization
    2. Online algorithms

Recommendations

Noiseless functions black-box optimization: evaluation of a hybrid particle swarm with differential operators
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

In this work we evaluate a Particle Swarm Optimizer hybridized with Differential Evolution and apply it to the Black-Box Optimization Benchmarking for noiseless functions (BBOB 2009). We have performed the complete procedure established in this special ...
A stigmergy-based algorithm for black-box optimization: noiseless function testbed
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

In this paper, we present a stigmergy-based algorithm for solving optimization problems with continuous variables, labeled Differential Ant-Stigmergy Algorithm (DASA). The performance of the DASA is evaluated on the set of benchmark problems provided ...
Dynamic partition search algorithm for global numerical optimization

This paper presents a novel evolutionary algorithm entitled Dynamic Partition Search Algorithm (DPSA) for global optimization problems with continuous variables. The DPSA is a population-based stochastic search algorithm in nature, which mainly consists ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Paris Ile de France region

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)3

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vermetten DDoerr CWang HKononova ABäck TLi XHandl J(2024)Large-Scale Benchmarking of Metaphor-Based Optimization HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654122(41-49)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654122
Xu TChen HHe JLi XHandl J(2024)Accelerate Evolution Strategy by Proximal Policy OptimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654090(1064-1072)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654090
Korošec PEftimov T(2024)Opt2Vec - A continuous optimization problem representation based on the algorithm's behavior: a case study on problem classificationInformation Sciences10.1016/j.ins.2024.121134(121134)Online publication date: Jul-2024
https://doi.org/10.1016/j.ins.2024.121134
Andova ACork JVodopija ATušar TFilipič B(2024)Predicting Algorithm Performance in Constrained Multiobjective Optimization: A Tough Nut to CrackApplications of Evolutionary Computation10.1007/978-3-031-56855-8_19(310-325)Online publication date: 3-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-56855-8_19
Bäck TKononova Avan Stein BWang HAntonov KKalkreuth Rde Nobel JVermetten Dde Winter RYe F(2023)Evolutionary Algorithms for Parameter Optimization—Thirty Years LaterEvolutionary Computation10.1162/evco_a_0032531:2(81-122)Online publication date: 1-Jun-2023
https://doi.org/10.1162/evco_a_00325
Vermetten DWang HSim KHart E(2023)To Switch or Not to Switch: Predicting the Benefit of Switching Between Algorithms Based on Trajectory FeaturesApplications of Evolutionary Computation10.1007/978-3-031-30229-9_22(335-350)Online publication date: 9-Apr-2023
https://doi.org/10.1007/978-3-031-30229-9_22
Vermetten DCaraffini Fvan Stein BKononova AWagner M(2022)Using structural bias to analyse the behaviour of modular CMA-ESProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534035(1674-1682)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534035
Nikolikj ATrajanov RCenikj GKorosec PEftimov T(2022)Identifying minimal set of Exploratory Landscape Analysis features for reliable algorithm performance prediction2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870439(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870439
Jankovic AVermetten DKostovska Ade Nobel JEftimov TDoerr C(2022)Trajectory-based Algorithm Selection with Warm-starting2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870222(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870222
Ye FDoerr CBäck TKrawiec K(2021)Leveraging benchmarking data for informed one-shot dynamic algorithm selectionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3459578(245-246)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3459578
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten