Page 59 - 49A Field Guide to Genetic Programming

5.3 GP Crossover 45

Parent 1 Parent 2

+ * +
Parent 1 * Common
sin + * * sin * + * Region
Alignment Parent 2
x x x y y y * y x y x y x *

y y y y
Selection of
Common
Crossover Point
Offspring 1 Offspring 2 Crossover Point
+ * + *
Swap
sin * * + Parent 1 sin * + * Parent 2

x y * y y x x y x y x y x *

y y y y

Figure 5.1: Example of one-point crossover between parents of different
sizes and shapes.

each locus to decide whether the corresponding offspring node should be
picked from the first or the second parent. If a node to be inherited belongs
to the base of the common region and is a function, then the subtree rooted
there is inherited as well. With this form of crossover, there can be a greater
mixing of the code near the root than with other operators.
In context-preserving crossover (D’haeseleer, 1994), the crossover points
are constrained to have the same coordinates, like in one-point crossover.
Note that the crossover points are not limited to the common region.
In size-fair crossover (Langdon, 1999a, 2000) the first crossover point is
selected randomly, as with standard crossover. Then the size of the subtree
to be removed from the first parent is calculated. This is used to constrain
the choice of the second crossover point so as to guarantee that the subtree
excised from the second parent will not be “unfairly” big.
Harries and Smith (1997) suggested five new crossover operators that
are like standard crossover but with probabilistic restrictions on the depth
of crossover points within the parent trees.
Since crossover and mutation are specific to the representation used in
GP, each new representation tends to need new crossover and mutation
operators. For example “ripple crossover” (O’Neill et al., 2003) is a way
of looking at crossover in grammatical evolution (Section 6.2.3 page 55).