Controlling Bloat: Individual and Population Based Approaches in Genetic Programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.2031
@PhdThesis{silva:thesis,
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
Silva}",
keywords = "genetic algorithms, genetic programming, bloat",
URL = "
http://cisuc.dei.uc.pt/ecos/dlfile.php?fn=1749_pub_phdsara.pdf",
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