Summary and Conclusion - Self-Adaptive Heuristics for Evolutionary Computation - page 133

work with discrete representations. For these not many successful self-adaptation
techniques are known.

• Self-adaptive inversion mutation. In this work we presented the SA-INV,

a successful example for discrete mutation strength self-adaptation. Inversion
mutation is the most common mutation operator for GAs on combinatorial
problems like the TSP. SA-INV is the self-adaptive variant of inversion muta-
tion. Its strategy parameter k determines the number of successive inversions,
i.e. swaps of edges. A convergence analysis proves that INV and SA-INV find
the optimum in finite time with probability one. The experimental analysis
showed that SA-INV is able to speed up the optimization, in particular at
the beginning of the search. Parameter k is usually decreasing during the
optimization as less and less edge swaps are advantageous for the improve-
ment and not the destruction of solutions. But when reaching k 1, SA-INV

slows down, as self-adaptation still produces solutions with k> 1andaworse
success rate. We call this problem strategy bound problem .Toovercomethe
strategy bound problem in later search phases, we introduced the SA-INV-c
heuristic, which sets k = 1 constantly if the condition u

≈

λ

2 is fulfilled. The
experimental analysis shows that the modification improves the performance
of SA-INV. The Wilcoxon rank-sum test validates the statistical significance
of the results.

≥

Two successful examples for self-adaptive mutations have been introduced. But
also self-adaptive properties for the second important genetic operator, crossover,
have been investigated. Crossover plays a controversial discussed role within EAs.
BBH and GR hypothesis give conflictive explanations for the working principle
of crossover. The structure of most existing crossover operators is not adaptive,
but either random or fixed.

• Self-adaptation of structural crossover properties. We introduced self-

adaptive n-point crossover, self-adaptive partially mapped crossover and self-
adaptive recombination for ES. Our experiments showed that self-adaptive
crossover achieves no significant improvements on combinatorial problems
like the TSP (PMX), on continuous optimization problems (discrete and
intermediate recombination) as well as on bit-string problems (one- and n-
point crossover). We see two main reasons for the weakness of self-adaptive
crossover. First, the fitness gain achieved by optimal crossover settings is
weak, e.g. for multimodal continuous problems. Experiments with the
crossover optimization EA could only discover valuable fitness gain on uni-
modal or monotone functions like sphere and ridge. Second, even if the gain
of a specific crossover strategy parameter set is advantageous, it may not be
optimal in the following generation. This hinders a self-adaptation of useful
crossover points and building blocks . For future research we see the challenge
to tighten the link between strategy parameter adaptation and fitness gain
by choosing individuals from different mating pools or subpopulations with
different properties.