# Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

arXiv: https://arxiv.org/abs/2604.04083 · HTML: https://mlsanity.com/paper/2604.04083/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 5 Apr 2026.

## Builds on (most cited first, 17 of 17)

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Level-based Analysis of Genetic Algorithms and other Search Processes](https://mlsanity.com/paper/1407.7663/) (2014)
- [A Tight Runtime Analysis for the (μ + λ) EA](https://mlsanity.com/paper/1812.11061/) (2018)
- [Optimal Parameter Choices via Precise Black-Box Analysis](https://mlsanity.com/paper/1807.03403/) (2018)
- [Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation](https://mlsanity.com/paper/2301.13687/) (2023)
- [Complexity Theory for Discrete Black-Box Optimization Heuristics](https://mlsanity.com/paper/1801.02037/) (2018)
- [On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms](https://mlsanity.com/paper/1903.10976/) (2019)
- [On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best](https://mlsanity.com/paper/2103.10394/) (2021)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [A General Dichotomy of Evolutionary Algorithms on Monotone Functions](https://mlsanity.com/paper/1803.09227/) (2018)
- [Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions](https://mlsanity.com/paper/2302.12338/) (2023)
- [How Population Diversity Influences the Efficiency of Crossover](https://mlsanity.com/paper/2404.12268/) (2024)
- [Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds](https://mlsanity.com/paper/2511.07125/) (2025)
- [Maintaining Diversity Provably Helps in Evolutionary Multimodal Optimization](https://mlsanity.com/paper/2406.02658/) (2024)

## Abstract (arXiv)

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 proposing a parent selection strategy for the (μ+1) genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, the resulting algorithm solves the Jumpk problem in O(k4knlog(n)) expected time. This bound is significantly smaller than the best known bound of O(nμlog(μ)+nlog(n)+nk-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 main novelty 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. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.