Evolution strategy

Evolution strategy

In computer science, 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

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 his 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. doi:10.1016/j.tcs.2004.11.017. 
  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. doi:10.1016/j.tcs.2006.04.004. 
  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. doi:10.1007/978-3-540-30217-9_29. 

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

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Natural evolution strategy — Natural evolution strategies (NES) are a family of numerical optimization algorithms for black box problems. Similar in spirit to evolution strategies, they iteratively update the (continuous) parameters of a search distribution by following the… …   Wikipedia

  • Evolution window — It was observed in evolution strategies that significant progress toward the fitness/objective function s optimum, generally, only can happen in a narrow band of the mutation step size σ. That narrow band is called evolution window.There are… …   Wikipedia

  • Evolution and the Theory of Games — [ISBN 0 521 28884 3] is a 1982 book by the British evolutionary biologist John Maynard Smith on evolutionary game theory. In it, Maynard Smith summarises work on evolutionary game theory that had developed in the 1970s, to which he made several… …   Wikipedia

  • evolution — evolutional, adj. evolutionally, adv. /ev euh looh sheuhn/ or, esp. Brit., /ee veuh /, n. 1. any process of formation or growth; development: the evolution of a language; the evolution of the airplane. 2. a product of such development; something… …   Universalium

  • Evolution of morality — The evolution of morality refers to the emergence of human moral behavior over the course of human evolution. Morality can be defined as a system of ideas about right and wrong conduct. In everyday life, morality is typically associated with… …   Wikipedia

  • Evolution (disambiguation) — In biology, evolution is a change in the inherited traits of a population from one generation to the next.Evolution may also refer to:Film* Evolution (film), a 2001 film by Ivan Reitman * , a 2006 filmTelevision* Evolution (TV series), a… …   Wikipedia

  • Evolution of sexual reproduction — The evolution of sexual reproduction is currently described by several competing scientific hypotheses. All sexually reproducing organisms derive from a common ancestor which was a single celled eukaryotic species[1]. Many protists reproduce… …   Wikipedia

  • Evolution of cetaceans — The approximately 80 modern species in the order Cetacea. A phylogeny showing the …   Wikipedia

  • Evolution of monogamy — Close RelationshipsThe evolution of monogamy refers to the natural history of mating systems in which species reproduce by forming pairs to raise offspring. Animals The evolution of mating systems in animals has received an enormous amount of… …   Wikipedia

  • Strategie d'evolution — Stratégie d évolution Les stratégies d évolution forment une famille de métaheuristiques d optimisation. Elles sont inspirées de la théorie de l évolution, et appartiennent à ce titre à la classe des algorithmes évolutionnaires. La méthode fut… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”