Evolution Strategies (ES & CMA-ES)

Overview

Evolution Strategies (ES) are a family of black-box optimization algorithms that search for optimal parameters by iteratively sampling perturbations around a current mean, evaluating their fitness, and updating the search distribution based on the best-performing samples. Unlike genetic algorithms, which operate on discrete chromosome representations, ES were designed from the start for continuous parameter spaces and represent the population as a multivariate probability distribution (typically Gaussian) rather than a fixed set of individuals.

The crown jewel of the ES family is CMA-ES (Covariance Matrix Adaptation Evolution Strategy), developed by Nikolaus Hansen and Andreas Ostermeier in 2001. CMA-ES adapts not just the mean (where to search) but also the full covariance matrix (the shape of the search distribution), enabling it to learn the local curvature of the fitness landscape without computing gradients. CMA-ES is considered the gold standard for black-box optimization of continuous functions with up to a few hundred dimensions and is the benchmark algorithm on the BBOB (Black-Box Optimization Benchmarking) test suite.

In 2017, OpenAI’s landmark paper “Evolution Strategies as a Scalable Alternative to Reinforcement Learning” (Salimans et al.) demonstrated that a simple variant of Natural Evolution Strategies (NES) could match the performance of deep RL algorithms (DQN, A3C, TRPO) on Atari games and MuJoCo locomotion tasks, while being dramatically simpler to implement and trivially parallelizable across thousands of CPUs. This result brought ES back into the mainstream AI engineering conversation and established ES as a viable alternative for policy optimization in high-dimensional settings.

How It Works

The (μ, λ) and (μ + λ) Schemes

ES algorithms are characterized by their selection scheme, using the notation (μ, λ) or (μ + λ):

(μ, λ)-ES: Generate λ offspring from μ parents; select the best μ offspring as the new parents. The parents are discarded each generation (“comma” selection). This provides stronger exploration pressure because even the best current solution must re-earn its place.
(μ + λ)-ES: Select the best μ from the combined pool of μ parents + λ offspring (“plus” selection). More conservative — the best-ever solution is never lost. But this can lead to premature convergence on deceptive landscapes.

CMA-ES uses (μ/μ_w, λ)-ES: all μ parents contribute to the mean update, weighted by fitness rank (μ_w denotes the effective number of parents after weighting). A typical setting: λ = 4 + ⌊3 ln(n)⌋ and μ = λ/2, where n is the problem dimensionality.

Basic ES: The (1+1)-ES

The simplest evolution strategy maintains a single parent and generates one offspring per iteration by adding Gaussian noise:

# (1+1)-ES: simplest evolution strategy
import numpy as np

def one_plus_one_es(f, x0, sigma=0.1, n_iters=10000):
    x = x0.copy()
    fx = f(x)

    for _ in range(n_iters):
        # Sample offspring by adding Gaussian noise
        x_new = x + sigma * np.random.randn(len(x))
        fx_new = f(x_new)

        # Plus selection: keep if better
        if fx_new < fx:
            x, fx = x_new, fx_new

    return x, fx

This is essentially random hill climbing with a fixed step size. The 1/5th success rule (Rechenberg, 1973) adapts σ: if more than 1/5 of mutations are successful, increase σ (the step is too small); if fewer, decrease σ (the step is too large).

Key Concept: The Step-Size Problem

A fixed step size σ is catastrophic: too large and you overshoot optima; too small and search stalls. The fundamental contribution of CMA-ES is solving this problem by learning a full covariance matrix that adapts both the scale and shape of the search distribution to the local fitness landscape — effectively learning a second-order model of the objective without computing the Hessian.

CMA-ES: Covariance Matrix Adaptation

CMA-ES maintains three state variables that it adapts each generation:

Mean m: The center of the search distribution. Updated by a weighted average of the best offspring (weighted recombination).
Step size σ: The overall scale of the search distribution. Adapted using a cumulative step-size adaptation (CSA) path that tracks whether successive steps are correlated (step too small) or anti-correlated (step too large).
Covariance matrix C: The shape of the search distribution. Adapted using two evolution paths — the rank-one update (captures the direction of successive mean shifts) and the rank-μ update (captures the covariance structure of the successful offspring). Together, these learn the inverse Hessian of the fitness landscape.

The sampling and update cycle:

# CMA-ES core loop (simplified)
import numpy as np

def cma_es_step(m, sigma, C, lam, mu, weights, f):
    n = len(m)

    # 1. Sample λ offspring from N(m, σ²C)
    z = np.random.randn(lam, n)                    # standard normal
    A = np.linalg.cholesky(C)                       # C = A @ A.T
    x = m + sigma * (z @ A.T)                       # transform samples

    # 2. Evaluate and rank
    fitnesses = [f(xi) for xi in x]
    ranked = np.argsort(fitnesses)                  # ascending (minimization)

    # 3. Update mean — weighted recombination of best μ
    selected = x[ranked[:mu]]
    m_new = weights @ selected                      # weighted average

    # 4. Update evolution paths and C (omitted for brevity)
    # — rank-one path: p_c tracks direction of m shifts
    # — rank-μ update: covC from selected offspring
    # — CSA path: p_σ for step-size control

    return m_new, sigma_new, C_new

Key Concept: Why CMA-ES Learns Curvature

