PaperlayerView exact revision on arXiv

Source-linked AI summary

The CMA Evolution Strategy: A Tutorial

Nikolaus Hansen

arXiv:1604.00772v2cs.LGstat.ML

TL;DR

CMA-ES addresses continuous black-box optimization on difficult non-linear and non-convex landscapes. The tutorial motivates and derives a randomized strategy that adapts a multivariate-normal search distribution. It reports broad competitiveness, invariance properties, and scope limitations involving variance control and selected problem classes.

  • Problem

    Continuous black-box optimization must search non-linear, non-convex landscapes using only objective-function evaluations, including rugged, ill-conditioned, and nonseparable problems.

  • Method

    CMA-ES uses a randomized multivariate-normal search distribution and adapts its covariance, mean, and step-size to the objective landscape.

  • Results

    The CMA-ES is highly competitive on a considerable number of test functions and has been successfully applied to many real-world problems.

  • Takeaways & Limitations

    CMA-ES is invariant to strictly monotonic objective transformations and to rotations, reflections, translations, and suitably initialized scaling transformations of the search space.

  • Takeaways & Limitations

    The discussion notes that variance or step-size bias can cause divergence or premature convergence, while controlled upward bias on noisy problems complicates termination decisions.

Abstract

from arXiv · show

This tutorial introduces the CMA Evolution Strategy (ES), where CMA stands for Covariance Matrix Adaptation. The CMA-ES is a stochastic, or randomized, method for real-parameter (continuous domain) optimization of non-linear, non-convex functions. We try to motivate and derive the algorithm from intuitive concepts and from requirements of non-linear, non-convex search in continuous domain.

Nomenclature

The paper defines notation and symbols for vectors, matrices, distributions, search points, generations, recombination, and adaptive CMA-ES parameters.

  • CMA abbreviates Covariance Matrix Adaptation, while EMNA denotes Estimation of Multivariate Normal Algorithm.
  • The population contains λ offspring, of which μ selected points contribute through recombination weights w_i.
  • The learning rates c_m, c_1, c_μ, c_σ, and c_c control mean, covariance, step-size, and evolution-path adaptation.
  • The objective function f maps R^n to R and is minimized over search points x.
  • The search distribution has mean m(g), covariance C(g), and step-size σ; p denotes an evolution path across generations.
  • N(0,I) is the standard multivariate normal distribution with independent standard-normal components, while N(m,C) has mean m and covariance C.

0 Preliminaries

The preliminaries establish positive-definite matrix geometry, multivariate-normal search distributions, black-box optimization, and the rationale for covariance adaptation.

  • 0 Preliminaries: The tutorial motivates and derives CMA-ES for non-linear, non-convex optimization in continuous domains.
  • The tutorial focuses on single-objective, non-elitist truncation selection rather than multi-objective or elitist CMA variants.
  • 0.1 Eigendecomposition of a Positive Definite Matrix: A positive-definite covariance matrix defines an ellipsoid whose principal axes are eigenvectors and whose squared axis lengths are eigenvalues.
  • 0.2 The Multivariate Normal Distribution: A multivariate normal N(m,C) is determined by its mean and positive-definite covariance matrix, with isotropic, diagonal, and rotated forms corresponding to different ellipsoid geometries.
  • 0.3 Randomized Black Box Optimization: Black-box optimization minimizes f(x) using only evaluated function values, so performance must relate achieved objective values to function-evaluation cost.
  • 0.3 Randomized Black Box Optimization: CMA-ES samples from multivariate normal distributions because they maximize entropy for given covariances and do not privilege coordinate directions.
  • 0.4 Hessian and Covariance Matrices: Covariance adaptation targets objective contours and, on convex-quadratic functions, approximates the inverse Hessian similarly to quasi-Newton methods.

1 Basic Equation: Sampling

CMA-ES generates each generation’s offspring by sampling a multivariate normal distribution centered at the current mean with covariance scaled by the step-size.

  • For generation g, the algorithm samples λ new search points from the current multivariate normal search distribution.
  • The sampling distribution is centered at m(g), the mean of the search distribution at generation g.
  • N(0,C(g)) denotes a zero-mean multivariate normal distribution with covariance C(g).
  • The resulting x_k^(g+1) are the offspring or search points for the next generation.
  • C(g) is the covariance matrix up to the scalar factor σ(g)^2, which determines the overall search scale.
  • The complete iteration then updates m(g+1), C(g+1), and σ(g+1).

