A Probabilistic and Multi-Objective Analysis of Lexicase Selection and -Lexicase Selection

Area of Science:

• Evolutionary Computation
• Artificial Intelligence
• Machine Learning

Background:

• Lexicase selection is a parent selection technique that evaluates training cases individually.
• Its effectiveness in program synthesis and symbolic regression is established, but theoretical underpinnings are lacking.

Purpose of the Study:

• To develop theoretical foundations explaining lexicase selection's performance.
• To propose and evaluate new variants for improved efficacy in continuous error spaces.

Main Methods:

• Derivation of an analytical formula for selection probabilities.
• Analysis of lexicase selection's relation to many-objective optimization.
• Introduction and testing of $$-lexicase selection variants.

Main Results:

• An analytical formula for selection probabilities was derived.
• Lexicase selection's behavior was linked to Pareto front boundaries.
• Identified performance limitations in specific population/case sizes and continuous error spaces.
• $$-lexicase selection demonstrated superior performance over diversity-maintenance strategies.

Conclusions:

• Theoretical insights into lexicase selection's mechanics were provided.
• $$-lexicase selection effectively addresses challenges in continuous error spaces.
• The proposed variants offer enhanced performance for regression tasks.