Efficient tree traversal to reduce code growth in tree-based genetic programming

摘要

Genetic programming is an evolutionary optimization method following the principle of program induction. Genetic programming often uses variable-length tree structures for representing candidate solutions. A serious problem with variable-length representations is code growth: during evolution these tree structures tend to grow in size without a corresponding increase in fitness. Many anti-bloat methods focus solely on size reduction and forget about fitness improvement, which is rather strange when using an "optimization" method. This paper reports the application of a semantically driven local search operator to control code growth and improve best fitness. Five examples, two theoretical benchmark applications and three real-life test problems are used to illustrate the obtained size reduction and fitness improvement. Performance of the local search operator is also compared with various other anti-bloat methods such as size and depth delimiters, an expression simplifier, linear and adaptive parsimony pressure, automatically defined functions and Tarpeian bloat control.