2 Selection and Recombination: Moving the Mean

CMA-ES moves its search-distribution mean by ranking offspring, selecting μ of λ points, and recombining them with weighted intermediate recombination.

  • The new mean m(g+1) is a weighted average of μ selected offspring from x^(g+1).
  • Recombination weights satisfy w_1 ≥ w_2 ≥ ··· ≥ w_μ > 0 and sum to one for the positively weighted selected points.
  • Truncation selection chooses μ < λ offspring, while ranking is determined by the objective function values.
  • The effective selection mass μ_eff measures information retained by weighted selection and obeys 1 ≤ μ_eff ≤ μ.
  • A typical setting uses μ_eff ≈ λ/4, with μ ≈ λ/2 and decreasing weights yielding μ_eff ≈ 3λ/8.
  • The generalized mean update uses learning rate c_m, usually set to 1, and equals the selected-point recombination under the default weights.
  • Choosing c_m < 1 can help on noisy functions, but excessively large test steps can misrank points outside the relevant region.

3 Adapting the Covariance Matrix

The section develops covariance-matrix adaptation from empirical estimation toward selected-step updates, cumulation, and a combined rank-µ/rank-one rule. It contrasts these estimators, identifies sample-size limitations, and explains how evolution paths improve adaptation for small selection masses.

  • 3.1 Estimating the Covariance Matrix From Scratch: The empirical covariance matrix is an unbiased estimator of the original covariance matrix when sampled points are treated as random variables.The estimator uses the realized sample mean as its reference mean.
  • 3.1 Estimating the Covariance Matrix From Scratch: Weighted selection changes covariance estimation from reproducing the original sampled distribution to reproducing selected, successful steps.The selected-step estimator uses a weighted mechanism and references the distribution of selected steps.
  • 3.1 Estimating the Covariance Matrix From Scratch: Equation (13) yields smaller variances than Equation (12), and typically decreases variances relative to C(g), making it susceptible to premature convergence.On a linear objective, Equation (12) increases variance in the gradient direction, whereas Equation (13) decreases it geometrically fast.
  • 3.2 Rank-µ-Update: Reliable covariance estimation from selected steps requires a sufficiently large effective selection mass, approximately µeff ≈10n for condition numbers below ten.Small populations commonly imply small µeff, motivating the use of information from previous generations.
  • 3.2 Rank-µ-Update: The rank-µ-update adapts covariance from weighted selected steps, with learning rate cµ ≈min(1, µeff/n2), while exponential smoothing emphasizes recent generations.The rank-µ covariance sum has rank min(µ, n) with probability one and can contain a single term when µ = 1.
  • 3.3.2 Cumulation: Utilizing the Evolution Path: The evolution-path update improves covariance adaptation for small µeff by exploiting correlations between consecutive steps, while the combined rule also uses the full population.The combined update therefore assigns rank-µ information particular importance in large populations and evolution-path information particular importance in small populations.

4 Step-Size Control

CMA-ES controls the overall step-size separately from covariance adaptation by comparing an evolution path with its expected length under random selection. Long paths increase σ, short paths decrease it, while the approach adapts quickly enough for competitive step-length changes but fails on very noisy objectives.

  • Motivation: Covariance adaptation alone does not explicitly control the distribution’s overall scale, motivating separate step-size control.Its scale changes only along selected directions or through non-adaptive fading of old information.
  • Adaptation speed: On fsphere, competitive performance requires the overall step length to decrease by about exp(0.25) ≈ 1.28 within n evaluations, but covariance learning can be too slow.This slowness occurs when µeff ≪ n.
  • Method: Cumulative path length control (CSA) controls σ independently of covariance adaptation by summing successive steps into an evolution path.The path length is used as the basis for step-size control.
  • Path-length intuition: Long paths indicate similarly directed, correlated steps and increase σ, whereas short paths indicate canceling, anti-correlated steps and decrease σ.Approximately perpendicular, uncorrelated steps represent the desired reference situation.
  • Step-size update: The algorithm compares path length with its expected length under random selection, increasing σ for longer-than-expected paths and decreasing it for shorter-than-expected paths.Random selection supplies the reference because consecutive steps are independent and uncorrelated.
  • Properties: The evolution-path length is an intuitive, empirically validated measure of overall step length and is considered the best known measure for µeff > 1.The path represents directional information more accurately than single steps, effectively amplifying covariance learning on cigar-like objectives.
  • Limitation: CSA fails to adapt nearly optimal step-sizes on very noisy objective functions.Choosing cm < 1 can be advantageous on noisy functions, but excessively large test steps harm ranking relevance.

