Iterative genetic improvement: scaling stochastic program synthesis

DOI10.1016/J.ARTINT.2023.103962arXiv2202.13040MaRDI QIDQ6136101FDOQ6136101

Authors:

Publication date: 28 August 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: Program synthesis aims to {it automatically} find programs from an underlying programming language that satisfy a given specification. While this has the potential to revolutionize computing, how to search over the vast space of programs efficiently is an unsolved challenge in program synthesis. In cases where large programs are required for a solution, it is generally believed that {it stochastic} search has advantages over other classes of search techniques. Unfortunately, existing stochastic program synthesizers do not meet this expectation very well, suffering from the scalability issue. Here we propose a new framework for stochastic program synthesis, called iterative genetic improvement to overcome this problem, a technique inspired by the practice of the software development process. The key idea of iterative genetic improvement is to apply genetic improvement to improve a current reference program, and then iteratively replace the reference program by the best program found. Compared to traditional stochastic synthesis approaches, iterative genetic improvement can build up the complexity of programs incrementally in a more robust way. We evaluate the approach on two program synthesis domains: list manipulation and string transformation. Our empirical results indicate that this method has considerable advantages over several representative stochastic program synthesizer techniques, both in terms of scalability and of solution quality.

Full work available at URL: https://arxiv.org/abs/2202.13040

zbMATH Keywords

artificial intelligenceevolutionary computationgenetic programmingprogram synthesisgenetic improvement

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic local search. Foundations and applications.
• Linear Genetic Programming
• Title not available (Why is that?)
• A Deductive Approach to Program Synthesis
• Programming by examples
• Program synthesis using deduction-guided reinforcement learning
• Scaling Enumerative Program Synthesis via Divide and Conquer
• From program verification to program synthesis
• Automating string processing in spreadsheets using input-output examples

Cited In (2)

• Program reversals for evolutions with non-uniform step costs
• Artificial Evolution

This page was built for publication: Iterative genetic improvement: scaling stochastic program synthesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136101)