Recent Developments in Program Synthesis with Evolutionary Algorithms
- URL: http://arxiv.org/abs/2108.12227v1
- Date: Fri, 27 Aug 2021 11:38:27 GMT
- Title: Recent Developments in Program Synthesis with Evolutionary Algorithms
- Authors: Dominik Sobania, Dirk Schweim, Franz Rothlauf
- Abstract summary: We identify the relevant evolutionary program synthesis approaches and provide an in-depth analysis of their performance.
The most influential approaches we identify are stack-based, grammar-guided, as well as linear genetic programming.
For future work, we encourage researchers not only to use a program's output for assessing the quality of a solution but also the way towards a solution.
- Score: 1.8047694351309207
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The automatic generation of computer programs is one of the main applications
with practical relevance in the field of evolutionary computation. With program
synthesis techniques not only software developers could be supported in their
everyday work but even users without any programming knowledge could be
empowered to automate repetitive tasks and implement their own new
functionality. In recent years, many novel program synthesis approaches based
on evolutionary algorithms have been proposed and evaluated on common benchmark
problems. Therefore, we identify in this work the relevant evolutionary program
synthesis approaches and provide an in-depth analysis of their performance. The
most influential approaches we identify are stack-based, grammar-guided, as
well as linear genetic programming. Further, we find that these approaches
perform well on benchmark problems if there is a simple mapping from the given
input to the correct output. On problems where this mapping is complex, e.g.,
if the problem consists of several sub-problems or requires iteration/recursion
for a correct solution, results tend to be worse. Consequently, for future
work, we encourage researchers not only to use a program's output for assessing
the quality of a solution but also the way towards a solution (e.g., correctly
solved sub-problems).
Related papers
- Searching Latent Program Spaces [0.0]
We propose an algorithm for program induction that learns a distribution over latent programs in a continuous space, enabling efficient search and test-time adaptation.
We show that can generalize beyond its training distribution and adapt to unseen tasks by utilizing test-time adaptation mechanisms.
arXiv Detail & Related papers (2024-11-13T15:50:32Z) - Genetic-based Constraint Programming for Resource Constrained Job
Scheduling [5.068093754585243]
Resource constrained job scheduling is a hard computation optimisation problem that originates in the mining industry.
Off-the-shelf solutions cannot solve this problem satisfactorily in reasonable timeframes.
This paper proposes a genetic programming algorithm to discover efficient search strategies of constraint programming.
arXiv Detail & Related papers (2024-02-01T09:57:38Z) - ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
We characterize several different forms of compositional generalization that are desirable in program synthesis.
We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
arXiv Detail & Related papers (2023-07-26T01:07:52Z) - Synthesizing a Progression of Subtasks for Block-Based Visual
Programming Tasks [21.33708484899808]
We propose a novel synthesis algorithm that generates a progression of subtasks that are high-quality, well-spaced in terms of their complexity.
We show the utility of our synthesis algorithm in improving the efficacy of AI agents for solving tasks in the Karel programming environment.
arXiv Detail & Related papers (2023-05-27T16:24:36Z) - Iterative Genetic Improvement: Scaling Stochastic Program Synthesis [11.195558777385259]
Program synthesis aims to it automatically find programs from an underlying programming language that satisfy a given specification.
Existing program synthesis techniques do not meet this expectation very well, suffering from the scalability issue.
Here we propose a new framework for program synthesis, called iterative genetic improvement to overcome this problem.
arXiv Detail & Related papers (2022-02-26T02:00:35Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric.
We show that in practice, automated search can find substantial improvements to the initial program.
arXiv Detail & Related papers (2021-09-14T20:52:55Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together.
The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively.
Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
arXiv Detail & Related papers (2021-03-10T03:16:12Z) - BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
We present a new synthesis approach that leverages learning to guide a bottom-up search over programs.
In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a set of input-output examples.
We show that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches.
arXiv Detail & Related papers (2020-07-28T17:46:18Z) - Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction.
By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes.
arXiv Detail & Related papers (2020-07-07T17:03:02Z) - Creating Synthetic Datasets via Evolution for Neural Program Synthesis [77.34726150561087]
We show that some program synthesis approaches generalize poorly to data distributions different from that of the randomly generated examples.
We propose a new, adversarial approach to control the bias of synthetic data distributions and show that it outperforms current approaches.
arXiv Detail & Related papers (2020-03-23T18:34:15Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.