Page 81 - 49A Field Guide to Genetic Programming

7.2 Graph-Based Genetic Programming 67

ing on whether instructions with side effects are used or not. If there are
no side effects, running a PDGP program can be seen as a propagation of
the input values from the bottom to the top of the program’s graph (as in
a feed-forward artificial neural network or data flow parallel computer).

7.2.2 Parallel Algorithm Discovery and Orchestration
In a system called parallel algorithm discovery and orchestration (PADO),
Teller (1996) used a combination of GP and linear discrimination to obtain
parallel classification programs for signals and images.
PADO programs include three parts: a main loop, some ADFs and an
indexed memory. The main loop is repeatedly executed for a fixed amount
of time. When the time is up, PADO programs are forced to halt by some
external control structure. The output of a program is the weighted average
of the outputs produced at each iteration of the loop. The weights are
proportional to the iteration count, so that more recent outputs count more.
The main loop and the ADFs in PADO are structured as arbitrary di-
rected graphs of nodes. Each node can have multiple outgoing arcs that
indicate possible flows of control. Each node has two main parts: an ac-
tion and a branch-decision. Each program has an argument stack and all
PADO actions pop their inputs from this argument stack and push their re-
sult back onto the argument stack. The actions are drawn from a primitive
set including the standard algebraic operations, minimum, maximum, nega-
tion, read from indexed memory, write to indexed memory, deterministic
and non-deterministic branching instructions, and primitives related to the
task of classifying images. The evaluation of PADO programs starts from a
designated node. After the execution of each node, control is passed to the
node chosen by the branch-decision function of the current node.

7.2.3 Cartesian GP

In Miller’s Cartesian GP (Miller, 1999; Miller and Smith, 2006), programs
are represented by linear chromosomes containing integers. These are di-
vided into groups of three or four. Each group corresponds to a position in
a 2-D array. One integer in each group defines the primitive (e.g., an AND
gate) at that location in the array. Other integers in the group define the
locations (coordinates) in the genome from which the inputs for that primi-
tive should be drawn. Each primitive does not itself define where its output
is used; this is done by later primitives. A primitive’s output may be used
more than once, or indeed not used at all, depending on the way in which
the other functions’ inputs are specified. Thus, Cartesian GP’s chromo-
somes represent graph-like programs, which is very similar to PDGP. The
main difference between the two systems is that Cartesian GP operators act
at the level of the linear chromosome, while in PDGP they act directly on