Page 57 - 49A Field Guide to Genetic Programming

5.2 GP Mutation 43

the space of program lengths. Experiments suggested that there was
far more bloat (cf. Section 11.3.1 page 101) with the first mutation
operator.
Node replacement mutation (also known as point mutation) is similar
to bit string mutation in that it randomly changes a point in the
individual. In linear GAs the change would be a bit flip. In GP,
instead, a node in the tree is randomly selected and randomly changed.
To ensure the tree remains legal, the replacement node has the same
number of arguments as the node it is replacing, e.g. (McKay, Willis,
and Barton, 1995, page 488).

Hoist mutation creates a new offspring individual which is copy of a ran-
domly chosen subtree of the parent. Thus, the offspring will be smaller
than the parent and will have a different root node (Kinnear, 1994a).
Shrink mutation replaces a randomly chosen subtree with a randomly
created terminal (Angeline, 1996). This is a special case of subtree
mutation where the replacement tree is a terminal. As with hoist
mutation, it is motivated by the desire to reduce program size.

Permutation mutation selects a random function node in a tree and then
randomly permuting its arguments (subtrees). Koza (1992) used per-
mutation in one experiment [page 600] where it was shown to have
little effect. In contrast, Maxwell (1996) had more success with a mu-
tation operator called swap, which is simply a permutation mutation
restricted to binary non-commutative functions.

Mutating constants at random Schoenauer, Sebag, Jouve, Lamy, and
Maitournam (1996) mutated constants by adding random noise from
a Gaussian distribution. Each change to a constant was considered a
separate mutation.

Mutating constants systematically A variety of potentially expensive
optimisation tools have been applied to try and fine-tune an existing
program by finding the “best” value for the constants within it. Indeed
STROGANOFF (Iba, Sato, and de Garis, 1995b; Nikolaev and Iba,
2006) optimises each tree modified by crossover. Clever mechanisms
are employed to minimise the computation required.
(McKay et al., 1995, page 489) is more in keeping with traditional GP
and uses a mutation operator that operates on terminals, replacing in-
put variables by constants and vice versa. In this approach “whenever
a new constant is introduced [. . . ] a non-linear least squares optimisa-
tion is performed to obtain the ‘best’ value of the constant(s)”. Schoe-
nauer, Lamy, and Jouve (1995) also used a mutation operator that