Lexicase Selection of Specialists
This research addresses the problem of understanding why lexicase selection outperforms other parent selection methods in evolutionary computation, with implications for improving optimization algorithms in machine learning and AI.
The study investigated whether selecting specialist individuals, who excel on some training cases but perform poorly on others, contributes to the performance advantages of lexicase selection over error-aggregating methods like tournament selection. Experiments showed that depriving lexicase selection of the ability to select specialists degraded its performance and diversity maintenance, supporting the hypothesis.
Lexicase parent selection filters the population by considering one random training case at a time, eliminating any individuals with errors for the current case that are worse than the best error in the selection pool, until a single individual remains. This process often stops before considering all training cases, meaning that it will ignore the error values on any cases that were not yet considered. Lexicase selection can therefore select specialist individuals that have poor errors on some training cases, if they have great errors on others and those errors come near the start of the random list of cases used for the parent selection event in question. We hypothesize here that selecting these specialists, which may have poor total error, plays an important role in lexicase selection's observed performance advantages over error-aggregating parent selection methods such as tournament selection, which select specialists much less frequently. We conduct experiments examining this hypothesis, and find that lexicase selection's performance and diversity maintenance degrade when we deprive it of the ability of selecting specialists. These findings help explain the improved performance of lexicase selection compared to tournament selection, and suggest that specialists help drive evolution under lexicase selection toward global solutions.