World Library  
Flag as Inappropriate
Email this Article

Evolution strategy

Article Id: WHEBN0000940033
Reproduction Date:

Title: Evolution strategy  
Author: World Heritage Encyclopedia
Language: English
Subject: Genetic algorithm, Evolutionary computation, Evolution window, Human-based evolutionary computation, CMA-ES
Collection: Evolutionary Algorithms, Stochastic Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Evolution strategy

In computer science, an evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.

Contents

  • History 1
  • Methods 2
  • See also 3
  • References 4
  • Bibliography 5
  • Research centers 6

History

The 'evolution strategy' optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and their co-workers.

Methods

Evolution strategies use natural problem-dependent representations, and primarily mutation and selection, as search operators. In 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 resulting algorithm is therefore invariant with respect to monotonic transformations of the objective function. The simplest evolution strategy operates on a population of size two: the current point (parent) and the result of its mutation. Only if the mutant's fitness is at least as good as the parent one, 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 (1 , λ)-ES the best mutant becomes the parent of the next generation while the current parent is always disregarded. For some of these variants, proofs of linear convergence (in a stochastic sense) have been derived on unimodal objective functions.[1][2]

Contemporary derivatives of evolution strategy often use a population of μ parents and also recombination as an additional operator, called (μ/ρ+, λ)-ES. This makes them less prone to get stuck in local optima.[3]

See also

References

  1. ^ Auger, A. (2005). "Convergence results for the (1,λ)-SA-ES using the theory of φ-irreducible Markov chains". Theoretical Computer Science (Elsevier) 334 (1-3): 35–69.  
  2. ^ Jägersküpper, J. (2006). "How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms". Theoretical Computer Science (Elsevier) 361 (1): 38–56.  
  3. ^ Hansen, N.; S. Kern (2004). "Evaluating the CMA Evolution Strategy on Multimodal Test Functions". Parallel Problem Solving from Nature - PPSN VIII. Springer. pp. 282–291.  

Bibliography

  • 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 Algorithm Engineering (Ls11) – University of Dortmund
  • Collaborative Research Center 531 – University of Dortmund
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.