Self-Adaptation - Self-Adaptive Heuristics for Evolutionary Computation - page 27

of crossover points be controlled self-adaptively in their approach called punc-
tuated crossover . Ostermeier et al. [102] introduced the cumulative path-length
control, an approach to derandomize the adaptation of strategy parameters. Two
algorithmic variants were the results of their attempts, the cumulative step-size
adaptation (CSA) and the covariance matrix adaptation (CMA), also see section
4.1.6. Weinberg [157] as well as Mercer and Sampson [90] were the first who in-
troduced metaevolutionary approaches. In metaevolutionary methods an outer
EA controls the parameters of an inner one which optimizes the problem itself.
3.2 An Extended Taxonomy of Parameter Setting
Techniques
After the design of the problem representation and the evaluation function the
EA has to be specified. Besides the chose of the genetic operators, adequate
parameters for the features of the EA have to be set. The parameter values
determine the effectivity and the eciency of the meta-heuristic. Appropriate
operators have to be chosen as well as appropriate initializations of the strategy
parameters. Furthermore, it can be useful to change these parameters during
the run of the EA. In order to classify parameter tuning and control techniques
of EAs the following aspects can be taken into account according to Eiben et
al. [37]: What is changed, how is the change made, what is the scope/level of
change and what is the evidence upon which the change is carried out.
3.2.1 Preliminary Work
Two main taxonomies of parameter adaptation have been introduced. Angeline
[1] divides parameter adaptation schemes into concepts with absolute update
rules and empirical update rules . Algorithms using absolute update rules change
their parameters using fixed rules and statistical data about the population or
over generations. The famous 1/5th success rule by Rechenberg [114] is an ex-
ample for this class of parameter adaptation. Algorithms with empirical update
rules control their parameters themselves. Strategy parameters are incorporated
into the individuals' genome and are subject to crossover and mutation. The
EA is able to control its parameters by letting individuals with high fitness val-
ues survive and inherit their strategy values. Furthermore, Angeline classifies
population-level , individual-level and component-level parameters. Population-
level parameters are changed for all individuals globally. Individual-level pa-
rameters are changed only for one individual while component-level adaptive
methods affect each component of an individual separately.
Eiben, Hinterding and Michalewicz [37] extended Angeline's adaptation tax-
onomy by taking the type of adaptation and the level of adaptation into account.
They distinguish between the following types of adaptation: static (user defined)
parameter settings, dynamic parameter control, adaptive parameter control and
self-adaptive parameter control. We take Eiben's taxonomy as the basis for our
extensions.