Randomized optimization heuristics (ROHs) are general-purpose solvers that are frequently applied for discrete or continuous optimization when other classes of solvers fail or are not applicable. Typical examples of ROHs include genetic algorithms, evolution strategies, and estimation-of-distribution algorithms (EDAs). Since ROHs are not designed with a proof or analysis in mind, their theoretical analysis is a particularly challenging endeavor. Yet, their practical success, extremely wide applicability, and growing relevance in many domains in industry and academic research push for progress in their understanding. This Dagstuhl Seminar is part of a very successful Dagstuhl Seminar series with the goal of driving this research area forward.

Over the span of more than two decades, the theoretical analysis of ROHs has made significant progress, going from simple settings to evermore complex scenarios. This advance allows us to tackle highly relevant topics that seemed out of reach before. In this seminar, we will focus on three such topics, for which our understanding is still limited, namely, (1) constraint handling, (2) multivariate EDAs, and (3) stochastic approximation and Markov chain stability analysis. In order to approach these problems from multiple angles, we aim to bring together top researchers from inside the ROH community and from related fields. This should result in a vibrant mixture of different expertise, allowing each participant of the seminar to learn about new topics, to participate in insightful discussions, and to potentially start promising collaborations.

Constraint handling is a classic topic in optimization with a theory-practice gap: Many real-world problems have constraints, while many algorithms and nearly all existing theoretical analyses are limited to unconstrained search spaces. In ROHs, the main route to optimization in the presence of constraints is to equip proven algorithms with additional constraint handling mechanisms. This is analogous to turning a gradient-based optimization algorithm into an interior-point solver by means of the barrier method. However, other communities like gradient-based and derivative-free optimization have different approaches to constraint handling.

EDAs constitute an important class of ROHs. In contrast to classical ROHs, which maintain an explicit multi-set of solutions, EDAs evolve a probabilistic model of the search space. Over the last years, EDAs have received growing interest from the theoretical ROH community. Still, to this date, all theoretical insights for EDAs refer to algorithms that build their probabilistic model based on the assumption that the problem variables are independent from each other (so-called univariate models). This is far from how EDAs are applied in practice, where these algorithms are capable of modeling complex (multivariate) interactions among the problem variables.

In the continuous domain, the main challenge is to analyze adaptive algorithms where the distribution for sampling candidate solutions is adapted in each iteration, using advanced mechanisms. In the past few years, tremendous theoretical progress was achieved to analyze step-size adaptive algorithms. Those results were proven using different approaches: finding a Lyapunov function in the state variables of the algorithm that satisfies a drift condition, using an ordinary differential equation (ODE) method, as well as analyzing the stability of underlying Markov chains. This progress was possible thanks to developing new theoretical tools that take into account the specificity of adaptive evolution strategies.

As with each seminar of this series, we are looking forward to exciting exchanges among researchers from the various areas invited, which has been instrumental in the past for substantial progress and unification in our field and beyond. With this foundation, this seminar offers a great opportunity to initiate collaborations connecting ROHs to neighboring fields that could drastically reduce the gap between theory and practice.

Creative Commons BY 4.0

Anne Auger, Tobias Glasmachers, Martin S. Krejca, and Johannes Lengler

Please log in to DOOR to see more details.

• Sumit Adak (Technical University of Denmark - Lyngby, DK) [dblp]
• Denis Antipov (University of Adelaide, AU) [dblp]
• Dirk Arnold (Dalhousie University - Halifax, CA) [dblp]
• Asma Atamna (Ruhr-Universität Bochum, DE) [dblp]
• Anne Auger (INRIA Saclay - Palaiseau, FR) [dblp]
• Dimo Brockhoff (INRIA Saclay - Palaiseau, FR) [dblp]
• Alexandre Chotard (Calais University, FR) [dblp]
• Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
• Carlos M. Fonseca (University of Coimbra, PT) [dblp]
• Stephan Frank (Ruhr-Universität Bochum, DE)
• Oskar Girardin (Ecole Polytechnique - Palaiseau, FR)
• Armand Gissler (Ecole Polytechnique - Palaiseau, FR) [dblp]
• Tobias Glasmachers (Ruhr-Universität Bochum, DE) [dblp]
• Andreia P. Guerreiro (INESC-ID - Lisbon, PT) [dblp]
• Nikolaus Hansen (Inria & Institut Polytechnique de Paris - Palaiseau, FR) [dblp]
• Mario Alejandro Hevia Fajardo (University of Birmingham, GB) [dblp]
• Thomas Jansen (Aberystwyth University, GB) [dblp]
• Alexander Jungeilges (Ruhr-Universität Bochum, DE)
• Kathrin Klamroth (Universität Wuppertal, DE) [dblp]
• Timo Kötzing (Hasso-Plattner-Institut, Universität Potsdam, DE) [dblp]
• Oswin Krause (University of Copenhagen, DK) [dblp]
• Martin S. Krejca (Ecole Polytechnique - Palaiseau, FR) [dblp]
• Per Kristian Lehre (University of Birmingham, GB) [dblp]
• Tristan Marty (Ecole Polytechnique - Palaiseau, FR)
• Daiki Morinaga (University of Tsukuba, JP) [dblp]
• Frank Neumann (University of Adelaide, AU) [dblp]
• Andre Opris (Universität Passau, DE) [dblp]
• Aishwarya Radhakrishnan (Hasso-Plattner-Institut, Universität Potsdam, DE) [dblp]
• Jonathan Rowe (University of Birmingham, GB) [dblp]
• Günter Rudolph (TU Dortmund, DE) [dblp]
• Thomas Sauerwald (University of Cambridge, GB) [dblp]
• Jonathan L. Shapiro (University of Manchester, GB) [dblp]
• Dirk Sudholt (Universität Passau, DE) [dblp]
• Andrew M. Sutton (University of Minnesota - Duluth, US) [dblp]
• Kento Uchida (Yokohama National University, JP) [dblp]
• Vanessa Volz (CWI - Amsterdam, NL) [dblp]
• Carsten Witt (Technical University of Denmark - Lyngby, DK) [dblp]
• Christine Zarges (Aberystwyth University, GB) [dblp]
• Weijie Zheng (Harbin Institute of Technology - Shenzhen, CN) [dblp]