Intron Detection and Pruning. In [60] Xxxxxxx proposes to replace the standard fitness measures gener- ally used with evolutionary algorithms with static analysis methods: by us- ing static analysis techniques it should be possible to evaluate an individ- ual’s behaviour across the entire input space instead of a limited number of test cases. However, for data classification replacing the fitness measure with static analysis techniques does not seem feasible due to the high dimensional nature of the search space. Instead of replacing the fitness function with static analysis methods, Keijzer [63] showed that static analysis can also be used as a pre-processing step for fitness evaluations. By using interval arithmetic to calculate the bounds of regression trees, functions containing undefined values are either deleted or assigned the worst possible performance value. We will use a combination of static analysis techniques and (semantic) pruning to detect and remove introns from our top-down atomic decision trees in order to address the problem caused by gp introns. A schematic overview of the gp intron detection and pruning process can be seen in Figure 5.1 where the black nodes indicate an intron subtree and xxx xxxx node indicates an intron node. After a new individual is created, either as a result of initialization or as the result of recombination and mutation of its parent(s), it is usually evaluated in order to determine its fitness. In our case we first scan the individual for the different types of introns using static analysis, resulting in an individual in which the different types of introns are marked. Depending on the types of introns the individual is pruned into a more condensed decision tree which is semantically the same as the original individual. The condensed decision tree is then used to evaluate the individual. Additionally, we will use the condensed trees in our fitness cache. This should improve the effectiveness of the cache as several syntactically different decision trees have the same condensed form. For the evolutionary process (e.g., crossover and mutation) as well as the tree size fitness measure we will still use the original top-down atomic trees so that the classification performance of our algorithms remains the same as without intron detection and pruning. The approach described above is related to several code-editing tech- niques [69, Section 11.6]. In [13] Xxxxxxxx and Banzhaf distinguish two types of introns in their Linear Genetic Programming (L...
