Program synthesis using uniform mutation by addition and deletion

Thomas Helmuth, Nicholas Freitag McPhee, Lee Spector

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

Abstract

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 rst 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 dierent locations. We nd that UMAD, with relatively high rates of addition and deletion, results in signicant 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.

Original languageEnglish (US)
Title of host publicationGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages1127-1134
Number of pages8
ISBN (Electronic)9781450356183
DOIs
StatePublished - Jul 2 2018
Event2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan
Duration: Jul 15 2018Jul 19 2018

Publication series

NameGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

Other

Other2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Country/TerritoryJapan
CityKyoto
Period7/15/187/19/18

Bibliographical note

Funding Information:
Thanks to the members of the Hampshire College Computational Intelligence Lab and Shawn Saliyev at the University of Minnesota, Morris for discussions that helped shape this work, and to Josiah Erikson for systems support. This material is based upon work supported by the National Science Foundation under Grant No. 1617087. Any opinions, ndings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reect the views of the National Science Foundation.

Publisher Copyright:
© 2018 Copyright held by the owner/author(s).

Keywords

  • Genetic operators
  • Mutation
  • Program synthesis
  • Push

Fingerprint

Dive into the research topics of 'Program synthesis using uniform mutation by addition and deletion'. Together they form a unique fingerprint.

Cite this