5 Discussion

The discussion presents CMA-ES as a competitive, flexible optimizer whose covariance, mean, and step-size adaptation address scaling, separability, population-size, and premature-convergence issues while providing broad invariance properties.

  • CMA-ES adapts the search distribution to badly scaled and non-separable problems, addressing a common weakness of evolutionary algorithms.
  • The covariance learning rates c1 and cµ prevent population degeneration even with small populations, while population size remains freely selectable.Small populations usually converge faster, whereas large populations help avoid local optima.
  • Step-size control prevents premature population convergence, although it does not prevent the search from ending at a local optimum.
  • CMA-ES is highly competitive on many test functions and has been successfully applied to numerous real-world problems.The tutorial presents this conclusion alongside the method's ability to handle rugged, ill-conditioned, and non-separable landscapes.
  • The algorithm separately controls change rates for the mean, covariance matrix, and step-size through distinct parameters.Mean change depends on cm, parent number, and recombination weights; covariance change uses c1 and cµ, and step-size change uses dσ.
  • CMA-ES is invariant to objective-value ranking and several search-space transformations, including rotations, scaling, diagonal transformations, and affine transformations.Uniform performance from these invariances is observed after the algorithm's state has been adapted.
  • Under random selection, the distribution mean, covariance matrix, and ln σ are unbiased, but variance or step-size bias can risk divergence or premature convergence.A controlled increase bias may suit noisy problems but makes termination decisions more difficult.

A Algorithm Summary: The (µ/µW, λ)-CMA-ES

The CMA-ES samples offspring from a multivariate normal distribution, ranks them, recombines selected points, and adapts covariance-related state and step-size through parameterized updates.

  • Sampling and selection: The algorithm samples λ search points from a multivariate normal distribution with zero mean and covariance matrix C, then identifies the ranked points xi:λ.The eigendecomposition C = BD^2B^T supports sampling and inverse-covariance calculations.
  • Sampling and selection: The new mean is formed as a weighted recombination of selected points, using recombination weights wi and the variance-effective selection mass µeff.The positive weights define the selected-parent contribution, while negative weights are handled separately in covariance adaptation.
  • Adaptation: The strategy uses evolution paths and a Heaviside function hσ to stall the covariance-path update when the normalized step is large.This prevents overly rapid axis expansion when the step-size is too small, including under changing objectives.
  • Algorithm identity: With negative covariance-matrix recombination weights, the method is sometimes called active CMA or aCMA-ES.The tutorial identifies this naming as associated with the default use of negative weights.
  • Adaptation: Negative recombination weights are bounded to preserve positive definiteness of C and limit variance reduction in any single direction.For the default population size, the positive-definiteness bound leaves the weights unchanged.
  • Parameter setting: Default parameters are designed as a robust setting for a wide range of functions, while increasing λ generally improves global search capability and robustness at reduced convergence speed.The tutorial recommends increasing, rather than decreasing, the population size when changing this setting.

B Implementational Concerns

Implementation requires generating correlated samples through the eigendecomposition of C and choosing cumulation settings that control adaptation horizons and dimensional behavior.

  • Cumulation settings: On the cigar function, the relationship between cc × n and evaluations divided by dimension to reach a target becomes invariant as dimension increases.The tutorial notes this dimensional invariance for the discussed setting.
  • Sampling and decomposition: To sample y ∼ N(0, C), the implementation draws z ∼ N(0, I) and computes y = BDz using the eigendecomposition C = BD^2B^T.The same decomposition supports transforming weighted steps into the coordinate system used for updates.
  • Sampling and decomposition: The weighted normalized step is computed as B Σ_i=1^µ wi zi:λ, linking selected samples to the covariance-coordinate update.This expression uses the eigendecomposition basis to form the weighted step.

B.2 Strategy internal numerical effort

