Part ofa series on the
Evolutionary algorithm
Chromosome Fitness function Genetic operator Crossover Mutation Selection Population model
Genetic algorithm (GA)
Chromosome Clonal selection algorithm Fly algorithm Genetic fuzzy systems Genetic memory Schema Promoter based GA
Genetic programming (GP)
Cartesian GP Linear GP Gene expression programming Grammatical evolution Multi expression programming
Differential evolution
Evolution strategy
Evolutionary programming
Related topics
Cellular EA Cultural algorithm Effective fitness Evolutionary computation Gaussian adaptation Grammar induction Evolutionary multimodal optimization Memetic algorithm Neuroevolution
v t e

This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(March 2015) (Learn how and when to remove this message)

Natural evolution strategies (NES) are a family ofnumerical optimization algorithms forblack box problems. Similar in spirit toevolution strategies, they iteratively update the (continuous) parameters of asearch distribution by following the natural gradient towards higher expected fitness.

The general procedure is as follows: theparameterized search distribution is used to produce a batch of search points, and thefitness function is evaluated at each such point. The distribution’s parameters (which includestrategy parameters) allow the algorithm to adaptively capture the (local) structure of the fitness function. For example, in the case of aGaussian distribution, this comprises the mean and thecovariance matrix. From the samples, NES estimates a search gradient on the parameters towards higher expected fitness. NES then performs a gradient ascent step along thenatural gradient, a second order method which, unlike the plain gradient, renormalizes the update with respect to uncertainty. This step is crucial, since it prevents oscillations, premature convergence, and undesired effects stemming from a given parameterization. The entire process reiterates until a stopping criterion is met.

All members of the NES family operate based on the same principles. They differ in the type ofprobability distribution and the gradientapproximation method used. Different search spaces require different search distributions; for example, in low dimensionality it can be highly beneficial to model the full covariance matrix. In high dimensions, on the other hand, a more scalable alternative is to limit the covariance to thediagonal only. In addition, highly multi-modal search spaces may benefit from moreheavy-tailed distributions (such asCauchy, as opposed to the Gaussian). A last distinction arises between distributions where we can analytically compute the natural gradient, and more general distributions where we need to estimate it from samples.

Let${\displaystyle \theta }$ denote the parameters of the search distribution${\displaystyle \pi (x|\theta )}$ and${\displaystyle f(x)}$ the fitness function evaluated at${\displaystyle x}$. NES then pursues the objective of maximizing theexpected fitness under the search distribution

${\displaystyle J(\theta )={\mathrm{E}}_{\theta }[f(x)]=\int f(x)\pi (x|\theta )dx}$

throughgradient ascent. The gradient can be rewritten as

${\displaystyle {\mathrm{\nabla }}_{\theta }J(\theta )={\mathrm{\nabla }}_{\theta }\int f(x)\pi (x|\theta )dx}$

${\displaystyle =\int f(x){\mathrm{\nabla }}_{\theta }\pi (x|\theta )dx}$

${\displaystyle =\int f(x){\mathrm{\nabla }}_{\theta }\pi (x|\theta )\frac{\pi (x|\theta )}{\pi (x|\theta )}dx}$

${\displaystyle =\int [f(x){\mathrm{\nabla }}_{\theta }\log \pi (x|\theta )]\pi (x|\theta )dx}$

${\displaystyle ={\mathrm{E}}_{\theta }\left[f(x){\mathrm{\nabla }}_{\theta }\log \pi (x|\theta )\right]}$

that is, theexpected value of${\displaystyle f(x)}$ times thelog-derivatives at${\displaystyle x}$. In practice, it is possible to use theMonte Carlo approximation based on a finite number of${\displaystyle \lambda }$ samples

${\displaystyle {\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{\lambda }\sum _{k=1}^{\lambda }f(x_k){\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta )}$.

Finally, the parameters of the search distribution can be updated iteratively

${\displaystyle \theta \leftarrow \theta +\eta {\mathrm{\nabla }}_{\theta }J(\theta )}$

Instead of using the plain stochastic gradient for updates, NESfollows thenatural gradient, which has been shown to possess numerous advantages over the plain (vanilla) gradient, e.g.:

• the gradient direction is independent of the parameterization of the search distribution
• the updates magnitudes are automatically adjusted based on uncertainty, in turn speeding convergence onplateaus and ridges.

The NES update is therefore

${\displaystyle \theta \leftarrow \theta +\eta {\mathbf{F}}^{-1}{\mathrm{\nabla }}_{\theta }J(\theta )}$,

where${\displaystyle \mathbf{F}}$ is theFisher information matrix.The Fisher matrix can sometimes be computed exactly, otherwise it is estimated from samples, reusing the log-derivatives${\displaystyle {\mathrm{\nabla }}_{\theta }\log \pi (x|\theta )}$.

NES utilizesrank-based fitness shaping in order to render thealgorithm more robust, andinvariant under monotonicallyincreasing transformations of the fitness function. For this purpose, the fitness of the population is transformed into a set ofutility values${\displaystyle u_1\ge \cdots \ge u_{\lambda }}$. Let${\displaystyle x_i}$ denote the i^th best individual.Replacing fitness with utility, the gradient estimate becomes

${\displaystyle {\mathrm{\nabla }}_{\theta }J(\theta )=\sum _{k=1}^{\lambda }{u}_k{\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta )}$.

The choice of utility function is a free parameter of the algorithm.

input:${\displaystyle f,{\theta }_{init}}$1repeat   2for${\displaystyle k=1\dots \lambda }$do//λ is the population size       3draw sample${\displaystyle x_k\sim \pi (\cdot |\theta )}$       4evaluate fitness${\displaystyle f(x_k)}$       5calculate log-derivatives${\displaystyle {\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta )}$       6end   7assign the utilities${\displaystyle u_k}$// based on rank   8estimate the gradient${\displaystyle {\mathrm{\nabla }}_{\theta }J\leftarrow \frac{1}{\lambda }\sum _{k=1}^{\lambda }{u}_k\cdot {\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta )}$   9estimate${\displaystyle \mathbf{F}\leftarrow \frac{1}{\lambda }\sum _{k=1}^{\lambda }{\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta ){\mathrm{\nabla }}_{\theta }\log \pi (x_k|\theta {)}^{\mathrm{\top }}}$// or compute it exactly    10update parameters${\displaystyle \theta \leftarrow \theta +\eta \cdot {\mathbf{F}}^{-1}{\mathrm{\nabla }}_{\theta }J}$//η is the learning rate11until stopping criterion is met

• Evolutionary computation
• Covariance matrix adaptation evolution strategy (CMA-ES)

• D. Wierstra, T. Schaul, J. Peters and J. Schmidhuber (2008).Natural Evolution Strategies. IEEE Congress on Evolutionary Computation (CEC).
• Y. Sun, D. Wierstra, T. Schaul and J. Schmidhuber (2009).Stochastic Search using the Natural Gradient. International Conference on Machine Learning (ICML).
• T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra and J. Schmidhuber (2010).Exponential Natural Evolution Strategies. Genetic and Evolutionary Computation Conference (GECCO).
• T. Schaul, T. Glasmachers and J. Schmidhuber (2011).High Dimensions and Heavy Tails for Natural Evolution Strategies. Genetic and Evolutionary Computation Conference (GECCO).
• T. Schaul (2012).Natural Evolution Strategies Converge on Sphere Functions. Genetic and Evolutionary Computation Conference (GECCO).

• Collection of NES implementations in different languages

• Evolution strategy
• Stochastic optimization

• Articles lacking in-text citations from March 2015
• All articles lacking in-text citations
• Articles with example pseudocode