Controlling bloating using depth constraint crossover

We develop a simple modification of crossover called depth constraint crossover to control bloating. As the name suggests, depth constraint crossover adds a depth constraint on the selection of crossover point. This method is motivated by the analysis of removal bias bloating theory. In this paper, we quantitatively define removal bias as the depth difference between swapped subtrees in crossover. Experiments show that the removal bias defined can be widely observed in GP problems and it is strongly correlated to the growth of population size. We find that by limiting the maximum depth difference between subtrees swapped in crossover with depth constraint crossover, it is possible to greatly reduce the removal bias and hence effectively control bloating. To analyze the efficiency of depth constraint crossover, we compare the technique with koza-style depth limiting method on four different problem domains. Experiment results show that the new technique are very effective in controlling bloating while still maintaining fitness.