Contents Top Previous Next

5.3 GP Crossover

During biological sexual reproduction, the genetic material from both mother and father is combined in such a way that genes in the child are in approximately the same position as they were in its parents. This is quite different from traditional tree-based GP crossover, which can move a subtree to a totally different position in the tree structure.

Crossover operators that tend to preserve the position of genetic material are called homologous, and several notions of homologous crossover have been proposed for GP. It is fairly straightforward to realise homologous crossover when using linear representations, and homologous operators are widely used in linear GP (cf. Figure  7.4 , page  155 ) (Defoin Platel, Clergue, and Collard2003Francone, Conrads, Banzhaf, and Nordin1999Hansen2003Hansen, Lowry, Meservy, and McDonald2007Nordin, Banzhaf, and Francone1999O'Neill, Ryan, Keijzer, and Cattolico2003). Various forms of homologous crossover have also been proposed for tree-based GP (Collet2007Langdon2000Lones2003MacCallum2003?).

The oldest homologous crossover in tree-based GP is one-point crossover ( Langdon and Poli2002Poli and Langdon19971998a). This works by selecting a common crossover point in the parent programs and then swapping the corresponding subtrees. To allow for the two parents having different shapes, one-point crossover analyses the two trees from the root nodes and selects the crossover point only from the parts of the two trees in the common region (see Figure  5.1 ). In the common region, the parents have the same shape.1 The common region is related to homology, in the sense that the common region represents the result of a matching process between parent trees. Within the common region between two parent trees, the transfer of homologous primitives can happen like it does in a linear bit string genetic algorithm.


Figure 5.1: Example of one-point crossover between parents of different sizes and shapes.

Uniform crossover for trees (Poli and Langdon1998b) works (in the common region) like uniform crossover in GAs. That is, the offspring are created by visiting the nodes in the common region and flipping a coin at each locus to decide whether the corresponding offspring node should be picked from the first or the second parent. If a node to be inherited belongs to the base of the common region and is a function, then the subtree rooted there is inherited as well. With this form of crossover, there can be a greater mixing of the code near the root than with other operators.

In context-preserving crossover (D'haeseleer1994), the crossover points are constrained to have the same coordinates, like in one-point crossover. Note that the crossover points are not limited to the common region.

In size-fair crossover (Langdon1999a2000) the first crossover point is selected randomly, as with standard crossover. Then the size of the subtree to be removed from the first parent is calculated. This is used to constrain the choice of the second crossover point so as to guarantee that the subtree excised from the second parent will not be "unfairly" big.

Harries and Smith (1997) suggested five new crossover operators that are like standard crossover but with probabilistic restrictions on the depth of crossover points within the parent trees.

Since crossover and mutation are specific to the representation used in GP, each new representation tends to need new crossover and mutation operators. For example "ripple crossover" (O'Neill et al.2003) is a way of looking at crossover in grammatical evolution (Section  6.2.3 page  127 ). As we shall see in Chapter  7 , specific crossover operators exist for linear GP (Section  7.1 ) and graph based GP systems (Section  7.2 ), such as PDGP (page  156 ), PADO (page  159 ) and Cartesian GP (page  160 ).

Contents Top Previous Next