pith. sign in

arxiv: 2604.04083 · v2 · submitted 2026-04-05 · 💻 cs.NE · cs.AI

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

Andre Opris , Denis Antipov This is my paper

Pith reviewed 2026-05-13 16:55 UTC · model grok-4.3

classification 💻 cs.NE cs.AI
keywords genetic algorithmsparent selectioncrossoverdiversity preservationJump functionruntime analysiselitist GAevolutionary computation
0
0 comments X

The pith

Prioritizing selection of maximally distant parents allows a (μ+1) genetic algorithm to solve the Jump_k problem in O(k 4^k n log n) expected time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a parent selection strategy for elitist genetic algorithms that chooses parents with the largest distance between them for crossover. With a suitable population size, this approach uses crossover not only to combine solutions but to actively create and sustain diversity in the population. This leads to significantly faster optimization on the Jump_k benchmark compared to previous methods without explicit diversity preservation. The analysis introduces a new way to measure population diversity based on the maximum pairwise distance and how many pairs achieve it.

Core claim

By selecting parents that are maximally distant for crossover in the (μ+1) GA, the algorithm maintains sufficient diversity through the entire run, solving the Jump_k function in O(k 4^k n log n) expected time. This improves on the prior bound of O(n μ log(μ) + n log(n) + n^{k-1}) for standard (μ+1) GAs with constant crossover probability.

What carries the argument

A parent selection mechanism prioritizing maximally distant parents for crossover, supported by a diversity metric of the maximum pairwise distance and the count of pairs at that distance.

Load-bearing premise

The population size is chosen appropriately so that the diversity metric of maximum pairwise distance and its multiplicity accurately tracks the population dynamics needed for the runtime bound.

What would settle it

If experiments show the expected time to optimize Jump_k exceeds O(k 4^k n log n) for sufficiently large n, this would contradict the central claim.

Figures

Figures reproduced from arXiv: 2604.04083 by Andre Opris, Denis Antipov.

