PPSN 2022: 25 Years of LeadingOnes (and Other Great Ideas)

A Scientific Workshop at PPSN 2022 Revisiting Günter Rudolph's Dissertation

Aims and topics of the workshop: 25 years ago, the doctoral dissertation of Günter Rudolph was published. It contained a huge number of ideas, many of which had a profound influence on the at that time very young field of runtime analyses of evolutionary algorithms. In this scientific workshop, we shall take a new look into this classic work. We will showcase some central ideas and concepts from this dissertation, we will discuss what follow-up works they triggered and what are the current best approaches to these problems today, and we will highlight the main open questions related to these topics.

Target audience: PPSN attendees interested in the topic of the workshop, either from a historical point of view or an interest in current theoretical research on topics started already in Günter Rudolph's dissertation.

Workshop Program

Time Speaker(s) Title
13:30–13:40 Organizers Opening
13:40–14:20 Frank Neumann On the Impact of Function 5.26
14:20–15:00 Dirk Arnold Convergence Properties of Evolutionary Algorithms in Continuous Search Spaces:
A Review of Chapter 6 in Günter Rudolph's Dissertation
Coffee Break
15:15–15:55 Martin Krejca The Precursor of Theory for Discrete EAs: What Happened 25 Years Ago?
15:55–16:35 Michael Emmerich and Ksenia Pereverdieva Design and Convergence Analysis of Evolution Strategies for General Search Spaces:
From Integer Evolution Strategies to the Design of Chemical Plants and Building Designs
16:35–16:45 Organizers Closing


Benjamin Doerr
Tobias Glasmachers
Thomas Jansen
Carsten Witt

Biosketches of the Organizers

Benjamin Doerr is a full professor at the French École Polytechnique. He received his diploma (1998), PhD (2000) and habilitation (2005) in mathematics from Kiel University. His research area is the theory of both problem-specific algorithms and randomized search heuristics like evolutionary algorithms. Major contributions to the latter include runtime analyses for existing evolutionary algorithms, the determination of optimal parameter values, and complexity theoretic results. Benjamin's recent focus is the theory-guided design of novel operators, on-the-fly parameter choices, and whole new evolutionary algorithms, hoping that theory not only explains, but also develops evolutionary computation. Together with Frank Neumann and Ingo Wegener, Benjamin Doerr founded the theory track at GECCO and served as its co-chair 2007-2009 and 2014. He is a member of the editorial boards of "Artificial Intelligence", "Evolutionary Computation", "Natural Computing", "Theoretical Computer Science", and three journals on classic algorithms theory.

Tobias Glasmachers is a professor at the institute for neural computation at the Ruhr-University of Bochum, Germany. He received his PhD from the faculty of Mathematics of the same university in 2008. Afterwards he joined the Swiss AI lab IDSIA for two years, where he was involved in developing natural evolution strategies. In 2012 he returned to Bochum as a junior professor, and he was appointed full professor in 2018. His research interests are optimization and machine learning. In the context of evolutionary algorithms he is interested in algorithm design and analysis of evolution strategies for single- and multi-objective optimization.

Thomas Jansen is Senior Lecturer and Head of the Department of Computer Science at Aberystwyth University (Wales, UK). He received his diploma (1996) and PhD (2000) from the Technical University Dortmund (Germany). He was a Post-Doc at Kenneth De Jong's EClab at the George Mason University (Fairfax, VA; 2001-2002), Junior Professor for Computational Intelligence at the Technical University Dortmund (Germany; 2002-2009) and Stokes Lecturer at University College Cork (Ireland; 2009-2013). His research area is analysis and design of randomised search heuristics including evolutionary algorithms, simulated annealing and artificial immune systems. Jointly with his PhD advisor Ingo Wegener he has developed methods for the runtime analysis of evolutionary algorithms and introduced black-box complexity. He is Associate Editor for Evolutionary Computation (MIT Press) and IEEE Transactions on Evolutionary Computation.

Carsten Witt is a professor at the Technical University of Denmark. He received his diploma and Ph.D. in Computer Science from the Technical University of Dortmund in 2000 and 2004, respectively. Carsten's main research interests are the theoretical aspects of randomized search heuristics, in particular evolutionary algorithms and estimation-of-distribution algorithms. He has given tutorials about the theoretical foundations of nature-inspired search heuristics both at PPSN and GECCO. Carsten Witt is a member of the steering committee of the international Theory of Randomized Search Heuristics (ThRaSH) workshop, which he co-organized both in physical and online format, and a member of the editorial boards of Evolutionary Computation, Artificial Intelligence and Theoretical Computer Science. He has been co-organizer of FOGA 2017 and of Dagstuhl research seminars on evolutionary algorithms and estimation-of-distribution algorithms.