Self-Adaptive Crossover - Self-Adaptive Heuristics for Evolutionary Computation - page 92

6.1.2 Preliminary Work
Self-adaptation for crossover played only a marginal role for EA research in the
last decades. Instead, most research concentrated on mutation operators. One
reason for this might be the historical development as it was first introduced for
ES and EP, where crossover was almost neglected at the beginning [91]. The first
attempt to integrate self-adaptation into crossover was punctuated crossover by
Schaffer and Morishima [128]. Punctuated crossover adapts the crossover points
for bit string representations and was experimentally proved better than stan-
dard one-point crossover. A strategy parameter vector with the same length as
the objective variable vector is added to the individual's representation. It is
filled with ones, the so called punctuation marks, wherever a crossover point ex-
ists. Punctuation marks from both parents indicate a change from which parent
the next part of the genome has to be copied to the offspring. This self-adaptive
variant outperforms a canonical GA on four of five De Jong's test functions.
Two interesting observations were made: First, some bit positions tended to ac-
cumulate more punctuation marks than others and these accumulations changed
over time. Second, the number of events, when nonidentical gene segments are
swapped between parents while offspring different from its parents is produced
is constant and depends on the representation length. Spears [147] does not hold
self-adaptation responsible for the success of punctuated crossover, but the us-
age of more than one crossover points. He proposed the one-bit self-adaptive
crossover, which makes use of a bit indicating the crossover type. This tech-
nique is similar to our self-adaptive mutation operator selection of section 4.6.
The bit switches between uniform and two-point crossover. From his tests on
N-peak problems Spears derived the conclusion that the key feature of his self-
adaptation experiment is not the possibility to select the best operator, but the
degree of freedom for the EA to choose among two operators during the search.
This kind of self-adaptation only concerns the selection of a crossover type, but
not its structure like in our approach. Maruo et al. introduced an approach,
where self-adaptive crossover means the control of the crossover probability p c
[88].
Another technique refers to the identification of building blocks, the LEGO
(linkage evolving genetic operator) algorithm [143]. Each gene exhibits two bits
indicating the linkage to neighboring genes which is only possible if the same
bits are set. New candidate solutions are created from left to right conducting
tournaments between parental blocks. Meyer-Nieberg and Beyer [91] point out
that even the standard 1- or n-point crossover operators for bit string repre-
sentations exhibit properties of a self-adaptive mutation operator. Bit positions
which are common in both parents are transferred to the offspring individuals
while other positions are filled randomly. This assumption is consistent with the
GR hypothesis and in contrast to the BBH.
6.1.3 Adaptation of the Crossover Structure
The concept of self-adaptation is a step into the direction of parameter indepen-
dent EC. Self-adaptation is usually associated with the step size control of ES.