|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectfr.inria.optimization.cmaes.CMAEvolutionStrategy
public class CMAEvolutionStrategy
implements the 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 of the underlying search space. Unlike a quasi-Newton method the CMA-ES does neither estimate nor use gradients, making it considerably more reliable in terms of finding a good, or even close to optimal, solution, finally.
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 & 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× function evaluations. On difficult problems the complete optimization (a single run) is expected to take roughly between and function evaluations.
The main functionality is provided by the methods double[][]
and
samplePopulation()
or updateDistribution(double[])
.
Here is an example code snippet, see file
CMAExample1.java for a similar example, and
CMAExample2.java for a more extended example with multi-starts implemented.
updateDistribution(double[][], double[])
// new a CMA-ES and set some initial values CMAEvolutionStrategy cma = new CMAEvolutionStrategy(); cma.readProperties(); // read options, see file CMAEvolutionStrategy.properties cma.setDimension(10); // overwrite some loaded properties cma.setTypicalX(0.5); // in each dimension, setInitialX can be used as well cma.setInitialStandardDeviation(0.2); // also a mandatory setting cma.opts.stopFitness = 1e-9; // optional setting // initialize cma and get fitness array to fill in later double[] fitness = cma.init(); // new double[cma.parameters.getPopulationSize()]; // initial output to files cma.writeToDefaultFilesHeaders(0); // 0 == overwrites old files // iteration loop while(cma.stopConditions.getNumber() == 0) { // core iteration step double[][] pop = cma.samplePopulation(); // get a new population of solutions for(int i = 0; i < pop.length; ++i) { // for each candidate solution i fitness[i] = fitfun.valueOf(pop[i]); // compute fitness value, where fitfun } // is the function to be minimized cma.updateDistribution(fitness); // use fitness array to update search distribution // output to files cma.writeToDefaultFiles(); ...in case, print output to console, eg. cma.println(), or process best found solution, getBestSolution()... } // while // evaluate mean value as it is the best estimator for the optimum cma.setFitnessOfMeanX(fitfun.valueOf(cma.getMeanX())); // updates the best ever solution ...retrieve best solution, termination criterion via stopConditions etc... return cma.getBestX(); // best evaluated search pointThe output generated by the function
writeToDefaultFiles
can be
plotted in Matlab or Scilab using plotcmaesdat.m or
plotcmaesdat.sci respectively, see writeToDefaultFiles()
.
The implementation follows very closely [3]. It supports small and large
population sizes, the latter by using the rank-µ-update [2],
together with weighted recombination for the covariance matrix, an
improved parameter setting for large populations [3] and an (initially) diagonal covariance matrix [5].
The latter is particularly useful for large dimension, e.g. larger 100.
The default population size is small [1]. An
independent restart procedure with increasing population size [4]
is implemented in class
.cmaes.examples.CMAExample2
Practical hint: In order to solve an optimization problem in reasonable time it needs to be reasonably encoded. In particular the domain width of variables should be similar for all objective variables (decision variables), such that the initial standard deviation can be chosen the same for each variable. For example, an affine-linear transformation could be applied to each variable, such that its typical domain becomes the interval [0,10]. For positive variables a log-encoding or a square-encoding should be considered, to avoid the need to set a hard boundary at zero, see here for a few more details.
References
samplePopulation()
,
updateDistribution(double[])
,
Serialized FormNested Class Summary | |
---|---|
class |
CMAEvolutionStrategy.CMAException
very provisional error handling. |
class |
CMAEvolutionStrategy.StopCondition
Interface to whether and which termination criteria are satisfied |
Field Summary | |
---|---|
CMAOptions |
options
options that can be changed (fields can be assigned) at any time to control the running behavior |
CMAParameters |
parameters
strategy parameters that can be set initially |
double[][] |
population
recent population, no idea whether this is useful to be public |
CMAEvolutionStrategy.StopCondition |
stopConditions
permits access to whether and which termination conditions were satisfied |
java.lang.String |
versionNumber
|
Constructor Summary | |
---|---|
CMAEvolutionStrategy()
postpones most initialization. |
|
CMAEvolutionStrategy(int dimension)
|
|
CMAEvolutionStrategy(java.util.Properties properties)
retrieves options and strategy parameters from properties input, see file CMAEvolutionStrategy.properties for valid properties |
|
CMAEvolutionStrategy(java.lang.String propertiesFileName)
reads properties (options, strategy parameter settings) from file propertiesFileName |
Method Summary | |
---|---|
double |
getAxisRatio()
ratio between length of longest and shortest axis of the distribution ellipsoid, which is the square root of the largest divided by the smallest eigenvalue of the covariance matrix |
long |
getBestEvaluationNumber()
|
double |
getBestFunctionValue()
objective function value of best solution found so far. |
double |
getBestRecentFunctionValue()
objective function value of the, best solution in the recent iteration (population) |
ISolutionPoint |
getBestRecentSolution()
Get best evaluated solution of the last (recent) iteration. |
double[] |
getBestRecentX()
best search point of the recent iteration. |
CMASolution |
getBestSolution()
get best evaluated solution found so far. |
double[] |
getBestX()
get best evaluated search point found so far. |
long |
getCountEval()
number of objective function evaluations counted so far |
long |
getCountIter()
number of iterations conducted so far |
java.lang.String |
getDataC()
correlations and covariances of the search distribution. |
java.lang.String |
getDataRowAxlen()
6-th to last column are sorted axis lengths axlen |
java.lang.String |
getDataRowFitness()
|
java.lang.String |
getDataRowStddev()
|
java.lang.String |
getDataRowXMean()
|
java.lang.String |
getDataRowXRecentBest()
|
int |
getDimension()
|
double[] |
getInitialX()
the final setting of initial x can
be retrieved only after init() was called |
double[] |
getMeanX()
Get mean of the current search distribution. |
CMAParameters |
getParameterDefaults()
get default parameters in new CMAParameters instance, dimension must have been set before calling getDefaults |
CMAParameters |
getParameterDefaults(int N)
get default parameters in new CMAParameters instance |
java.lang.String |
getPrintAnnotation()
returns an annotation string for the printings of method println(). |
java.lang.String |
getPrintLine()
printing output in a viewable formatting style. |
java.util.Properties |
getProperties()
get properties previously read from a property file. |
java.util.Random |
getRand()
get used random number generator instance |
long |
getSeed()
|
double |
getWorstRecentFunctionValue()
objective function value of the, worst solution of the recent iteration. |
java.lang.String |
helloWorld()
returns an informative initial message of the CMA-ES optimizer |
double[] |
init()
|
double[] |
init(int dimension)
|
double[] |
init(int dimension,
double[] initialX,
double[] initialStandardDeviations)
initialization providing all mandatory input arguments at once. |
double |
mahalanobisNorm(double[] x,
double[] mean)
compute Mahalanobis norm of x - mean w.r.t. |
void |
println()
calls println(getPrintLine()) |
void |
println(java.lang.String s)
calls System.out.println(s) and writes s to the file outcmaesdisp.dat by default, if writeDisplayToFile option is > 0 |
void |
printlnAnnotation()
|
void |
printlnHelloWorld()
calls println(helloWorld()) |
java.util.Properties |
readProperties()
reads properties from default input file CMAEvolutionStrategy.properties and sets options and strategy parameter settings accordingly. |
java.util.Properties |
readProperties(java.lang.String fileName)
reads properties from fileName and sets strategy parameters and options accordingly |
double[] |
resampleSingle(int index)
re-generate the index -th solution. |
double[][] |
samplePopulation()
Samples the recent search distribution lambda times |
long |
setCountEval(long c)
number of objective function evaluations counted so far |
void |
setDimension(int n)
search space dimensions must be set before the optimization is started. |
CMASolution |
setFitnessOfMeanX(double fitness)
eventually replaces the best-ever solution |
void |
setFromProperties(java.util.Properties properties)
reads properties from Properties class input and sets options and parameters accordingly |
void |
setInitialStandardDeviation(double startsigma)
|
void |
setInitialStandardDeviations(double[] startsigma)
|
void |
setInitialX(double x)
sets initialX to the same value in each coordinate |
void |
setInitialX(double[] x)
set initial search point to input value x . |
void |
setInitialX(double[] l,
double[] u)
set initial seach point x coordinate-wise uniform
between l and u ,
dimension needs to have been set before |
void |
setInitialX(double l,
double u)
set initial seach point xmean coordinate-wise uniform
between l and u ,
dimension needs to have been set before |
void |
setRand(java.util.Random rand)
|
void |
setSeed(long seed)
Setter for the seed for the random number generator java.util.Random(seed). |
void |
setTypicalX(double x)
sets typicalX value, the same value in each coordinate |
void |
setTypicalX(double[] x)
sets typicalX value, which will be overwritten by initialX setting from properties or setInitialX(double[]) function call. |
void |
updateDistribution(double[] functionValues)
update of the search distribution after samplePopulation(). |
void |
updateDistribution(double[][] population,
double[] functionValues)
update of the search distribution from a population and its function values, see updateDistribution(double[][], double[], 0) . |
void |
updateDistribution(double[][] population,
double[] functionValues,
int nInjected)
update of the search distribution from a population and its function values, an alternative interface for updateDistribution(double[] functionValues) . |
void |
writeToDefaultFiles()
writes data output to default files. |
void |
writeToDefaultFiles(int flgForce)
writes data output to default files. |
void |
writeToDefaultFiles(java.lang.String fileNamePrefix)
writes data to files fileNamePrefixfit.dat, ...xmean.dat ...xbest.dat, ...std.dat, ...axlen.dat. |
void |
writeToDefaultFilesHeaders(int flgAppend)
writes header lines to the default files. |
void |
writeToDefaultFilesHeaders(java.lang.String fileNamePrefix,
int flgAppend)
Writes headers (column annotations) to files |
void |
writeToFile(java.lang.String filename,
java.lang.String data,
int flgAppend)
writes a string to a file, overwrites first, appends afterwards. |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public final java.lang.String versionNumber
public CMAOptions options
public CMAParameters parameters
public CMAEvolutionStrategy.StopCondition stopConditions
public double[][] population
Constructor Detail |
---|
public CMAEvolutionStrategy()
public CMAEvolutionStrategy(java.util.Properties properties)
public CMAEvolutionStrategy(java.lang.String propertiesFileName)
propertiesFileName
public CMAEvolutionStrategy(int dimension)
dimension
- search space dimension, dimension of the
objective functions preimage, number of variablesMethod Detail |
---|
public double[] init(int dimension, double[] initialX, double[] initialStandardDeviations)
cma.init(N, X, SD);and
cma.setInitalX(X); // cma.setInitialStandardDeviations(SD); cma.init(N);The call to
init
is a point of no return for parameter
settings, and demands all mandatory input be set. init
then forces the
setting up of everything and calls
parameters.supplementRemainders()
. If init
was not called before, it is called once in
samplePopulation()
. The return value is only provided for sake of convenience.
dimension
- initialX
- double[] can be of size one, where all variables are set to the
same value, or of size dimensioninitialStandardDeviations
- can be of size one, where all standard
deviations are set to the same value, or of size dimension
double[] fitness
of length population size lambda to assign and pass
objective function values to updateDistribution(double[])
init()
,
init(int)
,
setInitialX(double[])
,
setTypicalX(double[])
,
setInitialStandardDeviations(double[])
,
samplePopulation()
,
CMAParameters.supplementRemainders(int, CMAOptions)
public double[] init(int dimension)
dimension
- search space dimensioninit(int, double[], double[])
public double[] init()
init(int, double[], double[])
public CMAParameters getParameterDefaults()
CMAParameters.getDefaults(int)
public CMAParameters getParameterDefaults(int N)
CMAParameters.getDefaults(int)
public java.util.Properties readProperties()
public java.util.Properties readProperties(java.lang.String fileName)
fileName
- of properties filepublic void setFromProperties(java.util.Properties properties)
properties
- java.util.Properties key-value hash tablereadProperties()
public double[][] samplePopulation()
lambda == parameters.getPopulationSize()
resampleSingle(int)
,
updateDistribution(double[])
,
CMAParameters.getPopulationSize()
public double[] resampleSingle(int index)
index
-th solution. After getting lambda
solution points with samplePopulation() the i-th point,
i=0...lambda-1, can be sampled anew by resampleSingle(i).
double[][] pop = cma.samplePopulation(); // check some stuff, i-th solution went wrong, therefore pop[i] = cma.resampleSingle(i); // assignment to keep the population consistent for (i = 0,...) fitness[i] = fitfun.valueof(pop[i]);
samplePopulation()
public double mahalanobisNorm(double[] x, double[] mean)
x
- mean
-
public void updateDistribution(double[][] population, double[] functionValues)
updateDistribution(double[][], double[], 0)
.
This might become updateDistribution(double[][], double[], popsize)
in future.
population
- double[lambda][N], lambda solutionsfunctionValues
- double[lambda], respective objective values of populationsamplePopulation()
,
updateDistribution(double[])
,
updateDistribution(double[][], double[], int)
public void updateDistribution(double[][] population, double[] functionValues, int nInjected)
updateDistribution(double[] functionValues)
. functionValues is used to establish an
ordering of the elements in population. The first nInjected elements do not need to originate
from #samplePopulation() or can have been modified (TODO: to be tested).
population
- double[lambda][N], lambda solutionsfunctionValues
- double[lambda], respective objective values of populationnInjected
- int, first nInjected solutions of population were not sampled by
samplePopulation() or modified afterwardssamplePopulation()
,
updateDistribution(double[])
public void updateDistribution(double[] functionValues)
samplePopulation()
,
updateDistribution(double[][], double[])
public double getAxisRatio()
public CMASolution getBestSolution()
Example: getBestSolution
getBestRecentSolution()
,
getBestX()
,
getMeanX()
public CMASolution setFitnessOfMeanX(double fitness)
fitness
- function value computed for the solution getMeanX()
public double[] getBestX()
getMeanX()
public double getBestFunctionValue()
getBestSolution()
public long getBestEvaluationNumber()
public ISolutionPoint getBestRecentSolution()
getBestSolution()
,
getBestRecentX()
,
getMeanX()
public double[] getBestRecentX()
getBestRecentFunctionValue()
public double getBestRecentFunctionValue()
getBestEvaluationNumber()
,
getBestFunctionValue()
public double getWorstRecentFunctionValue()
public double[] getMeanX()
getBestX()
,
getBestRecentX()
public int getDimension()
public long getCountEval()
public long getCountIter()
public double[] getInitialX()
x
can
be retrieved only after init()
was called
double[] initialX
start point chosen for
distribution mean value xmean
public java.util.Random getRand()
public java.util.Properties getProperties()
readProperties()
public long getSeed()
setSeed(long)
public long setCountEval(long c)
public void setDimension(int n)
public void setTypicalX(double x)
setTypicalX(double[])
public void setTypicalX(double[] x)
setInitialX(double[])
function call.
Otherwise the initialX is sampled normally distributed from typicalX with initialStandardDeviations
setTypicalX(double)
,
setInitialX(double[])
,
setInitialStandardDeviations(double[])
public void setInitialStandardDeviation(double startsigma)
public void setInitialStandardDeviations(double[] startsigma)
public void setInitialX(double x)
initialX
to the same value in each coordinate
x
- valuesetInitialX(double[])
public void setInitialX(double l, double u)
xmean
coordinate-wise uniform
between l
and u
,
dimension needs to have been set before
l
- double lower valueu
- double upper valuesetInitialX(double[])
,
setInitialX(double[], double[])
public void setInitialX(double[] l, double[] u)
x
coordinate-wise uniform
between l
and u
,
dimension needs to have been set before
l
- double lower valueu
- double upper valuepublic void setInitialX(double[] x)
x
. x.length==1
is possible, otherwise
the search space dimension is set to x.length
irrevocably
x
- double[] initial pointsetInitialX(double)
,
setInitialX(double, double)
public void setRand(java.util.Random rand)
public void setSeed(long seed)
init()
was called.
seed
- a long value to initialize java.util.Random(seed)public java.lang.String getPrintLine()
Iteration,#Fevals: rb Function Value Delta( best ,worst) |idx: Max SD idx: Min SD | minsigD sigma Axisratio | time, in eig 164( 8), 1638: 5.5061568003892640e-08 (-4e-08,3e-08) | 0: 3.3e-05 8: 1.5e-05 | 1.4e-05 5.6e-05 2.34 | 0.1 0.0shows the value of getPrintAnnotation() in the first line and in the second line
getPrintAnnotation()
public java.lang.String getPrintAnnotation()
public java.lang.String helloWorld()
public void println(java.lang.String s)
getPrintLine()
public void println()
getPrintLine()
public void printlnAnnotation()
getPrintAnnotation()
public void printlnHelloWorld()
helloWorld()
,
println(String)
public java.lang.String getDataRowFitness()
public java.lang.String getDataRowXRecentBest()
public java.lang.String getDataRowXMean()
public java.lang.String getDataRowAxlen()
public java.lang.String getDataRowStddev()
public java.lang.String getDataC()
public void writeToFile(java.lang.String filename, java.lang.String data, int flgAppend)
Example: cma.writeToFile("cmaescorr.dat", cma.writeC());
filename
- is a String giving the name of the file to be writtendata
- is a String of text/data to be writtenflgAppend
- for flgAppend>0 old data are not overwrittenpublic void writeToDefaultFiles()
The output is written to files that can be printed in Matlab or Scilab (a free and easy to install Matlab "clone").
Matlab:
cd 'directory_where_outfiles_and_plotcmaesdat.m_file_are' plotcmaesdat;Scilab:
cd 'directory_where_outfiles_and_plotcmaesdat.sci_file_are' getf('plotcmaesdat.sci'); plotcmaesdat;
writeToDefaultFiles(String fileNamePrefix)
,
writeToDefaultFiles(int)
public void writeToDefaultFiles(int flgForce)
flgForce
input parameter below.
flgForce
- 0==write depending on time spent with writing,
1==write if the iteration count has changed,
2==write always, overruled by negative values of maxTimeFractionForWriteToDefaultFiles propertywriteToDefaultFiles()
public void writeToDefaultFiles(java.lang.String fileNamePrefix)
fileNamePrefix
- prefix String for filenames created to write datawriteToDefaultFiles()
public void writeToDefaultFilesHeaders(int flgAppend)
flgAppend
- == 0 means overwrite files, == 1 means append to filespublic void writeToDefaultFilesHeaders(java.lang.String fileNamePrefix, int flgAppend)
fileNamePrefix
- String for filenames created to write data
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |