Knowledge-Driven Program Synthesis via Adaptive Replacement Mutation and Auto-constructed Subprogram Archives

We introduce Knowledge-Driven Program Synthesis (KDPS) as a variant of the program synthesis task that requires the agent to solve a sequence of program synthesis problems. In KDPS, the agent should use knowledge from the earlier problems to solve the later ones. We propose a novel method based on PushGP to solve the KDPS problem, which takes subprograms as knowledge. The proposed method extracts subprograms from the solution of previously solved problems by the Even Partitioning (EP) method and uses these subprograms to solve the upcoming programming task using Adaptive Replacement Mutation (ARM). We call this method $\text{PushGP}+\text{EP}+\text{ARM}$. With $\text{PushGP}+\text{EP}+\text{ARM}$, no human effort is required in the knowledge extraction and utilization processes. We compare the proposed method with PushGP, as well as a method using subprograms manually extracted by a human. Our $\text{PushGP}+\text{EP}+\text{ARM}$ achieves better train error, success count, and faster convergence than PushGP. Additionally, we demonstrate the superiority of PushGP+EP+ARM when consecutively solving a sequence of six program synthesis problems.

• Publication year

  2022

• Venue

  IEEE Symposium Series on Computational Intelligence

• Publication date

  2022-09-08

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/SSCI51031.2022.10022128arXiv 2209.03736
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Incorporating sub-programs as knowledge in program synthesis by PushGP and adaptive replacement mutation

  2022influential reference
• Evolution through Large Models

  2022cited by this paper
• Evolving modular soft robots without explicit inter-module communication using local self-attention

  2022cited by this paper
• Getting a Head Start on Program Synthesis with Genetic Programming

  2021cited by this paper
• Explaining and Exploiting the Advantages of Down-sampled Lexicase Selection

  2020cited by this paper
• Genetic Source Sensitivity and Transfer Learning in Genetic Programming

  2020cited by this paper
• On domain knowledge and novelty to improve program synthesis performance with grammatical evolution

  2019influential reference
• Improving Genetic Programming with Novel Exploration - Exploitation Control

  2019cited by this paper
• Teaching GP to program like a human software developer: using perplexity pressure to guide program synthesis approaches

  2019cited by this paper
• Automatic programming: The open issue?

  2019cited by this paper
• Extending Program Synthesis Grammars for Grammar-Guided Genetic Programming

  2018cited by this paper
• Program synthesis using uniform mutation by addition and deletion

  2018influential reference
• PyshGP: PushGP in Python

  2017cited by this paper
• General Program Synthesis Benchmark Suite

  2015influential reference
• Grammatical evolution

  2010cited by this paper
• JADE: Adaptive Differential Evolution With Optional External Archive

  2009cited by this paper
• Autoconstructive Evolution: Push, PushGP, and Pushpop

  2001cited by this paper
• Genetic Programming: On the Programming of Computers by Means of Natural Selection

  1992cited by this paper

• No citing papers are available for this paper.