Page 80 - 49A Field Guide to Genetic Programming

66 7 Linear and Graph Genetic Programming

max

max
∗ +
+

x y ∗ 3 ∗ 3

x y x y

(a) (b)

Figure 7.5: A sample tree where the same subtree is used twice (a) and
the corresponding graph-based representation of the same program (b). The
graph representation may be more efficient since it makes it possible to avoid
the repeated evaluation of the same subtree.

with nodes representing functions and terminals. Edges represent both con-
trol flow and data flow. The possible efficiency gains obtained by a graph
representation are illustrated in Figure 7.5.
In the simplest form of PDGP edges are directed and unlabelled, in
which case PDGP is a generalisation of standard GP. However, more com-
plex representations can be used, which allow the evolution of: programs,
including standard tree-like programs, logic networks, neural networks, re-
current transition networks and finite state automata. This can be achieved
by extending the representation by associating labels with the edges of the
program graph. In addition to the function and terminal sets, this form of
PDGP requires the definition of a link set. The labels on the links depend
on what is to be evolved. For example, in neural networks, the link labels
are numerical constants for the neural network weights. In a finite state au-
tomaton, the edges are labelled with the input symbols that determine the
FSA’s state transitions. It is even possible for the labels to be automatically
defined edges, which play a role similar to ADFs (Section 6.1.1) by invoking
other PDGP graphs.
In PDGP, programs are manipulated by special crossover and mutation
operators which guarantee the syntactic correctness of the offspring. Each
node occupies a position in a regular grid. The genetic operators act by
moving, copying or randomly generating sub-regions of the grid. For this
reason PDGP search operators are very efficient.
PDGP programs can be executed according to different policies depend-