cma.constraints_handler.AugmentedLagrangian

Augmented Lagrangian with adaptation of the coefficients

for minimization, implemented after Atamna et al FOGA 2017, Algorithm 1 and Sect 8.2, https://hal.inria.fr/hal-01455379/document.

cma.ConstrainedFitnessAL provides a (more) user-friendly interface to the AugmentedLagrangian class.

Input dimension is the search space dimension, boolean equality may be an iterable of length of number of constraints indicating the type for each constraint.

Below, the objective function value is denoted as f = f(x), the constraints values as g = g(x) <= 0, the penalties compute to penalties(x) = self(g(x)) = lam g + mu g^2 / 2 (if g > -lam / mu) for each element of g, as returned by calling the instance with g as argument.

The penalized "fitness" value f + sum(self(g)) shall be minimized. lam and mu are the Lagrange multipliers or coefficients.

An additional method, set_coefficients allows to initialize the Lagrange multipliers from data.

A short example (and doctest):

>>> import cma
>>> from cma.constraints_handler import AugmentedLagrangian, PopulationEvaluator
>>> m = 2  # number of constraints
>>> def objective(x):
...     return sum(x[m:]**2) + sum((x[:m] - 1)**2) - m
>>> def constraints(x):
...     return x[:m]
>>> es = cma.CMAEvolutionStrategy(3 * [1], 1, {
...          'termination_callback': lambda es: sum(es.mean**2) < 1e-8})  #doctest: +ELLIPSIS
(3_w,7)-aCMA-ES...
>>> al = AugmentedLagrangian(es.N)  # lam and mu still need to be set
>>> # al.chi_domega = 1.15  # is the new default, which seems to give better results than the original value
>>> # al.lam, al.mu = ...  # we could set the initial Lagrange coefficients here
>>> while not es.stop():
...     eva = PopulationEvaluator(objective, constraints)(es.ask(), m=es.mean)
...     al.set_coefficients(eva.F, eva.G)  # set lam and mu, not part of the original algorithm
...     al.update(eva.m['f'], eva.m['g'])
...     es.tell(eva.X, [f + sum(al(g)) for f, g in zip(eva.F, eva.G)])
>>> if es.result.evaluations > 3100:
...     print("evaluations %d !< 3100. 1500 is normal, 2700 happens rarely" % es.result.evaluations)
>>> assert 'callback' in es.stop()
>>> assert len(eva.feasibility_ratios) == m
>>> assert sum(eva.feasibility_ratios < 0) == sum(eva.feasibility_ratios > 1) == 0

Details: the input dimension is needed to compute the default change rate chi_domega (if chi_domega is None), to compute initial coefficients and to compare between h and g to update mu. The default dependency of chi_domega on the dimension seems to be however suboptimal. Setting self.chi_domega = 1.15 as is the current default seems to give better results than the original setting.

More testing based on the simpler ConstrainedFitnessAL interface:

>>> import cma
>>> for algorithm, evals in zip((0, 1, 2, 3), (2000, 2200, 1500, 1800)):
...     alf = cma.ConstrainedFitnessAL(cma.ff.sphere, lambda x: [x[0] + 1], 3,
...                                    find_feasible_first=True)
...     _ = alf.al.set_algorithm(algorithm)
...     alf.al.logging = False
...     x, es = cma.fmin2(alf, 3 * [1], 0.1, {'verbose':-9, 'seed':algorithm},  # verbosity+seed for doctest only
...                       callback=alf.update)
...     assert sum((es.mean - [-1, 0, 0])**2) < 1e-9, (algorithm, es.mean)
...     assert es.countevals < evals, (algorithm, es.countevals)
...     assert alf.best_feas.f < 10, (algorithm, str(alf.best_feas))
...     # print(algorithm, es.countevals, ) #alf.best_feas.__dict__)