Page 29 - 49A Field Guide to Genetic Programming

2.4 Recombination and Mutation 15

from the population. These are compared with each other and the best of
them is chosen to be the parent. When doing crossover, two parents are
needed and, so, two selection tournaments are made. Note that tourna-
ment selection only looks at which program is better than another. It does
not need to know how much better. This effectively automatically rescales
4
fitness, so that the selection pressure on the population remains constant.
Thus, a single extraordinarily good program cannot immediately swamp the
next generation with its children; if it did, this would lead to a rapid loss
of diversity with potentially disastrous consequences for a run. Conversely,
tournament selection amplifies small differences in fitness to prefer the bet-
ter program even if it is only marginally superior to the other individuals in
a tournament.
An element of noise is inherent in tournament selection due to the ran-
dom selection of candidates for tournaments. So, while preferring the best,
tournament selection does ensure that even average-quality programs have
some chance of having children. Since tournament selection is easy to imple-
ment and provides automatic fitness rescaling, it is commonly used in GP.
Considering that selection has been described many times in the evolu-
tionary algorithms literature, we will not provide details of the numerous
other mechanisms that have been proposed. (Goldberg, 1989), for example,
describes fitness-proportionate selection, stochastic universal sampling and
several others.

2.4 Recombination and Mutation

GP departs significantly from other evolutionary algorithms in the imple-
mentation of the operators of crossover and mutation. The most commonly
used form of crossover is subtree crossover. Given two parents, subtree
crossover randomly (and independently) selects a crossover point (a node)
in each parent tree. Then, it creates the offspring by replacing the subtree
rooted at the crossover point in a copy of the first parent with a copy of
the subtree rooted at the crossover point in the second parent, as illustrated
in Figure 2.5. Copies are used to avoid disrupting the original individuals.
This way, if selected multiple times, they can take part in the creation of
multiple offspring programs. Note that it is also possible to define a version
of crossover that returns two offspring, but this is not commonly used.
Often crossover points are not selected with uniform probability. Typical
GP primitive sets lead to trees with an average branching factor (the num-
ber of children of each node) of at least two, so the majority of the nodes
will be leaves. Consequently the uniform selection of crossover points leads
4 A key property of any selection mechanism is selection pressure. A system with a
strong selection pressure very highly favours the more fit individuals, while a system with
a weak selection pressure isn’t so discriminating.