Introduction into Evolution Strategy¶

The Principle of Evolution¶

Evolution Strategies (ES) are a class of stochastic, population-based optimization algorithms inspired by natural evolution. They are "black-box" optimizers, meaning they treat the objective function as a mystery: they don't require gradients or knowledge of the function’s internal structure—they simply observe the output for a given input.

Mathematically, we seek to minimize an objective function $f(\mathbf{x})$ (in general a non-linear, non-convex function) with respect to a real-parameter vector $\mathbf{x} \in \mathbb{R}^n$ (continuous domain). $$f: \mathbb R^n \rightarrow \mathbb R$$ Typically, the global optimum is often neither feasible (NP-hard) nor relevant in practice. Therefore, we want to find $\mathbf x$-values where $f(\mathbf{x})$ is as small as possible.

Estimation of Distribution Algorithm (EDA)¶

Here, we just consider the family of Estimation of Distribution Algorithms. Unlike traditional Genetic Algorithms, which evolve a population of encoded individuals (genotypes) with genetic operators such as crossover and bit-flip mutation, an EDA maintains a probabilistic model of the search space. In each generation, it "estimates" where the best solutions lie and updates its parameters accordingly.

General Framework

• $\lambda$: Population size (number of offspring per generation).
• $\theta^{(g)}$: State parameters of the distribution at generation $g$ (e.g., mean, variance).
• $P(x|\theta)$: The probability distribution (typically Gaussian) used to mutate the parents into offspring.
• $F_\theta$: The update function for $\theta$: it adjusts $\theta$ so that the probability of generating the successful individuals from the current generation is maximized for the next.

The Algorithm and the Ask-Tell design¶

Initialization: Choose $\theta^{(0)}$

The optimization follows a repetitive four-step cycle:

1. Sampling (Ask): The solver generates $\lambda$ new candidate solutions (offspring) independently from the current distribution:$$\mathbf{x}_1, \dots, \mathbf{x}_\lambda \sim P(\mathbf{x} | \theta^{(g)})$$
2. Evaluation: Calculate the cost (objective value) for each offspring with the objective function: $$f_k = f(\mathbf{x}_k) \quad \text{for } k=1 \dots \lambda$$ The solver doesn't know how this function works; it only receives the resulting cost scores $f_k$.
3. Tell & Update: The cost scores are returned to the solver. This is where the "intelligence" of the algorithm resides. The update function $F_\theta$ processes this feedback to re-estimate $\theta$, shifting the distribution toward high-quality (low-cost) regions: $$\theta^{(g+1)} = F_\theta\left(\theta^{(g)}, \{(\mathbf{x}_1, f_1), \dots, (\mathbf{x}_\lambda, f_\lambda)\}\right)$$ In modern Evolution Strategies, this update step implicitly includes Ranking, Selection, and Recombination.
4. Iteration: Repeat until a termination criterion (e.g., target cost reached, max generations, or distribution collapse) is met.

The software component solver encapsulates the algorithmic engine that maintains a probabilistic model of the search space, proposing candidate solutions through sampling and iteratively refining its internal parameters based on fitness feedback.

Selection and Recombination: From Offspring to the New Mean¶

Before looking at a specific example, we must define how the algorithm chooses which solutions "win" and how it uses them to move forward. In ES literature, we use two Greek letters to describe the population:

• $\lambda$ (Lambda): The number of offspring generated per generation. A larger $\lambda$ allows for better exploration but costs more function evaluations.
• $\mu$ (Mu): The number of top-performing individuals selected to influence the next generation.

Selection: Who survives?¶

There are two primary ways to handle the transition between generations:

• $(\mu, \lambda)$ Selection: The $\mu$ best are chosen only from the new offspring. The parents are discarded. This is often preferred because it allows the algorithm to "forget" bad areas and escape local optima.
• $(\mu + \lambda)$ Selection: The $\mu$ best are chosen from both offspring and parents (elitism).

While these discrete selection methods were the standard in early Evolution Strategies, modern ES has evolved toward Recombination. Instead of treating the $\mu$ survivors as "individuals" that simply live to the next round, modern strategies treat them as statistical data points. We don't just "pick" the winners; we recombine them to update the center of our search distribution.

Recombination: Creating the new center¶

In a strategy where $\mu > 1$, we have multiple survivors. Instead of having each survivor start its own independent family, we merge their "knowledge." This process is called Recombination.

