DEPTH AND SIZE LIMITS

In this last experimental section we present an experiment on the quintic symbolic regression problem (parameters as [Langdon2000]). This shows we can approximately predict when depth and size limits commonly used in GP will have an impact on the evolving population. This is so early that we anticipate these limits usually have an effect. Depth limits will tend to cause bushier solutions to be produced. Bushier trees are more likely to solve some problems (e.g. the parity problems) than random trees [Langdon1999b]. Hence a depth limit could have an unanticipated benefit. Conceivably there are problems when the bias introduced by a size limit could be helpful. However [,] show when the whole population presses against size or depth limits, they constrain subtree crossover possibly resulting in premature convergence.

Using the average depth of the initial population and rate of increase in depth from [Langdon2000, Table 4] we can estimate how long it will take for bloat to take the population on average to the depth limit (17). $\Delta\mbox{gens}=(17-3.64)/1.2=12$.

Figure 10 plots the mean sizes and depths for: no limits, a conventional depth limit (17) and a size limit of 200. They lie almost on top of each other until the fourth tick mark (corresponding to generation 12). Co-incidentally this is also the point where the size limited population diverges from the unlimited population. Given the variability between runs, the agreement between the prediction and measurements is surprisingly good.

Figure: 10 Evolution of population size and depth in a run of the quintic regression problem. Standard deviations shown every 5 generations.