CMAES (Covariance Matrix Adaptation Evolution Strategy)

This is the implementation of the Covariance Matrix Adaptation Evolution Strategy, as published in Hansen2006. In an evolution strategy, new candidate solutions are sampled according to a multivariate normal distribution in \(\mathbb {R} ^{n}\). 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 of this distribution. CMAES works iteratively, evaluating a number \(\lambda\) of samples per generation, and improving the covariance matrix for the samples in the next generation.

This solver also implements the Constrained Covariance Matrix Adaptation Evolution Strategy, as published in Arampatzis2019 and a version that includes gradient information Chen2009.

CCMAES is an extension of CMAES for constrained optimization problems. It uses the principle of viability boundaries to find an initial mean vector for the proposal distribution that does not violate constraints, and secondly it uses a constraint handling technique to efficiently adapt the proposal distribution to the constraints.

Usage

e["Solver"]["Type"] = "Optimizer/CMAES"

Results

These are the results produced by this solver:

Best F(x)

  • Usage: e[“Results”][“Best F(x)”] = real number

  • Description: Optimal value of F(x) found so far.

Best Parameters

  • Usage: e[“Results”][“Best Parameters”] = List of real number

  • Description: Value for the x parameters that produced the best F(x).

Variable-Specific Settings

These are settings required by this module that are added to each of the experiment’s variables when this module is selected.

Granularity

  • Usage: e[“Variables”][index][“Granularity”] = real number

  • Description: Specifies the granularity of a discrete variable, a granularity of 1.0 means that the variable can only take values in (.., -1.0, 0.0, +1.0, +2.0, ..) where the levels are set symmetric around the initial mean (here 0.0).

Lower Bound

  • Usage: e[“Variables”][index][“Lower Bound”] = real number

  • Description: [Hint] Lower bound for the variable’s value.

Upper Bound

  • Usage: e[“Variables”][index][“Upper Bound”] = real number

  • Description: [Hint] Upper bound for the variable’s value.

Initial Value

  • Usage: e[“Variables”][index][“Initial Value”] = real number

  • Description: [Hint] Initial value at or around which the algorithm shall start looking for an optimum.

Initial Mean

  • Usage: e[“Variables”][index][“Initial Mean”] = real number

  • Description: [Hint] Initial mean for the proposal distribution. This value must be defined between the variable’s Mininum and Maximum settings (by default, this value is given by the center of the variable domain).

Initial Standard Deviation

  • Usage: e[“Variables”][index][“Initial Standard Deviation”] = real number

  • Description: [Hint] Initial standard deviation of the proposal distribution for a variable (by default, this value is given by 30% of the variable domain width).

Minimum Standard Deviation Update

  • Usage: e[“Variables”][index][“Minimum Standard Deviation Update”] = real number

  • Description: [Hint] Lower bound for the standard deviation updates of the proposal distribution for a variable. Korali increases the scaling factor sigma if this value is undershot.

Values

  • Usage: e[“Variables”][index][“Values”] = List of real number

  • Description: [Hint] Locations to evaluate the Objective Function.

Configuration

These are settings required by this module.

Population Size

  • Usage: e[“Solver”][“Population Size”] = unsigned integer

  • Description: Specifies the number of samples to evaluate per generation (preferably $4+3*log(N)$, where $N$ is the number of variables).

Mu Value

  • Usage: e[“Solver”][“Mu Value”] = unsigned integer

  • Description: Number of best samples (offspring samples) used to update the covariance matrix and the mean (by default it is half the Sample Count).

Mu Type

  • Usage: e[“Solver”][“Mu Type”] = string

  • Description: Weights given to the Mu best values to update the covariance matrix and the mean.

  • Options:

    • “Linear”: Distributes Mu weights linearly decreasing.

    • “Equal”: Distributes Mu weights equally.

    • “Logarithmic”: Distributes Mu weights logarithmically decreasing.

    • “Proportional”: Distributes Mu weights proportional to objective function evaluation.

