B.Sc. Thesis: Viktor Nikolas Pfanschilling on Self-Programming Mutation and Crossover in Genetic Programming for Code Generation

Supervisors: Elmar Rückert, Prof. Dr. Jan Peters

Finished: 22.Oktober.2017

Abstract

In Genetic programming, the genetic operators mutation and crossover are defined by the developer in order to produce a system that automatically generates computer code, usually incorporating information about the target language as well as about the problem. The genetic operators are a critical design decision because they control the evolution of genomes. This thesis outlines a way of eliminating that design decision by parameterizing genetic operators as part of the genome. In doing so, we discovered that several measures are necessary to accommodate the lack of assumptions that can be made about genomes. Among these measures are the introduction of an ancestry tree of genomes as additional bookkeeping to enable backtracking, the employment of a method for selection of candidates from that structure and the manual implementation of the first genome.
In our experiments, we discovered that -when uncompensated for- our approach will tend to bloat the genome extremely and distort our metrics. The cause of this was that individuals changed their own code to better fit the way their code generator works. We were able to solve this though, by employing only crossover, thus shifting the responsibility of improvement solely on the code generator’s behavior. Our variant of crossover passes one genome’s code to another genomes mutation function. We also discovered that the exact implementation of the initial genome is extremely important and seemingly inconsequential changes like removing a few lines of dead code make a huge difference. The results show that our current setup is still insufficient but demonstrates that our measures are effective.

Thesis

Self-Programming Mutation and Crossover in Genetic Programming for Code Generation