cma.purecma

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

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

This code has two purposes:

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.
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	`BestSolution`	container to keep track of the best solution seen
Class	`CMAES`	class for non-linear non-convex numerical minimization with CMA-ES.
Class	`CMAESDataLogger`	data logger for class `CMAES`, that can record and plot data.
Class	`CMAESParameters`	static "internal" parameter setting for `CMAES`
Class	`DecomposingPositiveMatrix`	Symmetric matrix maintaining its own eigendecomposition.
Class	`ff`	versatile collection of test functions in static methods
Class	`SquareMatrix`	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

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