Accurate Replication in Genetic Programming

One characteristic tendency of genetic programming is the production of considerably larger trees than expected. It has been suggested that this is related to the ability of individuals to replicate accurately. In this paper we present theoretical analysis which shows that, for certain specific cases, the pressure for accurate replication induces an increase in tree size. In particular, we show that among fit individuals, larger trees are more likely to yield semantically equivalent children via the crossover operator, leading to an overall increase in the average size of fit individuals. This is followed by experimental results consistent with our analysis. We also include the results of experiments where the expected growth in tree size was not observed, suggesting that this phenomenon, while common, is not universal. 1 Introduction In The Selfish Gene [Dawkins 1976], Richard Dawkins argues that, over the course of evolutionary time, replicators in a population tend to increase in f..