Evolution strategy

From Wikipedia, the free encyclopedia

In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. It belongs to a more general class of evolutionary computation.

Evolution strategies use real-vectors as coding representation, and primarily mutation and selection as search operators. As common with evolutionary algorithms, the operators are applied in a loop. An iteration of the loop is called a generation. The sequence of generations is continued until a termination criterion is met.

Mutation is normally performed by adding a normally distributed random value to each vector component. The step size or mutation strength (ie. the standard deviation of the normal distribution) is often governed by self-adaptation (see evolution window). Individual step sizes for each coordinate or correlations between coordinates are either governed by self-adaptation or by covariance matrix adaptation (CMA-ES).

The (environmental) selection in evolution strategies is deterministic and only based on the fitness rankings, not on the actual fitness values. The simplest ES operates on a population of size two: the current point (parent) and the result of its mutation. Only if the mutant has a higher fitness than the parent, it becomes the parent of the next generation. Otherwise the mutant is disregarded. This is a (1+1)-ES. More generally, λ mutants can be generated and compete with the parent, called (1+λ)-ES. In a (1,λ)-ES the best mutant becomes the parent of the next generation while the current parent is always disregarded.

Contemporary derivatives of evolution strategy often use a population of μ parents and also recombination as an additional operator (called (μ/ρ+,λ)-ES). This is believed to make them less prone to get stuck in local optima. Because of using recombination, these algorithms might also be classified as real-coded genetic algorithms.

Contents 1 See also 2 References 3 Research Centers 4 External links

[edit] See also

• Genetic Algorithm

[edit] References

• H.-G. Beyer and H.-P. Schwefel. Evolution Strategies: A Comprehensive Introduction. Journal Natural Computing, 1(1):3-52, 2002.
• Hans-Georg Beyer: The Theory of Evolution Strategies: Springer April 27, 2001.
• Hans-Paul Schwefel: Evolution and Optimum Seeking: New York: Wiley & Sons 1995.
• Ingo Rechenberg: Evolutionsstrategie '94. Stuttgart: Frommann-Holzboog 1994.
• J. Klockgether and H. P. Schwefel (1970). Two-Phase Nozzle And Hollow Core Jet Experiments. AEG-Forschungsinstitut. MDH Staustrahlrohr Project Group. Berlin, Federal Republic of Germany. Proceedings of the 11th Symposium on Engineering Aspects of Magneto-Hydrodynamics, Caltech, Pasadena, Cal., 24.-26.3. 1970.

[edit] Research Centers

• Bionics & Evolutiontechnique at the Technical University Berlin
• Chair of Systems Analysis (Ls11) - University of Dortmund
• Collaborative Research Center 531 - University of Dormund

[edit] External links

• Animation: Optimisation of a Two-Phase Flashing Nozzle with an Evolution Strategy. - Animation of the Classical Experimental Optmization of a two phase flashing nozzle made by Professor Hans-Paul Schwefel and J. Klockgether. The result was shown at the Proceedings of the 11th Symposium on Engineering Aspects of Magneto-Hydrodynamics, Caltech, Pasadena, Cal., 24.-26.3. 1970.
• Bionics – Building on Bio-Evolution. By Ingo Rechenberg - A Brief Tutorial.
• CMA Evolution Strategy - a contemporary variant where the complete covariance matrix of the multivariate normal mutation distribution is adapted.
• Comparison of Evolutionary Algorithms on a Benchmark Function Set - The 2005 IEEE Congress on Evolutionary Computation: Session on Real-Parameter Optimization - The CMA-ES (Covariance Matrix Adaptation Evolution Strategy) applied in a benchmark function set.
• Evolution Strategies - A brief description.
• Evolution Strategies Animations - Some interesting animations and real world problems (such as format of lenses, bridges configurations, etc) solved through Evolution Strategies.
• Evolution Strategy in Action - 10 ES-Demonstrations. By Michael Herdy and Gianino Patone - 10 problems solved through Evolution Strategies.
• Evolutionary Algorithms Demos - There are some applets with Evolution Strategies and Genetic Algorithms that the user can manipulate to solve problems. Very interesting for a comparison between the two Evolutionary Algorithms.
• Evolutionary Car Racing Videos - The application of Evolution Strategies to evolve cars' behaviours.
• EvoWeb. - The European Network of Excellence in Evolutionary Computing.
• Learning To Fly: Evolving Helicopter Flight Through Simulated Evolution - A (10+23)-ES applied to evolve a helicopter flight controller.
• Professor Hans-Paul Schwefel talks to EvoNews - An interview with Professor Hans-Paul Schwefel, one of the Evolution Strategy pioneers.