# Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic
Algorithm

Benjamin Doerr1 Aymen Echarghaoui2 Mohammed Jamal2 Martin S. Krejca1

( 1Laboratoire d’Informatique (LIX), CNRS, École Polytechnique,
Institut Polytechnique de Paris, Palaiseau, France
2École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France )

###### Abstract

Most evolutionary algorithms (EAs) used in practice employ crossover. In
contrast, only for few and mostly artificial examples a runtime advantage from
crossover could be proven with mathematical means. The most convincing such
result shows that the $(\mu+1)$ genetic algorithm (GA) with population size
$\mu=O(n)$ optimizes jump functions with gap size $k\geq 3$ in time
$O(n^{k}/\mu+n^{k-1}\log n)$, beating the $\Theta(n^{k})$ runtime of many
mutation-based EAs. This result builds on a proof that the GA occasionally and
then for an expected number of $\Omega(\mu^{2})$ iterations has a population
that is not dominated by a single genotype.

In this work, we show that this diversity persist with high probability for a
time exponential in $\mu$ (instead of quadratic). From this better
understanding of the population diversity, we obtain stronger runtime
guarantees, among them the statement that for all $c\ln(n)\leq\mu\leq n/\log
n$, with $c$ a suitable constant, the runtime of the $(\mu+1)$ GA on
$\textsc{Jump}_{k}$, with $k\geq 3$, is $O(n^{k-1})$. Consequently, already
with logarithmic population sizes, the GA gains a speed-up of order
$\Omega(n)$ from crossover.

##  1 Introduction

In the vast majority of applications of evolutionary algorithms (EAs),
crossover is employed. This is natural since EAs are inspired by natural
evolution. However, since the ultimate goal of EAs is not to mimic evolution
but to compute good solutions for a given problem, one could wonder if there
is a real justification for the use of crossover, or, asking the question in a
less absolute manner, the questions are for which problems crossover can speed
up evolutionary algorithms, what are the reasons for the possible performance
gains through crossover, and what is the best way to employ crossover
(parameters, crossover operators, etc.).

With their fundamental nature, these are all question one could try to answer
via theoretical means, e.g., via mathematical runtime analyses [5, 20, 25,
35], which have given many important insights and explanations in the past.
Unfortunately, when it comes to understanding crossover, the mathematical
runtime analysis area was not very successful (but we note that other attempts
to understand crossover, e.g., the building block hypothesis [23] also
struggled to explain crossover [32]).

The main difficulty towards understanding crossover via mathematical tools are
the usually complicated population dynamics. We note that even when only
regarding mutation-based algorithms, still the majority of runtime analyses
regards algorithms with trivial populations such as _randomized local search_
or the ${(1+1)}$ EA [20]. The particular difficulty when adding crossover is
that we need to understand the diversity of the population. Crossover can only
be really effective when sufficiently different, good solutions are available.
That this is the core problem is easily visible from the existing runtime
analyses of crossover-based algorithms. We refer to Section 2 for a more
detailed discussion and give only few examples here. That diversity, more
precisely, arriving at a state with a diverse population, is the crucial
ingredient for profiting from crossover was already discussed very clearly in
the first runtime analysis of a crossover-based algorithm [27], which analyzes
how the $(\mu+1)$ genetic algorithm (GA) optimizes the Jump benchmark. Since
crossover can also contribute towards losing diversity, the positive results
shown in [27] are only valid for an unrealistically small crossover rate.
Doerr, Happ, and Klein [18], without adding uncommon assumptions, show an
advantage of crossover when solving the all-pairs-shortest-path problem, but
it is clear that this problem, asking for a short path between any two
vertices, just in the problem definition contains a strong diversity mechanism
that prevents the population from converging to a single genotype.

The maybe most convincing work proving an advantage from crossover by Dang et
al. [10], where again the ${(\mu+1)}$ GA optimizing Jump functions is
regarded. Interestingly, without particular modifications of the algorithm,
the authors manage to show that it repeatedly arrives at diverse populations
and keeps this diversity for a moderate time. More precisely, when optimizing
a jump function with gap size $k$, then after an expected time of $O(n\mu/k)$
iterations, the algorithm reaches a state where the largest genotype class in
the population contains at most $\mu/2$ individuals. This diversity of the
largest genotype class missing a constant fraction of the population stays for
an expected $O(\mu^{2})$ iterations. Given these numbers, the best runtime
results are obtained for a relatively large population size of $\Theta(\mu)$,
where a runtime gain of roughly a factor of $n/\log n$ can be proven. More
precisely, for a general population size $\mu\leq\kappa n$, with $\kappa$ a
sufficiently small constant, it was shown that the ${(\mu+1)}$ GA optimizes
jump functions with gap size $k\geq 3$ in time $O(n^{k}/\mu+n^{k-1}\log n)$.

The key proof argument of Dang et al. [10] is that the size of the largest
genotype class, once it is below $\mu$, is at least as likely to decrease as
to increase. This give a behavior resembling an unbiased random walk in the
interval $[\mu/2..\mu]$, and this is the reason why the diversity is shown to
persist for $O(\mu^{2})$ iterations.

In this work, we analyze the random process describing the largest genotype
class of the ${(\mu+1)}$ GA on Jump more carefully and show that once it is by
a constant factor below $\mu$, we do not have an unbiased random walk but a
constant drift towards smaller values (Lemma 10). Such a constant drift in,
say, the interval $[0.5\mu,0.75\mu]$, allows to argue that this diversity
remains for a number of iterations exponential in $\mu$. Consequently, already
for much smaller population sizes, we prove a most longer-lasting diversity
than in the previous work.

This result is interesting in its own right as it shows that diverse parent
populations are much easier to obtain than what previous works suggest. For
the particular problem of how fast the ${(\mu+1)}$ GA optimizes Jump
functions, we obtain a stronger advantage from crossover (Theorem 4), namely
by a factor of $\Omega(n)$, and this for all population sizes that are at
least $C\ln n$, $C$ a suitable constant. For smaller values of $\mu$, we still
obtain a significant speed-up from crossover, namely a runtime of
$O(e^{-\Omega(\mu)}n^{k})$, again a good improvement over the $O(n^{k}/\mu)$
guarantee from Dang et al. [10].

Overall, our results give some hope that also basic evolutionary algorithms
without greater adjustment are able to reach and then keep a diverse
population for a long time. This is clearly good news for the use of crossover
but might also yield other advantages, like a more effective exploration of
the search space.

##  2 Previous Work

Since the first rigorous result showing the benefit of crossover more than two
decades [26] ago, a variety of results for genetic algorithms (GAs), i.e.,
evolutionary algorithms that employ crossover, has been proven. Because
crossover introduces many dependencies into the population of the GA in
question, its analysis is notoriously difficult. Hence, most of the existing
results make additional, restrictive assumptions.

Non-standard parameter values. The analysis of GAs was initiated by Jansen and
Wegener [26], who considered jump functions of gap size $k$. They prove that
the ${(1+1)}$ EA requires in expectation $\Theta(n^{k})$ function evaluations
before it creates the optimum, whereas a ${(\mu+1)}$ GA with crossover rate
$p_{c}$ only requires $O(\mu n^{2}k^{3}+4^{k}/p_{c})$ evaluations. However, in
order to prove their result, the authors assume that $p_{c}=O(1/(kn))$,
relying on a long sequence of preferable mutations before crossover is capable
to produce the optimum more easily than mutation. In this setting, crossover
is only seen as useful once a sufficient diversity is achieved.

This result was later improved by Kötzing, Sudholt, and Theile [29], but the
authors still require that $p_{c}=O(k/n)$, as their proof relies on the same
technique as that of Jansen and Wegener [26].

Constant-factor improvements. For the classical OneMax problem, Sudholt [39]
proves that a special variant of the ${(\mu+1)}$ GA has a constant-factor
speed-up compared to any variant of the ${(1+1)}$ EA with mutation rates
between $2^{-n/3}$ and $(\sqrt{n}\ln(n))^{-1}$. As the algorithm only applies
crossover to the best individuals in the population, the $(2+1)$ GA uses the
best population size.

Corus and Oliveto [7] remove the elitist selection for crossover from the
analysis of Sudholt [39] and analyze the typical ${(\mu+1)}$ GA, with a
crossover rate of $1$. The authors prove that speed-ups of up to $25$ % are
possible when compared to the expected runtime of the ${(1+1)}$ EA. In a
subsequent work, the authors [8] improve this result by showing speed-ups of
at least $60$ % compared to not using crossover. These new results also prove
runtime bounds that reduce with the population size, thus showing a potential
benefit of a larger population.

Recently, Oliveto, Sudholt, and Witt [37] prove a lower bound for the $(2+1)$
GA on OneMax that matches the previous results [8]. Together, these results
show that having a larger population than $2$ is truly beneficial.

