Theory of Evolutionary Algorithms

Summary

Evolutionary algorithms (EAs) are stochastic optimization methods 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. From a more general perspective, EAs are one instance of bio-inspired search heuristics. Other examples include Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), where the search behaviors of ant colonies or insect swarms inspired a randomized search technique. Since the underlying ideas of bio-inspired search are easy to grasp and easy to apply, EAs and different bio-inspired search heuristics are widely used in many practical disciplines, mainly in computer science and engineering.

It is a central goal of theoretical investigations of search heuristics 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 and other bio-inspired search heuristics 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.

The theory of EAs today consists of a wide range of different approaches. Run-time analysis, schema theory, analyses of the dynamics of EAs, and systematic empirical analysis all consider different aspects of EA behavior. 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. In the most recent seminar, more recent types of bio-inspired search heuristics were discussed. Results regarding the runtime have been generalized from EAs to ACO and PSO. Although the latter heuristics follow a different design principle than EAs, the theoretical analyses reveal surprising similarities in terms of the underlying stochastic process. New analytic approaches were also surveyed.

The goals of the 2010 Dagstuhl seminar were twofold. The first goal was to discuss the potential and limitations of a unified theory of all types of bio-inspired search heuristics with focus on how to analyze the runtime of estimation-of-distribution algorithms, which themselves can be considered as a generalized model of ACO, PSO and EAs. The second goal of the seminar was to bridge the gap with the classical optimization community.

Fruitful and stimulating discussions among varying groups of participants occurred throughout the week of the Dagstuhl seminar on ``Theory of Evolutionary Algorithms''. Besides the presentations, the unconventional format of the working parties was successful in provoking discussions and stimulating the exchange of new ideas. The spotlight talks provided a great opportunity for new PhD students to introduce themselves to the community. The Dagstuhl seminars are firmly established in the community as 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.