Improving Inductive Program Synthesis by using Very Large Neighborhood Search and Variable-Depth Neighborhood Search

Brute, A state-of-the-art inductive program synthesis (IPS) system, introduced a two-phase algorithm; first, complex pro- gram instructions are invented from basic instructions. Sec- ond, a best-first search algorithm finds a sequence of invented instructions to solve an IPS task. This method is limited because invented instructions are always...

VanillaGP: Genetic Algorithm for Inductive Program Synthesis

Inductive Program Synthesis is the problem of generating programs from<br/>a set of input-output examples. Since it can be reduced to the search problem in the space of programs, many search algorithms have been successfully<br/>applied to it over the years. This paper proposes, develops, and analyses<br/>a novel algorithm in the family of...

Evolving a Domain-Specific Language to Speed Up Program Synthesis

Program synthesis is used in various ways to automate repetitive tasks or to generate software automatically. Search-based program synthesis constitutes searching the space of candidate programs created from a given language. However, this form of program synthesis is very expensive in terms of computing power. By optimising the synthesiser’s...

Genetic Algorithms for Inductive Program Synthesis

VanillaGP is an Inductive Program Synthesis algorithm that takes a Genetic Algorithm (GA) approach by using its 3 components: selection, mutation, and crossover. Many different alternatives exist for these components and although this is not the only application of a GAs on the Program Synthesis domain, it has not been extensively evaluated what...

Inductive Program Synthesis through using Monte Carlo Tree Search guided by a heuristic-based loss function

Recently, a new and promising Inductive Program Synthesis (IPS) system, Brute, showed the potential of using a heuristic-based loss function. However, Brute also has its limitations and struggles with escaping local optima. The Monte Carlo Tree Search might offer a solution to this problem since it balances between exploitation and exploration....

Improvements in Monte Carlo Tree Search for Inductive Program Synthesis

A recent development in program synthesis is using Monte Carlo Tree Search to traverse the search tree of possible programs in order to efficiently find a program that will successfully transform the given input to the desired output. Previous research has shown promising results as Monte Carlo Tree Search is able to escape local optima that...

Program Synthesis with A*

Search based synthesis has emerged as a powerful tool in program synthesis, the process of automatically generating implementations for software programs given some form of semantic specification. Search based synthesis involves a search over the space of candidate programs that can be derived from a given grammar. A recently developed new...