Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Natural evolution strategy
open-in-new
<h2 id="method">Method</h2> <p>The general procedure is as follows: the <i>parameterized</i> search distribution is used to produce a batch of search points, and the <a href="/facts/Fitness_function/Xeoc1I3C">fitness function</a> is evaluated at each such point. The distribution’s parameters (which include <i>strategy parameters</i>) allow the algorithm to adaptively capture the (local) structure of the fitness function. For example, in the case of a <a href="/facts/Gaussian_distribution/UapjjPyQ">Gaussian distribution</a>, this comprises the mean and the <a href="/facts/Covariance_matrix/kLhgjHC6">covariance matrix</a>. From the samples, NES estimates a search gradient on the parameters towards higher expected fitness. NES then performs a gradient ascent step along the <a href="/facts/Information_geometry/sFBShVbT">natural gradient</a>, 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. </p><p>All members of the NES family operate based on the same principles. They differ in the type of <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> and the gradient <a href="/facts/Approximation/LvYHsXzq">approximation</a> 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 the <a href="/facts/Diagonal_matrix/tjIAHrE6">diagonal</a> only. In addition, highly multi-modal search spaces may benefit from more <a href="/facts/Heavy-tailed_distribution/BHLSHPku">heavy-tailed distributions</a> (such as <a href="/facts/Cauchy_distribution/3HS6D3Xk">Cauchy</a>, 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. </p> <h3>Search gradients</h3> <p>Let θ {\displaystyle \theta } denote the parameters of the search distribution π ( x | θ ) {\displaystyle \pi (x\,|\,\theta )} and f ( x ) {\displaystyle f(x)} the fitness function evaluated at x {\displaystyle x} . NES then pursues the objective of maximizing the <i>expected fitness under the search distribution</i> </p> J ( θ ) = E θ [ f ( x ) ] = ∫ f ( x ) π ( x | θ ) d x {\displaystyle J(\theta )=\operatorname {E} _{\theta }[f(x)]=\int f(x)\;\pi (x\,|\,\theta )\;dx} <p>through <a href="/facts/Gradient_ascent/pFFrek0F">gradient ascent</a>. The gradient can be rewritten as </p> ∇ θ J ( θ ) = ∇ θ ∫ f ( x ) π ( x | θ ) d x {\displaystyle \nabla _{\theta }J(\theta )=\nabla _{\theta }\int f(x)\;\pi (x\,|\,\theta )\;dx} = ∫ f ( x ) ∇ θ π ( x | θ ) d x {\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;dx} = ∫ f ( x ) ∇ θ π ( x | θ ) π ( x | θ ) π ( x | θ ) d x {\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;{\frac {\pi (x\,|\,\theta )}{\pi (x\,|\,\theta )}}\;dx} = ∫ [ f ( x ) ∇ θ log π ( x | θ ) ] π ( x | θ ) d x {\displaystyle =\int {\Big [}f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta ){\Big ]}\;\pi (x\,|\,\theta )\;dx} = E θ [ f ( x ) ∇ θ log π ( x | θ ) ] {\displaystyle =\operatorname {E} _{\theta }\left[f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta )\right]} <p>that is, the <a href="/facts/Expected_value/1XV0JKL8">expected value</a> of f ( x ) {\displaystyle f(x)} times the <a href="/facts/Logarithmic_derivative/VL7GIwkl">log-derivatives</a> at x {\displaystyle x} . In practice, it is possible to use the <a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo</a> approximation based on a finite number of λ {\displaystyle \lambda } samples </p> ∇ θ J ( θ ) ≈ 1 λ ∑ k = 1 λ f ( x k ) ∇ θ log π ( x k | θ ) {\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }f(x_{k})\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )} . <p>Finally, the parameters of the search distribution can be updated iteratively </p> θ ← θ + η ∇ θ J ( θ ) {\displaystyle \theta \leftarrow \theta +\eta \nabla _{\theta }J(\theta )} <h3>Natural gradient ascent</h3> <p>Instead of using the plain stochastic gradient for updates, NES follows the natural gradient, which has been shown to possess numerous advantages over the plain (<i>vanilla</i>) gradient, e.g.: </p> <ul><li>the gradient direction is independent of the parameterization of the search distribution</li> <li>the updates magnitudes are automatically adjusted based on uncertainty, in turn speeding convergence on <a href="/facts/Plateau_(mathematics)/deq79bR9">plateaus</a> and ridges.</li></ul> <p>The NES update is therefore </p> θ ← θ + η F − 1 ∇ θ J ( θ ) {\displaystyle \theta \leftarrow \theta +\eta \mathbf {F} ^{-1}\nabla _{\theta }J(\theta )} , <p>where F {\displaystyle \mathbf {F} } is the <a href="/facts/Fisher_information/Q2JLexN9">Fisher information matrix</a>. The Fisher matrix can sometimes be computed exactly, otherwise it is estimated from samples, reusing the log-derivatives ∇ θ log π ( x | θ ) {\displaystyle \nabla _{\theta }\log \pi (x|\theta )} . </p> <h3>Fitness shaping</h3> <p>NES utilizes <a href="/facts/Ranking/9unRtwbc">rank</a>-based fitness shaping in order to render the algorithm more robust, and <i>invariant</i> under monotonically increasing transformations of the fitness function. For this purpose, the fitness of the population is transformed into a set of <a href="/facts/Utility/wlMDG74L">utility</a> values u 1 ≥ ⋯ ≥ u λ {\displaystyle u_{1}\geq \dots \geq u_{\lambda }} . Let x i {\displaystyle x_{i}} denote the ith best individual. Replacing fitness with utility, the gradient estimate becomes </p> ∇ θ J ( θ ) = ∑ k = 1 λ u k ∇ θ log π ( x k | θ ) {\displaystyle \nabla _{\theta }J(\theta )=\sum _{k=1}^{\lambda }u_{k}\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )} . <p>The choice of utility function is a free parameter of the algorithm. </p> <h3>Pseudocode</h3> input: f , θ i n i t {\displaystyle f,\;\;\theta _{init}} 1 repeat 2 for k = 1 … λ {\displaystyle k=1\ldots \lambda } do <i>// λ is the population size</i> 3 draw sample x k ∼ π ( ⋅ | θ ) {\displaystyle x_{k}\sim \pi (\cdot |\theta )} 4 evaluate fitness f ( x k ) {\displaystyle f(x_{k})} 5 calculate log-derivatives ∇ θ log π ( x k | θ ) {\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )} 6 end 7 assign the utilities u k {\displaystyle u_{k}} <i>// based on rank</i> 8 estimate the gradient ∇ θ J ← 1 λ ∑ k = 1 λ u k ⋅ ∇ θ log π ( x k | θ ) {\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )} 9 estimate F ← 1 λ ∑ k = 1 λ ∇ θ log π ( x k | θ ) ∇ θ log π ( x k | θ ) ⊤ {\displaystyle \mathbf {F} \leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k}|\theta )\nabla _{\theta }\log \pi (x_{k}|\theta )^{\top }} <i>// or compute it exactly</i> 10 update parameters θ ← θ + η ⋅ F − 1 ∇ θ J {\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J} <i>// η is the learning rate</i> 11 until stopping criterion is met <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Evolutionary_computation/qXyxPI8j">Evolutionary computation</a></li> <li><a href="/facts/CMA-ES/3zt1fcbJ">Covariance matrix adaptation evolution strategy (CMA-ES)</a></li></ul> <h2 id="bibliography">Bibliography</h2> <ul><li>D. Wierstra, T. Schaul, J. Peters and J. Schmidhuber (2008). <a href="http://www.idsia.ch/~tom/publications/nes.pdf">Natural Evolution Strategies</a>. IEEE Congress on Evolutionary Computation (CEC).</li> <li>Y. Sun, D. Wierstra, T. Schaul and J. Schmidhuber (2009). <a href="http://www.idsia.ch/~tom/publications/ssng.pdf">Stochastic Search using the Natural Gradient</a>. International Conference on Machine Learning (ICML).</li> <li>T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra and J. Schmidhuber (2010). <a href="http://www.idsia.ch/~tom/publications/xnes.pdf">Exponential Natural Evolution Strategies</a>. Genetic and Evolutionary Computation Conference (GECCO).</li> <li>T. Schaul, T. Glasmachers and J. Schmidhuber (2011). <a href="http://www.idsia.ch/~tom/publications/snes.pdf">High Dimensions and Heavy Tails for Natural Evolution Strategies</a>. Genetic and Evolutionary Computation Conference (GECCO).</li> <li>T. Schaul (2012). <a href="http://www.idsia.ch/~tom/publications/nesproof.pdf">Natural Evolution Strategies Converge on Sphere Functions</a>. Genetic and Evolutionary Computation Conference (GECCO).</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://schaul.site44.com/nes.html">Collection of NES implementations in different languages</a></li></ul>