research-article

Theory-inspired parameter control benchmarks for dynamic algorithm configuration

Authors:

André Biedenkapp,

Martin S. Krejca,

Carola DoerrAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 766 - 775

https://doi.org/10.1145/3512290.3528846

Published: 08 July 2022 Publication History

Abstract

It has long been observed that the performance of evolutionary algorithms and other randomized search heuristics can benefit from a non-static choice of the parameters that steer their optimization behavior. Mechanisms that identify suitable configurations on the fly ("parameter control") or via a dedicated training process ("dynamic algorithm configuration") are thus an important component of modern evolutionary computation frameworks. Several approaches to address the dynamic parameter setting problem exist, but we barely understand which ones to prefer for which applications. As in classical benchmarking, problem collections with a known ground truth can offer very meaningful insights in this context. Unfortunately, settings with well-understood control policies are very rare.

One of the few exceptions for which we know which parameter settings minimize the expected runtime is the LeadingOnes problem. We extend this benchmark by analyzing optimal control policies that can select the parameters only from a given portfolio of possible values. This also allows us to compute optimal parameter portfolios of a given size. We demonstrate the usefulness of our benchmarks by analyzing the behavior of the DDQN reinforcement learning approach for dynamic algorithm configuration.

References

[1]

Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, and Kurt Mehlhorn. 2019. The query complexity of a permutation-based variant of Mastermind. Discrete Applied Mathematics 260 (2019), 28--50.

Digital Library

[2]

Aldeida Aleti and Irene Moser. 2016. A Systematic Literature Review of Adaptive Parameter Control Methods for Evolutionary Algorithms. Comput. Surveys 49 (2016), 56:1--56:35.

[3]

Thomas Bäck. 1998. An Overview of Parameter Control Methods by Self-Adaption in Evolutionary Algorithms. Fundam. Informaticae 35, 1-4 (1998), 51--66.

[4]

Roberto Battiti, Mauro Brunato, and Franco Mascia. 2008. Reactive search and intelligent optimization. Vol. 45. Springer Science & Business Media.

[5]

Roberto Battiti and Paolo Campigotto. 2012. An Investigation of Reinforcement Learning for Reactive Search Optimization. In Autonomous Search, Y. Hamadi, E. Monfroy, and F. Saubion (Eds.). Springer, 131--160.

[6]