Initial Sigma Cumulation Factor

  • Usage: e[“Solver”][“Initial Sigma Cumulation Factor”] = real number

  • Description: Controls the learning rate of the conjugate evolution path (by default this variable is internally calibrated).

Initial Damp Factor

  • Usage: e[“Solver”][“Initial Damp Factor”] = real number

  • Description: Controls the updates of the covariance matrix scaling factor (by default this variable is internally calibrated).

Use Gradient Information

  • Usage: e[“Solver”][“Use Gradient Information”] = True/False

  • Description: Include gradient information for proposal distribution update.

Gradient Step Size

  • Usage: e[“Solver”][“Gradient Step Size”] = float

  • Description: Scaling factor for gradient step, only relevant if gradient information used.

Is Sigma Bounded

  • Usage: e[“Solver”][“Is Sigma Bounded”] = True/False

  • Description: Sets an upper bound for the covariance matrix scaling factor. The upper bound is given by the average of the initial standard deviation of the variables.

Initial Cumulative Covariance

  • Usage: e[“Solver”][“Initial Cumulative Covariance”] = real number

  • Description: Controls the learning rate of the evolution path for the covariance update (must be in (0,1], by default this variable is internally calibrated).

Diagonal Covariance

  • Usage: e[“Solver”][“Diagonal Covariance”] = True/False

  • Description: Covariance matrix updates will be optimized for diagonal matrices.

Mirrored Sampling

  • Usage: e[“Solver”][“Mirrored Sampling”] = True/False

  • Description: Generate the negative counterpart of each random number during sampling.

Viability Population Size

  • Usage: e[“Solver”][“Viability Population Size”] = unsigned integer

  • Description: Specifies the number of samples per generation during the viability regime, i.e. during the search for a parameter vector not violating the constraints.

Viability Mu Value

  • Usage: e[“Solver”][“Viability Mu Value”] = unsigned integer

  • Description: Number of best samples used to update the covariance matrix and the mean during the viability regime (by default this variable is half the Viability Sample Count).

Max Covariance Matrix Corrections

  • Usage: e[“Solver”][“Max Covariance Matrix Corrections”] = unsigned integer

  • Description: Max number of covairance matrix adaptions per generation during the constraint handling loop.

Target Success Rate

  • Usage: e[“Solver”][“Target Success Rate”] = real number

  • Description: Controls the updates of the covariance matrix scaling factor during the viability regime.

Covariance Matrix Adaption Strength

  • Usage: e[“Solver”][“Covariance Matrix Adaption Strength”] = real number

  • Description: Controls the covariane matrix adaption strength if samples violate constraints.

Normal Vector Learning Rate

  • Usage: e[“Solver”][“Normal Vector Learning Rate”] = real number

  • Description: Learning rate of constraint normal vectors (must be in (0, 1], by default this variable is internally calibrated).

Global Success Learning Rate

  • Usage: e[“Solver”][“Global Success Learning Rate”] = real number

  • Description: Learning rate of success probability of objective function improvements.

Termination Criteria

These are the customizable criteria that indicates whether the solver should continue or finish execution. Korali will stop when at least one of these conditions are met. The criteria is expressed in C++ since it is compiled and evaluated as seen here in the engine.

Max Condition Covariance Matrix

  • Usage: e[“Solver”][“Max Condition Covariance Matrix”] = real number

  • Description: Specifies the maximum condition of the covariance matrix.

  • Criteria: _k->_currentGeneration > 1 && (_maximumCovarianceEigenvalue >= _maxConditionCovarianceMatrix * _minimumCovarianceEigenvalue)

Min Standard Deviation

  • Usage: e[“Solver”][“Min Standard Deviation”] = real number

  • Description: Specifies the minimal standard deviation for any variable in any proposed sample.

  • Criteria: _k->_currentGeneration > 1 && (_currentMinStandardDeviation <= _minStandardDeviation)

