Contents Top Previous Next

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 ( 1996a1999a) proposed parallel distributed GP (PDGP), a form of GP that is suitable for the evolution of highly parallel programs which effectively reuse partial results. Programs are represented in PDGP as graphs with nodes representing functions and terminals. Edges represent both control flow and data flow. The possible efficiency gains obtained by a graph representation are illustrated in Figure  7.5 .

(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.

In the simplest form of PDGP edges are directed and unlabelled, in which case PDGP is a generalisation of standard GP. However, more complex representations can be used, which allow the evolution of: programs, including standard tree-like programs, logic networks, neural networks, recurrent 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 automaton, 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 depending 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 directed graphs of nodes. Each node can have multiple outgoing arcs that indicate possible flows of control. Each node has two main parts: an action and a branch-decision. Each program has an argument stack and all PADO actions pop their inputs from this argument stack and push their result back onto the argument stack. The actions are drawn from a primitive set including the standard algebraic operations, minimum, maximum, negation, 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 ( Miller1999Miller and Smith2006), programs are represented by linear chromosomes containing integers. These are divided 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 primitive 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 chromosomes 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 the graph. Also, traditionally Cartesian GP has always used mutation as its main search operation, while PDGP used both crossover and mutation. However, recently a new crossover has been proposed for Cartesian GP that provides faster convergence (Clegg, Walker, and Miller2007).

7.2.4 Evolving Parallel Programs using Indirect

The graph-based systems discussed above use representations which directly encode parallel programs. However, it is also possible to use non-graph-based GP to evolve parallel programs. For example, Bennett ( 1996) used a parallel virtual machine in which several standard tree-like programs (called "agents") would have their nodes executed in parallel. He included a two-stage mechanism which simulated parallelism of sensing actions and simple conflict resolution (prioritisation) for actions with side effects. Andre, Bennett, and Koza (1996) used GP to discover rules for cellular automata, a highly parallel computational architecture, which could solve large majority-classification problems. In conjunction with an interpreter implementing a parallel virtual machine, GP can also be used to translate sequential programs into parallel ones (?), or to develop parallel programs.

Contents Top Previous Next