org.apache.commons.math3.optim.nonlinear.scalar.noderiv

## Class CMAESOptimizer

- java.lang.Object
- - org.apache.commons.math3.optim.BaseOptimizer<PAIR>
  - - org.apache.commons.math3.optim.BaseMultivariateOptimizer<PointValuePair>
    - - org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
      - - org.apache.commons.math3.optim.nonlinear.scalar.noderiv.CMAESOptimizer

    public class CMAESOptimizer
    extends MultivariateOptimizer

An implementation of the active Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for non-linear, non-convex, non-smooth, global function minimization. The CMA-Evolution Strategy (CMA-ES) is a reliable stochastic optimization method which should be applied if derivative-based methods, e.g. quasi-Newton BFGS or conjugate gradient, fail due to a rugged search landscape (e.g. noise, local optima, outlier, etc.) of the objective function. Like a quasi-Newton method, the CMA-ES learns and applies a variable metric on the underlying search space. Unlike a quasi-Newton method, the CMA-ES neither estimates nor uses gradients, making it considerably more reliable in terms of finding a good, or even close to optimal, solution.

In general, on smooth objective functions the CMA-ES is roughly ten times slower than BFGS (counting objective function evaluations, no gradients provided). For up to N=10 variables also the derivative-free simplex direct search method (Nelder and Mead) can be faster, but it is far less reliable than CMA-ES.

The CMA-ES is particularly well suited for non-separable and/or badly conditioned problems. To observe the advantage of CMA compared to a conventional evolution strategy, it will usually take about 30 N function evaluations. On difficult problems the complete optimization (a single run) is expected to take roughly between 30 N and 300 N2 function evaluations.

This implementation is translated and adapted from the Matlab version of the CMA-ES algorithm as implemented in module `cmaes.m` version 3.51.

For more information, please refer to the following links:

- Matlab code
- Introduction to CMA-ES
- Wikipedia

Since:
  3.0
Version:
  $Id: CMAESOptimizer.java 1400108 2012-10-19 14:20:16Z erans $

### Nested Class Summary

Nested Classes
`private static class` `CMAESOptimizer.DoubleIndex` Used to sort fitness values.
`private class` `CMAESOptimizer.FitnessFunction` Normalizes fitness values to the range [0,1].
`static class` `CMAESOptimizer.PopulationSize` Population size.
`static class` `CMAESOptimizer.Sigma` Input sigma values.

### Field Summary

Fields
`private RealMatrix` `B` Coordinate system.
`private RealMatrix` `BD` B*D, stored for efficiency.
`private RealMatrix` `C` Covariance matrix.
`private double` `cc` Cumulation constant.
`private double` `ccov1` Learning rate for rank-one update.
`private double` `ccov1Sep` Learning rate for rank-one update - diagonalOnly
`private double` `ccovmu` Learning rate for rank-mu update'
`private double` `ccovmuSep` Learning rate for rank-mu update - diagonalOnly
`private int` `checkFeasableCount` Determines how often a new random offspring is generated in case it is not feasible / beyond the defined limits, default is 0.
`private double` `chiN` Expectation of ||N(0,I)|| == norm(randn(N,1)).
`private double` `cs` Cumulation constant for step-size.
`private RealMatrix` `D` Scaling.
`private double` `damps` Damping for step-size.
`private RealMatrix` `diagC` Diagonal of C, used for diagonalOnly.
`private RealMatrix` `diagD` Diagonal of sqrt(D), stored for efficiency.
`private int` `diagonalOnly` Defines the number of initial iterations, where the covariance matrix remains diagonal and the algorithm has internally linear time complexity.
`private int` `dimension` Number of objective variables/problem dimension
`private double[]` `fitnessHistory` History queue of best values.
`private boolean` `generateStatistics` Indicates whether statistic data is collected.
`private int` `historySize` Size of history queue of best values.
`private double[]` `inputSigma`
`private boolean` `isActiveCMA` Covariance update mechanism, default is active CMA.
`private boolean` `isMinimize` Number of objective variables/problem dimension
`private int` `iterations` Number of iterations already performed.
`private int` `lambda` Population size, offspring number.
`private double` `logMu2` log(mu + 0.5), stored for efficiency.
`private int` `maxIterations` Maximal number of iterations allowed.
`private int` `mu` Number of parents/points for recombination.
`private double` `mueff` Variance-effectiveness of sum w_i x_i.
`private double` `normps` Norm of ps, stored for efficiency.
`private RealMatrix` `pc` Evolution path.
`private RealMatrix` `ps` Evolution path for sigma.
`private RandomGenerator` `random` Random generator.
`private double` `sigma` Overall standard deviation - search volume.
`private List<RealMatrix>` `statisticsDHistory` History of D matrix.
`private List<Double>` `statisticsFitnessHistory` History of fitness values.
`private List<RealMatrix>` `statisticsMeanHistory` History of mean matrix.
`private List<Double>` `statisticsSigmaHistory` History of sigma values.
`private double` `stopFitness` Limit for fitness value.
`private double` `stopTolFun` Stop if fun-changes smaller stopTolFun.
`private double` `stopTolHistFun` Stop if back fun-changes smaller stopTolHistFun.
`private double` `stopTolUpX` Stop if x-changes larger stopTolUpX.
`private double` `stopTolX` Stop if x-change smaller stopTolX.
`private RealMatrix` `weights` Array for weighted recombination.
`private RealMatrix` `xmean` Objective variables.

