Program synthesis using uniform mutation by addition and deletion

By Thomas Helmuth, Nicholas Freitag McPhee, Lee Spector. 2018

65 citations recorded by the source corpus.

Most genetic programming systems use mutation and crossover operators to create child programs from selected parent programs. Typically the mutation operator will replace a randomly chosen subprogram in the parent with a new, randomly generated subprogram. In systems with linear genomes, a uniform mutation operator can be used that has some probability of replacing any particular gene with a new, randomly chosen gene. In this paper, we present a new uniform mutation operator called Uniform Mutation by Addition and Deletion (UMAD), which first adds genes with some probability before or after every existing gene, and then deletes random genes from the resulting genome. In UMAD it is not necessary that the new genes replace old genes, as the additions and deletions can occur in different locations. We find that UMAD, with relatively high rates of addition and deletion, results in significant increases in problem-solving performance on a range of program synthesis benchmark problems. In our experiments, we compare this method to a variety of alternatives, showing that it equals or outperforms all of them. We explore this new mutation operator and other well-performing high-rate mutation schemes to determine what traits are crucial to improved performance.

Subfields: Artificial Intelligence, Computer Science Applications, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Quoc V. Le
  2. Hanxiao Liu
  3. Zihang Dai
  4. Jianfeng Gao
  5. Mohit Bansal
  6. David R. So
  7. Luke S. Zettlemoyer
  8. Noam Shazeer

In Code Generation & Program Synthesis

  1. Quoc V. Le

Citations in the corpus