module documentation

A minimalistic implemention of CMA-ES without using numpy.

The Covariance Matrix Adaptation Evolution Strategy, CMA-ES, serves for numerical nonlinear function minimization.

The main functionality is implemented in

  1. class CMAES, and
  2. function fmin which is a small single-line-usage wrapper around CMAES.

This code has two purposes:

  1. for READING and UNDERSTANDING the basic flow and the details of the CMA-ES algorithm. The source code is meant to be read. For a quick glance, study the first few code lines of fmin and the code of method CMAES.tell, where all the real work is done in about 20 lines of code (search "def tell" in the source). Otherwise, reading from the top is a feasible option, where the codes of fmin, CMAES.__init__, CMAES.ask, CMAES.tell are of particular interest.
  2. apply CMA-ES when the python module numpy is not available. When numpy is available, cma.fmin or cma.CMAEvolutionStrategy are preferred to run "serious" simulations. The latter code has many more lines, but usually executes faster, offers a richer user interface, better termination options, boundary and noise handling, injection, automated restarts...

Dependencies: math.exp, math.log and random.normalvariate (modules matplotlib.pylab and sys are optional).

Testing: call python purecma.py at the OS shell. Tested with Python 2.6, 2.7, 3.3, 3.5, 3.6.

URL: http://github.com/CMA-ES/pycma

Last change: September, 2017, version 3.0.0

This code is released into the public domain (that is, you may use and modify it however you like).

Author
Nikolaus Hansen, 2010-2011, 2017
Class ​Best​Solution container to keep track of the best solution seen
Class CMAES class for non-linear non-convex numerical minimization with CMA-ES.
Class ​CMAESData​Logger data logger for class CMAES, that can record and plot data.
Class ​CMAESParameters static "internal" parameter setting for CMAES
Class ​Decomposing​Positive​Matrix Symmetric matrix maintaining its own eigendecomposition.
Class ff versatile collection of test functions in static methods
Class ​Square​Matrix rudimental square matrix class
Function argsort return index list to get a in order, ie a[argsort(a)[i]] == sorted(a)[i]
Function dot usual dot product of "matrix" A with "vector" b.
Function eig eigendecomposition of a symmetric matrix.
Function eye return identity matrix as list of "vectors" (lists themselves)
Function fmin non-linear non-convex minimization procedure, a functional interface to CMA-ES.
Function minus subtract vectors, return a - b
Function plus add vectors, return a + b
Function safe​_str return s as str safe to eval or raise an exception.
Function test test of the purecma module, called if __name__ == "__main__".
Variable __​_author__ Undocumented
Variable __author__ Undocumented
Variable __license__ Undocumented
Variable __version__ Undocumented
Variable ​OOOptimizer Undocumented
Variable ​Recombination​Weights Undocumented
Variable _​Base​Data​Logger Undocumented
def argsort(a):
return index list to get a in order, ie a[argsort(a)[i]] == sorted(a)[i]
def dot(A, b, transpose=False):

usual dot product of "matrix" A with "vector" b.

A[i] is the i-th row of A. With transpose=True, A transposed is used.

def eig(C):

eigendecomposition of a symmetric matrix.

Return the eigenvalues and an orthonormal basis of the corresponding eigenvectors, (EVals, Basis), where

  • Basis[i]: list, is the i-th row of Basis
  • the i-th column of Basis, ie [Basis[j][i] for j in range(len(Basis))] is the i-th eigenvector with eigenvalue EVals[i]

Details: much slower than numpy.linalg.eigh.

def eye(dimension):
return identity matrix as list of "vectors" (lists themselves)
def fmin(objective_fct, xstart, sigma, args=(), maxfevals='1e3 * N**2', ftarget=None, verb_disp=100, verb_log=1, verb_save=1000):

non-linear non-convex minimization procedure, a functional interface to CMA-ES.

Parameters

objective_fct: callable
a function that takes as input a list of floats (like [3.0, 2.2, 1.1]) and returns a single float (a scalar). The objective is to find x with objective_fct(x) to be as small as possible.
xstart: list or sequence
list of numbers (like [3.2, 2, 1]), initial solution vector, its length defines the search space dimension.
sigma: float
initial step-size, standard deviation in any coordinate
args: tuple or sequence
additional (optional) arguments passed to objective_fct
ftarget: float
target function value
maxfevals: int or str
maximal number of function evaluations, a string is evaluated with N as search space dimension
verb_disp: int
display on console every verb_disp iteration, 0 for never
verb_log: int
data logging every verb_log iteration, 0 for never
verb_save: int
save logged data every verb_save * verb_log iteration

Return

