Theory of Evolutionary Algorithms

Summary

The 2006 Dagstuhl Seminar "Theory of Evolutionary Algorithms'' carried forward a series of Dagstuhl seminars that started in 2000 and has become an established event in the community. In the week from from 05.02.2006 to 10.02.2006, 56 researchers from 12 countries discussed their recent work and recent trends in evolutionary computation.

Evolutionary algorithms (EAs) are randomized search heuristics. Introduced in the 60s and havinf come to great popularity in the 80s, they have been applied successfully in many different areas. Borrowing ideas from natural evolution, these algorithms operate on a population (multiset) of candidate solutions to a task. Promising candidates are selected from the population based on their fitness (objective function value) to become parents. Offspring are generated as variants of parents by means of stochastic crossover and mutation operators. The population for the next generation is chosen from parents and offspring, and the process then repeats until some stopping criterion is met.  A wealth of different EAs have been developed which vary and embellish this basic theme, including the use of stochastic operators adapted to the search space and task, sophisticated methods for adapting parameters during a run, co-evolutionary paradigms, and explicit estimation of distributions.

Evolutionary algorithm theory is three decades old, but only recently has theory migrated to provably correct foundations. In addition, the vast majority of practitioners are collectively generating EA variants at a rate which far outpaces the speed with which the comparatively few theoreticians can analyze them. Making the situation worse, what most practitioners say they want - an inexpensive answer for how best to optimize - is in general impossible to achieve. All of this has contributed to a chasm between proven theoretical results and evolutionary algorithms as applied in practice.

Evolutionary algorithm theory is comprised of diverse approaches from various perspectives having differing objectives.  Facet-wise analyses concentrating on one-step behavior of EAs (schema theory being the best known approach of this kind), analyses based on Markov chains, infinite population models, heuristic analysis borrowing ideas from statistical mechanics, run time analysis in the spirit of the analysis of randomized algorithms, and other approaches, have been developed separately and almost independently.