Diversity mechanisms. Another common way to analyze crossover is to employ
mechanisms that aim at increasing the diversity in the population of the GA.
Depending on the mechanism and on the problem, such approaches can be very
fruitful. However, the respective results rather showcase, similar to the non-
standard parameter values, how well crossover can exploit a diverse
population. It is not clearly evident to what extent crossover by itself is
already useful.

Oliveto, He, and Yao [36] consider the vertex cover problem and analyze the
${(\mu+1)}$ EA (without crossover) as well as the $(\mu+1)$ randomized local
search (RLS) with crossover, both employing deterministic crowding. This
mechanism guarantees that if a newly created individual is at least as good as
its parent(s), one of the parents is removed. The paper shows that just using
deterministic crowding without crossover is already sufficient for finding
minimal covers on bipartite graphs. Hence, the results rather show the benefit
of the diversity mechanism.

Lehre and Yao [31] also consider deterministic crowding, combined with a
variant of the ${(\mu+1)}$ GA (called SSGA). They show that using crossover
with constant crossover rate improves the expected runtime of the $(\mu+1)$
SSGA from at least exponential to quadratic in the problem size. Although this
is an impressive speed-up, the considered algorithm uses a crossover that
exchanges exactly one component among two parents, thus making rather local
changes, which is uncommon for crossover.

Neumann et al. [33] consider the single-receiver island model with $1$-point
crossover. They consider a problem for which a variant of the ${(\mu+1)}$ GA
(for populations of order at most $n/\log^{3}(n)$) has for each crossover rate
at least an exponential runtime, with high probability. In contrast, they
prove that the island model optimizes this problem with high probability
efficiently. This result rather highlights the benefits of the island model in
this scenario than of crossover.

Dang et al. [9] analyze the expected runtime of the ${(\mu+1)}$ GA optimizing
jump functions, for a variety of different diversity mechanisms. The runtime
is always better (for appropriate parameters) than that of the mutation-only
${(1+1)}$ EA. As before, these results heavily rely on the diversity mechanism
for crossover to be useful.

Sutton [40] proves that a multi-start variant of the ${(\mu+1)}$ GA optimizes
the closest-string problem in randomized fixed-parameter tractable (FPT) time.
The article also shows that if crossover is removed, there are instances that
are not solved in FPT time.

Problem-specific knowledge. Doerr, Happ, and Klein [18] analyze the impact of
crossover for the all-pairs-shortest-path problem, which is a non-artificial,
combinatorial problem. The authors prove that the algorithm variant with
crossover improves the expected runtime by a factor of
$\Theta(\sqrt{n/\log(n)})$. In order to prevent infeasible solutions from
entering the population, the algorithm employs a mechanism that detects
infeasible solutions and discards them. This work was later improved by Doerr
et al. [19] by utilizing better crossover operators.

Non-standard crossover operator. A decade ago, Doerr, Doerr, and Ebel [16, 17]
proposed the ${(1+(\lambda,\lambda))}$ GA—a GA that introduces a novel
crossover operator that is aimed to exploit information learned from good
_and_ bad samples. Doerr and Doerr [14] prove that the
${(1+(\lambda,\lambda))}$ GA has an expected runtime on OneMax that is
improved by a factor of order $\sqrt{\ln(n)}$ compared to many other
evolutionary algorithms.

Since then, the ${(1+(\lambda,\lambda))}$ GA has been studied on different
problems [2, 3, 4, 21]. Notably, Antipov, Doerr, and Karavaev [4] prove that
the ${(1+(\lambda,\lambda))}$ GA optimizes jump functions with gap size $k$,
with optimal parameters (depending on $k$), in the order of
$(n/k)^{k/2}e^{\Theta(k)}$, which is faster by a factor of
$(nk)^{-k/2}e^{\Theta(k)}$ compared to the traditional ${(1+1)}$ EA.

Other articles determine optimal parameter settings of the
${(1+(\lambda,\lambda))}$ GA and propose how to choose them dynamically [1,
13, 15]. Especially, Antipov and Doerr [1] show for jump functions with gap
size $k$ that choosing the parameters of the ${(1+(\lambda,\lambda))}$ GA
according to a heavy-tailed distribution (independent of $k$) achieves a
performance close to the best instance-specific parameter choice.

Multi-objective optimization. Although it is not the focus of this article and
not a restriction, we would like to mention that crossover has also been
studied for multi-objective problems [24, 34, 38]. Especially recently, the
most-widely used EA for multi-objective optimization, NSGA/̄II [12], which
employs crossover, has been studied [6, 11, 22].

Standard algorithm with standard parameters. To the best of our knowledge, the
only result that considers the ${(\mu+1)}$ GA with typical parameters is the
article by Dang et al. [10]. For jump functions with gap size $k$, the authors
prove (for optimal parameters, including a slightly higher mutation rate than
normal) an expected runtime of up to $O(n^{k-1})$, which is better by a factor
of $n$ than the expected runtime when employing no crossover. The analysis
tracks the diversity of the population, showing that there are phases lasting
about $\mu^{2}$ iterations in expectation in which a sufficient diversity in
the population emerges naturally. During such a phase, the probability to
create the optimum via crossover and mutation is better by a factor of about
$n$ compared to only mutation. The analysis further reveals that crossover is
_not_ detrimental for creating the desired diversity, thus, providing a
convincing argument for why crossover is typical favorable in practice.

##  3 Preliminaries

We introduce the notation used throughout this paper, the algorithm and
function that we consider in our analysis (Section 3.1), as well as the
stochastic tools we use for deriving our results (Section 3.2).

###  3.1 Mathematical Notation

Let $\mathbb{N}$ denote the set of all natural numbers (including $0$), and
let $\mathbb{R}$ be the set of real numbers. For $m,n\in\mathbb{N}$, let
$[m..n]=[m,n]\cap\mathbb{N}$, that is, the discrete interval from $m$ to $n$.
Further, we define the special case $[n]\coloneqq[1..n]$. We consider pseudo-
Boolean maximization, that is, for a given $n\in\mathbb{N}_{\geq 1}$, we aim
to find a global maximum for a given $n$-dimensional objective function
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ (a _fitness function_), which maps bit
strings to reals. We call elements from $\\{0,1\\}^{n}$ _individuals_ and
their objective-function value _fitness_. Throughout this paper, whenever we
use big-O notation, we assume that the statement is asymptotic in the problem
dimension $n$.

Given a random variable $X$, a $\sigma$-algebra $\mathcal{F}$, and an event
$A$ with $\Pr[A]>0$, let
$\operatorname{\mathds{E}}[X\mid\mathcal{F};A]=\operatorname{\mathds{E}}[X\cdot{\mathds{1}}_{A}\mid\mathcal{F}]/\Pr[A]$.
We make use of this notation when we condition on a $\sigma$-algebra but also
make case distinctions via events.

For two _individuals_ $x,y\in\\{0,1\\}^{n}$, we define their _Hamming
distance_ as the number of positions that they differ in. Further, let
$|x|_{1}$ denote the number of $1$s in a bit-string $x$.

Let $n\in\mathbb{N}_{\geq 1}$, and let $k\in[n]$. We consider the
$\textsc{Jump}_{k}\colon\\{0,1\\}^{n}\to\mathbb{N}$ fitness function, which is
defined as

$\textsc{Jump}_{k}\colon x\mapsto\begin{cases}k+|x|_{1}&\text{if $|x|_{1}=n$
or $|x|_{1}\leq n-k$},\\\ n-|x|_{1}&\text{otherwise.}\end{cases}$ (1)

Whenever we mention $\textsc{Jump}_{k}$ in this paper, we assume that its
parameters $n$ and $k$ are implicitly given.

The function value of $\textsc{Jump}_{k}$ increases with the number of $1$s in
the individual until the _plateau_ of local optima is reached, which consists
of all points with exactly $n-k$ $1$s. However, the only global optimum of
$\textsc{Jump}_{k}$ is the all-$1$s string. Between the plateau and the global
optimum, that is, for all individuals with more than $n-k$ but less than $n$
$1$s, there is a gap of length $k-1$ of fitness worse than for any individual
outside of this area. Elitist EAs that only have solutions on the plateau thus
have to change $k$ bits in a single iteration in order to get from the plateau
to the global optimum (also referred to as a _jump_).

We consider the ${(\mu+1)}$ GA (Algorithm 1) with _population size_
$\mu\in\mathbb{N}_{\geq 2}$, _crossover rate_ $p_{c}\in[0,1]$, and _mutation
rate_ $p_{m}\in[0,1]$. The algorithm maintains a multiset (the _population_)
of $\mu$ individuals, which is initialized with uniform samples from the
search space and afterward updated iteratively. In each iteration, a new
individual is created and potentially replaces an individual in the population
in the following way, where all random choices are independent: With
probability $p_{c}$, two individuals from the current population are selected
uniformly at random (the _parents_). Then, a new individual (the _offspring_)
is created by _uniform crossover_ of the parents, that is, each bit of the
offspring is chosen uniformly at random from the respective positions of the
parents. Afterward, _standard bit mutation_ with mutation rate $p_{m}$ is
applied to the offspring, that is, each of its bits is flipped independently
with probability $p_{m}$. Otherwise, with probability $1-p_{c}$, a parent is
selected uniformly at random from the current population and produces an
offspring only via standard bit mutation. Last, in any case, an individual
with the lowest fitness among the current population and the offspring is
removed, breaking ties uniformly at random. The resulting multiset forms the
population for the next iteration. We define the runtime of the ${(\mu+1)}$ GA
as the number of fitness function evaluations until an optimal solution is
evaluated for the first time.

