Dagstuhl Seminar 22081
Theory of Randomized Optimization Heuristics
( Feb 20 – Feb 25, 2022 )
- Anne Auger (INRIA Saclay - Palaiseau, FR)
- Carlos M. Fonseca (University of Coimbra, PT)
- Tobias Friedrich (Hasso-Plattner-Institut, Universität Potsdam, DE)
- Johannes Lengler (ETH Zürich, CH)
- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)
- Self-adjusting Population Sizes for the (1, λ)-EA on Monotone Functions : article : PPSN 2022 accepted paper - Kaufmann, Marc; Larcher, Maxime; Lengler, Johannes; Zou, Xun - Cornell University : arXiv.org, 2022. - 43 pp..
- Contributions to Dynamic Analysis of Differential Evolution Algorithms - Resende, Lucas; Takahashi, Ricardo H. C. - Cambridge : MIT Press, 2023. - 31 pp. - (Evolutionary Computation ; accepted paper 2023).
- Analysing Equilibrium States for Population Diversity - Lengler, Johannes; Opris, Andre; Sudholt, Dirk - Cornell University : arXiv.org, 2023. - 23 pp..
- Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima - Jorritsma, Joost; Lengler, Johannes; Sudholt, Dirk - Cornell University : arXiv.org, 2023. - 18 pp..
- The Cost of Randomness in Evolutionary Algorithms: Crossover can Save Random Bits : article in EvoCOP 2023: Evolutionary Computation in Combinatorial Optimization - Kneissl, Carlo; Sudholt, Dirk - Berlin : Springer, 2023. - pp 179-194 - (Lecture notes in computer science ; 13987 : article).
- A Proof that Using Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation - Dang, Duc-Cuong; Opris, Andre; Salehi, Bahare; Sudholt, Dirk - Cornell University : arXiv.org, 2023. - 14 pp..
This seminar is part of a biennial seminar series. This year, we focused on connections between classical topics of the community, such as Evolutionary Algorithms and Evolutionary Strategies (EA, ES), Estimation-of-Distribution Algorithms (EDA) and Evolutionary Multi-Objective Optimization (EMO), and related fields like Stochastic Gradient Descent (SGD) and Bayesian Optimization (BO). The mixture proved to be extremely successful. Already the first talk turned into a two hours long, vivid and productive plenary discussion. Participants like Peter Richtarik and Sebastian Stich brought valuable new perspectives from the SGD community, and Mickaël Binois contributed the BO perspective. This yielded some new approaches to long-standing open problems, specifically for a convergence proof of the CMA-ES algorithm on quadratic functions.
Another interesting and fruitful aspect of the seminar was a shift of perspective to search spaces that are under-represented in the community. Traditionally, the search spaces are product spaces, either discrete (especially the n-dimensional hypercube), or continuous (d-dimensional Euclidean space). This year we had some intense discussions in plenum and in working groups on other search spaces, triggered especially by Ekhine Irurozki's presentation on permutation spaces.
Naturally, a big part of the seminar was also devoted to classical topics of the community. Highlights included talks by Benjamin Doerr on the first runtime result for the Non-Dominated Sorting Genetic Algorithm (NSGA-II) and by Tobias Glasmachers on Convergence Analysis of the Hessian Estimation Evolution Strategy (HE-ES). The latter is the first convergence proof for a covariance matrix algorithm that does not truncate the condition number of the estimated covariance matrix. Some interesting new topics were also identified in traditional fields, such as whether we can understand better in which situations adapativity is necessary for efficient optimization by considering k-adaptive query complexity of optimization benchmarks.
Overall, as organizers we were extremely happy with the mix of core community members and researchers from related fields. The connections with the latter were close enough that scientific discussions could (also) happen on technical levels, which is particularly useful since some low-hanging fruits are available from such interchanges. Importantly, the exchange happened between people who would probably not have met each other outside of the Dagstuhl Seminar.
The seminar took place during the peak of the Omicron wave of Covid19, which made planning very difficult. The key step during preparation phase was a survey among the participants a few weeks before the seminar. We asked how likely it was that they could participate in person, and under which circumstances they would prefer which format (in-person or hybrid). The participants signalled us very clearly that they wanted this event to happen, and that they wanted it to happen in person. We want to thank all participants for their support! Other seminars in the week before and after ours had to be cancelled altogether, and this might also have happened to our seminar if not for the determination of our participants.
The seminar was smaller than previous versions, due to corona regulations. Moreover, some participants had to cancel at the last moment because they were corona-positive, or because they had no reliable child care. Especially the latter point can be frustrating, and we hope that Dagstuhl will be able to resume their support for on-site child care in the future. On the positive side, the intensity of the seminar more than made up for the smaller size, and might even have been due to the smaller number of participants.
Finally, we want to thank Dagstuhl for their great support, both financially and to their great staff. We could always feel that it was their top priority to help us, and we are greatly indebted for the support!
Anne Auger, Carlos M Fonseca, Tobias Friedrich, Johannes Lengler
Optimization is at the core of many applications in academia or industry. At the heart of an optimization problem is a search space and one or more objective functions to be optimized. In practical applications, objective functions are often not explicitly known, and therefore cannot be written analytically. Instead, they are available to the optimizer as a black-box. In those situations, exact optimization methods such as (integer) linear programming, semi-definite programming, etc., cannot be applied. Instead, one needs to resort to black-box or gray-box methods. Among those, randomized optimization heuristics (ROHs) are often the methods of choice when objective function gradients are not available, when the objective functions are not convex, are subject to noise or uncertainty, or when one needs to optimize several conflicting objectives. In this last case, one talks about multiobjective optimization, a field where ROHs are successful because they allow the Pareto front to be approximated as a whole in contrast to more classical approaches based on objective aggregation that find a single solution at a time.
The field of ROHs, including evolutionary algorithms (EAs), shares some common ground with the related field of Machine Learning (ML). Learning is underlying many important algorithms such as Estimation-of-Distribution Algorithms (EDAs), Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES), and Linkage-Tree Genetic Algorithms, with several components of those algorithms strongly connected to (or using) machine learning techniques such as hierarchical clustering and expectation maximization algorithms. Also, optimization is an important component of machine learning for training neural networks or for hyperparameter tuning, which is a typical black-box problem.
Theoretical analysis of ROH helps to quantify the performance of different methods on different fitness landscapes and classes of functions in order to improve the understanding of the algorithms, compare them, and get more insights into the influence of different components and parameters. Important progress has been made in the past years to understand more and more complex algorithms that are increasingly closer to those used in practice. Yet, crucial aspects are still missing, such as a better understanding of the dynamics of set-based optimization methods in the context of multiobjective optimization, being able to analyze algorithms that learn associations between variables, both in continuous and discrete domains, as well as the corresponding parameter adaptation mechanisms. Those share some common ground with stochastic gradient descent (SGD) algorithms and will be a focus topic of the Dagstuhl Seminar.
In this context, the overall goal of this Dagstuhl Seminar is to drive research in theory of ROHs towards analyzing more and more complex methods that are closer to state-of-the-art ROHs and, specifically, methods that have some impact outside the Evolutionary Computation domain. In addition to specialists in the theory of ROHs, researchers with expertise in the design of EDAs, adaptive Evolution Strategies and evolutionary multiobjective optimization (EMO) algorithms, but also expert researchers from derivative free optimization, Bayesian optimization, and optimization for machine learning, including adaptive stochastic gradient descent techniques are invited.
- Mickaël Binois (INRIA - Sophia Antipolis, FR) [dblp]
- Alexandre Chotard (Calais University, FR) [dblp]
- Duc-Cuong Dang (University of Southampton, GB) [dblp]
- Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Carola Doerr (Sorbonne University - Paris, FR) [dblp]
- Carlos M. Fonseca (University of Coimbra, PT) [dblp]
- Armand Gissler (Ecole Polytechnique - Palaiseau, FR)
- Tobias Glasmachers (Ruhr-Universität Bochum, DE) [dblp]
- Andreia P. Guerreiro (INESC-ID - Lisboa, PT)
- Nikolaus Hansen (INRIA Saclay - Palaiseau, FR) [dblp]
- Ekhine Irurozki (Telecom Paris, FR) [dblp]
- Martin S. Krejca (Sorbonne University - Paris, FR) [dblp]
- Johannes Lengler (ETH Zürich, CH) [dblp]
- Xiaoyue Li (Hasso-Plattner-Institut, Universität Potsdam, DE)
- Peter Richtarik (KAUST - Thuwal, SA) [dblp]
- Günter Rudolph (TU Dortmund, DE) [dblp]
- Sebastian U. Stich (CISPA - Saarbrücken, DE) [dblp]
- Dirk Sudholt (Universität Passau, DE) [dblp]
- Andrew M. Sutton (University of Minnesota - Duluth, US) [dblp]
- Ricardo Takahashi (Federal University of Minas Gerais-Belo Horizonte, BR)
- Elizabeth Wanner (CEFET - Belo Horizonte, BR) [dblp]
- Dagstuhl Seminar 00071: Theory of Evolutionary Algorithms (2000-02-13 - 2000-02-18) (Details)
- Dagstuhl Seminar 02031: Theory of Evolutionary Algorithms (2002-01-13 - 2002-01-18) (Details)
- Dagstuhl Seminar 04081: Theory of Evolutionary Algorithms (2004-02-15 - 2004-02-20) (Details)
- Dagstuhl Seminar 06061: Theory of Evolutionary Algorithms (2006-02-05 - 2006-02-10) (Details)
- Dagstuhl Seminar 08051: Theory of Evolutionary Algorithms (2008-01-27 - 2008-02-01) (Details)
- Dagstuhl Seminar 10361: Theory of Evolutionary Algorithms (2010-09-05 - 2010-09-10) (Details)
- Dagstuhl Seminar 13271: Theory of Evolutionary Algorithms (2013-06-30 - 2013-07-05) (Details)
- Dagstuhl Seminar 15211: Theory of Evolutionary Algorithms (2015-05-17 - 2015-05-22) (Details)
- Dagstuhl Seminar 17191: Theory of Randomized Optimization Heuristics (2017-05-07 - 2017-05-12) (Details)
- Dagstuhl Seminar 19431: Theory of Randomized Optimization Heuristics (2019-10-20 - 2019-10-25) (Details)
- Dagstuhl Seminar 24271: Theory of Randomized Optimization Heuristics (2024-06-30 - 2024-07-05) (Details)
- Neural and Evolutionary Computing
- black-box optimization
- evolutionary and genetic algorithms
- stochastic gradient descent
- randomized search algorithms
- theoretical computer science
- derivative-free optimization