http://www.dagstuhl.de/08051

January 27 – February 1 , 2008, Dagstuhl Seminar 08051

Theory of Evolutionary Algorithms

Organizers

Dirk V. Arnold (Dalhousie University, CA)
Anne Auger (Université Paris Sud, FR)
Jonathan E. Rowe (University of Birmingham, GB)
Carsten Witt (Technical University of Denmark – Lyngby, DK)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available

Summary

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.

Dagstuhl Seminar Series

Classification

  • Artificial Intelligence / Robotics
  • Data Structures / Algorithms / Complexity
  • Optimization / Scheduling
  • Soft Computing / Evol. Algorithms

Keywords

  • Evolutionary Algorithms
  • Theoretical Analysis
  • Optimization Time

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.