The tuple (xmin:list, es:CMAES), where xmin is the best seen (evaluated) solution and es is the correspoding CMAES instance. Consult help(es.result) of property result for further results.

Example

The following example minimizes the function ff.elli:

>>> try: import cma.purecma as purecma
... except ImportError: import purecma
>>> def felli(x):
...     return sum(10**(6 * i / (len(x)-1)) * xi**2
...                for i, xi in enumerate(x))
>>> res = purecma.fmin(felli, 3 * [0.5], 0.3, verb_disp=100)  # doctest:+SKIP
evals: ax-ratio max(std)   f-value
    7:     1.0  3.4e-01  240.2716966
   14:     1.0  3.9e-01  2341.50170536
  700:   247.9  2.4e-01  0.629102574062
 1400:  1185.9  5.3e-07  4.83466373808e-13
 1421:  1131.2  2.9e-07  5.50167024417e-14
termination by {'tolfun': 1e-12}
best f-value = 2.72976881789e-14
solution = [5.284564665206811e-08, 2.4608091035303e-09, -1.3582873173543187e-10]
>>> print(res[0])  # doctest:+SKIP
[5.284564665206811e-08, 2.4608091035303e-09, -1.3582873173543187e-10]
>>> res[1].result[1])  # doctest:+SKIP
2.72976881789e-14
>>> res[1].logger.plot()  # doctest:+SKIP

Details

After importing purecma, this call:

>>> es = purecma.fmin(pcma.ff.elli, 10 * [0.5], 0.3, verb_save=0)[1]  # doctest:+SKIP

and these lines:

>>> es = purecma.CMAES(10 * [0.5], 0.3)
>>> es.optimize(purecma.ff.elli, callback=es.logger.add)  # doctest:+SKIP

do pretty much the same. The verb_save parameter to fmin adds the possibility to plot the saved data during the execution from a different Python shell like pcma.CMAESDataLogger().load().plot(). For example, with verb_save == 3 every third time the logger records data they are saved to disk as well.

See Also
CMAES, OOOptimizer.
def minus(a, b):
subtract vectors, return a - b
def plus(a, b):
add vectors, return a + b
def safe_str(s, known_words=None):

return s as str safe to eval or raise an exception.

Strings in the dict known_words are replaced by their values surrounded with a space, which the caller considers safe to evaluate with eval afterwards.

Known issues:

>>> try: from cma.purecma import safe_str
... except ImportError: from purecma import safe_str
>>> safe_str('int(p)', {'int': 'int', 'p': 3.1})  # fine
' int ( 3.1 )'
>>> safe_str('int(n)', {'int': 'int', 'n': 3.1})  # unexpected
' i 3.1 t ( 3.1 )'
def test():

test of the purecma module, called if __name__ == "__main__".

Currently only based on doctest:

>>> try: import cma.purecma as pcma
... except ImportError: import purecma as pcma
>>> import random
>>> random.seed(8)
>>> xmin, es = pcma.fmin(pcma.ff.rosenbrock, 4 * [0.5], 0.5,
...                      verb_disp=0, verb_log=1)
>>> print(es.counteval)
1712
>>> print(es.best.evals)
1704
>>> assert es.best.f < 1e-12
>>> random.seed(5)
>>> es = pcma.CMAES(4 * [0.5], 0.5)
>>> es.params = pcma.CMAESParameters(es.params.dimension,
...                                  es.params.lam,
...                                  pcma.RecombinationWeights)
>>> while not es.stop():
...     X = es.ask()
...     es.tell(X, [pcma.ff.rosenbrock(x) for x in X])
>>> print("%s, %s" % (pcma.ff.rosenbrock(es.result[0]) < 1e-13,
...                   es.result[2] < 1600))
True, True

Large population size:

>>> random.seed(4)
>>> es = pcma.CMAES(3 * [1], 1)
>>> es.params = pcma.CMAESParameters(es.params.dimension, 300,
...                                  pcma.RecombinationWeights)
>>> es.logger = pcma.CMAESDataLogger()
>>> try:
...    es = es.optimize(pcma.ff.elli, verb_disp=0)
... except AttributeError:  # OOOptimizer.optimize is not available
...     while not es.stop():
...         X = es.ask()
...         es.tell(X, [pcma.ff.elli(x) for x in X])
>>> assert es.result[1] < 1e13
>>> print(es.result[2])
9300
___author__: str =

Undocumented

__author__: str =

Undocumented

__license__: str =

Undocumented

__version__: str =

Undocumented

OOOptimizer =

Undocumented

RecombinationWeights =

Undocumented

_BaseDataLogger =

Undocumented