Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving
Evolutionary Computation · 2024
DOI: 10.1162/evco_a_00346 ↗Kurz gefasst
Fachartikel in der Zeitschrift Evolutionary Computation, 2024. Verfasst von Ryan Boldi und 7 weiteren Autor:innen. Beteiligte Einrichtung: University of Massachusetts, Amherst, MA 01003, USA rbahlousbold@umass.edu. Hauptthemen laut MEDLINE: Problem Solving. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 59 Literaturangaben.
Abstract (Originalsprache)
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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- University of Massachusetts, Amherst, MA 01003, USA rbahlousbold@umass.edu.
- Johannes Gutenberg University, Mainz, 55128, Germany briesch@uni-mainz.de.
- Johannes Gutenberg University, Mainz, 55128, Germany dsobania@uni-mainz.de.
- Grand Valley State University, Allendale, MI 49401, USA lalejina@gvsu.edu.
- Hamilton College, Clinton, NY, 13323, USA thelmuth@hamilton.edu.
- Johannes Gutenberg University, Mainz, 55128, Germany rothlauf@uni-mainz.de.
ORCID-Profile: Ryan Boldi, Martin Briesch, Dominik Sobania, Alexander Lalejini, Thomas Helmuth, Franz Rothlauf, Charles Ofria, Lee Spector
Zitieren
APA
Boldi, R., Briesch, M., Sobania, D., Lalejini, A., Helmuth, T., Rothlauf, F., Ofria, C., & Spector, L. (2024). Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving. Evolutionary Computation. https://doi.org/10.1162/evco_a_00346
Vancouver
Boldi R, Briesch M, Sobania D, Lalejini A, Helmuth T, Rothlauf F, et al. Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving. Evolutionary Computation. 2024. doi:10.1162/evco_a_00346
BibTeX
@article{Boldi2024,
author = {Boldi, Ryan and Briesch, Martin and Sobania, Dominik and Lalejini, Alexander and Helmuth, Thomas and Rothlauf, Franz and Ofria, Charles and Spector, Lee},
title = {Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving},
journal = {Evolutionary Computation},
year = {2024},
doi = {10.1162/evco_a_00346}
}
EUVIMED