Page 79 - 49A Field Guide to Genetic Programming

7.2 Graph-Based Genetic Programming 65

Parent 1

Parent 2

Offspring
Figure 7.3: Typical linear GP crossover. Two instructions are randomly
chosen in each parent (top two genomes) as cut points. The code fragment
excised from the first parent is then replaced with the code fragment excised
from the second to generate the child (lower chromosome).

Parent 1

Parent 2

Offspring 1

Offspring 2

Figure 7.4: Discipulus’s “homologous” crossover (Foster, 2001; Francone
et al., 1999; Nordin et al., 1999). Crossover is performed on two parents (top
two programs) to yield two offspring (bottom). The two crossover points are
the same in both parents, so the exised code does not change its position
relative to the start of the program (left edge), and the child programs have
the same lengths as their parents. Homologous crossover is often combined
with a small amount of normal two point crossover (Figure 7.3) to introduce
length changes into the GP population.

7.2 Graph-Based Genetic Programming

Trees are special types of graphs. So it is natural to ask what would happen
if one extended GP so as to be able to evolve graph-like programs. Starting
from the mid 1990s, researchers have proposed several extensions of GP that
do just that, albeit in different ways.

7.2.1 Parallel Distributed GP

Poli (1996a, 1999a) proposed parallel distributed GP (PDGP), a form of GP
that is suitable for the evolution of highly parallel programs which effec-
tively reuse partial results. Programs are represented in PDGP as graphs