The covariance matrix C converges toward the inverse Hessian of the objective function (scaled). This means CMA-ES effectively performs second-order optimization without ever computing gradients or Hessians explicitly. On an ill-conditioned quadratic function with condition number 10⁶, CMA-ES adapts C to elongate the search distribution along the poorly-conditioned axis, maintaining efficient progress — while a fixed-σ ES would stall.

Natural Evolution Strategies (NES) and the OpenAI Approach

Natural Evolution Strategies (Wierstra et al., 2008) take a different angle: treat the search distribution parameters θ as the object to optimize, and compute the natural gradient of the expected fitness with respect to θ. The REINFORCE-style gradient estimator:

# NES / OpenAI-ES gradient estimator
# ∇_θ E[f(x)] ≈ (1/λ) Σᵢ f(xᵢ) ∇_θ log p(xᵢ; θ)
# For Gaussian with fixed σ:
# ∇_m E[f(x)] ≈ (1/λσ) Σᵢ f(xᵢ) · εᵢ    where εᵢ = (xᵢ - m)/σ

def openai_es_step(m, sigma, f, lam=100, lr=0.01):
    n = len(m)
    eps = np.random.randn(lam, n)
    rewards = np.array([f(m + sigma * eps[i]) for i in range(lam)])

    # Rank-normalize rewards for robustness
    ranks = np.argsort(np.argsort(rewards)).astype(float)
    ranks = (ranks / (lam - 1)) - 0.5  # center around 0

    # Gradient estimate
    grad = (1.0 / (lam * sigma)) * (ranks @ eps)
    m_new = m + lr * grad
    return m_new

OpenAI’s key contribution was showing that this simple algorithm, with antithetic sampling (mirrored noise), fitness shaping (rank normalization), and massive parallelism (1,440 CPUs), could train neural network policies for Atari and MuJoCo tasks in minutes rather than hours. The parallelism is trivially efficient: each worker evaluates one perturbation, and only the scalar fitness and the random seed need to be communicated — not gradients or parameters.

CMA-ES vs. Other Methods

CMA-ES vs. Bayesian Optimization (BO)

CMA-ES excels at moderate-dimensional problems (10–100+ variables) where function evaluations are not extremely expensive (seconds to minutes each). It has no surrogate model overhead and scales better with dimensionality.
BO (GP-UCB, TPE) excels at very expensive evaluations (hours each) with few variables (<20). The Gaussian process surrogate amortizes the cost of each evaluation but scales cubically with the number of observations.

CMA-ES vs. Gradient Descent

CMA-ES requires no gradients and handles noisy, discontinuous, multimodal objectives. But it scales poorly beyond ~1000 dimensions because the covariance matrix is O(n²) in space and O(n³) per update (eigendecomposition).
Gradient descent (SGD/Adam) scales to billions of parameters but requires differentiable objectives.

CMA-ES vs. Genetic Algorithms

CMA-ES is purpose-built for continuous optimization and adapts the search distribution shape. It is consistently the top performer on continuous benchmarks (BBOB/COCO).
GAs are more natural for discrete/combinatorial problems and use crossover to recombine building blocks. For continuous problems, CMA-ES almost always outperforms GAs.

Practical Applications

Hyperparameter Optimization

CMA-ES is available as a sampler in Optuna (optuna.samplers.CmaEsSampler) and is the recommended choice when the hyperparameter space is continuous and moderate-dimensional (e.g., tuning 10–50 real-valued hyperparameters jointly). It outperforms random search and often matches TPE with fewer evaluations in this regime.

Reinforcement Learning Policy Optimization

OpenAI’s ES approach trains neural network policies by treating the network weights as the search parameters. Advantages over gradient-based RL (PPO, SAC): no need for backpropagation through rollouts, no value function approximation, trivially parallelizable, and invariant to reward delays/sparsity. EvoTorch (Meta) and evosax (JAX) provide GPU-accelerated ES implementations for RL.

Robot Design and Sim-to-Real

ES is widely used for co-optimizing robot morphology and controller parameters in simulation, then transferring to hardware. The gradient-free nature of ES handles the non-differentiable physics simulation boundary naturally.

Game AI and Procedural Content Generation

ES has been used to evolve game-playing agents (Atari, board games) and to optimize parameters of procedural content generators (level design, terrain generation) where the fitness function involves simulation rollouts that are not differentiable.

Key Takeaways

Evolution Strategies optimize continuous parameters by sampling from and adapting a probability distribution (typically Gaussian) over the search space — no gradients required.
CMA-ES is the gold standard for black-box continuous optimization in moderate dimensions (10–1000 variables). It learns the covariance structure (effective Hessian inverse) of the fitness landscape.
CMA-ES population size scales as λ = 4 + ⌊3 ln(n)⌋. For a 100-dimensional problem, that’s ~18 samples per generation — quite efficient.
The OpenAI ES paper (Salimans et al., 2017) showed that NES with massive parallelism can train RL policies competitively with PPO/A3C, with dramatically simpler implementation.
Use CMA-ES for continuous hyperparameter optimization (Optuna’s CmaEsSampler), RL policy search, and simulation-based design. Use Bayesian optimization for very expensive evaluations with few variables. Use GAs for combinatorial/discrete problems.
The main limitation is scaling: covariance matrix adaptation is O(n²) space and O(n³) per generation, making it impractical beyond ~1000 dimensions without low-rank approximations (sep-CMA-ES, VD-CMA).