- 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://hdl.handle.net/10316/8542",
-
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.",
- notes = "Supervisor: Ernesto Jorge Fernandes Costa",
