Probabilistic Lexicase Selection
Li Ding Edward Pantridge Lee Spector
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.