Problem-Solving Benefits of Down-Sampled Lexicase Selection
Created by W.Langdon from
gp-bibliography.bib Revision:1.8010
- @Article{Helmuth:2022:ALife,
-
author = "Thomas Helmuth and Lee Spector",
-
title = "Problem-Solving Benefits of Down-Sampled {Lexicase}
Selection",
-
journal = "Artificial Life",
-
year = "2021",
-
volume = "27",
-
number = "3-4",
-
pages = "183--203",
-
month = "Summer-Fall",
-
note = "Special issue highlights from the 2020 Conference on
Artificial Life",
-
keywords = "genetic algorithms, genetic programming, parent
selection, lexicase selection, down-sampled lexicase
selection, program synthesis",
-
ISSN = "1064-5462",
-
URL = "https://direct.mit.edu/artl/article-pdf/doi/10.1162/artl_a_00341/1960075/artl_a_00341.pdf",
-
DOI = "doi:10.1162/artl_a_00341",
-
size = "21 pages",
-
abstract = "In genetic programming, an evolutionary method for
producing computer programs that solve specified
computational problems, parent selection is ordinarily
based on aggregate measures of performance across an
entire training set. Lexicase selection, by contrast,
selects on the basis of performance on random sequences
of training cases; this has been shown to enhance
problem-solving power in many circumstances. Lexicase
selection can also be seen as better reflecting
biological evolution, by modeling sequences of
challenges that organisms face over their lifetimes.
Recent work has demonstrated that the advantages of
lexicase selection can be amplified by down-sampling,
meaning that only a random subsample of the training
cases is used each generation. This can be seen as
modeling the fact that individual organisms encounter
only subsets of the possible environments and that
environments change over time. Here we provide the most
extensive benchmarking of down-sampled lexicase
selection to date, showing that its benefits hold up to
increased scrutiny. The reasons that down-sampling
helps, however, are not yet fully understood.
Hypotheses include that down-sampling allows for more
generations to be processed with the same budget of
program evaluations; that the variation of training
data across generations acts as a changing environment,
encouraging adaptation; or that it reduces overfitting,
leading to more general solutions. We systematically
evaluate these hypotheses, finding evidence against all
three, and instead draw the conclusion that
down-sampled lexicase selection's main benefit stems
from the fact that it allows the evolutionary process
to examine more individuals within the same
computational budget, even though each individual is
examined less completely.",
-
notes = "Also known as \cite{10.1162/artl_a_00341} Published
March 2022",
- }
Genetic Programming entries for
Thomas Helmuth
Lee Spector
Citations