Module purecma
[hide private]
[frames] | no frames]

Module purecma

source code

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

Version: 3.0.0

Classes [hide private]
  CMAESParameters
static "internal" parameter setting for CMAES
  CMAES
class for non-linear non-convex numerical minimization with CMA-ES.
  CMAESDataLogger
data logger for class CMAES, that can record and plot data.
  ff
versatile collection of test functions in static methods
  BestSolution
container to keep track of the best solution seen
  SquareMatrix
rudimental square matrix class
  DecomposingPositiveMatrix
Symmetric matrix maintaining its own eigendecomposition.
Functions [hide private]
 
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.
source code
 
eye(dimension)
return identity matrix as list of "vectors" (lists themselves)
source code
 
dot(A, b, transpose=False)
usual dot product of "matrix" A with "vector" b.
source code
 
plus(a, b)
add vectors, return a + b
source code
 
minus(a, b)
subtract vectors, return a - b
source code
 
argsort(a)
return index list to get a in order, ie a[argsort(a)[i]] == sorted(a)[i]
source code
 
safe_str(s, known_words=None)
return s as str safe to eval or raise an exception.
source code
 
eig(C)
eigendecomposition of a symmetric matrix.
source code
 
test()
test of the purecma module, called if __name__ == "__main__".
source code
Variables [hide private]
  RecombinationWeights = None
hash(x)
  __author__ = 'Nikolaus Hansen'
  __package__ = None
hash(x)
Function Details [hide private]

fmin(objective_fct, xstart, sigma, args=(), maxfevals='1e3 * N**2', ftarget=None, verb_disp=100, verb_log=1, verb_save=1000)

source code 

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

This call:

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

and these lines:

>> import cma.purecma as pcma
>> 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 Also: CMAES, OOOptimizer.

dot(A, b, transpose=False)

source code 

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.

safe_str(s, known_words=None)

source code 

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

eig(C)

source code 

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.

test()

source code 

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:

>>> try: import cma.purecma as pcma
... except ImportError: import purecma as pcma
>>> import random
>>> 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