Page 56 - 49A Field Guide to Genetic Programming

42 5 Alternative Initialisations and Operators in Tree-based GP

5.2 GP Mutation

5.2.1 Is Mutation Necessary?

Mutation was used in early experiments in the evolution of programs, e.g.,
in (Bickel and Bickel, 1987; Cramer, 1985; Fujiki and Dickinson, 1987). It
was not, however, used in (Koza, 1992) and (Koza, 1994), as Koza wished to
demonstrate that mutation was not necessary and that GP was not perform-
ing a simple random search. This has significantly influenced the field, and
mutation is often omitted from GP runs. While mutation is not necessary
for GP to solve many problems, O’Reilly (1995) argued that mutation — in
combination with simulated annealing or stochastic iterated hill climbing —
can perform as well as crossover-based GP in some cases. Nowadays, mu-
tation is widely used in GP, especially in modelling applications. Koza also
advises to use of a low level of mutation; see, for example, (Koza, Bennett,
Andre, and Keane, 1996b).
Comparisons of crossover and mutation suggest that including mutation
can be advantageous. Chellapilla (1997b) found that a combination of six
mutation operators performed better than previously published GP work on
four simple problems. Harries and Smith (1997) also found that mutation
based hill climbers outperformed crossover-based GP systems on similar
problems. Luke and Spector (1997) suggested that the situation is complex,
and that the relative performance of crossover and mutation depends on
both the problem and the details of the GP system.

5.2.2 Mutation Cookbook
With linear bit string GAs, mutation usually consists of random changes in
bit values. In contrast, in GP there are many mutation operators in use.
Often multiple types of mutation are beneficially used simultaneously (e.g.,
see (Kraft, Petry, Buckles, and Sadasivan, 1994) and (Angeline, 1996)). We
describe a selection of mutation operators below:

Subtree mutation replaces a randomly selected subtree with another ran-
domly created subtree (Koza, 1992, page 106). Kinnear (1993) defined
a similar mutation operator, but with a restriction that prevents the
offspring from being more than 15% deeper than its parent.

Size-fair subtree mutation was proposed in two forms by Langdon
(1998). In both cases, the new random subtree is, on average, the
same size as the code it replaces. The size of the random code is given
either by the size of another random subtree in the program or chosen
at random in the range [l/2, 3l/2] (where l is the size of the subtree
being replaced). The first of these methods samples uniformly in the
space of possible programs, whereas the second samples uniformly in