Paper deep dive
Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
Andre Opris, Denis Antipov
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 4/10/2026, 2:32:21 AM
Summary
This paper proposes a novel parent selection strategy for the (μ+1) genetic algorithm (GA) that prioritizes selecting maximally distant parents for crossover. The authors demonstrate that this approach significantly improves the algorithm's performance on the Jump_k problem, achieving an expected runtime of O(k4^kn log(n)), which is superior to previous bounds for (μ+1) GAs without explicit diversity-preserving mechanisms. The analysis introduces a new diversity metric based on the maximum Hamming distance between individuals and the number of pairs at that distance, providing theoretical insights into how crossover can actively maintain and increase population diversity.
Entities (4)
Relation Signals (2)
(μ+1) Genetic Algorithm → solves → Jump_k
confidence 95% · the resulting algorithm solves the Jump_k problem in O(k4^kn log(n)) expected time
Parent Selection → improves → (μ+1) Genetic Algorithm
confidence 90% · proposing a parent selection strategy for the (μ+1) genetic algorithm (GA) that prioritizes the selection of maximally distant parents
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2604.04083v2
- Canonical: https://arxiv.org/abs/2604.04083v2
Trouble viewing inline? Open PDF directly →
Full Text
96,041 characters extracted from source content.
Expand or collapse full text
by Parent Selection Mechanisms in Elitist Crossover-Based Algorithms Andre Opris andre.opris@uni-passau.de 0000-0002-7730-7831 University of PassauPassauGermany and Denis Antipov denis.antipov@lip6.fr 0000-0001-7906-096X Sorbonne Université, CNRS, LIP6ParisFrance (2026) 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 (μ+1)(μ+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))O(k4^kn (n)) expected time. This bound is significantly smaller than the best known bound of O(nμlog(μ)+nlog(n)+nk−1)O(nμ (μ)+n (n)+n^k-1) for any (μ+1)(μ+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. Evolutionary algorithms, Theory, Parent Selection, Crossover †journalyear: 2026†copyright: c†conference: Genetic and Evolutionary Computation Conference; July 13–17, 2026; San Jose, Costa Rica†booktitle: Genetic and Evolutionary Computation Conference (GECCO ’26), July 13–17, 2026, San Jose, Costa Rica†doi: 10.1145/3795095.3805131†isbn: 979-8-4007-2487-9/2026/07†ccs: Theory of computation Theory of randomized search heuristics†ccs: Theory of computation Evolutionary algorithms†ccs: Computing methodologies Genetic algorithms 1. Introduction Evolutionary algorithms (EAs for brevity) are one of the most widely used random search heuristics for solving real-world optimization problems. They combine ease of application (they do not require any prior knowledge of the problem and treat it as a black box) with the ability to efficiently find good solutions. During the last three decades theory has derived lots of valuable analyses of mutation-based EAs (the ones that can create new individuals only by taking one of the previously sampled individuals and changing it), and it is fair to say that we understand these algorithms quite well, including the best ways to apply them (Doerr et al., 2020; Antipov and Doerr, 2021; Lengler, 2020; Doerr et al., 2024b), the limits of their efficiency (Doerr, 2020b, Section 3.6), and their behavior in more complex settings such as multi-objective optimization (Doerr and Qu, 2023a; Opris, 2025). However, EAs that create new individuals with crossover by recombining two existing individuals (these algorithms are often called genetic algorithms, or GAs) are still not well-understood, although the first proofs of crossover being helpful have appeared more than 25 years ago (Jansen and Wegener, 1999). This is since the population dynamics of GAs are much more complex than in mutation-based EAs: one needs to analyze how the diversity evolves over time, which is very challenging. At the same time, in practice crossover is considered to be an essential ingredient of an efficient EA (Pavai and Geetha, 2016). So far, theoretical studies of GAs have shown that crossover can immensely help when the population of the algorithm is diverse: recombining two good but different solutions into a new one can often result into even better individuals (Dang et al., 2016; Corus and Oliveto, 2020). However, the main challenge lies in obtaining a diverse population, since crossover is generally believed to reduce the diversity or have no significant effect on it (see the overview of related work in Section 1.2). For this reason, most of the theoretical studies rely in their analyses on the diversity being increased in mutation-only steps of GAs, and these studies often use either a very small probability of crossover or some mechanisms that artificially improve diversity using the problem’s properties. In the light of the previous studies, the main result of this paper comes as a surprise: we show that crossover can actually help to increase diversity when we regularly choose the most distant individuals as parents. Our analysis reveals a very interesting interaction of mutation and crossover, where mutation helps to increase the maximal distance between individuals in the population, while crossover helps to create more pairs of individuals in that distance from each other, which prevents the algorithm from decreasing this maximal distance. Roughly speaking, if we measure diversity via this maximal distance, then crossover allows us to get a solid foothold at the current diversity level, so we stay there for long enough for mutation to increase diversity. This mechanism turns out to be almost as effective at escaping local optima as very strong diversity preserving mechanisms (see (Dang et al., 2016) for the latter). In addition, we show that crossover can support fast hill-climbing, avoiding slow-downs that might be caused by large populations. The key to such behavior is the strategy of parent selection. This aspect of EAs has previously been studied mostly for non-elitist algorithms, where the parent population “dies out” in each iteration, and only the fittest offspring survives to reproduce in the next iteration and also in multi-objective optimization (see a detailed overview in Section 1.2). However, most of those studies considered mutation-only EAs, except for the paper by Corus et al. (2018). The results of this paper illustrate the potential benefits of using non-uniform parent selection in elitist algorithms, especially for catalyzing the ability of crossover to help to diversify the population. Although our analysis is performed only on one benchmark function, the intuition behind the reasons of diversification of the population is not tailored to it, which makes the insights obtained in this paper interesting for practitioners. In particular, we are optimistic that the processes similar to the ones observed in our proofs take place also on problem landscapes with local optima networks (LONs, introduced by Ochoa et al. (2008)), allowing crossover driven by parent selection with a bias toward furthest individuals to effectively find such networks without any prior landscape analysis of the problem class. 1.1. Our contribution The main result of this paper is Theorem 3.6, which shows that the (μ+1) GA (formally defined in Section 2) which with probability p performs crossover and chooses the furthest parents for it can find the global optimum of Jumpk (with jump size k) in expected O(4kn/p)O(4^kn/p) fitness evaluations, if its population size μ is at least c⋅4klog(n)/pc· 4^k (n)/p for some constant c and if its population is already on the plateau of Jumpk. The main reason that this parent selection helps us is not because of the last step when we can choose the furthest parents to create the optimum (as it might seem in the context of the previous studies of the (μ+1) GA) but because of its role in diversification of the algorithm’s population. We also show that this parent selection allows to reach the local optima of Jumpk in O(nμ/p+nlog(n/k))O(nμ/p+n (n/k)), that is, it does not slow the algorithm down on “easy” parts of the problem and is even beneficial for hill-climbing tasks. The main technical novelty that this paper brings to the toolbox of runtime analysis of EAs is the new diversity measure that we study. This measure captures the maximum distance between the individuals in the population and the number of disjoint pairs of individuals in that distance (see Definition 3.1), and our analysis shows that it is a meaningful description of the population structure. Some of our results for this measure (Lemma 3.2 and Lemma 3.3) are proven without any bind to the fitness function or parent selection method, which, we believe, creates a decent foundation for more general analyses of the (μ+1) GA (even with uniform parent selection). 1.2. Related Work Theoretical studies of crossover. Numerous theoretical studies are dedicated to finding the best practices of using crossover. Many of them analyze evolutionary algorithms with and without crossover on the Jumpk benchmark.111Jumpkis formally defined later in Section Preliminaries. This pseudo-Boolean test function has a unique global optimum, and all points in radius k (which is a parameter of the benchmark) from the global optimum are local optima with the second-best function value. Typically, evolutionary algorithms easily reach these local optima and then they either have to perform a “jump” by mutating one local optimum precisely into the global optimum or by correctly recombining two local optima via crossover. This benchmark was first introduced by Jansen and Wegener (1999, 2002), and they showed that classic mutation-only evolutionary algorithms need Θ(nk) (n^k) time to find the optimum, while crossover-based (μ+1) GA can do that in O(4k⋅poly(n))O(4^k·poly(n)) expected time (where n is the dimensionality of the problem, usually called the problem size). The gap between these two performances is super-polynomial, when k=ω(1)∩O(log(n))k=ω(1)∩ O( (n)). The main disadvantage of this result is that it was proven only for an algorithm with an extremely small probability to perform crossover (much smaller than commonly used in practice). In particular, the analysis was built on the idea that the algorithm first diversifies its population through mutation, covering many different local optima, and then crossover can recombine two individuals into the optimal solution. Many follow-up works that analyzed the (μ+1) GA on Jumpk can be divided into two categories. The first group are the works focusing on the analysis of the vanilla (μ+1) GA with reasonable crossover rate. The central result in this line of work was obtained by Dang et al. (2018), who showed that, due to mutation, a small amount of diversity can spread through the population, so that the majority genotype constitutes only a 1−Ω(1)1- (1) fraction of the population. Recently, this result was refined by Doerr et al. (2024a) who proved that the diversity created in this manner is maintained for an exponential time. However, in both cases, the amplitude of the diversity (that is, the maximum distance between individuals) can be small, so the upper bound on the runtime proven in those papers is O~(nk−1) O(n^k-1) fitness evaluations, that is, by factor Θ~(n) (n) better than the runtime Θ(nk) (n^k) of classic mutation-based EAs. The second group consists of works that analyzed a modified version of the algorithm, which introduced various mechanisms to speed-up diversification of the population and/or preserve the diversity of the population for a longer time (Kötzing et al., 2011; Opris et al., 2024; Dang et al., 2018, 2016; Ren et al., 2024). Some of the algorithms proposed in these works even achieved O(4k+nlog(n))O(4^k+n (n)) runtime on Jumpk, which is the best theoretically possible performance for a large class of evolutionary algorithms, as it was shown by Opris et al. (2025a). Unfortunately, the arguments used in the proofs of these works were not applicable to the vanilla (μ+1) GA, and they do not explain its population dynamics. On the positive side, these works introduced various diversity measures which help to capture the state of the population, which is especially helpful for empirical studies. Interestingly, many analyses in both of these groups of works were similar in having a pessimistic view on crossover iterations: their arguments used mutation-only iterations as the main source of diversity improvements, while crossover iterations were assumed to produce the worst possible individuals. The purpose of using low crossover probability or diversity-preserving tie-breaking rules was primarily in dealing with the negative effect of such presumably bad crossover offspring. This resulted in the common belief that crossover does not help to diversify population or even prevent the algorithm from doing it. There are many theoretical results studying the (μ+1) GA on other benchmark functions, such as OneMax (Corus and Oliveto, 2020), RoyalRoad (Jansen and Wegener, 2002; Jansen and Sudholt, 2005) (including a variant of this function for permutation spaces (Opris et al., 2025b)) or LeadingOnes (Cerf and Lengler, 2024), and all of them to different extent show benefits of using crossover in evolutionary algorithms. However, the main argument there is the same as on Jumpk: the algorithm first obtains some diversity via mutations and then exploits it with crossover to get better progress than it can get by only using mutation. Crossover has also been analyzed on multiple combinatorial problems such as graph coloring (Fischer and Wegener, 2005; Sudholt, 2005) and all-pairs shortest path (Doerr and Theile, 2009; Doerr et al., 2012), and although the arguments used in their proofs are very problem-specific, they nevertheless demonstrate various ways in which crossover can be useful. Recently, following a rapid emergence of theoretical analyses of multi-objective optimizers, several works proved the positive impact of crossover also in this domain (Opris, 2026; Dang et al., 2024; Doerr and Qu, 2023b). Parent selection. Strategy of selecting individuals to reproduce is one of the crucial parts of most evolutionary algorithms that allows to balance between exploration (finding new promising areas of the search space) and exploitation (thoroughly searching in an area of high interest). Various parent selection mechanisms were studied theoretically in the area of multi-objective optimization (Laumanns et al., 2004; Covantes Osuna et al., 2018; Bian and Qian, 2022) and in the area of non-elitist EAs (Baker, 1989; Goldberg and Deb, 1990; Motoki, 2002; Lehre, 2011; Dang et al., 2022; Corus et al., 2018). Most these studies focus on mutation-only EAs, with exception being (Corus et al., 2018). In this paper, however, the proofs pessimistically assume that crossover offspring are always the worst possible solutions (with exception of their analysis of GAs on some trivial problems), which lines up with the analyses of the (μ+1) GA mentioned earlier (and therefore, with understanding of the role of crossover). For the elitist single-objective EAs (such as the (μ+1) GA studied in this work) parent selection was only studied for the mutation-only counterpart of the (μ+1) GA, the (μ+1) EA, by Corus et al. (2021) (further developed by Corus et al. (2025)), where they showed a counter-intuitive result that giving the priority to the worst individuals to reproduce allows avoiding getting stuck in local optima and to find many optima in one run. Summary. From this overview of existing results one can see that it is well understood that crossover can be beneficial when recombining individuals of a diverse population, but its role in diversifying a population is still unclear. This implies a lack of understanding of population dynamics of crossover-based algorithms. It is also notable that it is not known, which parent selection strategies work best for crossover-based EAs. In this work, we aim at making progress toward covering these two blind spots of theory of evolutionary computation. 2. Preliminaries 2.1. Notation We denote by |A||A| the cardinality of a finite set A, by log the logarithm to base 22 and by ln the logarithm to base e. For n∈ℕn we write [n]≔1,2,…,n[n] \1,2,…,n\. For x∈0,1nx∈\0,1\^n and I⊂[n]I⊂[n] we denote by |x|1I≔∑i∈Ixi|x|_1^I _i∈ Ix_i the number of ones and by |x|0I≔∑i∈I(1−xi)|x|_0^I _i∈ I(1-x_i) the number of zeros at positions from I, respectively. For I⊂[n]I⊂[n] and x,y∈0,1nx,y∈\0,1\^n, let HI(x,y)≔∑i∈I|xi−yi|H_I(x,y) _i∈ I|x_i-y_i| be the number of positions from I in which x and y differ. If I=[n]I=[n] we also write |x|1=|x|1I|x|_1=|x|_1^I, |x|0=|x|0I|x|_0=|x|_0^I and H(x,y)=HI(x,y)H(x,y)=H_I(x,y), the latter denoting the Hamming distance between x and y. We call x complementary to y with respect to I if xi≠yix_i≠ y_i for all i∈Ii∈ I. The Jumpk benchmark is defined as Jumpk(x)≔|x|1+kif |x|1=n or |x|1≤n−k,n−|x|1otherwise. Jump$_k$(x) cases|x|_1+k&if |x|_1=n or |x|_1≤ n-k,\\ n-|x|_1&otherwise. cases By plateau we mean the set of all search points with n−kn-k ones in the context of Jumpk(x) Jump$_k$(x). 2.2. Algorithm We define a slightly modified version of the classic (μ+1) GA incorporating parent selection mechanisms. We use the following notation. For t∈ℕ0t _0 the population of the (μ+1) GA in the beginning of iteration t is denoted by PtP_t, and it a multiset of μ individuals, that is, x1,…,xμ\x_1,…,x_μ\ where xi∈0,1nx_i∈\0,1\^n for i∈1,…,ni∈\1,…,n\. Let also mtD_m^t be a distribution over PtP_t and ctD_c^t be a distribution over Pt×PtP_t× P_t. These distributions must be chosen by the algorithm user, but in our analysis this choice is not so important, so they should be seen as some arbitrary distributions. The (μ+1) GA that we consider in this paper starts with some initial population, and then performs iterations until some stopping criterion is met.222As in most theoretical analyses, we do not specify the stopping criterion, but we assume that the algorithm does not stop before it finds the optimum. In each iteration with probability pcp_c (independently from other iterations) it performs a crossover step. In this case, two parents x1,x2x_1,x_2 are selected following distribution ctD_c^t, and uniform crossover is applied to x1x_1 and x2x_2, creating offspring y′y that takes each bit from one of the parents (with equal probability from each parent, and independently for each bit position), and then it applies standard bit mutation to y′y , flipping each bit independently with probability 1/n1/n to generate an offspring y. With probability (1−pc)(1-p_c), the algorithm performs a mutation-only iteration, selecting parent x following distribution mtD_m^t and applying standard bit mutation to it to generate an offspring y. The offspring y replaces a worst search point z from the previous population if its fitness is not worse than the fitness of z. If there are several worst points, the algorithm selects one of them uniformly at random. The pseudocode of this algorithm is depicted in Algorithm 1. 1t←0t← 0; 2 let P0P_0 contain μ search points chosen uniformly at random; 3 while termination criterion not met do 4 with probability pcp_c do 5 choose x1,x2∼ctx_1,x_2 _c^t; 6 y′←crossover(x1,x2)y (x_1,x_2); 7 y←mutation(y′)y (y ); 8 9 else 10 select x∼mtx _m^t; 11 y←mutation(x)y (x); 12 13 select z∈Ptz∈ P_t uniformly at random from all search points with minimum fitness in PtP_t; 14 if f(y)≥f(z)f(y)≥ f(z) then Pt+1←(Pt∪y)∖zP_t+1←(P_t∪\y\) \z\; 15 t←t+1t← t+1; 16 Algorithm 1 (μ+1) GA with parent selection mechanisms defined by distributions ctD_c^t and mtD_m^t. This definition covers many different selection mechanisms that can be used for parent selection. In particular, tournament, linear ranking, and fitness proportionate selection (Lehre, 2011), power-law selection (Dang et al., 2022) or inverse tournament selection (Corus et al., 2021). The important property of these selection mechanisms that we use in our analysis is the lower bound on the probability to choose the most distant pair of individuals as crossover parents. Namely, we define pfu≔inft∈ℕPr[H(x1,x2)=dt∣(x1,x2)∼ct], p_fu _t [H(x_1,x_2)=d_t (x_1,x_2) _c^t ], where dt=maxy1,y2∈PtH(y1,y2)d_t= _y_1,y_2∈ P_tH(y_1,y_2). We do not use any properties of ctD_c^t, except that pfu=Ω(4r(k−r)ln(n)/(pcμ))p_fu= (4^r(k-r) (n)/(p_cμ)) for a natural number 1≤r≤k1≤ r≤ k (see Theorem 3.6 below). Hence, it should only depend mildly on the parameters of the Jumpk problem, and also on the algorithm’s population size μ. We note that the uniform selection does not satisfy this condition (since it yields pfu=Θ(1μ2)p_fu= ( 1μ^2)), and neither do all fitness-based selection methods (since pfup_fu can be even zero). However, selection methods that rank all pairs of individuals by their Hamming distance (in non-ascending order) and then choose a pair according to this ranking can satisfy this condition. In particular, a power-law selection (similar to the fitness-based selection from (Dang et al., 2022)) or an ℓ -tournament selection with ℓ=Ω(4r(k−r)ln(n)μ/pc) = (4^r(k-r) (n)μ/p_c) satisfy the condition on pfup_fu. 2.3. Useful Tools Gambler’s ruin problem (Feller, 1968): Consider a gambler who wins or loses a dollar with probabilities p and q, respectively. He has an initial capital of ℓ and plays against an opponent with the initial capital a−ℓa- . The game continues until the gambler’s capital either is reduced to zero or has increased to a, that is, until one of the two players is ruined. The problem may also be described as a random walk starting at 0<ℓ<a0< <a with absorbing states at 0 and a where it moves to the right or left with probability p and q, respectively. The process terminates when the particle reaches either 0 or a. The position of the particle after n steps represents the gambler’s capital after n games. Then the following holds. Lemma 2.1. [Chapter 14 in (Feller, 1968)] The probability of the gambler going broke (or the particle reaches 0) is (q/p)a−(q/p)ℓ(q/p)a−1. (q/p)^a-(q/p) (q/p)^a-1. Useful bounds: The following inequalities on the amplified success rate in λ independent trials are useful. Lemma 2.2 (Lemma 10 in (Badkobeh et al., 2015)). For every p∈[0,1]p∈[0,1] and every λ∈ℕλ , 1−(1−p)λ∈[pλ1+pλ,2pλ1+pλ]. 1-(1-p)^λ∈ [ pλ1+pλ, 2pλ1+pλ ]. Negative drift theorem: We also need the following version of the negative drift theorem (see Theorem 3 in (Kötzing, 2016)). Theorem 2.3. Let (Xt)t≥0(X_t)_t≥ 0 be random variables over ℝR, each with finite expectation, and let n>0n>0. With T:=mint≥0:Xt≥n∣X0≤0T:= \t≥ 0:X_t≥ n X_0≤ 0\ we denote the random variable describing the earliest point that the random process exceeds n, given a starting value of at most 0. Suppose there are c with 0<c<n0<c<n and ε<0 <0 such that, for all t, the following holds: (1) E[Xt+1−Xt∣X0,…Xt,T>t]≤εE[X_t+1-X_t X_0,...X_t,T>t]≤ , (2) |Xt−Xt+1|<c|X_t-X_t+1|<c. Then, for all s≥0s≥ 0, Pr(T≤s)≤sexp(−n|ε|2c2). (T≤ s)≤ s (- n| |2c^2). On binomial distribution: the following lemma estimates the probability that a binomial random value exceeds its expectation. Lemma 2.4. Let X∼Bin(n,12)X (n, 12) with n≥1n≥ 1. Then for all odd n we have Pr[X>n2]=12. [X> n2]= 12. For all even n we have Pr[X>n2]≥12(1−2πn). [X> n2]≥ 12 (1- 2π n ). In both cases, Pr[X>n2]≥12(1−1π). [X> n2]≥ 12 (1- 1π ). Proof. Since Y=n−XY=n-X follows the same distribution as X, we can use the symmetry of binomial distribution: (1) Pr[X>n2]=Pr[Y<n2]=Pr[X<n2]. [X> n2]= [Y< n2]= [X< n2]. For odd n we have Pr[X>n2]+Pr[X<n2]=1 [X> n2]+ [X< n2]=1, hence by (1) we have Pr[X>n2]=1/2 [X> n2]=1/2. For even n we need to take into account the event when X=n2X= n2, that is, we have Pr[X>n2]+Pr[X=n2]+Pr[X<n2]=1, [X> n2]+ [X= n2]+ [X< n2]=1, hence, Pr[X>n2]=12(1−Pr[X=n2]). [X> n2]= 12 (1- [X= n2] ). For binomial distribution, using eq. (1.4.18) in the book chapter by Doerr (2020a) that bounds binomial coefficients, we have Pr[X=n2]=(n/2)12n≤2πn. [X= n2]= nn/2 12^n≤ 2π n. Hence, we have Pr[X>n2]≥12(1−2πn). [X> n2]≥ 12 (1- 2π n ). Noting that the smallest even n is n=2n=2 and uniting these two lower bounds, we prove the last statement of the lemma. ∎ On binomial coefficients. The following lemma can be used to estimate some range of binomial coefficients. This result can be distilled from Lemma 8 by Doerr and Winzen (2014), where this result was formulated for the case of large n (but the proof does not use it). Lemma 2.5 (Lemma 8 by Doerr and Winzen (2014)). For any n∈ℕn and any ℓ=n2±γn = n2±γ n we have (nℓ)≥2n2πne4γ n ≥ 2^n2 π ne^4γ. 3. The (μ+1)(μ+1) GA with Furthest Parent Selection Escapes Plateau Efficiently The goal of this section is to demonstrate that the (μ+1)(μ+1) GA with parent selection mechanisms can escape the plateau of Jumpk efficiently. To achieve this, we analyze the population dynamics of this algorithm with special focus on the last part of optimization, when the whole population is on the plateau. This analysis is structured as follows. First, to measure population diversity, we introduce d(Pt)d(P_t) as the maximum Hamming distance between two individuals from PtP_t and mtm_t as the maximum number of disjoint pairs with this distance (Definition 3.1) and then give some elementary properties of this measure (Lemmas 3.2 and 3.3). We note that higher values of dtd_t increase the probability of creating the global optimum from two individuals x and y with H(x,y)=dtH(x,y)=d_t via crossover and mutation afterwards, while higher values of mtm_t make it less likely that dtd_t will decrease in future iterations without first increasing. We then estimate the probability of increasing dtd_t or mtm_t, as well as the probability of reaching the global optimum from two individuals with distance dtd_t (Lemmas 3.4 and 3.5). With all these ingredients in place, we proceed to prove the main result of this section, Theorem 3.6, which bounds the expected time to escape the plateau. The proof strategy is as follows. As far as dtd_t does not increase, mtm_t performs an unfair random walk on 1,…,ℓ\1,…, \ for a large value ℓ where the probability to increase mtm_t is higher than decreasing it (Claim 1 in the proof of Theorem 3.6). Then, if mt≥ℓm_t≥ , the negative drift theorem is used to show that, with sufficiently high probability, dtd_t increases or the global optimum is created, before dtd_t decreases (Claim 2 in the proof of Theorem 3.6). These allow us to show that with constant probability dtd_t never decreases, which allows us to condition on that and to derive an upper bound on the time the algorithm spends on the plateau before it finds the optimum. Definition 3.1. Let PtP_t be a population of individuals. Let d(Pt)≔maxH(x,y)∣x,y∈Ptd(P_t) \H(x,y) x,y∈ P_t\ if Pt≠∅P_t≠ . Set d(Pt)=−∞d(P_t)=-∞ if Pt=∅P_t= . Further, let m(Pt): m(P_t): =max|Y|∣Y⊂Pt×Pt such that x≠y, = \|Y| Y⊂ P_t× P_t such that x≠ y, H(x,y)=dt, and x,y∩w,z=∅ H(x,y)=d_t, and \x,y\∩\w,z\= for all (x,y),(w,z)∈Y. for all (x,y),(w,z)∈ Y\. One sees immediately the following basic properties. Lemma 3.2. The following holds. (1) If there is only one pair x,y\x,y\ of search points with distance d(Pt)>0d(P_t)>0 then m(Pt)=1m(P_t)=1. (2) We have that m(Pt)≤⌊μ/2⌋m(P_t)≤ μ/2 . (3) If dtd_t increases by adding an individual x to PtP_t, then m(Pt∪x)=1m(P_t∪\x\)=1. Proof. The only multiset of most distant pairs of search points is Y=x,yY=\\x,y\\ which proves (1) and the number of disjoint pairs in PtP_t is at most ⌊μ/2⌋ μ/2 which proves (2). Every pair of individuals in Pt∪xP_t∪\x\ with maximum distance contains x, proving (3). ∎ We note that d(Pt)d(P_t) and m(Pt)m(P_t) have not been used before in theoretical studies of the (μ+1) GA. Most of the measures that have been used for this purpose were studied by Dang et al. (2016) who incorporated such measures into the tie-breaking mechanism of the (μ+1) GA. In particular, such measures as convex hull (the number of positions with different bits present in it), total Hamming distance and fitness sharing were maximized when breaking ties between individuals with the same fitness, and Dang et al. showed that it immensely helps the crossover to create good individuals, speeding up the (μ+1) GA on Jumpk. The measure closest to ours is the measure studied empirically in (Doerr et al., 2024a), where the authors tracked the maximum distance and the probability to choose a pair of parents in that distance for crossover (that is, instead of m(Pt)m(P_t) they considered a total number of pairs of individuals in distance d(Pt)d(P_t)). Those results looked very promising, however there were no theoretical analyses of this measure. Graphically, m(Pt)m(P_t) can be visualized as follows. Let Gt=(Vt,Et)G_t=(V_t,E_t), be a graph where each vertex of VtV_t represents one of the μ individuals in PtP_t, and there exists an edge between two vertices if and only if the distance between the two corresponding individuals is d(Pt)d(P_t). Then m(Pt)m(P_t) is the size of a maximum matching, which is the lower bound on the number of nodes one has to remove to have no edge left. Now we present some straightforward structural results for d(Pt)d(P_t) and m(Pt)m(P_t) of any population PtP_t, independent of the underlying fitness function. Lemma 3.3. Let PtP_t be a population with dt≔d(Pt)>0d_t d(P_t)>0, and mt≔m(Pt)m_t m(P_t). Then the following properties hold. (1) Suppose mt=1m_t=1. Then there are at most two y∈Pty∈ P_t such that d(Pt∖y)<dtd(P_t \y\)<d_t. For the other x∈Ptx∈ P_t, d(Pt∖x)=dtd(P_t \x\)=d_t. (2) Suppose mt>1m_t>1. Then there is S⊂PtS⊂ P_t with |S|=2mt|S|=2m_t such that d(S)=dtd(S)=d_t and m(S)=mtm(S)=m_t. Hence, m(Pt∖y)=mtm(P_t \y\)=m_t for all y∈Pt∖Sy∈ P_t S. Proof. (1): Let x,y∈Ptx,y∈ P_t with H(x,y)=dtH(x,y)=d_t. Removing any other individual cannot increase dtd_t (since we reduce the number of pairs) and it does not reduce dtd_t, since x and y are still in the population. Hence, dtd_t does not change. (2): Let Y⊂Pt×PtY⊂ P_t× P_t with |Y|=mt|Y|=m_t such that H(x,y)=dtH(x,y)=d_t and x,y∩w,z=∅\x,y\∩\w,z\= for all (x,y),(w,z)∈Y(x,y),(w,z)∈ Y (which exists by the definition of mtm_t). Let S≔x∈Pt∣∃y∈Pt such that (x,y)∈Y∨(y,x)∈Y.S \x∈ P_t ∃ y∈ P_t such that (x,y)∈ Y (y,x)∈ Y\. Note that S contains exactly the elements appearing in a pair in Y and hence, |S|=2mt|S|=2m_t. Removing any element not from S cannot increase mtm_t (since then mtm_t is the maximum over a smaller set) and it also does not change Y, hence we still have mtm_t disjoint pairs in distance dtd_t. ∎ In the remainder of this section we estimate the expected runtime of the (μ+1) GA on Jumpk when it starts with the whole population already on the plateau, which is shown in Theorem 3.6. Note that when the whole population is on the plateau, then dtd_t can only take even values (since the distance between two individuals on the plateau can be only even). The following lemma provides lower bounds on the probabilities that, in a single iteration of Algorithm 1, the value m(Pt)m(P_t) or d(Pt)d(P_t) increases. Lemma 3.4. Consider an iteration t of the (μ+1) GA with furthest parent selection where PtP_t is on the plateau of Jumpk, dt:=d(Pt)d_t:=d(P_t) and mt:=m(Pt)m_t:=m(P_t). Then with probability at least pc⋅pfu4⋅(12)dt(1−2mt+1μ)≕pup(dt,mt) p_c· p_fu4· ( 12 )^d_t (1- 2m_t+1μ ) p_up(d_t,m_t) either dtd_t increases or mtm_t increases. Proof. If mt=⌊μ/2⌋m_t= μ/2 then the lemma trivially holds since pup(dt,mt)≤0p_up(d_t,m_t)≤ 0. So suppose that mt<⌊μ/2⌋m_t< μ/2 . We show that the probability pup(dt,mt)p_up(d_t,m_t) results from crossover on a most distant pair, producing a specific outcome x on plateau to increase the number of disjoint pairs by one, omitting mutation and not removing any individual from such a pair afterwards. With probability pc⋅pfup_c· p_fu, the (μ+1) GA applies crossover on a pair of most distant parents. Suppose that this happens, and let w,z∈Ptw,z∈ P_t be individuals with H(w,z)=dtH(w,z)=d_t, on which crossover is applied. Let b≔dt/2b d_t/2 and I⊂[n]I⊂[n] be the set of positions i with wi≠ziw_i≠ z_i. We call any i∈Ii∈ I a complementary position. Since w,zw,z are on plateau, we have |w|0=|z|0=k|w|_0=|z|_0=k and hence, |w|1I=|z|1I=|w|0I=|z|0I=b|w|_1^I=|z|_1^I=|w|_0^I=|z|_0^I=b (see Figure 1). Let J≔[n]∖IJ [n] I be the non-complementary part. By Lemma 3.3(2) there is S⊂PtS⊂ P_t such that |S|=2mt<μ|S|=2m_t<μ and m(S)=mtm(S)=m_t. Let y be any individual from Pt∖SP_t S, and let a≔|y|0Ia |y|_0^I (see Figure 1). We now aim at generating a crossover offspring x such that (i) it is on the plateau and (i) it is in distance at least dtd_t from y. If we succeed in it, and then this offspring is not changed by mutation, then adding x into the population (without yet removing any individual) increases either mtm_t (if H(x,y)=dtH(x,y)=d_t, then they form a new disjoint pair which can be added to S) or even dtd_t (if H(x,y)>dtH(x,y)>d_t). To show how we can generate such an x, we first note that x is on the plateau if (and only if) it has exactly b zero-bits (and thus b one-bits) in I, since in J it coincides with both parents that have k−bk-b zero-bits there (see Figure 1). The fact that x coincides with its parents in J also implies that HJ(x,y)H_J(x,y) is the same as HJ(w,y)H_J(w,y), which is at least the difference in the number of zero-bits in J in these two individuals, that is, HJ(x,y)≥|(k−a)−(k−b)|=|a−b|H_J(x,y)≥|(k-a)-(k-b)|=|a-b|. Now we want to set bits of x in I in such way that there were at least dt−|a−b|=2b−|a−b|d_t-|a-b|=2b-|a-b| different positions. Consider first the case when a≥ba≥ b (that is, majority of the bits of y in I are zeros). Then we can put b one-bits of x in the positions that are zeros in y, and put zeros in the rest of them. It implies that y and x are different in b positions that are ones in x, and in all 2b−a2b-a positions that are ones in y, that is, HI(x,y)=b+2b−a=2b−|a−b|H_I(x,y)=b+2b-a=2b-|a-b|. If a<ba<b then we can put b zero-bits of x in the positions that are ones in y, and put ones in the rest of them. It implies that y and x are also different in b positions that are zeros in x, and in all 2b−a2b-a positions that are zeros in y, implying HI(x,y)=b+2b−a=2b−|a−b|H_I(x,y)=b+2b-a=2b-|a-b|. Hence, we always can create offspring x that is in distance at least dtd_t from y by choosing correct values for the bits in I, probability of which is at least (12)dt( 12)^d_t. This offspring is then not changed by mutation with probability at least (1−1n)n≥14(1- 1n)^n≥ 14, where we used n≥2n≥ 2 (since it is the minimum n for which Jumpk can be defined). w:w:11111111111111111111110000000000000111111111111z:z:11111111111111111111110000000111111111111000000JJIIk−bk-bbbbby:y:k−ak-a zerosaa zerosx:x:11111111111111111111110000000b zeros Figure 1. Illustration to the proof of Lemma 3.4, where the two parent individuals are w and z, another individual to which we aim to create a pair is y and the crossover offspring is x. Finally, we also take into account the selection step, when we remove a random individual from the population. If H(x,y)>dtH(x,y)>d_t, the lemma holds since m(Pt)≥1m(P_t)≥ 1 and dtd_t increases if y is not removed (happening with probability 1−1/μ1-1/μ). If H(x,y)=dtH(x,y)=d_t, then m(Pt+1)=m(S∪x,y)=mt+1m(P_t+1)=m(S∪\x,y\)=m_t+1 and mtm_t increases if no individual from S∪yS∪\y\ is removed, which happens with probability 1−(2mt+1)/μ1-(2m_t+1)/μ. Bringing together the probabilities to perform crossover on the most distant parents, creating the right offspring, not mutating it and then not removing a wrong individuals in the selection completes the proof. ∎ We also provide lower bounds on the probabilities of increasing dtd_t and of creating the global optimum, each independent of mtm_t. Lemma 3.5. Consider an iteration t of the (μ+1) GA with furthest parent selection where PtP_t is on plateau, dt:=d(Pt)d_t:=d(P_t) and mt:=m(Pt)m_t:=m(P_t). Suppose that k≤n/3k≤ n/3. Then the following holds. (1) If dt<2kd_t<2k, then with probability at least pc⋅pfu⋅(12)dt13en(1−1μ)≕pup∗(dt)p_c· p_fu· ( 12 )^d_t 13en (1- 1μ ) p_up^*(d_t) dtd_t increases. (2) With probability at least pc⋅pfu⋅(12)dt1enk−dt/2≕popt(dt)p_c· p_fu· ( 12 )^d_t 1en^k-d_t/2 p_opt(d_t) the global optimum is created. Proof. Statement (1): The following scenario increases dtd_t. The (μ+1) GA performs crossover, chooses two most distant parents w,zw,z and creates x on plateau via crossover such that H(w,x)=dtH(w,x)=d_t (e.g. x=zx=z). Afterwards, it flips exactly a one bit and a zero bit in x at positions where w and z coincide and remains the other bits unchanged to create x′x . Then H(w,x′)=dt+2H(w,x )=d_t+2. Finally, x′x should not be removed from PtP_t. Hence, dtd_t is increased with probability at least pc⋅pfu p_c· p_fu ⋅(12)dt(k−dt/2)(n−k−dt/2)n2⋅(1−1n)n−2(1−1μ) · ( 12 )^d_t (k-d_t/2)(n-k-d_t/2)n^2· (1- 1n )^n-2 (1- 1μ ) ≥pc⋅pfu⋅(12)dt13en(1−1μ). ≥ p_c· p_fu· ( 12 )^d_t 13en (1- 1μ ). Statement (2): To create the optimum, the (μ+1) GA can perform crossover, choose two most distant parents w,zw,z and create the outcome x with xi=1x_i=1 at all positions i where wi≠ziw_i≠ z_i. Then it can flip the remaining k−dt/2k-d_t/2 zeros with mutation and remains the other bits unchanged. This happens with probability at least pc⋅pfu⋅(12)dt1nk−dt/2(1−1n)n−k+dt/2 p_c· p_fu· ( 12 )^d_t 1n^k-d_t/2 (1- 1n )^n-k+d_t/2 concluding the proof. ∎ Finally we are able to prove the main theorem in this paper which gives an upper bound for the expected time until the (μ+1) GA with furthest parent selection finds the global optimum, starting from a population on the plateau. The theorem holds for arbitrary values of 2≤k≤n/32≤ k≤ n/3 but requires that μ≥c⋅4r(k−r)ln(n)/(pcpfu)μ≥ c· 4^r(k-r) (n)/(p_cp_fu) for a sufficiently large constant c, where pcp_c and pfup_fu may depend on μ. Theorem 3.6. Consider the (μ+1) GA with furthest parent selection on Jumpk for 2≤k≤n/32≤ k≤ n/3. Let r∈[k−1]r∈[k-1]. Suppose μ≥c⋅4r(k−r)ln(n)/(pcpfu)μ≥ c· 4^r(k-r) (n)/(p_cp_fu) for a sufficiently large constant c and suppose that it starts with an arbitrary population P0P_0, all individuals of which are on the plateau. Then the expected number of fitness evaluations that the algorithm takes to find the global optimum is O(4r⋅nk−r/(pcpfu))O(4^r· n^k-r/(p_cp_fu)). Proof. Let dt≔d(Pt)d_t d(P_t) and mt≔m(Pt)m_t m(P_t) from Definition 3.1. The main goal is to show that with at least constant probability, the value dt∈0,2,…,2r−2d_t∈\0,2,…,2r-2\ never decreases before the all-ones string is created. To this end, we first show in Claim 1 that for every dt∈0,2,…,2r−2d_t∈\0,2,…,2r-2\, with sufficiently high probability, either a pair of individuals with distance at least dt+2d_t+2 is created, or mtm_t increases to a large value without decreasing dtd_t. Then, in Claim 2 we apply the negative drift theorem to prove that, with sufficiently high probability, a decrease of dtd_t does not occur before either its increase (if dt<2rd_t<2r so that it is possible) or the finding of the global optimum. Afterwards we conduct the desired runtime analysis with the method of typical runs (see Wegener, 2002, Section 11). For convenience, we define ℓ≔ℓ(δ,k,n)≔⌊20δln(kn)⌋ (δ,k,n) 20δ (kn) for 1≤δ≤k−r1≤δ≤ k-r, where δ is an auxiliary variable introduced to apply the negative drift theorem for different values of dtd_t in Claim 2. Let c from the condition on μ be at least 640. Then due to ln(nk)≤2ln(n) (nk)≤ 2 (n) (2) ℓμ≤20δln(kn)320⋅4r(k−r)ln(kn)/(pcpfu)≤pcpfu16⋅4r. μ≤ 20δ (kn)320· 4^r(k-r) (kn)/(p_cp_fu)≤ p_cp_fu16· 4^r. Claim 1. Let 1≤δ≤k−r1≤δ≤ k-r. Then for every dt∈2,…,2rd_t∈\2,…,2r\ the probability to increase dtd_t (if dt<2rd_t<2r) or to increase mtm_t to at least ℓ in a future iteration before decreasing dtd_t is at least 1−58122r−dt1- 58 12^2r-d_t. Proof of Claim. Without loss of generality we assume that mt<ℓ≤⌊μ/2⌋m_t< ≤ μ/2 . We first observe that in order to decrease dtd_t, at least mtm_t different individuals must be removed from the population. Therefore, it is only possible to achieve this in a single iteration when mt=1m_t=1. Let ℰ−E^- be the event that in one iteration the algorithm either decreases mtm_t, if mt>1m_t>1, or it decreases dtd_t, if mt=1m_t=1. Since we assume that all individuals are on the plateau, the removed individual is selected uniformly at random, hence the probability that ℰ−E^- occurs is at most 2mt/μ2m_t/μ (by Lemma 3.3(1) and (2)). Let ℰ+E^+ be the event to increase mtm_t or to increase dtd_t in one iteration. By Lemma 3.4, for each mt∈1,…,ℓ−1m_t∈\1,…, -1\ and dt∈0,2,…,2rd_t∈\0,2,…,2r\, the probability that ℰ+E^+ occurs is at least (3) pc⋅pfu4⋅(12)dt⋅μ−2ℓμ≥pc⋅pfu5⋅(12)dt≕c(dt) p_c· p_fu4· ( 12 )^d_t· μ-2 μ≥ p_c· p_fu5· ( 12 )^d_t c(d_t) owing to 2ℓ/μ≤pcpfu8⋅(12)2r≤1/52 /μ≤ p_cp_fu8· ( 12 )^2r≤ 1/5 (by Eq. (2)). Now we describe the process of increasing and decreasing dtd_t, as well as evolution of the value mtm_t if dtd_t remains unchanged over the time t, according to the following Markov chain with states S0,S1,…,S⌊μ/2⌋S_0,S_1,…,S_ μ/2 and T. State T will be entered if dtd_t increases, and state S0S_0 if dtd_t decreases. Furthermore, SiS_i for i≥1i≥ 1 will be entered if i=mti=m_t and dtd_t does not change. The transition probability from SiS_i to Si−1S_i-1 is at most 2i/μ2i/μ and from SiS_i to Si+1,T\S_i+1,T\ is at least c(dt)c(d_t). The transition probability from SiS_i to SjS_j for |j−i|≥2|j-i|≥ 2 is zero. Here, T and S0S_0 are absorbing states. If the current state is SiS_i for i≥2i≥ 2, then dtd_t cannot decrease (since dtd_t can decrease only in S1S_1). Hence, the aim is to determine the probability to reach T or SℓS_ before S0S_0. For 1≤i≤ℓ−11≤ i≤ -1 the probability of reaching Si+1S_i+1 or T before Si−1S_i-1 starting from SiS_i is given by Pr(Bi∣Ai∪Bi) (B_i A_i∪ B_i) =Pr(Bi)Pr(Ai∪Bi)≥Pr(Bi)Pr(Bi)+Pr(Ai) = (B_i) (A_i∪ B_i)≥ (B_i) (B_i)+ (A_i) ≥Pr(Bi)Pr(Bi)+2i/μ≥c(dt)c(dt)+2i/μ ≥ (B_i) (B_i)+2i/μ≥ c(d_t)c(d_t)+2i/μ ≥c(dt)c(dt)+2(ℓ−1)/μ≕pu, ≥ c(d_t)c(d_t)+2( -1)/μ p_u, where AiA_i denotes the event that we reach Si−1S_i-1, and BiB_i the event to reach Si+1S_i+1 or T. Hence, the probability of reaching S0S_0 before T or SℓS_ can be bounded from above by the probability that an unfair random walk with ℓ+1 +1 states Z0,…,ZℓZ_0,…,Z_ with transition probability pup_u from ZiZ_i to Zi+1Z_i+1 and pd=1−pup_d=1-p_u from Zi+1Z_i+1 to ZiZ_i for all i∈0∪[ℓ−1]i∈\0\∪[ -1] reaches Z0Z_0 before ZℓZ_ when starting from Z1Z_1. This stochastic process is also known as the Gambler’s Ruin Problem (Lemma 2.1) this probability is (pd/pu)ℓ−(pd/pu)(pd/pu)ℓ−1=pdpu⋅1−(pd/pu)ℓ−11−(pd/pu)ℓ≤pdpu. (p_d/p_u) -(p_d/p_u)(p_d/p_u) -1= p_dp_u· 1-(p_d/p_u) -11-(p_d/p_u) ≤ p_dp_u. This concludes the proof of this claim since pdpu p_dp_u =2(ℓ−1)c(dt)μ≤pcpfu8⋅4r⋅1pcpfu5⋅2dt=58122r−dt. = 2( -1)c(d_t)μ≤ p_cp_fu8· 4^r· 1 p_cp_fu5· 2^d_t= 58 12^2r-d_t. ■ The upper bound on the probability that a decrease of dtd_t occurs before an increase (if dt<2rd_t<2r) or the creation of the global optimum is as follows. Claim 2. Let 1≤δ≤k−r1≤δ≤ k-r. Consider an iteration t of the (μ+1) GA and suppose that mt≥ℓm_t≥ . Then the following holds. (1) If 0<dt<2r0<d_t<2r, the probability to decrease dtd_t before increasing it or creating the global optimum is at most 19/(10k)19/(10k). (2) If dt=2rd_t=2r and δ=k−rδ=k-r, the probability to decrease dtd_t before creating the global optimum is at most 3/43/4. Proof of Claim. Let c(dt)c(d_t) and pup_u be as in the proof of Claim 1. Denote by AtA_t the event that mtm_t or dtd_t decreases, by BtB_t that mtm_t increases (and hence not dtd_t), but the optimum is not created, and by CtC_t the event that dtd_t increases or the optimum is created. Further, denote by B~t B_t the event from (the proof of) Lemma 3.4 and by C~t C_t the event from (the proof of) Lemma 3.5(1) if dt<2rd_t<2r, or Lemma 3.5(2) if dt=2rd_t=2r. Note that C~t⊂Ct C_t⊂ C_t and B~t⊂Bt∪Ct B_t⊂ B_t∪ C_t. Further, B~t B_t and C~t C_t are disjoint since in the latter, at least one bit is flipped, whereas in the former, no bits are flipped during mutation. Therefore, we can pessimistically assume that Bt=B~tB_t= B_t and Ct=C~tC_t= C_t as this only reduces the probability for increasing dtd_t if dt<2rd_t<2r or creating the optimum if dt=2rd_t=2r before decreasing dtd_t and mtm_t can only change by at most one if dtd_t does not decrease. For the same reason, we can assume that Pr(At)=2mt/μ (A_t)=2m_t/μ, Pr(Bt)=c(dt) (B_t)=c(d_t) (see Equation 3), and Pr(Ct)=pup∗(dt) (C_t)=p_up^*(d_t) if dt<2rd_t<2r, while Pr(Ct)=popt(dt) (C_t)=p_opt(d_t) if dt=2rd_t=2r. We can also assume that in each iteration of the (μ+1) GA, one of the events At,BtA_t,B_t or CtC_t occurs since otherwise dtd_t and mtm_t do not change and we make no progress. At first we derive an upper bound for the probability of decreasing dtd_t within s∈ℕs iterations, assuming that dtd_t does not increase for each dt∈0,2,…,2r−2d_t∈\0,2,…,2r-2\ and the optimum is not created during this time. To this end, we apply the negative drift theorem (see Theorem 2.3) on Xt=ℓ−mtX_t= -m_t. The target Xt+1=ℓX_t+1= is reached when mt=1m_t=1 and dtd_t decreases in iteration t. Note that X0≤0X_0≤ 0 and XtX_t has finite expectation since 0≤mt≤μ/20≤ m_t≤μ/2. We define T≔inft>0∣Xt=ℓT \t>0 X_t= \ and verify both drift conditions for XtX_t. On the one hand, we have |Xt+1−Xt|≤1|X_t+1-X_t|≤ 1, since mtm_t can increase or decrease by at most 11 in each iteration, as long as the optimum is not reached. On the other hand, for all values of X0,…,XtX_0,…,X_t where the target has not been reached yet under the condition of At∪BtA_t∪ B_t and Xt≥0X_t≥ 0 (i.e. mt≤ℓm_t≤ ) we have E[Xt+1−Xt] E[X_t+1-X_t] =Pr(Xt+1=Xt+1) = (X_t+1=X_t+1) −Pr(Xt+1=Xt−1) - (X_t+1=X_t-1) =Pr(ℓ−mt+1=ℓ−mt+1) = ( -m_t+1= -m_t+1) −Pr(ℓ−mt+1=ℓ−mt−1) - ( -m_t+1= -m_t-1) =Pr(mt+1=mt−1)−Pr(mt+1=mt+1) = (m_t+1=m_t-1)- (m_t+1=m_t+1) =P(At)P(At)+P(Bt)−P(Bt)P(At)+P(Bt) = P(A_t)P(A_t)+P(B_t)- P(B_t)P(A_t)+P(B_t) =12mt/μ+c(dt)(2mtμ−c(dt)) = 12m_t/μ+c(d_t) ( 2m_tμ-c(d_t) ) ≤12ℓ/μ+c(dt)(2ℓμ−c(dt)) ≤ 12 /μ+c(d_t) ( 2 μ-c(d_t) ) With eq. (2), we get by plugging in the right hand side for ℓ/μ /μ and the value for c(dt)c(d_t) from eq. (3) due to dt<2rd_t<2r ≤1pc⋅pfu8⋅(12)2r+pc⋅pfu5⋅2dt(pc⋅pfu8⋅(12)2r−pc⋅pfu5⋅2dt) ≤ 1 p_c· p_fu8· ( 12 )^2r+ p_c· p_fu5· 2^d_t ( p_c· p_fu8· ( 12 )^2r- p_c· p_fu5· 2^d_t ) =15⋅2dt+8⋅4r(5⋅2dt−8⋅4r) = 15· 2^d_t+8· 4^r (5· 2^d_t-8· 4^r ) ≤15⋅2dt+8⋅2dt(5⋅2dt−8⋅2dt) ≤ 15· 2^d_t+8· 2^d_t (5· 2^d_t-8· 2^d_t ) =5−85+8=−313≕−ε<0. = 5-85+8=- 313 - <0. Finally, we obtain by the negative drift theorem for all s>0s>0 (4) Pr(T≤s) (T≤ s) ≤sexp(−ℓε2)=sexp(−3ℓ26)≤sexp(−2δln(kn)). ≤ s (- 2 )=s (- 3 26 )≤ s (-2δ (kn) ). where ℓ=⌊20δln(kn)⌋ = 20δ (kn) for an auxiliary 1≤δ≤k−r1≤δ≤ k-r. Now we verify the two single claims stated in the lemma. (1): Recall that by our assumption Pr(Ct)=pup∗(dt)=pc⋅pfu⋅(12)dt⋅13en. (C_t)=p_up^*(d_t)=p_c· p_fu· ( 12 )^d_t· 13en. Then the probability that dtd_t increases (see eq. (2) and (3)) is at least Pr(Ct)Pr(At)+Pr(Bt)+Pr(Ct)≥pup∗(dt)2ℓ/μ+c(dt)+pup∗(dt) (C_t) (A_t)+ (B_t)+ (C_t)≥ p_up^*(d_t)2 /μ+c(d_t)+p_up^*(d_t) ≥pc⋅pfu3en⋅(12)dtpc⋅pfu8(12)2r+pc⋅pfu5⋅(12)dt+pc⋅pfu3en⋅(12)dt ≥ p_c· p_fu3en· ( 12 )^d_t p_c· p_fu8 ( 12 )^2r+ p_c· p_fu5· ( 12 )^d_t+ p_c· p_fu3en· ( 12 )^d_t ≥13en2dt8⋅(12)2r+3en5+1≥13en8+3en5+3n3 ≥ 1 3en2^d_t8· ( 12 )^2r+ 3en5+1≥ 1 3en8+ 3en5+ 3n3 ≥14n≕σ(n)≕σ, ≥ 14n σ(n) σ, since by our assumption, in each iteration the event Dt:=At∪Bt∪CtD_t:=A_t∪ B_t∪ C_t occurs. Denote by T~ T the number of iterations until dtd_t increases. Then the probability to increase dtd_t in s iterations (which means T~≤s T≤ s) if dtd_t does not decrease (which means T>sT>s) is the probability that the event CtC_t does occur at least one time in s iterations under the condition that T>sT>s holds. Hence we obtain for s∈ℕs Pr(T~≤s∣T>s)≥1−(1−σ)s≥s⋅σ1+s⋅σ≥1−1s⋅σ ( T≤ s T>s)≥ 1- (1-σ )^s≥ s·σ1+s·σ≥ 1- 1s·σ where the second inequality is due to Lemma 2.2. By letting s=20k/(19σ)=80kn/19s=20k/(19σ)=80kn/19 we obtain Pr(T~≤s∣T>s)≥1−1920kPr( T≤ s T>s)≥ 1- 1920k. On the other hand we have by eq. (4) where we plug in δ=1δ=1 and s=80kn/19s=80kn/19 Pr(T≤s)≤sexp(−2δln(kn))=80kn19k2n2≤1920k (T≤ s)≤ s (-2δ (kn))= 80kn19k^2n^2≤ 1920k for n sufficiently large. Hence, the probability to increase dtd_t within the next s=80kn/19s=80kn/19 iterations while not decreasing dtd_t is Pr((T~≤s)∩(T>s)) (( T≤ s)∩(T>s) .) =Pr(T~≤s∣T>s)⋅P(T>s) = ( T≤ s T>s)· P(T>s) ≥(1−1920k)(1−1920k)≥1−1910k, ≥ (1- 1920k ) (1- 1920k )≥ 1- 1910k, where we used the Weierstrass product inequality (1−x)(1−y)≥1−x−y(1-x)(1-y)≥ 1-x-y for x,y≥0x,y≥ 0. (2): Recall that by Lemma 3.5(2) due to dt=2rd_t=2r popt(2r)=pc⋅pfu⋅(12)2r1enk−r p_opt(2r)=p_c· p_fu· ( 12 )^2r 1en^k-r and therefore the probability to create 1n1^n is at least (conditioned on DtD_t), Pr(Ct)Pr(At)+Pr(Bt)+Pr(Ct)≥popt(2r)2ℓ/μ+c(2r)+popt(2r) (C_t) (A_t)+ (B_t)+ (C_t)≥ p_opt(2r)2 /μ+c(2r)+p_opt(2r) ≥pc⋅pfuenk−r⋅(12)2rpc⋅pfu8⋅(12)2r+pc⋅pfu5⋅(12)2r+pc⋅pfuenk−r⋅(12)2r ≥ p_c· p_fuen^k-r· ( 12 )^2r p_c· p_fu8· ( 12 )^2r+ p_c· p_fu5· ( 12 )^2r+ p_c· p_fuen^k-r· ( 12 )^2r ≥1enk−r8+enk−r5+nk−r≥12nk−r≕τ. ≥ 1 en^k-r8+ en^k-r5+n^k-r≥ 12n^k-r τ. Denote by T T the time until 1n1^n is created. Then we obtain for s∈ℕs iterations with a similar argument as above Pr (T^≤s∣T>s)≥1−(1−τ)s≥τs1+τs≥1−1τs. ( T≤ s T>s)≥ 1- (1-τ )^s≥ τ s1+τ s≥ 1- 1τ s. For s=4nk−rs=4n^k-r we obtain Pr(T^≤s∣T>s)≥1/2Pr( T≤ s T>s)≥ 1/2. Further, by eq. 4 and pluggin in δ=k−rδ=k-r and s=4nk−rs=4n^k-r, Pr(T≤s) (T≤ s) ≤sexp(−2δln(kn))≤sexp(−2δln(n)) ≤ s (-2δ (kn))≤ s (-2δ (n)) =s⋅n−2δ=4nk−rn−2(k−r)≤1/2 =s· n^-2δ=4n^k-rn^-2(k-r)≤ 1/2 for n sufficiently large due to k>rk>r. With a similar argument as above, the probability of creating the optimum within the next s=4nk−rs=4n^k-r iterations before decreasing dtd_t is at least = Pr(~T≤s ∣T ¿ s) ⋅P(T ¿ s) ≥(1−1/2)(1−1/2)=1/4=1−3/4, ≥(1-1/2)(1-1/2)=1/4=1-3/4, which concludes the proof of this claim. ■ For a fixed but arbitrary dt=d_t=d, by Claim 1 we either increase mtm_t to ℓ , increase dtd_t, or find the global optimum before dtd_t decreases with probability at least 1−58122r−d1- 58 12^2r-d. Conditional on this event and pessimistically assuming that we neither increased dtd_t, nor we found the optimum (that is, we still have dt=d_t=d and mt≥ℓm_t≥ ), we apply Claim 2 distinguishing two cases. If 0<d<2r0<d<2r, then we increase dtd_t or find the global optimum before we decrease dtd_t with probability at least 1−1910k1- 1910k. If d=2rd=2r, then we find the global optimum before decreasing dtd_t with probability 1−34=141- 34= 14. Combining the probabilities of these events for all d∈2,4,…,2rd∈\2,4,…,2r\ and recalling that r≤k−1r≤ k-1, we conclude that the probability that dtd_t never decreases before we find the optimum is at least (1−1910k)r−1⋅14⋅∏j=1r(1−58122r−2j) (1- 1910k )^r-1· 14·Π _j=1^r (1- 58 12^2r-2j ) ≥(1−1910k)k−2⋅14⋅∏j=1r(1−58122r−2j) ≥ (1- 1910k )^k-2· 14·Π _j=1^r (1- 58 12^2r-2j ) ≥(1−1910k)k−1.9⋅14⋅(1−58∑j=0∞14j) ≥ (1- 1910k )^k-1.9· 14· (1- 58Σ _j=0^∞ 14^j ) ≥1e1.9⋅14⋅(1−5811−1/4)=1e1.9⋅14⋅16∈Ω(1), ≥ 1e^1.9· 14· (1- 58 11-1/4 )= 1e^1.9· 14· 16∈ (1), where we used the Weierstrass product inequality ∏j=1m(1−xj)≥1−x1−…−xmΠ _j=1^m(1-x_j)≥ 1-x_1-…-x_m for m∈ℕm , xi∈[0,1]x_i∈[0,1] and that for 0<c<k0<c<k we have (1−ck)k−c=((1−ck)k/c−1)c≥1/ec (1- ck )^k-c= ( (1- ck )^k/c-1 )^c≥ 1/e^c owing to (1−1/x)x−1≥1/e(1-1/x)^x-1≥ 1/e for x>1x>1. Denote the decrease of dtd_t as a failure. In the following we condition on the event that no failure occurs which happens with probability at least Ω(1) (1) and we estimate the expected time until the optimum is found. To succeed, one may increase dtd_t at most r times if dt<2rd_t<2r (resulting in a value of dt=2rd_t=2r) and then derive the all one string. By Lemma 3.5(1), an increase of dtd_t happens with probability at least pc⋅pfu⋅13en⋅2dt(1−1μ)≥pc⋅pfu⋅16en⋅2dt. p_c· p_fu· 13en· 2^d_t (1- 1μ )≥ p_c· p_fu· 16en· 2^d_t. Hence, the total expected waiting time (conditioned on the event that no failure occurs) until there is a pair of individuals with distance 2r2r is at most a partial sum of the geometric series ∑i=0r−16en22ipcpfu _i=0^r-1 6en2^2ip_cp_fu ≤6enpcpfu∑i=0r−14i=O(4rnpcpfu). ≤ 6enp_cp_fu _i=0^r-14^i=O ( 4^rnp_cp_fu ). When dt≥2rd_t≥ 2r, the optimum is created with probability at least pc⋅pfu⋅14r1enk−r. p_c· p_fu· 14^r 1en^k-r. Then the expected waiting time to generate the all-ones string is at most O(nk−r4r/(pcpfu))O(n^k-r4^r/(p_cp_fu)). Therefore, the expected waiting time in total is at most O(4rnpcpfu+nk−r4rpcpfu)=O(nk−r4rpcpfu). O ( 4^rnp_cp_fu+ n^k-r4^rp_cp_fu )=O ( n^k-r4^rp_cp_fu ). If a failure occurs (i.e. dtd_t decreases during the run), we repeat the above arguments and need another period of O(nk−r4r/(pcpfu))O(n^k-r4^r/(p_cp_fu)) iterations in expectation if no further failure occurs. Hence, the bound on the expected number of iterations follows by multiplying the above with O(1)O(1), noting that in expectation, O(1)O(1) repetitions are sufficient. ∎ Note that the population size in Theorem 3.6 depends only logarithmically on n, but exponentially on k. If k=O(1)k=O(1) and pcpfu∈Ω(1)p_cp_fu∈ (1), a population size of O(log(n))O( (n)) suffices to escape the plateau in expected O(n)O(n) iterations. Even for k=ω(1)k=ω(1), pcpfu∈Ω(1)p_cp_fu∈ (1) and μ=c⋅4klog(n)μ=c· 4^k (n) we get a runtime bound of O(4k⋅n)O(4^k· n) to create 1n1^n. Moreover, it is only by a factor of n worse than the bound Ω(4k) (4^k), which is the best possible lower bound achievable by a broad class of (μ+1)(μ+1) GAs to escape the plateau (namely, by elitist algorithms that use any type of parent selection and perform either standard bit mutation alone or uniform crossover followed by standard bit mutation in a single iteration (Opris et al., 2025a, Theorem 5.5)) 4. Furthest Parent Selection Is Also Helpful at Hill Climbing In this section, we show that in addition to diversifying the population of the (μ+1) GA, furthest parent selection also helps at optimizing easy monotonic problems. For this, we estimate the runtime of the algorithm on Jumpk until it gets the whole population on the plateau starting from a random population (which is the most common way to initialize the algorithm). Lemma 4.1. Consider the (μ+1) GA with furthest parent selection on Jumpk with 2≤k≤n/22≤ k≤ n/2 and crossover probability 0<pc≤10<p_c≤ 1. Then the expected number of fitness evaluations made by the algorithm before the whole population is on the plateau is O(nμpcpfu+nlog(nk)).O ( nμp_cp_fu+n ( nk) ). The proof of this lemma is based on the following lemma that estimates the probabilities of creating a crossover offspring that is better than the worst of its parents. Lemma 4.2. Let f denote the Jumpk function and let x and y be two arbitrary different individuals such that f(y)≤f(x)f(y)≤ f(x), f(x)<n+kf(x)<n+k (x is not the global optimum) and f(y)<nf(y)<n (y is not a local optimum). Let z be the result of uniform crossover between x and y. There exist constants c1,c2,c3>0c_1,c_2,c_3>0 that do not depend on x and y such that (1) if f(y)≤n−8kf(y)≤ n-8 k, then Pr[f(z)>f(y)]≥c1 [f(z)>f(y)]≥ c_1; (2) if f(y)>n−8kf(y)>n-8 k, then Pr[f(z)>f(y)]≥c2k [f(z)>f(y)]≥ c_2 k; (3) Pr[f(z)>f(y)−k]≥c3 [f(z)>f(y)- k]≥ c_3, even if f(y)=nf(y)=n. Proof. We distinguish several cases depending on the fitness of y. First, we consider y with the worst fitness values, when it is in the fitness valley between local optima and the global optimum. In the second case, y is on the main slope of Jumpk, but not too close to the local optima, namely, in distance more than 8k8 k from any of them. Finally, we consider the case when y is close to local optima. These cases are illustrated in Figure 2. Note that the first two cases cover statement (1) of the lemma. The last case covers statement (2). And statement (3) will be covered by all three cases together. |x|1|x|_1Jumpk(x) Jump$_k$(x)n−kn-kkknnn−8kn-8 kn+kn+k8k8 kCase 1Case 2Case 3Local and global optima Figure 2. Illustration of the fitness values that correspond to different cases considered in the proof of Lemma 4.2. Case 1: y in the valley. In this case, x has at least as many zero-bits as y (since f(x)≥f(y)f(x)≥ f(y)), and to create a strictly better offspring z, we need z to have strictly more zero-bits than y. Let D be the set of positions in which x and y differ (since x≠yx≠ y, D≠∅D≠ ), and let Δ=|D|>0 =|D|>0. The crossover offspring z coincides with y (and x) in all positions from [n]∖D[n] D, and in each position in D it has either zero or one with equal probability (independently from other positions). Since f(x)≥f(y)f(x)≥ f(y), there are at most Δ2 2 zero-bits in y in positions in D (that is, |y|0D≤Δ2|y|_0^D≤ 2). Hence, if in z more than half of bits in positions in D are zeros (that is, |z|0D>Δ2|z|_0^D> 2), then z has a strictly better fitness than y. Since |z|0D|z|_0^D follows a binomial distribution Bin(Δ,12)Bin( , 12), by Lemma 2.4 we have Pr[|z|0D>Δ2]≥12(1−1π)≕c1′, [|z|_0^D> 2]≥ 12 (1- 1π ) c_1 , which is a candidate to be c1c_1 from the first lemma statement. Since Pr[f(z)>f(y)−k]≥Pr[f(z)>f(y)] [f(z)>f(y)- k]≥ [f(z)>f(y)], the same lower bound on this probability applies, hence c1′c_1 is also a candidate for c3c_3 from the third statement. Case 2: y is in the main slope, but not too close to the local optima. More precisely, we assume that |y|1≤n−k−8k|y|_1≤ n-k-8 k. In this case, x has at least as many one-bits as y (contrary to the previous case, since the slope points in the opposite direction). To create a better offspring z, we need to have strictly more one-bits than in y, but we also need to have |z|1≤n−k|z|_1≤ n-k, since otherwise z is in the fitness valley, and therefore its fitness is worse than the fitness of y (note that we pessimistically disregard an unlikely event of z being the global optimum). Therefore, the probability of z being strictly better than y is at least the probability of z having more one-bits than y minus the probability of z having more than n−kn-k one-bits. The former can be bounded similar to the previous case, but swapping zero-bits and one-bits in all arguments, hence this probability is at least c1′c_1 . We now bound the probability of z having more than n−kn-k one-bits. We do it in two steps. First, we show that this is a sub-event of crossover taking no more than Δ2+2Δ 2+2 one-bits in positions in D. Then, we bound the probability of this sub-event via Chernoff bounds. Let D¯ D be a complement of D to [n][n], that is, D¯=[n]∖D D=[n] D. Note that |x|1D¯=|y|1D¯=|z|1D¯|x|_1 D=|y|_1 D=|z|_1 D and that |x|1D=Δ−|y|1D|x|_1^D= -|y|_1^D, hence we have |x|1=|x|1D+|x|1D¯=Δ−|y|1D+|y|1D¯=|y|1−2|y|1D+Δ, |x|_1=|x|_1^D+|x|_1 D= -|y|_1^D+|y|_1 D=|y|_1-2|y|_1^D+ , therefore, |x|1+|y|12=|y|1−|y|1D+Δ2=|y|1D¯+Δ2=|z|1D¯+Δ2. |x|_1+|y|_12=|y|_1-|y|_1^D+ 2=|y|_1 D+ 2=|z|_1 D+ 2. Using this, we can write (5) |z|1=|z|1D+|z|1D¯=|z|1D+|x|1+|y|12−Δ2. |z|_1=|z|_1^D+|z|_1 D=|z|_1^D+ |x|_1+|y|_12- 2. Note that x is not the global optimum, hence |x|1≤n−k|x|_1≤ n-k. Also note that Δ is at most |y|0+|x|0≤2|y|0|y|_0+|x|_0≤ 2|y|_0 (since in positions that are not zero in y and that are not zero in x they both have a one-bit, hence this position is not in D). Then, if we assume that |z|1D≤Δ2+2Δ|z|_1^D≤ 2+2 , then we have (6) |z|1≤n−k+|y|12+2Δ≤(n−k)−(n−k)−|y|12+22|y|0=(n−k)−|y|0−k2+22|y|0. split|z|_1&≤ n-k+|y|_12+2 \\ &≤(n-k)- (n-k)-|y|_12+2 2|y|_0\\ &=(n-k)- |y|_0-k2+2 2|y|_0. split By solving a quadratic inequality, one can see that |y|0−k2≥22|y|0 |y|_0-k2≥ 2 2|y|_0 if |y|0≥k+16+42k+16|y|_0≥ k+16+4 2k+16. For k≥100k≥ 100 we have that k+16+42k+16≥k+8k+16+4 2k+16≥ k+8 k and therefore |y|0≥k+8k|y|_0≥ k+8 k. Hence, from |z|1D≤Δ2+2Δ|z|_1^D≤ 2+2 it follows that |z|1≤n−k|z|_1≤ n-k. We only need to estimate the probability of the former event. Since |z|1D|z|_1^D follows a binomial distribution Bin(Δ,12)Bin( , 12) with expectation Δ2 2, the probability that |z|1D|z|_1^D exceeds Δ2+2Δ 2+2 can be bounded via Chernoff bounds. Pr[|z|1D>Δ2+2Δ] [|z|_1^D> 2+2 ] =Pr[|z|1D>E[|z|1D](1+4Δ)] = [|z|_1^D>E[|z|_1^D] (1+ 4 )] ≤exp(−(4Δ)2Δ23)=e−8/3. ≤ (- ( 4 )^2 23 )=e^-8/3. Thus, if k≥100k≥ 100, then the probability that |y|1<|z|1≤n−k|y|_1<|z|_1≤ n-k is at least c1′−e−8/3=12(1−1π)−e−8/3≥0.148≕c1′. c_1 -e^-8/3= 12 (1- 1π )-e^-8/3≥ 0.148 c_1 . Finally, we treat small values of k<100k<100. All arguments up to eq. (6) work for them as well, but |y|0−k2≥22|y|0 |y|_0-k2≥ 2 2|y|_0 holds only when |y|0≥k+16+42k+16|y|_0≥ k+16+4 2k+16 (which for k<100k<100 is not necessarily larger than k+8k+8 k). In these small distances from the global optimum we have Δ≤2|y|0=O(1) ≤ 2|y|_0=O(1), hence the probability Pr[|z|1D=|y|1D+1] [|z|_1^D=|y|_1^D+1] is at least some constant (independent of n and k). Denote this constant by c1′c_1 . Uniting cases 1 and 2. We now have Pr[f(z)>f(y)]≥minc1′,c1′,c1′≕c1, [f(z)>f(y)]≥ \c_1 ,c_1 ,c_1 \ c_1, which completes the proof of the first statement. Note that c1c_1 also bounds Pr[f(z)>f(y)−k] [f(z)>f(y)- k] for all y such that f(y)≤n−8kf(y)≤ n-8 k, hence it is our candidate for c3c_3. Case 3: y is close to the local optima. Namely, in this case we assume that n−k−8k<|y|1<n−kn-k-8 k<|y|_1<n-k. In this case, we utilize Lemma 2.5. Note that we have |x|0≤|y|0≤k+8k|x|_0≤|y|_0≤ k+8 k, hence the distance between them is at most Δ≤2k+16k≤18k ≤ 2k+16 k≤ 18k. In this case, to create a strictly better individual, it is sufficient to have |z|1D=⌊Δ2⌋+1|z|_1^D= 2 +1, since, similar to eq. (5), it implies |z|1=|x|1+|y1|2+1−[Δ is odd] |z|_1= |x|_1+|y_1|2+1-[ is odd] where [Δ is odd]=1[ is odd]=1 if Δ is odd, and 0 otherwise. If |x|1=|y|1|x|_1=|y|_1 (which implies that Δ is even), then |z|1=|y|1+1|z|_1=|y|_1+1, and since y is not in the local optimum, z does not fall to the fitness valley. Otherwise, this implies |y|1<|z|1≤|x|1|y|_1<|z|_1≤|x|_1, hence z is also better than y and does no fall into the fitness valley. We now estimate the probability of |z|1D=⌊Δ2⌋+1|z|_1^D= 2 +1. If Δ is even, by Lemma 2.5, this probability is at least (Δ2+1)2−Δ=(Δ2+1Δ⋅Δ)2−Δ≥12πΔe4/Δ, 2+12^- = 2+ 1 · 2^- ≥ 12 π e^4/ , and if Δ is odd, then it is at least (Δ2+12)2−Δ=(Δ2+12Δ⋅Δ)2−Δ≥12πΔe2/Δ, 2+ 122^- = 2+ 12 · 2^- ≥ 12 π e^2/ , Since Δ≤18k ≤ 18k, in both cases this is at least 12πΔe4≥1218πke4=c2k, 12 π e^4≥ 12 18π ke^4= c_2 k, where we define c2≔162πe4c_2 16 2πe^4. Also, in this sub-case, by Lemma 2.5 for all i∈[0..⌊Δ⌋]i∈[0.. ] the probability that |z|1D=⌈Δ2⌉−i|z|_1^D= 2 -i is at least (Δ⌈Δ2⌉−i)2−Δ=(Δ⌈Δ2⌉−iΔ⋅Δ)2−Δ≥12πΔe4i/Δ≥12πΔe4. 2 -i2^- = 2 - i · 2^- ≥ 12 π e^4i/ ≥ 12 π e^4. Hence, recalling that Δ≤18k ≤ 18k, we have Pr[f(z)>f(y)−k] [f(z)>f(y)- k] ≥Pr[f(z)>f(y)−Δ18] ≥ [f(z)>f(y)- 18] ≥∑i=0⌊Δ18⌋Pr[|z|1D=⌈Δ2⌉−i] ≥ _i=0 18 [|z|_1^D= 2 -i] ≥Δ18⋅12πΔe4=16e42π≕c3′. ≥ 18· 12 π e^4= 16e^4 2π c_3 . Taking c3≔minc1,c3′c_3 \c_1,c_3 \ completes the proof of the last statement. ∎ With Lemma 4.2, we can prove Lemma 4.1. Proof of Lemma 4.1. Enumerate the fitness values of Jumpk by a0,a1,…,ana_0,a_1,…,a_n in increasing order (that is, ana_n is the optimal value n+kn+k and an−1a_n-1 is the value at local optima n). For each i∈0,…,ni∈\0,…,n\ and j∈0,…,μ−1j∈\0,…,μ-1\, we say that a population PtP_t is in state (i,j)(i,j) if all individuals in PtP_t have fitness at least aia_i, and exactly j individuals have fitness strictly greater than aia_i. We aim to estimate the time until the algorithm reaches a population in a state (i,j)(i,j) with i≥n−1i≥ n-1, which means that all individuals are either on the plateau or are optimal. We call such states target states. Note that the state of the population can only improve over time, where we define state (i,j)(i,j) to be better than state (ℓ,m)( ,m) if i>ℓi> , or if i=ℓi= and j>mj>m (that is, they are ordered lexicographically). Since states are attained in a non-decreasing order, each state is visited at most once, hence the time to reach a target state can be bounded by the sum of the times required to leave each non-target state. To estimate the time to leave a given state, we provide lower bounds on the probability of leaving that state in a single iteration. We distinguish two cases: when the population consists only of copies of the same individual, and when there are several different genotypes in the population. Case 1: population of copies. This is possible only in states (i,0)(i,0). To escape this state the algorithm has to create a strictly better individual. It is possible by either performing a mutation-only iteration, where the algorithm flips one bit leading to a better state, or by a crossover iteration, where mutation after crossover does the same (note that the result of crossover will be identical to its parents, since the parents are identical). Therefore, for states (i,0)(i,0) with i<k−2i<k-2 (representing the fitness valley), the probability of escaping in one iteration is the probability that mutation flips one of (n−i+1)(n-i+1) one-bits (and does not flip any other bit), that is, (n−(i+1))n(1−1n)n−1≥(n−k+1)en≥12e. (n-(i+1))n (1- 1n )^n-1≥ (n-k+1)en≥ 12e. Similarly, the probability to escape a state (i,0)(i,0) where i≥k−1i≥ k-1 is at least (n−(i−(k−1)))n(1−1n)n−1≥(n−i+k−1)en. (n-(i-(k-1)))n (1- 1n )^n-1≥ (n-i+k-1)en. Case 2: diverse population. In this case, if the algorithm performs crossover and furthest parent selection, then it definitely chooses different individuals as parents. The algorithm escapes the current state, if it creates an individual that is strictly better than the worst individual in the population (since it either increases i or j). We will use Lemma 4.2 to estimate the probability to create such offspring. We consider two sub-cases depending on the worst fitness in the population. In both sub-cases we count on the algorithm to perform a crossover iteration with furthest parent selection (this occurs with probability pcpfup_cp_fu) and on mutation to flip no bits (this occurs with probability (1−1n)n≥14(1- 1n)^n≥ 14). Sub-case 2.1: i<n−9ki<n-9 k. This implies that the worst fitness in the population is at most n−9kn-9 k. Then let y be the worst of two parents chosen for crossover. If f(y)≤n−8kf(y)≤ n-8 k, then by Lemma 4.2 (1) with probability c1c_1 we create an offspring that is better than y, hence it is better than the worst individual in the population. Otherwise, if f(y)>n−8kf(y)>n-8 k, then by Lemma 4.2 (3) we create an offspring z with fitness larger than f(y)−k>n−9k>if(y)- k>n-9 k>i with probability at least c3c_3. Therefore, in this sub-case, the probability to escape the current state is at least pcpfu4minc1,c3 p_cp_fu4 \c_1,c_3\. Sub-case 2.2: i≥n−9ki≥ n-9 k. In this case, by Lemma 4.2 (1) and (2), the probability to create an offspring that is better than the worst of the parents (and hence, its fitness is better than the worst fitness in the population) is at least minc1,c2k \c_1, c_2 k\. Therefore, probability to escape the current state is at least pcpfu4minc1,c2k p_cp_fu4 \c_1, c_2 k\ Now, if we denote by pi,jp_i,j the probability to escape state (i,j)(i,j) in one iteration (which we estimated above), then the expected time until it happens is 1pi,j 1p_i,j. Summing these expected times over all states with i<n−1i<n-1, we can obtain on upper bound on time until the whole population is on the plateau. We split this sum into several parts, and in the following we use 1min(a,b)≤1a+1b 1 (a,b)≤ 1a+ 1b for multiple times. First, for i<k−2i<k-2 we have ∑i=0k−3 _i=0^k-3 (11/(2e)+∑j=1μ−11pcpfu4minc1,c3) ( 11/(2e)+ _j=1^μ-1 1 p_cp_fu4 \c_1,c_3\ ) ≤∑i=0k−3(2e+∑j=0μ−11pcpfu4minc1,c3)=O(k+kμpcpfu). ≤ _i=0^k-3 (2e+ _j=0^μ-1 1 p_cp_fu4 \c_1,c_3\ )=O (k+ kμp_cp_fu ). Then, for i∈[k−2..n−⌊9k⌋−1]i∈[k-2..n- 9 k -1] we have ∑i=k−2n−⌊9k⌋−1 _i=k-2^n- 9 k -1 (1n−i+k−1en+∑j=1μ−11pcpfu4minc1,c3) ( 1 n-i+k-1en+ _j=1^μ-1 1 p_cp_fu4 \c_1,c_3\ ) ≤∑i=k−2n−⌊9k⌋−1(en(n−i+k−1)+∑j=0μ−14pcpfuminc1,c3) ≤ _i=k-2^n- 9 k -1 ( en(n-i+k-1)+ _j=0^μ-1 4p_cp_fu \c_1,c_3\ ) =O(nlog(nk)+nμpcpfu). =O (n ( nk)+ nμp_cp_fu ). Finally, for larger i we have ∑i=n−⌊9k⌋n−2 _i=n- 9 k ^n-2 (1n−i+k−1en+∑j=1μ−11pcpfu4minc1,c2k) ( 1 n-i+k-1en+ _j=1^μ-1 1 p_cp_fu4 \c_1, c_2 k\ ) ≤∑i=n−⌊9k⌋n−2(en(n−i+k−1)+∑j=0μ−14pcpfuminc1,c2k) ≤ _i=n- 9 k ^n-2 ( en(n-i+k-1)+ _j=0^μ-1 4p_cp_fu \c_1, c_2 k\ ) =O(n+kμ⋅kpcpfu)=O(n+kμpcpfu) =O (n+ kμ· kp_cp_fu )=O (n+ kμp_cp_fu ) Summing these three bounds, we complete the proof. ∎ We note that it is difficult to make a meaningful comparison between the bound from Lemma 4.1 and the runtime of the vanilla (μ+1) GA with uniform parent selection, as there is limited prior work analyzing its behavior on such easy-to-climb landscapes. The closest related result for the vanilla (μ+1) GA is the analysis on the OneMax benchmark (essentially, Jumpk with k=1k=1) provided by Corus and Oliveto (2020) who proved a O(nlog(n))O(n (n)) runtime, but only for small values of μ=o(log(n))μ=o( (n)). Our result indicates that the furthest parent selection with pcpfu=Ω(1)p_cp_fu= (1) has a similar performance (in asymptotic sense) for such small population sizes. It is also notable that Witt (2006) showed Θ(nlog(n)+μn) (n (n)+μ n) runtime of the mutation-only (μ+1) EA, which is the same as our upper bound for the (μ+1) GA with furthest parent selection. This is good news for our algorithm, since it is known that some parent selection methods can slow down evolutionary algorithms. For example, the parent selection for the mutation-only (μ+1) EA proposed in (Corus et al., 2021) is slower on OneMax, solving it in Θ(μnlog(n)) (μ n (n)) (despite this, that selection was shown to be very helpful at avoiding premature convergence to local optima). Now we are able to combine Lemma 4.1 with Theorem 3.6 to derive the total runtime of the (μ+1) GA with furthest parent selection on Jumpk. Corollary 4.3. Consider the (μ+1) GA with furthest parent selection on Jumpk for 2≤k≤n/32≤ k≤ n/3. Let r∈[k−1]r∈[k-1]. Suppose μ≥c⋅4r(k−r)log(n)/(pcpfu)μ≥ c· 4^r(k-r) (n)/(p_cp_fu) for a sufficiently large constant c. Then the expected number of fitness evaluations that the algorithm takes to find the global optimum is O(nμ/(pcpfu)+4r⋅nk−r/(pcpfu))O(nμ/(p_cp_fu)+4^r· n^k-r/(p_cp_fu)). Proof. We need expected O(nμ/(pcpfu)+nlog(n))O(nμ/(p_cp_fu)+n (n)) fitness evaluations until the whole population is on the plateau by Lemma 4.1. Then, by Theorem 3.6, we need further O(4r⋅nk−r/(pcpfu))O(4^r· n^k-r/(p_cp_fu)) fitness evaluations in expectation to find the all-ones string. Summing up both runtimes provides the result, noting that the term nlog(n)n (n) is absorbed by nμ/(pcpfu)nμ/(p_cp_fu) since k−r≥1k-r≥ 1. ∎ For the smallest possible value of μ and for r=k−1r=k-1, this upper bound is simplified to O(4knlog(n)(pcpfu)2)O( 4^kn (n)(p_cp_fu)^2), which is O(4knlog(n))O(4^kn (n)) when pcpfu=Ω(1)p_cp_fu= (1). Comparing it to the O(nk−1)O(n^k-1) bound proved by Doerr et al. (2024a) for the vanilla (μ+1) GA, one can see that our bound is by factor Θ((pcpfu)2nk−24klog(n)) ( (p_cp_fu)^2n^k-24^k (n)) smaller. Interestingly, this significant performance boost is comparable with the boost of diversity mechanisms studied by Dang et al. (2018) that do not allow to accept individuals that reduce diversity while breaking ties between individuals with equal fitness. However, in contrast with these mechanisms, parent selection does not impose constraints on the search process by stricter offspring selection, but on the contrary it increases the variance of the crossover outcomes, allowing better exploration of the search space. 5. Conclusion In this paper, we have performed runtime analysis of the (μ+1) GA with parent selection mechanism that prioritizes the most distant parents in iterations with crossover on the Jumpk benchmark. This analysis is powered by the introduced diversity measure which simultaneously captures the maximum distance dtd_t between individuals in the population and the number of pairs mtm_t of individuals in that distance. Our analysis revealed complex population dynamics that could be described thanks to this measure. Despite the diversity of the population can decrease sometimes, the proposed parent selection mechanism makes events of significant decrease (when dtd_t decreases) very unlikely, so they rarely happen before we find the optimum. Interestingly, a similar picture was reported by Doerr et al. (2024a) in their experimental study of the vanilla (μ+1) GA: the maximum distance between individuals of population grew over time, and on each level of diversity the algorithm’s position was solidified by creating more pairs of individuals in that distance. Although the role of crossover in diversifying the population and in enhancing hill-climbing that we observed in this paper has been magnified by parent selection, that empirical result makes us believe that similar dynamics also arise in the vanilla (μ+1) GA. Thus, we are optimistic that the results of this paper also bring us closer to the understanding of the effectiveness of this classic GA and, more broadly, of population dynamics in crossover-based algorithms. Acknowledgements.The authors thank Timo Kötzing, and Aishwarya Radhakrishnan for their contributions to the early stages of this project, including initiating the study and valuable discussions. We also acknowledge funding by the European Union (ERC, “dynaBBO”, grant no. 101125586). References D. Antipov and B. Doerr (2021) A tight runtime analysis for the (μ+λ)(μ+λ) EA. Algorithmica 83, p. 1054–1095. Cited by: §1. G. Badkobeh, P. K. Lehre, and D. Sudholt (2015) Black-box complexity of parallel search with distributed populations. In Foundations of Genetic Algorithms (FOGA 2015), p. 3–15. Cited by: Lemma 2.2. J. E. Baker (1989) An analysis of the effects of selection in genetic algorithms. Ph.D. Thesis, Vanderbilt University. Cited by: §1.2. C. Bian and C. Qian (2022) Better running time of the non-dominated sorting genetic algorithm I (NSGA-I) by using stochastic tournament selection. In Parallel Problem Solving from Nature (PPSN 2022), p. 428–441. Cited by: §1.2. S. Cerf and J. Lengler (2024) How population diversity influences the efficiency of crossover. In Parallel Problem Solving from Nature (PPSN 2024), p. 102–116. Cited by: §1.2. D. Corus, D. Dang, A. V. Eremeev, and P. K. Lehre (2018) Level-based analysis of genetic algorithms and other search processes. IEEE Transactions on Evolutionary Computation 22 (5), p. 707–719. External Links: Document Cited by: §1.2, §1. D. Corus, A. Lissovoi, P. S. Oliveto, and C. 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 Optimization 1 (1), p. 1–38. Cited by: §1.2, §2.2, §4. D. Corus, P. S. Oliveto, and F. Zheng (2025) Hybrid selection allows steady-state evolutionary algorithms to control the selective pressure in multimodal optimisation. In Genetic and Evolutionary Computation Conference (GECCO 2025), p. 881–889. Cited by: §1.2. D. Corus and P. S. Oliveto (2020) On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms. Algorithmica 82 (12), p. 3676–3706. Cited by: §1.2, §1, §4. E. Covantes Osuna, W. Gao, F. Neumann, and D. Sudholt (2018) Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation. Theoretical Computer Science 832, p. 123–142. Cited by: §1.2. D. Dang, A. V. Eremeev, P. K. Lehre, and X. Qin (2022) Fast non-elitist evolutionary algorithms with power-law ranking selection. In Genetic and Evolutionary Computation Conference (GECCO 2022), p. 1372–1380. Cited by: §1.2, §2.2, §2.2. D. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton (2018) Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation 22 (3), p. 484–497. Cited by: §1.2, §1.2, §4. D. Dang, T. Friedrich, M. S. Krejca, T. Kötzing, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton (2016) Escaping local optima with diversity-mechanisms and crossover. In Genetic and Evolutionary Computation Conference (GECCO 2016), p. 645–652. Cited by: §1.2, §1, §1, §3. D. Dang, A. Opris, and D. Sudholt (2024) Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. Artificial Intelligence 330, p. 104098. Cited by: §1.2. B. Doerr, C. Doerr, and J. Yang (2020) Optimal parameter choices via precise black-box analysis. Theoretical Computer Science 801, p. 1–34. External Links: Document, Link Cited by: §1. B. Doerr, A. Echarghaoui, M. Jamal, and M. S. Krejca (2024a) Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations. In Conference on Artificial Intelligence (AAAI 2024), Cited by: §1.2, §3, §4, §5. B. Doerr, E. Happ, and C. Klein (2012) Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425 (0), p. 17–33. Cited by: §1.2. B. Doerr and Z. Qu (2023a) From understanding the population dynamics of the NSGA-I to the first proven lower bounds. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, p. 12408–12416. Cited by: §1. B. Doerr and Z. Qu (2023b) Runtime analysis for the NSGA-I: provable speed-ups from crossover. In Conference on Artificial Intelligence, (AAAI 2023), p. 12399–12407. Cited by: §1.2. B. Doerr and M. Theile (2009) Improved analysis methods for crossover-based algorithms. In Genetic and Evolutionary Computation Conference, (GECCO 2009), p. 247–254. Cited by: §1.2. B. Doerr and C. Winzen (2014) Ranking-based black-box complexity. Algorithmica 68 (3), p. 571–609. Cited by: §2.3, Lemma 2.5. B. Doerr (2020a) Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, p. 1–87. Cited by: §2.3. C. Doerr, D. A. Janett, and J. Lengler (2024b) Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions. Algorithmica 86 (10), p. 3115–3152. Cited by: §1. C. Doerr (2020b) Complexity theory for discrete black-box optimization heuristics. In Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, B. Doerr and F. Neumann (Eds.), Natural Computing Series, p. 133–212. Cited by: §1. W. Feller (1968) An introduction to probability theory and its applications. John Wiley & Sons. Cited by: §2.3, Lemma 2.1. S. Fischer and I. Wegener (2005) The one-dimensional Ising model: Mutation versus recombination. Theoretical Computer Science 344 (2–3), p. 208–225. Cited by: §1.2. D. E. Goldberg and K. Deb (1990) A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms (FOGA 1990), p. 69–93. Cited by: §1.2. T. Jansen and D. Sudholt (2005) Design and analysis of an asymmetric mutation operator. In Congress on Evolutionary Computation (CEC 2005), p. 497–504. Cited by: §1.2. T. Jansen and I. Wegener (1999) On the analysis of evolutionary algorithms - A proof that crossover really can help. In European Symposium on Algorithms (ESA 1999), J. Nesetril (Ed.), p. 184–193. Cited by: §1.2, §1. T. Jansen and I. Wegener (2002) On the analysis of evolutionary algorithms – a proof that crossover really can help. Algorithmica 34 (1), p. 47–66. Cited by: §1.2, §1.2. T. Kötzing, D. Sudholt, and M. Theile (2011) How crossover helps in pseudo-boolean optimization. In Genetic and Evolutionary Computation Conference (GECCO 2011), p. 989–996. Cited by: §1.2. T. Kötzing (2016) Concentration of first hitting times under additive drift. Algorithmica 75, p. 490 – 506. Cited by: §2.3. M. Laumanns, L. Thiele, and E. Zitzler (2004) Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. Evolutionary Computation 8 (2), p. 170–182. Cited by: §1.2. P. K. Lehre (2011) Fitness-levels for non-elitist populations. In Genetic and Evolutionary Computation Conference (GECCO 2011), p. 2075–2082. Cited by: §1.2, §2.2. J. Lengler (2020) A general dichotomy of evolutionary algorithms on monotone functions. IEEE Transactions on Evolutionary Computation 24 (6), p. 995–1009. Cited by: §1. T. Motoki (2002) Calculating the expected loss of diversity of selection schemes. Evolutionary Computation 10 (4), p. 397–422. Cited by: §1.2. G. Ochoa, M. Tomassini, S. Vérel, and C. Darabos (2008) A study of NK landscapes’ basins and local optima networks. In Genetic and Evolutionary Computation Conference, (GECCO 2008), p. 555–562. Cited by: §1. A. Opris, J. Lengler, and D. Sudholt (2024) A tight O(4k/pc4^k/p_c) runtime bound for a (μ+1)-GA on Jump for realistic crossover probabilities. In Genetic and Evolutionary Computation Conference (GECCO 2024), p. 1605–1613. Cited by: §1.2. A. Opris, J. Lengler, and D. Sudholt (2025a) Achieving tight O(4k)O(4^k) runtime bounds on jumpk by proving that genetic algorithms evolve near-maximal population diversity. Algorithmica, p. 1432–1541. Cited by: §1.2, §3. A. Opris, S. Sonntag, and D. Sudholt (2025b) A royal road function for permutation spaces: an example where order crossover is provably essential. In Genetic and Evolutionary Computation Conference (GECCO 2025), New York, NY, USA, p. 1631–1640. Cited by: §1.2. A. Opris (2025) Towards a rigorous understanding of the population dynamics of the nsga-i: tight runtime bounds. External Links: 2511.07125, Link Cited by: §1. A. Opris (2026) Many-objective problems where crossover is provably essential. Artificial Intelligence 350, p. 104453. Cited by: §1.2. G. Pavai and T. V. Geetha (2016) A survey on crossover operators. ACM Comput. Surv. 49 (4). External Links: ISSN 0360-0300 Cited by: §1. S. Ren, Z. Qiu, C. Bian, M. Li, and C. Qian (2024) Maintaining diversity provably helps in evolutionary multimodal optimization. In International Joint Conference on Artificial Intelligence (IJCAI 2024), p. 7012–7020. Cited by: §1.2. D. Sudholt (2005) Crossover is provably essential for the Ising model on trees. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005), p. 1161–1167. Cited by: §1.2. I. Wegener (2002) Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In Evolutionary Optimization, R. Sarker, X. Yao, and M. Mohammadian (Eds.), p. 349–369 (english). Cited by: §3. C. Witt (2006) Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation 14 (3), p. 484–497. External Links: Document Cited by: §4.