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).

AuthorNikolaus Hansen, 2010-2011, 2017
Function fmin non-linear non-convex minimization procedure, a functional interface to CMA-ES.
Class CMAESParameters static "internal" parameter setting for CMAES
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 ff versatile collection of test functions in static methods
Class BestSolution container to keep track of the best solution seen
Class SquareMatrix rudimental square matrix class
Class DecomposingPositiveMatrix Symmetric matrix maintaining its own eigendecomposition.
Function eye return identity matrix as list of "vectors" (lists themselves)
Function dot usual dot product of "matrix" A with "vector" b.
Function plus add vectors, return a + b
Function minus subtract vectors, return a - b
Function argsort return index list to get a in order, ie a[argsort(a)[i]] == sorted(a)[i]
Function safe_str return s as str safe to eval or raise an exception.
Function eig eigendecomposition of a symmetric matrix.
Function test test of the purecma module, called if __name__ == "__main__".
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
sigma: float
initial step-size, standard deviation in any coordinate
args: tuple or sequence
arguments to objective_fct
ftarget: float
target function value
maxfevals: int or str
maximal number of function evaluations, a string is evaluated with N being the 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:

>> from cma import purecma, ff
>> res = purecma.fmin(ff.elli, 3 * [0.5], 0.3, verb_disp=100)
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])
[5.284564665206811e-08, 2.4608091035303e-09, -1.3582873173543187e-10]
>> print(res[1].result[1])
2.72976881789e-14
>> res[1].logger.plot()  # needs pylab/matplotlib to be installed

Details

After importing purecma:

>> import cma.purecma as pcma
>> import random

This call:

>> pcma.fmin(pcma.ff.elli, 10 * [0.5], 0.3, verb_save=0)

and these lines:

>> es.logger = pcma.CMAESDataLogger() >> pcma.CMAES(10 * [0.5], 0.3).optimize(pcma.ff.elli, ... callback=es.logger.add)

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 AlsoCMAES, OOOptimizer.
def eye(dimension):
return identity matrix as list of "vectors" (lists themselves)
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 plus(a, b):
add vectors, return a + b
def minus(a, b):
subtract vectors, return a - b
def argsort(a):
return index list to get a in order, ie a[argsort(a)[i]] == sorted(a)[i]
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:

>>> from cma.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 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 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(3)
>>> xmin, es = pcma.fmin(pcma.ff.rosenbrock, 4 * [0.5], 0.5,
...                      verb_disp=0, verb_log=1)
>>> print(es.counteval)
1680
>>> print(es.best.evals)
1664
>>> 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, %d" % (pcma.ff.rosenbrock(es.result[0]) < 1e13,
...                   es.result[2]))
True, 1584

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
API Documentation for cma, generated by pydoctor at 2018-03-03 13:51:41.