Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving

Created by W.Langdon from gp-bibliography.bib Revision:1.8129

@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",
• year = "2024",
• volume = "32",
• number = "4",
• pages = "307--337",
• month = "Winter",
• 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