A Study of Good Predecessor Programs for Reducing Fitness Evaluation Cost in Genetic Programming

Good predecessor programs (GPPs) are the ancestors of the best program found in a genetic programming (GP) evolution. This paper reports on an investigation into GPPs with the ultimate goal of reducing fitness evaluation cost in tree-based GP systems. A framework is developed for gathering information about GPPs and a series of experiments is conducted on a symbolic regression problem, a binary classification problem, and a multi-class classification program with increasing levels of difficulty in different domains. The analysis of the data shows that during evolution, GPPs typically constitute less than 33% of the total programs evaluated, and may constitute less than 5%. The analysis results further shows that in all evaluated programs, the proportion of GPPs is reduced by increasing tournament size and to a less extent, affected by population size. Problem difficulty seems to have no clear influence on the proportion of GPPs.