HOME

TheInfoList



OR:

Evolution strategy (ES) from computer science is a subclass of
evolutionary algorithms Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least Approximation, approximately, for which no exact or satisfactory solution methods are k ...
, which serves as an
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
technique. It uses the major genetic operators
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, ...
, recombination and selection of parents.


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, so problem space and search space are identical. In common with
evolutionary algorithms Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least Approximation, approximately, for which no exact or satisfactory solution methods are k ...
, 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. The special feature of the ES is the self-adaptation of mutation step sizes and the
coevolution In biology, coevolution occurs when two or more species reciprocally affect each other's evolution through the process of natural selection. The term sometimes is used for two traits in the same species affecting each other's evolution, as well a ...
associated with it. The ES is briefly presented using the standard form, pointing out that there are many variants. The real-valued chromosome contains, in addition to the n decision variables, n' mutation step sizes _j, where: 1\leq j\leq n'\leq n. Often one mutation step size is used for all decision variables or each has its own step size. Mate selection to produce \lambda offspring is random, i.e. independent of fitness. First, new mutation step sizes are generated per mating by intermediate recombination of the parental _ with subsequent mutation as follows: : '_j = \sigma_j \cdot e^ where \mathcal(0,1) is a
normally distributed In probability theory and statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real number, real-valued random variable. The general form of its probability density function is f(x ...
random variable with mean 0 and standard deviation 1. \mathcal(0,1) applies to all '_j, while \mathcal_j(0,1) is newly determined for each '_j. Next, discrete recombination of the decision variables is followed by a
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, ...
using the new mutation step sizes as standard deviations of the normal distribution. The new decision variables x_j' are calculated as follows: :x_j'=x_j+\mathcal_j(0,_j') This results in an evolutionary search on two levels: First, at the problem level itself and second, at the mutation step size level. In this way, it can be ensured that the ES searches for its target in ever finer steps. However, there is also the danger of being able to skip larger invalid areas in the search space only with difficulty.


Variants

The ES knows two variants of best selection for the generation of the next parent population (\mu - number of parents, \lambda - number of offspring): * (\mu,\lambda ): The \mu best offspring are used for the next generation (usually \mu=\frac). * (\mu +\lambda ): The best are selected from a union of \mu parents and \lambda offspring. Bäck and Schwefel recommend that the value of \lambda should be approximately seven times the \mu, whereby \mu must not be chosen too small because of the strong selection pressure. Suitable values for \mu are application-dependent and must be determined experimentally. The selection of the next generation 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 and oldest evolution strategy \mathit 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. More generally, \lambda mutants can be generated and compete with the parent, called ''(1+\lambda )''. In (1,\lambda ) 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 mathematical analysis, particularly numerical analysis, the rate of convergence and order of convergence of a sequence that converges to a limit are any of several characterizations of how quickly that sequence approaches its limit. These are ...
(in a
stochastic Stochastic (; ) is the property of being well-described by a random probability distribution. ''Stochasticity'' and ''randomness'' are technically distinct concepts: the former refers to a modeling approach, while the latter describes phenomena; i ...
sense) have been derived on unimodal objective functions. 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 strategy, Evolution strategies (ES) are stochastic, Derivative-free optimization, derivative-free methods for numerical ...
). 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 d ...
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. In 2025, Chen et.al. proposed a multi-agent evolution strategy for consensus-based distributed optimization, where a novel step adaptation method is designed to help multiple agents control the step size cooperatively.


See also

* Covariance matrix adaptation evolution strategy (CMA-ES) * Derivative-free optimization *
Evolutionary computation Evolutionary computation from computer science 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 ...
*
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 g ...
* Natural evolution strategy *
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 Darwinism, Darwinian competition can be modelled. It originated in 1973 wi ...


References


Bibliography

* Ingo Rechenberg (1971): ''Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution'' (PhD thesis). Reprinted by Frommann-Holzboog (1973). * Hans-Paul Schwefel (1974): ''Numerische Optimierung von Computer-Modellen'' (PhD thesis). Reprinted by Birkhäuser (1977). * Hans-Paul Schwefel:
Evolution and Optimum Seeking
'. New York: Wiley & Sons 1995. * 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. * 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) – TU Dortmund University
Collaborative Research Center 531 – TU Dortmund University
{{DEFAULTSORT:Evolution Strategy