### Fields inherited from class org.apache.commons.math3.optim.BaseOptimizer

`evaluations`

### Constructor Summary

Constructors
Constructor and Description
`CMAESOptimizer(int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker)`

### Method Summary

Methods
`private void` `checkParameters()` Checks dimensions and values of boundaries and inputSigma if defined.
`private static void` `copyColumn(RealMatrix m1, int col1, RealMatrix m2, int col2)` Copies a column from m1 to m2.
`private static RealMatrix` `diag(RealMatrix m)`
`private static RealMatrix` `divide(RealMatrix m, RealMatrix n)`
`protected PointValuePair` `doOptimize()` Performs the bulk of the optimization algorithm.
`private static RealMatrix` `eye(int n, int m)`
`List<RealMatrix>` `getStatisticsDHistory()`
`List<Double>` `getStatisticsFitnessHistory()`
`List<RealMatrix>` `getStatisticsMeanHistory()`
`List<Double>` `getStatisticsSigmaHistory()`
`private void` `initializeCMA(double[] guess)` Initialization of the dynamic search parameters
`private static int[]` `inverse(int[] indices)`
`private static RealMatrix` `log(RealMatrix m)`
`private static double` `max(double[] m)`
`private static double` `max(RealMatrix m)`
`private static double` `min(double[] m)`
`private static double` `min(RealMatrix m)`
`private static RealMatrix` `ones(int n, int m)`
`PointValuePair` `optimize(OptimizationData... optData)` Stores data and performs the optimization.
`private void` `parseOptimizationData(OptimizationData... optData)` Scans the list of (required and optional) optimization data that characterize the problem.
`private static void` `push(double[] vals, double val)` Pushes the current best fitness value in a history queue.
`private double[]` `randn(int size)`
`private RealMatrix` `randn1(int size, int popSize)`
`private static RealMatrix` `repmat(RealMatrix mat, int n, int m)`
`private static int[]` `reverse(int[] indices)`
`private static RealMatrix` `selectColumns(RealMatrix m, int[] cols)`
`private static RealMatrix` `sequence(double start, double end, double step)`
`private int[]` `sortedIndices(double[] doubles)` Sorts fitness values.
`private static RealMatrix` `sqrt(RealMatrix m)`
`private static RealMatrix` `square(RealMatrix m)`
`private static RealMatrix` `sumRows(RealMatrix m)`
`private static RealMatrix` `times(RealMatrix m, RealMatrix n)`
`private static RealMatrix` `triu(RealMatrix m, int k)`
`private void` `updateBD(double negccov)` Update B and D from C.
`private void` `updateCovariance(boolean hsig, RealMatrix bestArx, RealMatrix arz, int[] arindex, RealMatrix xold)` Update of the covariance matrix C.
`private void` `updateCovarianceDiagonalOnly(boolean hsig, RealMatrix bestArz)` Update of the covariance matrix C for diagonalOnly > 0
`private boolean` `updateEvolutionPaths(RealMatrix zmean, RealMatrix xold)` Update of the evolution paths ps and pc.
`private static RealMatrix` `zeros(int n, int m)`

### Methods inherited from class org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer

`computeObjectiveValue, getGoalType`

### Methods inherited from class org.apache.commons.math3.optim.BaseMultivariateOptimizer

`getLowerBound, getStartPoint, getUpperBound`

### Methods inherited from class org.apache.commons.math3.optim.BaseOptimizer

`getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount`

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### Field Detail

#### lambda

    private int lambda

