CMA-ES (DEAP/cmaes)

Covariance Matrix Adaptation Evolution Strategy

← Back to Optimizer Competition
CMA-ES (Covariance Matrix Adaptation Evolution Strategy; Hansen & Ostermeier, 1996) samples offspring from N(mean, σ2·C) and updates C, σ, and mean from the μ best offspring each generation. HumpDay's CMAEvolutionStrategy implements Hansen-standard CMA-ES wrapped in an IPOP restart layer (Auger & Hansen, 2005) so the optimizer can escape local optima on multimodal landscapes instead of converging once and stopping, then finishes with an L-BFGS-B polish from the best-found point across all restarts.

HumpDay's CMA-ES at a glance

  • Recommended parameters: λ = min(50, 4 + ⌊3·log(n)⌋) (doubled at each IPOP restart), μ = λ/2, recombination weights wi = log(μ + 0.5) − log(i) normalised.
  • Adaptation: rank-1 + rank-μ C-update with positive-definiteness guard, cumulative step-size adaptation, evolution paths.
  • Sampler: Cholesky factor L of C, with eigendecomp-based C−½ refresh each iteration.
  • Polish: reserve min(20·n_dim, n_trials/2) evaluations for L-BFGS-B from the CMA-ES best.

IPOP-CMA-ES restart layer

Auger & Hansen (2005, "A Restart CMA Evolution Strategy with Increasing Population Size", CEC 2005, HAL preprint) introduced the standard restart mechanism that turns a single-basin local optimizer into a competitive global one. When the inner CMA run hits any of the canonical termination criteria, all state is reset and the algorithm restarts with a larger population.

  • TolFun: the range of best-of-generation values over the last max(10, 30·n/λ) generations falls below 1e-12.
  • TolX: the effective step σ · &sqrt;max(eig(C)) falls below 1e-12.
  • ConditionCov: the condition number of C exceeds 1e14 — the search distribution has degenerated and further updates would be numerically unsafe.

On restart, λ is doubled and the mean / σ / C / evolution paths are all reset. Successive restarts therefore explore more aggressively, which is what gives IPOP-CMA-ES its global-search behavior. self.best_x persists across restarts via the base class, so the best point found in any prior run is preserved.

Interactive 3D Visualization

See CMA-ES in action on 3D optimization surfaces:

Loading 3D visualization...

Requires WebGL support

Instructions: Choose a test function and algorithm, then click Start to watch the step-by-step optimization process.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.
  • Overhead tier 3: heavy (~10ms/iter; full quadratic model or O(n3) eigendecomposition). Eligible when measured eval_time ≥ 1 ms.
  • Dimensional cap: n_dim ≤ 100 — eigendecomposition O(n3) per generation.
  • Minimum trials: max(20, 4n) — CMA-ES wants several generations of λ ≈ 4·n evaluations.

Implementation Details

Component Details Links
Original Algorithm Hansen & Ostermeier
Self-adaptive evolution strategy with covariance matrix learning
Invariant to affine transformations of the search space
Published: 1996-2001 		Tutorial
Reference Implementation cmaes Python package
Official CMA-ES implementation by Nikolaus Hansen
Highly optimized with numerous variants
Package: cmaes 		pycma cmaes
HumpDay Python HumpDay CMAEvolutionStrategy
Hansen-standard CMA-ES with rank-1 + rank-μ C-update, evolution paths, CSA, then L-BFGS-B polish from the best CMA-ES point.
Pure Python; no required dependencies.
File: humpday/optimizers/evolutionary_algorithms.py 		Source
HumpDay JavaScript Browser CMAEvolutionStrategy
Mirrors the Python port line-for-line, including the L-BFGS-B polish stage.
Class: CMAEvolutionStrategy 		JS Port

Performance characteristics

  • Best for: Ill-conditioned and rotation-sensitive continuous objectives. CMA-ES learns anisotropy and is — for a single black-box algorithm — one of the most powerful continuous optimizers.
  • Worst for: Very high dimensions with tight budgets — the C-matrix update is O(n2) per generation, and the eigendecomp is O(n3).
  • Per generation: λ offspring evaluations + one rank-1/rank-μ C-update + one eigendecomp for C−½.
  • Relative to the cmaes reference at n_trials=200, n_dim=2: HumpDay matches on sphere and Ackley, wins on Ackley by a margin. See SOTA status for the live numbers.

Educational Resources

Core Algorithm Components

  • Population: λ offspring generated from multivariate normal distribution
  • Selection: μ best individuals become parents for next generation
  • Recombination: Weighted average of selected individuals
  • Covariance Update: C(g+1) = (1-c_cov)C(g) + c_cov * update
  • Step Size: σ adapted based on evolution path length
  • Evolution Paths: Track search direction over generations

Mathematical Foundation

  • Multivariate Normal: x ~ N(m, σ²C) sampling distribution
  • Rank-μ Update: C_μ = Σᵢ wᵢ yᵢyᵢᵀ (rank-μ covariance update)
  • Rank-1 Update: C₁ = p_c p_cᵀ (evolution path outer product)
  • CSA: Cumulative Step-size Adaptation using conjugate evolution path
  • Invariance: Transformation-invariant under affine coordinate changes

️ Key Parameters

  • Population Size: λ = 4 + ⌊3ln(n)⌋
  • Parents: μ = ⌊λ/2⌋
  • Weights: wᵢ = ln(μ+0.5) - ln(i) for i=1..μ
  • Learning Rates: c_cov ≈ 2/(n²+6), c_c ≈ 4/(n+4)
  • Damping: d_σ ≈ 1 + 2max(0, √((μ_eff-1)/(n+1)) - 1)

CMA-ES Variants

  • CMA-ES: Standard algorithm with full covariance adaptation
  • IPOP-CMA-ES: Increasing population restart strategy — what HumpDay implements
  • BIPOP-CMA-ES: Bi-population restart strategy (alternates large/small populations)
  • sep-CMA-ES: Separable CMA-ES for high dimensions
  • VD-CMA: VkD-CMA for very high dimensions
  • xNES: Natural Evolution Strategy variant

Applications & Success Stories

  • Engineering Design: Antenna design, aerodynamics optimization
  • Machine Learning: Neural network hyperparameter optimization
  • Control Systems: Controller parameter tuning
  • Game AI: Strategy parameter evolution
  • Scientific Computing: Parameter estimation in complex models
  • Black-Box Challenges: Consistent top performer in BBOB competitions

Why CMA-ES is Special

  • Invariance Properties: Rotation and scaling invariant
  • Self-Adaptation: Learns problem structure automatically
  • Principled Design: Theoretically motivated updates
  • Empirical Success: Top performer on many benchmark suites
  • Noise Handling: Built-in mechanisms for noisy optimization
  • Constraint Handling: Extensions for constrained problems