Package ec.eda.cmaes

# Class CMAESSpecies

java.lang.Object
ec.Species
ec.vector.VectorSpecies
ec.vector.FloatVectorSpecies
ec.eda.cmaes.CMAESSpecies

All Implemented Interfaces:
  `Prototype`, `Setup`, `Serializable`, `Cloneable`

public class CMAESSpecies extends FloatVectorSpecies
CMAESSpecies is a FloatVectorSpecies which implements a faithful version of the CMA-ES algorithm. The class has two basic methods. The newIndividual(...) method generates a new random individual underneath the current CMA-ES gaussian distribution. The updateDistribution(...) method revises the gaussian distribution to reflect the fitness results of the population.

CMAESSpecies must be used in combination with CMAESBreeder, which will call it at appropriate times to revise the distribution and to generate a new subpopulation of individuals. It must also be used in combination with CMAESInitializer, which will use it to generate the initial population.

Note importantly that CMAESSpecies ignores the subpopulation size. Instead the first thing it will do is revise the subpopulation size to reflect the "lambda" parameter. This is a consequence of another feature of CMAESSpecies: many of its parameters do not have fixed default values, but rather values which are computed on the fly if the user does not provide them. For this reason, it also prints out these values when running so the user may see what values it used for that given run. The computed default values use equations which are common in the CMA-ES literature and are described below.

CMAESSpecies also has an "alternative termination" option. Normally ECJ terminates when the optimal individual is discovered or when the generations or maximum number of evaluations has been exceeded. CMA-ES can optionally terminate when the eigenvalues of the covariance matrix of its gaussian distribution are too small. Among other things, this will generally prevent CMA-ES from terminating abnormally because an eigenvalue has gone negative (due to floating point underflows). But by default this alternative termination is turned off, and CMA-ES will simply terminate in that case.

CMAESSpecies needs initial values of sigma (the scaling parameter for its covariance matrix) and the mean of the gaussian distribution. By default sigma's initial value is 1.0. The mean must be set to one of "zero" (meaning the origin), "center" (meaning the center of the genome space defined by the min and max gene values for each gene), or "random" (meaning a randomly- chosen point in the space". If it is not set to any of these, you may alternatively set the initial mean values by hand. But you must do one of the two.

Initializing the covariance matrix can be a problem in in CMA-ES, particularly if it is large relative to the gene bounds. If CMA-ES generates a random individual under its current distribution and that individual violates the bounds of just a single gene, it is invalid and must be regenerated. If you have a lot of genes, and the covariance matrix is large relative to their bounds, then the probability that this will occur rapidly approaches 1.0, so CMA-ES will be trapped in an effectively infinite loop endlessly producing invalid individuals.

This can be remedied in a few ways. First there is an option available to force the initial covariance matrix to NOT be the identity matrix (the default) but instead be scaled according to the gene bounds. That may help. You can also of course reduce sigma. Last, you can turn on an alternative individual generation mechanism; here, if a specific gene bound is violated, then *for that gene only* the value is chosen at random uniformly from within the gene bounds.

CMAESSpecies relies on the EJML matrix library, available at http://ejml.org/

Parameters

