Evolving a Search Procedure for Program Synthesis

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.