Probabilistic Lexicase Selection
This addresses a computational bottleneck for researchers and practitioners in genetic programming, enabling deeper theoretical insights and practical enhancements in domains like program synthesis and symbolic regression, though it is an incremental improvement.
The authors tackled the NP-hard problem of calculating selection probabilities in lexicase selection by introducing probabilistic lexicase selection (plexicase selection), which approximates the distribution efficiently and achieves state-of-the-art performance competitive with lexicase selection while significantly improving computation efficiency on benchmarks like PSB and SRBench.
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.