Improving generalization of evolved programs through automatic simplification

Thomas Helmuth, Edward Pantridge, Nicholas Freitag McPhee, Lee Spector

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

46 Scopus citations

Abstract

Programs evolved by genetic programming unfortunately often do not generalize to unseen data. Reliable synthesis of programs that generalize to unseen data is therefore an important open problem. We present evidence that smaller programs evolved using the PushGP system tend to generalize better over a range of program synthesis problems. Like in many genetic programming systems, programs evolved by PushGP usually have pieces that can be removed without changing the behavior of the program. We describe methods for automatically simplifying evolved programs to make them smaller and potentially improve their generalization. We present five simplification methods and analyze their strengths and weaknesses on a suite of general program synthesis benchmark problems. All of our methods use a straightforward hill-climbing procedure to remove pieces of a program while ensuring that the resulting program gives the same errors on the training data as did the original program. We show that automatic simpliication, previously used both for post-run analysis and as a genetic operator, can significantly improve the generalization rates of evolved programs.

Original languageEnglish (US)
Title of host publicationGECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages937-944
Number of pages8
ISBN (Electronic)9781450349208
DOIs
StatePublished - Jul 1 2017
Event2017 Genetic and Evolutionary Computation Conference, GECCO 2017 - Berlin, Germany
Duration: Jul 15 2017Jul 19 2017

Publication series

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

Conference

Conference2017 Genetic and Evolutionary Computation Conference, GECCO 2017
Country/TerritoryGermany
CityBerlin
Period7/15/177/19/17

Bibliographical note

Publisher Copyright:
© 2017 ACM.

Keywords

  • Automatic simplification
  • Generalization
  • Genetic programming
  • Overfitting
  • Push

Fingerprint

Dive into the research topics of 'Improving generalization of evolved programs through automatic simplification'. Together they form a unique fingerprint.

Cite this