Controlling Bloat: Individual and Population Based Approaches in Genetic Programming

Authors

Abstract

Genetic Programming (GP) is the automated learning of computer programs. Basically a search process, it is capable of solving complex problems by evolving populations of computer programs, using Darwinian evolution and Mendelian genetics as inspiration. Theoretically, GP can solve any problem whose candidate solutions can be measured and compared, making it a widely applicable technique. Furthermore, the solutions found by GP are usually provided in a format that users can understand and modify to their needs. But its high versatility is also the cause of some difficulties. The search space of GP is virtually unlimited and programs tend to grow in size during the evolutionary process. Code growth is a healthy result of genetic operators in search of better solutions, but it also permits the appearance of pieces of redundant code that increase the size of programs without improving their fitness. Besides consuming precious time in an already computationally intensive process, redundant code may start growing rapidly, a phenomenon known as bloat. Bloat can be defined as an excess of code growth without a corresponding improvement in fitness. This is a serious problem in GP, often leading to the stagnation of the evolutionary process. Although many bloat control methods have been proposed so far, a definitive solution is yet to be found.

This thesis provides a comprehensive description of all the bloat theories proposed so far, and a detailed taxonomy of available bloat control methods. Then it proposes two novel bloat control approaches, Dynamic Limits and Resource-Limited GP, both implemented on the GPLAB software package, also developed in the context of this thesis. Dynamic Limits restricts the size or depth allowed at the individual level, while Resource-Limited GP imposes restrictions only at the population level, regardless of the particularities of the individuals within. Four different problems were used as a benchmark to study the efficiency of both Dynamic Limits and Resource-Limited GP. They represent a varied selection of problems in terms of bloat dynamics and response to different bloat control techniques: Symbolic Regression of the quartic polynomial, Artificial Ant on the Santa Fe food trail, 5-Bit Even Parity, and 11-Bit Boolean Multiplexer. The results of exhaustive experiments have shown that, although Dynamic Limits was a more efficient bloat control method than Resource-Limited GP across the set of problems studied, both approaches successfully performed the task they were designed to. Without adding any parameters to the search process, it was possible to match the performance of some of the best state-of-the-art methods available so far.

Keywords

genetic programming, bloat, dynamic limits, limited resources

Subject

Genetic Programming

PhD Thesis

Controlling Bloat: Individual and Population Based Approaches in Genetic Programming, April 2008

PDF File