In an evolutionary algorithm, a scalar value is typically used to define a solution's behaviour (although multiobjective methods may use a vector). This value, defined by a fitness function, must be able to distinguish different degrees of solution quality. This coarseness often leads to deception, as in the Artificial Ant problem [Langdon and Poli, 2002], or fails to identify solutions that are relatively good in the current population but extremely poor to continue a search with, as in the case of very small solutions in Regression problems. Thus, measuring the sampling of behaviours during a run using only the fitness value may not be as informative as one would like, and so problem specific definitions of behaviour are used, defined as follows:
In this section, the tracking of sampled structures is performed by considering the binary tree shapes regardless of tree content. The number of unique tree shapes of each size that are sampled during the run of the algorithm are counted.
A canonical genetic programming system is run for 51 generations, using a generational algorithm with a population size of 500. Initial tree creation is carried out using ramped half-n-half with tree sizes between depths 2 and 4. Subtree crossover, with internal node selection set at 90% probability and maximum depth of 10, is used for recombination - no mutation or duplication is used. There are 30 random runs collected for each problem domain.
The results for each problem domain are depicted in two graphs showing the average number of unique tree shapes sampled and unique behaviours sampled of a given size. Each line represents the cumulative total of unique tree shapes (or behaviours) in each generation during a run. Each successive ten generations are highlighted with symbols. Thus, the space between two lines represents the number of new unique tree shapes (or behaviours) of a given size that were sampled in a generation. The larger the space, the more effort genetic programming spends on searching unique tree shapes (or behaviours) of that size.