Page 78 - 49A Field Guide to Genetic Programming

64 7 Linear and Graph Genetic Programming

bomb disposal (Deschaine, Hoover, Skibinski, Patel, Francone, Nordin, and
Ades, 2002).
Note that execution speed is not the only reason for using linear GP. Al-
though interpreted linear programs are slower than machine-code programs,
an interpreted linear GP system can be more efficient than an interpreted
tree-based systems. Also, a simple linear structure lends itself to rapid anal-
ysis. Brameier and Banzhaf (2001) showed a linear program can be easily
scanned and any “dead code” it contains can be removed. In some ways the
search space of linear GP is also easier to analyse than that of trees (Lang-
don, 1999b, 2002a,b, 2003a; Langdon and Banzhaf, 2005). For example,
Langdon (2006); Langdon and Poli (2006,?, 2008) have used (in simulation)
two simple architectures, called T7 and T8), for several large scale experi-
ments and for the mathematical analysis of Turing complete GP. For these
reasons, it makes sense to consider linear virtual-machine code GP even
when using languages like Java that are typically run on virtual machines;
one can in fact use a virtual machine (like (Leung et al., 2002)) to inter-
pret the evolved byte code (Harvey, Foster, and Frincke, 1999; Lukschandl,
Borgvall, Nohle, Nordahl, and Nordin, 2000).

7.1.3 Linear GP Operators

The typical crossover and mutation operators for linear GP ignore the details
of the machine code of the computer being used. For example, crossover may
choose randomly two crossover points in each parent and swaps the code
between them. Since the crossed over fragments are typically of different
lengths, such a crossover may change the programs’ lengths, cf. Figure 7.3.
Since computer machine code is organised into 32- or 64-bit words, the
crossover points occur only at the boundaries between words. Therefore,
a whole number of words, containing a whole number of instructions are
typically swapped over. Similarly, mutation operations normally respect
word boundaries and generate legal machine code. However, linear GP lends
itself to a variety of other genetic operations. For example, Figure 7.4 shows
homologous crossover. Many other crossover and mutation operations are
possible (Langdon and Banzhaf, 2005).
In a compiling genetic programming system (Banzhaf, Francone, and
Nordin, 1996) the mutation operator acts on machine code instructions
and is constrained to “ensure that only instructions in the function set are
generated and that the register and constant values are within predefined
ranges allowed in the experimental set up”. On some classification prob-
lems Banzhaf et al. (1996) reported that performance was best when using
crossover and mutation in equal proportions. They suggested that this was
due to the GP population creating “introns” (blocks of code that does not
affect fitness) in response to the crossover operator, and that these were sub-
sequently converted into useful genetic material by their mutation operator.