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

Abstract

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.