Towards an Information Theoretic Framework for Genetic Programming

An information—theoretic framework is presented for the development and analysis of the ensemble learning approach of genetic programming. As evolution proceeds, this approach suggests that the mutual information between the target and models should: (i) not decrease in the population; (ii) concentrate in fewer individuals; and (iii) be “distilled” from the inputs, eliminating excess entropy. Normalized information theoretic indices are developed to measure fitness and diversity of ensembles, without

a priori

knowledge of how the multiple constituent models might be composed into a single model. With the use of these indices for reproductive and survival selection, building blocks are less likely to be lost and more likely to be recombined. Price's Theorem is generalized to pair selection and rewritten to show key factors related to heritability and evolvability. Heritability of information should be stronger than that of error, improving evolvability. We support these arguments with simulations using a logic function benchmark and a time series application. For a chaotic time series prediction problem, for instance, the proposed approach avoids familiar difficulties (premature convergence, deception, poor scaling, and early loss of needed building blocks) with standard GP symbolic regression systems; informationbased fitness functions showed strong intergenerational correlations as required by Price's Theorem.