evolution strategies

Evolution Strategies (ES)

ES are a class of evolutionary optimization algorithms for continuous, gradient-free parameter optimization.

There is no one definition, but broadly:

ES is an algorithm that provides the user a set of candidate solutions to evaluate a problem. The evaluation is based on an objective function that takes a given solution and returns a single fitness value. Based on the fitness results of the current solutions, the algorithm will then produce the next generation of candidate solutions that is more likely to produce even better results than the current generation. The iterative process will stop once the best known solution is satisfactory for the user. ¹

In a nutshell:
ES maintain a probability distribution (typically gaussian) over the parameter space:

1. Sample population: ${\theta }_i\sim \mathcal{N}(\mu ,{\sigma }^2)$

2. Evaluate fitness: $f({\theta }_i)$

3. Update distribution parameters based on fitness, repeat.

   Unlike GA which uses discrete representations with crossover, ES operates directly on real-valued vectors and is mutation-driven.

Variants

cma-es
natural evolution strategies
OpenAI-ES

Simple ES

The simplest form of an evolution strategy is just iteratively updating the mean of the sampling distribution (green) to the best solution of the current population (red). This only works on toy problems.

Selection in ES $(\mu +\lambda )$, $(\mu ,\lambda )$

$\mu$ … elites, best performing individuals of a generation
$\lambda$ … population size (including elites)
$(\mu +\lambda )$ … give the parents a chance to compete with their children (elitist, best survive)
$(\mu ,\lambda )$ … replace parents by children (can help overcome local optimium through turnover/diversity→ advantage over gradient-based methods; bio inspo: death of old age)

https://szhaovas.github.io/2023-02-06-cmaesall/

https://szhaovas.github.io/2022-09-06-cmaes/

References

https://lilianweng.github.io/posts/2019-09-05-evolution-strategies/

Footnotes

1. Highly recommended blog: https://blog.otoro.net/2017/10/29/visual-evolution-strategies ↩