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


Authors: Huayang Xie, Mengjie Zhang, Peter Andreae
Source: GZipped PostScript (54kb); Adobe PDF (154kb)


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 between 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.

Keywords: Fitness evaluation, good predecessor programs, population clustering

[Up to Computer Science Technical Report Archive: Home Page]