Comparative analysis of the Metropolis-Hastings algorithm as applied to the domain of program synthesis

Comparative analysis of the Metropolis-Hastings algorithm as applied to the domain of program synthesis

van Wieringen, Victor (TU Delft Electrical Engineering, Mathematics and Computer Science)

Dumančić, S. (mentor)
Poulsen, C.B. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2022-01-28

In this research the Metropolis-Hastings algorithmis implemented for the problem of program synthesis and compared with Brute, a best-first search, together with multiple other different search algorithms. The implementation and choices of the Metrolpolis-Hastings algorithm are discussed in detail. The algorithms are tested for three different domains, each with their own associated DSL. Finally, comparisons are drawn between the search algorithms by analyzing the results of these experiments. It is found that the performance of any search algorithm depends very heavily on the specific domain and cost function used and the Metropolis-Hastings algorithm falls short in terms of performance when compared with other conventional methods.

program synthesis
Metropolis-Hastings algorithm
comparative analysis
search-based program synthesis

http://resolver.tudelft.nl/uuid:8b408583-150d-42eb-9a72-a5d69b9b7d11

Student theses

bachelor thesis

© 2022 Victor van Wieringen