Class CMAESOptimizer
- All Implemented Interfaces:
BaseMultivariateOptimizer<MultivariateFunction>
,BaseMultivariateSimpleBoundsOptimizer<MultivariateFunction>
,BaseOptimizer<PointValuePair>
,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 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 function evaluations. On difficult problems the complete optimization (a single run) is expected to take roughly between and 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.
- Since:
- 3.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Deprecated.Used to sort fitness values.private class
Deprecated.Normalizes fitness values to the range [0,1].static class
Deprecated.Population size.static class
Deprecated.Input sigma values. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate RealMatrix
Deprecated.Coordinate system.private RealMatrix
Deprecated.B*D, stored for efficiency.private RealMatrix
Deprecated.Covariance matrix.private double
Deprecated.Cumulation constant.private double
Deprecated.Learning rate for rank-one update.private double
Deprecated.Learning rate for rank-one update - diagonalOnlyprivate double
Deprecated.Learning rate for rank-mu update'private double
Deprecated.Learning rate for rank-mu update - diagonalOnlyprivate int
Deprecated.Determines how often a new random offspring is generated in case it is not feasible / beyond the defined limits, default is 0.private double
Deprecated.Expectation of ||N(0,I)|| == norm(randn(N,1)).private double
Deprecated.Cumulation constant for step-size.private RealMatrix
Deprecated.Scaling.private double
Deprecated.Damping for step-size.static final int
Deprecated.Default value forcheckFeasableCount
: 0.static final int
Deprecated.Default value fordiagonalOnly
: 0.static final boolean
Deprecated.Default value forisActiveCMA
: true.static final int
Deprecated.Default value formaxIterations
: 30000.static final RandomGenerator
Deprecated.Default value forrandom
.static final double
Deprecated.Default value forstopFitness
: 0.0.private RealMatrix
Deprecated.Diagonal of C, used for diagonalOnly.private RealMatrix
Deprecated.Diagonal of sqrt(D), stored for efficiency.private int
Deprecated.Defines the number of initial iterations, where the covariance matrix remains diagonal and the algorithm has internally linear time complexity.private int
Deprecated.Number of objective variables/problem dimensionprivate double[]
Deprecated.History queue of best values.private boolean
Deprecated.Indicates whether statistic data is collected.private int
Deprecated.Size of history queue of best values.private double[]
Deprecated.private boolean
Deprecated.Covariance update mechanism, default is active CMA.private boolean
Deprecated.Number of objective variables/problem dimensionprivate int
Deprecated.Number of iterations already performed.private int
Deprecated.Population size, offspring number.private double
Deprecated.log(mu + 0.5), stored for efficiency.private int
Deprecated.Maximal number of iterations allowed.private int
Deprecated.Number of parents/points for recombination.private double
Deprecated.Variance-effectiveness of sum w_i x_i.private double
Deprecated.Norm of ps, stored for efficiency.private RealMatrix
Deprecated.Evolution path.private RealMatrix
Deprecated.Evolution path for sigma.private RandomGenerator
Deprecated.Random generator.private double
Deprecated.Overall standard deviation - search volume.private List
<RealMatrix> Deprecated.History of D matrix.Deprecated.History of fitness values.private List
<RealMatrix> Deprecated.History of mean matrix.Deprecated.History of sigma values.private double
Deprecated.Limit for fitness value.private double
Deprecated.Stop if fun-changes smaller stopTolFun.private double
Deprecated.Stop if back fun-changes smaller stopTolHistFun.private double
Deprecated.Stop if x-changes larger stopTolUpX.private double
Deprecated.Stop if x-change smaller stopTolX.private RealMatrix
Deprecated.Array for weighted recombination.private RealMatrix
Deprecated.Objective variables.Fields inherited from class org.apache.commons.math3.optimization.direct.BaseAbstractMultivariateOptimizer
evaluations
-
Constructor Summary
ConstructorsConstructorDescriptionDeprecated.As of version 3.1: Parameterlambda
must be passed with the call tooptimize
(whereas in the current code it is set to an undocumented value).CMAESOptimizer
(int lambda) Deprecated.As of version 3.1: Parameterlambda
must be passed with the call tooptimize
(whereas in the current code it is set to an undocumented value)..CMAESOptimizer
(int lambda, double[] inputSigma) Deprecated.CMAESOptimizer
(int lambda, double[] inputSigma, int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics) Deprecated.CMAESOptimizer
(int lambda, double[] inputSigma, int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker) Deprecated.CMAESOptimizer
(int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker) Deprecated. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
Deprecated.Checks dimensions and values of boundaries and inputSigma if defined.private static void
copyColumn
(RealMatrix m1, int col1, RealMatrix m2, int col2) Deprecated.Copies a column from m1 to m2.private static RealMatrix
diag
(RealMatrix m) Deprecated.private static RealMatrix
divide
(RealMatrix m, RealMatrix n) Deprecated.protected PointValuePair
Deprecated.Perform the bulk of the optimization algorithm.private static RealMatrix
eye
(int n, int m) Deprecated.Deprecated.Deprecated.Deprecated.Deprecated.private void
initializeCMA
(double[] guess) Deprecated.Initialization of the dynamic search parametersprivate static int[]
inverse
(int[] indices) Deprecated.private static RealMatrix
log
(RealMatrix m) Deprecated.private static double
max
(double[] m) Deprecated.private static double
max
(RealMatrix m) Deprecated.private static double
min
(double[] m) Deprecated.private static double
min
(RealMatrix m) Deprecated.private static RealMatrix
ones
(int n, int m) Deprecated.protected PointValuePair
optimizeInternal
(int maxEval, MultivariateFunction f, GoalType goalType, OptimizationData... optData) Deprecated.Optimize an objective function.private void
parseOptimizationData
(OptimizationData... optData) Deprecated.Scans the list of (required and optional) optimization data that characterize the problem.private static void
push
(double[] vals, double val) Deprecated.Pushes the current best fitness value in a history queue.private double[]
randn
(int size) Deprecated.private RealMatrix
randn1
(int size, int popSize) Deprecated.private static RealMatrix
repmat
(RealMatrix mat, int n, int m) Deprecated.private static int[]
reverse
(int[] indices) Deprecated.private static RealMatrix
selectColumns
(RealMatrix m, int[] cols) Deprecated.private static RealMatrix
sequence
(double start, double end, double step) Deprecated.private int[]
sortedIndices
(double[] doubles) Deprecated.Sorts fitness values.private static RealMatrix
sqrt
(RealMatrix m) Deprecated.private static RealMatrix
square
(RealMatrix m) Deprecated.private static RealMatrix
Deprecated.private static RealMatrix
times
(RealMatrix m, RealMatrix n) Deprecated.private static RealMatrix
triu
(RealMatrix m, int k) Deprecated.private void
updateBD
(double negccov) Deprecated.Update B and D from C.private void
updateCovariance
(boolean hsig, RealMatrix bestArx, RealMatrix arz, int[] arindex, RealMatrix xold) Deprecated.Update of the covariance matrix C.private void
updateCovarianceDiagonalOnly
(boolean hsig, RealMatrix bestArz) Deprecated.Update of the covariance matrix C for diagonalOnly > 0private boolean
updateEvolutionPaths
(RealMatrix zmean, RealMatrix xold) Deprecated.Update of the evolution paths ps and pc.private static RealMatrix
zeros
(int n, int m) Deprecated.Methods inherited from class org.apache.commons.math3.optimization.direct.BaseAbstractMultivariateSimpleBoundsOptimizer
optimize, optimize
Methods inherited from class org.apache.commons.math3.optimization.direct.BaseAbstractMultivariateOptimizer
computeObjectiveValue, getConvergenceChecker, getEvaluations, getGoalType, getLowerBound, getMaxEvaluations, getStartPoint, getUpperBound, optimize, optimizeInternal
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.apache.commons.math3.optimization.BaseMultivariateOptimizer
optimize
Methods inherited from interface org.apache.commons.math3.optimization.BaseOptimizer
getConvergenceChecker, getEvaluations, getMaxEvaluations
-
Field Details
-
DEFAULT_CHECKFEASABLECOUNT
public static final int DEFAULT_CHECKFEASABLECOUNTDeprecated.Default value forcheckFeasableCount
: 0.- See Also:
-
DEFAULT_STOPFITNESS
public static final double DEFAULT_STOPFITNESSDeprecated.Default value forstopFitness
: 0.0.- See Also:
-
DEFAULT_ISACTIVECMA
public static final boolean DEFAULT_ISACTIVECMADeprecated.Default value forisActiveCMA
: true.- See Also:
-
DEFAULT_MAXITERATIONS
public static final int DEFAULT_MAXITERATIONSDeprecated.Default value formaxIterations
: 30000.- See Also:
-
DEFAULT_DIAGONALONLY
public static final int DEFAULT_DIAGONALONLYDeprecated.Default value fordiagonalOnly
: 0.- See Also:
-
DEFAULT_RANDOMGENERATOR
Deprecated.Default value forrandom
. -
lambda
private int lambdaDeprecated.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 boolean isActiveCMADeprecated.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 int checkFeasableCountDeprecated.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[] inputSigmaDeprecated.- See Also:
-
dimension
private int dimensionDeprecated.Number of objective variables/problem dimension -
diagonalOnly
private int diagonalOnlyDeprecated.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:
-
isMinimize
private boolean isMinimizeDeprecated.Number of objective variables/problem dimension -
generateStatistics
private boolean generateStatisticsDeprecated.Indicates whether statistic data is collected. -
maxIterations
private int maxIterationsDeprecated.Maximal number of iterations allowed. -
stopFitness
private double stopFitnessDeprecated.Limit for fitness value. -
stopTolUpX
private double stopTolUpXDeprecated.Stop if x-changes larger stopTolUpX. -
stopTolX
private double stopTolXDeprecated.Stop if x-change smaller stopTolX. -
stopTolFun
private double stopTolFunDeprecated.Stop if fun-changes smaller stopTolFun. -
stopTolHistFun
private double stopTolHistFunDeprecated.Stop if back fun-changes smaller stopTolHistFun. -
mu
private int muDeprecated.Number of parents/points for recombination. -
logMu2
private double logMu2Deprecated.log(mu + 0.5), stored for efficiency. -
weights
Deprecated.Array for weighted recombination. -
mueff
private double mueffDeprecated.Variance-effectiveness of sum w_i x_i. -
sigma
private double sigmaDeprecated.Overall standard deviation - search volume. -
cc
private double ccDeprecated.Cumulation constant. -
cs
private double csDeprecated.Cumulation constant for step-size. -
damps
private double dampsDeprecated.Damping for step-size. -
ccov1
private double ccov1Deprecated.Learning rate for rank-one update. -
ccovmu
private double ccovmuDeprecated.Learning rate for rank-mu update' -
chiN
private double chiNDeprecated.Expectation of ||N(0,I)|| == norm(randn(N,1)). -
ccov1Sep
private double ccov1SepDeprecated.Learning rate for rank-one update - diagonalOnly -
ccovmuSep
private double ccovmuSepDeprecated.Learning rate for rank-mu update - diagonalOnly -
xmean
Deprecated.Objective variables. -
pc
Deprecated.Evolution path. -
ps
Deprecated.Evolution path for sigma. -
normps
private double normpsDeprecated.Norm of ps, stored for efficiency. -
B
Deprecated.Coordinate system. -
D
Deprecated.Scaling. -
BD
Deprecated.B*D, stored for efficiency. -
diagD
Deprecated.Diagonal of sqrt(D), stored for efficiency. -
C
Deprecated.Covariance matrix. -
diagC
Deprecated.Diagonal of C, used for diagonalOnly. -
iterations
private int iterationsDeprecated.Number of iterations already performed. -
fitnessHistory
private double[] fitnessHistoryDeprecated.History queue of best values. -
historySize
private int historySizeDeprecated.Size of history queue of best values. -
random
Deprecated.Random generator. -
statisticsSigmaHistory
Deprecated.History of sigma values. -
statisticsMeanHistory
Deprecated.History of mean matrix. -
statisticsFitnessHistory
Deprecated.History of fitness values. -
statisticsDHistory
Deprecated.History of D matrix.
-
-
Constructor Details
-
CMAESOptimizer
Deprecated.As of version 3.1: Parameterlambda
must be passed with the call tooptimize
(whereas in the current code it is set to an undocumented value).Default constructor, uses default parameters -
CMAESOptimizer
Deprecated.As of version 3.1: Parameterlambda
must be passed with the call tooptimize
(whereas in the current code it is set to an undocumented value)..- Parameters:
lambda
- Population size.
-
CMAESOptimizer
Deprecated.- Parameters:
lambda
- Population size.inputSigma
- Initial standard deviations to sample new points around the initial guess.
-
CMAESOptimizer
@Deprecated public CMAESOptimizer(int lambda, double[] inputSigma, int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics) Deprecated.- Parameters:
lambda
- Population size.inputSigma
- Initial standard deviations to sample new points around the initial guess.maxIterations
- Maximal number of iterations.stopFitness
- Whether to stop if objective function value is smaller thanstopFitness
.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.
-
CMAESOptimizer
@Deprecated public CMAESOptimizer(int lambda, double[] inputSigma, int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker) Deprecated.- Parameters:
lambda
- Population size.inputSigma
- Initial standard deviations to sample new points around the initial guess.maxIterations
- Maximal number of iterations.stopFitness
- Whether to stop if objective function value is smaller thanstopFitness
.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.
-
CMAESOptimizer
public CMAESOptimizer(int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker) Deprecated.- Parameters:
maxIterations
- Maximal number of iterations.stopFitness
- Whether to stop if objective function value is smaller thanstopFitness
.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 Details
-
getStatisticsSigmaHistory
Deprecated.- Returns:
- History of sigma values.
-
getStatisticsMeanHistory
Deprecated.- Returns:
- History of mean matrix.
-
getStatisticsFitnessHistory
Deprecated.- Returns:
- History of fitness values.
-
getStatisticsDHistory
Deprecated.- Returns:
- History of D matrix.
-
optimizeInternal
protected PointValuePair optimizeInternal(int maxEval, MultivariateFunction f, GoalType goalType, OptimizationData... optData) Deprecated.Optimize an objective function.- Overrides:
optimizeInternal
in classBaseAbstractMultivariateOptimizer<MultivariateFunction>
- Parameters:
maxEval
- Allowed number of evaluations of the objective function.f
- Objective function.goalType
- Optimization type.optData
- Optimization data. The following data will be looked for:- Returns:
- the point/value pair giving the optimal value for objective function.
-
doOptimize
Deprecated.Perform the bulk of the optimization algorithm.- Specified by:
doOptimize
in classBaseAbstractMultivariateOptimizer<MultivariateFunction>
- Returns:
- the point/value pair giving the optimal value of the objective function.
-
parseOptimizationData
Deprecated.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()Deprecated.Checks dimensions and values of boundaries and inputSigma if defined. -
initializeCMA
private void initializeCMA(double[] guess) Deprecated.Initialization of the dynamic search parameters- Parameters:
guess
- Initial guess for the arguments of the fitness function.
-
updateEvolutionPaths
Deprecated.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
Deprecated.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) Deprecated.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) Deprecated.Update B and D from C.- Parameters:
negccov
- Negative covariance factor.
-
push
private static void push(double[] vals, double val) Deprecated.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) Deprecated.Sorts fitness values.- Parameters:
doubles
- Array of values to be sorted.- Returns:
- a sorted array of indices pointing into doubles.
-
log
Deprecated.- Parameters:
m
- Input matrix- Returns:
- Matrix representing the element-wise logarithm of m.
-
sqrt
Deprecated.- Parameters:
m
- Input matrix.- Returns:
- Matrix representing the element-wise square root of m.
-
square
Deprecated.- Parameters:
m
- Input matrix.- Returns:
- Matrix representing the element-wise square of m.
-
times
Deprecated.- Parameters:
m
- Input matrix 1.n
- Input matrix 2.- Returns:
- the matrix where the elements of m and n are element-wise multiplied.
-
divide
Deprecated.- Parameters:
m
- Input matrix 1.n
- Input matrix 2.- Returns:
- Matrix where the elements of m and n are element-wise divided.
-
selectColumns
Deprecated.- Parameters:
m
- Input matrix.cols
- Columns to select.- Returns:
- Matrix representing the selected columns.
-
triu
Deprecated.- Parameters:
m
- Input matrix.k
- Diagonal position.- Returns:
- Upper triangular part of matrix.
-
sumRows
Deprecated.- Parameters:
m
- Input matrix.- Returns:
- Row matrix representing the sums of the rows.
-
diag
Deprecated.- 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
Deprecated.Copies a column from m1 to m2.- Parameters:
m1
- Source matrix.col1
- Source column.m2
- Target matrix.col2
- Target column.
-
ones
Deprecated.- Parameters:
n
- Number of rows.m
- Number of columns.- Returns:
- n-by-m matrix filled with 1.
-
eye
Deprecated.- 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
Deprecated.- Parameters:
n
- Number of rows.m
- Number of columns.- Returns:
- n-by-m matrix of zero values.
-
repmat
Deprecated.- 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
Deprecated.- Parameters:
start
- Start value.end
- End value.step
- Step size.- Returns:
- a sequence as column matrix.
-
max
Deprecated.- Parameters:
m
- Input matrix.- Returns:
- the maximum of the matrix element values.
-
min
Deprecated.- Parameters:
m
- Input matrix.- Returns:
- the minimum of the matrix element values.
-
max
private static double max(double[] m) Deprecated.- Parameters:
m
- Input array.- Returns:
- the maximum of the array values.
-
min
private static double min(double[] m) Deprecated.- Parameters:
m
- Input array.- Returns:
- the minimum of the array values.
-
inverse
private static int[] inverse(int[] indices) Deprecated.- Parameters:
indices
- Input index array.- Returns:
- the inverse of the mapping defined by indices.
-
reverse
private static int[] reverse(int[] indices) Deprecated.- Parameters:
indices
- Input index array.- Returns:
- the indices in inverse order (last is first).
-
randn
private double[] randn(int size) Deprecated.- Parameters:
size
- Length of random array.- Returns:
- an array of Gaussian random numbers.
-
randn1
Deprecated.- Parameters:
size
- Number of rows.popSize
- Population size.- Returns:
- a 2-dimensional matrix of Gaussian random numbers.
-