Class 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
    • 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.
      • 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.
      • ps

        private RealMatrix ps
        Evolution path for sigma.
      • normps

        private double normps
        Norm of ps, stored for efficiency.
      • BD

        private RealMatrix BD
        B*D, stored for efficiency.
      • diagD

        private RealMatrix diagD
        Diagonal of sqrt(D), stored for efficiency.
      • 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.
      • 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 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 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.
      • 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.