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

[63] proved that the (1+1)-ES using Gaussian mutations adapted by the 1/5-
rule needs a linear number of steps, i.e. O ( n ), to halve the approximation error
on the sphere function. The bound O ( n ) holds with ”overwhelming probability
of 1

λ √ ln λ )for
the (1 + λ )-ES with Rechernberg's rule. He proposes a modified 1/5th rule for
λ descendants as the regular algorithm fails for more than a single isotropic
mutation. To the best of our knowledge, a runtime analysis for a self-adaptive
ES has not been conducted yet with the exception of Auger's Markov chain
result.

e −Ω ( n 1 / 3 ) ”. Later, Jagerskupper [64] proved the bound O ( n − ·

3.7 A Self-Adaptive Estimation of Distribution View on
EAs

In the following we present a more generalized view on self-adaptation, i.e. we
define self-adaptation from the point of view of estimation of distribution algo-
rithms (EDAs). EDAs estimate the optimum with probability distributions.

3.7.1 Preliminary Views on Self-Adaptation

Back [8] gave insight into a generalized view on self-adaptation. From his point of
view self-adaptation is biasing the population distribution to appropriate regions
of the search space controlling the transmission function (crossover and/or mu-
tation) between parents and offspring. Beyer and Meyer-Nieberg [91] point out
that this can happen explicitly or implicitly. We refer to explicit self-adaptation
if strategy variables exist which control the operator's properties. In contrast,
implicit self-adaptation means that the operators exhibit properties that allow bi-
asing the population distribution without containing strategy parameters. Beyer
and Deb [33], [34] showed that binary GAs with well-designed crossover oper-
ators exhibit self-adaptive behavior, although they do not contain any strat-
egy variables. They point out that one- and n-point-crossover can be seen as
self-adaptive mutation operators for binary representations as common bit posi-
tions of the parents are transferred to the offspring. Consequently, the diversity
in the parental population controls the diversity of the offspring population.
Also Glickman and Sycara [46] see implicit self-adaptation as a non-injective
genotype-phenotype mapping with variations of the genome. It exhibits an in-
fluence on the transmission function, but does not influence the fitness. Further-
more, the success of self-adaptation depends on the population's diversity. The
self-adaptation of the operator's parameters improve the convergence speed .The
degree of diversity determines the convergence reliability .
Another point of view on self-adaptation is the following. The strategy part
of the genome is neutral concerning genotype-phenotype mapping, Igel and Tou-
ssaint [61] express that all neutral parts of the genome give the EA the ability
to “vary the search space distribution independent of the phenotypic variation”.
A genome part is called neutral if it does not cause an influence on the pheno-
type and on the fitness. As the an analog argument holds for self-adaptation.