Comparative analysis of the Metropolis-Hastings algorithm as applied to the domain of program synthesis
V.J. van Wieringen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
S. Dumancic – Mentor (TU Delft - Algorithmics)
Casper Bach Poulsen – Graduation committee member (TU Delft - Programming Languages)
More Info
expand_more
Link to the custom codebase that was implemented and used
https://github.com/victorvwier/BEP_project_synthesisOther 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 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.