Evolution Strategies

Evolution strategies do not only evolve solutions, but also how solutions are varied. They are a mutation-driven search for real-valued/continuous optimization problems, using Gaussian perturbation and deterministic selection, with strong theoretical foundations.

There are two evolution “levels”.

• Solution evolution: Candidate solutions $x\in {\mathbb{R}}^n$ that represent problem variables are mutated to explore new regions, and selected based on fitness $F(x)$.
• Strategy evolution: A mutation strength $\sigma$ that controls the search step size, determining exploration vs. exploitation, is also mutated and selected.

Thus, an individual in ES comprises of both the candidate and the mutation strength, such that we have $⟨x,\sigma ⟩$ or $⟨x_1,\dots ,x_n,{\sigma }_1,\dots ,{\sigma }_n⟩$.

Comparing to other search strategies:

Formulation

Problem setting: Black-box optimization in ${\mathbb{R}}^n$ without gradient information.

Search model:

$$x_k\sim \mathcal{N}(m,{\sigma }^{2}C)$$

• $m\in {\mathbb{R}}^n$ is the current search mean (center of sampling)
• $\sigma >0$ is the global step size (overall exploration scale)
• $C\in {\mathbb{R}}^{n\times n}$ is the covariance (shape + directions)

Selection mechanism:

$$(\mu ,\lambda )\text{or}(\mu +\lambda )$$

Deterministic truncation of the best individuals (rank-based.)

Selection Mechanisms

• See ES Selection Strategies

Mutation

• See ES Gaussian Mutation

Mutation is the primary search operator in ES.

Recombination/Crossover

• See ES Recombination

Recombination is optional but often used to combine parental information. New solutions are mainly created through mutation.