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

Bachelor thesis (2022)

Authors

V.J. van Wieringen Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - EEMCS (mentor)
C.B. Poulsen Programming Languages - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Victor van Wieringen
More Info
expand_more

Published Date

28-01-2022

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.