A suite of diagnostic metrics for characterizing selection schemes

Benchmark suites provide useful measurements of an evolutionary algorithm's problem-solving capacity, but the constituent problems are often too complex to cleanly identify an algorithm's strengths and weaknesses. Here, we introduce the benchmark suite DOSSIER (``Diagnostic Overview of Selection Schemes In Evolutionary Runs'') for empirically analyzing selection schemes on important aspects of exploitation and exploration. Exploitation is fundamentally hill climbing, but we consider two scenarios: pure exploitation where each position in the representation can be optimized independently, and constrained exploitation where upward progress is more limited due to interactions between positions. Exploration is necessary when the optimization path is less clear; we consider the ability to follow multiple independent hill climbing pathways and the ability to cross fitness valleys. Each combination of these scenarios produces distinct fitness landscapes that help characterize the evolutionary dynamics associated with a given selection scheme. We analyze six popular selection schemes. Tournament selection and truncation selection both excelled at with exploitation metrics, but performed poorly when exploration was required; conversely, novelty search excelled at exploration but failed to exploit gradients. Fitness sharing performed well when overcoming deception, but poorly across all other diagnostics. Nondominated sorting was best for maintaining diverse populations comprised of individuals inhabiting multiple optima, but struggled to effectively exploit gradients. Lexicase selection balanced search space exploration without sacrificing exploitation, generally performing well across diagnostics. Our work demonstrates the value of diagnostics for quickly building an intuitive understanding of selection scheme characteristics, which can then be used to improve or develop new selection methods.