June 30 to July 5, 2013, Dagstuhl Seminar 13271
Theory of Evolutionary Algorithms
Benjamin Doerr (MPI für Informatik – Saarbrücken, DE)
Nikolaus Hansen (INRIA Saclay – Île-de-France, FR)
Jonathan L. Shapiro (University of Manchester, GB)
L. Darrell Whitley (Colorado State University, US)
1 / 2 >
For support, please contact
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.
In recent years, new methods have been developed at a rapid pace. Some of the advancements for continuous optimization methods have been enabled by focusing on how evolutionary algorithms can be compared and contrasted to more traditional gradient based methods. Arguably, evolutionary algorithms are one of the best methods now available for derivative-free optimization (DFO) on higher dimensional problems.
Another area of rapid recent advancement is in the area of run-time analysis for evolutionary algorithms applied to discrete optimization problems. Here, some techniques could be successfully borrowed from traditional algorithm analysis, but many new techniques were necessary to understand the more complicated stochastic processes arising from nature-inspired algorithms.
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 has become the leading meeting for EA theorists in the world.
This year, the following topics had the particular attention of organizers, speakers both of overview and specialized talks, and participants of the breakout sessions (also called "working parties" or "working groups" in other Dagstuhl seminars). A brief summary of the breakout sessions can be found in Section 4.
Advanced Runtime Analysis Methods. One difficulty common to the analysis of most randomized search heuristics is that, while in principle these are nothing more than randomized algorithms, their particular nature disallows the use of many methods used in the classical analysis of the randomized algorithms community. The particular difficulties include dealing with populations (instead of a single search point as in other local optimizers) or recombination (instead of mutation only, which creates a search point close to the parent). Both the fitness level method and various variants of the drift analysis method were greatly improved in the last three years to cope with these difficulties. Also, the fixed budget view on runtime analysis was recognized as an alternative way of analyzing the performance of randomized search heuristics, and may better reflect performance indicators used by practitioners.
Complexity Theory for Randomized Search Heuristics. Complexity theory is one of the corner stones of classical computer science. Informally speaking, the black-box complexity of a problem is the number of fitness evaluations needed to find its solution. Unfortunately, it turns out that some notoriously hard problems like the clique problem in graphs have a ridiculously small black-box complexity. In their 2010 GECCO award winning paper, Lehre and Witt presented a promising way out of this dilemma. They introduced a restricted version of black-box complexity that on the one hand still covers most known evolutionary approaches, but on the other hand forbids the counter-intuitive tricks that led to the undesired results in the first approach. Following up on this work, several variants of black-box complexity have been suggested. During the seminar, in particular during the breakout session on this topic, these were intensively discussed, new variations have been proposed, both from the theory perspective and from practitioners, and a new approach was presented explaining how to gain new and better evolutionary algorithms from black-box complexity results.
Theory of Natural Evolutionary Algorithms. Recently, the idea of conducting a natural gradient descent in the space of sampling probability distributions has been introduced in evolution strategies. The idea offers a very principled design technique for search algorithms that sample from a parameterized distribution. Comparable to classical deterministic optimization, an iterated gradient descent is performed on the distribution parameters. The remarkable difference is that the curvature information on this space is known a priori. A natural descent that is based on the inner product from the Fisher information matrix uses this curvature and is comparable to a Newton method. This new and promising idea is lesser-known and largely unexploited for evolutionary computation. This is a completely new topic for this seminar series, but it is related to previous work on Covariance Matrix Adaptation.
Theory for Multi-Objective Optimization. One of the most explosive areas of growth both within evolutionary algorithms and in derivative-free optimization is multi-objective optimization. This is because good evolutionary algorithms now exist that can cover complex Pareto fronts for 2 to 12 objectives. This gives practitioners a much more informative view of the trade-offs that are possible when facing a multi-objective decision, and can also reveal trade-offs that otherwise would never be seen: for example if we are wishing to minimize cost and maximize quality, there can be "knees" at specific locations on the Pareto front where one might dramatically improve quality while incurring only a slight increase in cost. This is why multi-objective optimization methods that "map" the Pareto front are exciting. Yet, there is not a great deal of work on the theory of multi-objective optimization. Evolutionary algorithms are the method of choice for derivative-free multi-objective optimization and there is a great need to bring together theoreticians who are interested in evolutionary algorithms and those practitioners who are developing multi-objective optimization methods. This was another new topic for this seminar series.
Landscape Analysis. Landscape Analysis is an old idea: one should be able to compute features of a search space that can be used to guide search. One of the problems is that the kinds of metrics that one might wish to know about usually take exponential time to compute exactly. However, recent work has shown that some NP-hard problems (TSP, Graph Coloring, MAXSAT) can be decomposed to the point that Fourier methods can be used to exactly compute statistic moments of the search space (and subspaces of the search space) in polynomial time; these computation normally require exponential time for arbitrary problems. How can this information be used to guide the search, and to potentially replace heuristics with more exact information? New results in this area open new opportunities for exploration at this seminar series.
Dagstuhl Seminar Series
- 10361: "Theory of Evolutionary Algorithms" (2010)
- 08051: "Theory of Evolutionary Algorithms" (2008)
- 06061: "Theory of Evolutionary Algorithms " (2006)
- 04081: "Theory of Evolutionary Algorithms" (2004)
- 02031: "Theory of Evolutionary Algorithms" (2002)
- 00071: "Theory of Evolutionary Algorithms" (2000)
- Evolutionary Algorithms
- Search Heuristics
- Evolutionary algorithms
- Bio-inspired search heuristics
- Theoretical analysis
- Complexity analysis