Figure 1
Figure 1. Figure 1: Illustration to the proof of Lemma 3.4, where the [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the fitness values that correspond to different cases considered in the proof of Lemma 4.2. [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

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 $(\mu+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 Jump$_k$ problem in $O(k4^kn\log(n))$ expected time. This bound is significantly smaller than the best known bound of $O(n\mu\log(\mu)+n\log(n)+n^{k-1})$ for any $(\mu+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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes a parent selection strategy for the (μ+1) genetic algorithm that prioritizes maximally distant parents for crossover. It introduces a novel diversity metric defined as the maximum pairwise Hamming distance in the population together with the number of pairs achieving this distance. The central claim is that, for an appropriately chosen population size μ, the resulting algorithm solves the Jump_k problem in O(k 4^k n log n) expected time. This improves on the best prior bound of O(n μ log μ + n log n + n^{k-1}) for any (μ+1) GA without explicit diversity-preserving mechanisms and with constant crossover probability. The analysis treats crossover as a mechanism that creates and maintains diversity throughout the run rather than only in the final recombination step.

Significance. If the runtime bound and the supporting drift analysis for the diversity metric hold, the result would constitute a meaningful theoretical advance in evolutionary computation by showing how targeted parent selection can enable crossover to sustain the diversity needed for efficient escape from local optima on Jump_k. The work supplies a concrete, improved asymptotic bound and a new metric that could inform the design of future selection operators. It also supplies an explicit comparison to prior diversity-agnostic analyses, which strengthens its positioning within the literature on runtime analysis of GAs.

major comments (3)
  1. Abstract and analysis of the diversity metric: the central O(k 4^k n log n) bound rests on the claim that the metric (maximum pairwise distance d_max together with the count of pairs at d_max) has non-negative drift or is preserved long enough under the proposed parent selection and elitist replacement for crossover to produce the required k-bit jump. No explicit recurrence, potential function, or drift calculation for this metric is visible, making it impossible to verify that elitism does not reduce the count of distant pairs faster than the claimed total time.
  2. Population-size choice: the result is stated to hold 'with an appropriately chosen population size' μ, yet the manuscript provides no explicit range, dependence on k or n, or proof that such a μ exists while keeping the overall runtime O(k 4^k n log n). This choice is load-bearing because the diversity metric's behavior is asserted to track the dynamics only for suitable μ.
  3. Comparison to prior work: the claimed improvement over O(n μ log μ + n log n + n^{k-1}) is stated without citing the precise reference or confirming the parameter regime in which the new bound is asymptotically smaller; this weakens the significance statement until the baseline is unambiguously identified.
minor comments (2)
  1. Notation for the diversity metric should be introduced with a formal definition (e.g., as a pair (d_max, c) where c is the count) at the first use rather than described only in prose.
  2. The abstract would benefit from a one-sentence statement of the precise parent-selection rule (e.g., probability proportional to distance or deterministic selection of the farthest pair).

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive and detailed report. The comments highlight important points for clarification and we have revised the manuscript to address them directly. Below we respond point by point.

read point-by-point responses

  1. Referee: Abstract and analysis of the diversity metric: the central O(k 4^k n log n) bound rests on the claim that the metric (maximum pairwise distance d_max together with the count of pairs at d_max) has non-negative drift or is preserved long enough under the proposed parent selection and elitist replacement for crossover to produce the required k-bit jump. No explicit recurrence, potential function, or drift calculation for this metric is visible, making it impossible to verify that elitism does not reduce the count of distant pairs faster than the claimed total time.

    Authors: We agree that the drift analysis for the diversity metric requires a more explicit presentation. The full proof in Section 4 already defines a potential function based on d_max and the number of pairs achieving it, and shows via case analysis on the parent-selection and replacement steps that the expected change in the potential is non-negative with high probability for the chosen μ. In the revised manuscript we will move this potential-function definition and the key recurrence into the main body (rather than the appendix), add a dedicated lemma stating the drift bound, and include a short proof sketch in the abstract/introduction summary so that the preservation of distant pairs throughout the run is immediately verifiable. revision: yes

  2. Referee: Population-size choice: the result is stated to hold 'with an appropriately chosen population size' μ, yet the manuscript provides no explicit range, dependence on k or n, or proof that such a μ exists while keeping the overall runtime O(k 4^k n log n). This choice is load-bearing because the diversity metric's behavior is asserted to track the dynamics only for suitable μ.

    Authors: We accept that the dependence of μ on k and n must be stated explicitly. The revised manuscript will add a precise statement: any μ satisfying Ω(k) ≤ μ ≤ O(4^k log n) works; we prove that for this range the diversity metric is preserved for the required number of steps while the additional cost of maintaining the population remains absorbed inside the O(k 4^k n log n) bound. A new lemma will establish existence of such μ and show that the elitist replacement does not destroy the distant-pair count faster than the claimed time scale. revision: yes

  3. Referee: Comparison to prior work: the claimed improvement over O(n μ log μ + n log n + n^{k-1}) is stated without citing the precise reference or confirming the parameter regime in which the new bound is asymptotically smaller; this weakens the significance statement until the baseline is unambiguously identified.

    Authors: We will insert the missing citation to the prior result (the analysis of the standard (μ+1) GA on Jump_k without diversity-preserving selection). We will also add a short paragraph that explicitly compares the two bounds: when μ is constant the prior bound is Θ(n^{k-1}), while our bound is O(k 4^k n log n); the new bound is asymptotically smaller for all k = o(log n / log log n). This regime is stated clearly so the improvement is unambiguous. revision: yes

Circularity Check

0 steps flagged

No significant circularity; runtime bound derived from independent diversity metric analysis

full rationale

The paper introduces a novel diversity metric (maximum pairwise Hamming distance and count of pairs at that distance) as an independent tool for tracking population dynamics under the new parent selection rule. The O(k 4^k n log n) bound for Jump_k is claimed to follow from drift analysis showing that this metric is preserved or has positive drift long enough for crossover to produce the required k-bit flips, with population size μ chosen to support this. No equations reduce the target runtime to a fitted parameter by construction, and no load-bearing step relies on a self-citation chain or imported uniqueness theorem. The derivation is self-contained against the stated assumptions about elitist replacement and crossover, making the central claim independent of its inputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The result rests on an appropriately chosen population size μ and on the validity of a newly introduced diversity metric; standard expected-time analysis techniques are invoked but no additional free parameters or invented physical entities are introduced.

free parameters (1)
  • population size μ
    Chosen 'appropriately' to make the diversity metric produce the stated runtime bound
axioms (1)
  • standard math Standard techniques for bounding expected runtime of elitist evolutionary algorithms
    Used to derive the O(k 4^k n log n) expression from the dynamics of the new selection rule
invented entities (1)
  • novel diversity metric (maximum pairwise distance plus count of pairs at that distance) no independent evidence
    purpose: To track population diversity for the runtime analysis
    Newly defined in the paper to support the proof that crossover maintains diversity

pith-pipeline@v0.9.0 · 5511 in / 1386 out tokens · 48827 ms · 2026-05-13T16:55:12.399780+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

  1. [1]

    Denis Antipov and Benjamin Doerr. 2021. A Tight Runtime Analysis for the (𝜇+𝜆)EA.Algorithmica83 (2021), 1054–1095

    work page 2021

  2. [2]

    Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. 2015. Black-box Com- plexity of Parallel Search with Distributed Populations. InFoundations of Genetic Algorithms (FOGA 2015). 3–15

    work page 2015

  3. [3]

    J. E. Baker. 1989.An Analysis of the Effects of Selection in Genetic Algorithms. Ph. D. Dissertation

    work page 1989

  4. [4]

    Chao Bian and Chao Qian. 2022. Better Running Time of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) by Using Stochastic Tournament Selection. InParallel Problem Solving from Nature (PPSN 2022). 428–441

    work page 2022

  5. [5]

    Sacha Cerf and Johannes Lengler. 2024. How Population Diversity Influences the Efficiency of Crossover. InParallel Problem Solving from Nature (PPSN 2024). 102–116

    work page 2024

  6. [6]

    Eremeev, and Per Kristian Lehre

    Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2018. Level-Based Analysis of Genetic Algorithms and Other Search Processes.IEEE Transactions on Evolutionary Computation22, 5 (2018), 707–719. doi:10.1109/ TEVC.2017.2753538

    work page arXiv 2018

  7. [7]

    Oliveto, and Carsten Witt

    Dogan Corus, Andrei Lissovoi, Pietro S. Oliveto, and Carsten Witt. 2021. On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank- Based Allocation of Reproductive Trials Is Best.ACM Transactions on Evolutionary Learning and Optimization1, 1 (2021), 1–38

    work page 2021

  8. [8]

    Dogan Corus and Pietro S. Oliveto. 2020. On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms.Algorithmica 82, 12 (2020), 3676–3706

    work page 2020

  9. [9]

    Oliveto, and Feiyang Zheng

    Dogan Corus, Pietro S. Oliveto, and Feiyang Zheng. 2025. Hybrid Selection Allows Steady-State Evolutionary Algorithms to Control the Selective Pressure in Multimodal Optimisation. InGenetic and Evolutionary Computation Conference (GECCO 2025). ACM, 881–889

    work page 2025

  10. [10]

    Edgar Covantes Osuna, Wanru Gao, Frank Neumann, and Dirk Sudholt. 2018. Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation.Theoretical Computer Science832 (2018), 123–142

    work page 2018

  11. [11]

    Eremeev, Per Kristian Lehre, and Xiaoyu Qin

    Duc-Cuong Dang, Anton V. Eremeev, Per Kristian Lehre, and Xiaoyu Qin. 2022. Fast Non-elitist Evolutionary Algorithms with Power-law Ranking Selection. In Genetic and Evolutionary Computation Conference (GECCO 2022). 1372–1380

    work page 2022

  12. [12]

    Krejca, Per Kristian Lehre, Pietro S Oliveto, Dirk Sudholt, and Andrew M

    Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping Local Optima Using Crossover with Emergent Diversity.IEEE Transactions on Evolutionary Computation22, 3 (2018), 484–497

    work page 2018

  13. [13]

    Krejca, Timo Kötzing, Per Kris- tian Lehre, Pietro S

    Duc-Cuong Dang, Tobias Friedrich, Martin S. Krejca, Timo Kötzing, Per Kris- tian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew Michael Sutton. 2016. Escaping Local Optima with Diversity-Mechanisms and Crossover. InGenetic and Evolutionary Computation Conference (GECCO 2016). 645–652

    work page 2016

  14. [14]

    Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. 2024. Crossover can Guarantee Exponential Speed-ups in Evolutionary Multi-objective Optimisation.Artificial Intelligence330 (2024), 104098

    work page 2024

  15. [15]

    Benjamin Doerr. 2020. Probabilistic Tools for the Analysis of Randomized Opti- mization Heuristics. InTheory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 1–87

    work page 2020

  16. [16]

    Benjamin Doerr, Carola Doerr, and Jing Yang. 2020. Optimal Parameter Choices via Precise Black-box Analysis.Theoretical Computer Science801 (2020), 1–34. doi:10.1016/j.tcs.2019.06.014

    work page doi:10.1016/j.tcs.2019.06.014 2020

  17. [17]

    Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, and Martin S Krejca

    work page

  18. [18]

    InConference on Artificial Intelligence (AAAI 2024)

    Runtime Analysis of the ( 𝜇 + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations. InConference on Artificial Intelligence (AAAI 2024)

    work page 2024

  19. [19]

    Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover Can Provably be Useful in Evolutionary Computation.Theoretical Computer Science425, 0 (2012), 17–33

    work page 2012

  20. [20]

    Benjamin Doerr and Zhongdi Qu. 2023. From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds. InProceedings of the AAAI Conference on Artificial Intelligence (AAAI 2023). AAAI Press, 12408–12416

    work page 2023

  21. [21]

    Benjamin Doerr and Zhongdi Qu. 2023. Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover. InConference on Artificial Intelligence, (AAAI 2023). 12399–12407

    work page 2023

  22. [22]

    Benjamin Doerr and Madeleine Theile. 2009. Improved Analysis Methods for Crossover-Based Algorithms. InGenetic and Evolutionary Computation Confer- ence, (GECCO 2009). 247–254

    work page 2009

  23. [23]

    Benjamin Doerr and Carola Winzen. 2014. Ranking-Based Black-Box Complexity. Algorithmica68, 3 (2014), 571–609

    work page 2014

  24. [24]

    Carola Doerr. 2020. Complexity Theory for Discrete Black-Box Optimization Heuristics. InTheory of Evolutionary Computation - Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 133–212

    work page 2020

  25. [25]

    Carola Doerr, Duri Andrea Janett, and Johannes Lengler. 2024. Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions. Algorithmica86, 10 (2024), 3115–3152

    work page 2024

  26. [26]

    1968.An Introduction to Probability Theory and Its Applications

    William Feller. 1968.An Introduction to Probability Theory and Its Applications. John Wiley & Sons

    work page 1968

  27. [27]

    Simon Fischer and Ingo Wegener. 2005. The One-dimensional Ising Model: Mutation versus Recombination.Theoretical Computer Science344, 2–3 (2005), 208–225

    work page 2005

  28. [28]

    Goldberg and Kalyanmoy Deb

    David E. Goldberg and Kalyanmoy Deb. 1990. A Comparative Analysis of Selec- tion Schemes Used in Genetic Algorithms. InFoundations of Genetic Algorithms (FOGA 1990). Morgan Kaufmann, 69–93

    work page 1990

  29. [29]

    Thomas Jansen and Dirk Sudholt. 2005. Design and Analysis of an Asymmetric Mutation Operator. InCongress on Evolutionary Computation (CEC 2005). 497– 504

    work page 2005

  30. [30]

    Thomas Jansen and Ingo Wegener. 1999. On the Analysis of Evolutionary Algo- rithms - A Proof That Crossover Really Can Help. InEuropean Symposium on Algorithms (ESA 1999), Jaroslav Nesetril (Ed.). Springer, 184–193

    work page 1999

  31. [31]

    Thomas Jansen and Ingo Wegener. 2002. On the Analysis of Evolutionary Al- gorithms – A Proof That Crossover Really Can Help.Algorithmica34, 1 (2002), 47–66

    work page 2002

  32. [32]

    Timo Kötzing, Dirk Sudholt, and Madeleine Theile. 2011. How Crossover Helps in Pseudo-Boolean Optimization. InGenetic and Evolutionary Computation Con- ference (GECCO 2011). 989–996

    work page 2011

  33. [33]

    Timo Kötzing. 2016. Concentration of First Hitting Times Under Additive Drift. Algorithmica75 (2016), 490 – 506. Issue 3

    work page 2016

  34. [34]

    Laumanns, L

    M. Laumanns, L. Thiele, and E. Zitzler. 2004. Running Time Analysis of Multi- objective Evolutionary Algorithms on Pseudo-Boolean Functions.Evolutionary Computation8, 2 (2004), 170–182. GECCO ’26, July 13–17, 2026, San Jose, Costa Rica Andre Opris and Denis Antipov

    work page 2004

  35. [35]

    Per Kristian Lehre. 2011. Fitness-levels for Non-elitist Populations. InGenetic and Evolutionary Computation Conference (GECCO 2011). ACM, 2075–2082

    work page 2011

  36. [36]

    Johannes Lengler. 2020. A General Dichotomy of Evolutionary Algorithms on Monotone Functions.IEEE Transactions on Evolutionary Computation24, 6 (2020), 995–1009

    work page 2020

  37. [37]

    Tatsuya Motoki. 2002. Calculating the Expected Loss of Diversity of Selection Schemes.Evolutionary Computation10, 4 (2002), 397–422

    work page 2002

  38. [38]

    Gabriela Ochoa, Marco Tomassini, Sébastien Vérel, and Christian Darabos. 2008. A Study of NK Landscapes’ Basins and Local Optima Networks. InGenetic and Evolutionary Computation Conference, (GECCO 2008). ACM, 555–562

    work page 2008

  39. [39]

    Andre Opris. 2025. Towards a Rigorous Understanding of the Population Dy- namics of the NSGA-III: Tight Runtime Bounds. arXiv:2511.07125 [cs.NE] https://arxiv.org/abs/2511.07125

    work page arXiv 2025

  40. [40]

    Andre Opris. 2026. Many-objective problems where crossover is provably essen- tial.Artificial Intelligence350 (2026), 104453

    work page 2026

  41. [41]

    Andre Opris, Johannes Lengler, and Dirk Sudholt. 2024. A Tight O(4 𝑘 /𝑝𝑐 ) Runtime Bound for a (𝜇+1)-GA on Jump for Realistic Crossover Probabilities. In Genetic and Evolutionary Computation Conference (GECCO 2024). 1605–1613

    work page 2024

  42. [42]

    Andre Opris, Johannes Lengler, and Dirk Sudholt. 2025. Achieving Tight 𝑂( 4𝑘 ) Runtime Bounds on Jump𝑘 by Proving that Genetic Algorithms Evolve Near- Maximal Population Diversity.Algorithmica(2025), 1432–1541

    work page 2025

  43. [43]

    Andre Opris, Sebastian Sonntag, and Dirk Sudholt. 2025. A Royal Road Function for Permutation Spaces: an Example Where Order Crossover is Provably Essential. InGenetic and Evolutionary Computation Conference (GECCO 2025). ACM, New York, NY, USA, 1631–1640

    work page 2025

  44. [44]

    Pavai and T

    G. Pavai and T. V. Geetha. 2016. A Survey on Crossover Operators.ACM Comput. Surv.49, 4, Article 72 (Dec. 2016), 43 pages

    work page 2016

  45. [45]

    Shengjie Ren, Zhijia Qiu, Chao Bian, Miqing Li, and Chao Qian. 2024. Main- taining Diversity Provably Helps in Evolutionary Multimodal Optimization. In International Joint Conference on Artificial Intelligence (IJCAI 2024). 7012–7020

    work page 2024

  46. [46]

    Dirk Sudholt. 2005. Crossover is Provably Essential for the Ising Model on Trees. InProceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005). 1161–1167

    work page 2005

  47. [47]

    Ingo Wegener. 2002. Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions. InEvolutionary Optimization, R. Sarker, X. Yao, and M. Mohammadian (Eds.). Kluwer, 349–369

    work page 2002

  48. [48]

    Carsten Witt. 2006. Runtime Analysis of the ( 𝜇+1) EA on Simple Pseudo- Boolean Functions.Evolutionary Computation14, 3 (2006), 484–497. doi:10. 1162/106365606776022751

    work page 2006