Implicitly Controlling Bloat in Genetic Programming

During the evolution of solutions using genetic programming (GP) there is generally an increase in average tree size without a corresponding increase in fitness-a phenomenon commonly referred to as bloat. Although previously studied from theoretical and practical viewpoints there has been little progress in deriving controls for bloat which do not explicitly refer to tree size. Here, the use of spatial population structure in combination with local elitist replacement is shown to reduce bloat without a subsequent loss of performance. Theoretical concepts regarding inbreeding and the role of elitism are used to support the described approach. The proposed system behavior is confirmed via extensive computer simulations on benchmark problems. The main practical result is that by placing a population on a torus, with selection defined by a Moore neighborhood and local elitist replacement, bloat can be substantially reduced without compromising performance.