In Evolution Strategies, we use Intermediate Recombination. We calculate a single "Center of Mass" from all $\mu$ survivors. This new center becomes the mean $\mathbf{m}^{(g+1)}$ for the entire next generation. Mathematically: $$\mathbf{m}^{(g+1)} = \sum_{i=1}^{\mu} w_i \mathbf{x}_{i:\lambda}$$ Where:

• $\mathbf{x}_{i:\lambda}$ represents the $i$-th best individual of the current generation.
• $w_i$ are the weights assigned to each survivor.

Weighting Strategies: $(\mu/\mu, \lambda)$ vs. $(\mu/\mu_w, \lambda)$¶

How much influence should each survivor have? There are two main approaches:

"Weighted Recombination" is explained in detail later. Let's look at an example before.

Why Recombine?¶

Recombination is generally more robust than selecting a single winner because it provides:

• Noise Reduction: If one offspring is "lucky" due to a random jump in a noisy landscape, averaging it with other top performers pulls the search back toward a more reliable consensus.
• Stability: The movement of the population center becomes smoother. Instead of "zig-zagging" toward the optimum by following single lucky points, the mean "drifts" steadily toward the best region.
• Faster Convergence: In high-dimensional spaces, the average of several good points is often closer to the true optimum than any single point in the group.

Mutation and the Distribution Parameters $\theta$¶

Mutation is the process of adding stochastic (random) noise to the parameters to explore the search space. In Evolution Strategies, this is typically done using a Gaussian (Normal) Distribution.

In this context, the state of our search is defined by the parameter set $\theta$. In the most general case, $\theta$ is a composite of three elements: $$\theta = \{ \mathbf{m}, \sigma, \mathbf{C} \}$$

• $\mathbf{m}$ (Location): The mean vector, representing the center of the "search cloud."
• $\sigma$ (Scale): The step-size, controlling the global mutation strength.
• $\mathbf{C}$ (Shape): The covariance matrix, determining the orientation and "stretch" of the cloud.

The standard mutation for an individual $i$ is the realization of the current model:

$$\mathbf{x}_i = \mathbf{m} + \sigma \cdot \mathcal{N}(0, \mathbf{C})$$ Where:

• $\mathcal{N}(0, \mathbf{C})$: A random vector drawn from a normal distribution with mean $0$ and covariance matrix $\mathbf C$ .

Simplifying $\theta$ for Basic ES¶

In many basic Evolution Strategies, we do not yet try to learn the correlations between variables. If we fix the covariance matrix as the Identity matrix ($\mathbf{C} = \mathbf{I}$), our distribution remains perfectly spherical (isotropic). In this case, our state parameters simplify to:

$$\theta = \{ \mathbf{m}, \sigma \}$$

The "intelligence" of the algorithm resides in the update function $F_\theta$. It takes the results from the current generation and calculates the parameters for the next. For the simplified case where $\mathbf{C} = \mathbf{I}$, the function $F_\theta$ is composed of two distinct parts:

1. Updating the Mean ($F_{\mathbf{m}}$): This "Update of the Mean" was already explained.
2. Updating the Step-size ($F_\sigma$): This is explained later in section "Step-Size Control (Meta-Evolution)".

A Simple 2D Example: The $(2/2, 10)$ Strategy¶

Now, let's visualize this. Imagine we are searching for the minimum of a function $f(\mathbf{x})$. We use a $(2/2, 10)$ strategy: we create 10 offspring, and the top 2 are averaged to find the next center.

1. Initialization: Start with a mean $\mathbf{m}^{(g)}$ and step-size $\sigma$.
2. The Loop:
   • Sample: Generate 10 offspring $\mathbf{x}_k = \mathbf{m}^{(g)} + \sigma \mathcal{N}(0, \mathbf{I})$.
   • Evaluate: Calculate $f(\mathbf{x}_k)$ for all 10.
   • Select & Recombine: Rank them, take the 2 best, and calculate the new mean: $\mathbf{m}^{(g+1)} = \frac{1}{2}\mathbf{x}_{1:10} + \frac{1}{2}\mathbf{x}_{2:10}$.
3. Iteration: The next 10 offspring are sampled from this updated $\mathbf{m}^{(g+1)}$.

Note: for clarity this example keeps the step-size $\sigma$ fixed. Adapting $\sigma$ is introduced in the "Step-Size Control" section below — with a constant $\sigma$ the search settles near the target but cannot tighten onto it.

Weighting Strategies¶

When the solver performs the Tell & Update step, it must decide how much to trust each survivor. While equal weights are simple, they treat the "champion" and the "borderline survivor" as equals.

