Evolving a Search Procedure for Program Synthesis
M.T. Okoń (TU Delft - Electrical Engineering, Mathematics and Computer Science)
S. Dumančić – Mentor (TU Delft - Algorithmics)
G. Smaragdakis – Graduation committee member (TU Delft - Cyber Security)
More Info
expand_more
Other 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
In recent months, researchers developed several new search procedures to augment the process of program synthesis. While many of them performed better than their predecessors, the proposed solutions are still far from ideal. One possible way of overcoming the shortcomings of single search methods is employing genetic algorithms, which have been proven useful in many tasks of similar scale. This paper aims to answer the question of whether it is possible to utilize that sort of algorithms to find an efficient combination of search procedures in a program synthesis problem. An implementation of a genetic algorithm is proposed with parameters and operators chosen through a literature study and a series of experiments on three different domains. To outline different approaches to program synthesis, two fitness functions are examined. Finally, evolved search procedures are discussed and compared with the already existing solutions. One of them in particular, namely a combination of Brute and A* algorithms, manages to surpass their singular counterparts in certain cases.