An Exploration of Exploration: Measuring the Ability of Lexicase Selection to Find Obscure Pathways to Optimality

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

@InProceedings{Guadalupe-Hernandez:2021:GPTP,

• author = "Jose {Guadalupe Hernandez} and Alex Lalejini and Charles Ofria",
• title = "An Exploration of Exploration: Measuring the Ability of Lexicase Selection to Find Obscure Pathways to Optimality",
• booktitle = "Genetic Programming Theory and Practice XVIII",
• year = "2021",
• editor = "Wolfgang Banzhaf and Leonardo Trujillo and Stephan Winkler and Bill Worzel",
• series = "Genetic and Evolutionary Computation",
• pages = "83--107",
• address = "East Lansing, USA",
• month = "19-21 " # may,
• publisher = "Springer",
• keywords = "genetic algorithms, genetic programming, lexicase selection",
• isbn13 = "978-981-16-8112-7",
• DOI = "doi:10.1007/978-981-16-8113-4_5",
• abstract = "Parent selection algorithms (selection schemes) steer populations through a problems search space, often trading off between exploitation and exploration. Understanding how selection schemes affect exploitation and exploration within a search space is crucial to tackling increasingly challenging problems. Here, we introduce an exploration diagnostic that diagnoses a selection schemes capacity for search space exploration. We use our exploration diagnostic to investigate the exploratory capacity of lexicase selection and several of its variants: epsilon lexicase, down-sampled lexicase, cohort lexicase, and novelty-lexicase. We verify that lexicase selection out-explores tournament selection, and we show that lexicase selection exploratory capacity can be sensitive to the ratio between population size and the number of test cases used for evaluating candidate solutions. Additionally, we find that relaxing lexicase elitism with epsilon lexicase can further improve exploration. Both down-sampling and cohort lexicase, two techniques for applying random subsampling to test cases, degrade lexicases exploratory capacity; however, we find that cohort partitioning better preserves lexicase exploratory capacity than down-sampling. Finally, we find evidence that novelty-lexicase addition of novelty test cases can degrade lexicase capacity for exploration. Overall, our findings provide hypotheses for further exploration and actionable insights and recommendations for using lexicase selection. Additionally, this work demonstrates the value of selection scheme diagnostics as a complement to more conventional benchmarking approaches to selection scheme analysis.",
• notes = "Part of \cite{Banzhaf:2021:GPTP} published after the workshop in 2022",

}

Genetic Programming entries for Jose Guadalupe Hernandez Alexander Lalejini Charles Ofria

Citations