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 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.For more information, please refer to the following links:
- Since:
- 3.0
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description 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.private static class
CMAESOptimizer.ValuePenaltyPair
Stores the value and penalty (for repair of out of bounds point).
-
Field Summary
Fields Modifier and Type Field Description 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 - diagonalOnlyprivate double
ccovmu
Learning rate for rank-mu update'private double
ccovmuSep
Learning rate for rank-mu update - diagonalOnlyprivate 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 dimensionprivate 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 dimensionprivate 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 java.util.List<RealMatrix>
statisticsDHistory
History of D matrix.private java.util.List<java.lang.Double>
statisticsFitnessHistory
History of fitness values.private java.util.List<RealMatrix>
statisticsMeanHistory
History of mean matrix.private java.util.List<java.lang.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 Description CMAESOptimizer(int maxIterations, double stopFitness, boolean isActiveCMA, int diagonalOnly, int checkFeasableCount, RandomGenerator random, boolean generateStatistics, ConvergenceChecker<PointValuePair> checker)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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)
java.util.List<RealMatrix>
getStatisticsDHistory()
java.util.List<java.lang.Double>
getStatisticsFitnessHistory()
java.util.List<RealMatrix>
getStatisticsMeanHistory()
java.util.List<java.lang.Double>
getStatisticsSigmaHistory()
private void
initializeCMA(double[] guess)
Initialization of the dynamic search parametersprivate 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.protected 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 > 0private boolean
updateEvolutionPaths(RealMatrix zmean, RealMatrix xold)
Update of the evolution paths ps and pc.private double
valueRange(CMAESOptimizer.ValuePenaltyPair[] vpPairs)
Get range of values.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, optimize
-
-
-
-
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 java.util.List<java.lang.Double> statisticsSigmaHistory
History of sigma values.
-
statisticsMeanHistory
private final java.util.List<RealMatrix> statisticsMeanHistory
History of mean matrix.
-
statisticsFitnessHistory
private final java.util.List<java.lang.Double> statisticsFitnessHistory
History of fitness values.
-
statisticsDHistory
private final java.util.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 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 Detail
-
getStatisticsSigmaHistory
public java.util.List<java.lang.Double> getStatisticsSigmaHistory()
- Returns:
- History of sigma values.
-
getStatisticsMeanHistory
public java.util.List<RealMatrix> getStatisticsMeanHistory()
- Returns:
- History of mean matrix.
-
getStatisticsFitnessHistory
public java.util.List<java.lang.Double> getStatisticsFitnessHistory()
- Returns:
- History of fitness values.
-
getStatisticsDHistory
public java.util.List<RealMatrix> getStatisticsDHistory()
- Returns:
- History of D matrix.
-
optimize
public PointValuePair optimize(OptimizationData... optData) throws TooManyEvaluationsException, DimensionMismatchException
Stores data and performs the optimization.The list of parameters is open-ended so that sub-classes can extend it with arguments specific to their concrete implementations.
When the method is called multiple times, instance data is overwritten only when actually present in the list of arguments: when not specified, data set in a previous call is retained (and thus is optional in subsequent calls).
Important note: Subclasses must override
BaseOptimizer.parseOptimizationData(OptimizationData[])
if they need to register their own options; but then, they must also callsuper.parseOptimizationData(optData)
within that method.- Overrides:
optimize
in classMultivariateOptimizer
- Parameters:
optData
- Optimization data. In addition to those documented inMultivariateOptimizer
, this method will register the following data:- Returns:
- a point/value pair that satisfies 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 classBaseOptimizer<PointValuePair>
- Returns:
- the point/value pair giving the optimal value of the objective function.
-
parseOptimizationData
protected void parseOptimizationData(OptimizationData... optData)
Scans the list of (required and optional) optimization data that characterize the problem.- Overrides:
parseOptimizationData
in classMultivariateOptimizer
- 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.
-
valueRange
private double valueRange(CMAESOptimizer.ValuePenaltyPair[] vpPairs)
Get range of values.- Parameters:
vpPairs
- Array of valuePenaltyPairs to get range from.- Returns:
- a double equal to maximum value minus minimum value.
-
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.
-
-