Facilitating Function Application in Code Building Genetic Programming
Thomas Helmuth, Jayden Fedoroff, Edward Pantridge, Lee C. Spector · Proceedings of the Genetic and Evolutionary Computation Conference · 2024
Code Building Genetic Programming (CBGP) is a method for general inductive program synthesis that uses a genetic algorithm and a formal type system to evolve linear genomes that are compiled into type-safe programs in a host language. Prior work showed that CBGP can evolve programs that use arbitrary abstractions from existing codebases along with higher-order functions and polymorphism. In tests on benchmark problems, however, the problem solving capabilities of CBGP have been mixed. One hypothesized explanation for weak performance on some problems is that many functions encountered during the compilation process are typically not applied. Here we propose two modifications to the compilation algorithm, both of which make it more likely that functions will be applied when composing programs. The first modification changes how frequently CBGP attempts to perform function application, while the second allows the construction of function applications to backtrack. While both modifications increase solution rates on benchmark problems, the backtracking modification shows more promise with a modest increase in computational cost and no additional configuration requirements. We argue that this modification should be considered the new standard compilation algorithm for CBGP systems.