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

6 Self-Adaptive Crossover

Just as a child creates magnificent fortresses through the arrangement of simple
blocks, so does a genetic algorithm seek near optimal performance through the
juxtaposition of short, low-order, high-performance schemata, or building blocks.
Goldberg about the building block hypothesis [47], p. 41.

Crossover plays a controversially discussed role within EAs. The building block
hypothesis (BBH) assumes that crossover combines different useful blocks of
parents. The genetic repair effect (GR) hypothesis assumes that common prop-
erties of parental solutions are mixed. Most of today's crossover operators do not
exhibit adaptive properties, but are either completely random or fixed. In this
chapter self-adaptive crossover operators for string and combinatorial represen-
tations are introduced. For GAs in string representation self-adaptive crossover
means the automatic adaptation of crossover points. With self-adaptive crossover
we take a step towards exploiting the structure of the problem automatically,
i.e. finding the building blocks or common features self-adaptively. The features
we prose to control self-adaptively are crossover points for string representations
and recombination factors for ES. A success of self-adaptive crossover would be a
hint for the existence of building blocks. A failure would not prove that building
blocks do not exist, but could either be a hint for their absence or for the fact
that they cannot be identified with self-adaptive crossover points.
In section 6.1 we discuss the role of crossover and introduce the self-adaptive
crossover concept. Section 6.2 introduces self-adaptive n-point crossover with an
experimental analysis. We test the SA crossover operators for string representa-
tions on the problems onemax, ackley and 3-SAT. Partially mapped crossover
(PMX) is a crossover operator for combinatorial search domains. In section
6.3 we introduce a self-adaptive variant of PMX. Afterwards, section 6.4 an-
alyzes self-adaptive recombination for ES. Although the experimental results of
this chapter are not very encouraging, the crossover point optimization EA of
section 6.5 shows that optimal crossover points exist.

6.1 The Self-Adaptive Crossover Concept

There are two reasons why self-adaptation for crossover is not a simple under-
taking. First, the set of problems where crossover might be beneficial is small