Page 76 - 49A Field Guide to Genetic Programming

62 7 Linear and Graph Genetic Programming

Arg 2
Output Arg 1 Opcode
R0..R7 R0..R7 + − * / 0...127
or
R0..R7

Figure 7.2: Format of a linear GP engine instruction. R0 to R7 refer to
CPU’s registers.

neighbouring instructions being normally executed in consecutive time steps
(albeit control structures, jumps and loops may change the execution order).
So, why not evolve linear programs? This led Banzhaf (1993), Perkis (1994)
as well as Openshaw and Turton (1994) to try linear GP.
Secondly, computers do not naturally run tree-shaped programs, so in-
terpreters or compilers have to be used as part of tree-based GP. On the
contrary, by evolving the binary bit patterns actually obeyed by the com-
puter, linear GP can avoid the use of this computationally expensive ma-
chinery and GP can run several orders of magnitude faster. This desire for
speed drove Nordin (1994), Nordin et al. (1999), Crepeau (1995) and Eklund
(2002).

7.1.2 Linear GP Representations

As discussed in Section 2.1, it is possible to use a linear representation in
tree-based GP. When doing so, however, the linear structures are simply
flattened representations of the trees. Thus, in the linear structure one can
still identify the root node, its children, and the rest of the tree structure.
In such a system, instructions typically communicate via their arguments.
The semantics of linear GP are quite different, however. In linear GP, in-
structions typically read their input(s) from one or more registers or memory
locations and store the results of their calculations in a register. For exam-
ple, they might take the form shown in Figure 7.2. This means instructions
in linear GP all have equivalent roles and communicate only via registers
or memory. In linear GP there is no equivalent of the distinction between
functions and terminals inherent in tree-based GP. Also, in the absence of
loops or branches, the position of the instructions determines the order of
their execution. Typically, this not the case for the structures representing
trees. 1
The instructions in linear GP may or may not represent executable ma-
chine code. That is, there are essentially two flavour of linear GP: machine
code GP, where each instruction is directly executable by the CPU, and
1 Typically, in tree-based-GP the nodes are visited (but not executed) from left to right
in depth-first order. Primitives are only executed, however, when their arguments have
been evaluated. So, the root node is the first node visited but the last executed.