# Probabilistic Lexicase Selection

arXiv: https://arxiv.org/abs/2305.11681 · HTML: https://mlsanity.com/paper/2305.11681/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 19 May 2023.

## Builds on (most cited first, 16 of 16)

- [Contemporary Symbolic Regression Methods and their Relative Performance](https://mlsanity.com/paper/2107.14351/) (2021)
- [Learning concise representations for regression by evolving networks of trees](https://mlsanity.com/paper/1807.00981/) (2018)
- [Epsilon-Lexicase Selection for Regression](https://mlsanity.com/paper/1905.13266/) (2019)
- [Lexicase selection in Learning Classifier Systems](https://mlsanity.com/paper/1907.04736/) (2019)
- [Problem-solving benefits of down-sampled lexicase selection](https://mlsanity.com/paper/2106.06085/) (2021)
- [Evolutionary Quantum Architecture Search for Parametrized Quantum Circuits](https://mlsanity.com/paper/2208.11167/) (2022)
- [Genetic programming approaches to learning fair classifiers](https://mlsanity.com/paper/2004.13282/) (2020)
- [Lexicase Selection at Scale](https://mlsanity.com/paper/2208.10719/) (2022)
- [Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving](https://mlsanity.com/paper/2301.01488/) (2023)
- [Lexicase Selection of Specialists](https://mlsanity.com/paper/1905.09372/) (2019)
- [Code Building Genetic Programming](https://mlsanity.com/paper/2008.03649/) (2020)
- [Evolving Neural Selection with Adaptive Regularization](https://mlsanity.com/paper/2204.01662/) (2022)
- [Batch Tournament Selection for Genetic Programming](https://mlsanity.com/paper/1904.08658/) (2019)
- [Calculating lexicase selection probabilities is NP-Hard](https://mlsanity.com/paper/2301.06724/) (2023)
- [Population Diversity Leads to Short Running Times of Lexicase Selection](https://mlsanity.com/paper/2204.06461/) (2022)
- [Functional Code Building Genetic Programming](https://mlsanity.com/paper/2206.04561/) (2022)

## Built on by (most cited first, 3 of 3)

- [Pareto-Optimal Learning from Preferences with Hidden Context](https://mlsanity.com/paper/2406.15599/) (2024)
- [Particularity](https://mlsanity.com/paper/2306.06812/) (2023)
- [DALex: Lexicase-like Selection via Diverse Aggregation](https://mlsanity.com/paper/2401.12424/) (2024)

## Abstract (arXiv)

Lexicase selection is a widely used parent selection algorithm in genetic programming, known for its success in various task domains such as program synthesis, symbolic regression, and machine learning. Due to its non-parametric and recursive nature, calculating the probability of each individual being selected by lexicase selection has been proven to be an NP-hard problem, which discourages deeper theoretical understanding and practical improvements to the algorithm. In this work, we introduce probabilistic lexicase selection (plexicase selection), a novel parent selection algorithm that efficiently approximates the probability distribution of lexicase selection. Our method not only demonstrates superior problem-solving capabilities as a semantic-aware selection method, but also benefits from having a probabilistic representation of the selection process for enhanced efficiency and flexibility. Experiments are conducted in two prevalent domains in genetic programming: program synthesis and symbolic regression, using standard benchmarks including PSB and SRBench. The empirical results show that plexicase selection achieves state-of-the-art problem-solving performance that is competitive to the lexicase selection, and significantly outperforms lexicase selection in computation efficiency.