Probabilistic Lexicase Selection
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.
Code (1)
Tasks
Program SynthesisregressionSymbolic RegressionSimilar Papers 제목 키워드 기반
A probabilistic and multi-objective analysis of lexicase selection and epsilon-lexicase selection
Lexicase selection is a parent selection method that considers training cases individually, rather than in aggregate, when performing parent selection. Whereas previous work has demonstrated the ability of lexicase selec…
Program SynthesisregressionSymbolic RegressionAn Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality
Parent selection algorithms (selection schemes) steer populations through a problem's search space, often trading off between exploitation and exploration. Understanding how selection schemes affect exploitation and expl…
BenchmarkingDiagnosticDown-Sampled Epsilon-Lexicase Selection for Real-World Symbolic Regression Problems
Epsilon-lexicase selection is a parent selection method in genetic programming that has been successfully applied to symbolic regression problems. Recently, the combination of random subsampling with lexicase selection s…
Program SynthesisregressionSymbolic RegressionComparing and Combining Lexicase Selection and Novelty Search
Lexicase selection and novelty search, two parent selection methods used in evolutionary computation, emphasize exploring widely in the search space more than traditional methods such as tournament selection. However, le…
DiversityProgram SynthesisCalculating lexicase selection probabilities is NP-Hard
Calculating the probability of an individual solution being selected under lexicase selection is an important problem in attempts to develop a deeper theoretical understanding of lexicase selection, a state-of-the art pa…