Covariance Matrix Adaptation ES - GII/JEAF GitHub Wiki

The algorithm CMA-ES was firstly proposed by Nikolaus Hansen and Andreas Ostermeier in [1] . This algorithm uses a multivariate normal distribution to generate a new population each generation. The CMA-ES is a second order approximation algorithm, i.e., with the adaptation of the parameters of the covariance matrix is able to obtain information about the dependencies between the variables of the problem and to adapt them according to these dependencies during the optimization process. It behavior is based on the estimation, according to an iterative process, the covariance matrix of a multivariate normal distribution that approximates the problem parameters. This matrix is closely related with the Hessian inverse matrix. In optimization, this matrix is used to determine the critical points of a function using the second derivatives. However, there are problems in which it is not possible to obtain the Hessian matrix or the critical points, either because the function is not derivable or because the computation of this matrix is highly computational expensive due to the large number of problem parameters. The covariance matrix allow to adjust the distribution used during the search process to the contour of the function to be optimized. By using the covariance matrix instead of the Hessian matrix, the algorithm do not use or even approximate gradients. The CMA-ES algorithm obtain successful results in discontinuous, multimodal, noise and ruggedness functions. It is invariant to rotations, reflections and translations of the search space.

The next diagram shows the JEAF elements developed to support the CMA-ES implementation. First, it is necessary to implement a main class, the CMAEvolutionaryAlgorithm Class. This class is used to store and modify parameters that are common to different elements of the CMA-ES implementation like the operators.

As an example, a CMA-ES configuration file could be found here. Following, the main elements of this configuration file are explained.

The Evolutionary Algorithm Class tag should indicate that the class that we want to instantiate is the CMAEvolutionaryAlgorithm Class. This class represents a CMA-ES algorithm. It is used to store the parameters that are common to the elementes necesary to run it like the operators or the StopTests.

To configure this algorithm it is necessary to indicate the following parameters. None of them are mandatory, if they do not appear in the configuration file, the algorithm set them to their default values with the method setDefaultParameters.

• InitialX: one or N values that indicate the initial value of xMean.
• TypicalX: one or N values that indicate the initial value of typicalX used to generate the initial values of xMean.
• InitialStandardDeviation: one or N values that indicate the initial value of sigma.
• Mu: an integer value that indicates the number of elements used to update the parameters of the distribution that samples the population at each generation.
• RecombinationType: Plugin used to generates the weights to update the distribution.
• Cs: step-size cumulation parameter.
• Damps: step-size damping parameter.
• DiagonalCovarianceMatrix: an integer value which indicates the number of initial iterations with diagonal covariance matrix, where 1 means always, -1 means default value 150*N/lambda and 0 means never.

where N is the dimension of the problem.

As a subclass of EvolutionaryStrategy, it is also necessary to indicate the value of the parameters Lambda. Again, it is not necessary to specified its value, in this case the default value is used.

As any EA of the JEAF library, it is necessary to indicate and to configure the Comparator Class and the EvaluationStrategy Class.

The Population, Objective, StopTests and LogTools elements are configured as any other Evolutionary Algorithm in JEAF. An explanation about how they should be configured could be found here.

The OperatorChain element is configured as a common operator chain, but two operators should be used. At this version, two operators are implemented. The CMAUpdateDistributionOperator is implemented as a selection operator. It is in charge of update the parameters that are used to generate the multivariate normal distribution by using the information provided by the individuals of the population. The CMASamplePopulationOperator generates a new population from the updated covariance matrix.

<OperatorChains>
   <SelectionChain>
      <Operator>
         <Class>es.udc.gii.common.eaf.algorithm.operator.selection.CMAUpdateDistributionOperator</Class>        
      </Operator>
   </SelectionChain>
   <ReproductionChain>
      <Operator>
         <Class>es.udc.gii.common.eaf.algorithm.operator.reproduction.CMASamplePopulationOperator</Class>
      </Operator>
   </ReproductionChain>
<OperatorChains/>

In a latter version of the CMA-ES [2] , the authors introduce a restart-CMA-ES strategy. At each generation, the restart criteria are evaluated, if one of the is fulfill the algorithm restart according to the restart strategy. At the current JEAF version the restart strategy proposed in [ 2 ], the IPOP-stategy, is implemented ( IPOPRestartStrategy Class). Each time the algorithm fulfill the restart criteria, the algorithm population size is increased by a factor of IncrPopFactor.

<RestartStrategy>
   <Class>es.udc.gii.common.eaf.algorithm.restart.IPOPRestartStrategy</Class>
      <MaxNumRestarts>4</MaxNumRestarts>
      <IncrPopFactor>2.0</IncrPopFactor>
</RestartStrategy>
<RestartTests>
   <RestartTest>
      <Class>es.udc.gii.common.eaf.stoptest.cma.CMATolXStopTest</Class>
   </RestartTest>
   <RestartTest>
      <Class>es.udc.gii.common.eaf.stoptest.cma.CMATolXUpStopTest</Class>
   </RestartTest>
   <RestartTest>
      <Class>es.udc.gii.common.eaf.stoptest.TolFunStopTest</Class>
      <TolFun>1.0e-11</TolFun>
   </RestartTest>
</RestartTests>

At this version, the restart criteria used in [2] are implemented. This restart criteria behave as follows:

• TolFunStopTest: stop when the function value changes below TolFun.
• TolFunHistStopTest: stop when history of function value changes below TolFunHist.
• CMATolXStopTest: stop when standard deviation below TolX.
• CMATolXUpStopTest: stop when standard deviation increased by more than TolXUpFactor.

For more information about the CMA-ES, visit the authors homepage at https://www.lri.fr/~hansen/cmaesintro.html.