Page 60 - 49A Field Guide to Genetic Programming

46 5 Alternative Initialisations and Operators in Tree-based GP

As we shall see in Chapter 7, specific crossover operators exist for lin-
ear GP (Section 7.1) and graph based GP systems (Section 7.2), such as
PDGP (page 65), PADO (page 67) and Cartesian GP (page 67).

5.4 Other Techniques

GP can be hybridised with other techniques. For example, Iba, de Garis, and
Sato (1994), Nikolaev and Iba (2006), and Zhang and M¨uhlenbein (1995)
have incorporated information theoretic and minimum description length
ideas into GP fitness functions to provide a degree of regularisation and
so avoid over-fitting (and bloat, see Section 11.3). As mentioned in Sec-
tion 6.2.3, computer language grammars can be incorporated into GP.
Whereas genetic programming typically uses an evolutionary algorithm
to search the space of computer programs, various other heuristic search
methods can also be applied to program search, including: enumeration
(Olsson, 1995), hill climbing (O’Reilly and Oppacher, 1994a), and simu-
lated annealing (O’Reilly, 1996; Tsoulos and Lagaris, 2006). As discussed
in Chapter 8, it is also possible to extend Estimation of Distribution Algo-
rithms (EDAs) to the variable size representations used in GP.
Another alternative is to use co-evolution with multiple populations,
where the fitness of individuals in one population depends on the behaviour
of individuals in other populations. There have been many successful appli-
cations of co-evolution in GP, including (Azaria and Sipper, 2005a; Brameier,
Haan, Krings, and MacCallum, 2006; Buason, Bergfeldt, and Ziemke, 2005;
Channon, 2006; Dolinsky, Jenkinson, and Colquhoun, 2007; Funes, Sklar,
Juille, and Pollack, 1998a; Gagn´e and Parizeau, 2007; Hillis, 1992; Hornby
and Pollack, 2001; Mendes, de B. Voznika, Nievola, and Freitas, 2001; Pi-
aseczny, Suzuki, and Sawai, 2004; Schmidt and Lipson, 2006; Sharabi and
Sipper, 2006; Soule, 2003; Soule and Komireddy, 2006; Spector, 2002; Spec-
tor and Klein, 2006; Spector, Klein, Perry, and Feinstein, 2005b; Wilson and
Heywood, 2007; Zhang and Cho, 1999).
Finally, it is worth mentioning that program trees can be manipulated
with editing operations (Koza, 1992). For example, if the root node of
a subtree is × but one of its arguments is always guaranteed to evaluate
to 0, then we can replace the subtree rooted there with the terminal 0.
If the root node of a subtree is + and one argument evaluates to 0, we
can replace the subtree with the other argument of the +. Editing can
reduce the complexity of evolved solutions and can make them easier to
understand. However, it may also lead to GP getting stuck in local optima,
so editing operations should probably be used sparingly at run time. Other
reorganisation operations of various types are also possible. For example,
after trees are generated by GP, (Garcia-Almanza and Tsang, 2006, 2007)
prune branches and combine branches from different trees.