1 $t\leftarrow 0$;

2 $P^{(0)}\leftarrow\mu$ individuals, uniformly at random from
$\\{0,1\\}^{n}$;

3 while  __termination criterion met__ do // iteration $t$

4 $p\leftarrow$ value from $[0,1)$ uniformly at random;

5 if  _$p <p_{c}$_ then

6 $x^{(t)},y^{(t)}\leftarrow$ two individuals from $P^{(t)}$ chosen uniformly
at random (with replacement);

7 $\widetilde{z}^{(t)}\leftarrow$ new individual created by uniform crossover
of $x^{(t)}$ and $y^{(t)}$;

8 $z^{(t)}\leftarrow\widetilde{z}^{(t)}$ augmented by standard bit mutation;

9

10 else

11 $m^{(t)}\leftarrow$ copy of an individual from $P^{(t)}$ chosen uniformly
at random;

12 $z^{(t)}\leftarrow m^{(t)}$ augmented by standard bit mutation;

13

14 $\ell^{(t)}\leftarrow$ individual with the lowest fitness from
$P^{(t)}\cup\\{z^{(t)}\\}$, breaking ties uniformly at random;

15 $P^{(t+1)}\leftarrow(P^{(t)}\cup\\{z^{(t)}\\})\setminus\\{\ell^{(t)}\\}$;

16 $t\leftarrow t+1$;

17

Algorithm 1 The ${(\mu+1)}$ GA with parameters $\mu\in\mathbb{N}_{\geq 2}$ and
$p_{c},p_{m}\in[0,1]$, maximizing fitness function $f$

###  3.2 Tools for Our Analyses

Our analysis of the ${(\mu+1)}$ GA on $\textsc{Jump}_{k}$ (Section 4) follows
the one by Dang et al. [10] and splits the runtime of the algorithm into the
following two phases: The first phase considers the expected number of
iterations until the algorithm finds the optimum or until the entire
population is on the plateau. The second phase carefully analyses the
diversity of the population on the plateau until the optimum is created. For
the first phase, we use the result by Dang et al. [10] for the general setting
of $p_{c}=\Omega(1)$.

######  Theorem 1 ([10, Lemma $1$]).

Consider the ${(\mu+1)}$ GA with $p_{c}=\Omega(1)$ and
$p_{m}=\Theta(\frac{1}{n})$ optimizing $\textsc{Jump}_{k}$ with $k=o(n)$. Then
the expected time until either the optimum is found or the entire population
is on the plateau is $O(n\sqrt{k}(\mu\log(\mu)+\log(n)))$.

For the second phase, we eventually aim to create the optimum of
$\textsc{Jump}_{k}$ via crossover (followed by mutation) of two individuals
with a Hamming distance of $2$. The following theorem provides the probability
of constructing the optimum in the general case. It is a slight reformulation
of [10, Lemma $3$] (from mutation rate $\frac{1}{n}$ to rate
$\Theta(\frac{1}{n})$). For the sake of completeness, we still provide a
proof.

######  Lemma 2 ([10, Lemma $2$]).

Let $n\in\mathbb{N}_{\geq 1}$, let $k\in[n/2]$, let $d\in[0..k]$, and let
$p_{m}=\Theta(\frac{1}{n})$. Furthermore, let $x,y\in\\{0,1\\}^{n}$ with
$|x|_{1}=|y|_{1}=n-k$ and such that their Hamming distance is $2d$. Then the
probability that the result of uniform crossover of $x$ and $y$, followed
independently by standard bit mutation with mutation rate $p_{m}$, is the
all-$1$s string is $\Omega(4^{-d}n^{-k+d})$.

###### Proof.

Since $x$ and $y$ each have $n-k$ $1$s and a Hamming distance of $2d$, they
have $n-k-d$ $1$s in common. Analogously, they have $k-d$ $0$s in common.
Hence, uniform crossover produces an offspring $z$ with $n-k+d$ $1$s by
choosing a $1$ each time that $x$ and $y$ differ. The probability for this
event is $2^{-2d}=4^{-d}$. Afterward mutation creates the all-$1$s string out
of $z$ by flipping its remaining $k-d$ $0$s to $1$s (and not flipping any
other bits). Due to the assumption $p_{m}=\Theta(\frac{1}{n})$ and due to
$(1-p_{m})^{n}=\Theta(1)$, the probability of this event is
$(1-p_{m})^{n-k+d}p_{m}^{k-d}\geq(1-p_{m})^{n}p_{m}^{k-d}=\Omega(n^{-k+d})$.
Since crossover and mutation act independently, the result follows. ∎

In the second phase, we show via the negative-drift theorem below that the
diversity of the population on the plateau persist with high probability for a
time exponential in $\mu$. This theorem is a version of [28, Theorem $3$]
where the drift does not need to be negative for the entire search space but
only for parts of it.

######  Theorem 3 ([30, Corollary $3.24$]).

Let $(X_{t})_{t\in\mathbb{N}}$ be a random process over $\mathbb{R}$ adapted
to a filtration $(\mathcal{F}_{t})_{\in\mathbb{N}}$. Further, let $X_{0}\leq
0$, let $b\in\mathbb{R}_{>0}$, and let $T=\inf\\{t\in\mathbb{N}\mid X(t)\geq
b\\}$. Suppose that there are constants $a\in\mathbb{R}_{\leq 0}$,
$c\in(0,b)$, and $\varepsilon\in\mathbb{R}_{<0}$ such that, for all
$t\in\mathbb{N}$, it holds that

  1. (i)

$\operatorname{\mathds{E}}[(X_{t+1}-X_{t})\cdot\mathbf{1}_{X_{t}\geq
a}\cdot\mathbf{1}_{T<t}\mid\mathcal{F}_{t}]\leq\varepsilon\cdot\mathbf{1}_{X_{t}\geq
a}\cdot\mathbf{1}_{T<t}$, that

  2. (ii)

$|X_{t+1}-X_{t}|\cdot\mathbf{1}_{X_{t}\geq
a}\cdot\mathbf{1}_{T<t}<c\cdot\mathbf{1}_{X_{t}\geq a}+\mathbf{1}_{X_{t}<a}$,
and that

  3. (iii)

$X_{t+1}\cdot\mathbf{1}_{X_{t}<a}\cdot\mathbf{1}_{T<t}\leq 0$.

Then, for all $t\in\mathbb{N}$, it holds that $\Pr[T\leq t]\leq
t^{2}\exp\mathopen{}\mathclose{{}\left(-\frac{b|\varepsilon|}{2c^{2}}}\right)$.

##  4 Runtime Analysis

We analyze the ${(\mu+1)}$ GA with mutation rate $\frac{\chi}{n}$, where
$\chi\in\mathbb{R}_{>0}$ is a constant, and with constant crossover rate,
following the ideas of Dang et al. [10]. We show that once the entire
population of the ${(\mu+1)}$ GA is on the plateau, the population quickly
reaches a state where the largest genotype class has at most $\frac{3}{4}\mu$
individuals for a time exponential in $\mu$ with high probability. During this
time, applying crossover to any two individuals with Hamming distance at least
$2$, followed by mutation, results in a speed-up of order $\Omega(n)$ over
only applying crossover.

######  Theorem 4.

Let $\chi\in\Theta(1)$. Consider the ${(\mu+1)}$ GA with population size
$\mu=O(n)$, crossover rate $p_{c}=\Theta(1)$, and mutation rate
$p_{m}=\frac{\chi}{n}$ optimizing $\textsc{Jump}_{k}$ with $k=o(n)$. Last, let
$C=\frac{1+\frac{7}{4}\chi}{512e}p_{c}$. Then the expected runtime is

$\displaystyle
O\mathopen{}\mathclose{{}\left(n\sqrt{k}(\mu\log(\mu)+\log(n))+\frac{\mu
n+\mu^{2}\log(\mu)}{n^{-k+1}\min(\exp(\frac{C\mu}{2}),n^{k-1})}+n^{k-1}}\right).$

In our analysis, we assume that the entire population of the ${(\mu+1)}$ GA is
on the plateau, as Theorem 1 covers the expected time it takes until the
algorithm reaches this state (or finds the optimum). Like Dang et al. [10], we
consider the population dynamics on the plateau and show that sufficiently
diverse individuals show up and remain for a long time.

