Page 30 - 49A Field Guide to Genetic Programming

16 2 Tree-based GP

Parents Offspring

Crossover
Point + (x+y)+3 + (x/2)+3

+ 3 / 3

x y x 2

Crossover
Point ∗ (y+1) (x/2)
*
+ /

y 1 x 2 GARBAGE

Figure 2.5: Example of subtree crossover. Note that the trees on the left
are actually copies of the parents. So, their genetic material can freely be
used without altering the original individuals.

to crossover operations frequently exchanging only very small amounts of
genetic material (i.e., small subtrees); many crossovers may in fact reduce
to simply swapping two leaves. To counter this, Koza (1992) suggested the
widely used approach of choosing functions 90% of the time and leaves 10%
of the time. Many other types of crossover and mutation of GP trees are
possible. They will be described in Sections 5.2 and 5.3, pages 42–46.
The most commonly used form of mutation in GP (which we will call
subtree mutation) randomly selects a mutation point in a tree and substi-
tutes the subtree rooted there with a randomly generated subtree. This is
illustrated in Figure 2.6. Subtree mutation is sometimes implemented as
crossover between a program and a newly generated random program; this
operation is also known as “headless chicken” crossover (Angeline, 1997).
Another common form of mutation is point mutation, which is GP’s
rough equivalent of the bit-flip mutation used in genetic algorithms (Gold-
berg, 1989). In point mutation, a random node is selected and the primitive
stored there is replaced with a different random primitive of the same arity
taken from the primitive set. If no other primitives with that arity ex-
ist, nothing happens to that node (but other nodes may still be mutated).
When subtree mutation is applied, this involves the modification of exactly
one subtree. Point mutation, on the other hand, is typically applied on a