Population size, offspring number. The primary strategy parameter to play with, which can be increased from its default value. Increasing the population size improves global search properties in exchange to speed. Speed decreases, as a rule, at most linearly with increasing population size. It is advisable to begin with the default small population size.

#### isActiveCMA

    private final boolean isActiveCMA

Covariance update mechanism, default is active CMA. isActiveCMA = true turns on "active CMA" with a negative update of the covariance matrix and checks for positive definiteness. OPTS.CMA.active = 2 does not check for pos. def. and is numerically faster. Active CMA usually speeds up the adaptation.

#### checkFeasableCount

    private final int checkFeasableCount

Determines how often a new random offspring is generated in case it is not feasible / beyond the defined limits, default is 0.

#### inputSigma

    private double[] inputSigma

See Also:
  `CMAESOptimizer.Sigma`

#### dimension

    private int dimension

Number of objective variables/problem dimension

#### diagonalOnly

    private int diagonalOnly

Defines the number of initial iterations, where the covariance matrix remains diagonal and the algorithm has internally linear time complexity. diagonalOnly = 1 means keeping the covariance matrix always diagonal and this setting also exhibits linear space complexity. This can be particularly useful for dimension > 100.

See Also:
  A Simple Modification in CMA-ES

#### isMinimize

    private boolean isMinimize

Number of objective variables/problem dimension

#### generateStatistics

    private final boolean generateStatistics

Indicates whether statistic data is collected.

#### maxIterations

    private final int maxIterations

Maximal number of iterations allowed.

#### stopFitness

    private final double stopFitness

Limit for fitness value.

#### stopTolUpX

    private double stopTolUpX

Stop if x-changes larger stopTolUpX.

#### stopTolX

    private double stopTolX

Stop if x-change smaller stopTolX.

#### stopTolFun

    private double stopTolFun

Stop if fun-changes smaller stopTolFun.

#### stopTolHistFun

    private double stopTolHistFun

Stop if back fun-changes smaller stopTolHistFun.

#### mu

    private int mu

Number of parents/points for recombination.

#### logMu2

    private double logMu2

log(mu + 0.5), stored for efficiency.

#### weights

    private RealMatrix weights

Array for weighted recombination.

#### mueff

    private double mueff

Variance-effectiveness of sum w_i x_i.

#### sigma

    private double sigma

Overall standard deviation - search volume.

#### cc

    private double cc

Cumulation constant.

#### cs

    private double cs

Cumulation constant for step-size.

#### damps

    private double damps

Damping for step-size.

#### ccov1

    private double ccov1

Learning rate for rank-one update.

#### ccovmu

    private double ccovmu

Learning rate for rank-mu update'

#### chiN

    private double chiN

Expectation of ||N(0,I)|| == norm(randn(N,1)).

#### ccov1Sep

    private double ccov1Sep

Learning rate for rank-one update - diagonalOnly

#### ccovmuSep

    private double ccovmuSep

Learning rate for rank-mu update - diagonalOnly

#### xmean

    private RealMatrix xmean

Objective variables.

#### pc

    private RealMatrix pc

Evolution path.

#### ps

    private RealMatrix ps

Evolution path for sigma.

#### normps

    private double normps

Norm of ps, stored for efficiency.

#### B

    private RealMatrix B

Coordinate system.

#### D

    private RealMatrix D

Scaling.

#### BD

    private RealMatrix BD

B*D, stored for efficiency.

#### diagD

    private RealMatrix diagD

Diagonal of sqrt(D), stored for efficiency.

#### C

    private RealMatrix C

Covariance matrix.

#### diagC

    private RealMatrix diagC

Diagonal of C, used for diagonalOnly.

#### iterations

    private int iterations

Number of iterations already performed.

#### fitnessHistory

    private double[] fitnessHistory

History queue of best values.

#### historySize

    private int historySize

Size of history queue of best values.

#### random

    private final RandomGenerator random

Random generator.

#### statisticsSigmaHistory

    private final List<Double> statisticsSigmaHistory

History of sigma values.

#### statisticsMeanHistory

    private final List<RealMatrix> statisticsMeanHistory

History of mean matrix.

#### statisticsFitnessHistory

    private final List<Double> statisticsFitnessHistory

History of fitness values.

#### statisticsDHistory

    private final List<RealMatrix> statisticsDHistory

History of D matrix.

### Constructor Detail