Logarithmic Weighting¶

A common choice in modern ES (and the default in CMA-ES) is logarithmic weighting. This strategy penalizes lower-ranked individuals more harshly than a linear drop-off would. It ensures the "champion" has a significantly stronger influence on the new mean $\mathbf{m}^{(g+1)}$ than the mediocre survivors at the bottom of the top-$\mu$ list.

The raw weights $w'$ are calculated as:

$$w'_i = \ln(\mu + 0.5) - \ln(i) \quad \text{for } i = 1 \dots \mu$$

Normalization:

To ensure the weights sum to 1, we normalize the raw values:

$$w_i = \frac{w'_i}{\sum_{j=1}^{\mu} w'_j}$$

Example Weight Calculation ($\mu=5$)

In this example, we use the common logarithmic weighting scheme: $w'_i = \ln(\mu + 0.5) - \ln(i)$.

Notice that the Best individual has about 18 times the influence of the 5th individual. This aggressive weighting allows the search center to shift decisively toward the most promising direction while still benefiting from the "smoothing" effect of the other survivors.

Step-Size Control (Meta-Evolution)¶

One of the most critical challenges in ES is determining the value of $\sigma$ (mutation rate).

• If $\sigma$ is too large: The algorithm "overshoots" the target and bounces around the optimum without ever settling.
• If $\sigma$ is too small: The algorithm moves too slowly (crawls) or gets stuck in tiny local "potholes."

Step-size control allows the algorithm to automatically adapt $\sigma$ during the search. This is often called Meta-Evolution because the algorithm is evolving not just the solution, but also the parameters of the search itself.

The 1/5th Success Rule¶

One of the oldest and most intuitive methods for controlling step size is the 1/5th Success Rule. It is based on the observation that if more than 20% of mutations are successful (better than the parent), the search is likely in a smooth area and should move faster.

Why $0.85$ for increase/decrease?

• Stability: A $15\%$ change per generation allows the algorithm to adapt to the landscape's curvature without losing control.
• Symmetry: Using $c$ and $1/c$ ensures that if the success rate is exactly $1/5$, the step size remains neutral over time.
• Damping: In higher dimensions, the "volume" of the search space grows exponentially. Smaller multipliers prevent the "curse of dimensionality" from making $\sigma$ explode or collapse too quickly.

Modern Approach: Cumulative Step-Size Adaptation (CSA)¶

Modern algorithms like CMA-ES (later in this course) use Evolution Paths. Instead of just looking at the current generation, they track the direction the mean has moved over several generations.

1. Consistent direction: If the mean has been moving in a straight line, $\sigma$ is increased (the algorithm "sprints").
2. Changing direction: If the mean is zig-zagging or turning back, $\sigma$ is decreased (the algorithm "slows down" to investigate).

Why a Covariance Matrix? The Limits of Circular Search¶

So far our search cloud has been isotropic: with $\mathbf{C} = \mathbf{I}$, the offspring $\mathbf{x} = \mathbf{m} + \sigma\,\mathcal{N}(0, \mathbf{I})$ scatter equally in all directions — a circle (in 2D) or a sphere (in $n$D). This works well when the landscape looks the same in every direction near the optimum.

Real objective functions rarely do. Consider a long, narrow, tilted valley — the contour lines are stretched, rotated ellipses (a high condition number). A circular cloud now faces a dilemma:

• To avoid overshooting the narrow direction, $\sigma$ must stay small.
• But a small $\sigma$ means tiny steps along the long direction — so the search crawls down the valley.

The circle simply does not match the shape of the problem, and most samples land in unpromising directions. The figure below contrasts an isotropic cloud with one that has been reshaped to fit the valley.

Shaping the Cloud = Learning the Geometry¶

The right-hand cloud is clearly better matched to the valley: it takes large steps along the long direction and small, careful steps across the narrow one. That elongated, rotated ellipse is nothing more than the geometry of $\mathcal{N}(0, \mathbf{C})$ — the covariance matrix $\mathbf{C}$ stretches (through its eigenvalues) and rotates (through its eigenvectors) the search.

But we don't know the valley's shape in advance — that is the whole point of a black-box optimizer. The key insight of CMA-ES: the successful offspring reveal it for us. If the winners of a generation cluster along a particular direction, that direction is promising — so we adapt $\mathbf{C}$ toward the covariance of the selected winners (a small, incremental update each generation rather than a full reset) and sample the next generation from the updated shape. The cloud gradually molds itself to the local landscape, while $\sigma$ remains the global scale on top of it.