To make things more formal, we refer to identical individuals as a _species_.
For a given species, we call an individual belonging to this species a _$y$
-individual_, otherwise we say it is a _non- $y$-individual_. Since the
population is on the plateau, individuals from different species have a
Hamming distance of at least $2$. Hence, for a constant $c\in(0,1)$, if the
largest species has a size of at most $c\mu$ and due to the constant crossover
rate, there is a constant probability to select two individuals for crossover
that have a Hamming distance of at least $2$. By Lemma 2, the probability to
create the optimum via such a crossover followed by mutation is at least
$\Omega(n^{-k+1})$, which concludes the analysis.

In order to make these points rigorous, we carefully analyze how the size of a
species evolves over the iterations. To this end, for species $s$ (where $s$
is just a symbol), we view its size $Y_{s}$ as a random process over
$[0..\mu]$. In the following, we analyze the transition probabilities of this
random process, which we define for all $y\in[\mu]$, all $t\in\mathbb{N}$, and
all events $A$ with non-zero probability as

$\displaystyle p^{(s,t)}_{+}(y\mid A)$
$\displaystyle\coloneqq\Pr[Y_{s}(t+1)-Y_{s}(t)=1\mid Y_{s}(t)=y,A]\text{ and}$
(2) $\displaystyle p^{(s,t)}_{-}(y\mid A)$
$\displaystyle\coloneqq\Pr[Y_{s}(t+1)-Y_{s}(t)=-1\mid Y_{s}(t)=y,A].$

When analyzing the transition probabilities stated above, we make a case
distinction with respect to how the offspring in an iteration is created. In
total, we consider three different cases: Lemmas 5 and 6 assume that crossover
(followed by mutation) is performed with parents whose Hamming distance is at
most $2$. Lemma 7 assumes that crossover is performed with parents whose
Hamming distance is larger than $2$. And Lemma 8 assumes that only mutation is
performed.

Our analysis differs from the one of Dang et al. [10] in how carefully we
analyze the transition probabilities above, and also that we consider
(constant) crossover rates less than $1$. Dang et al. show that the largest
species remains small for an amount of time that is equal to that of a fair
random walk (about $\mu^{2}$ iterations). In contrast, we show that there is
actually a drift toward decreasing the species, which grows as the size of the
species decreases to around $\frac{\mu}{2}$. To this end, we use the results
by Dang et al. that show how likely the size of a species is to increase.
However, we go into detail about how likely the size decreases, as this is
important for the drift, and we also consider the case of only applying
mutation in a single iteration.

The following lemma bounds the probabilities of a species increasing as well
as the probability of a monomorphic population to create a new genotype. We
phrase the lemma in a way for which it actually holds, which is more
permissive than what Dang et al. [10] claim, when looking into their proof.

######  Lemma 5 ([10, Lemma $3$]).

Let $\chi\in\Theta(1)$. Consider a single iteration $t\in\mathbb{N}$ of the
${(\mu+1)}$ GA with population size $\mu\in\mathbb{N}_{\geq 2}$, crossover
rate $p_{c}=\Theta(1)$, and mutation rate $p_{m}=\frac{\chi}{n}$ optimizing
$\textsc{Jump}_{k}$ with $k=o(n)$. Let $A$ denote the event that the entire
population $P^{(t)}$ is on the plateau and that the offspring produced this
iteration is created via crossover of two parents whose Hamming distance is at
most $2$ (followed by mutation). Assume that $A$ has a positive probability of
occurring. Last, let $s$ be a species of $P^{(t)}$. Then, for the transition
probabilities defined in equation (2) and for all $y\in[\mu]$, it holds that

$\displaystyle p^{(s,t)}_{+}(y\mid A)$
$\displaystyle\leq\frac{(\mu-y)y(\mu+y)}{2(\mu+1)\mu^{2}}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+O\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\frac{1}{n}}\right)\text{,
and}$ $\displaystyle p^{(s,t)}_{-}(\mu\mid A)$
$\displaystyle=\Omega\mathopen{}\mathclose{{}\left(\frac{k}{n}}\right).$

In the following lemma, in the same setting of Lemma 5, we bound the
probability of the size of a species decreasing for the sizes not covered by
Lemma 5. It follows closely the proof of [10, Lemma $3$], but it is more
detailed about the case when two non-$y$-individuals are selected as parents
for the crossover.

######  Lemma 6.

Let $\chi\in\Theta(1)$. Consider a single iteration $t\in\mathbb{N}$ of the
${(\mu+1)}$ GA with population size $\mu\in\mathbb{N}_{\geq 2}$, crossover
rate $p_{c}=\Theta(1)$, and mutation rate $p_{m}=\frac{\chi}{n}$ optimizing
$\textsc{Jump}_{k}$ with $k=o(n)$. Let $A$ denote the event that the entire
population $P^{(t)}$ is on the plateau and that the offspring produced this
iteration is created via crossover of two parents whose Hamming distance is at
most $2$ (followed by mutation). Assume that $A$ has a positive probability of
occurring. Last, let $s$ be a species of $P^{(t)}$. Then, for the transition
probabilities defined in equation (2) and for all $y\in[\mu-1]$, it holds that

$p^{(s,t)}_{-}(y\mid
A)\geq\frac{y(\mu-y)\mathopen{}\mathclose{{}\left(\mu\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)+\frac{1}{2}y\chi}\right)}{2(\mu+1)\mu^{2}}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}.$

###### Proof.

Decreasing the size of $s$ entails that an offspring that is a
non-$y$-individual is created (as clarified in the lemma) and then not removed
afterward during the selection. Let $q(y\mid A)$ denote the probability
(conditional on $A$) that a non-$y$-individual is created by mutation and
crossover. Assuming that the offspring is on the plateau, then, since all
individuals are on the plateau, the individual for deletion is selected
uniformly at random. Thus, since we consider a $y$-individual to be removed,
we get

$\displaystyle p^{(s,t)}_{-}(y\mid A)\geq q(y\mid
A)\mathopen{}\mathclose{{}\left(\frac{y}{\mu+1}}\right).$ (3)

We bound $q(y\mid A)$ via a case distinction with respect to what species the
parents of the crossover belong to.

Case 1. The parents are a $y$-individual and a non-$y$-individual. The
probability to select such parents is $2\frac{y}{\mu}\frac{\mu-y}{\mu}$. We
now make another case distinction with respect to the outcome of the
crossover.

Case 1.1. The crossover result if a copy of the non-$y$-individual parent.
This occurs with probability $\frac{1}{4}$. Afterward, the crossover offspring
is not changed by mutation with probability $(1-\frac{\chi}{n})^{n}$.

Case 1.2. Crossover produces an individual with $k-1$ $0$s. This occurs with
probability $\frac{1}{4}$. Afterward, mutation creates a non-$y$-individual by
flipping a single of the $n-k$ $1$s that do not lead to a $y$-individual. The
probability of this mutation is $(n-k)\frac{\chi}{n}(1-\frac{\chi}{n})^{n-1}$.

Case 1.3. Crossover produces an individual with $k+1$ $0$s. This occurs with
probability $\frac{1}{4}$. Afterward, mutation creates a non-$y$-individual by
flipping a single of $k$ $1$s that do not lead back to a $y$-individual. The
probability of this mutation is $k\frac{\chi}{n}(1-\frac{\chi}{n})^{n-1}$

Concluding Case 1. Combining the three cases yields

$\displaystyle\frac{2y}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(\frac{1}{4}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+\frac{1}{4}(n-k)\frac{\chi}{n}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n-1}}\right.$
$\displaystyle\qquad\qquad\quad\mathopen{}\mathclose{{}\left.+\frac{1}{4}k\frac{\chi}{n}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n-1}}\right)$
$\displaystyle=\frac{1}{2}\frac{y}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\chi\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{-1}}\right)$
$\displaystyle\geq\frac{1}{2}\frac{y}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\chi}\right).$

Case 2. The parents are two non-$y$-individuals. The probability to select
such parents is $(\frac{\mu-y}{\mu})^{2}$. We now make a case distinction with
respect to the Hamming distance of the parents, which is either $0$ or $2$,
since we condition on $A$.

Case 2.1. The parents have Hamming distance $0$. Crossover produces a copy of
the parents. If the following mutation does not flip any bits, which occurs
with probability $(1-\frac{\chi}{n})^{n}$, the result is on the plateau.

Case 2.2. The parents have Hamming distance $2$. Then, we are in a similar
scenario as in Case $1$ above. The difference to Case $1.1$ is that the
probability of the crossover producing a non-$y$-individual is $\frac{1}{2}$,
as both parents are non-$y$-individuals in our current case, so copying them
is sufficient.

The difference to Case $1.2$ is that there are _at least_ $n-k$ $1$s that, if
flipped, do not create a $y$-individual, as we do not know how many $1$s the
offspring shares with a $y$-individual. We know though that there is only a
single genotype for the $y$-individuals, so there is only at most one
possibility for the crossover offspring to hit this genotype if a single bit
is flipped.

