On Self-Adaptation in Evolution Strategies

Self-adaptation of strategy parameters is an essential feature in evolution strategies. Typically, and most important, parameters of the search distribution (mutation distribution) are adapted, for example a single step-size. An advanced objective is to facilitate an adaptation to nonseparable and/or badly scaled problems. In the evolution strategy this requires the adaptation of arbitrary normal mutation distributions (with zero mean) and this is equivalent to a general linear transformation of the object parameter space. General demands on such an adaptation mechanism are considered in [1]. In case of successful adaptation local and global search properties can be improved [1].

In the early nineties we developed the derandomized approach to self-adaptation in evolution strategies (see e.g. [1],[2]]). In an advanced level of derandomization the adaptation takes place without any independent stochastic variation of the strategy parameters. The selected points (more specific: selected mutation steps) in object parameter space are used directly for strategy parameter adjustment. We compared three different approaches to self-adaptation of their capability to adapt arbitrary normal mutation distributions and to meet the demands identified in [1]:

The common mutative approach (different mutation operators were tested).
The hierachically ordered multi-population approach, where a few populations with different strategy parameter settings run in parallel for a given isolation time.
The completely derandomized approach (CMA-ES).

When the mutation operator was chosen carefully [3] all three approaches could reliably adapt arbitrary normal mutation distributions independently of the chosen coordinate system. (This cannot be achieved with the conventional mutation operator [4].) The following table shows quite coarse performance data of the three approaches:

mutative multi-population derandomized

population size 4n² 6×6 10

serial progress 1 / n³ 0.04 / n 0.1 / n

adaptation costs 20n⁴ 300n⁵ 80n²

	mutative	multi-population	derandomized
population size	4n²	6×6	10
serial progress	1 / n³	0.04 / n	0.1 / n
adaptation costs	20n⁴	300n⁵	80n²

Here n is the problem dimension and the following applies:

population size	Roughly the minimal population size (λ) that allows a reliable adaptation within this strategy variant.
serial progress	Progress rate per generation divided by the population size (i.e. φ / λ) on the sphere model with a distance to optimum of one. The serial progress φ/λ can be interpreted as the relative reduction of the distance to optimum per function evaluation. The highly competitive (1+1)-ES with optimal step size has a serial progress rate of 0.2 / n. It reduces the distance to optimum by approximately 20% in n steps. Large progress rates are to be preferred.
adaptation costs	Number of function evaluations needed to adapt from a spherical distribution to an elliptical distribution or vice versa. The elliptical target distribution has n different axis lengths and a maximal axis length ratio of 1000. Small adaptation costs are to be preferred.

We can conclude from the data that for problem dimensions greater than three only the derandomized approach turns out to be of practical relevance. Only the CMA-ES reliably adapts arbitrary normal mutation distributions (independently of the chosen coordinate system) with a reasonable efficiency. Moreover it reveals very competitive serial progress rates.

References

[1] Hansen, N. and Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 9(2), pp. 159-195.

[2] Ostermeier, A., Gawelczyk, A. and Hansen, N. (1994). A Derandomized Approach to Self-Adaptation of Evolution Strategies. Evolutionary Computation 2(4), 369-380.

[3] Ostermeier, A. and N. Hansen (1999). An evolution strategy with coordinate system invariant adaptation of arbitrary normal mutation distributions within the concept of mutative strategy parameter control. In W.Banzhaf, J.Daida, A.Eiben, M.H.Garzon, V.Honavar, M.Jakiela, R.E.Smith (Eds.), GECCO-99 Proceedings of the Genetic and Evolutionary Computation Conference, pp. 902-909, San Francisco: Morgan Kaufmann Publishers.

[4] Hansen , N. (2000). Invariance, Self-Adaptation and Correlated Mutations in Evolution Strategies. Sixth International Conference on Parallel Problem Solving from Nature (PPSN VI), Proceedings, pp. 355-364.

http://www.lri.fr/~hansen/research_adapt.html, updated May, 2006