- Source: 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 the natural gradient towards higher expected fitness.
Method
The general procedure is as follows: the parameterized search distribution is used to produce a batch of search points, and the fitness function is evaluated at each such point. The distribution’s parameters (which include strategy parameters) allow the algorithm to adaptively capture the (local) structure of the fitness function. For example, in the case of a Gaussian distribution, this comprises the mean and the covariance matrix. From the samples, NES estimates a search gradient on the parameters towards higher expected fitness. NES then performs a gradient ascent step along the natural 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 of probability distribution and the gradient approximation 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 diagonal only. In addition, highly multi-modal search spaces may benefit from more heavy-tailed distributions (such as Cauchy, 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.
= Search gradients
=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 expected fitness under the search distribution
J
(
θ
)
=
E
θ
[
f
(
x
)
]
=
∫
f
(
x
)
π
(
x
|
θ
)
d
x
{\displaystyle J(\theta )=\operatorname {E} _{\theta }[f(x)]=\int f(x)\;\pi (x\,|\,\theta )\;dx}
through gradient ascent. The gradient can be rewritten as
∇
θ
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]}
that is, the expected value of
f
(
x
)
{\displaystyle f(x)}
times the log-derivatives at
x
{\displaystyle x}
. In practice, it is possible to use the Monte Carlo approximation based on a finite number of
λ
{\displaystyle \lambda }
samples
∇
θ
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 )}
.
Finally, the parameters of the search distribution can be updated iteratively
θ
←
θ
+
η
∇
θ
J
(
θ
)
{\displaystyle \theta \leftarrow \theta +\eta \nabla _{\theta }J(\theta )}
= Natural gradient ascent
=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 (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 on plateaus and ridges.
The NES update is therefore
θ
←
θ
+
η
F
−
1
∇
θ
J
(
θ
)
{\displaystyle \theta \leftarrow \theta +\eta \mathbf {F} ^{-1}\nabla _{\theta }J(\theta )}
,
where
F
{\displaystyle \mathbf {F} }
is the Fisher information matrix.
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 )}
.
= Fitness shaping
=NES utilizes rank-based fitness shaping in order to render the
algorithm more robust, and invariant under monotonically
increasing transformations of the fitness function.
For this purpose, the fitness of the population is transformed into a set of utility 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
∇
θ
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 )}
.
The choice of utility function is a free parameter of the algorithm.
= Pseudocode
=input:
f
,
θ
i
n
i
t
{\displaystyle f,\;\;\theta _{init}}
1 repeat
2 for
k
=
1
…
λ
{\displaystyle k=1\ldots \lambda }
do // λ is the population size
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}}
// based on rank
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 }}
// or compute it exactly
10 update parameters
θ
←
θ
+
η
⋅
F
−
1
∇
θ
J
{\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}
// η is the learning rate
11 until stopping criterion is met
See also
Evolutionary computation
Covariance matrix adaptation evolution strategy (CMA-ES)
Bibliography
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).
External links
Collection of NES implementations in different languages
Kata Kunci Pencarian:
- Generasi Z
- Protokol Montreal
- Selandia Baru
- Keberatan terhadap evolusi
- Bakteri
- Virus
- Perancangan cerdas
- Taman Nasional Bouba Njida
- Legalisme agresif
- Globalisasi
- Natural evolution strategy
- Evolution strategy
- Differential evolution
- CMA-ES
- Genetic algorithm
- Evolutionary computation
- Evolutionary algorithm
- Genetic programming
- Selection (genetic algorithm)
- Strategy
