Evolving a Search Procedure for Program Synthesis

Evolving a Search Procedure for Program Synthesis

Okoń, Michał (TU Delft Electrical Engineering, Mathematics and Computer Science)

Dumančić, S. (mentor)
Smaragdakis, G. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2022-06-23

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.

Program Synthesis
Genetic Algorithm
Search Procedures
Algorithm Selection

http://resolver.tudelft.nl/uuid:9da22502-e494-47f2-b26e-0d0bdca76500

Student theses

bachelor thesis

© 2022 Michał Okoń