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 language | English (US) |
---|---|
Title of host publication | GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery, Inc |
Pages | 937-944 |
Number of pages | 8 |
ISBN (Electronic) | 9781450349208 |
DOIs | |
State | Published - Jul 1 2017 |
Event | 2017 Genetic and Evolutionary Computation Conference, GECCO 2017 - Berlin, Germany Duration: Jul 15 2017 → Jul 19 2017 |
Publication series
Name | GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | 2017 Genetic and Evolutionary Computation Conference, GECCO 2017 |
---|---|
Country/Territory | Germany |
City | Berlin |
Period | 7/15/17 → 7/19/17 |
Bibliographical note
Publisher Copyright:© 2017 ACM.
Keywords
- Automatic simplification
- Generalization
- Genetic programming
- Overfitting
- Push