base.`mean` String, one of center, zero, or random | (the initial mean for the distribution) If not provided, base.`mean`.0 and so on must be given
base.`mean` String, one of center, zero, or random | (the initial mean for the distribution) If not provided, base.`mean`.0 and so on must be given
base.`mean`.i Floating-point value | (the value of dimension i of the initial mean vector) These values will override those set as a result of base.`mean`
base.`sigma` Floating-point value > 0.0 | (the sigma scaling parameter) If not provided, this defaults to 1.0.
base.`lambda` Integer > base.`mu` | (lambda population size) If not provided, this defaults to 4 + Math.floor(3 * Math.log(n)).
base.`lambda` Integer > 1 | (mu truncated population size) If not provided, this defaults to Math.floor(lambda / 2.0).
base.`weight`.i Float >= 0 | (weight for individual i (i from 0 to mu-1)) If not provided, this defaults to Math.log((lambda + 1.0) / (2.0 * (i + 1))).
base.`cc` 0 <= Float < 1 | (c_c parameter) If not provided, this defaults to (4.0+mueff/n) / (n+4.0 + 2.0*mueff/n) Where mueff is defined in the variables below, and n is the genome size
base.`cs` 0 <= Float < 1 | (c_sigma parameter) If not provided, this defaults to (mueff+2.0)/(n+mueff+5.0) Where mueff is defined in the variables below, and n is the genome size
base.`c1` 0 <= Float < 1 (and c1 > (1-cmu)) | (c_1 parameter) If not provided, this defaults to 2.0 / ((n+1.3)*(n+1.3)+mueff) Where mueff is defined in the variables below, and n is the genome size
base.`cmu` 0 <= Float < 1 (and cmu > (1-c1)) | (c_mu parameter) If not provided, this defaults to Math.min(1.0-c1, 2.0*(mueff-2.0+1.0/mueff) / ((n+2.0)*(n+2.0)+mueff)) Where mueff is defined in the variables below, and n is the genome size
base.`damps` 0 <= Float < 1 | (d_sigma dampening parameter) If not provided, this defaults to 1.0 + 2.0*Math.max(0.0, Math.sqrt((mueff-1.0)/(n+1.0))-1.0) + cs Where mueff is defined in the variables below, and n is the genome size
base.`covariance` String, either "identity" (default) or "scaled" | Covariance matrix initialization procedure. If "identity", then the covariance matrix is initialized to the identity matrix. If "scaled", then the covariance matrix is initialized to a diagonal matrix whose values are squares of each gene range (max - min).
base.`alternative-generator` true or false (default) | Whether or not to use the alternative indivdiual-generation procedure. If "true", then if, in the process of generating an individual, we have failed alternative-generator-tries times to create an individual which falls within the min and max gene values for each gene, then whenever a gene value violates those constraints we will simply randomize it to something uniformly chosen between the min and max. If "false", then whenever an individual violates constraints, we will try again as necessary.
base.`alternative-generator-tries` Integer > 1 (default is 100) | How many times we try to generate a valid individual before possibly using the alternative-generator approach.
base.`alternative-termination` boolean, default false | Should we also terminate on CMA-ES's additional termination conditions?.

Default Base
eda.cma-es.species

