Page 58 - 49A Field Guide to Genetic Programming

44 5 Alternative Initialisations and Operators in Tree-based GP

affects all constants in an individual where “a numerical partial gra-
dient ascent is achieved to reach the nearest local optimum”. Finally,
Sharman, Esparcia Alcazar, and Li (1995) used simulated annealing to
update numerical values (which represented signal amplification gains)
within individuals.

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 ma-
terial are called homologous, and several notions of homologous crossover
have been proposed for GP. It is fairly straightforward to realise homolo-
gous crossover when using linear representations, and homologous operators
are widely used in linear GP (cf. Figure 7.4, page 65) (Defoin Platel, Clergue,
and Collard, 2003; Francone, Conrads, Banzhaf, and Nordin, 1999; Hansen,
2003; Hansen, Lowry, Meservy, and McDonald, 2007; Nordin, Banzhaf, and
Francone, 1999; O’Neill, Ryan, Keijzer, and Cattolico, 2003). Various forms
of homologous crossover have also been proposed for tree-based GP (Col-
let, 2007; Langdon, 2000; Lones, 2003; MacCallum, 2003; Yamamoto and
Tschudin, 2005).
The oldest homologous crossover in tree-based GP is one-point crossover
(Langdon and Poli, 2002; Poli and Langdon, 1997, 1998a). This works by se-
lecting 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.
Uniform crossover for trees (Poli and Langdon, 1998b) 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
1 Nodes in the common region need not be identical but they must have the same
arity. That is, they must both be leaves or both be functions with the same number of
inputs.