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 selection to solve difficult problems in program synthesis and symbolic regression, the central goal of this paper is to develop the theoretical underpinnings that explain its performance. To this end, we derive an analytical formula that gives the expected probabilities of selection under lexicase selection, given a population and its behavior. In addition, we expand upon the relation of lexicase selection to many-objective optimization methods to describe the behavior of lexicase selection, which is to select individuals on the boundaries of Pareto fronts in high-dimensional space. We show analytically why lexicase selection performs more poorly for certain sizes of population and training cases, and show why it has been shown to perform more poorly in continuous error spaces. To address this last concern, we propose new variants of epsilon-lexicase selection, a method that modifies the pass condition in lexicase selection to allow near-elite individuals to pass cases, thereby improving selection performance with continuous errors. We show that epsilon-lexicase outperforms several diversity-maintenance strategies on a number of real-world and synthetic regression problems.
Code (1)
Tasks
Program SynthesisregressionSymbolic RegressionSimilar Papers 제목 키워드 기반
On the Robustness of Lexicase Selection to Contradictory Objectives
Lexicase and epsilon-lexicase selection are state of the art parent selection techniques for problems featuring multiple selection criteria. Originally, lexicase selection was developed for cases where these selection cr…
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-pa…
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…
BenchmarkingDiagnosticA Performance Analysis of Lexicase-Based and Traditional Selection Methods in GP for Symbolic Regression
In recent years, several new lexicase-based selection variants have emerged due to the success of standard lexicase selection in various application domains. For symbolic regression problems, variants that use an epsilon…
regressionSymbolic RegressionDown-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 Regression