See Also:
  - Serialized Form

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `int`
  `altGeneratorTries`
  How many times should we try to generate a valid individual before we give up and use the useAltGenerator approach?
  `org.ejml.simple.SimpleMatrix`
  `b`
  The "B" matrix, eigendecomposed from the "C" covariance matrix of the distribution.
  `org.ejml.data.DenseMatrix64F`
  `bd`
  b x d
  `org.ejml.simple.SimpleMatrix`
  `c`
  The "C" covariance matrix of the distribution.
  `double`
  `c1`
  The c_1 rank-1 update learning rate.
  `double`
  `cc`
  The c_c rank-one evolution path cumulation parameter.
  `double`
  `chiN`
  An estimate of the expected size of the standard multivariate gaussian N(0,I).
  `double`
  `cmu`
  The c_{\mu} rank-mu update learning rate.
  `double`
  `cs`
  The c_{\sigma} mutation rate evolution path learning rate.
  `org.ejml.simple.SimpleMatrix`
  `d`
  The "C" matrix, eigendecomposed from the "C" covariance matrix of the distribution.
  `double`
  `damps`
  The d_{\sigma} dampening for the mutation rate update.
  `static final int`
  `DEFAULT_ALT_GENERATOR_TRIES`
  Default value (100) for altGeneratorTries.
  `org.ejml.simple.SimpleMatrix`
  `invsqrtC`
  C^{-1/2}.
  `int`
  `lambda`
  The individuals generated from the distribution.
  `int`
  `lastEigenDecompositionGeneration`
  The most recent generation where an eigendecomposition on C was performed into B and D
  `static final int`
  `MAX_TRIES_BEFORE_WARNING`
  `int`
  `mu`
  The truncated individuals used to update the distribution.
  `double`
  `mueff`
  The "mu_{eff}" constant in CMA-ES.
  `static final String`
  `P_ALTERNATIVE_GENERATOR`
  `static final String`
  `P_ALTERNATIVE_GENERATOR_TRIES`
  `static final String`
  `P_ALTERNATIVE_TERMINATION`
  `static final String`
  `P_C1`
  `static final String`
  `P_CC`
  `static final String`
  `P_CMAES_SPECIES`
  `static final String`
  `P_CMU`
  `static final String`
  `P_COVARIANCE`
  `static final String`
  `P_CS`
  `static final String`
  `P_DAMPS`
  `static final String`
  `P_LAMBDA`
  `static final String`
  `P_MEAN`
  `static final String`
  `P_MU`
  `static final String`
  `P_SIGMA`
  `static final String`
  `P_WEIGHTS`
  `org.ejml.simple.SimpleMatrix`
  `pc`
  The p_c evolution path vector.
  `org.ejml.simple.SimpleMatrix`
  `ps`
  The p_{\sigma} evolution path vector.
  `org.ejml.data.DenseMatrix64F`
  `sbd`
  bd x sigma
  `double`
  `sigma`
  The "sigma" scaling factor for the covariance matrix.
  `boolean`
  `useAltGenerator`
  If, after trying altGeneratorTries to build an indiviual, we are still building one which violates min/max gene constraints, should we instead fill those violated genes with uniformly-selected values between the min and max?
  `boolean`
  `useAltTermination`
  Should we terminate when the eigenvalues get too small? If we don't, they might go negative and the eigendecomposition will fail.
  `static final String`
  `V_CENTER`
  `static final String`
  `V_IDENTITY`
  `static final String`
  `V_RANDOM`
  `static final String`
  `V_SCALED`
  `static final String`
  `V_ZERO`
  `double[]`
  `weights`
  The ranked fitness weights for the mu individuals.
  `org.ejml.simple.SimpleMatrix`
  `xmean`
  The mean of the distribution.

  ### Fields inherited from class ec.vector.FloatVectorSpecies

  `C_GAUSS_MUTATION, C_INTEGER_RANDOM_WALK_MUTATION, C_INTEGER_RESET_MUTATION, C_POLYNOMIAL_MUTATION, C_RESET_MUTATION, DEFAULT_OUT_OF_BOUNDS_RETRIES, gaussMutationStdev, maxGene, minGene, mutationDistributionIndex, mutationIsBounded, mutationType, outOfBoundsRetries, P_MAXGENE, P_MINGENE, P_MUTATION_BOUNDED, P_MUTATION_DISTRIBUTION_INDEX, P_MUTATIONTYPE, P_OUTOFBOUNDS_RETRIES, P_POLYNOMIAL_ALTERNATIVE, P_RANDOM_WALK_PROBABILITY, P_STDEV, polynomialIsAlternative, randomWalkProbability, V_GAUSS_MUTATION, V_INTEGER_RANDOM_WALK_MUTATION, V_INTEGER_RESET_MUTATION, V_POLYNOMIAL_MUTATION, V_RESET_MUTATION`

  ### Fields inherited from class ec.vector.VectorSpecies

  `C_ANY_POINT, C_GEOMETRIC, C_INTERMED_RECOMB, C_LINE_RECOMB, C_NONE, C_ONE_POINT, C_ONE_POINT_NO_NOP, C_SIMULATED_BINARY, C_TWO_POINT, C_TWO_POINT_NO_NOP, C_UNIFORM, chunksize, crossoverDistributionIndex, crossoverProbability, crossoverType, duplicateRetries, dynamicInitialSize, genomeIncreaseProbability, genomeResizeAlgorithm, genomeSize, lineDistance, maxInitialSize, minInitialSize, mutationProbability, P_CHUNKSIZE, P_CROSSOVER_DISTRIBUTION_INDEX, P_CROSSOVERPROB, P_CROSSOVERTYPE, P_DUPLICATE_RETRIES, P_GENOMESIZE, P_GEOMETRIC_PROBABILITY, P_LINEDISTANCE, P_MUTATIONPROB, P_NUM_SEGMENTS, P_SEGMENT, P_SEGMENT_END, P_SEGMENT_START, P_SEGMENT_TYPE, P_UNIFORM_MAX, P_UNIFORM_MIN, P_VECTORSPECIES, V_ANY_POINT, V_GEOMETRIC, V_INTERMED_RECOMB, V_LINE_RECOMB, V_ONE_POINT, V_ONE_POINT_NO_NOP, V_SIMULATED_BINARY, V_TWO_POINT, V_TWO_POINT_NO_NOP, V_UNIFORM`

  ### Fields inherited from class ec.Species

  `f_prototype, i_prototype, P_FITNESS, P_INDIVIDUAL, P_PIPE, pipe_prototype`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `CMAESSpecies()`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Object`
  `clone()`
  Creates a new individual cloned from a prototype, and suitable to begin use in its own evolutionary context.
  `Parameter`
  `defaultBase()`
  Returns the default base for this prototype.
  `Individual`
  `newIndividual(EvolutionState state, int thread)`
  Provides a brand-new individual to fill in a population.
  `void`
  `setup(EvolutionState state, Parameter base)`
  The default version of setup(...) loads requested pipelines and calls setup(...) on them and normalizes their probabilities.
  `void`
  `updateDistribution(EvolutionState state, Subpopulation subpop)`
  Revises the CMA-ES distribution to reflect the current fitness results in the provided subpopulation.

  ### Methods inherited from class ec.vector.FloatVectorSpecies

  `gaussMutationStdev, inNumericalTypeRange, loadParametersForGene, maxGene, minGene, mutationDistributionIndex, mutationIsBounded, mutationType, outOfRangeRetryLimitReached, polynomialIsAlternative, randomWalkProbability`

  ### Methods inherited from class ec.vector.VectorSpecies

  `contains, contains, contains, contains, duplicateRetries, fill, fill, fill, fill, initializeGenomeSegmentsByEndIndices, initializeGenomeSegmentsByStartIndices, mutationProbability, setupGenome`

  ### Methods inherited from class ec.Species

  `buildMisc, newIndividual, newIndividual, updateIndividual, updateSubpopulation`

  ### Methods inherited from class java.lang.Object

  `equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Field Details

  - ### P_CMAES_SPECIES

    public static final String P_CMAES_SPECIES
    See Also:
      - Constant Field Values

  - ### P_LAMBDA

    public static final String P_LAMBDA
    See Also:
      - Constant Field Values

  - ### P_MU

    public static final String P_MU
    See Also:
      - Constant Field Values

  - ### P_SIGMA

    public static final String P_SIGMA
    See Also:
      - Constant Field Values

  - ### P_MEAN

    public static final String P_MEAN
    See Also:
      - Constant Field Values

  - ### P_WEIGHTS

    public static final String P_WEIGHTS
    See Also:
      - Constant Field Values

  - ### P_CC

    public static final String P_CC
    See Also:
      - Constant Field Values

  - ### P_CS

    public static final String P_CS
    See Also:
      - Constant Field Values

  - ### P_C1

    public static final String P_C1
    See Also:
      - Constant Field Values

  - ### P_CMU

    public static final String P_CMU
    See Also:
      - Constant Field Values

  - ### P_DAMPS

    public static final String P_DAMPS
    See Also:
      - Constant Field Values

  - ### V_CENTER

    public static final String V_CENTER
    See Also:
      - Constant Field Values

  - ### V_ZERO

    public static final String V_ZERO
    See Also:
      - Constant Field Values

  - ### V_RANDOM

    public static final String V_RANDOM
    See Also:
      - Constant Field Values

  - ### P_COVARIANCE

    public static final String P_COVARIANCE
    See Also:
      - Constant Field Values

  - ### V_IDENTITY

    public static final String V_IDENTITY
    See Also:
      - Constant Field Values

  - ### V_SCALED

    public static final String V_SCALED
    See Also:
      - Constant Field Values

  - ### P_ALTERNATIVE_TERMINATION

    public static final String P_ALTERNATIVE_TERMINATION
    See Also:
      - Constant Field Values

  - ### P_ALTERNATIVE_GENERATOR

    public static final String P_ALTERNATIVE_GENERATOR
    See Also:
      - Constant Field Values

  - ### P_ALTERNATIVE_GENERATOR_TRIES

    public static final String P_ALTERNATIVE_GENERATOR_TRIES
    See Also:
      - Constant Field Values

  - ### lambda

    public int lambda
    The individuals generated from the distribution. If not specified in the parameters, by default lambda = 4+(int)Math.floor(3*Math.log(n));

  - ### mu

    public int mu
    The truncated individuals used to update the distribution. If not specified in the parameters, by default mu = (int)Math.floor(lambda/2.0);

  - ### weights

    public double[] weights
    The ranked fitness weights for the mu individuals. If not specified in the parameters, by default weights[i] = ln((lambda + 1) / 2i). Then all the weights are normalized so that they sum to 1.

  - ### mueff

    public double mueff
    The "mu_{eff}" constant in CMA-ES. This is set to 1.0 / the sum of the squares of each of the weights[...]

  - ### cmu

    public double cmu
    The c_{\mu} rank-mu update learning rate. If not specified in the parameters, by default cmu = Math.min(1-c1, 2 * (mueff - 2 + 1/mueff) / ((n+2)*(n+2) + mueff)) where n is the genome size.

  - ### c1

    public double c1
    The c_1 rank-1 update learning rate. If not specified in the parameters, by default c1 = 2 / ((n + 1.3) * (n + 1.3) + mueff) where n is the genome size.

  - ### cc

    public double cc
    The c_c rank-one evolution path cumulation parameter. If not specified in the parameters, by default cc = (4 + mueff / n) / (n + 4 + 2 * mueff/n) where n is the genome size.

  - ### cs

    public double cs
    The c_{\sigma} mutation rate evolution path learning rate. If not specified in the parameters, by default cs = (mueff + 2) / (n + mueff + 5) where n is the genome size.

  - ### damps

    public double damps
    The d_{\sigma} dampening for the mutation rate update. If not specified in the parameters, by default damps = cs + 2 * Math.max(1, Math.sqrt((mueff - 1) / (n + 1))) - 1 otherwise known as damps = 1 + 2 * Math.max(0, Math.sqrt((mueff - 1) / (n + 1)) - 1) + cs where n is the genome size.

  - ### sigma

    public double sigma
    The "sigma" scaling factor for the covariance matrix.

  - ### xmean

    public org.ejml.simple.SimpleMatrix xmean
    The mean of the distribution.

  - ### c

    public org.ejml.simple.SimpleMatrix c
    The "C" covariance matrix of the distribution.

  - ### b

    public org.ejml.simple.SimpleMatrix b
    The "B" matrix, eigendecomposed from the "C" covariance matrix of the distribution.

  - ### d

    public org.ejml.simple.SimpleMatrix d
    The "C" matrix, eigendecomposed from the "C" covariance matrix of the distribution.

  - ### bd

    public org.ejml.data.DenseMatrix64F bd
    b x d

  - ### sbd

    public org.ejml.data.DenseMatrix64F sbd
    bd x sigma

  - ### invsqrtC

    public org.ejml.simple.SimpleMatrix invsqrtC
    C^{-1/2}. This is equal to B x D^{-1} x B^T

  - ### ps

    public org.ejml.simple.SimpleMatrix ps
    The p_{\sigma} evolution path vector.

  - ### pc

    public org.ejml.simple.SimpleMatrix pc
    The p_c evolution path vector.

  - ### chiN

    public double chiN
    An estimate of the expected size of the standard multivariate gaussian N(0,I). This is chiN = Math.sqrt(n)*(1.0-1.0/(4.0*n)+1.0/(21.0*n*n))

  - ### lastEigenDecompositionGeneration

    public int lastEigenDecompositionGeneration
    The most recent generation where an eigendecomposition on C was performed into B and D

  - ### useAltTermination

    public boolean useAltTermination
    Should we terminate when the eigenvalues get too small? If we don't, they might go negative and the eigendecomposition will fail.

  - ### useAltGenerator

    public boolean useAltGenerator
    If, after trying altGeneratorTries to build an indiviual, we are still building one which violates min/max gene constraints, should we instead fill those violated genes with uniformly-selected values between the min and max?

  - ### altGeneratorTries

    public int altGeneratorTries
    How many times should we try to generate a valid individual before we give up and use the useAltGenerator approach?

  - ### DEFAULT_ALT_GENERATOR_TRIES

    public static final int DEFAULT_ALT_GENERATOR_TRIES
    Default value (100) for altGeneratorTries.
    See Also:
      - Constant Field Values

  - ### MAX_TRIES_BEFORE_WARNING

    public static final int MAX_TRIES_BEFORE_WARNING
    See Also:
      - Constant Field Values