The difference to Case $1.3$ is the same as the one to Case $1.2$ but when
swapping $1$s and $0$s in the argument.

Concluding Case 2. Since Case $2.2$ is a lower bound of Case $2.1$, we only
use it as a bound for Case 2. Using the respective probabilities, borrowing
from Case 1 as explained, we get that the probability of Case 2 is bounded
from below by

$\displaystyle\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\mathopen{}\mathclose{{}\left(\frac{1}{2}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+\frac{1}{4}(n-k)\frac{\chi}{n}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n-1}}\right.$
$\displaystyle\qquad\qquad\quad\mathopen{}\mathclose{{}\left.+\frac{1}{4}k\frac{\chi}{n}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n-1}}\right)$
$\displaystyle=\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{-1}}\right)$
$\displaystyle\geq\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right).$

Combining the cases. Overall, the probability of adding a non-$y$-individual
to the population before selection is

$\displaystyle q(y)$
$\displaystyle\geq\frac{1}{2}\frac{y}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\chi}\right)+\frac{1}{2}\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)$
$\displaystyle=\frac{1}{2}\frac{1}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(y(1+\chi)+(\mu-y)\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)}\right)\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}$
$\displaystyle=\frac{1}{2}\frac{1}{\mu}\frac{\mu-y}{\mu}\mathopen{}\mathclose{{}\left(\mu\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)+\frac{1}{2}y\chi}\right)\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}.$

Substituting $q(y\mid A)$ into equation (3) concludes the proof. ∎

The following lemma, by Dang et al. [10], considers the case where crossover
is applied to two parents with Hamming distance at least $4$, as it was
excluded from Lemmas 5 and 6. In contrast to Lemmas 5 and 6, this lemma
requires that the considered species has a size of at least $\frac{\mu}{2}$.

######  Lemma 7 ([10, Lemma 4]).

Let $\chi\in\Theta(1)$. Consider a single iteration $t\in\mathbb{N}$ of the
${(\mu+1)}$ GA with population size $\mu\in\mathbb{N}_{\geq 2}$, crossover
rate $p_{c}=\Theta(1)$, and mutation rate $p_{m}=\frac{\chi}{n}$ optimizing
$\textsc{Jump}_{k}$ with $k=o(n)$. Let $A^{\prime}$ denote the event that the
entire population $P^{(t)}$ is on the plateau and that the offspring produced
this iteration is created via crossover (followed by mutation) of two parents
whose Hamming distance is larger than $2$, i.e., at least $4$. Assume that
$A^{\prime}$ has a positive probability of occurring. Last, let $s$ be a
species of $P^{(t)}$. Then, for the transition probabilities defined in
equation (2) and for all $y\in[\frac{\mu}{2}..\mu]$, it holds that
$p^{(s,t)}_{-}(y\mid A^{\prime})\geq 2p^{(s,t)}_{+}(y\mid A^{\prime})$.

The following lemma considers the transition probabilities of a species under
the assumption that only mutation is applied.

######  Lemma 8.

Let $\chi\in\Theta(1)$. Consider a single iteration $t\in\mathbb{N}$ of the
${(\mu+1)}$ GA with population size $\mu\in\mathbb{N}_{\geq 2}$, crossover
rate $p_{c}=\Theta(1)$, and mutation rate $p_{m}=\frac{\chi}{n}$ optimizing
$\textsc{Jump}_{k}$ with $k=o(n)$. Let $B$ denote the event that the entire
population $P^{(t)}$ is on the plateau and that the offspring produced this
iteration is created via mutation (and no crossover). Assume that $B$ has a
positive probability of occurring. Last, let $s$ be a species of $P^{(t)}$.
Then, for the transition probabilities defined in equation (2) and for all
$y\in[\mu]$, it holds that

$\displaystyle p^{(s,t)}_{+}(y\mid A)$
$\displaystyle=\frac{y(\mu-y)}{\mu(\mu+1)}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+O\mathopen{}\mathclose{{}\left(\frac{(\mu-y)^{2}}{n\mu^{2}}}\right)\text{,
and}$ $\displaystyle p^{(s,t)}_{-}(y\mid A)$
$\displaystyle\geq\frac{y(\mu-y)}{\mu(\mu+1)}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}.$

###### Proof.

Increase. We start by bounding $p^{(s,t)}_{+}(y)$ from above. In order for the
number of $y$-individuals to increase, mutation needs to produce a
$y$-individual, which happens in the following two ways:

  1. (i)

A $y$-individual is selected and mutation does not flip any bits. This occurs
with probability $(1-\frac{\chi}{n})^{n}$.

  2. (ii)

A non-$y$-individual is selected. Hence, at least one specific position must
be flipped, occuring with probability $O(\frac{1}{n})$.

After mutation, a non-$y$-individual needs to be removed from the population
in order for the number of $y$-individuals to increase. The probability to
remove a non-$y$-individual is $\frac{\mu-y}{\mu+1}$. Hence, the overall
probability for an increase is at most
$\frac{y(\mu-y)}{\mu(\mu+1)}(1-\frac{\chi}{n})^{n}+O\mathopen{}\mathclose{{}\left(\frac{(\mu-y)^{2}}{n\mu^{2}}}\right)$.

Decrease. We now bound $p^{(s,t)}_{-}(y)$ from below. To this end, we only
consider the case that (i) a non-$y$-individual is selected for mutation, (ii)
that it is copied via mutation (i.e., flipping no bits), and (iii) that a
$y$-individual is removed during selection. Event (i) occurs with probability
$\frac{\mu-y}{\mu}$, event (ii) with probability $(1-\frac{\chi}{n})^{n}$, and
event (iii) with probability $\frac{y}{\mu+1}$. Hence, the overall probability
for a decrease is at least
$\frac{y(\mu-y)}{\mu(\mu+1)}(1-\frac{\chi}{n})^{n}.$ ∎

The next lemma bounds the expected time for a species to reach a size of at
most $\frac{\mu}{2}$, by Dang et al. [10]. The authors only consider the
largest species, but since the proof relies on the transition probabilities we
stated so far in this section, which are not specific to the largest species,
the lemma is actually more general.

######  Lemma 9 ([10, Lemma $6$]).

Let $\chi\in\Theta(1)$. Consider the ${(\mu+1)}$ GA with population size
$\mu=O(n)$, crossover rate $p_{c}=\Theta(1)$, and mutation rate
$p_{m}=\frac{\chi}{n}$ optimizing $\textsc{Jump}_{k}$ with $k=o(n)$. Further,
let $s$ be a species, and let $t^{*}\in\mathbb{N}$ be an iteration such
$P^{(t^{*})}$ is entirely on the plateau. In addition, let $Y_{s}(t^{*})$ be
defined as above equation (2). Let $T=\inf\\{t\in\mathbb{N}\mid
Y_{s}(t^{*}+t)\leq\frac{\mu}{2}\\}$. Then $\operatorname{\mathds{E}}[T\mid
Y_{s}(t^{*})]=O(\mu n+\mu^{2}\log(\mu))$.

The following lemma shows that once a species has a size of at most
$\frac{\mu}{2}$, then, for any constant $\lambda\in(\frac{1}{2},1)$, its size
does not reach $\lambda\mu$ with high probability in a number of iterations
exponential in $\mu$.

######  Lemma 10.

Let $\chi\in\Theta(1)$. Consider the ${(\mu+1)}$ GA with population size
$\mu\in\mathbb{N}_{\geq 2}$, crossover rate $p_{c}=\Theta(1)$, and mutation
rate $p_{m}=\frac{\chi}{n}$ optimizing $\textsc{Jump}_{k}$ with $k=o(n)$.
Further, let $s$ be a species, and let $t^{*}\in\mathbb{N}$ be an iteration
such $P^{(t^{*})}$ is entirely on the plateau. Assume that $Y_{s}(t^{*})$ (as
defined above equation (2)) is at least $\frac{\mu}{2}$. Let
$\lambda\in(\frac{1}{2},1)$, and let $T=\inf\\{t\in\mathbb{N}\mid
Y_{s}(t+t^{*})\geq\lambda\mu\\}$. Last, let
$C=\frac{(2\lambda-1)(1+(1+\lambda)\chi)}{256e}p_{c}$. Then, for all
$t\in\mathbb{N}$, it holds that $\Pr[T\leq t]\leq t^{2}\cdot\exp(-C\mu)$.

###### Proof.

We aim to apply the negative-drift theorem (Theorem 3) with
$(\mathcal{F}_{t})_{t\in\mathbb{N}}$ being the canonical filtration of
$(Y_{s}(t+t^{*}))_{t\in\mathbb{N}}$. We consider the process
$(X_{t})_{t\in\mathbb{N}}$, which is defined such that, for all
$t\in\mathbb{N}$, it holds that $X_{t}=Y_{s}(t+t^{*})-\frac{\mu}{2}$.
Furthermore, we choose the variables of Theorem 3 by defining that
$b=(\lambda-\frac{1}{2})\mu$, $c=1$,
$\varepsilon=-\frac{1+(1+\lambda)\chi}{64e}p_{c}$ being a constant, and $a=0$.