Max Standard Deviation

  • Usage: e[“Solver”][“Max Standard Deviation”] = real number

  • Description: Specifies the maximal standard deviation for any variable in any proposed sample.

  • Criteria: _k->_currentGeneration > 1 && (_currentMaxStandardDeviation >= _maxStandardDeviation)

Max Value

  • Usage: e[“Solver”][“Max Value”] = real number

  • Description: Specifies the maximum target fitness to stop maximization.

  • Criteria: _k->_currentGeneration > 1 && (+_bestEverValue > _maxValue)

Min Value Difference Threshold

  • Usage: e[“Solver”][“Min Value Difference Threshold”] = real number

  • Description: Specifies the minimum fitness differential between two consecutive generations before stopping execution.

  • Criteria: _k->_currentGeneration > 1 && (fabs(_currentBestValue - _previousBestValue) < _minValueDifferenceThreshold)

Max Infeasible Resamplings

  • Usage: e[“Solver”][“Max Infeasible Resamplings”] = unsigned integer

  • Description: Maximum number of resamplings per candidate per generation if sample is outside of Lower and Upper Bound.

  • Criteria: (_maxInfeasibleResamplings > 0) && (_infeasibleSampleCount >= _maxInfeasibleResamplings)

Max Model Evaluations

  • Usage: e[“Solver”][“Max Model Evaluations”] = unsigned integer

  • Description: Specifies the maximum allowed evaluations of the computational model.

  • Criteria: _maxModelEvaluations <= _modelEvaluationCount

Max Generations

  • Usage: e[“Solver”][“Max Generations”] = unsigned integer

  • Description: Determines how many solver generations to run before stopping execution. Execution can be resumed at a later moment.

  • Criteria: _k->_currentGeneration > _maxGenerations

Default Configuration

These following configuration will be assigned by default. Any settings defined by the user will override the given settings specified in these defaults.

{
"Best Ever Value": -Infinity,
"Covariance Matrix Adaption Strength": 0.1,
"Current Max Standard Deviation": -Infinity,
"Current Min Standard Deviation": Infinity,
"Diagonal Covariance": false,
"Global Success Learning Rate": 0.2,
"Gradient Step Size": 0.01,
"Initial Cumulative Covariance": -1.0,
"Initial Damp Factor": -1.0,
"Initial Sigma Cumulation Factor": -1.0,
"Is Sigma Bounded": false,
"Max Covariance Matrix Corrections": 1000000,
"Maximum Covariance Eigenvalue": -Infinity,
"Minimum Covariance Eigenvalue": Infinity,
"Mirrored Sampling": false,
"Model Evaluation Count": 0,
"Mu Type": "Logarithmic",
"Mu Value": 0,
"Normal Generator": {
    "Mean": 0.0,
    "Standard Deviation": 1.0,
    "Type": "Univariate/Normal"
    },
"Normal Vector Learning Rate": -1.0,
"Population Size": 0,
"Target Success Rate": 0.1818,
"Termination Criteria": {
    "Max Condition Covariance Matrix": Infinity,
    "Max Generations": 10000000000,
    "Max Infeasible Resamplings": 1000000,
    "Max Model Evaluations": 1000000000,
    "Max Standard Deviation": Infinity,
    "Max Value": Infinity,
    "Min Standard Deviation": -Infinity,
    "Min Value Difference Threshold": -Infinity
    },
"Uniform Generator": {
    "Maximum": 1.0,
    "Minimum": 0.0,
    "Type": "Univariate/Uniform"
    },
"Use Gradient Information": false,
"Variable Count": 0,
"Viability Mu Value": 0,
"Viability Population Size": 2
}

Variable Defaults

These following configuration will be assigned to each of the experiment variables by default. Any settings defined by the user will override the given settings specified in these defaults.

{
"Granularity": 0.0,
"Initial Mean": NaN,
"Initial Standard Deviation": NaN,
"Initial Value": NaN,
"Lower Bound": -Infinity,
"Minimum Standard Deviation Update": 0.0,
"Upper Bound": Infinity,
"Values": []
}