#### CMAESOptimizer

    public CMAESOptimizer(int maxIterations,
                  double stopFitness,
                  boolean isActiveCMA,
                  int diagonalOnly,
                  int checkFeasableCount,
                  RandomGenerator random,
                  boolean generateStatistics,
                  ConvergenceChecker<PointValuePair> checker)

Parameters:
  `maxIterations` - Maximal number of iterations.
  `stopFitness` - Whether to stop if objective function value is smaller than `stopFitness`.
  `isActiveCMA` - Chooses the covariance matrix update method.
  `diagonalOnly` - Number of initial iterations, where the covariance matrix remains diagonal.
  `checkFeasableCount` - Determines how often new random objective variables are generated in case they are out of bounds.
  `random` - Random generator.
  `generateStatistics` - Whether statistic data is collected.
  `checker` - Convergence checker.
Since:
  3.1

### Method Detail

#### getStatisticsSigmaHistory

    public List<Double> getStatisticsSigmaHistory()

Returns:
  History of sigma values.

#### getStatisticsMeanHistory

    public List<RealMatrix> getStatisticsMeanHistory()

Returns:
  History of mean matrix.

#### getStatisticsFitnessHistory

    public List<Double> getStatisticsFitnessHistory()

Returns:
  History of fitness values.

#### getStatisticsDHistory

    public List<RealMatrix> getStatisticsDHistory()

Returns:
  History of D matrix.

#### optimize

    public PointValuePair optimize(OptimizationData... optData)
                            throws TooManyEvaluationsException,
                                   DimensionMismatchException

Stores data and performs the optimization.

Overrides:
  `optimize` in class `MultivariateOptimizer`
Parameters:
  `optData` - Optimization data. The following data will be looked for:
  - `MaxEval`
  - `InitialGuess`
  - `SimpleBounds`
  - `ObjectiveFunction`
  - `CMAESOptimizer.Sigma`
  - `CMAESOptimizer.PopulationSize`
Returns:
  a point/value pair that satifies the convergence criteria.
Throws:
  `TooManyEvaluationsException` - if the maximal number of evaluations is exceeded.
  `DimensionMismatchException` - if the initial guess, target, and weight arguments have inconsistent dimensions.

#### doOptimize

    protected PointValuePair doOptimize()

Performs the bulk of the optimization algorithm.

Specified by:
  `doOptimize` in class `BaseOptimizer<PointValuePair>`
Returns:
  the point/value pair giving the optimal value of the objective function.

#### parseOptimizationData

    private void parseOptimizationData(OptimizationData... optData)

Scans the list of (required and optional) optimization data that characterize the problem.

Parameters:
  `optData` - Optimization data. The following data will be looked for:
  - `CMAESOptimizer.Sigma`
  - `CMAESOptimizer.PopulationSize`

#### checkParameters

    private void checkParameters()

Checks dimensions and values of boundaries and inputSigma if defined.

#### initializeCMA

    private void initializeCMA(double[] guess)

Initialization of the dynamic search parameters

Parameters:
  `guess` - Initial guess for the arguments of the fitness function.

#### updateEvolutionPaths

    private boolean updateEvolutionPaths(RealMatrix zmean,
                               RealMatrix xold)

Update of the evolution paths ps and pc.

Parameters:
  `zmean` - Weighted row matrix of the gaussian random numbers generating the current offspring.
  `xold` - xmean matrix of the previous generation.
Returns:
  hsig flag indicating a small correction.

#### updateCovarianceDiagonalOnly

    private void updateCovarianceDiagonalOnly(boolean hsig,
                                    RealMatrix bestArz)

Update of the covariance matrix C for diagonalOnly > 0

Parameters:
  `hsig` - Flag indicating a small correction.
  `bestArz` - Fitness-sorted matrix of the gaussian random values of the current offspring.

#### updateCovariance

    private void updateCovariance(boolean hsig,
                        RealMatrix bestArx,
                        RealMatrix arz,
                        int[] arindex,
                        RealMatrix xold)

Update of the covariance matrix C.

Parameters:
  `hsig` - Flag indicating a small correction.
  `bestArx` - Fitness-sorted matrix of the argument vectors producing the current offspring.
  `arz` - Unsorted matrix containing the gaussian random values of the current offspring.
  `arindex` - Indices indicating the fitness-order of the current offspring.
  `xold` - xmean matrix of the previous generation.

#### updateBD

    private void updateBD(double negccov)

Update B and D from C.

Parameters:
  `negccov` - Negative covariance factor.

#### push

    private static void push(double[] vals,
            double val)

