Evolution strategies began in Berlin in the 1960s, when Ingo Rechenberg and Hans-Paul Schwefel optimized the shapes of physical objects in wind-tunnel and other flow experiments by random variation and selection. Unlike genetic algorithms, which grew out of models of adaptation and favored binary strings and crossover, evolution strategies worked directly on real-valued parameters and relied mainly on mutation drawn from a normal distribution. Their central question was how large each mutation should be. Steps that are too small make little progress, and steps that are too large miss improvements nearby, so the right step size changes as the search approaches an optimum.
The field's answers form a sequence. Rechenberg's analysis of simple models led to the 1/5 success rule, which enlarges the step size when many mutations succeed and shrinks it when few do. Schwefel let each individual carry its own step sizes and evolved them along with the solution, an approach called self-adaptation. Hansen and Ostermeier then replaced that randomness with deterministic rules that learn the full covariance of the mutation distribution from the path the search has taken. The result, CMA-ES, is a standard method for difficult continuous optimization problems. Natural evolution strategies later recast the whole approach as gradient ascent on the parameters of the search distribution, which connected it to machine learning and to reinforcement learning at scale.
The methods differ in what they adapt and in what tells them how to adapt it. In ten dimensions, on the ellipsoid with condition number $10^6$ used throughout the topic's experiments:
| Method | Mutation distribution adapted | Signal used | Ellipsoid, $n = 10$ |
|---|---|---|---|
| (1+1)-ES, 1/5 rule | one step size | success rate | not solved in $10^6$ evaluations |
| Self-adaptation, one step size | one step size per individual | selection of the individuals carrying it | not solved in $10^5$ |
| Self-adaptation, $n$ step sizes | axis-parallel ellipsoid | the same | about 11,600 evaluations, $(15/15,100)$ |
| CMA-ES | full covariance and step size | ranked steps and evolution paths | about 5,600 |
| SNES | axis-parallel ellipsoid | natural gradient of expected fitness | about 2,800 |
Rotate the ellipsoid so that its axes no longer match the coordinates, and CMA-ES needs about 5,500 evaluations, the same as before, while SNES no longer reaches the target in $10^5$; individual step sizes are tied to the coordinate axes in the same way. Each article measures its method in detail.
Articles
- The (1+1) ES and the 1/5 success rule: one parent, one Gaussian offspring, Rechenberg's progress-rate analysis, step-size control by success rate, and what linear convergence means, measured on the sphere and an ill-conditioned ellipsoid.
- Plus and comma selection and self-adaptation: plus and comma selection, recombination of real vectors, step sizes that evolve with the solution, and why comma selection helps them adapt.
- CMA-ES: covariance matrix adaptation, evolution paths, step-size control, default parameters and restarts, and its behavior on standard test functions compared with a binary genetic algorithm.
- Natural evolution strategies and evolution strategies for reinforcement learning: search gradients, the natural gradient, the link to CMA-ES, and the scalable evolution strategies used to train neural network policies.
Related topics
Evolution strategies share their history and vocabulary with the rest of evolutionary computation, and their step-size control is a principled answer to the local search trade-offs of hill climbing. They are often used for real-valued problems that genetic algorithms handle through binary encodings, and for weight-only neuroevolution of large networks.
References
- Beyer, H.-G., and Schwefel, H.-P. (2002). Evolution strategies: A comprehensive introduction. Natural Computing, 1(1), 3–52.
- Hansen, N. (2016). The CMA evolution strategy: A tutorial. arXiv:1604.00772.