Genetic Algorithms for Inductive Program Synthesis
M.R. Tromp (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Sebastijan Dumančić – Mentor (TU Delft - Algorithmics)
M. Molenaar – Graduation committee member (TU Delft - Computer Graphics and Visualisation)
More Info
expand_more
GitHub repository containing the received codebase and all implemented alternatives.
https://github.com/MarijeTromp/BEP_How_To_Train_Your_DragonOther than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
VanillaGP is an Inductive Program Synthesis algorithm that takes a Genetic Algorithm (GA) approach by using its 3 components: selection, mutation, and crossover. Many different alternatives exist for these components and although this is not the only application of a GAs on the Program Synthesis domain, it has not been extensively evaluated what the effects of using these different alternatives or combinations of them are. We explored this by evaluating the performance of multiple alternatives per component and comparing the results of combinations of these alternatives to VanillaGP. These evaluations were done on 3 IPS domains: robot, ASCII art, and strings. From these evaluations we conclude that Stochastic Universal Sampling combined with Queen Bee Crossover and an altered version of One Mutation Per Solution performs best on the string domain, and Down-Sampled Lexicase Selection combined with Three Parent Crossover and the same altered version of OMPS performs best on the other domains.