Pushes the current best fitness value in a history queue.

Parameters:
  `vals` - History queue.
  `val` - Current best fitness value.

#### sortedIndices

    private int[] sortedIndices(double[] doubles)

Sorts fitness values.

Parameters:
  `doubles` - Array of values to be sorted.
Returns:
  a sorted array of indices pointing into doubles.

#### log

    private static RealMatrix log(RealMatrix m)

Parameters:
  `m` - Input matrix
Returns:
  Matrix representing the element-wise logarithm of m.

#### sqrt

    private static RealMatrix sqrt(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  Matrix representing the element-wise square root of m.

#### square

    private static RealMatrix square(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  Matrix representing the element-wise square of m.

#### times

    private static RealMatrix times(RealMatrix m,
                   RealMatrix n)

Parameters:
  `m` - Input matrix 1.
  `n` - Input matrix 2.
Returns:
  the matrix where the elements of m and n are element-wise multiplied.

#### divide

    private static RealMatrix divide(RealMatrix m,
                    RealMatrix n)

Parameters:
  `m` - Input matrix 1.
  `n` - Input matrix 2.
Returns:
  Matrix where the elements of m and n are element-wise divided.

#### selectColumns

    private static RealMatrix selectColumns(RealMatrix m,
                           int[] cols)

Parameters:
  `m` - Input matrix.
  `cols` - Columns to select.
Returns:
  Matrix representing the selected columns.

#### triu

    private static RealMatrix triu(RealMatrix m,
                  int k)

Parameters:
  `m` - Input matrix.
  `k` - Diagonal position.
Returns:
  Upper triangular part of matrix.

#### sumRows

    private static RealMatrix sumRows(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  Row matrix representing the sums of the rows.

#### diag

    private static RealMatrix diag(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  the diagonal n-by-n matrix if m is a column matrix or the column matrix representing the diagonal if m is a n-by-n matrix.

#### copyColumn

    private static void copyColumn(RealMatrix m1,
                  int col1,
                  RealMatrix m2,
                  int col2)

Copies a column from m1 to m2.

Parameters:
  `m1` - Source matrix.
  `col1` - Source column.
  `m2` - Target matrix.
  `col2` - Target column.

#### ones

    private static RealMatrix ones(int n,
                  int m)

Parameters:
  `n` - Number of rows.
  `m` - Number of columns.
Returns:
  n-by-m matrix filled with 1.

#### eye

    private static RealMatrix eye(int n,
                 int m)

Parameters:
  `n` - Number of rows.
  `m` - Number of columns.
Returns:
  n-by-m matrix of 0 values out of diagonal, and 1 values on the diagonal.

#### zeros

    private static RealMatrix zeros(int n,
                   int m)

Parameters:
  `n` - Number of rows.
  `m` - Number of columns.
Returns:
  n-by-m matrix of zero values.

#### repmat

    private static RealMatrix repmat(RealMatrix mat,
                    int n,
                    int m)

Parameters:
  `mat` - Input matrix.
  `n` - Number of row replicates.
  `m` - Number of column replicates.
Returns:
  a matrix which replicates the input matrix in both directions.

#### sequence

    private static RealMatrix sequence(double start,
                      double end,
                      double step)

Parameters:
  `start` - Start value.
  `end` - End value.
  `step` - Step size.
Returns:
  a sequence as column matrix.

#### max

    private static double max(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  the maximum of the matrix element values.

#### min

    private static double min(RealMatrix m)

Parameters:
  `m` - Input matrix.
Returns:
  the minimum of the matrix element values.

#### max

    private static double max(double[] m)

Parameters:
  `m` - Input array.
Returns:
  the maximum of the array values.

#### min

    private static double min(double[] m)

Parameters:
  `m` - Input array.
Returns:
  the minimum of the array values.

#### inverse

    private static int[] inverse(int[] indices)

Parameters:
  `indices` - Input index array.
Returns:
  the inverse of the mapping defined by indices.

#### reverse

    private static int[] reverse(int[] indices)

Parameters:
  `indices` - Input index array.
Returns:
  the indices in inverse order (last is first).

#### randn

    private double[] randn(int size)

Parameters:
  `size` - Length of random array.
Returns:
  an array of Gaussian random numbers.

#### randn1

    private RealMatrix randn1(int size,
                    int popSize)

Parameters:
  `size` - Number of rows.
  `popSize` - Population size.
Returns:
  a 2-dimensional matrix of Gaussian random numbers.