Effects of lexicase and tournament selection on diversity recovery and maintenance

Thomas Helmuth, Nicholas Freitag McPhee, Lee Spector

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

23 Scopus citations

Abstract

In genetic programming systems, parent selection algorithms select the programs from which offspring will be produced by random variation and recombination. While most parent selection algorithms select programs on the basis of aggregate performance on multiple test cases, the lexicase selection algorithm considers each test case individually, in random order, for each parent selection event. Prior work has shown that lexicase selection can produce both more diverse populations and more solutions when applied to several hard problems. Here we examine the effects of lexicase selection, compared to those of the more traditional tournament selection algorithm, on population error diversity using two program synthesis problems. We conduct experiments in which the same initial population is used to start multiple runs, each using a different random number seed. The initial populations are extracted from genetic programming runs, and fall into three categories: high diversity populations, low diversity populations, and populations that occur after diversity crashes. The reported data shows that lexicase selection can maintain high error diversity and also that it can re-diversify less-diverse populations, while tournament selection consistently produces lower diversity.

Original languageEnglish (US)
Title of host publicationGECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsTobias Friedrich
PublisherAssociation for Computing Machinery, Inc
Pages983-990
Number of pages8
ISBN (Electronic)9781450343237
DOIs
StatePublished - Jul 20 2016
Event2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion - Denver, United States
Duration: Jul 20 2016Jul 24 2016

Publication series

NameGECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

Other

Other2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion
Country/TerritoryUnited States
CityDenver
Period7/20/167/24/16

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grants No. 1129139 and 1331283.

Publisher Copyright:
© 2016 ACM.

Keywords

  • Diversity
  • Hyperselection
  • Lexicase selection
  • Pushgp
  • Tournament selection

Fingerprint

Dive into the research topics of 'Effects of lexicase and tournament selection on diversity recovery and maintenance'. Together they form a unique fingerprint.

Cite this