1 Problems and Measures

The same three problems from earlier in this chapter (from the control experiments) are used in the following empirical study. However, in the following study, problem specific measures of solution behaviour are used.

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:

• Ant: each food item is uniquely labeled to create a vector representing the order in which the food is collected,
• Parity: a vector of integer values, where the size is the total classified correctly and the contents indicate which of the $2^5$ test cases were correctly classified,
• Regression: a vector of integer values represents the angles between test points (from the horizontal) taken by a solution.

These definitions capture more information than their typical scalar value fitness would, but are still a reduction of the complete behaviour of a solution. The Ant behaviour represents the unique sequence of food collection, where the largest sequence is 89 and the smallest is 0. The Parity behaviour describes which specific instances are correctly classified. The definition of behaviour for the Regression domain describes the change in angle from the horizontal between each function point in the candidate solution. By casting these angles as integers, when two successive angles in the vector are identical, only the first is kept. Thus, the size of the vector alludes to the complexity of the solution (the number of ``bends'' in the graph of that function), but not directly to the fitness value as the target function is not considered. Figure 5.8 highlights the differences between the standard fitness function and the definition of behaviour proposed here.

Figure 5.8: Behaviour definition example for the Regression domain, with standard fitness calculation (mean squared error) and the behaviour definition.

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.

Figure 5.9: Ant results, cumulative sampling of unique structures and behaviours.

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.