By the definition of $X$, it holds that $T=\inf\\{t\in\mathbb{N}\mid
X_{t}\geq(\lambda-\frac{1}{2})\mu=b\mu\\}$.

We make sure that the different conditions of Theorem 3 are all met. For the
sake of readability, we omit the indicator functions in this proof.

Condition (i). Let $t\in\mathbb{N}$, and let $y=Y_{s}(t+t^{*})$. By the
definition of $Y_{s}$ and of $X$, it that

$\operatorname{\mathds{E}}[X_{t+1}-X_{t}\mid{\mathcal{F}_{t}}]=p^{(s,t+t^{*})}_{+}(y\mid{\mathcal{F}_{t}})-p^{(s,t+t^{*})}_{-}(y\mid{\mathcal{F}_{t}}).$
(4)

We aim to bound equation (4) from above by using the bounds of Lemmas 5 and 6.
To this end, we define the constants

$\displaystyle C_{+}$
$\displaystyle=\frac{(\mu-y)y(\mu+y)}{2(\mu+1)\mu^{2}}\textrm{ and}$
$\displaystyle C_{-}$
$\displaystyle=\frac{y(\mu-y)\mathopen{}\mathclose{{}\left(\mu\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)+\frac{1}{2}y\chi}\right)}{2(\mu+1)\mu^{2}}.$

We now make a case distinction with respect to the different bounds on the
transition probabilities from the different settings of Lemmas 5, 6, 7, and 8.

Case 1. We consider the setting of Lemmas 5 and 6. Let $A$ denote the
respective event from those lemmas. Since there is always the chance to pick
the same individual twice for crossover, $\Pr[A]>0$. The respective bounds
from Lemmas 5 and 6 yield that, noting that $y<\mu$, as we assume that
$y\in[\frac{\mu}{2},\lambda\mu]$ but omit the indicator functions,

$\displaystyle p^{(s,t+t^{*})}_{+}(y\mid A)-p^{(s,t+t^{*})}_{-}(y\mid A)$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(C_{+}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}-C_{-}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+O\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\frac{\mu-y}{\mu}}\right)^{2}\frac{1}{n}}\right)}\right)$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(-C_{+}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\frac{\mu\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)+\frac{1}{2}y\chi}{\mu+y}+o(1)}\right)$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(-\frac{(\mu-y)y\mathopen{}\mathclose{{}\left(\mu\mathopen{}\mathclose{{}\left(1+\frac{1}{2}\chi}\right)+\frac{1}{2}y\chi}\right)}{2(\mu+1)\mu^{2}}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}+o(1)}\right).$

Using that $y\in[\frac{\mu}{2},\lambda\mu]$ and that
$\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)^{n}\geq\frac{1}{e}\mathopen{}\mathclose{{}\left(1-\frac{\chi}{n}}\right)$,
we get

$\operatorname{\mathds{E}}[X_{t+1}-X_{t}\mid\mathcal{F}_{t};A]\leq-\frac{2+(1+\lambda)\chi}{16e}+o(1).$
(5)

Case 2. We consider the setting of Lemma 7. Let $A^{\prime}$ denote the
respective event from this lemma. Assume that $\Pr[A^{\prime}]>0$. By Lemma 7,
we get

$\displaystyle p^{(s,t+t^{*})}_{+}(y\mid A^{\prime})-p^{(s,t+t^{*})}_{-}(y\mid
A^{\prime})\leq-p^{(s,t+t^{*})}_{+}(y\mid A^{\prime})\leq 0.$ (6)

Case 3. We consider the setting of Lemma 8. Let $B$ denote the respective
event from this lemma. Assume that $\Pr[B]>0$. By Lemma 8, we get

$p^{(s,t+t^{*})}_{+}(y\mid B)-p^{(s,t+t^{*})}_{-}(y\mid B)\leq
O\mathopen{}\mathclose{{}\left(\frac{(\mu-y)^{2}}{n\mu^{2}}}\right)=O\mathopen{}\mathclose{{}\left(\frac{1}{n}}\right).$
(7)

Combining the cases. Since the events $A$, $A^{\prime}$, and $B$ partition the
possible events of how the population changes in a single iteration, we
determine $p^{(s,t+t^{*})}_{+}(y)-p^{(s,t+t^{*})}_{-}(y)$ via the law of total
probability. To this end, we first discuss whether the events $A$,
$A^{\prime}$, and $B$ have positive probability for the relevant setting of
$y\in[\frac{\mu}{2},\lambda\mu]$.

Since $p_{c}>0$, crossover has a positive probability of being used in each
iteration. Conditional on crossover being used, since $y\geq\frac{\mu}{2}$, if
crossover picks a $y$-individual twice, occurring with probability
$(\frac{y}{\mu})^{2}\geq\frac{1}{4}$, then this is sufficient for $A$ to
occur. Hence, $\Pr[A]\geq\frac{1}{4}$.

The probabilities of $A^{\prime}$ and $B$ may be $0$. If $\Pr[B]=0$, then
$\Pr[A\cup A^{\prime}]=1$. And if $\Pr[A^{\prime}]=0$, then
$\Pr[A\mid\overline{B}]=1$. Since, by Case 2, the drift in the event of
$A^{\prime}$ (equation (6)) is negative and since event $A$ covers the case
that crossover is applied entirely otherwise, we ignore $A^{\prime}$ in the
following. Further, since, by Case 3, the drift in the event of $B$ (equation
(7)) is positive, we pessimistically estimate its probability by $1$.

Together, these considerations yield, combining equations (5), (6), and (7),
as well as equation (4) that

$\displaystyle\operatorname{\mathds{E}}[X_{t+1}-X_{t}\mid{\mathcal{F}_{t}}]\leq\mathopen{}\mathclose{{}\left(-\frac{2+(1+\lambda)\chi}{16e}+o(1)}\right)\Pr[A\mid\mathcal{F}_{t}]+O\mathopen{}\mathclose{{}\left(\frac{1}{n}}\right)$
$\displaystyle\leq-\frac{1+(1+\lambda)\chi}{16e}p_{c}\cdot\frac{1}{4}=-\frac{1+(1+\lambda)\chi}{64e}p_{c}=\varepsilon.$

Condition (ii). This condition is satisfied for $c=1$, as $y$ changes by at
most $1$ per iteration.

Condition (iii). If $X_{t}<0=a$, then, by the definition of $X$, it follows
that $y<\frac{\mu}{2}$. Since $y$ changes by at most $1$ in a single
iteration, it follows that $Y_{s}(t+1+t^{*})\leq\frac{\mu}{2}$, which is
equivalent to $X_{t+1}\leq 0$.

Applying the drift theorem. Since all conditions of Theorem 3 are met, we
apply it and get for all $t\in\mathbb{N}$ that

$\Pr[T\leq t]\leq
t^{2}\exp\mathopen{}\mathclose{{}\left(-\frac{(2\lambda-1)|\varepsilon|\mu}{4}}\right).$

Noting that $C=\frac{(2\lambda-1)(1+(1+\lambda)\chi)}{256e}p_{c}$ concludes
the proof. ∎

We have all the tools we require to prove our main result.

###### Proof of Theorem 4.

We split the runtime into two parts, mainly focusing on the second part. The
first part considers the expected number of fitness function evaluations until
the entire population of the ${(\mu+1)}$ GA is on the plateau or until the
optimum is found. The second part assumes that the entire population of the
${(\mu+1)}$ GA is on the plateau, and it considers the expected number of
fitness function evaluations (which is equivalent to iterations here, since we
evaluate a single new individual each iteration) until the optimum of
$\textsc{Jump}_{k}$ is found. By the linearity of expectation, the overall
expected runtime of the ${(\mu+1)}$ GA is at most the sum of the expected
times of these two parts, since the second part ignores whether the optimum is
found in the first part.

First part. Theorem 1 bounds the expected time for the first part by
$O(n\sqrt{k}(\mu\log(\mu)+\log(n)))$. Hence, for the remainder ot this proof,
we focus on the second part.

Second part. Since we count iterations from the first point in time that the
entire population is on the plateau, we assume that this time point is $0$,
simplifying the forthcoming calculations. Let $T$ be the first point in time
(starting from the newly defined $0$) such that the ${(\mu+1)}$ GA creates the
optimum.

We split $T$ into _phases_ of deterministic length $\ell$ (which we specify
later). If the ${(\mu+1)}$ GA does not find the optimum during a single phase,
we go into the next phase, repeating our arguments. To this end, let $R$
denote the number of phases that pass until the ${(\mu+1)}$ GA creates the
optimum for the first time. By definition, it then holds that $T\leq R\ell$.
Consequently,
$\operatorname{\mathds{E}}[T]\leq\operatorname{\mathds{E}}[R]\ell$.

