Controlling Bloat: Individual and Population Based Approaches in Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Sara Silva",
  title =        "Controlling Bloat: Individual and Population Based
                 Approaches in Genetic Programming",
  school =       "Coimbra University",
  year =         "2008",
  address =      "Portugal",
  month =        apr,
  note =         "Full author name is Sara Guilherme Oliveira {da
  keywords =     "genetic algorithms, genetic programming, bloat",
  URL =          "",
  isbn13 =       "978-989-20-1137-0",
  size =         "165 pages",
  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.",

Genetic Programming entries for Sara Silva