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

java.lang.Object
  extended by org.apache.commons.math3.optim.BaseOptimizer<PAIR>
      extended by org.apache.commons.math3.optim.BaseMultivariateOptimizer<PointValuePair>
          extended by org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
              extended by 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:

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

Nested Class Summary
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
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
CMAESOptimizer(int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker)
           
 
Method Summary
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:
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:

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.


Copyright (c) 2003-2013 Apache Software Foundation