Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving
- Publikationstyp:
- Zeitschriftenaufsatz
- Metadaten:
-
- Abstract
- <jats:title>Abstract</jats:title> <jats:p>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.</jats:p>
- Autoren
- Ryan Boldi
- Martin Briesch
- Dominik Sobania
- Alexander Lalejini
- Thomas Helmuth
- Franz Rothlauf
- Charles Ofria
- Lee Spector
- DOI
- 10.1162/evco_a_00346
- eISSN
- 1530-9304
- Zeitschrift
- Evolutionary Computation
- Sprache
- en
- Online publication date
- 2024
- Paginierung
- 1 - 31
- Status
- Published online
- Herausgeber
- MIT Press
- Herausgeber URL
- http://dx.doi.org/10.1162/evco_a_00346
- Datum der Datenerfassung
- 2024
- Titel
- Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving
Datenquelle: Crossref
- Andere Metadatenquellen:
-
- 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 amount 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.
- Addresses
- University of Massachusetts, Amherst, MA 01003, USA rbahlousbold@umass.edu.
- Autoren
- Ryan Boldi
- Martin Briesch
- Dominik Sobania
- Alexander Lalejini
- Thomas Helmuth
- Franz Rothlauf
- Charles Ofria
- Lee Spector
- DOI
- 10.1162/evco_a_00346
- eISSN
- 1530-9304
- Externe Identifier
- PubMed Identifier: 38271633
- Open access
- false
- ISSN
- 1063-6560
- Zeitschrift
- Evolutionary computation
- Sprache
- eng
- Medium
- Print-Electronic
- Online publication date
- 2024
- Paginierung
- 1 - 32
- Datum der Veröffentlichung
- 2024
- Status
- Published
- Datum der Datenerfassung
- 2024
- Titel
- Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving.
- Sub types
- Journal Article
Datenquelle: Europe PubMed Central
- 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 amount 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.
- Autoren
- Ryan Boldi
- Martin Briesch
- Dominik Sobania
- Alexander Lalejini
- Thomas Helmuth
- Franz Rothlauf
- Charles Ofria
- Lee Spector
- Autoren-URL
- https://www.ncbi.nlm.nih.gov/pubmed/38271633
- DOI
- 10.1162/evco_a_00346
- eISSN
- 1530-9304
- Zeitschrift
- Evol Comput
- Schlüsselwörter
- Genetic programming
- informed down-sampling
- lexicase selection
- Sprache
- eng
- Country
- United States
- Paginierung
- 1 - 32
- PII
- 119216
- Datum der Veröffentlichung
- 2024
- Status
- Published online
- Titel
- Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving.
- Sub types
- Journal Article
Datenquelle: PubMed
- Beziehungen:
- Eigentum von