www.gp-field-guide.org.uk
Contents Top Previous Next

5.4 Other Techniques

GP can be hybridised with other techniques. For example, Iba, de Garis, and Sato (1994), Nikolaev and Iba (2006), and ? 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 Section  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 (Olsson1995), hill climbing (O'Reilly and Oppacher1994a), and simulated annealing (O'Reilly1996?). As discussed in Chapter  8 , it is also possible to extend Estimation of Distribution Algorithms (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 applications of co-evolution in GP, including (Azaria and Sipper2005aBrameier, Haan, Krings, and MacCallum2006Buason, Bergfeldt, and Ziemke2005Channon2006Dolinsky, Jenkinson, and Colquhoun2007Funes, Sklar, Juille, and Pollack1998aGagné and Parizeau2007Hillis1992Hornby and Pollack2001Mendes, de B. Voznika, Nievola, and Freitas2001Piaseczny, Suzuki, and Sawai2004Schmidt and Lipson2006Sharabi and Sipper2006Soule2003Soule and Komireddy2006Spector2002Spector and Klein2006Spector, Klein, Perry, and Feinstein2005b??).

Finally, it is worth mentioning that program trees can be manipulated with editing operations (Koza1992). 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 Tsang20062007) prune branches and combine branches from different trees.


www.gp-field-guide.org.uk
Contents Top Previous Next