Introduction - Self-Adaptive Heuristics for Evolutionary Computation - page 4

freedom, especially when controlled self-adaptively. In order to minimize compu-
tational and implementation effort in comparison to other operators, the biased
mutation operator (BMO) has been developed. The BMO will be introduced as
a self-adaptive operator for biasing mutations into beneficial directions. It makes
use of a self-adaptive bias coe cient vector ξ which determines the direction of the
bias. The absolute bias can be computed by multiplication with the step sizes. We
introduce a couple of variants. The sBMO makes use of only one step size, but of-
fers N directions for the bias while the cBMO uses N steps sizes but only one bias
direction. Another biased mutation operator is the DMO, whose bias is adapted
according to the descent direction defined by the population centers of two suc-
cessive generations. Simplified theoretical considerations model the intuition, that
the success rate of biased Gaussian mutation is bigger than the success rate of the
unbiased correlate on monotone functions. This condition is fulfilled as long as
the DMO mechanism is able to find the descent direction. Experiments and sta-
tistical tests will show that the bias is beneficial in constrained domains, on ridge
functions and on some multimodal problems.
Chapter V: Self-Adaptive Mutations for Combinatorial Search Domains
In the past, the most successful applications of self-adaptation concerned mu-
tation operators. The most famous example is the step size adaptation of ES.
Discrete strategy parameters for self-adaptive mutations have not been consid-
ered much. In this chapter we propose to treat the number of successive in-
version mutations as mutation strength and evolve it self-adaptively. Inversion
mutation (INV) is a mutation operator for the evolutionary search in combi-
natorial domains. A famous example is the traveling salesman problem (TSP).
One application of INV swaps two pairwise connections, k iterations of INV in-
duce a bigger change of the original solution. The idea of self-adaptive inversion
mutation (SA-INV) is the self-adaptive control of the number of iterations the
operator INV is applied. A convergence analysis proves that INV and SA-INV
find the optimum in finite time with probability one. The experimental results
on various TSP instances show that SA-INV accelerates the optimization at the
beginning of the search. It turns out that at later phases of the search, more
than one applications of INV destroy the solution and lead to significant fitness
deteriorations. We call this problem strategy bound problem and offer an easy
heuristic. The Wilcoxon rank-sum test validates the statistical relevance of the
experiments.
Chapter VI: Self-Adaptive Crossover for Evolutionary Algorithms
Crossover plays a controversially discussed role within EAs. The building block
hypothesis assumes that crossover combines different useful blocks of the so-
lution. The genetic repair effect hypothesis assumes that common features of
parental solutions are mixed. The structure of existing crossover operators is
usually either fixed or based on randomness. With self-adaptive crossover we
take a step towards exploiting the structure of the problem automatically, i.e.