6 Recombination, Mutation and Reproduction

Recombination is usually implemented as subtree crossover between two parents. The mechanics of the subtree crossover method were initially described by Cramer (1985) and Koza (1992) and have been examined in detail in a variety of studies, e.g. [D'haeseleer, 1994,Luke and Spector, 1998,Langdon, 2000b,Igel and Chellapilla, 1999,Gathercole and Ross, 1996]. The algorithm can be described as follows: Two trees are selected from the population, a subtree in each tree is selected and the two subtrees are exchanged between the trees. Either one or both children are considered for the new population. For example, consider the two binary trees with roots $+$ and $\div$,

$$\Tree [.$+$ [.\framebox{$+$}2 2 ] 2 ] \Tree [.$\div$ 1 [.\framebox{$\div$}1 1 ] ]$$

Two crossover points are chosen ( and ) and subtrees are exchanged to produce the two following trees:

$$\Tree [.$+$ [.\framebox{$\div$}1 1 ] 2 ] \Tree [.$\div$ 1 [.\framebox{$+$}2 2 ] ]$$

Subtree selection is done by assigning a uniform probability to all internal nodes and leaf nodes separately. Then, an internal node selection probability, usually set to 0.9, defines the frequency of leaves or subtrees selected for recombination. Note that, typically, as trees grow in size, the probability of selecting subtrees near the leaves grows. This is because there are more nodes in these locations, giving them a higher cumulative probability of being selected.

Since in canonical genetic programming all functions and terminals return and expect the same type, any exchange of subtrees between two trees will be valid. Many possible variations of recombination exist. For example, Homologous and Size Fair crossover [Langdon, 2000b] attempt to preserve tree structures and the size of exchanged subtrees. Other operators are described in [Langdon, 1998a].

Subtree crossover tends to be the dominant operator in genetic programming, while mutation operators are often used at lower rates. Subtree mutation was investigated in comparison with subtree crossover in [Luke and Spector, 1998]. Other forms of mutation include single-node mutations and various forms of code-editing to remove unnecessary code from trees. The reproduction operator copies an individual from one population into the next.

The production and selection of new individuals is carried out in a generational or steady-state algorithm. In a generational algorithm, a new population is created from parents in the current population. In a steady-state algorithm, one offspring is created and placed into the existing population, either randomly or based on fitness. The comma and plus methods for offspring and parent selection used in evolutionary strategies are also possible, see Section 2.2. Other examples of offspring production force children to compete amongst themselves, such as brood selection [Altenberg, 1994,Tackett, 1994], or use methods based on similarity to bias toward similar or dissimilar parents, such as disassortative mating [Ryan, 1994].