CMA-ES

Contents

CMA-ES#

Disclaimer: We make use of the implementation available at PyPi [20] published by the author Nikolaus Hansen under the BSD license.

CMA-ES was proposed in [21]. Moreover, a comparing review can be found in [22]. CMA-ES stands for covariance matrix adaptation evolution strategy. Evolution strategies (ES) are stochastic, derivative-free methods for numerical optimization of non-linear or non-convex continuous optimization problems. They belong to the class of evolutionary algorithms and evolutionary computation. An evolutionary algorithm is broadly based on the principle of biological evolution, namely the repeated interplay of variation (via recombination and mutation) and selection: in each generation (iteration) new individuals (candidate solutions) are generated by variation, usually in a stochastic way, of the current parental individuals. Then, some individuals are selected to become the parents in the next generation based on their fitness or objective function value \(f(x)\). Like this, over the generation sequence, individuals with better and better \(f\)-values are generated. (excerpt from Wikipedia).

Example#

[1]:

import numpy as np

from pymoo.algorithms.soo.nonconvex.cmaes import CMAES
from pymoo.problems import get_problem
from pymoo.optimize import minimize

problem = get_problem("sphere")

algorithm = CMAES(x0=np.random.random(problem.n_var))

res = minimize(problem,
               algorithm,
               seed=1,
               verbose=False)

print(f"Best solution found: \nX = {res.X}\nF = {res.F}\nCV= {res.CV}")

Best solution found:
X = [0.50000005 0.50000002 0.50000006 0.49999997 0.50000004 0.49999998
 0.5        0.49999995 0.49999996 0.49999998]
F = [1.25420079e-14]
CV= [0.]

CMA-ES already has several stopping criteria implemented. However, as for other algorithms, the number of iterations or function evaluations can be directly passed to minimize.

[2]:

res = minimize(problem,
               algorithm,
               ('n_iter', 10),
               seed=1,
               verbose=True)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))

==================================================================================================================
n_gen  |  n_eval  |     f_avg     |     f_min     |     f_gap     |     sigma     | min_std  | max_std  |   axis
==================================================================================================================
     1 |        1 |  0.6986960474 |  0.6986960474 |  0.6986960474 |  0.1000000000 |  0.10000 |  0.10000 |  1.00005
     2 |       11 |  0.6733528575 |  0.4977089344 |  0.4977089344 |  0.0974846541 |  0.09477 |  0.10034 |  1.25174
     3 |       21 |  0.4843171753 |  0.3239301703 |  0.3239301703 |  0.1063119849 |  0.10238 |  0.11043 |  1.42202
     4 |       31 |  0.4758940562 |  0.2514928738 |  0.2514928738 |  0.1170922884 |  0.11099 |  0.12598 |  1.53633
     5 |       41 |  0.4262738507 |  0.1419624633 |  0.1419624633 |  0.1266156469 |  0.11661 |  0.13582 |  1.67456
     6 |       51 |  0.3553537461 |  0.1245409686 |  0.1245409686 |  0.1317225627 |  0.11865 |  0.14798 |  1.71835
     7 |       61 |  0.3163032862 |  0.1245409686 |  0.1245409686 |  0.1420714997 |  0.12841 |  0.16754 |  1.79624
     8 |       71 |  0.2937093051 |  0.1245409686 |  0.1245409686 |  0.1475818526 |  0.12967 |  0.18041 |  1.90914
     9 |       81 |  0.3080307608 |  0.0703019852 |  0.0703019852 |  0.1421243389 |  0.11955 |  0.17379 |  1.94820
    10 |       91 |  0.2003261799 |  0.0533900214 |  0.0533900214 |  0.1351436853 |  0.11130 |  0.16197 |  1.94535
Best solution found:
X = [0.46566145 0.52708665 0.48501552 0.51507902 0.52451953 0.66842551
 0.59295939 0.40799194 0.54020854 0.44226551]
F = [0.05339002]

[3]:

res = minimize(problem,
               algorithm,
               ('n_eval', 50),
               seed=1,
               verbose=True)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))

