Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
This work provides a deeper theoretical understanding of crossover's role in population dynamics for evolutionary computation researchers, though it is incremental as it builds on existing GA frameworks.
The paper tackles the theoretical understanding of parent selection in genetic algorithms by incorporating strategies into the (μ+1) GA, showing that selecting maximally distant parents with probability Ω(1) solves the Jump_k problem in O(k4^k n log(n)) expected time, significantly improving over the previous best bound of O(nμ log(μ) + n log(n) + n^{k-1}).
Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by incorporating different parent selection strategies into the $(μ+1)$ genetic algorithm (GA). We show that, with an appropriately chosen population size and a parent selection strategy that selects a pair of maximally distant parents with probability $Ω(1)$ for crossover, the resulting algorithm solves the Jump$_k$ problem in $O(k4^kn\log(n))$ expected time. This bound is significantly smaller than the best known bound of $O(nμ\log(μ)+n\log(n)+n^{k-1})$ for any $(μ+1)$~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The crucial point of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals, as it has been done in many previous works. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.