Dagstuhl Seminar 08051
Theory of Evolutionary Algorithms
( Jan 27 – Feb 01, 2008 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/08051
Organizers
- Dirk Arnold (Dalhousie University, CA)
- Anne Auger (Université Paris Sud, FR)
- Jonathan Rowe (University of Birmingham, GB)
- Carsten Witt (Technical University of Denmark - Lyngby, DK)
Contact
Impacts
- Crossover can provably be useful in evolutionary computation : article : pp. 17-33 - Doerr, Benjamin; Happ, Edda; Klein, Christian - Amsterdam : Elsevier, 2012 - (Theoretical computer science : 425. 2012, pp. 17-33).
- More effective crossover operators for the all-pairs shortest path problem : article : pp. 12-26 - Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine - Amsterdam : Elsevier, 2013 - (Theoretical computer science : 471. 2013, 1).
- Representation Invariant Genetic Operators : article : pp. 635-660 - Rowe, Jonathan E.; Vose, Michael D.; Wright, Alden H. - Cambridge : MIT Press, 2010 - (Evolutionary Computation : 18. 2010, 4 : pp. 635-660). DOI: 10.1162/EVCO_a_00007.
Evolutionary algorithms (EAs) are randomised heuristics for search and optimisation that are based on principles derived from natural evolution. Mutation, recombination, and selection are iterated with the goal of driving a population of candidate solutions toward better and better regions of the search space. Since the underlying idea is easy to grasp and almost no information about the problem to be optimised is necessary in order to apply it, EAs are widely used in many practical disciplines, mainly in computer science and engineering.
It is a central goal of theoretical investigations of EAs to assist practitioners with the tasks of selecting and designing good strategy variants and operators. Due to the rapid pace at which new strategy variants and operators are being proposed, theoretical foundations of EAs still lag behind practice. However, EA theory has gained much momentum over the last few years and has made numerous valuable contributions to the field of evolutionary computation.
EA theory today consists of a wide range of different approaches. Run-time analysis, facet-wise analysis that concentrates on the one-step behaviour of EAs (e.g., the well-known schema theory), analysis of the dynamics of EAs, and systematic empirical analysis all consider different aspects of EA behaviour. Moreover, they employ different methods and tools for attaining their goals, such as Markov chains, infinite population models, or ideas based on statistical mechanics or population dynamics.
The focus of the 2006 Dagstuhl Seminar on the ``Theory of Evolutionary Algorithms'' was to find common ground among the multitude of theoretical approaches and identify open questions central to the field as a whole. In the ensuing discussions during the seminar it became clear that the existence of a wide variety of approaches can be considered evidence of the richness of the field, and that each stream has its own raison d'\^etre. For example, rigorous analysis yields exact results, but can only deal with relatively simple problems. Purely experimental analysis can deal with much more complicated problems, but does not generalise well.
The goals of the 2008 seminar were twofold. The first goal was to gain a systematic understanding of what the capabilities and limitations of the different methodological approaches are, and how they can assist and complement each other. The second goal was to address some of the central open questions identified during the previous seminar, and to establish what the various theoretical approaches can contribute to answering them with a focus on issues related to design and analysis of EAs. For situations where a complete theoretical analysis is out of reach, the goal was to establish a rigorous framework for empirical studies.
The seminar brought together 47 researchers from nine countries, and from across the spectrum of EA theory. Talks were arranged into eight sessions, grouped loosely around common themes, such as hardness and complexity, multi-objective optimisation, coevolution, and continuous optimisation.
Many of the presentations and discussions were dedicated to identifying the limitations of the various approaches, shedding light on their complementarity, and arriving at a wider consent with regard to advantages and disadvantages of the different techniques. A new theme that had been largely absent from previous Dagstuhl seminars on the ``Theory of Evolutionary Algorithms'' and that recurred again and again during the present seminar was a discussion of how experimental work can complement and inspire theoretical analysis. Further themes that were discussed and that are expected to have an impact on future research are the adaptation of mutation distributions in continuous search spaces, and how tools for investigating the stability of Markov chains can be used for the analysis of adaptive algorithms. Finally, important steps were made toward the goal of applying the tools and techniques that have been developed for the runtime analysis of evolutionary algorithms to other modern search heuristics, such as ant colony optimisation and swarm intelligence approaches.
Besides the presentations, and as at past Dagstuhl seminars on ``Theory of Evolutionary Algorithms'', fruitful and stimulating discussions among varying groups of participants occurred throughout the week. The Dagstuhl seminars are firmly established in the community as a biannual event, and we hope to be able to build on this success and continue to promote discussions between researchers in different areas of EA theory at further workshops in the future.
- Dirk Arnold (Dalhousie University, CA) [dblp]
- Anne Auger (Université Paris Sud, FR) [dblp]
- Thomas Bartz-Beielstein (FH Köln, DE) [dblp]
- Hans-Georg Beyer (Fachhochschule Vorarlberg, AT) [dblp]
- Yossi Borenstein (University of Essex, GB)
- Jürgen Branke (University of Warwick, GB) [dblp]
- Dimo Brockhoff (ETH Zürich, CH) [dblp]
- Anthony Bucci (Icosystem, US)
- Kenneth A. De Jong (George Mason University - Fairfax, US) [dblp]
- Benjamin Doerr (MPI für Informatik - Saarbrücken, DE) [dblp]
- Anton V. Eremeev (Sobolev Institute of Mathematics - Omsk, RU) [dblp]
- Steffen Finck (Fachhochschule Vorarlberg, AT)
- Olivier Francois (TIMC Laboratory, FR)
- Tobias Friedrich (MPI für Informatik - Saarbrücken, DE) [dblp]
- Nikolaus Hansen (University of Paris South XI, FR) [dblp]
- Jun He (University of Birmingham, GB) [dblp]
- Holger H. Hoos (University of British Columbia - Vancouver, CA) [dblp]
- Christian Igel (Ruhr-Universität Bochum, DE) [dblp]
- Jens Jägersküpper (TU Dortmund, DE)
- Thomas Jansen (TU Dortmund, DE) [dblp]
- William B. Langdon (University of Essex, GB) [dblp]
- Nicholas Freitag McPhee (University of Minnesota - Morris, US)
- Alexander Melkozerov (Fachhochschule Vorarlberg, AT)
- Silja Meyer-Nieberg (Universität der Bundeswehr - München, DE) [dblp]
- Boris S. Mitavskiy (University of Sheffield, GB)
- Frank Neumann (MPI für Informatik - Saarbrücken, DE) [dblp]
- Pietro S. Oliveto (University of Birmingham, GB) [dblp]
- Riccardo Poli (University of Essex, GB) [dblp]
- Elena Popovici (Icosystem, US)
- Adam Prugel-Bennett (University of Southampton, GB) [dblp]
- Colin Reeves (Coventry University, GB)
- J. Neal Richter (Montana State University - Bozeman, US)
- Jonathan Rowe (University of Birmingham, GB) [dblp]
- Günter Rudolph (TU Dortmund, DE) [dblp]
- Lothar M. Schmitt (The University of Aizu, JP)
- Hans-Paul Schwefel (TU Dortmund, DE) [dblp]
- Jonathan L. Shapiro (University of Manchester, GB) [dblp]
- Dirk Sudholt (TU Dortmund, DE) [dblp]
- Olivier Teytaud (Université Paris Sud, FR) [dblp]
- Lothar Thiele (ETH Zürich, CH) [dblp]
- Ingo Wegener (TU Dortmund, DE)
- Darrell Whitley (Colorado State University, US) [dblp]
- R. Paul Wiegand (University of Central Florida - Orlando, US)
- Carsten Witt (Technical University of Denmark - Lyngby, DK) [dblp]
- Alden Wright (University of Montana - Missoula, US)
- Xin Yao (University of Birmingham, GB) [dblp]
- Eckart Zitzler (ETH Zürich, CH)
Related Seminars
- 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 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 22081: Theory of Randomized Optimization Heuristics (2022-02-20 - 2022-02-25) (Details)
- Dagstuhl Seminar 24271: Theory of Randomized Optimization Heuristics (2024-06-30 - 2024-07-05) (Details)
Classification
- artificial intelligence / robotics
- data structures / algorithms / complexity
- optimization / scheduling
- soft computing / evol. algorithms
Keywords
- Evolutionary Algorithms
- Theoretical Analysis
- Optimization Time
