Genetic Programming

An increasingly popular technique is that of Genetic Programming (GP). In a standard genetic program, the representation used is a variable-sized tree of functions and values. Each leaf in the tree is a label from an available set of value labels. Each internal node in the tree is labelled from an available set of function labels. The entire tree corresponds to a single function that may be evaluated. Typically, the tree is evaluated in a left-most depth-first manner. A leaf is evaluated as the corresponding value. A function is evaluated using as arguments the result of the evaluation of its children.

Genetic algorithms and genetic programming are similar in most other aspects, except that the reproduction operators are tailored to a tree representation. The most commonly used operator is subtree crossover, in which an entire subtree is swapped between two parents (see Figure 1).

Figure 1. Subtree Crossover of Parents a) & b) to form Offspring c) & d)

In a standard genetic program, all values and functions are assumed to return the same type, although functions may vary in the number of arguments they take. This closure principle [Koza94] allows any subtree to be considered structurally on par with any other subtree, and ensures that operators such as sub-tree crossover will always produce legal offspring.

Current genetic programming applications are not limited to finding simple mathematical relationships. Ongoing research deals with areas like the modeling of inverse kinematics, navigation, and the automation of the design of complex structures.