Evolution strategy

From Wikipedia, the free encyclopedia

In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It was created in the 1960s and 70s by Ingo Rechenberg and his co-workers, and belongs to the more general class of evolutionary computation or artificial evolution. For a peer-reviewed definition, consult also Scholarpedia's Evolution Strategies.

Evolution strategies use natural problem-dependent representations, 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.

As far as real-valued search spaces are concerned, mutation is normally performed by adding a normally distributed random value to each vector component. The step size or mutation strength (i.e. 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.

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

[edit] See also

• Genetic algorithm
• Evolutionary computation

[edit] References

• Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
• Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
• 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 Dortmund

[edit] External links

• Demo applet of a evolutionary algorithm for solving TSP's and VRPTW problems
• Animation: Optimization of a Two-Phase Flashing Nozzle with an Evolution Strategy. - Animation of the Classical Experimental Optimization 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 and compared to nine other Evolutionary Algorithms.
• 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.