Single parent genetic programming

The most controversial part of genetic programming is its highly disruptive and potentially innovative subtree crossover operator. The clearest problem with the crossover operator is its potential to induce defensive meta-selection for large parse trees, a process usually termed "bloat." Single parent genetic programming is a form of genetic programming in which bloat is reduced by doing subtree crossover with a fixed population of ancestor trees. Analysis of mean tree size growth demonstrates that this fixed and limited set of crossover partners provides implicit, automatic control on tree size in the evolving population, reducing the need for additionally disruptive trimming of large trees. The choice of ancestor trees can also incorporate expert knowledge into the genetic programming system. The system is tested on four problems: plus-one-recall-store (PORS), odd parity, plus-times-half (PTH) and a bioinformatics model fitting problem (NIPs). The effectiveness of the technique varies with the problem and choice of ancestor set. At the extremes, improvements in time to solution in excess of 4700-fold were observed for the PORS problem, and no significant improvements for the PTH problem were observed.