André Biedenkapp, H. Furkan Bozkurt, Theresa Eimer, Frank Hutter, and Marius Lindauer. 2020. Dynamic Algorithm Configuration: Foundation of a New Meta-Algorithmic Framework. In Proc. of European Conference on Artificial Intelligence (ECAI'20) (Frontiers in Artificial Intelligence and Applications, Vol. 325). IOS Press, 427--434.

[7]

André Biedenkapp, Nguyen Dang, Martin S. Krejca, Frank Hutter, and Carola Doerr. 2022. Code and data repository of this paper. https://github.com/ndangtt/LeadingOnesDAC.

[8]

Mauro Birattari. 2009. Tuning Metaheuristics - A Machine Learning Perspective. Studies in Computational Intelligence, Vol. 197. Springer.

[9]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal Fixed and Adaptive Mutation Rates for the LeadingOnes Problem. In Proc. of Parallel Problem Solving from Nature (PPSN'10) (LNCS, Vol. 6238). Springer, 1--10.

[10]

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. J. Oper. Res. Soc. 64, 12 (2013), 1695--1724.

[11]

Nathan Buskulic and Carola Doerr. 2021. Maximizing Drift Is Not Optimal for Solving OneMax. Evol. Comput. 29, 4 (2021), 521--541.

[12]

Maxim Buzdalov and Arina Buzdalova. 2015. Can OneMax help optimizing LeadingOnes using the EA+RL method?. In Proc. of Congress on Evolutionary Computation (CEC'15). IEEE, 1762--1768.

[13]

Maxim Buzdalov and Carola Doerr. 2020. Optimal Mutation Rates for the (1 + λ) EA on OneMax. In Proc. of Parallel Problem Solving from Nature (PPSN'20) (LNCS, Vol. 12270). Springer, 574--587.

Digital Library

[14]

Maxim Buzdalov and Carola Doerr. 2021. Optimal static mutation strength distributions for the (1 + λ) evolutionary algorithm on OneMax. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'21). ACM, 660--668.

Digital Library

[15]

Luís Da Costa, Álvaro Fialho, Marc Schoenauer, and Michèle Sebag. 2008. Adaptive operator selection with dynamic multi-armed bandits. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'08). ACM, 913--920.

[16]

Christian Daniel, Jonathan Taylor, and Sebastian Nowozin. 2016. Learning Step Size Controllers for Robust Neural Network Training, See [55].

[17]

Benjamin Doerr. 2019. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science 773 (2019), 115--137.

Digital Library

[18]

Benjamin Doerr and Carola Doerr. 2018. Optimal Static and Self-Adjusting Parameter Choices for the (1+(λ,λ)) Genetic Algorithm. Algorithmica 80 (2018), 1658--1709.

Digital Library

[19]

Benjamin Doerr and Carola Doerr. 2020. Theory of Parameter Control Mechanisms for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 271--321.

[20]

Benjamin Doerr, Carola Doerr, and Johannes Lengler. 2021. Self-Adjusting Mutation Rates with Provably Optimal Success Rules. Algorithmica 83, 10 (2021), 3108--3147. Available at https://arxiv.org/abs/1902.02588.

Digital Library

[21]

Benjamin Doerr, Carola Doerr, and Jing Yang. 2016. k-Bit Mutation with Self-Adjusting k Outperforms Standard Bit Mutation. In Proc. of Parallel Problem Solving from Nature (PPSN'16) (LNCS, Vol. 9921). Springer, 824--834.

[22]

Benjamin Doerr, Carola Doerr, and Jing Yang. 2020. Optimal parameter choices via precise black-box analysis. Theoretical Computer Science 801 (2020), 1--34.

[23]

Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2018. On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'18). ACM, 1015--1022.

Digital Library

[24]

Carola Doerr and Johannes Lengler. 2018. The (1+1) Elitist Black-Box Complexity of LeadingOnes. Algorithmica 80, 5 (2018), 1579--1603. Also available at https://arxiv.org/abs/1604.02355.

Digital Library

[25]

Carola Doerr and Markus Wagner. 2018. Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'18). ACM, 943--950.

Digital Library

[26]

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

[27]

Theresa Eimer, André Biedenkapp, Maximilian Reimer, Steven Adriaensen, Frank Hutter, and Marius Lindauer. 2021. DACBench: A Benchmark Library for Dynamic Algorithm Configuration. In Proc. of International Joint Conference on Artificial Intelligence (IJCAI'21). ijcai.org, 1668--1674.

[28]

Álvaro Fialho, Luís Da Costa, Marc Schoenauer, and Michèle Sebag. 2008. Extreme Value Based Adaptive Operator Selection. In Proc. of Parallel Problem Solving from Nature (PPSN'08) (LNCS, Vol. 5199). Springer, 175--184.

[29]

Álvaro Fialho, Luís Da Costa, Marc Schoenauer, and Michèle Sebag. 2010. Analyzing bandit-based adaptive operator selection mechanisms. Annals of Mathematics and Artificial Intelligence 60 (2010), 25--64.

Digital Library

[30]

George T. Hall, Pietro S. Oliveto, and Dirk Sudholt. 2022. On the impact of the performance metric on eficient algorithm configuration. Artif. Intell. 303 (2022), 103629.

Digital Library

[31]

Assaf Hallak, Dotan Di Castro, and Shie Mannor. 2015. Contextual Markov Decision Processes. CoRR abs/1502.02259 (2015). http://arxiv.org/abs/1502.02259

[32]

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

Digital Library

[33]

Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. 2018. Deep reinforcement learning that matters. In Proceedings of the Thirty-Second Conference on Artificial Intelligence (AAAI'18), Sheila A. McIlraith and Kilian Q. Weinberger (Eds.). AAAI Press, 3207--3214.

[34]

Holger H. Hoos. 2012. Automated Algorithm Configuration and Parameter Tuning. In Autonomous Search, Youssef Hamadi, Éric Monfroy, and Frédéric Saubion (Eds.). Springer, 37--71.

[35]

Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Thomas Stützle. 2009. ParamILS: An Automatic Algorithm Configuration Framework. Journal of Artifcial Intelligence Research 36 (2009), 267--306.

Digital Library

[36]

Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (Eds.). 2019. Automated Machine Learning - Methods, Systems, Challenges. Springer.

[37]

Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu. 2017. Population Based Training of Neural Networks. arXiv:1711.09846 [cs.LG] (2017).

[38]

Giorgos Karafotias, Mark Hoogendoorn, and A.E. Eiben. 2015. Parameter Control in Evolutionary Algorithms: Trends and Challenges. IEEE Transactions on Evolutionary Computation 19 (2015), 167--187.

Digital Library

[39]

Giorgos Karafotias, Selmar K. Smit, and A. E. Eiben. 2012. A Generic Approach to Parameter Control. In Proc. of Applications of Evolutionary Computation (EvoApplications'12) (LNCS, Vol. 7248). Springer, 366--375.

Digital Library

[40]

Eric Kee, Sarah Airey, and Walling Cyre. 2001. An Adaptive Genetic Algorithm. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'01). Morgan Kaufmann, 391--397.

Digital Library

[41]

Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. 2021. A Survey of Generalisation in Deep Reinforcement Learning. arXiv:2111.09794 [cs.LG] (2021).

[42]

Scott Kirkpatrick, C. D. Gelatt, and Mario P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220 (1983), 671--680.

[43]

Michail G. Lagoudakis and Michael L. Littman. 2000. Algorithm Selection using Reinforcement Learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML'00), Pat Langley (Ed.). Morgan Kaufmann Publishers, 511--518.

[44]

Michail G. Lagoudakis and Michael L. Littman. 2001. Learning to Select Branching Rules in the DPLL Procedure for Satisfiability. Electronic Notes in Discrete Mathematics 9 (2001), 344--359.

[45]

Per Kristian Lehre and Carsten Witt. 2012. Black-Box Search by Unbiased Variation. Algorithmica 64 (2012), 623--642.

Digital Library

[46]

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2020. Simple Hyper-Heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for LeadingOnes. Evol. Comput. 28, 3 (2020), 437--461.

Digital Library

[47]

Ilya Loshchilov and Frank Hutter. 2017. SGDR: Stochastic Gradient Descent with Warm Restarts. In Proceedings of the International Conference on Learning Representations (ICLR'17). Published online: iclr.cc.

[48]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature 518, 7540 (2015), 529--533.

[49]

Jack Parker-Holder, Vu Nguyen, and Stephen J. Roberts. 2020. Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits. In Proceedings of the 33rd International Conference on Advances in Neural Information Processing Systems (NeurIPS'20), Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). Curran Associates.

[50]

Jack Parker-Holder, Raghu Rajan, Xingyou Song, André Biedenkapp, Yingjie Miao, Theresa Eimer, Baohe Zhang, Vu Nguyen, Roberto Calandra, Aleksandra Faust, Frank Hutter, and Marius Lindauer. 2022. Automated Reinforcement Learning (AutoRL): A Survey and Open Problems. CoRR abs/2201.03916 (2022). arXiv:2201.03916 https://arxiv.org/abs/2201.03916

[51]

James E. Pettinger and Richard M. Everson. 2002. Controlling Genetic Algorithms with Reinforcement Learning. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'02), W. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. Potter, A. Schultz, J. Miller, E. Burke, and N. Jonoska (Eds.). Morgan Kaufmann Publishers, 692.

[52]

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

[53]

John R. Rice. 1976. The Algorithm Selection Problem. Advances in Computers 15 (1976), 65--118.

[54]

Yoshitaka Sakurai, Kouhei Takada, Takashi Kawabe, and Setsuo Tsuruta. 2010. A Method to Control Parameters of Evolutionary Algorithms by Using Reinforcement Learning. In Proceedings of Sixth International Conference on Signal-Image Technology and Internet-Based Systems (SITIS), K. Yétongnon, A. Dipanda, and R. Chbeir (Eds.). IEEE Computer Society, 74--79.

Digital Library

[55]

D. Schuurmans and M. Wellman (Eds.). 2016. Proceedings of the Thirtieth National Conference on Artificial Intelligence (AAAI'16). AAAI Press.

[56]

Gresa Shala, André Biedenkapp, Noor Awad, Steven Adriaensen, Marius Lindauer, and Frank Hutter. 2020. Learning Step-Size Adaptation in CMA-ES. In Proceedings of the Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN'20) (Lecture Notes in Computer Science). Springer, 691--706.

Digital Library

[57]

Mudita Sharma, Alexandros Komninos, Manuel López-Ibáñez, and Dimitar Kazakov. 2019. Deep Reinforcement Learning-Based Parameter Control in Differential Evolution. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'19). ACM, 709--717.

Digital Library

[58]

Selmar K. Smit and A. E. Eiben. 2009. Comparing parameter tuning methods for evolutionary algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC'09). IEEE, 399--406.

[59]

David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller, and Marius Lindauer. 2021. Learning Heuristic Selection with Dynamic Algorithm Configuration. In Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS'21), H. H. Zhuo, Q. Yang, M. Do, R. Goldman, S. Biundo, and M. Katz (Eds.). AAAI, 597--605.

[60]

Dirk Sudholt. 2013. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 17 (2013), 418--435.

Digital Library

[61]

Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement learning - an introduction. MIT Press. https://www.worldcat.org/oclc/37293240

Digital Library

[62]

Hado van Hasselt, Arthur Guez, and David Silver. 2016. Deep Reinforcement Learning with Double Q-Learning, See [55], 2094--2100.

[63]

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 Conference (GECCO'19). ACM, 951--959.

Digital Library

[64]

Christopher. J. C. H. Watkins. 1989. Learning from Delayed Rewards. Ph. D. Dissertation. King's College, Cambridge, United Kingdom.

[65]

Thomas Weise, Yan Chen, Xinlu Li, and Zhize Wu. 2020. Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. Applied Soft Computing 92 (2020), 106269.

Cited By

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
Chen DBuzdalov MDoerr CDang N(2023)Using Automated Algorithm Configuration for Parameter ControlProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607127(38-49)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607127

Index Terms

Theory-inspired parameter control benchmarks for dynamic algorithm configuration
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Randomized search

Recommendations

Using Automated Algorithm Configuration for Parameter Control
FOGA '23: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Dynamic Algorithm Configuration (DAC) tackles the question of how to automatically learn policies to control parameters of algorithms in a data-driven fashion. This question has received considerable attention from the evolutionary community in recent ...
Configuring irace using surrogate configuration benchmarks
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Over the recent years, several tools for the automated configuration of parameterized algorithms have been developed. These tools, also called configurators, have themselves parameters that influence their search behavior and make them malleable to ...
When parameter tuning actually is parameter control
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

In this paper, we show that sequential parameter optimization (SPO), a method that was designed for (offline) parameter tuning, can be successfully used as a controller for multistart approaches of evolutionary algorithms (EA). We demonstrate this by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 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: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
125
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Chen DBuzdalov MDoerr CDang N(2023)Using Automated Algorithm Configuration for Parameter ControlProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607127(38-49)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607127

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