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.

See also

• Genetic algorithm
• Evolutionary computation

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.

Research centers

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

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.