↑ arvau

Wikipedia / CMA-ES

Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy for numerical optimization. Evolution strategies (ES) are stochastic, derivative-free methods for numerical optimization of non-linear or non-convex continuous optimization problems. They belong to the class of evolutionary algorithms and evolutionary computation. An evolutionary algorithm is broadly based on the principle of biological evolution, namely the repeated interplay of variation (via recombination and mutation) are generated by variation of the current parental individuals, usually in a stochastic way. Then, some individuals are selected to become the parents in the next generation based on their fitness or objective function-values are generated over the generation sequence.

In an evolution strategy, new candidate solutions are usually sampled according to a multivariate normal distribution. Recombination amounts to selecting a new mean value for the distribution. Mutation amounts to adding a random vector, a perturbation with zero mean. Pairwise dependencies between the variables in the distribution are represented by a covariance matrix. The covariance matrix adaptation (CMA) is a method to update the covariance matrix is ill-conditioned.

Adaptation of the covariance matrix amounts to learning a second order model of the underlying objective function similar to the approximation of the inverse Hessian matrix in the quasi-Newton method in classical optimization. In contrast to most classical methods, fewer assumptions on the underlying objective function are made. Because only a ranking (or, equivalently, sorting) of candidate solutions is exploited, neither derivatives nor even an (explicit) objective function is required by the method. For example, the ranking could come about from pairwise competitions between the candidate solutions in a Swiss-system tournament.

Principles

Two main principles for the adaptation of parameters of the search distribution are exploited in the CMA-ES algorithm.

First, a maximum-likelihood principle predicated on the idea that increasing (though not necessarily maximizing) the sample probability of successful candidate solutions or search directions is beneficial. The mean of the distribution is updated such that the likelihood of previously successful candidate solutions is maximized. The covariance matrix of the distribution is updated (incrementally) such that the likelihood of previously successful search steps is increased. Both updates can be interpreted as a natural gradient descent. Also, in consequence, the CMA conducts an iterated principal components analysis of successful search steps while retaining all principal axes. Estimation of distribution algorithms and the Cross-Entropy Method are based on very similar ideas, but generally estimate (non-incrementally) the covariance matrix by maximizing the likelihood of successful solution points rather than successful search steps.

Second, two paths of the time evolution of the distribution mean of the strategy are recorded, called search or evolution paths. These paths contain significant information about the correlation between consecutive steps. Specifically, if consecutive steps are taken in a similar direction, the evolution paths become long. The evolution paths are exploited in two ways. One path is used for the covariance matrix adaptation procedure in place of single successful search steps and facilitates a possibly much faster variance increase of favorable directions. The other path is used to conduct an additional step-size control. This step-size control aims to make consecutive movements of the distribution mean orthogonal in expectation. The step-size control effectively prevents premature convergence yet allowing fast convergence to an optimum.

Algorithm

In the following the most commonly used (μ/μw,λ)-CMA-ES is outlined, where in each iteration step a weighted combination of the μ best out of λ new candidate solutions is used to update the distribution parameters. The main loop consists of three main parts: 1) sampling of new solutions, 2) re-ordering of the sampled solutions based on their fitness, 3) update of the internal state variables based on the re-ordered samples. A pseudocode of the algorithm looks as follows.

set\lambda  // number of samples per iteration, at least two, generally > 4
initializem\sigmaC=Ip_\sigma=0p_c=0  // initialize state variables
while not terminate do  // iterate
    fori in\{1\ldots\lambda\} do\lambda new solutions and evaluate them
