cma.recombination_weights.RecombinationWeights

class documentation

class RecombinationWeights(list):

View In Hierarchy

a list of decreasing (recombination) weight values.

To be used in the update of the covariance matrix C in CMA-ES as w_i:

C <- (1 - c1 - cmu * sum w_i) C + c1 ... + cmu sum w_i y_i y_i^T

After calling finalize_negative_weights, the weights w_i let 1 - c1 - cmu * sum w_i = 1 and guaranty positive definiteness of C if y_i^T C^-1 y_i <= dimension for all w_i < 0.

Class attributes/properties:

  • lambda_: number of weights, alias for len(self)
  • mu: number of strictly positive weights, i.e. sum([wi > 0 for wi in self])
  • mueff: variance effective number of positive weights, i.e. 1 / sum([self[i]**2 for i in range(self.mu)]) where 1 == sum([self[i] for i in range(self.mu)])**2
  • mueffminus: variance effective number of negative weights
  • positive_weights: np.array of the strictly positive weights
  • finalized: True if class instance is ready to use

Class methods not inherited from list:

Usage:

>>> # from recombination_weights import RecombinationWeights
>>> from cma.recombination_weights import RecombinationWeights
>>> dimension, popsize = 5, 7
>>> weights = RecombinationWeights(popsize)
>>> c1 = 2. / (dimension + 1)**2  # caveat: __future___ division
>>> cmu = weights.mueff / (weights.mueff + dimension**2)
>>> weights.finalize_negative_weights(dimension, c1, cmu)
>>> print('weights = [%s]' % ', '.join("%.2f" % w for w in weights))
weights = [0.59, 0.29, 0.12, 0.00, -0.31, -0.57, -0.79]
>>> print("sum=%.2f, c1+cmu*sum=%.2f" % (sum(weights),
...                                      c1 + cmu * sum(weights)))
sum=-0.67, c1+cmu*sum=0.00
>>> print('mueff=%.1f, mueffminus=%.1f, mueffall=%.1f' % (
...       weights.mueff,
...       weights.mueffminus,
...       sum(abs(w) for w in weights)**2 /
...         sum(w**2 for w in weights)))
mueff=2.3, mueffminus=2.7, mueffall=4.8
>>> weights = RecombinationWeights(popsize)
>>> print("sum=%.2f, mu=%d, sumpos=%.2f, sumneg=%.2f" % (
...       sum(weights),
...       weights.mu,
...       sum(weights[:weights.mu]),
...       sum(weights[weights.mu:])))
sum=0.00, mu=3, sumpos=1.00, sumneg=-1.00
>>> print('weights = [%s]' % ', '.join("%.2f" % w for w in weights))
weights = [0.59, 0.29, 0.12, 0.00, -0.19, -0.34, -0.47]
>>> weights = RecombinationWeights(21)
>>> weights.finalize_negative_weights(3, 0.081, 0.28)
>>> weights.insert(weights.mu, 0)  # add zero weight in the middle
>>> weights = weights.set_attributes_from_weights()  # change lambda_
>>> assert weights.lambda_ == 22
>>> print("sum=%.2f, mu=%d, sumpos=%.2f" %
...       (sum(weights), weights.mu, sum(weights[:weights.mu])))
sum=0.24, mu=10, sumpos=1.00
>>> print('weights = [%s]%%' % ', '.join(["%.1f" % (100*weights[i])
...                                     for i in range(0, 22, 5)]))
weights = [27.0, 6.8, 0.0, -6.1, -11.7]%
>>> weights.zero_negative_weights()  #  doctest:+ELLIPSIS
[0.270...
>>> "%.2f, %.2f" % (sum(weights), sum(weights[weights.mu:]))
'1.00, 0.00'
>>> mu = int(weights.mu / 2)
>>> for i in range(len(weights)):
...     weights[i] = 1. / mu if i < mu else 0
>>> weights = weights.set_attributes_from_weights()
>>> 5 * "%.1f  " % (sum(w for w in weights if w > 0),
...                 sum(w for w in weights if w < 0),
...                 weights.mu,
...                 weights.mueff,
...                 weights.mueffminus)
'1.0  0.0  5.0  5.0  0.0  '

The optimal weights on the sphere and other functions are closer to exponent 0.75:

>>> for expo, w in [(expo, RecombinationWeights(5, exponent=expo))
...                 for expo in [1, 0.9, 0.8, 0.7, 0.6, 0.5]]:
...    assert all([len(w(i)) == i for i in range(3, 8)])
...    print(7 * "%.2f " % tuple([expo, w.mueff] + w))
1.00 1.65 0.73 0.27 0.00 -0.36 -0.64
0.90 1.70 0.71 0.29 0.00 -0.37 -0.63
0.80 1.75 0.69 0.31 0.00 -0.39 -0.61
0.70 1.80 0.67 0.33 0.00 -0.40 -0.60
0.60 1.84 0.65 0.35 0.00 -0.41 -0.59
0.50 1.89 0.62 0.38 0.00 -0.43 -0.57

>>> for lam in [8, 8**2, 8**3, 8**4]:
...     if lam == 8:
...         print(" lam expo mueff        w[i] / w[i](1)")
...         print("          /mu(1) 1   2    3    4    5    6    7    8")
...     w1 = RecombinationWeights(lam, exponent=1)
...     for expo, w in [(expo, RecombinationWeights(lam, exponent=expo))
...                     for expo in [1, 0.8, 0.6]]:
...         print('%4d ' % lam + 10 * "%.2f " % tuple([expo, w.mueff / w1.mueff] + [w[i] / w1[i] for i in range(8)]))
 lam expo mueff        w[i] / w[i](1)
          /mu(1) 1   2    3    4    5    6    7    8
   8 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
   8 0.80 1.11 0.90 1.02 1.17 1.50 1.30 1.07 0.98 0.93
   8 0.60 1.24 0.80 1.02 1.35 2.21 1.68 1.13 0.95 0.85
  64 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
  64 0.80 1.17 0.82 0.86 0.88 0.91 0.93 0.95 0.97 0.98
  64 0.60 1.36 0.65 0.72 0.76 0.80 0.84 0.87 0.91 0.94
 512 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
 512 0.80 1.20 0.76 0.78 0.79 0.80 0.81 0.82 0.83 0.83
 512 0.60 1.42 0.56 0.59 0.61 0.63 0.64 0.65 0.67 0.68
4096 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
4096 0.80 1.21 0.71 0.73 0.74 0.74 0.75 0.75 0.76 0.76
4096 0.60 1.44 0.50 0.52 0.53 0.54 0.55 0.55 0.56 0.56

Reference: Hansen 2016, arXiv:1604.00772.

Method __call__ return a cut or expanded weight list with similar mueff if possible
Method __init__ return recombination weights list, post condition is sum(self) == 0 and sum(self.positive_weights) == 1.
Method do_asserts assert consistency.
Method finalize_negative_weights finalize negative weights using dimension and learning rates c1 and cmu.
Method set_attributes_from_weights make the class attribute values consistent with weights, in case after (re-)setting the weights from input parameter weights, post condition is also sum(self.postive_weights) == 1.
Method zero_negative_weights finalize by setting all negative weights to zero
Instance Variable debug Undocumented
Instance Variable exponent Undocumented
Instance Variable finalized Undocumented
Instance Variable mu Undocumented
Instance Variable mueff Undocumented
Property asarray return weights as numpy array
Property lambda_ alias for len(self)
Property mueffminus Undocumented
Property positive_weights all (strictly) positive weights as np.array.
Method _negative_weights_limit_sum lower bound the sum of negative weights to -abs(value).
Method _negative_weights_set_sum set sum of negative weights to -abs(value)
Instance Variable _c1 Undocumented
Instance Variable _cmu Undocumented
def __call__(self, lambda_):

return a cut or expanded weight list with similar mueff if possible

def __init__(self, len_, exponent=1):

return recombination weights list, post condition is sum(self) == 0 and sum(self.positive_weights) == 1.

Positive and negative weights sum to 1 and -1, respectively. The number of positive weights, self.mu, is about len_/2. Weights are strictly decreasing.

finalize_negative_weights (...) or zero_negative_weights () should be called to finalize the negative weights.

Parameters
len_AKA lambda is the number of weights, see attribute lambda_ which is an alias for len(self). Alternatively, a list of "raw" weights can be provided.
exponentUndocumented
def do_asserts(self):

assert consistency.

Assert:

  • attribute values of lambda_, mu, mueff, mueffminus
  • value of first and last weight
  • monotonicity of weights
  • sum of positive weights to be one
def finalize_negative_weights(self, dimension, c1, cmu, pos_def=True):

finalize negative weights using dimension and learning rates c1 and cmu.

This is a rather intricate method which makes this class useful. The negative weights are scaled to achieve in this order:

  1. zero decay, i.e. c1 + cmu * sum w == 0,
  2. a learning rate respecting mueff, i.e. sum |w|^- / sum |w|^+ <= 1 + 2 * self.mueffminus / (self.mueff + 2),
  3. if pos_def guaranty positive definiteness when sum w^+ = 1 and all negative input vectors used later have at most their dimension as squared Mahalanobis norm. This is accomplished by guarantying (dimension-1) * cmu * sum |w|^- < 1 - c1 - cmu via setting sum |w|^- <= (1 - c1 -cmu) / dimension / cmu.

The latter two conditions do not change the weights with default population size.

Details:

  • To guaranty 3., the input vectors associated to negative weights must obey ||.||^2 <= dimension in Mahalanobis norm.
  • The third argument, cmu, usually depends on the (raw) weights, in particular it depends on self.mueff. For this reason the calling syntax weights = RecombinationWeights(...).finalize_negative_weights(...) is not supported.
def set_attributes_from_weights(self, weights=None, do_asserts=True):

make the class attribute values consistent with weights, in case after (re-)setting the weights from input parameter weights, post condition is also sum(self.postive_weights) == 1.

This method allows to set or change the weight list manually, e.g. like weights[:] = new_list or using the pop, insert etc. generic list methods to change the list. Currently, weights must be non-increasing and the first weight must be strictly positive and the last weight not larger than zero. Then all weights are normalized such that the positive weights sum to one.

def zero_negative_weights(self):

finalize by setting all negative weights to zero

debug: bool =

Undocumented

exponent: int =

Undocumented

finalized: bool =

Undocumented

mu =

Undocumented

mueff =

Undocumented

@property
asarray =

return weights as numpy array

@property
lambda_ =

alias for len(self)

@property
mueffminus =

Undocumented

@property
positive_weights =

all (strictly) positive weights as np.array.

Useful to implement recombination for the new mean vector.

def _negative_weights_limit_sum(self, value):

lower bound the sum of negative weights to -abs(value).

def _negative_weights_set_sum(self, value):

set sum of negative weights to -abs(value)

Precondition: the last weight must no be greater than zero.

Details: if no negative weight exists, all zero weights with index lambda / 2 or greater become uniformely negative.

_c1 =

Undocumented

_cmu =

Undocumented