An Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality
This work provides insights for researchers and practitioners in evolutionary computation to optimize selection schemes for challenging problems, though it is incremental as it builds on existing lexicase variants.
The paper tackled the problem of understanding how parent selection algorithms affect exploration in search spaces by introducing an exploration diagnostic to measure this capacity. It found that lexicase selection outperforms tournament selection in exploration, with epsilon lexicase improving it further, while down-sampling and novelty-lexicase degrade it, and cohort partitioning preserves it better than down-sampling.
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 exploration within a search space is crucial to tackling increasingly challenging problems. Here, we introduce an "exploration diagnostic" that diagnoses a selection scheme's capacity for search space exploration. We use our exploration diagnostic to investigate the exploratory capacity of lexicase selection and several of its variants: epsilon lexicase, down-sampled lexicase, cohort lexicase, and novelty-lexicase. We verify that lexicase selection out-explores tournament selection, and we show that lexicase selection's exploratory capacity can be sensitive to the ratio between population size and the number of test cases used for evaluating candidate solutions. Additionally, we find that relaxing lexicase's elitism with epsilon lexicase can further improve exploration. Both down-sampling and cohort lexicase -- two techniques for applying random subsampling to test cases -- degrade lexicase's exploratory capacity; however, we find that cohort partitioning better preserves lexicase's exploratory capacity than down-sampling. Finally, we find evidence that novelty-lexicase's addition of novelty test cases can degrade lexicase's capacity for exploration. Overall, our findings provide hypotheses for further exploration and actionable insights and recommendations for using lexicase selection. Additionally, this work demonstrates the value of selection scheme diagnostics as a complement to more conventional benchmarking approaches to selection scheme analysis.