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

It was originally introduced by Rechenberg [114] and Schwefel [132], later by Fo-
gel [42] for EP. Self-adaptive algorithms are characterized by the integration of
strategy parameters, which influence the genetic operators, into the individual's
chromosomes. These parameters undergo genetic variation and are involved into
the evolutionary optimization process. For detailed descriptions and definitions
we refer to chapter 3.
Crossover is the main genetic operator besides mutation and selection. Its
role has not been satisfactorily explained. Is it just creating noise similar to
mutation or are there really building blocks, structurally connected parts of
the solution useful to exchange during evolution? And where are the borders
of these building blocks, the best positions for crossover points? Do they really
exist, and, if so, are they dynamically changing during the optimization pro-
cess or are they constant? We think that these questions cannot be answered
in general, but are problem dependent. In the following we attempt to use the
concept of self-adaptation to let the evolution itself identify the structural pa-
rameters of crossover. It was our hope that this exploitation aspect of crossover
is a source of effectivity and eciency improvements. For string representations
these parameters mainly concern the crossover points.
In this chapter the designs for self-adaptive crossover operators are proposed.
For binary and integer values the string representation is commonly used. For
these kinds of representations intuitive crossover operators exist. Let p 1 ,..., p ρ
be ρ parents, each consisting of objective variables O =( p 1 ,...,p N ). We extend
the genome by strategy variables Σ =( Λ 1 ,...,Λ n ), which encode self-adaptive
crossover features. Each individual consists of p i =( O, Σ ), the same holds for
offspring individuals o i .

Crossover Point Selection Schemes

Consider ρ parents are used during recombination. It has to be specified, which
crossover point set Σ ζ of the ρ parents are used. We propose the following
heuristic to determine Σ ζ :

Best inheritance. In this mode the strategy set Σ ζ of the best of the randomly
chosen ρ parents is used and inherited to all offspring solutions.

•

ζ = argmax j, 1 ≤j≤ρ f ( p j ) (6.1)

For the sake of completeness we introduce the variations dominant and inter-
mediate inheritance :
• Dominant inheritance. Aparent p ζ is randomly chosen from the ρ parents

with uniform distribution. Its strategy set Σ ζ

is taken.

• Intermediate inheritance. For each component of the ρ strategy sets an in-

termediate strategy set Σ is computed by

j =1 Λ k
ρ

Λ i = . (6.2)