The implementation reduces eigendecomposition overhead by spacing recalculations across generations and provides termination criteria aimed mainly at numerical stability and stagnation.

  • Computational effort: Recomputing B and D only every about max(1, floor(1/(10n(c1 + cµ)))) generations reduces eigendecomposition effort from O(n^3) to O(n^2) per generated search point.The reduced cost is comparable to a matrix-vector multiplication.
  • Computational effort: The reported overall strategy internal time consumption is roughly 3 × (n + 5)^2 × 10^-8 seconds per function evaluation on a 2.5 GHz Pentium 4.This is an implementation-time measurement rather than objective-function evaluation cost.
  • Numerical requirements: A Cholesky decomposition alone is insufficient because the algorithm must compute C^-1/2 correctly.The eigendecomposition provides B and D for this inverse transformation.
  • Termination criteria: Flat fitness can interfere with step-size increases and TolFun, so observing equal function values should generally prompt termination and reconsideration of the objective formulation.The passage frames flat fitness as a practical termination signal.

B.5 Boundaries and Constraints

Boundary and constraint handling is problem dependent: repair, penalization, or resampling can maintain feasibility, but simple repair may violate the distributional assumptions of CMA-ES.

  • Constraint-handling choices: The tutorial presents boundary and constraint handling as problem dependent and distinguishes repair-based, penalty-based, and resampling approaches.The appropriate method depends on whether a repair mechanism is available and on the feasible-domain setting.
  • Resampling: If the optimum is sufficiently inside the feasible domain, assigning infeasible points a poor fitness and repeatedly resampling until feasibility can handle general boundaries and constraints.The construction uses a constant feasible point and an fmax worse than the feasible population or domain.
  • Repair and penalization: Simple repair before applying update equations is not recommended because it can heavily violate CMA-ES assumptions about the distribution of solution points.The stated risks include divergence or excessively rapid step-size convergence.
  • Repair and penalization: For box boundaries, repair clips infeasible components to the closest boundary value, then evaluates the repaired point and adds a distance-dependent penalty.The repaired solution is disregarded afterward for the update procedure described.
  • Repair and penalization: When no repair mechanism is available, infeasible points can receive a penalty based on constraint violation and an offset derived from feasible-point fitness values.The penalty scale α should make objective differences and penalty differences have similar magnitudes.

C MATLAB Source Code

The MATLAB excerpt presents the CMA-ES algorithm’s core flow, including covariance-matrix and step-size adaptation. It is intended primarily for reading and understanding the algorithm rather than computational efficiency.

  • This implementation does not include negative weights, setting wi = 0 for i > µ in Table 1.
  • The source code is an excerpt implementing the key parts of the CMA-ES algorithm for reading and understanding its basic flow.The code comments explicitly state that computational efficiency is sometimes disregarded.
  • The algorithm updates the covariance matrix using old-matrix retention, rank-one adaptation, a correction term, and rank-µ adaptation.The covariance update uses coefficients c1 and cµ together with the evolution path and selected steps.
  • The step size σ is adapted exponentially according to the evolution path length relative to χN.The update is implemented as sigma = sigma * exp((cs/damps)*(norm(ps)/chiN - 1)).

D Reformulation of Learning Parameter ccov

The tutorial reformulates CMA-ES covariance-learning coefficients to improve their behavior across effective population sizes. The new formulation is compared with earlier learning rates and is designed around more consistent coefficient variation.

  • Reformulation of Learning Parameter ccov: The reformulation targets the learning coefficients in the covariance update for consistency and clarity.
  • Reformulation of Learning Parameter ccov: The resulting coefficients are quite similar to the previous formulation, while c1 becomes monotonic in µeff^-1.
  • Reformulation of Learning Parameter ccov: The sum c1 + cµ becomes virtually monotonic in µeff under the new formulation.
  • Reformulation of Learning Parameter ccov: An alternative coefficient formulation depends on the covariance matrix’s degrees of freedom and corrects for very small λ.The covariance matrix has n^2 + n degrees of freedom, as indicated by the supplied expression and surrounding text.
  • Reformulation of Learning Parameter ccov: For µeff = 1, the reformulated coefficient cµ is chosen to be larger than zero.
  • Reformulation of Learning Parameter ccov: Figure 8 compares the new learning rates with the old ones across µeff for multiple dimensional settings.The figure includes cases with n = 3 and n = 10 above, and n = 2 and n = 40 below.
  • Reformulation of Learning Parameter ccov: For µcov ≈ 2, the difference between formulations is maximal because c1 decreases more slowly and ccov is non-monotonic in µcov.
Loading 1604.00772v2…