HOME

TheInfoList



OR:

In computer science, an evolution strategy (ES) is an
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
technique based on ideas of
evolution Evolution is change in the heritable characteristics of biological populations over successive generations. These characteristics are the expressions of genes, which are passed on from parent to offspring during reproduction. Variation ...
. It belongs to the general class of
evolutionary computation In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, th ...
or
artificial evolution In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduct ...
methodologies.


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 Hans-Paul Schwefel (born December 4, 1940) is a German computer scientist and professor emeritus at University of Dortmund (now Dortmund University of Technology), where he held the chair of systems analysis from 1985 until 2006. He is one of the ...
and their co-workers.


Methods

Evolution strategies use natural problem-dependent representations, and primarily
mutation In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA or viral replication, m ...
and
selection Selection may refer to: Science * Selection (biology), also called natural selection, selection in evolution ** Sex selection, in genetics ** Mate selection, in mating ** Sexual selection in humans, in human sexuality ** Human mating strateg ...
, 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. For real-valued search spaces, mutation is performed by adding a normally distributed random vector. 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, which are essentially defined by an underlying
covariance matrix In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square matrix giving the covariance between each pair of elements of ...
, are controlled in practice either by self-adaptation or by covariance matrix adaptation (
CMA-ES Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy for numerical optimization. Evolution strategies (ES) are stochastic, derivative-free methods for numerical optimization of non-linear or non-convex continu ...
). When the mutation step is drawn from a
multivariate normal distribution In probability theory and statistics, the multivariate normal distribution, multivariate Gaussian distribution, or joint normal distribution is a generalization of the one-dimensional ( univariate) normal distribution to higher dimensions. One ...
using an evolving
covariance matrix In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square matrix giving the covariance between each pair of elements of ...
, it has been hypothesized that this adapted matrix approximates the inverse Hessian of the search landscape. This hypothesis has been proven for a static model relying on a quadratic approximation. 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 Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
sense) have been derived on unimodal objective functions. Contemporary derivatives of evolution strategy often use a population of μ parents and recombination as an additional operator, called ''(μ/ρ+, λ)-ES''. This makes them less prone to settle in local optima.


See also

* Covariance matrix adaptation evolution strategy (CMA-ES) *
Derivative-free optimization Derivative-free optimization is a discipline in mathematical optimization that does not use derivative information in the classical sense to find optimal solutions: Sometimes information about the derivative of the objective function ''f'' is unav ...
*
Evolutionary computation In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, th ...
*
Genetic algorithm In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to ge ...
*
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 t ...
*
Evolutionary game theory Evolutionary game theory (EGT) is the application of game theory to evolving populations in biology. It defines a framework of contests, strategies, and analytics into which Darwinian competition can be modelled. It originated in 1973 with John M ...


References


Bibliography

* Ingo Rechenberg (1971): ''Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution'' (PhD thesis). Reprinted by Frommann-Holzboog (1973). *
Hans-Paul Schwefel Hans-Paul Schwefel (born December 4, 1940) is a German computer scientist and professor emeritus at University of Dortmund (now Dortmund University of Technology), where he held the chair of systems analysis from 1985 until 2006. He is one of the ...
(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. * M. Emmerich, O.M. Shir, and H. Wang
Evolution Strategies
In: Handbook of Heuristics, 1-31. Springer International Publishing (2018).


Research centers



* ttp://ls11-www.cs.uni-dortmund.de/ Chair of Algorithm Engineering (Ls11) – University of Dortmund
Collaborative Research Center 531 – University of Dortmund
{{DEFAULTSORT:Evolution Strategy Evolutionary algorithms