Probabilistic Lexicase Selection

Li Ding, Edward R. Pantridge, Lee Spector

Introduction

In the field of Genetic Programming (GP), parent selection is a critical mechanism that determines which individuals contribute their genetic material to the next generation. Among various strategies, Lexicase selection has emerged as a "gold standard" due to its semantic-aware nature. Unlike traditional methods that aggregate performance into a single scalar fitness value, Lexicase evaluates individuals on every training case independently, effectively maintaining population diversity and solving complex problems that require specialized sub-behaviors.

Despite its success, Lexicase selection faces two significant hurdles: computational inefficiency and theoretical opacity. The recursive selection process is computationally expensive to run for every parent in a large population, and calculating the exact probability of an individual being selected is an NP-hard problem. This paper introduces Plexicase, a novel algorithm designed to approximate Lexicase's selection probabilities. Plexicase enables direct, high-speed sampling and introduces a tunable hyperparameter to balance the trade-off between exploration and exploitation.

The Plexicase Algorithm

Plexicase transforms the "black-box" recursive process of Lexicase into a more transparent "gray-box" probabilistic model. The method follows three primary stages:

  1. Pareto Set Filtering: The algorithm first identifies individuals who are not "strictly dominated" by others. Using a vectorized pairwise comparison, Plexicase filters out individuals who perform worse than at least one other individual on every single test case. These dominated individuals have a 0% probability of selection in standard Lexicase and are removed to streamline calculations.
  2. Probability Assignment via Elitism: Rather than simulating the recursive elimination loop, Plexicase estimates selection probability based on an individual's elitism—the specific count of training cases where they achieve the global best fitness. This serves as a high-fidelity proxy for their likelihood of surviving the Lexicase selection shuffle.
  3. The $\alpha$ Hyperparameter: A key innovation of Plexicase is the introduction of $\alpha$, a "temperature" setting that controls the distribution of selection probabilities.
  4. Low $\alpha$: Flattens the distribution, spreading probability more evenly to encourage exploration.
  5. High $\alpha$: Sharpens the distribution, favoring top performers to encourage exploitation.
  6. $\alpha = 1$: Functions as a direct approximation of standard Lexicase selection.

Experimental Evaluation

The researchers evaluated Plexicase against standard Lexicase using two rigorous benchmarks:

  • Program Synthesis Benchmark Suite (PSB): Seven problems (e.g., median, smallest, vector-average) representing introductory computer science tasks.
  • SRBench: A large-scale symbolic regression platform involving 20 black-box regression problems with sample sizes ranging from 40 to 200.

Key Results and Insights

Computational Efficiency

Plexicase demonstrated a significant reduction in runtime. In program synthesis tasks, the algorithm achieved a speedup of up to 10x compared to standard Lexicase. This efficiency is largely attributed to the shift from recursive elimination to vectorized comparisons, allowing the algorithm to process the entire population simultaneously. The performance gains were even more substantial when Plexicase was paired with training case downsampling.

Problem-Solving Success

Plexicase matched or exceeded the success rates of Lexicase across the benchmarks. A notable example occurred in the median problem under downsampling conditions: Plexicase achieved a 98% success rate, significantly outperforming Lexicase's 70%. This suggests that the probabilistic approximation may actually improve robustness in certain scenarios.

Fidelity and Stability

To ensure Plexicase remained true to its inspiration, the authors measured the "Overlap Ratio"—the frequency with which Plexicase selects the same individuals as Lexicase. This ratio remained consistently above 0.8 for the general population and above 0.9 for unique individuals, confirming the high fidelity of the approximation. Furthermore, in symbolic regression tasks, $\epsilon$-Plexicase exhibited lower variance across different problems than $\epsilon$-Lexicase, indicating a more stable solver.

Conclusion

Plexicase addresses the primary weaknesses of Lexicase selection by providing a mathematically grounded, computationally efficient, and tunable alternative. By moving from recursion to a probabilistic framework, it provides researchers with a "knob" ($\alpha$) to adapt the selection pressure to the specific needs of a problem. While currently tested on standard GP benchmarks, the efficiency of Plexicase opens the door for its application in larger-scale domains, including deep neural network optimization and parameterized quantum computing models.

Summary updated

BibTeX
@inproceedings{ding2023probabilistic,
  author = {Li Ding and Edward R. Pantridge and Lee Spector},
  title = {{Probabilistic Lexicase Selection}},
  booktitle = {GECCO},
  year = {2023},
  url = {https://openreview.net/forum?id=t27lbMqZZb},
}
Figure