next up previous contents
Next: 8 Summary Up: 5 Genetic Lineages and Previous: 6 Analysis of Results   Contents

7 Discussion of Sampling

How does one search for computer programs, and how does one know if one program is better than another? The intuitive broad sampling of a complex solution space by a population in genetic programming is one reason why the algorithm may be considered useful. Early work by Cramer (1985) and Koza (1992) laid the foundations for this procedural representation, where the use of single-value scalars as fitness combined and complex representations were already in use in other evolutionary algorithm domains. While it may have been straightforward to apply these methods to program evolution for genetic programming, the conflicts arising in this representation are well documented [Daida et al., 2001,O'Reilly, 1998,Daida et al., 2003b,O'Reilly and Goldberg, 1998]. The results presented here, based on the sampling of unique tree shapes and unique behaviours, further describe genetic programming's ability to sample a complex solution space.

The behaviour definition has enriched the description of the sampling of solutions by genetic programming. In the Ant problem, the geographic distribution of food pellets on the Ant trail may allow for many Ant behaviours that are able to collect 20 to 24 pellets, but unable to easily collect more. In this problem, the standard definition of fitness creates deception [Langdon and Poli, 2002] that has already been shown to negatively impair fitness improvement. However, the more gradual decrease in the ability to sample different behaviours of higher fitness explains why genetic programming often outperforms hill-climbing methods that search with poor solutions. The peaks of behaviours sampled at size 20 and 24 may represent local optima that trap search.

Figure 5.12: 95% confidence bars for the average cumulative structure and behaviour sampling distributions. From left to right is the Ant, Parity and Regression problems with structure on top and behaviour below.
The behaviour distribution for the Parity problem is particularly interesting as it shows the ability of genetic programming to sample many different near-random type behaviours. Sampling such high numbers of different behaviours is promising but a likely cause of deception and negative contextual shifts of subtrees, explaining why hill-climbing and elitist strategies are more effective on this problem [O'Reilly and Oppacher, 1994,Juels and Wattenberg, 1995].

While the Regression problem used a behaviour that did not directly reflect its fitness value, the behaviour did reflect the complexity of solutions. The preference toward sampling behaviours of a small size and complexity could be caused by neutrality in the fitness values or the result of a biased structure sampling. In the latter case, the inability to increase structure size is hypothesized to be positively correlated with the inability to increase the complexity of solutions. This hypothesis seems plausible for the Regression domain, considering that subtree crossover typically functions near the leaves (terminals).

With respect to the sampling of unique structures of various sizes, all problems showed that while genetic programming is predisposed to code growth (and bloat), unique tree shapes of large sizes are sampled less. That is, a fewer number of big tree shapes are sampled. Remember that the number of different programs for a given tree shape increases exponentially with an increase in size. Thus, while fewer large and unique tree shapes are being sampled, the algorithm could be sampling more different programs of those shapes. The different structures of the same size that are sampled more frequently would appear to be attractive to genetic programming for one reason or another. The depth limit imposed here and the mechanics of subtree crossover are also possible causes.

Poli and McPhee (2001) examined the distributions of a variable-length linear genomes using standard crossover and a flat landscape. The authors found that the distribution of genome lengths sampled during search resembled a gamma distribution and that shorter genomes were sampled much more than longer ones. With respect to the results presented here, when the non-cumulative version of Figures 5.9 to 5.11 are examined, the distribution of unique tree shapes sampled in the Ant and Regression experiments also resembles a gamma distribution. While it is less clear for the Parity experiments, additional analysis into these distributions would provide further support of the results presented in [Poli and McPhee, 2001].

These results also suggest several possibilities to improve performance. The sizes of behaviours that were sampled in high numbers may represent areas of deception in the fitness space. This deception may be reduced by pressuring the search away from areas of neutral fitness. Previous research showing a positive correlation between high fitness-based diversity with good fitness could be the result of avoided deception leading to better fitness. Thus, when a population contains many different but equal in fitness behaviours, we may wish to move the search toward a less deceptive region of the search space. Leading the ant to follow a specific food trail reduced deception and improved fitness [Langdon and Poli, 2002]. For the Regression domain, using a component of complexity in the fitness function may also improve the performance of genetic programming. Similarly, the Parity fitness function could be amended to reflect which instances a solution solves correctly to reduce deception. Of course, exploration (global search) and exploitation (local search) ability will be affected when such methods are employed to reduce deception.

next up previous contents
Next: 8 Summary Up: 5 Genetic Lineages and Previous: 6 Analysis of Results   Contents
S Gustafson 2004-05-20