Genetic Programming

Genetic programming is a variation of genetic algorithms where the individuals are tree-shaped structures (trees for short) instead of flat vectors. Genetic programming is so-called because, in early demonstrations of the technique$^\ref{koza}$, the trees represented simple computer programs². However, trees can represent any hierarchal data; they do not have to represent a computer program.

Figure 2: Diagram of a tree representing Expression 1

Because mathematical expressions are hierarchal in nature, a tree is ideal for storing arbitrary single-valued mathematical expressions, For example, consider Expression 1:

$$2\sin(x+0.4)+\mathrm{arctanh}(x-1)^2$$ (1)

Fig. 2 depicts this expression graphed as a tree. Each box in the figure is called a node. The shaded nodes in Fig. 2, from which spring no subtrees, are called terminal nodes, or leaves; they can be thought of as functions with no arguments. The unshaded nodes, from which subtrees do spring, are called nonterminal nodes, or branches; they represent functions of one or more arguments. Graphed this way, one can visualize how the computer performs genetic operations on trees.

Figure 3: Diagram of a crossover operation.

Fig. 3 diagrams a crossover operation. Crossover operates on two parent trees and results in two child trees. In crossover, a node is randomly chosen in each parent tree; this node is the crossover point. Then, the parents swap subtrees at the crossover points, forming two new trees. In Fig. 3, the subtrees to be crossed are shaded. The figure depicts Expression 1 crossing with $2e^{x-4}$, where the subtrees $\mathrm{arctanh}(x-1)^2$ and $x-4$ are exchanged to yield $2\sin(x+0.4)+x-4$ and $2e^{\mathrm{arctanh}(x-1)^2}$.

Figure 4: Diagram of a mutation operation.

Fig. 4 diagrams a mutation operation. Mutation operates on only one tree. As in crossover, a random node (called the mutation point) is selected. Then, a completely random subtree replaces the subtree at the mutation point. Figure 4 shows the subtree $4/5x$ replacinh $\sin(x+0.4)$ in Expression 1, yielding $2(4/5x)+\mathrm{arctanh}(x-1)^2$.