The Covariance Connection¶

This closes the arc of the course. The same covariance matrix you have already met reappears here as the engine of the search:

• PCA: the eigen-decomposition of $\mathbf{C}$ gives the principal axes of the search ellipse — the directions of largest and smallest step.
• Hessian / Newton: an adapted $\mathbf{C}$ approximates the inverse local curvature ($\mathbf{C} \approx \mathbf{H}^{-1}$), so CMA-ES behaves like a gradient-free version of Newton's method — the classical fast optimizer that uses the curvature to rescale its steps (explained just below).
• Kalman filter: $\mathbf{C}$ is again a "shape of uncertainty" — here, uncertainty about where the optimum lies.

In one paragraph — what is the Hessian $\mathbf{H}$? It is the matrix of second derivatives of $f$; it measures the local curvature, i.e. how fast the slope changes as you move. For an elliptical valley its eigenvectors point along the ellipse's axes and its eigenvalues are the curvatures — a large eigenvalue means a sharply-curving, narrow direction, a small one a gently-curving, long direction. The inverse $\mathbf{H}^{-1}$ is therefore large along the long directions and small along the narrow ones: exactly the shape the search cloud should have.

And what is Newton's method? It is the classical fast optimizer that exploits this curvature. Plain gradient descent just steps along the slope (the gradient), so it zig-zags in a narrow valley. Newton's method instead multiplies the gradient by $\mathbf{H}^{-1}$, which rescales every step by the local curvature — large along the gently-curving directions, small across the sharply-curving ones — and so heads almost straight to the minimum. Learning $\mathbf{C} \approx \mathbf{H}^{-1}$ gives CMA-ES this very same step-rescaling, but without any gradient or derivative: it reads the shape off the ranking of the sampled points alone (a "second-order" behaviour achieved by a black-box method).

And conjugate directions? Two directions are conjugate (with respect to the curvature) if optimizing along one does not undo the progress already made along the other. Searching along such non-interfering directions avoids the slow zig-zag that plain gradient descent shows in a narrow valley; CMA-ES's step-size path (CSA) steers the search toward them for the same reason.

For the full derivations see Hessian-matrix and conjugate-directions.

Basic ES fixes $\mathbf{C} = \mathbf{I}$ and only adapts $\mathbf{m}$ and $\sigma$. CMA-ES adds the missing ingredient — it learns $\mathbf{C}$ — which is why it is the state-of-the-art black-box optimizer.

The Cost of Learning $\mathbf{C}$ — and Leaner Alternatives¶

Learning the full covariance matrix is powerful, but it is not free. Since $\mathbf{C}$ is a symmetric $n \times n$ matrix, it has $\tfrac{n(n+1)}{2} = \mathcal{O}(n^2)$ free parameters. Storing it costs $\mathcal{O}(n^2)$ memory, and — more importantly — learning that many numbers reliably takes on the order of $\mathcal{O}(n^2)$ function evaluations. For small or moderate dimension $n$ this is well spent; in high dimensions it becomes prohibitive.

The remedy is to restrict the shape of $\mathbf{C}$ to fewer parameters, trading generality for speed:

• Diagonal covariance — keep only the $n$ diagonal entries of $\mathbf{C}$ (one variance per coordinate; $\mathcal{O}(n)$ parameters). The search ellipsoid can then stretch along the coordinate axes but not rotate. This learns roughly $n$ times faster and is the right choice for separable or nearly-separable problems — those where the variables are only weakly coupled, so the promising directions already line up with the coordinate axes. (This is the idea behind separable variants such as sep-CMA-ES.)

• Low-rank + diagonal covariance — represent $\mathbf{C}$ as a diagonal plus a few $k \ll n$ dominant directions ($\mathcal{O}(n\,k)$ parameters). This captures the most important correlated directions while ignoring the rest. It suits very high-dimensional problems with a low effective dimensionality — where the difficulty is concentrated in a handful of coupled directions rather than spread across all $\binom{n}{2}$ variable pairs. (This is the idea behind limited-memory variants such as LM-CMA and VkD-CMA.)

Rule of thumb: use the full $\mathbf{C}$ for moderate $n$, or whenever correlations are strong or unknown (it is the robust default and cannot be hurt by correlations); use a diagonal model for separable / weakly-correlated problems; use a low-rank + diagonal model in very high dimension when only a few directions truly matter.

Summary: From Basic ES to CMA-ES¶