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

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

Rasing, Stef (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

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 of the same com- plexity, also when less or more complexity is needed. Also, best-first search falls into local optima easily. In this paper, I describe Vlute, an IPS system using Large Neighborhood Search (LNS), in which a solution is gradually improved by exploring neighboring solutions, and Variable-Depth Invent (VDI), in which instruction complexity is increased dynami- cally. Vlute is tested on three IPS domains (robot-planning, string transformations, and drawing ASCII-art). Results show that using VDI improves Vlute’s performance only for string transformation. Vlute can outperform Brute and escape local optima encountered by Brute also only for string transforma- tion. A limitation of Vlute is finding large programs.

Program Synthesis
Inductive Program Synthesis
Very Large Neighborhood Search
Large Neighborhood Search
Variable-Depth Neighborhood Search

http://resolver.tudelft.nl/uuid:a24ed4f6-6abd-4661-86b8-c5a965d62e4e

https://github.com/victorvwier/BEP_project_synthesis.git Branch with my last changes: "brute_extend_invent"

Student theses

bachelor thesis

© 2022 Stef Rasing