x_i ={}{}=m{}=\sigma^2 C )
f_i = \operatorname{fitness}(x_i)
x_{1\ldots\lambda} ←x_{s(1)\ldots s(\lambda)}s(i) = \operatorname{argsort}(f_{1\ldots\lambda}, i) // sort solutions
m' = mm - m'x_i - m'       
m ←(x_1, \ldots ,x_\lambda)  // move mean to better solutions 
p_\sigma ←(p_\sigma,\sigma^{-1} C^{-1/2} (m - m'))  // update isotropic evolution path
p_c ←(p_c,\sigma^{-1}(m - m'),\|p_\sigma\|)  // update anisotropic evolution path
C ←(C,p_c,(x_1 - m')/\sigma,\ldots ,(x_\lambda - m')/\sigma)  // update covariance matrix
\sigma ←(\sigma,\|p_\sigma\|)  // update step-size using isotropic path length
returnmx_1

must be updated last. The update equations for the five state variables are specified in the following.

. The five state variables are

  • , the distribution mean and current favorite solution to the optimization problem,

  • , the step-size,

  • , a symmetric and positive-definite covariance matrix and

  • , two evolution paths, initially set to the zero vector.

from a multivariate normal distribution

-sorted candidate solutions as

the new mean value is computed as

.

is updated using cumulative step-size adaptation (CSA), sometimes also denoted as path length control is updated first.

where

is larger than the expected value

and decreased if it is smaller. For this reason, the step-size update tends to make consecutive steps C_k^{-1}-conjugate.

Finally, the covariance matrix is updated, where again the respective evolution path is updated first.

denotes the transpose and

The covariance matrix update tends to increase the likelihood. This completes the iteration step.

by a factor of two for each restart. is predetermined by the number of available processors), the above introduced parameters are not specific to the given objective function and therefore not meant to be modified by the user.

Example code in MATLAB/Octave

Theoretical foundations

Given the distribution parametersmean, variances and covariancesthe normal probability distribution for sampling new candidate solutions is the maximum entropy probability distribution, that is, the sample distribution with the minimal amount of prior information built into the distribution. More considerations on the update equations of CMA-ES are made in the following.

Variable metric

The CMA-ES implements a stochastic variable-metric method. In the very particular case of a convex-quadratic objective function

adapts to the inverse of the Hessian matrix, up to, up to on a static model, relying on the quadratic approximation.

Maximum-likelihood updates

The update equations for mean and covariance matrix maximize a likelihood while resembling an expectation–maximization algorithm maximizes a log-likelihood, such that

where

remark first that this is the case for any diagonal matrix non-diagonal are equivalent.

, maximizes a log-likelihood in that

is the above maximum-likelihood estimator. See estimation of covariance matrices for details on the derivation.

Natural gradient descent in the space of sample distributions

Akimoto et al. and Glasmachers et al. discovered independently that the update of the distribution parameters resembles the descent in direction of a sampled natural gradient, i.e. without step-size control and rank-one update, CMA-ES can thus be viewed as an instantiation of Natural Evolution Strategies (NES). The natural gradient is independent of the parameterization of the distribution. Taken with respect to the parameters of the sample distribution can be expressed as

. The so-called score function, indicates the relative sensitivity of w.r.t. , and the expectation is taken with respect to the distribution . The natural gradient, complying with the Fisher information metric (an informational distance measure between probability distributions and the curvature of the relative entropy), now reads

where the Fisher information is the expectation of the Hessian of and renders the expression independent of the chosen parameterization. Combining the previous equalities we get

A Monte Carlo approximation of the latter expectation takes the average over samples from

.

Ollivier et al., as they are defined in the CMA-ES. The weights are an asymptotically consistent estimator of the CDFth order statistic, that is,

-values. More concisely, using the CDF-transformations. Now we define

is the density of the multivariate normal distribution is fixed

and for

and, after some calculations, the updates in the CMA-ES turn out as

and

) for the orthogonal parameters as well. with negative values only for the latter (so-called active CMA).

Stationarity or unbiasedness

, we find that

and under some mild additional assumptions on the initial conditions

and with an additional minor correction in the covariance matrix update for the case where the indicator function evaluates to zero, we find

Invariance

Invariance properties imply uniform performance on a class of objective functions. They have been argued to be an advantage, because they allow to generalize and predict the behavior of the algorithm and therefore strengthen the meaning of empirical results obtained on single functions. The following invariance properties have been established for CMA-ES.

Any serious parameter optimization method should be translation invariant, but most methods do not exhibit all the above described invariance properties. A prominent example with the same invariance properties is the Nelder–Mead method, where the initial simplex must be chosen respectively.

Convergence

Conceptual considerations like the scale-invariance property of the algorithm, the analysis of simpler evolution strategies for rank-based direct search methods can often be observed (depending on the context denoted as linear convergence or log-linear or exponential convergence). Informally, we can write

, and more rigorously

or similarly,

are remarkable and they are in both cases the best one can hope for in this kind of algorithm. Linear convergence of CMA-ES with probability one has been demonstrated for convex quadratic functions.

Interpretation as coordinate-system transformation

Using a non-identity covariance matrix for the multivariate normal distribution in evolution strategies is equivalent to a coordinate system transformation of the solution vectors, mainly because the sampling equation

The covariance matrix defines a bijective transformation (encoding) for all solution vectors into a space, where the sampling takes place with identity covariance matrix. Because the update equations in the CMA-ES are invariant under linear coordinate system transformations, the CMA-ES can be re-written as an adaptive encoding procedure applied to a simple evolution strategy with identity covariance matrix. This adaptive encoding procedure is not confined to algorithms that sample from a multivariate normal distribution (like evolution strategies), but can in principle be applied to any iterative search method.

Performance in practice

In contrast to most other evolutionary algorithms. Optionally, the number of candidate samples λ (population size) can be modified by the user in order to change the characteristic search behavior (see above) and termination conditions can or should be adjusted to the problem at hand.

The CMA-ES has been empirically successful in various applications and is considered to be particularly useful on non-convex, non-separable, ill-conditioned, multi-modal or noisy objective functions. One survey of Black-Box optimizations found it outranked 31 other optimization algorithms, performing especially strongly on "difficult functions" or larger-dimensional search spaces.

The search space dimension ranges typically between two and a few hundred. Assuming a black-box optimization scenario, where gradients are not available (or not useful) and function evaluations are the only considered cost of search, the CMA-ES method is likely to be outperformed by other methods in the following conditions:

function evaluations, the CMA-ES shows most often superior performance.

Variations and extensions

The (1+1)-CMA-ES the (1+1)-CMA-ES is a close variant of Gaussian adaptation. Some Natural Evolution Strategies) and they formalize the update of variances and covariances on a Cholesky factor instead of a covariance matrix. The CMA-ES has also been extended to multiobjective optimization as MO-CMA-ES. Another remarkable extension has been the addition of a negative update of the covariance matrix with the so-called active CMA. Using the additional active CMA update is considered as the default variant nowadays.

See also

References

Bibliography

fr:Stratégie d'évolution#CMA-ES