Since the entire population is on the plateau until the optimum is found for
the first time, each phase (except for the last one) has the same, independent
probability of finding the optimum. Let $q$ be this probability, noting that
$q>0$. Since the probability of finding the optimum in the last phase is $1$,
the probability $q$ is a lower bound for this phase as well. Thus, $R$ is
stochastically dominated by a geometric random variable with success
probability $q$, and it follows that $E[R]\leq\frac{1}{q}$. Together with the
arguments from the previous paragraph, this yields overall
$E[T]\leq\frac{\ell}{q}$.

Bounding the success probability. For the remaining part, we aim to bound $q$.
Let $c_{1}\in\mathbb{N}$ be a sufficiently large constant from the big-O
result in Lemma 9. Further, let $c_{2}\in\mathbb{N}$ be a sufficiently small
constant from the big-O result in Lemma 2, for the case $d=2$. In addition,
let $t=\min(\exp(\frac{C\mu-1}{2}),\frac{1}{c_{2}}n^{k-1})$. Last, let
$\ell=2c_{1}(\mu n+\mu^{2}\log(\mu))+t$. We consider a single phase.

Achieving a sufficient diversity. During a phase, we wait for the first
iteration $L$ (relative to the start of the phase) until the largest species
has a size $y$ of at most $\frac{\mu}{2}$. By Lemma 9 and by definition of
$c_{1}$, the _expected_ time for this is at most $c_{1}(\mu
n+\mu^{2}\log(\mu))$. Since $L$ is a non-negative random variable, it follows
by Markov’s inequality that $\Pr[L\geq
2\operatorname{\mathds{E}}[L]]\leq\frac{1}{2}$. We assume in the following
that $L<2\operatorname{\mathds{E}}[L]=2c_{1}(\mu n+\mu^{2}\log(\mu))$. Note
that, it holds that $2c_{1}(\mu n+\mu^{2}\log(\mu))\leq\ell$.

Lasting diversity. Given that $y\leq\frac{\mu}{2}$ during the phase, by Lemma
10, choosing $\lambda=\frac{3}{4}$, it follows that $y<\lambda\mu$ for $t$
iterations (as defined above) with probability at least $1-\frac{1}{e}$. We
assume that this event occurs. Note that by the definition of $\ell$, a phase
is long enough to account for this length.

Success probability in a single iteration. Since $y<\lambda\mu$, there are at
least two different species in the population. Since the population is on the
plateau, different species have a Hamming distance of at least $2$. Thus,
during each of the at least $t$ iterations, the probability that the
${(\mu+1)}$ GA performs crossover on two individuals of Hamming distance at
least $2$ is given by the probability that the second parent belongs to a
different species than the first. Since $y<\lambda\mu$, this probability is at
least $\frac{1-\lambda}{\mu}=\frac{1}{4}$. Conditional on choosing such
parents, Lemma 2 states that the optimum is produced with a probability of
$\Omega(n^{-k+1})$. Overall, the probability that, in a single iteration, the
optimum is created is at least
$p_{c}\cdot\frac{1}{4}\cdot\Omega(n^{-k+1})=\Omega(n^{-k+1})$. Let
$q^{\prime}$ denote this probability.

Success probability during lasting diversity. By the arguments discussed in
the previous two paragraphs, the ${(\mu+1)}$ GA has $t$ iterations during
which the success probability of each is at least $q^{\prime}$. The
probability that the optimum is created during any of these iterations is at
least $1-(1-q^{\prime})^{t}\geq 1-\exp(-q^{\prime}t)$. By the definition of
$t$, it holds that $q^{\prime}t\leq 1$. Thus, since it holds for all
$x\in[0,1]$ that $\exp(-x)\leq 1-\frac{x}{2}$, it follows that
$1-\exp(-q^{\prime}t)\geq\frac{q^{\prime}t}{2}$.

Concluding a phase. Assuming that the different events discussed above occur
during a phase, recalling the definition of $q$, it follows that
$q\geq\frac{1}{2}\cdot(1-\frac{1}{e})\cdot\frac{q^{\prime}t}{2}=\Omega(q^{\prime}t)$.

Concluding the second part. With our bound for $q$, we conclude
$\operatorname{\mathds{E}}[T]\leq\frac{\ell}{q}=O\bigl{(}\frac{\ell}{q^{\prime}t}\bigr{)}=O\bigl{(}\frac{\mu
n+\mu^{2}\log(\mu)}{q^{\prime}t}+\frac{1}{q^{\prime}}\bigr{)}$. ∎

(a) A single run of the ${(\mu+1)}$ GA on $\textsc{Jump}_{k}$ with the
parameters $n=100$, $k=5$, $\mu=20$, $p_{c}=1$, and $p_{m}=\frac{1}{n}$.

(b) A single run of the ${(\mu+1)}$ GA on $\textsc{Jump}_{k}$ with the
parameters $n=1000$, $k=5$, $\mu=200$, $p_{c}=1$, and $p_{m}=\frac{1}{n}$.

Figure 1: The relative frequencies of the different Hamming distances of the
population of the ${(\mu+1)}$ GA (Algorithm 1) on the plateau of
$\textsc{Jump}_{k}$ (equation (1)), for the respective parameter settings.
Each plot depicts a single run of the ${(\mu+1)}$ GA on $\textsc{Jump}_{k}$
starting with the entire population on the plateau. The initial population is
chosen such that it consists of a single species (i.e., $\mu$ copies of the
same individual), chosen uniformly at random among all individuals with
exactly $k$ $0$s and $n-k$ $1$s. The run is stopped once the algorithm creates
the global optimum. The $x$-axis denotes the number of iterations of the
algorithm. The different colors refer to the different Hamming distances in
the population. The $y$-axis depicts the relative frequency of each such
Hamming distance among all $\binom{\mu}{2}$ pairs of individuals. Since all
individuals are on the plateau, the Hamming distances are always even numbers.
The maximum number is twice the gap size, i.e., $2k$. Please refer to Section
5.1 for more information.

##  5 Experimental Evaluation

Our runtime analysis in Section 4, especially Lemma 10, shows that once the
entire population of the ${(\mu+1)}$ GA is on the plateau, there are phases of
length exponential in $\mu$ during which the largest species (that is,
identical individuals) is at most $\frac{3}{4}\mu$. During this time, it is
possible that various different species get produced. The larger the Hamming
distance of two species, the easier it is to find the optimum of
$\textsc{Jump}_{k}$ (Lemma 2), potentially improving the runtime. In fact,
experiments by Dang et al. [10, Fig. $6$] suggest that the expected runtime of
the ${(\mu+1)}$ GA on $\textsc{Jump}_{k}$ is rather in the order of
$n\ln(n)+4^{k}$ for certain mutation rates.

Since the key to improving our result (Theorem 4) is to better understand how
diverse the population on the plateau really is during phases of lasting
diversity, we investigate these population dynamics empirically in this
section. As Dang et al. [10] present an extensive empirical analysis of the
runtime of different algorithm variants on $\textsc{Jump}_{k}$, we focus on a
quantity they did not cover, namely, the relative frequencies of all pairwise
Hamming distances in the population. A higher ratio of a larger Hamming
distance implies a larger probability to create the optimum. Thus, these
numbers provide strong insights into how well the population is spread out in
order to create the optimum.

###  5.1 Frequencies of Pairwise Hamming Distances

We analyze and discuss how the relative frequencies of pairwise Hamming
distances in the population of the ${(\mu+1)}$ GA on the plateau of
$\textsc{Jump}_{k}$ evolve over the algorithm’s iterations. Figure 1 shows our
results and explains our experimental setup. We see both in Figures 1(a) and
1(b) that the different possible Hamming distances (from $0$ to $10$, in steps
of $2$) emerge in increasing order of thir value (that is, first distance $0$,
then $2$, and so on). This trend is qualitatively the same for both figures,
with larger fluctuations for the smaller dimension size (Figures 1(a)).

Initially, by the setup of the experiment, all individuals have a Hamming
distance of $0$ to each other. However, after a short time (relative to the
entire runtime), the frequency for distance $0$ decreases rapidly and the one
for distance $2$ grows rapidly. From this point on, the frequency for distance
$0$ remains very low for the rest of the run. That is, the diversity in the
population is very high (and remains high). This supports the findings by Dang
et al. [10, Fig. $2$], whose experiments also show that the diversity in the
population remains very high during a run.

A similar behavior occurs for other neighboring pairs of distances, such as
$2$ and $4$, although this effect is far more pronounced in Figure 1(b). After
the frequency of a distance $d\in\\{2,4,6\\}$ grows, the frequency of distance
$d+2$ also grows until it overtakes the value of $d$. From this point on, the
frequency of $d$ typically remains below that of $d+2$, going so far that $d$
is almost not present anymore after some time (Figure 1(b)). This trend seems
to also emerge for distances $8$ and $10$, although their frequencies do not
meet, since the optimum is found before. These dynamics suggest that the
population does not only diversify in the number of species over time but also
increases in pairwise distances to each other.