- ## Constructor Details

  - ### CMAESSpecies

    public CMAESSpecies()

- ## Method Details

  - ### defaultBase

    public Parameter defaultBase()
    Description copied from interface: `Prototype`
    Returns the default base for this prototype. This should generally be implemented by building off of the static base() method on the DefaultsForm object for the prototype's package. This should be callable during setup(...).
    Specified by:
      `defaultBase` in interface `Prototype`
    Overrides:
      `defaultBase` in class `VectorSpecies`

  - ### setup

    public void setup(EvolutionState state, Parameter base)
    Description copied from class: `Species`
    The default version of setup(...) loads requested pipelines and calls setup(...) on them and normalizes their probabilities. If your individual prototype might need to know special things about the species (like parameters stored in it), then when you override this setup method, you'll need to set those parameters BEFORE you call super.setup(...), because the setup(...) code in Species sets up the prototype.
    Specified by:
      `setup` in interface `Prototype`
    Specified by:
      `setup` in interface `Setup`
    Overrides:
      `setup` in class `FloatVectorSpecies`
    See Also:
      - `Prototype.setup(EvolutionState,Parameter)`

  - ### clone

    public Object clone()
    Description copied from interface: `Prototype`
    Creates a new individual cloned from a prototype, and suitable to begin use in its own evolutionary context.

    Typically this should be a full "deep" clone. However, you may share certain elements with other objects rather than clone hem, depending on the situation:

    - If you hold objects which are shared with other instances, don't clone them.
    - If you hold objects which must be unique, clone them.
    - If you hold objects which were given to you as a gesture of kindness, and aren't owned by you, you probably shouldn't clone them.
    - DON'T attempt to clone: Singletons, Cliques, or Populations, or Subpopulation.
    - Arrays are not cloned automatically; you may need to clone an array if you're not sharing it with other instances. Arrays have the nice feature of being copyable by calling clone() on them.

    Implementations.

    - If no ancestor of yours implements clone(), and you have no need to do clone deeply, and you are abstract, then you should not declare clone().
    - If no ancestor of yours implements clone(), and you have no need to do clone deeply, and you are not abstract, then you should implement it as follows:

      ``

           public Object clone()
               {
               try
                   {
                   return super.clone();
                   }
               catch ((CloneNotSupportedException e)
                   { throw new InternalError(); } // never happens
               }

    - If no ancestor of yours implements clone(), but you need to deep-clone some things, then you should implement it as follows:

      ``

           public Object clone()
               {
               try
                   {
                   MyObject myobj = (MyObject) (super.clone());

                   // put your deep-cloning code here...
                   }
               catch ((CloneNotSupportedException e)
                   { throw new InternalError(); } // never happens
               return myobj;
               }

    - If an ancestor has implemented clone(), and you also need to deep clone some things, then you should implement it as follows:

      ``

           public Object clone()
               {
               MyObject myobj = (MyObject) (super.clone());

               // put your deep-cloning code here...

               return myobj;
               }

    Specified by:
      `clone` in interface `Prototype`
    Overrides:
      `clone` in class `Species`

  - ### newIndividual

    public Individual newIndividual(EvolutionState state, int thread)
    Description copied from class: `Species`
    Provides a brand-new individual to fill in a population. The default form simply calls clone(), creates a fitness, sets evaluated to false, and sets the species. If you need to make a more custom genotype (as is the case for GPSpecies, which requires a light rather than deep clone), you will need to override this method as you see fit.
    Overrides:
      `newIndividual` in class `VectorSpecies`

  - ### updateDistribution

    public void updateDistribution(EvolutionState state, Subpopulation subpop)
    Revises the CMA-ES distribution to reflect the current fitness results in the provided subpopulation.