Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving
Created by W.Langdon from
gp-bibliography.bib Revision:1.8098
- @Article{Boldi:ECJ,
-
author = "Ryan Boldi and Martin Briesch and Dominik Sobania and
Alexander Lalejini and Thomas Helmuth and
Franz Rothlauf and Charles Ofria and Lee Spector",
-
title = "Informed Down-Sampled Lexicase Selection: Identifying
Productive Training Cases for Efficient Problem
Solving",
-
journal = "Evolutionary Computation",
-
note = "Online Early",
-
keywords = "genetic algorithms, genetic programming, lexicase
selection, informed down-sampling",
-
ISSN = "1063-6560",
-
URL = "https://arxiv.org/abs/2301.01488",
-
URL = "https://doi.org/10.1162/evco_a_00346",
-
eprint = "https://direct.mit.edu/evco/article-pdf/doi/10.1162/evco_a_00346/2352336/evco_a_00346.pdf",
-
DOI = "doi:10.1162/evco_a_00346",
-
abstract = "Genetic Programming (GP) often uses large training
sets and requires all individuals to be evaluated on
all training cases during selection. Random
down-sampled lexicase selection evaluates individuals
on only a random subset of the training cases, allowing
for more individuals to be explored with the same
number of program executions. However, sampling
randomly can exclude important cases from the
down-sample for a number of generations, while cases
that measure the same behavior (synonymous cases) may
be overused. In this work, we introduce Informed
Down-Sampled Lexicase Selection. This method leverages
population statistics to build down-samples that
contain more distinct and therefore informative
training cases. Through an empirical investigation
across two different GP systems (PushGP and
Grammar-Guided GP), we find that informed down-sampling
significantly outperforms random down-sampling on a set
of contemporary program synthesis benchmark problems.
Through an analysis of the created down-samples, we
find that important training cases are included in the
down-sample consistently across independent
evolutionary runs and systems. We hypothesize that this
improvement can be attributed to the ability of
Informed Down-Sampled Lexicase Selection to maintain
more specialist individuals over the course of
evolution, while still benefiting from reduced
per-evaluation costs.",
-
notes = "boldi2024informeddownsampledlexicaseselection
University of Massachusetts, Amherst, MA 01003, USA",
- }
Genetic Programming entries for
Ryan Boldi
Martin Briesch
Dominik Sobania
Alexander Lalejini
Thomas Helmuth
Franz Rothlauf
Charles Ofria
Lee Spector
Citations