==================================================================================================================
n_gen  |  n_eval  |     f_avg     |     f_min     |     f_gap     |     sigma     | min_std  | max_std  |   axis
==================================================================================================================
     1 |        1 |  0.6986960474 |  0.6986960474 |  0.6986960474 |  0.1000000000 |  0.10000 |  0.10000 |  1.00005
     2 |       11 |  0.6733528575 |  0.4977089344 |  0.4977089344 |  0.0974846541 |  0.09477 |  0.10034 |  1.25174
     3 |       21 |  0.4843171753 |  0.3239301703 |  0.3239301703 |  0.1063119849 |  0.10238 |  0.11043 |  1.42202
     4 |       31 |  0.4758940562 |  0.2514928738 |  0.2514928738 |  0.1170922884 |  0.11099 |  0.12598 |  1.53633
     5 |       41 |  0.4262738507 |  0.1419624633 |  0.1419624633 |  0.1266156469 |  0.11661 |  0.13582 |  1.67456
     6 |       51 |  0.3553537461 |  0.1245409686 |  0.1245409686 |  0.1317225627 |  0.11865 |  0.14798 |  1.71835
Best solution found:
X = [0.50609315 0.50873343 0.39444275 0.40066132 0.55412427 0.56631945
 0.64766792 0.59292662 0.35257516 0.70955692]
F = [0.12454097]

Also, easily restarts can be used, which are known to work very well on multi-modal functions. For instance, Rastrigin can be solved rather quickly by:

[4]:

problem = get_problem("rastrigin")

algorithm = CMAES(restarts=10, restart_from_best=True)

res = minimize(problem,
               algorithm,
               ('n_evals', 2500),
               seed=1,
               verbose=False)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))

Best solution found:
X = [-1.23061656e-05 -3.45545234e-06]
F = [3.241367e-08]

Our framework internally calls the cma.fmin2 function. All parameters that can be used there either as a keyword argument or an option can also be passed to the CMAES constructor. An example with a few selected cma.fmin2 parameters is shown below:

[5]:

import numpy as np
from pymoo.util.normalization import denormalize

# define an intitial point for the search
np.random.seed(1)
x0 = denormalize(np.random.random(problem.n_var), problem.xl, problem.xu)

algorithm = CMAES(x0=x0,
                  sigma=0.5,
                  restarts=2,
                  maxfevals=np.inf,
                  tolfun=1e-6,
                  tolx=1e-6,
                  restart_from_best=True,
                  bipop=True)

res = minimize(problem,
               algorithm,
               seed=1,
               verbose=False)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))

Best solution found:
X = [-0.0171417  -0.00799399]
F = [0.07091441]

For more details about hyperparameters, we refer to the software documentation of the fmin2 in CMA-ES, which can be found here. A quick explanation of possible parameters is also provided in the API documentation below.

API#

class pymoo.algorithms.soo.nonconvex.cmaes.CMAES(self, x0=None, sigma=0.1, normalize=True, parallelize=True, maxfevals=np.inf, tolfun=1e-11, tolx=1e-11, restarts=0, restart_from_best='False', incpopsize=2, eval_initial_x=False, noise_handler=None, noise_change_sigma_exponent=1, noise_kappa_exponent=0, bipop=False, cmaes_verbose=-9, verb_log=0, output=CMAESOutput(), pop_size=None, **kwargs)[source]

Covariance Matrix Adaptation Evolution Strategy.

Parameters:

  • x0 – Initial guess of minimum solution (array or string expression).

  • sigma – Initial standard deviation in each coordinate.

  • normalize – Whether to normalize problem bounds.

  • parallelize – Whether to call objective function batch-wise.

  • maxfevals – Maximum number of function evaluations.

  • tolfun – Termination tolerance in function value.

  • tolx – Termination tolerance in x-changes.

  • restarts – Number of restarts with increasing population size (IPOP-CMA-ES).

  • restart_from_best – Whether to restart from best solution.

  • incpopsize – Multiplier for population size increase.

  • eval_initial_x – Whether to evaluate initial solution.

  • noise_handler – Noise handling instance or class.

  • noise_change_sigma_exponent – Exponent for sigma increment.

  • noise_kappa_exponent – Kappa exponent for noise treatment.

  • bipop – Whether to use BIPOP-CMA-ES restart strategy.

  • cmaes_verbose – Verbosity level for CMA-ES output.

  • verb_log – Verbosity for logging to files.

  • output – Output display configuration.

  • pop_size – Population size (overrides CMA-ES default).

  • **kwargs – Additional CMA-ES options passed to CMAEvolutionStrategy.

Contents