We have generalised existing explanations for the widely observed growth in GP program size with successive generations (bloat) to give a simple statistical argument which should be generally applicable both to GP and other systems using discrete variable length representations and static evaluation functions. Briefly, in general simple static evaluation functions quickly drive search to converge, in the sense of concentrating the search on trial solutions with the same fitness as previously found trial solutions. In general variable length allows many more long representations of a given solution than short ones of the same solution. Thus (in the absence of a parsimony bias) we expect longer representations to occur more often and so representation length to tend to increase. That is fitness based selection leads to bloat.
In Sections 3, 4 and 5 we have taken a typical GP problem and demonstrated with fitness selection it suffers from bloat whereas without selection it does not. We have demonstrated that if fitness selection is removed, there is a slight bias in common GP crossover (caused by the practical requirement to limit bloat) which causes a slow reduction in program size. NB fitness causes bloat in spite of a small crossover bias in favour of parsimony. Detailed measurement of crossover confirms after an extended period of evolution, most crossovers are not disruptive (i.e. most children have the same fitness as their parents). It also shows children with the same fitness as their parents are on average consistently longer than them.
In Section 5.1.1 we apply Price's Theorem for the first time to program lengths within GP populations. We confirm experimentally that it fits GP populations unless restrictions on program size have significant impact. We used Price's Theorem to prove fitness selection is required for a change in average representation length. In Section 6 we discussed
the circumstances in which we need to control bloat and current mechanisms which do control it but suggest a way forward may be to consider more complex dynamic fitness functions.