Theory of Evolutionary Algorithms

Motivation

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. Much of this momentum is due to the Dagstuhl seminars on ``Theory of Evolutionary Algorithms'', which have been held biannually since 2000. We want to build on this success and continue to promote discussions between researchers in different areas of the theory of all kinds of bio-inspired search heuristics.

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 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.

Theoretical studies of EAs in continuous domain have recently evoked interest of people working in the field of classical numerical optimization. Although stochastic and deterministic optimization algorithms address optimization of different types of problems---mainly convex and smooth for deterministic algorithms and noisy, multimodal, irregular for stochastic algorithms---the focuses of both fields became closer and closer: on the one hand many hybridizations of stochastic search and gradient-based algorithms have been proposed, on the other hand, derivative-free optimization is now a well- established part of the research in the classical optimization community. For these reasons we think that the proposed Dagstuhl seminar would benefit from discussions with the classical optimization community. In particular, we have invited researchers working on pattern-search algorithms and derivative-free trust-region methods.

The proposed seminar is centered on the cross-fertilization of EAs and other search methods. First, we want to discuss the potential and limitations of a common theory of bio-inspired search heuristics. Open questions like how to analyze the runtime of estimation-of-distribution algorithms, which themselves can be considered as a generalized model of ACO, PSO and EAs will be considered. Second, we want to bridge the gap with the classical optimization community. One focus will be to lay down a basis for a common theory for stochastic optimization in evolutionary algorithms and classical optimization.