Towards scalable genetic programming

Genetic programming (GP) is a technique for automatically solving optimization problems where candidate solutions are expressible as trees with no human intervention. We propose an extension of GP, termed scalable genetic programming, which solves problems parameterized by a scalable difficulty parameter. We first define a taxonomy of evolutionary computation (EC) systems that identifies variability dimensions and levels for EC systems. We define an algorithm, the scientist algorithm, which uses genetic programming as a subroutine to reliably make progress on scalable problems. The scientist algorithm uses a toolkit of provided routines to progress, by carrying out experiments to determine the value of different methods. We define several of the tools for this toolkit. We define and implement an algorithm for systematically considering all small trees for a problem. We then use these small trees in an iterative algorithm to define subroutines that improve performance on a problem under study. Using this algorithm, we beat the best known performance on the artificial ant on the Santa Fe trail problem by a factor of 7.

As science depends on accurate hypothesis testing to make progress, we perform a comparison and evaluation of statistical techniques used to evaluate evolutionary computation systems. Finding many of these wanting, with the exception of computational effort, we introduce two additional techniques, effective mean best fitness and the y-test. We also perform an extensive analysis of the computational effort, and identify some statistical cautions around the use of this key statistic. We provide an algorithm that carefully uses computational effort to determine the best values of population size and generation number for an EC treatment.

Finally, we identify several components that are of use with the scientist algorithm. We treat the use of multiobjective algorithms in GP, principal components analysis, and their combination. We demonstrate this by providing and testing an algorithm that makes evolved trees parsimonious. We introduce the notion of incremental evolution, and use it to make useful subroutines automatically from successful solutions to easy problems. We then use this to demonstrate scalable genetic programming on an integer sorting problem.