Last, we see that the run ends in both cases once there is a sufficiently high
fraction of individuals with maximum Hamming distance in the population. This
conforms with the hypothesis that the actual expected runtime is in the order
of $n\ln(n)+4^{k}$.

##  6 Conclusion

In this work, we detected and mathematically proved that the diversity
occurring when the ${(\mu+1)}$ GA optimizes Jump functions persists much
longer than known before, namely for a time exponential in the population size
$\mu$ instead of quadratic. This result allowed us to prove superior runtime
guarantees, in particular, for small population sizes.

Our experiments support our finding that once the population is not anymore
dominated by a single genotype, this diversity lasts for a long time. However,
our experiments also show that the diversity produced by the ${(\mu+1)}$ GA is
even stronger than what our proofs show. Not only does no genotype class
dominate, but also the typical Hamming distance between individuals grows. If
such an effect could be proven, this would immediately lead to much stronger
runtime guarantees. This is clearly the most interesting, possibly not very
easy, continuation of this work.

## References

  * [1] Denis Antipov and Benjamin Doerr.  Runtime analysis of a heavy-tailed ${(1+(\lambda,\lambda))}$ genetic algorithm on jump functions.  In Parallel Problem Solving From Nature, PPSN 2020, Part II, pages 545–559. Springer, 2020.
  * [2] Denis Antipov, Benjamin Doerr, and Vitalii Karavaev.  A tight runtime analysis for the ${(1+(\lambda,\lambda))}$ GA on LeadingOnes.  In Foundations of Genetic Algorithms, FOGA 2019, pages 169–182. ACM, 2019.
  * [3] Denis Antipov, Benjamin Doerr, and Vitalii Karavaev.  The ${(1+(\lambda,\lambda))}$ GA is even faster on multimodal problems.  In Genetic and Evolutionary Computation Conference, GECCO 2020, pages 1259–1267. ACM, 2020.
  * [4] Denis Antipov, Benjamin Doerr, and Vitalii Karavaev.  A rigorous runtime analysis of the ${(1+(\lambda,\lambda))}$ GA on jump functions.  Algorithmica, 84:1573–1602, 2022.
  * [5] Anne Auger and Benjamin Doerr, editors.  Theory of Randomized Search Heuristics.  World Scientific Publishing, 2011.
  * [6] Chao Bian and Chao Qian.  Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection.  In Parallel Problem Solving From Nature, PPSN 2022, pages 428–441. Springer, 2022.
  * [7] Dogan Corus and Pietro S. Oliveto.  Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms.  IEEE Transactions on Evolutionary Compututation, 22:720–732, 2018\.
  * [8] Dogan Corus and Pietro S. Oliveto.  On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms.  Algorithmica, 82:3676–3706, 2020.
  * [9] Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton.  Escaping local optima with diversity mechanisms and crossover.  In Genetic and Evolutionary Computation Conference, GECCO 2016, pages 645–652. ACM, 2016.
  * [10] Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton.  Escaping local optima using crossover with emergent diversity.  IEEE Transactions on Evolutionary Computation, 22:484–497, 2018\.
  * [11] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt.  A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation.  In Conference on Artificial Intelligence, AAAI 2023. AAAI Press, 2023.  To appear.
  * [12] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  IEEE Transactions on Evolutionary Computation, 6:182–197, 2002\.
  * [13] Benjamin Doerr.  Optimal parameter settings for the $(1+(\lambda,\lambda))$ genetic algorithm.  In Genetic and Evolutionary Computation Conference, GECCO 2016, pages 1107–1114. ACM, 2016.
  * [14] Benjamin Doerr and Carola Doerr.  A tight runtime analysis of the (1+($\lambda$, $\lambda$)) genetic algorithm on OneMax.  In Genetic and Evolutionary Computation Conference, GECCO 2015, pages 1423–1430. ACM, 2015.
  * [15] Benjamin Doerr and Carola Doerr.  Optimal static and self-adjusting parameter choices for the ${(1+(\lambda,\lambda))}$ genetic algorithm.  Algorithmica, 80:1658–1709, 2018.
  * [16] Benjamin Doerr, Carola Doerr, and Franziska Ebel.  Lessons from the black-box: fast crossover-based genetic algorithms.  In Genetic and Evolutionary Computation Conference, GECCO 2013, pages 781–788. ACM, 2013.
  * [17] Benjamin Doerr, Carola Doerr, and Franziska Ebel.  From black-box complexity to designing new genetic algorithms.  Theoretical Computer Science, 567:87–104, 2015.
  * [18] Benjamin Doerr, Edda Happ, and Christian Klein.  Crossover can provably be useful in evolutionary computation.  Theoretical Computer Science, 425:17–33, 2012.
  * [19] Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann, and Madeleine Theile.  More effective crossover operators for the all-pairs shortest path problem.  Theoretical Computer Science, 471:12–26, 2013.
  * [20] Benjamin Doerr and Frank Neumann, editors.  Theory of Evolutionary Computation—Recent Developments in Discrete Optimization.  Springer, 2020.  Also available at http://www.lix.polytechnique.fr/Labo/Benjamin.Doerr/doerr˙neumann˙book.html.
  * [21] Benjamin Doerr, Frank Neumann, and Andrew M. Sutton.  Time complexity analysis of evolutionary algorithms on random satisfiable $k$-CNF formulas.  Algorithmica, 78:561–586, 2017.
  * [22] Benjamin Doerr and Zhongdi Qu.  From understanding the population dynamics of the NSGA-II to the first proven lower bounds.  In Conference on Artificial Intelligence, AAAI 2023. AAAI Press, 2023.  To appear.
  * [23] John H. Holland.  Adaptation in Natural and Artificial Systems.  University of Michigan Press, 1975.
  * [24] Zhengxin Huang, Yuren Zhou, Zefeng Chen, and Xiaoyu He.  Running time analysis of MOEA/D with crossover on discrete optimization problem.  In Conference on Artificial Intelligence, AAAI 2019, pages 2296–2303. AAAI Press, 2019.
  * [25] Thomas Jansen.  Analyzing Evolutionary Algorithms – The Computer Science Perspective.  Springer, 2013.
  * [26] Thomas Jansen and Ingo Wegener.  On the analysis of evolutionary algorithms – a proof that crossover really can help.  In European Symposium on Algorithms, ESA 1999, pages 184–193. Springer, 1999.
  * [27] Thomas Jansen and Ingo Wegener.  The analysis of evolutionary algorithms – a proof that crossover really can help.  Algorithmica, 34:47–66, 2002.
  * [28] Timo Kötzing.  Concentration of first hitting times under additive drift.  Algorithmica, 75:490–506, 2016.
  * [29] Timo Kötzing, Dirk Sudholt, and Madeleine Theile.  How crossover helps in pseudo-Boolean optimization.  In Genetic and Evolutionary Computation Conference, GECCO 2011, pages 989–996. ACM, 2011.
  * [30] Martin S. Krejca.  Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms.  PhD thesis, Universität Potsdam, 2019.
  * [31] Per Kristian Lehre and Xin Yao.  Crossover can be constructive when computing unique input-output sequences.  Soft Computing, 15:1675–1687, 2011.
  * [32] Melanie Mitchell, John H. Holland, and Stephanie Forrest.  When will a genetic algorithm outperform hill climbing.  In Advances in Neural Information Processing Systems, NIPS 1993, pages 51–58. Morgan Kaufmann, 1993.
  * [33] Frank Neumann, Pietro S. Oliveto, Günter Rudolph, and Dirk Sudholt.  On the effectiveness of crossover for migration in parallel evolutionary algorithms.  In Genetic and Evolutionary Computation Conference, GECCO 2011, pages 1587–1594. ACM, 2011.
  * [34] Frank Neumann and Madeleine Theile.  How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem.  In Parallel Problem Solving from Nature, PPSN 2010, Part I, pages 667–676. Springer, 2010.
  * [35] Frank Neumann and Carsten Witt.  Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity.  Springer, 2010.
  * [36] Pietro S. Oliveto, Jun He, and Xin Yao.  Analysis of population-based evolutionary algorithms for the vertex cover problem.  In Congress on Evolutionary Computation, CEC 2008, pages 1563–1570. IEEE, 2008.
  * [37] Pietro S. Oliveto, Dirk Sudholt, and Carsten Witt.  Tight bounds on the expected runtime of a standard steady state genetic algorithm.  Algorithmica, 84:1603–1658, 2022.
  * [38] Chao Qian, Yang Yu, and Zhi-Hua Zhou.  An analysis on recombination in multi-objective evolutionary optimization.  Artificial Intelligence, 204:99–119, 2013.
  * [39] Dirk Sudholt.  Crossover speeds up building-block assembly.  In Genetic and Evolutionary Computation Conference, GECCO 2012, pages 689–702. ACM, 2012.
  * [40] Andrew M. Sutton.  Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem.  Algorithmica, 83:1138–1163, 2021.