11institutetext: Ecole Polytechnique, Paris, France 22institutetext: ETH
Zürich, Zürich, Switzerland

# How Population Diversity Influences the Efficiency of Crossover

Sacha Cerf 11 Johannes Lengler 22

###### Abstract

Our theoretical understanding of crossover is limited by our ability to
analyze how population diversity evolves. In this study, we provide one of the
first rigorous analyses of population diversity and optimization time in a
setting where large diversity and large population sizes are required to speed
up progress. We give a formal and general criterion which amount of diversity
is necessary and sufficient to speed up the $(\mu+1)$ Genetic Algorithm on
LeadingOnes. We show that the naturally evolving diversity falls short of
giving a substantial speed-up for any $\mu=o(\sqrt{n})$. On the other hand, we
show that even for $\mu=2$, if we simply break ties in favor of diversity then
this increases diversity so much that optimization is accelerated by a
constant factor.

##  1 Introduction

One of the central aspects of genetic algorithms (GAs) is their ability to
recombine existing solutions via crossover. This is considered crucial and
important in practical applications [30]. In order for crossover to be
helpful, it is vital that the population remains diverse, which gives a very
specific setting for the exploration/exploitation dualism. Unfortunately, our
ability to mathematically analyze population diversity and its impact on
runtime has been limited to situations of small populations and/or small
diversity, as we will review below. To already give one example, in easy
hillclimbing settings like the OneMax problem111For $x\in\\{0,1\\}^{n}$, the
OneMax function is defined via $f(x)=\sum_{i=1}^{n}x_{i}$., a tiny Hamming
distance of $2$ between two parents of equal fitness is already beneficial for
crossover. In such situations, crossover has been proven to be helpful [28].

In this paper, we will treat a situation that was not amenable for analysis
with previous techniques, because crossover will only be beneficial if the
population diversity is quite large. More precisely, we will study the
LeadingOnes function $\textsc{LO}(x)$, which returns for $x\in\\{0,1\\}^{n}$
the number of one-bits before the first zero-bit in $x$, see Section 2.1 for
the formal definition. For a string $x$ with $\textsc{LO}(x)=k$, in order to
improve its fitness it is necessary to flip the $(k+1)$st bit in $x$. Thus, it
is rather hard to find such an improvement. OneMax and LeadingOnes are the
most common theoretical benchmarks for hillclimbing in discrete search spaces,
where OneMax is supposed to be particularly easy222In fact, it can be
mathematically proven that OneMax is the easiest problem with unique optimum
for many algorithms [8, 27, 32, 16]. and LeadingOnes is designed to be
particularly hard [26]. By construction of LeadingOnes, a crossover between
two bit-strings $x$ and $y$, where $\textsc{LO}(x)=k$, can only be fitter than
$x$ if the two parents differ specifically in the $(k+1)$st position. This is
a quite strong requirement and this situation will usually only occur if the
population is very diverse. In contrast, on OneMax an offspring of $x$ and $y$
can be fitter than $x$ if the parents differ in _any_ position where $x$ has a
zero-bit, which happens even with minimal population diversity. The main
contribution of this paper is that we develop a method to track the population
diversity even if it is large, and that we give a general criterion to
translate population diversity into runtime333We measure the runtime as the
number of function evaluations until the optimum is evaluated. for the
$(\mu+1)$ GA on LeadingOnes.

###  1.1 Our Results

We analyze the runtime of the elitist $(\mu+1)$ Genetic Algorithm (or
$(\mu+1)$ GA for short) on LeadingOnes. We use standard options for mutation
and crossover operators: standard bit mutation with rate $\chi/n$ for some
constant $\chi>0$ and uniform crossover with uniform parent selection, see
Section 2.2 for details. It was known before that without crossover, the
expected runtime of the $(\mu+1)$ GA on LeadingOnes is
$(1+o(1))\frac{e^{\chi}-1}{2\chi^{2}}n^{2}$ for all $\mu=o(n/\log n)$ [1, 31].

Our first result is that this runtime stays the same for the $(\mu+1)$ GA for
any $\mu=O(\sqrt{n}/\log^{2}n)$, up to a $(1+o(1))$ factor.444For ease of
terminology we will ignore $(1+o(1))$ factors in the rest of this exposition.
The core contribution of the proof lies in showing that the population
diversity, measured by the average Hamming distance of two randomly selected
parents, is bounded by $O(\mu)$. We show in a general setting that this
diversity is too small to speed up the runtime by any constant factor. Our
technique builds on a recent result by Jorritsma, Lengler and Sudholt [16],
who analyzed how population diversity of the $(\mu+1)$ GA evolves in the
absence of selective pressure, i.e., for a flat fitness function. Hence, for
moderately large population sizes, the $(\mu+1)$ GA lacks population
diversity.

Our second result shows that this problem can be overcome easily, as it is
rather easy to increase population diversity. If we simply break ties between
equally fit individuals in favor of diversity, then even for $\mu=2$ the
average Hamming distance increases to $\Omega(n)$. This speeds up optimization
by a constant factor.

#### Intuitive Explanation of the Results

##### Preparation: runtime without crossover.

Let us first recapitulate where the runtime for $\mu=1$ comes from (without
crossover, as this does not make sense for $\mu=1$). When the current search
point $x$ has fitness $\textsc{LO}(x)=k$, then for an improvement it is
necessary to flip the $(k+1)$st bit of $x$, which happens with probability
$\chi/n$. The expected time until this happens is $n/\chi$. There is a second
condition: the bits $1,\ldots,k$ must not be flipped. It can be shown that
this second condition leads to an aggregated factor of $(e^{\chi}-1)/\chi$.
This is not completely obvious, but is also not hard with the modern tools of
_drift analysis_ that have been developed in the last decade [20]. Moreover,
the second condition will not interfere with the effect of crossover, so we
will ignore this technical aspect in the intuitive explanation below.

The two aforementioned conditions for fitness improvement would lead to a
runtime of $(1+o(1))\frac{e^{\chi}-1}{\chi^{2}}n^{2}$ if it was necessary to
visit all $n$ fitness levels. However, this is not necessary. When the
$(k+1)$st bit is flipped, then it may happen by chance that the $(k+2)$nd bit
is already set to one, in which case the algorithm will skip fitness level
$k+1$. This happens with probability $1/2$, and in this case the $(k+2)$nd bit
is called a _free rider_. There can be more than one free rider at once, and
the number of free riders is well-understood: it is geometrically distributed
with parameter $1/2$, and the expected number of free riders in a fitness
improvement is $1$.555The geometric distribution is truncated at $n-k$, so the
expectation is slightly lower than $1/2$, but this subtlety does not affect
the main order term of the runtime. Hence, in expectation only every second
fitness level is visited, which reduces the runtime by a factor of $2$, and
leads to the overal runtime of $(1+o(1))\frac{e^{\chi}-1}{2\chi^{2}}n^{2}$.

Without crossover, the above explanation remains essentially unchanged for
larger $\mu$, as long as $\mu=o(n/\log n)$. The reason is that once the first
individual reaches fitness level $k$, it only takes time
$\Theta(\mu\log\mu)=o(n)$ until all individuals are on this fitness level.
This time is negligible compared to the time that is needed for the next
improvement. Once all individuals have reached fitness $k$, all parents have
the same chance to produce an offspring of larger fitness, so the effect of
the larger population size is negligible. The discussion up to this point was
known from previous work.

##### Extra free riders through crossover.

Our main insight lies in the following. With crossover there is an additional
chance to make progress. Consider the situation that the whole population is
at fitness level $k$, and an offspring $x$ reaches a new fitness level for the
first time. Assume for simplicity that there are no free riders in this step,
so $\textsc{LO}(x)=k+1$, although the effect also exists when free riders are
present. Then $x$ has a one-bit at position $k+1$ and a zero-bit at position
$k+2$. All other individuals have a zero-bit at position $k+1$ because they
all have fitness $k$. But it is possible that there is another individual $y$
which has a one-bit at position $k+2$. If $x$ and $y$ perform a crossover,
then there is a chance of $1/4$ that it gets the one-bit at position $k+1$
from $x$, and the one-bit at position $k+2$ from $y$, i.e., that it combines
the best from the two parents. This effectively gives an _extra free rider_.
If this scenario happens for a constant fraction of all levels, this reduces
the runtime by a constant factor.

There are two key question for the runtime analysis:

  1. 1.

Conditional on $\textsc{LO}(x)=k+1$, how likely is it that there is an
individual $y$ in the population with a one-bit in position $k+2$?

  2. 2.

If there exists such $y$, how likely is it that $y$ transfers its gene to $x$
before it is replaced by individuals of higher fitness?

The answer to the second question is more positive than might seem on first
glance, because in each generation the probability that $y$ passes on its gene
is only $O(1/\mu)$. However, in order to replace the old population by fitter
individuals, the algorithm needs some time: it must select $x$ or its equally
fit descendants at least $\mu$ times. (Here we omit the unlikely case that the
level is reached a second time by mutation.) Intuitively, this corresponds to
$\mu$ chances to select $y$ as the second parent and perform the gene
transfer, each with probability $1/\mu$. The real situation is more complex
since $y$ could be replaced earlier, but it suffices if the gene continues to
exist in the population until half of the population has reached fitness at
least $k+1$. In this case, it already has a chance of $\Omega(1)$ to be passed
on in form of an extra free rider. We will not need this argument directly for
the proofs, but believe that it provides the right intuition: genes that exist
are efficiently transferred into extra free riders.

##### Connection to diversity.

For point 1, recall that $\textsc{LO}(x)=k+1$ means in particular that $x$ has
a zero-bit at position $k+2$. This is key to the situation: we want to obtain
a one-bit in a specific position where $x$ can not provide the one-bit by
itself. Thus, the probability to understand is: how likely is it that the bit
value of $y$ differs from the bit value of $x$ in position $k+2$? This is
closely connected to the Hamming distance between $x$ and $y$ and thus, to the
diversity. In fact, the LeadingOnes function has a high level of symmetry, and
the bits $k+2,\ldots,n$ do not have any effect on the fitness before the
creation of $x$. Hence, if $x$ and $y$ have Hamming distance $d$, then the
bits in which they differ are uniformly at random among $k+2,\ldots,n$ (plus
the two special position $k$ and $k+1$). Thus, we can compute the probability
that $x$ and $y$ differ in position $k+2$ from their Hamming distance, which
is directly connected to the population diversity.

Let us quantify the effect as a function of $\mu$. Once a new fitness interval
is reached, the old population is replaced, which represents a genetic
bottleneck that reduces diversity. Afterwards, the average Hamming distance
starts growing again. If given enough time, it will grow until it reaches
$\Theta(\mu)$, at which point it maxes out because diversity may also get lost
again whenever individuals are removed from the population. These _equilibrium
dynamics_ were recently discovered and quantified in [16]. For
$\mu=o(\sqrt{n})$, this means that the average Hamming distance stays at
$\Theta(\mu)$, and the probability that a fixed individual $y$ differs in
position $k+2$ from $x$ is only $O(\mu/n)$. By a union bound over all $\mu$
individuals, the probability that the desired one-bit exists somewhere in the
population is at most $O(\mu^{2}/n)=o(1)$. Since this one-bit typically does
not exist, crossover has no chance of providing an extra free rider. We prove
this formally, where for technical reasons we make the slightly stronger
assumption $\mu=o(\sqrt{n}/\log^{2}n)$.

If we modify the $(\mu+1)$ GA to break ties in favor of larger population
diversity, then the population dynamics changes. We analyze this case for
$\mu=2$, where the equilibrium shifts from $\Theta(1)$ to $\Theta(n)$.
Moreover, the time required to reach diversity $\Theta(n)$ is only $O(n)$.
This is quick enough to give on average a constant number of extra free riders
per fitness level, which leads to a constant factor speed-up.

Although we do not examine the case in this paper, let us briefly speculate on
the case $\mu=\Omega(\sqrt{n})\cap o(n/\log n)$, without modification of the
tie-breaking rule. This may look promising since the aforementioned
equilibrium dynamics remain true: the average Hamming distance is
$\Theta(\mu)$, so it seems conceivable that point 1 from above has a high
probability. However, we conjecture that this is not the case, and that the
probability is $o(1)$, because the diversity is generated by $o(n)$ positions
who differ in many pairs, while $n-o(n)$ positions are identical throughout
the population. Nevertheless, we believe that this setting is worth exploring,
since a mechanism for increasing diversity in this regime could potentially
lead to runtime $o(n^{2})$. We leave the exploration of this regime to future
work.

###  1.2 Related Work

There is a very long history of theoretical work on crossover, and we can only
give a brief overview. For a thorough overview of the theoretical study of
population diversity we refer to the review by Sudholt [29]. For the more
specific question how diversity can provably decrease runtime, a more detailed
discussion can be found in [6].

Our result on LeadingOnes is by far not the first setting in which crossover
is provably beneficial. Historically one of the first rigorous mathematical
results were for functions that were specifically tailored to make crossover
beneficial, such as the RealRoyalRoad function [15]. A non-tailored example is
the OneMax function mentioned above. Sudholt [28] proved that crossover
accelerates a non-standard version of the $(2+1)$ GA by a constant factor on
OneMax. Subsequent work by Corus and Oliveto [2] showed that a constant factor
speedup is also obtained for the standard $(2+1)$ GA. However, their analyses
rely on the fact that crossover between _any_ two different search points is
helpful for OneMax. So it sufficed to show that the diversity is not literally
zero. Experiments in [2] indicated that larger population sizes than $2$ might
be helpful, but so far it could not be mathematically shown that higher
population sizes $\mu=\omega(1)$ (or even $\mu>2$) leads to substantially
larger diversity that speeds up optimization on OneMax.

Another important benchmark problem is the Jump function, where the optimum is
surrounded by a fitness valley of size $k$. There has been a long and rich
line of research for crossover on this function, particularly on the $(\mu+1)$
GA and some variations [3, 6, 14, 17, 22, 25]. It had been understood early
that mutation can increase diversity substantially [17], but it remained
unclear how crossover influences the population dynamics. Hence, polynomial
runtime bounds independent of $k$ (for constant $k$) could only be shown if
crossover happens so rarely that it does not influence the dynamics of
population diversity [14, 17], or if the process is amended with diversity-
enhancing mechanisms [3]. Without such mechanisms and for larger crossover
probabilities, analyses were for a long time limited to minimal amounts of
diversity [6, 25]. Even so recent results as the work by Doerr, Echarghaoui,
Jamal and Krejca from 2023 [6] could only make use of Hamming distances of at
least one, i.e., the proof relied on showing that crossover is frequently
performed between two individuals which are not identical to each other.
However, very recently Lengler, Opris and Sudholt [22] could show a tight
bound by showing that the typical Hamming distances are $2k$, which is the
maximal possible Hamming distance on the plateau of local optima of Jump.
Hence, they could show that the diversity is very close to the theoretical
maximum. However, they could only show their result for a modified version of
the $(\mu+1)$ GA in which the parents produce several offspring at the same
time, and proceed with the fittest. Nevertheless, the result is a milestone as
is was the first result on Jump in which high amounts of diversity could be
analytically quantified for a crossover-based algorithm without explicit
diversity-enhancing mechanism. Notably, the result in [22] built on the same
techniques from 2023 in [21] that we also build upon.

Other theoretical work has shown benefits of problem-specific crossover
operators [7, 24], of special ways of applying crossover as in the successful
design of the ${(1+(\lambda,\lambda))}$ GA [5], and of crossover that is
enhanced by diversity-preserving mechanisms [3, 19, 23]. A discussion of those
and further results can be found in [6] and [29].

##  2 Preliminaries

In this section, we formally introduce the optimization problem and algorithm
studied in the paper. Then, we introduce the notations that will be used in
our analysis. We also explain the concept of unbiased operators from [18]
since some of our results hold for arbitrary unbiased mutation and crossover
operators.

###  2.1 LeadingOnes

LeadingOnes, or short LO, is the function which assigns to each bit-string $x$
the number of consecutive ones from the left of $x$.

######  Definition 1 (LeadingOnes)

Let $n\in\mathbb{N}$. The LeadingOnes fitness of a bit-string
$x\in\\{0,1\\}^{n}$ is

$\textsc{LO}(x)=\textsc{Leading\\-Ones}(x)=\sum_{i=1}^{n}\prod_{j=1}^{i}x_{j}=\max\\{1\leq
i\leq n\mid\forall 1\leq j\leq i:x_{j}=1\\}.$

We will sometimes write $f$ instead of LeadingOnes for the sake of
conciseness.

The LeadingOnes function is a standard benchmark problem. Besides OneMax, it
is the most common hillclimbing benchmark in discrete domains. While OneMax is
designed as a particularly easy hillclimbing, LeadingOnes was designed as a
harder hillclimbing task [26]: for any search point other than the optima,
there exists only one flip that leads to an improvement of the fitness
function (flipping the first 0-bit).

###  2.2 The $(\mu+1)$ GA

The $(\mu+1)$ Genetic Algorithm, or $(\mu+1)$ GA for short, is described in
Algorithm 1 for arbitrary mutation and (binary) crossover operators and for
arbitrary tie-breaking rules. Our main result will use _standard bit-mutation_
and _uniform crossover_ : standard bit-wise mutation with mutation rate $\chi$
flips every bit of a bit-string independently with probability $\chi/n$, and
uniform crossover consists in taking each bit from one of the two parents,
with equal probability and independently from each other. Pseudo-code for
these operators are in Algorithms 2 and 3. Moreover, we will always break ties
in favor of the offspring except for Section 3.2, where we explicitly study a
variant of the $(2+1)$ GA which uses a diversity-increasing tie-breaking
mechanism.

Some of our results, in particular in Section 2.4.1 are true for more general
mutation and crossover operators and tie-breakers.

1 $t\leftarrow 0$; Generate initial population
$P_{0}\in(\\{0,1\\}^{n})^{\mu}$.

2 repeat

3 With probability $p_{c}$, choose a random parent pair of parents in $P_{t}$
which do not have the same index and generate the offspring $y$ via crossover.
Otherwise, choose a random parent $x\in P_{t}$ and copy it to get $y$.

4 Apply mutation on $y$ to get $y^{\prime}$.

5 Choose $z$ uniform at random among the individuals in $P_{t}$ with minimal
fitness.

6 if  _ $f(y^{\prime})>f(z)$_ then

7 $P_{t+1}\leftarrow P_{t}\backslash\\{z\\}\cup\\{y^{\prime}\\}$.

8 if  _ $f(y^{\prime})=f(z)$ and tie-breaker decides for $y^{\prime}$_ then

9 $P_{t+1}\leftarrow P_{t}\backslash\\{z\\}\cup\\{y^{\prime}\\}$.

10 $t\leftarrow t+1$

11until  _forever_ ;

Algorithm 1 The $(\mu+1)$-GA for maximizing a fitness function $f$.

Input : $y$, bit-string of size $n$

1 for  _$1\leq i\leq n$_ do

2 With probability $p$, set $y_{i}=1-y_{i}$

Algorithm 2 Standard bit-wise mutation

Input : $x_{1},x_{2}$, bit-strings of size $n$

1 Initialize a string $y$ of size $n$

2for  _$1\leq i\leq n$_ do

3 With probability $\frac{1}{2}$, set $y_{i}=x_{1_{i}}$

4 Otherwise, set $y_{i}=x_{2_{i}}$

5

6return _y_

Algorithm 3 Uniform crossover

###  2.3 Notation

General notation. We consider the LeadingOnes function on the search space
$\\{0,1\\}^{n}$ for $n\to\infty$, and all Landau notation like
$O(.),\Omega(.),\ldots$ is with respect to this limit. We denote search points
by $x=(x_{1},...,x_{n})$. For any two search points $x,y$, the _Hamming
distance_ $H(x,y)$ of $x$ and $y$ is the number of positions $1\leq i\leq n$
such that $x_{i}\neq y_{i}$. For $x\in\\{0,1\\}^{n}$, we define
$0_{x}=\\{1\leq i\leq n\mid x_{i}=0\\}$, and $1_{x}=\\{1\leq i\leq n\mid
x_{i}=1\\}$. For $S\subseteq\\{1,\dots,n\\}$, we define $x_{S}=(x_{i})_{i\in
S}$. For the special case where $S$ is an integer interval with lower and
upper bounds $m$ and $M$, we may write $x_{[m:M]}$, or even $x_{[m:]}$ if
$M=n$. Finally, for two random variables $X$ and $Y$, we write $X\preceq Y$
for "$X$ is stochastically dominated by $Y$". We use the same notation if $Y$
is a probability distribution. We write $\mathcal{G}(p)$ for the geometric
distribution with mean $1/p$.

$(\mu+1)$ GA process. We denote by $\chi$ the expected number of bits flipped
by any mutation operator, and assume $\chi=\Theta(1)$ throughout the paper.
For $t\in\mathbb{N}^{*}$,
$P_{t}=\\{x^{t}_{1},\dots,x^{t}_{\mu}\\}\in(\\{0,1\\}^{n})^{\mu}$ is the
population after iteration $t$. $P_{0}$ is the population after
initialization. The best fitness of an individual in $P_{t}$ is denoted
$F_{t}=\max\\{\textsc{LO}(x),$ $x\in P_{t}\\}$. Any individual in $P_{t}$ that
has fitness $F_{t}$ is called _fit_. An offspring will be called "valid" if it
is included in the population at the next iteration. The event "a valid
offspring is produced at timestep $t$" will be denoted by $V_{t}$. For any
$x,y\in P_{t}$, we say that "x produces an offspring" (or "x and y produce an
offspring") if the offspring $y^{\prime}$ in Algorithm 1 is derived by
mutation from a copy of $x$ (in case of no crossover) or from the crossover
between $x$ and $y$ (in case of crossover). We call $C_{t}$ the event "a
crossover was performed at iteration $t$", and $M^{i}_{t}$ the event "bit $i$
is mutated at time $t$".

For $0\leq i\leq n$, we will use the expression "level $i$ is _reached_ " to
signify "$\exists t\in\mathbb{N},F_{t}=i$". This event will also sometimes be
called $R_{i}$. We denote by $T^{\mathrm{in}}_{i}$ the time at which we reach
fitness level $i$, by $T^{\mathrm{o}}_{i}$ the time spent under or at fitness
level $i$, and by $\mathrm{Succ}_{i}$ the fitness level reached after crossing
or leaving fitness level $i$, that is $F_{T^{\mathrm{o}}_{i}+1}$. We say that
a population $P$ is _consolidated_ if all individuals in $P$ have the same
fitness $i$, and in this case we write $f(P)=i$ by slight abuse of notation.
We call the _consolidation time_ for fitness level $i$ the time from reaching
this level until a consolidated population on this fitness level occurs,
$T^{c}_{i}=\min\\{t\geq T^{\mathrm{in}}_{i}\mid\forall x\in P_{t},f(x)=i\\}$.
Note that there may be no consolidated population on fitness level $i$. In
that case, we will say that $T^{c}_{i}=T^{o}_{i}$ by convention. As in [12],
"fitness level $i$ is _essential_ " means that it is reached, and left by
mutation, i.e $R_{i}$ is realized and $C_{T^{\mathrm{o}}_{i}}=0$, or $R_{i}$
is realized and $C_{T^{\mathrm{o}}_{i}}=1$, but the intermediate offspring $y$
generated by crossover at $T^{\mathrm{o}}_{i}$ has fitness lower than $i+1$
(the improvement is brought by the mutated final offspring $y^{\prime}$). We
call this event $E_{i}$. If an essential fitness level $i$ is left before
_consolidation_ ($T^{c}_{i}>T^{\mathrm{o}}_{i}$), it is called "strange",
which is denoted $S_{i}$. An essential fitness level $i$ which is not strange
is called "normal", which is denoted by $N_{i}$. We also denote
$\mathrm{ESucc}_{i}$ the smallest essential fitness level after $i$, i.e.
$\mathrm{ESucc}_{i}:=\min\\{j>i\mid E_{j}\\}$. We set
$\mathrm{ESucc}_{i}:=n+1$ if there is no $j>i$ with $E_{j}$.

Diversity measure. Following [21], we define for a population $P$ the sum of
pairwise Hamming distances in the population $S(P)=\sum_{x\in P}\sum_{y\in
P}H(x,y)$, and for $x\in\\{0,1\\}^{n}$, the sum $S_{P}(x)=\sum_{y\in P}H(x,y)$
of Hamming distances between $x$ and all individuals in $P$. Note that the
average Hamming distance between two individuals (without repetition) is
$\frac{S_{P}(x)}{\mu(\mu-1)}$. When it is clear, we will omit the index of the
population $P$ we are summing over: $S_{P}(x)=S(x)$. Finally, we call
"diversity of the population at time $t$", the quantity
$d_{t}=\frac{S(P^{\prime}_{t})}{\mu(\mu-1)(n-F_{t}-1)}$, where
$P^{\prime}_{t}=\\{x_{[F_{t}+2:]},x\in P_{t}\\}$. This is the average pairwise
Hamming distance of the non-optimized parts of the bit-strings in the
population (not counting the bit just after the current fitness level),
normalized by the size of the non-optimized part of a fit bit-string.

Runtime. For $\mu\in\mathbb{N}^{*}$, the _runtime_ $T^{\mu}=T^{\mu}_{n}$ of
the $(\mu+1)$ GA on LeadingOnes is the number of function evaluations before
the optimum is found.

###  2.4 Unbiased offspring generation mechanisms

Our analysis builds on the fact that, for a given individual in the
population, the bits between $F_{t}+2$ and $n$ are uniformly distributed in
the space of bit-strings of size $n-F_{t}-1$, and that the bits in which two
individuals differ are evenly distributed in this range. As we will show
below, this is generally true if mutation, crossover, and tie-breaker are
_unbiased_ operators. The notion of unbiased operators has been introduced in
[18] as operators which are invariant under automorphisms of the hypercube. We
recall the definition of unbiased operators from [21]. Since the group of
automorphisms is generated by permuations and by applying XOR with fixed bit-
strings, it suffices to require the following two conditions.

###### Definition 2

Let $\psi:(\\{0,1\\}^{n})^{k}\rightarrow\\{0,1\\}^{n}$ be _k-ary operator_.
$\psi$ is _unbiased_ if the following two conditions hold for all
$y,x_{1},\dots,x_{k}\in\\{0,1\\}^{n}$

  1. (i).

For every permutation of $n$ positions $\sigma$,

$\Pr(\psi(x_{1},\dots,x_{k})=y)=\Pr(\psi(\sigma(x_{1}),\dots,\sigma(x_{k}))=\sigma(y)).$

  2. (ii).

For every bit-string $z$ of length $n$,

$\Pr(\psi(x_{1},\dots,x_{k})=y)=\Pr(\psi(x_{1}\oplus z,\dots,x_{k}\oplus
z)=y\oplus z).$

The unbiased framework has been very successful especially in the context of
black-box complexity [11]. Most of the standard mutation operators, such as
standard bit-wise mutation or the heavy-tailed mutation used in _fast GAs_ [9]
are unbiased. Many crossover operators are unbiased, like uniform crossover,
but some, like the single-point crossover, are not, see [13] for details. Our
default in this paper are standard bit-wise mutation and uniform crossover,
both of which are unbiased. Note that a tie-breaker can be considered as a
$(\mu+2)$-ary operator, taking as an input the full population of size $\mu$
and two additional search points between which we want to break ties, one of
which it needs to return.

For the $(\mu+1)$ GA, we call the combination of crossover (if applied),
mutation and tie-breaking as _offspring generation mechanism_ , and we call
such a mechanism unbiased if all three operators that constitute it are
unbiased. We call the algorithm $(\mu+1)$ GA unbiased if its offspring
generation mechanism is unbiased and if it is initialized with a $0$-ary
unbiased operator. We may now prove some useful results that are true for an
unbiased $(\mu+1)$ GA on the LeadingOnes problem. Define, for every
automorphism of the hypercube $\pi$, and every population $P$,
$\pi(P)=\\{\pi(x),x\in P\\}$, and $F(P)=\max\\{\textsc{LO}(y),y\in P\\}$. The
following result states that the $(\mu+1)$ GA with population $P_{t}$ is
invariant under automorphisms that keep the first $F(P_{t})+1$ bits fixed.

###### Lemma 1

Consider a run of the $(\mu+1)$ GA using an unbiased offspring generation
mechanism. Then for all $t\geq 0$, all $Q,P\in\\{0,1\\}^{\mu}$ and all
automorphisms $\pi$ of the hypercube such that for all bit-string $x$, and all
$j\leq F(P)+1$, $\pi(x)_{j}=x_{j}$,

$\Pr(P_{t+1}=Q\mid P_{t}=P)=\Pr(P_{t+1}=\pi(Q)\mid P_{t}=\pi(P)).$

###### Proof

Let $\pi$ be as in the lemma. In the notation of Algorithm 1, the only part of
the algorithm that is not unbiased is the selection of $z$, which is chosen
uniformly random among the individuals in $P_{t}$ with minimal fitness. Denote
the set of individuals with minimal fitness in $P$ by $m(P)$. Then we claim

$\pi(m(P))=m(\pi(P)).$ (1)

To see this, note that all individuals $x\in P$ have fitness at most
$\textsc{LO}(x)\leq F(P)$. Hence, the fitness of $x$ is determined by the bits
$x_{[1:F(P)+1]}$. Since these bits are unchanged under $\pi$, we obtain
$\textsc{LO}(\pi(x))=\textsc{LO}(x)$ for all $x\in P$. In particular, the set
of individuals of minimal fitness in $P$ is unchanged by $\pi$, which implies
(1).

Since $z$ is selected uniformly at random from $m(P_{t})$, Equation (1)
implies for all $z_{0}\in P$,

$\Pr(z=z_{0}\mid P_{t}=P)=\Pr(z=\pi(z_{0})\mid P_{t}=\pi(P)).$

Since all other steps of Algorithm 1 are unbiased, they are invariant under
arbitrary automorphisms, and in particular they are invariant under $\pi$.
This proves Lemma 1.∎

Since $F(P_{t})$ can only increase for the $(\mu+1)$ GA, we obtain the
following symmetry as an immediate consequence.

###### Lemma 2

Consider an unbiased $(\mu+1)$ GA. For all $t\geq 0$, all
$P\in\\{0,1\\}^{\mu}$ and all automorphism $\pi$ of the hypercube such that
for all bit-string $x$, and all $j\leq F(P)+1$, $\pi(x)_{j}=x_{j}$,

$\Pr(P_{t}=P)=\Pr(P_{t}=\pi(P)).$

###### Proof

We proceed by recursion over $t$. For $t=0$, we know that $P_{0}$ is obtained
by a zero-ary unbiased operator, so the proposition is true.

Suppose that the proposition is true for some $t\geq 0$. Then,

∎

Lemma 2 has some interesting corollaries, the first one being on the
distribution of the non-optimized part of a single bit-string in the
population.

###### Corollary 1

For all $1\leq j\leq\mu$, $x^{t}_{j_{[F_{t}+2:]}}$ is uniformly distributed on
$\\{0,1\\}^{n-F_{t}-1}$.

###### Proof

Let $1\leq j\leq\mu$. Let $s,s^{\prime}\in\\{0,1\\}^{n-F_{t}-1}$. Denote by
$b$ the bit-string of length $n$ such that $b_{i}=0$ for all $i\leq F_{t}+1$,
and $b_{[F_{t}+1:]}=s\oplus s^{\prime}$. Then the automorphism of the
hypercube $\pi_{b}$ defined as $\pi_{b}(x)=x\oplus b$ for all
$x\in\\{0,1\\}^{n}$ satisfies the hypothesis of Lemma 2. Moreover, for
$y\in\\{0,1\\}^{n-F_{t}-1}$, if we denote as $\Pi(y)$ the set of populations,
the $j$-th element of which has bits from $F_{t}+2$ to $n$ equal to $x$, then
$\pi_{b}$ induces a bijection between $\Pi(s)$ and $\Pi(s^{\prime})$. It
follows from Lemma 2 that:

$\Pr(P_{t}\in\Pi(s))=\Pr(P_{t}\in\Pi(s^{\prime})),$

which can be rewritten as:

$\displaystyle\Pr(x^{t}_{j_{[F_{t}+2:]}}=s)=\Pr(x^{t}_{j_{[F_{t}+2:]}}=s^{\prime}).$
∎

We also get the following very useful result that helps us bound the size of
the fitness jumps.

###### Corollary 2

For all $t\geq 0$, for all $2\leq j$, $\Pr(F_{t+1}-F_{t}\geq j\mid
F_{t+1}-F_{t}\geq 1)=2^{-(j-1)}$.

###### Proof

Using a similar argument as in the last proof, and the unbiasedness of
$\mathcal{C}$, we simply argue that for all $t\geq 0$, the offspring $y_{t}$
generated at time $t$ is such that $y_{t_{[F_{t}+2:]}}$ is uniformly
distributed over the set of bit-strings of size $n-F_{t}-1$, even conditioned
on the fact that it improves fitness. Hence, the probability that there it has
a streak of $j-1$ $1$-bits starting from position $F_{t}+2$ is $2^{-(j-1)}$. ∎

Finally, we prove this result on the distribution of the bits that differ
between two individuals in the population at a given iteration. Recall that
$d_{t}$ is the average density of non-equal bits in the population when we
restrict to the non-optimized part of the bit-string $[F_{t}+1:n]$.

###### Corollary 3

Let $t\geq 0$, and $1\leq i,i^{\prime}\leq\mu$ with $i\neq i^{\prime}$. Let
$d:=x^{t}_{i_{[F_{t}+2:]}}\oplus x^{t}_{i^{\prime}_{[F_{t}+2:]}}$ be the
string that has a $1$ where $x^{t}_{i}$ and $x^{t}_{i^{\prime}}$ are different
and a $0$ elsewhere, restricted to the non-optimized part. Then, for any pair
of bit-strings $s,s^{\prime}\in\\{0,1\\}^{n-F_{t}-1}$ of equal Hamming weight:

$\Pr(d=s)=\Pr(d=s^{\prime}).$

In particular, for any $j\in[F_{t}+2:n]$ and for all $H\geq 0$,

$\displaystyle\Pr\left((x_{i}^{t})_{j}\neq(x_{i^{\prime}}^{t})_{j}\mid
H(x^{t}_{i_{[F_{t}+2:]}},x^{t}_{{i^{\prime}}_{[F_{t}+2:]}})=H\right)$
$\displaystyle=\frac{H}{n-F_{t}-1}.$

Moreover, if the tie-breaker is symmetric with respect to permutations of the
population and the initial population is uniformly random, then

$\displaystyle\Pr((x_{i}^{t})_{j}\neq(x_{i^{\prime}}^{t})_{j}\mid d_{t})$
$\displaystyle=d_{t}.$

####  2.4.1 Preliminary results on the consolidation process

The following lemmas treat the time of raising the whole population to fitness
at least $i$, after this fitness level has been found. This time is well-known
to have expectation $O(\mu\log\mu)$, e.g. [31]. Here we provide a tail bound.
Note that the crossover probability $p_{c}$ and the parameter
$p_{\text{clone}}$ that appears in the following lemma are not included into
the index of $C_{\beta}$ because those are part of the algorithm, which we
consider as fixed.

###### Lemma 3

Consider the $(\mu+1)$ GA with a mutation operator that has probability
$p_{\text{clone}}$ of duplicating the parent. Let $1\leq i\leq n$ be any
fitness level of LeadingOnes. For any $t\geq 0$, denote by $X_{t}$ the number
of individuals of fitness larger or equal to $i$ in $P_{T^{in}_{i}+t}$. Then,
for any constant $\beta>0$, $p_{\text{clone}}>0$ and $p_{c}<1$, there exists
$C_{\beta}>0$ such that for $n$ big enough the following holds for all
$C>C_{\beta}$.

$\displaystyle\Pr(X_{C\mu\log\mu}<\mu)\leq\mu^{-\beta}.$ (2)

More precisely, the statement holds for
$C\geq(1+\beta)/((1-p_{c})p_{\text{clone}})$. For standard bit mutation with
constant mutation rate $\chi$, Equation (2) holds for all
$C>(1+\beta)e^{\chi}/(1-p_{c})$ if $n$ is sufficiently large.

###### Proof

For $1\leq j\leq\mu-1$, let $T_{j}$ be the random variable denoting the time
to go from $j$ to $s>j$ individuals with fitness larger or equal to $i$ (let
us call such a fitness "large"). If an individual that has large fitness is
chosen for reproduction and makes a copy of itself, the number of individuals
with large fitness increases. This happens with probability at least
$j(1-p_{c})p_{\text{clone}}/\mu$. Now, note that for any $C>0$,

$\Pr(X_{C\mu\log\mu}<\mu)\leq\Pr(\sum_{j=1}^{\mu-1}T_{j}>C\mu\log\mu).$

Finally, we apply Theorem 1.10.35 from [10], which yields (2) for $C\geq
C_{\beta}:=(1+\beta)/((1-p_{c})p_{\text{clone}})$. For standard bit mutation
with mutation rate $\chi$, the statement follows from
$p_{\text{clone}}=(1-\chi/n)^{n}=(1-o(1))e^{-\chi}$, and hence
$(1+\beta)/((1-p_{c})p_{\text{clone}})<C$ for sufficiently large $n$.∎

The above lemma immediately translates into a tail bound for the consolidation
time $T_{i}^{c}$. Recall that this is the first time when either all
individuals have fitness at least $i$, or at least one individual has fitter
strictly larger than $i$.

###### Lemma 4

In the situation of Lemma 3, for any constant $\beta>0$, $p_{\text{clone}}>0$,
$p_{c}<1$ and $C>C_{\beta}$ and any fitness level $1\leq i\leq n$, if $n$ is
sufficiently large,

$\Pr(T^{c}_{i}-T^{\mathrm{in}}_{i}>C\mu\log\mu)\leq\mu^{-\beta}.$

###### Proof

Let $1\leq i\leq n$ be any fitness level. For any $t\geq 0$, denote by $X_{t}$
the number of individuals of fitness larger or equal to $i$ in
$P_{T^{in}_{i}+t}$. For $0\leq t\leq T^{c}_{i}-T^{in}_{i}$, there are no
individuals with fitness larger than $i$ in the population, so the population
is consolidated on $i$ at time $C\mu\log\mu$ if and only if
$X_{C\mu\log\mu}=\mu$. Hence,

$\displaystyle\Pr(T^{c}_{i}-T^{\mathrm{in}}_{i}>C\mu\log\mu)$
$\displaystyle=\Pr(X_{C\mu\log\mu}<\mu\cap
T^{c}_{i}-T^{\mathrm{in}}_{i}>C\mu\log\mu)$
$\displaystyle\leq\Pr(X_{C\mu\log\mu}<\mu).$

We conclude by Lemma 3.∎

As mentioned above, the same bound also holds in expectation. This can either
be derived from Lemma 4 with a bit of computation or taken from [31].

###### Corollary 4

For any fitness level $1\leq i\leq n$,
$\mathbb{E}[T^{c}_{i}-T^{\mathrm{in}}_{i}]=O(\mu\log\mu)$.

##  3 Analysis of the $(\mu+1)$ GA on LeadingOnes for different population
regimes

In this section, we will first show that the number of extra free-riders
determines the expected runtime of the $(\mu+1)$ GA. Throughout the section,
we will assume that the $(\mu+1)$ GA uses standard bit mutation where the
mutation rate $\chi$ and the crossover probability $p_{c}<1$ are constants.
However, at first the algorithm may use any respectful666In a respectful
crossover, if both parents have the same bit at some position $i$, the
offspring also has the same bit at position $i$. unbiased crossover operator
and and unbiased tie-breaking rule.

In Section 3.1, we show that if $\mu=O(\sqrt{n}/\log^{2}n)$ then the leading
constant of the runtime remains unchanged. However, as we show in 3.2, even
for $\mu=2$, a simple diversity-preserving mechanism suffices to obtain a
constant speedup factor. Our strategy is based on the notion of _extra free-
riders_ due to crossover, as introduced in Section 2.3. This term is derived
from the term "free-rider" originating in [12], defined as follows.

######  Definition 3 (free-riders)

Let $x$ be a bit-string of size $n$, and suppose that $\textsc{LO}(x)=i$ for
some $1\leq i\leq n-2$. The free-riders of $x$ are the leading ones of the
sub-string $(x_{i+2},\dots,x_{n})$.

In other words, a free-rider of a bit-string $x$ is a bit that automatically
becomes a leading one as soon as the first zero bit of $x$ is flipped. In an
evolutionary optimization context, these free-riders allow us to skip some
fitness levels. In the context of the $(\mu+1)$ GA, we prefer to associate
free riders with a fitness level $i$ as follows. Recall that $E_{i}$ is the
event that the $i$-th fitness level is essential.

######  Definition 4 (Free-riders associated to a fitness level)

For $0\leq i\leq n-1$, we denote as $F_{i}$ and call "free-riders associated
to level $i$" the following random variable.

$F_{i}=\begin{cases}\mathrm{Succ}_{i}-i-1&\text{if $E_{i}$}\\\
0&\text{otherwise}\end{cases}$

Extending on this idea, we define "extra free-riders" as additional leading
ones that are obtained with crossover.

######  Definition 5 (extra free-riders)

Let $x$ and $x^{\prime}$ be two bit-strings of size $n$. Denote
$\textsc{Leading\\-Ones}(x)=i$, $\textsc{Leading\\-Ones}(x^{\prime})=j$, and
suppose $j>i$. Consider the result $y$ of a crossover between $x$ and
$x^{\prime}$, with $\textsc{Leading\\-Ones}(y)=k$. The extra free-riders
brought by this crossover are the bits $y_{[j+1:k]}$.

Note that if the crossover operator is _respectful_ , which is the case for
most common crossover operators (see [21] for a classification), then the
1-bits at positions $j+1,\dots,k$ come from either $x$ or $x^{\prime}$. Thus,
the reason why we suggest the name "extra free-rider" is because, just like
normal free-riders, these 1-bits already _accidentally_ exist among the
population (that is, they are not here because of an optimization choice of
the algorithm, but because of genetic drift), and allow us to overcome some
fitness plateaus in negligible time.

The typical scenario for the acquisition of extra free-riders is that, after
the whole population is brought to a common fitness plateau, diversity
accumulates on the non-optimized trailing part of the bit-strings. Then, when
an individual $x$ reaches a higher fitness level, some individuals in the
lower levels may happen to have a $1$-bit at the position corresponding to the
next fitness level. If a crossover between one of these individuals and an
individual of fitness $f(x)$ is performed, then with a good probability we get
extra free-riders. These extra free-riders can be obtained from multiple
successive crossovers, until the next fitness level is left via mutation. We
introduce a useful definition that stems from this observation. Recall that
$\mathrm{ESucc}_{i}$ is the smallest essential fitness level after level $i$.

######  Definition 6 (Extra free-riders associated to a fitness level)

For $0\leq i\leq n-1$, we denote as $\mathrm{EF}_{i}$ and call "extra free-
riders associated to level $i$" the following random variable.

$\mathrm{EF}_{i}=\begin{cases}\mathrm{ESucc}_{i}-\mathrm{Succ}_{i}&\text{if
$E_{i}$}\\\ 0&\text{otherwise}\end{cases}$

The two following lemmas draw a link between the expected value of
$\mathrm{EF}_{i}$ for any reached fitness level $i$ in a given implementation
of the $(\mu+1)$ GA, and the expected runtime of the algorithm. Recall that we
consider the $(\mu+1)$ GA with standard bit-wise mutation with mutation rate
$\chi=\Theta(1)$, $p_{c}<1$, any respectful crossover operator, and any
unbiased tie-breaker, but the proof may be adapted to most known mutation
mechanisms.

###### Lemma 5

Consider the $(\mu+1)$ GA with standard bit mutation and any respectful
unbiased mutation operator. Suppose that there exists a sequence of functions
$(m_{n})_{n\in\mathbb{N}}$, uniformly convergent to a function $m$, and
$k(n)=\omega(1)$, such that
$\varepsilon_{m_{n}}=\max\\{|m_{n}(x)-m_{n}(y)|\mid|x-y|\leq\frac{n}{k}\\}=o(1)$,
and, for all fitness level $0\leq i\leq n-1$, $\Pr(\mathrm{EF}_{i}\geq 1\mid
N_{i})\geq m_{n}(\frac{i}{n})$. Then:

$\mathbb{E}[T^{\mu}]\leq\frac{n^{2}}{\chi}\int_{0}^{1}\frac{e^{\chi
x}}{2+m(x)}dx+o(n^{2}).$

###### Lemma 6

Consider the $(\mu+1)$ GA with standard bit mutation and any respectful
unbiased mutation operator. Suppose that there exists a sequence of functions
$(M_{n})_{n\in\mathbb{N}}$ defined on $[0,1]$, uniformly convergent to a
function $M$, and $k(n)=\omega(1)$, such that
$\varepsilon_{M_{n}}=\max\\{|M_{n}(x)-M_{n}(y)|\mid|x-y|\leq\frac{n}{k}\\}=o(1)$,
and, for all fitness level $0\leq i\leq n-1$, $\mathbb{E}[\mathrm{EF}_{i}\mid
N_{i}]\leq M_{n}(\frac{i}{n})$. Suppose also that the event $A:$ "for all
$1\leq i\leq n,\mathrm{ESucc}_{i}-i=o(\frac{n}{\max(k,\mu\log\mu)})$" holds
with high probability. Then:

$\mathbb{E}[T^{\mu}]\geq\frac{n^{2}+o(n^{2})}{\chi}\int_{0}^{1}\frac{e^{\chi
x}}{2+M(x)}dx.$

Everything remains true if the bound for $\mathbb{E}[EF_{i}\mid N_{i}]$ holds
for $o(n)\leq i\leq n-o(n)$, but for the sake of simplicity, we will suppose
that the bounds hold for any $i$.

###### Observation 1

Note that for the case where $m_{n}$ is constant, the inequality from Lemma 5
becomes:

$\mathbb{E}[T^{\mu}]\leq\frac{1}{2+m_{n}}\frac{e^{\chi}-1}{\chi^{2}}n^{2}+o(n^{2}),$

and similarly, for the case where $M_{n}$ is constant, the inequality from
Lemma 6 becomes:

$\mathbb{E}[T^{\mu}]\geq\frac{1}{2+M_{n}}\frac{e^{\chi}-1}{\chi^{2}}n^{2}+o(n^{2}).$

###### Observation 2

When $p_{c}=0$, one can simply set $m_{n}=M_{n}=0$, and obtain:

$\mathbb{E}[T^{1}]=\frac{e^{\chi}-1}{2\chi^{2}}n^{2}+o(n^{2}),$

which is, up to a negligible term, the runtime proved by [1] for the ${(1+1)}$
EA.

The reader may notice that these two lemmas are stated in a much stronger form
that what we will use in this paper, that is, the case where $M_{n}$ or
$m_{n}$ are constant. This is because we believe they can be a useful tool for
whoever would like to study other variants of the $(\mu+1)$ GA, where these
two quantities might depend on the current fitness level.

To prove these lemmas, we will need two preparatory results. The first one
will help us neglect strange fitness levels.

###### Lemma 7

For any fitness level $0\leq i\leq n-1$,
$\Pr(S_{i})=O\left(\frac{\mu\log\mu}{n}\right)$.

###### Proof

Let $0\leq i\leq n-1$ be any fitness level. For any integer $k\geq 0$, denote
by $A_{k}$ the event "between time steps $T_{i}^{in}$ and
$T_{i}^{in}+k\mu\log\mu$, the population consolidates on $i$", and for $k\geq
1$ denote by $M_{k}$ the event "between time steps
$T_{i}^{in}+(k-1)\mu\log\mu$ and $T_{i}^{in}+k\mu\log\mu$, level $i$ is left
by mutation" . For $S_{i}$ to happen, it must be that for some $k\geq 0$,
$A_{j}$ is not realized and $M_{k+1}$ is. Hence, by a union bound,

$\displaystyle\Pr(S_{i})$
$\displaystyle\leq\sum_{k=0}^{\infty}\Pr(\bar{A_{k}}\cap M_{k+1}).$

Now, note that during a time frame of $\mu\log\mu$, by a union bound, the
probability to flip the $i+1$-st bit is at most $\frac{\chi\mu\log\mu}{n}$,
independently of previous steps. Hence, for $k\geq 0$,
$\Pr(M_{k+1}\mid\bar{A_{k}})\leq\frac{\chi\mu\log\mu}{n}$. Moreover, by Lemma
4 there is a constant $C>0$ such that $\Pr(\bar{A_{k}})\leq\mu^{-C(k-1)}$ for
all $k\geq 0$. We deduce that $\sum_{k=0}^{\infty}\Pr(\bar{A_{k}}\cap
M_{k+1})\leq\sum_{k=0}^{\infty}\frac{\chi\mu\log\mu}{n}\cdot\mu^{-C(k-1)}=O(\frac{\mu\log\mu}{n})$,
which concludes the proof. ∎

The second preliminary result essentially tells that we need to focus our
efforts on studying the time spent on normal fitness levels.

###### Lemma 8

For $\mu=o(n/\log n)$ the following equality holds:

$\mathbb{E}[T^{\mu}]=\sum_{i=0}^{n-1}\mathbb{E}[\mathds{1}_{N_{i}}(T^{\mathrm{o}}_{i}-T^{c}_{i})]+o(n^{2}).$

###### Proof

The only fitness levels $i$ for which $T^{c}_{i}<T^{\mathrm{o}}_{i}$ are
normal fitness levels. Hence, the runtime of the $(\mu+1)$ GA can be
decomposed as:

$T^{\mu}=\sum_{i=0}^{n-1}\mathds{1}_{N_{i}}(T^{\mathrm{o}}_{i}-T^{c}_{i})+\sum_{i=0}^{n-1}(T^{c}_{i}-T^{\mathrm{in}}_{i}).$

By Corollary 4, the second term is at most $O(n\mu\log\mu)=o(n^{2})$ in
expectation, which concludes the proof.∎

With this preparation, we can now prove Lemma 5 and 6.

######  Proof (of Lemma 5)

By Lemma 8 we may focus on normal levels. We observe that on any normal
fitness level $i$, we have
$T^{\mathrm{o}}_{i}-T^{c}_{i}\sim\mathcal{G}((1-\frac{\chi}{n})^{i}\frac{\chi}{n})$.
Indeed, from the moment when consolidation happens, every individual in the
population has fitness level $i$. Consequently, at each iteration, regardless
of which parent(s) we select, and of whether we use crossover or not (since
the crossover operator is respectful, it conserves common bits among the
parents, in which case the first $i$ 1-bits are always copied to the
offspring), the probability of producing an offspring with fitness level
higher than $i$ is determined only by the mutation phase, where we have to
keep the first $i$ bits untouched (with probability $(1-\frac{\chi}{n})^{i}$)
and mutate the $(i+1)$-st bit (with probability $\frac{\chi}{n}$).

We also need to know how many normal levels there are in a local window of
fitness levels. This number will depend on the expected size of the jumps
between essential fitness levels, which in turn depends on the expected number
of extra free-riders associated to normal fitness levels. The more extra free-
riders we get, the sparser normal fitness levels are, and the faster the
optimization is. To make this precise, we will use the following argument: we
partition the fitness level in local fitness windows of size $\frac{n}{k}$
(where $k$ is defined in the statement of the lemma), and then, we show that
the expected cumulative size of the jumps starting from normal fitness levels
inside these windows is roughly $\frac{n}{k}$. Combining this observation with
the upper or lower bound on the expected number of extra free-riders
associated to normal fitness levels, which is roughly uniform over the local
fitness windows, we can count the expected number of normal fitness levels
inside the window, which allows us to bound the first term by splitting it
into smaller sums over these local windows. Following this idea, let us
define, for $0\leq j\leq k$, $i_{j}=\frac{jn}{k}$. Then, for $i_{j}\leq
i<i_{j+1}$, define the truncated number of extra free-riders associated to
fitness level $i$ as

$\widetilde{\mathrm{EF}}_{i}:=\min(i_{j+1},\mathrm{ESucc}_{i})-\mathrm{Succ}_{i}.$

We will first argue that for all $0\leq j\leq k-1$:

$\sum_{i=i_{j}}^{i_{j+1}-1}\mathds{1}_{E_{i}}(1+F_{i}+\widetilde{\mathrm{EF}}_{i})\leq\frac{n}{k}.$
(3)

Indeed, the sum in the middle is simply $i_{j+1}-L_{j}$, where $L_{j}$ is the
first essential level in $[i_{j},i_{j+1}]$, if such a level exists. In
particular the sum is at least $i_{j+1}-i_{j}=\frac{n}{k}$. If no essential
level exists then the sum is zero and the bound is still true.

Recall that $N_{i}$ denotes the event that level $i$ is normal. Since
$N_{i}\subset E_{i}$, we deduce that:

$\sum_{i=i_{j}}^{i_{j+1}-1}\mathds{1}_{N_{i}}(1+F_{i}+\widetilde{\mathrm{EF}}_{i})\leq\frac{n}{k}.$
(4)

Note that $\mathbb{E}[\widetilde{\mathrm{EF}_{i}}\mid
N_{i}]\geq\Pr(\mathrm{EF}_{i}\geq 1\mid N_{i})\geq m_{n}(\frac{i}{n})$. Using
$(F_{i}\mid N_{i})\preceq\mathcal{G}(\frac{1}{2})-1$, this yields for all
level $i$:

$\mathbb{E}[\mathds{1}_{N_{i}}(1+F_{i}+\widetilde{\mathrm{EF}_{i}})]\geq\mathbb{E}[\mathds{1}_{N_{i}}](2+m_{n}(\frac{i}{n})).$

Hence, by definition of $\varepsilon_{M_{n}}$, for $i_{j}\leq i\leq
i_{j+1}-1$,

$\mathbb{E}[\mathds{1}_{N_{i}}(1+F_{i}+\mathrm{EF}_{i})]\geq\mathbb{E}[\mathds{1}_{N_{i}}](2+m_{n}(\frac{i_{j}}{n})-\varepsilon_{m_{n}})=\mathbb{E}[\mathds{1}_{N_{i}}](2+m_{n}(\frac{j}{k})-\varepsilon_{m_{n}}).$

Plugging this last inequality into (4), we get the desired bound for the
expected number of essential levels in the local window $i_{j}\leq i<i_{j+1}$.

$\sum_{i=i_{j}}^{i_{j+1}-1}\mathbb{E}[\mathds{1}_{N_{i}}]\leq\frac{n}{k(2+m_{n}(\frac{j}{k})-\varepsilon_{m_{n}})}$

By Lemma 8 and the fact that
$T^{\mathrm{o}}_{i}-T^{c}_{i}\sim\mathcal{G}((1-\frac{\chi}{n})^{i}\frac{\chi}{n})$,
it suffices to bound
$\sum_{i=0}^{n-1}\mathbb{E}[\mathds{1}_{N_{i}}\mathcal{G}((1-\frac{\chi}{n})^{i}\frac{\chi}{n})]$.
We decompose this sum in smaller sums over the local windows:

$\displaystyle\begin{split}\sum_{i=0}^{n-1}\mathbb{E}[\mathds{1}_{N_{i}}\mathcal{G}((1-\frac{\chi}{n})^{i}\frac{\chi}{n})]&=\sum_{j=0}^{k-1}\sum_{i=i_{j}}^{i_{j+1}-1}\mathbb{E}[\mathds{1}_{N_{i}}\mathcal{G}((1-\frac{\chi}{n})^{i}\frac{\chi}{n})]\\\
&\leq\sum_{j=0}^{k-1}\sum_{i=i_{j}}^{i_{j+1}-1}\mathbb{E}[\mathds{1}_{N_{i}}](1-\frac{\chi}{n})^{-i}\frac{n}{\chi}\\\
&\leq\sum_{j=0}^{k-1}\frac{n}{k(2+m_{n}(\frac{j}{k})-\varepsilon_{m_{n}})}\frac{n}{\chi}(1-\frac{\chi}{n})^{-{i_{j}}}\\\
&\leq\frac{n^{2}}{\chi}\left(\frac{1}{k}\sum_{j=0}^{k-1}\frac{1}{2+m_{n}(\frac{j}{k})+\varepsilon_{m_{n}}}((1-\frac{\chi}{n})^{-n})^{\frac{j}{k}})\right).\end{split}$
(5)

Thanks to the uniform convergence of $m_{n}$ to $m$, and of the function
$x\rightarrow(1-\frac{\chi}{n})^{-nx}$ to to the function $x\rightarrow
e^{\chi x}$ over $x\in[0,1]$ when $n\longrightarrow\infty$, the term between
parentheses converges to $\int_{0}^{1}\frac{e^{\chi x}}{2+m(x)}$ as
$k\to\infty$. This concludes the proof.∎

The proof of Lemma 6 is very similar, but requires a little bit more work to
justify that exceedingly large jumps cannot occur.

######  Proof (of Lemma 6)

The proof follows the same steps than that of Lemma 5, but we need to work
conditioned on $A$. As in the previous proof, for $0\leq j\leq k$, define
$i_{j}=\frac{jk}{n}$.

Conditioned on $A$, the first fitness level $L_{j}$ reached in the window
$[i_{j},i_{j+1}]$ is at most
$i_{j}+o\left(\frac{n}{\max(\mu\log\mu,k)}\right)$. Following an analogous
argument than for inequality (3), we have for all $0\leq j\leq k-1$:

$\frac{n}{k}-o\left(\frac{n}{\max(\mu\log\mu,k)}\right)-1=\frac{n+o(n)}{k}\leq\sum_{i=i_{j}}^{i_{j+1}-1}\mathds{1}_{E_{i}}(1+F_{i}+\mathrm{EF}_{i}).$
(6)

Now, we need to argue that strange fitness levels do not contribute too much
to the above quantity in expectation. This contribution is exactly:

$\sum_{i=i_{j}}^{i_{j+1}-1}\mathbb{E}[\mathds{1}_{S_{i}}(1+F_{i}+\mathrm{EF}_{i})\mid
A]=\sum_{i=i_{j}}^{i_{j+1}-1}\Pr(S_{i}\mid A)(1+\mathbb{E}[F_{i}\mid
S_{i},A]+\mathbb{E}[\mathrm{EF}_{i}\mid S_{i},A]).$

The second factor of each summand is simply
$\mathbb{E}[\mathrm{ESucc}_{i}-i\mid A,S_{i}]$, which is
$o(\frac{n}{\mu\log\mu})$ by definition of $A$. Moreover, by Lemma 7
$\Pr(S_{i}\mid
A)\leq\frac{\Pr(S_{i})}{P(A)}=\frac{P(S_{i})}{1-o(1)}=o(\frac{\mu\log\mu}{n})$.
This yields that the total contribution of strange levels is
$o(1)(i_{j+1}-i_{j})=o(\frac{n}{k})$. Hence, conditioned on $A$, the lower
bound (6) that holds for essential levels, also holds for normal levels.

$\frac{n+o(n)}{k}\leq\sum_{i=i_{j}}^{i_{j+1}-1}\mathds{1}_{N_{i}}(1+F_{i}+\mathrm{EF}_{i}).$
(7)

By an analogous computation to the proof of Lemma 5, we obtain:

$\sum_{i=0}^{n-1}\mathbb{E}[\mathds{1}_{N_{i}}\mathcal{G}(1-\frac{\chi}{n})^{i}\frac{\chi}{n}]\geq\frac{n^{2}+o(n^{2})}{\chi}\int_{0}^{1}\frac{e^{\chi
x}}{2+M(x)}dx.$

Finally,

$\displaystyle\mathbb{E}[T^{\mu}]$ $\displaystyle\geq
P(A)\mathbb{E}[T^{\mu}\mid A]$
$\displaystyle\geq(1-o(1))\sum_{i=0}^{n-1}\mathbb{E}[\mathds{1}_{N_{i}}\mathcal{G}(1-\frac{\chi}{n})^{i}\frac{\chi}{n}]$
$\displaystyle\geq\frac{n^{2}+o(n^{2})}{\chi}\int_{0}^{1}\frac{e^{\chi
x}}{2+M(x)}dx,$

following the same steps as in 5.∎

###  3.1 The vanilla $(\mu+1)$ GA is not faster than the vanilla ${(1+1)}$ EA
for $\mu\in O(\sqrt{n}/\log^{2}n)$.

In this section, we show that one cannot expect speedups in using the vanilla
$(\mu+1)$ GA compared to the ${(1+1)}$ EA for any population size
$\mu=O(\sqrt{n}/\log^{2}n)$. We call "vanilla" the implementation of the
$(\mu+1)$ GA consisting in standard bit-wise mutation, uniform crossover and
uniform tie-breaker. This absence of a substantial speedup stems from the fact
that such populations reach a natural diversity equilibrium which is not big
enough to be exploited by crossover. This leads to a small number of expected
extra free-riders, and hence, by Lemma 6, a negligible speedup.

We will first show inductively that with high probability there are no gaps
larger than $O(\log n)$ between normal fitness levels. To this end, we will
make the simplifying assumption that the population is initialized with the
all-0 bit-strings. This slight cheat conveniently provides us with the base
case of the induction. We do not believe that this is really needed, but did
not see an easy way to remove this assumption.

We will first show that the expected diversity when leaving a given fitness
level is small.

###### Lemma 9

Consider the $(\mu+1)$ GA with population size $\mu=o(\sqrt{n})$. Let $1\leq
i\leq n-\omega(\mu)$ and suppose that at some timestep $t_{0}\geq 0$,
$P_{t_{0}}$ is consolidated, and $f(P_{t_{0}})=i$. Then,

$\mathbb{E}[d_{T^{o}_{i}}]\leq
O\left(d(P_{t_{0}})\frac{\mu^{2}}{n}+\frac{\mu}{n-i}\right).$

###### Proof

We rely on a result from [21] (Corollary 3.4 and Theorem 4.3) which we restate
here in a simplified form:

###### Lemma 10

Consider a population $Q_{t}=\\{x_{1},\dots,x_{\mu}\\}$ of individuals of size
$N>0$. Consider any process that

  1. 1.

creates $y$ by any random procedure such that $\mathbb{E}(S(y))=S(Q_{t})/\mu;$

  2. 2.

creates $y^{\prime}$ from $y$ by an unbiased mutation operator which flips
$\chi$ bits in expectation;

  3. 3.

sets $Q_{t+1}=Q_{t}\cup\\{y^{\prime}\\}\backslash\\{x_{d}\\}$ for a uniformly
random $1\leq d\leq\mu$.

Then,

$\mathbb{E}[S(Q_{t+1})\mid
S(Q_{t})]=\left(1-\frac{2}{\mu^{2}}-\frac{4(\mu-1)\chi}{\mu^{2}N}\right)S(Q_{t})+2(\mu-1)\chi.$

Moreover, let $T_{d}=\inf\\{t\mid S(Q_{t})\leq 2\alpha\\}$, where
$\alpha:=\frac{2(\mu-1)\mu^{2}\chi n}{n+4(\mu-1)\chi}$. If $\mu=o(n)$, then

$\mathbb{E}[T_{d}]=O(\mu^{2}\log n).$

The population $P_{t}$ of the vanilla $(\mu+1)$ GA running on LeadingOnes
clearly verifies hypotheses 1 and 2. However, it does not verify hypothesis 3
as is. To make use of Lemma 10, we need to do some rescaling. First, we fix a
normal level $0\leq i\leq n-\omega(\mu)$. We denote by $T^{\mathrm{val}}_{j}$
the $j$-th time where a valid offspring is generated after
$T^{\mathrm{in}}_{i}$. Note that $T^{\mathrm{val}}_{0}$ is equal to
$T^{\mathrm{in}}_{i}$. Then, we define, for $t\geq 0$,
$Q_{t}=\\{x_{[F_{t}+2:]},x\in P_{T^{\mathrm{val}}_{t}}\\}$. The population
$Q_{t}$ now verifies the hypotheses for Lemma 10, for $t$ such that
$T^{\mathrm{val}}_{t}\leq T^{\mathrm{o}}_{i}$. Let $t^{*}$ be the last $t$
such that $T^{\mathrm{val}}_{t^{*}}\leq T_{i}$. Then,
$\mathcal{G}(\frac{\chi}{n})\preceq t^{*}$: since $i$ is normal, we know that
it will be left by mutation, and every validated offspring produced via
mutation has probability $\frac{\chi}{n}$ to have fitness higher than $i$.
Denote $n_{i}=n-i$, and note that $n_{i}=\omega(\mu)$ by hypothesis. For
$t\leq t^{*}$:

$\mathbb{E}[S(Q_{t+1})\mid
S(Q_{t}),t^{*}]=\left(1-\frac{2}{\mu^{2}}+\frac{4(\mu-1)\chi}{\mu^{2}n_{i}}\right)S(Q_{t})+2(\mu-1)\chi,$

where we note that $\frac{4(\mu-1)\chi}{\mu^{2}n_{i}}=o(\frac{1}{\mu^{2}})$.
Denote by $\alpha$ the fixed point of this arithmetic-geometric recursion. It
is easy to see that $\alpha=\Theta(\mu^{3})$, see [21].

Solving the recursion yields:

$\displaystyle\mathbb{E}[S(Q_{t^{*}})\mid
t^{*}]=(S(P_{t_{0}})-\alpha)\left(1-\frac{2}{\mu^{2}}+o\left(\frac{1}{\mu^{2}}\right)\right)^{t^{*}}+\alpha,$

Thus, by the law of total expectation:

$\displaystyle\mathbb{E}[S(Q_{t^{*}})]$
$\displaystyle\leq\sum_{t=1}^{\infty}\frac{\chi}{n}(1-\frac{\chi}{n})^{t-1}\alpha\left[1-(1-\frac{2}{\mu^{2}}+o(\frac{1}{\mu^{2}}))\right]^{t*}$
$\displaystyle+S(P_{t_{0}})\sum_{t=1}^{\infty}\frac{\chi}{n}(1-\frac{\chi}{n})^{t-1}\left[1-\frac{2}{\mu^{2}}+o(\frac{1}{\mu^{2}})\right]^{t^{*}}.$

Noticing that, by virtue of $\mu^{2}=o(n)$,

$\sum_{t=1}^{\infty}\frac{\chi}{n}(1-\frac{\chi}{n})^{t-1}\left[1-\frac{2}{\mu^{2}}+o(\frac{1}{\mu^{2}})\right]^{t^{*}}=\frac{\chi}{n}\frac{1-\frac{2}{\mu^{2}}+o(\frac{1}{\mu^{2}})}{1-(1-\frac{\chi}{n})(1-\frac{2}{\mu^{2}}+o(\frac{1}{\mu^{2}}))}=O(\frac{\mu^{2}}{n}),$

one obtains:

$\displaystyle\mathbb{E}[S(Q_{t^{*}})]\leq\alpha(1-O(\frac{\mu^{2}}{n}))+O(S(P_{t_{0}})\frac{\mu^{2}}{n})=O(\mu^{3}+S(P_{t_{0}})\frac{\mu^{2}}{n}).$

Since $S(Q_{t}^{*})=S(P_{T^{o}_{i}})$, this yields:

$\displaystyle\mathbb{E}[d_{T^{o}_{i}}]\leq\frac{\mathbb{E}[S(Q_{t^{*}})]}{O(\mu^{2}n_{i})}=O(\frac{\mu}{n_{i}}+d(P_{t_{0}})\frac{\mu^{2}}{n}).$
∎

Next we show inductively that the algorithm frequently encounters consolidated
fitness levels with small diversity. We use the following terminology.

###### Definition 7

We call a population $P$ of size $\mu$ _good_ if $P$ is consolidated (all
individuals have the same fitness) and $d(P)\leq 1/\mu$. For the $(\mu+1)$ GA
on LeadingOnes, we call a fitness level $i$ _good_ if there exists a good
population $P_{t}$ with $f(P_{t})=i$.

We can now show by induction that good fitness levels are never more than
$O(\log n)$ apart. The inductive step is provided by the following lemma.

###### Lemma 11

Suppose that $\mu=O(\sqrt{n}/\log^{2}n)$ and that $i=n-\omega(\mu^{2})$ is a
good fitness level. Then with probability $1-o(1/n)$ the next good fitness
level $i^{\prime}$ satisfies $i^{\prime}=i+O(\log n)$.

###### Proof

Consider a good population $P_{t}$ on level $i$ and a position $j>i+1$. Recall
that if not all individuals are identical in position $j$, then it contributes
at least $2\mu-2$ to the diversity. Hence, the number of such $j$ in which not
all individuals are identical is at most
$S(P_{t})/(2\mu-2)=\tfrac{\mu}{2}(n-i-1)d_{t}\leq(n-i-1)/2$ since $P_{t}$ was
good. Hence, at least half of the $n-i-1$ non-optimized positions are
identical in all individuals in $P_{t}$. By symmetry, each such position has
probability exactly $1/2$ that the whole population has a zero-bit. Let us
call such positions _stopping positions_. By the Chernoff bound, for a
suitable constant $C>0$ the number of stopping positions among the next $C\log
n$ fitness levels $i+2,\ldots,i+C\log n+1$ is at least $\log n$ with
probability $1-o(1/n)$.

Now consider the next $\tau:=C^{2}\mu^{2}\log^{3}n=o(n)$ generations. The
probability that a fixed stopping position is flipped by at least one mutation
during that time is $o(1)$. Hence, the probability that all $\log n$ stopping
positions are flipped at least once is $o(1/n)$. Hence, with probability
$1-o(1/n)$ the fitness will not exceed $i+C\log n$ during those $\tau$
generations. By pigeonhole principle there must be a fitness level $j$ on
which the algorithm spends at least $\tau^{\prime}:=\tau/(C\log
n)=C\mu^{2}\log^{2}n$ generations. In the following we will analyze the
behaviour on this level $j$.

Once the fitness level $j$ is reached by at least one individual, with
probability $1-o(1/n)$ it takes $O(\mu\log\mu)=o(\tau^{\prime})$ generations
to consolidate the population on fitness level $j$, by Lemma 4. In Lemma 10 we
considered the time $T_{d}$ until the diversity on such a level drops below
$2\alpha$ for $\alpha:=\frac{2(\mu-1)\mu^{2}\chi
n}{n+4(\mu-1)\chi}=O(\mu^{3})$, and stated that
$\mathbb{E}[T_{d}]=O(\mu^{2}\log n)$. Now we split the time after
consolidation on level $j$ into intervals of lengths $2\mathbb{E}[T_{d}]$. In
each such interval, by Markov’s inequality the diversity drops below $2\alpha$
with probability at least $1/2$. The number of such intervals is at least
$\Omega(\tau^{\prime}/\mathbb{E}[T_{d}])=\Omega(\log n)$, where we can make
the hidden constant as big as we like due to the factor $C$ in
$\tau^{\prime}$. Hence, the probability that the diversity drops below
$2\alpha$ in at least one such phase is $1-o(1/n)$. The lemma now follows
because when the diversity of $P_{t}$ drops to $S(P_{t})\leq 2\alpha$ then
$d(P_{t})=\frac{S(P_{t})}{\mu(\mu-1)(n-i-1)}=O(\frac{\mu}{n-i+1})=o(1/\mu)$,
which implies that $P_{t}$ is a good population. Hence, level $j$ is good with
probability at least $1-o(1/n)$.∎

Applying Lemma 11 inductively immediately yields the following corollary,
which automatically satisfies the last hypothesis of Lemma 6:

###### Corollary 5

Consider the $(\mu+1)$ GA with $\mu=O(\sqrt{n}/\log^{2}n)$ starting in the
all-zero string. Then, with probability $1-o(1)$, $\forall 1\leq i\leq
n,\mathrm{ESucc}_{i}-i=O(\log n)$.

In what follows, we work conditionally on the event $J:"\forall 1\leq i\leq
n,\mathrm{ESucc}_{i}-i=O(\log n)"$. Note that since $J$ has high probability
by the previous corollary, we only need to prove the hypotheses of Lemma 6
conditional on $J$, by virtue of
$\mathbb{E}[T^{\mu}]\geq\mathbb{E}[T^{\mu}\mid J]\Pr(J)$.

Now, we can prove that the expected number of extra free-riders is negligible.

###### Lemma 12

Consider the $(\mu+1)$ GA with $\mu=O(\sqrt{n}/\log^{2}n)$ starting in the
all-zero string. Then for all $1\leq i\leq n-\omega(\mu^{2})$,
$\mathbb{E}[\mathrm{EF}_{i}\mid N_{i}]=o(1)$.

###### Proof

Consider any normal fitness level $1\leq i\leq n$. The structure of the proof
resembles the structure of the proof of Lemma 11, but this time we do not need
so small error probabilities because even in the worst case we only need to
consider the $O(\log n)$ levels between normal fitness levels. We define the
population $Q_{t}$ for $t\geq 0$, and $t^{*}$ as in the proof of Lemma 9. We
know that $\mathcal{G}({\frac{\chi}{n}})\preceq t^{*}$, and hence, if we let
$T=o(\frac{n}{\log n})$, we have $\Pr(t^{*}\leq T)=o(\frac{1}{\log n})$. Let
us call $E$ the event that $t^{*}>T$. Note that $\mu^{2}\log n\log\log
n=o(T)$, hence we may split $T$ into $\omega(\log\log n)$ phases of size
$\mu^{2}\log n$ intervals each. Conditioned on $E$, similarly to the proof of
Lemma 11 and Markov’s inequality, each interval has a constant probability of
reaching $d(P_{t})\leq\frac{2\alpha}{\mu^{2}n_{i}}=O(\frac{\mu}{n_{i}})$,
where $\alpha$ is given in Lemma 10. Hence, with probability
$1-o(\frac{1}{\log n})$, at some timestep $t_{0}$,
$d(P_{t_{0}})=O(\frac{\mu}{n_{i}})$. Let us call this event $F$. By Lemma 9,
we obtain:

$\mathbb{E}[d_{T^{o}_{i}}\mid E,F]=O(\frac{\mu}{n_{i}}).$

By the law of total expectation:

$\mathbb{E}[\mathrm{EF}_{i}]=\mathbb{E}[\mathrm{EF}_{i}\mid\bar{E}]\Pr(\bar{E})+\mathbb{E}[\mathrm{EF}_{i}\mid
E,\bar{F}]\Pr(E,\bar{F})+\mathbb{E}[\mathrm{EF}_{i}\mid E,F]\Pr(E,F)$

For the first term, note that since we conditioned on $J$,
$\mathbb{E}[\mathrm{EF}_{i}\mid\bar{E}]=O(\log n)$, and that
$P(\bar{E})=o(\frac{1}{\log n})$. Hence, this term is $o(1)$.

For the second term, again $\mathbb{E}[\mathrm{EF}_{i}\mid E,\bar{F}]=O(\log
n)$, and $\Pr(E,\bar{F})\leq\Pr(\bar{F}\mid E)=o(\frac{1}{\log n})$, so this
term is again $o(1)$.

As for the third term, notice that if the column $\mathrm{Succ}_{i}+1$ is a
stopping column, that is, a column where all individuals in the population
have a $0$-bit, then with high probability $\mathrm{Succ}_{i}+1$ is normal,
and in particular $\mathrm{EF}_{i}=0$.

Indeed, in that case, the probability of leaving fitness level $i$ before
consolidation is at most the probability that a mutation in column
$\mathrm{Succ}_{i}+1$ happens before consolidation, which we already derived
to be $O(\frac{\mu\log\mu}{n})$ in the proof of Lemma 7.

It remains to prove that, conditioned on $E\cap F$, $\mathrm{Succ}_{i}+1$ is a
stopping column with high probability. Denote by $x$ the individual that
reaches fitness $\mathrm{Succ}_{i}$ first. By definition,
$x_{\mathrm{Succ}_{i}+1}=0$. Hence, the probability that $\mathrm{Succ}_{i}+1$
is not a stopping column is the probability that at least one individual in
the population is different that $x$ on column $\mathrm{Succ}_{i}$ at time
$T^{\mathrm{in}}_{\mathrm{Succ}_{i}}$. At time $T^{o}_{i}$, the probability
that a given individual is different than $x$ on this column is
$d_{T^{o}_{i}}$ by Corollary 3. Hence, at time
$T^{\mathrm{in}}_{\mathrm{Succ}_{i}}$, it is at most
$d_{T^{o}_{i}}+O(\frac{1}{n})=O(\frac{\mu}{n_{i}})$, where the additive
$O(1/n)$ takes into account that $x$ might be generated by mutating the
$\mathrm{Succ}_{i}+1$-th bit. Hence, the expected number $N$ of individuals
different than $x$ on this column is

$\mathbb{E}[N]=(\mu-1)O(\frac{\mu}{n_{i}})=O(\frac{\mu^{2}}{n_{i}})=o(1).$

We conclude using the fact that $\Pr(N\geq 1)\leq\mathbb{E}[N]$.∎

###  3.2 Using a diversity improving tie-breaker speeds up the $(2+1)$ GA on
LeadingOnes by a constant factor.

In this section, we introduce a particular tie-breaker, and show that it
ensures a constant factor improvement for which we derive a lower bound.
Finally, we show that using an adaptative crossover probability leads to
further improvement.

Throughout the whole section, we will denote $P=\\{x_{1},x_{2}\\}$ with
$x_{2}\preceq x_{1}$. If there is an ambiguity on the value of $t$, we will
write $P_{t}=\\{x_{1}^{t},x_{2}^{t}\\}$. In this section, we introduce a tie-
breaking mechanism that enhances the efficiency of crossovers by keeping the
two individuals in the population genetically diverse. When two individuals
are in a tie, this tie-breaker chooses the one that has the highest $S$-value
among the rest of the population (that is, the one furthest away from the rest
of the population in Hamming distance). This has the effect of keeping a
population with a high $d_{t}$ value, and hopefully that crossover is more
likely to bring interesting novelties in the genotype of the offspring. Here
is a pseudocode for this tie-breaker:

Input : Q: a set of bit-strings of size $n$.

x, y: two bit strings of length $n$.

1

2if  _$S_{Q\backslash\\{x,y\\}}(x)\geq S_{Q\backslash\\{x,y\\}}(y)$_ then

3 return _x_

4else

5 return _y_

Algorithm 4 The diversity improving tie-breaker.

This tie-breaker is similar to that studied by [4] (Section 5.5), who proved
that it significantly enhances the optimization of the Jump functions.

###### Observation 3

This tie-breaker is unbiased because automorphisms of the hypercube preserve
the Hamming distance.

Now, we observe that this tie-breaker indeeds improves $d_{t}$ when the
offspring produced at $t$ is not better than one of the individuals.

###### Lemma 13

Consider a run of the $(\mu+1)$ GA for any population size $\mu$, using the
diversity improving tie-breaker. Suppose that the offspring $y$ produced at
time $t$ is not fitter than any of the individuals in $P_{t}$. Then,
$d_{t+1}\geq d_{t}$.

###### Proof

Since the new offspring $y$ does not reduce the size of the non-optimized part
of a fit bit-string in the population, we just have to show that
$S(P_{t+1})\geq S(P_{t})$. Suppose that the newly generated offspring is
introduced in the population $P_{t+1}$ (otherwise the result is trivial). This
means that $P_{t+1}=P_{t}\backslash\\{x\\}\cup\\{y\\}$ for some $x\in P_{t}$
such that

$S_{P_{t}\backslash\\{x\\}}(x)\leq S_{P_{t}\backslash\\{x\\}}(y)$

On the other hand,

$\displaystyle S(P_{t+1})$ $\displaystyle=\sum_{z\in P_{t},z\neq
x}H(y,z)+\sum_{z\in P_{t},z\neq x}S_{P_{t}\backslash\\{x\\}}(z)+H(z,y)$
$\displaystyle=2S_{P_{t}\backslash\\{x\\}}(y)+\sum_{z\in P_{t},z\neq
x}S_{P_{t}}(z)-H(z,x)$
$\displaystyle=2S_{P_{t}\backslash\\{x\\}}(y)-S_{P_{t}\backslash\\{x\\}}(x)+\sum_{z\in
P_{t},z\neq x}S_{P_{t}}(z)$
$\displaystyle=2(S_{P_{t}\backslash\\{x\\}}(y)-S_{P_{t}\backslash\\{x\\}}(x))+S(P_{t}).$

Applying the previous inequality gives the desired result.∎

We will now prove the following theorem:

###### Theorem 3.1

Consider the $(2+1)$ GA using standard bit-wise mutation, uniform crossover
with constant probability $p_{c}$, and the diversity-improving tie-breaker.
Then its runtime $T$ satisfies:

$\mathbb{E}[T]\leq\frac{2}{2+\frac{p_{c}(1-p_{c})}{12-8p_{c}}}\cdot\frac{e^{\chi}-1}{2\chi^{2}}n^{2}+o(n^{2})$

Note that the fraction is a constant strictly smaller than $1$, and the second
factor is up to a $(1+o(1))$ the runtime of a vanilla $(2+1)$ GA (with uniform
tie-breaking), or a ${(1+1)}$ EA. This means that the diversity-improving tie-
breaker brings a constant factor improvement compared to the vanilla $(2+1)$
GA and the ${(1+1)}$ EA. Note that there is room for improvement in the
precise constant, since empirically the speedup seems to be about twice as
large.

The first step to prove this theorem is to study the diversity evolution
process on a fitness plateau.

###### Lemma 14

Consider a run of the $(2+1)$ GA using the diversity-improving tie-breaker and
standard bit-wise mutation with any mutation rate $\chi$ and uniform
crossover. Let $0\leq i\leq n-1$. Then,

$\mathbb{E}[d_{T^{\mathrm{o}}_{i}}\mid
N_{i}]\geq\frac{1-p_{c}}{3-2p_{c}}+o(1)$

.

Let us first make the following observation.

###### Observation 4

Assume that the whole population has fitness at least $F_{t}$. Then every
crossover of two parents has also fitness at least $F_{t}$. Hence, regardless
of whether crossover happened or not, the probability that the offspring has
fitness at least $F_{t}$ is $(1-\chi/n)^{F_{t}}$. By Bayes’ theorem, this
conversely implies that the event that an offspring has fitness at least
$F_{t}$ does not change the probability that crossover has happened. In
formula, for all $t\geq 0$, if we denote by $y_{t}$ the offspring produced at
time $t$:

$\Pr(C_{t}\mid f(y_{t})\geq F_{t},t\geq T^{c}_{F_{t}})=p_{c}.$

We may now prove the lemma.

######  Proof (of Lemma 14)

Let $0\leq i\leq n-1$ be a normal fitness level. Define $T^{\mathrm{fit}}_{t}$
to be the time when the $t$-th offspring with fitness equal to $i$ or higher
is generated after consolidation. Define the bit-string
$b_{t}=\neg((x^{T^{\mathrm{fit}}_{t}}_{1})_{[i+2:]}\oplus(x^{T^{\mathrm{fit}}_{t}}_{2})_{[i+2:]})$,
so $b_{t}$ has a one-bit if $x^{T^{\mathrm{fit}}_{t}}_{1}$ and
$x^{T^{\mathrm{fit}}_{t}}_{2}$ coincide in their non-optimized part, and a
zero-bit otherwise. Define $t^{*}$ to be the last $t$ such that
$T^{\mathrm{fit}}_{t}\leq T^{\mathrm{o}}_{i}$. Note that
$\textsc{OM}_{t}=\textsc{OneMax}(b_{t})=(n-i-1)d_{T^{\mathrm{fit}}_{t}}$, so
$\textsc{OM}_{t^{*}}=n_{i}d_{T^{\mathrm{o}}_{i}}$, where $n_{i}=n-i-1$.

Now, note that when the offspring generated at $T^{\mathrm{fit}}_{t}$ is
generated without crossover (probability $1-p_{c}$ by the last observation),
the increase of $\textsc{OM}_{t}$ in one time step is always bigger than the
difference between the number of mutations that happened in the set
$0_{b_{t}}$ and in the set $1_{b_{t}}$, which have respectively an expectation
of $\frac{\chi}{n}(n_{i}-\textsc{OM}_{t})$, and
$\frac{\chi}{n}\textsc{OM}_{t}$. In every other case, the tie-breaker ensures
that $\textsc{OM}_{t}$ increases. This gives:

$\displaystyle\mathbb{E}[\textsc{OM}_{t+1}-\textsc{OM}_{t}\mid\textsc{OM}_{t}]\geq(1-p_{c})(n_{i}-2\textsc{OM}_{t})\frac{\chi}{n},$

or equivalently

$\displaystyle\mathbb{E}[\textsc{OM}_{t+1}\mid\textsc{OM}_{t}]\geq\textsc{OM}_{t}(1-2\frac{\chi}{n}(1-p_{c}))+n_{i}(1-p_{c})\frac{\chi}{n}.$

By the law of total expectation:

$\mathbb{E}[\textsc{OM}_{t+1}\mid\textsc{OM}_{0}]\geq\mathbb{E}[\textsc{OM}_{t}\mid\textsc{OM}_{0}](1-2\frac{\chi}{n}(1-p_{c}))+n_{i}(1-p_{c})\frac{\chi}{n}.$

Solving the arithmetic-geometric recursion yields:

$\mathbb{E}[\textsc{OM}_{t}\mid\textsc{OM}_{0}]\geq(\textsc{OM}_{0}-\frac{n_{i}}{2})(1-2\frac{\chi}{n}(1-p_{c}))^{t}+\frac{n_{i}}{2}.$

Since $\textsc{OM}_{0}\geq 0$, we get:

$\mathbb{E}[\textsc{OM}_{t^{*}}\mid
t^{*}]\geq\frac{n_{i}}{2}\left(1-\left(1-\frac{2\chi}{n}(1-p_{c})\right)^{t^{*}}\right).$

Moreover, $t^{*}\sim\mathcal{G}(\frac{\chi}{n})$. Indeed, every generated
offspring has probability $\frac{\chi}{n}$ to leave level $i$, regardless of
if crossover was used or not to generate it, since we always apply mutation
after crossover. Hence, by the law of total expectation:

$\displaystyle\mathbb{E}[\textsc{OM}_{t^{*}}]$
$\displaystyle\geq\sum_{t=1}^{\infty}\frac{\chi}{n}\left(1-\frac{\chi}{n}\right)^{t-1}\frac{n_{i}}{2}\left(1-\left(1-\frac{2\chi}{n}(1-p_{c})\right)^{t}\right)$
$\displaystyle\geq\frac{n_{i}}{2}\left[1-\left(1-\frac{2\chi}{n}(1-p_{c})\right)\frac{\chi}{n}\sum_{t=0}^{\infty}\left(\left(1-\frac{\chi}{n}\right)\left(1-\frac{2\chi}{n}(1-p_{c})\right)\right)^{t}\right]$
$\displaystyle\geq\frac{n_{i}}{2}\left[1-\left(1-\frac{2\chi}{n}(1-p_{c})\right)\frac{\frac{\chi}{n}}{1-(1-\frac{\chi}{n})(1-\frac{2\chi}{n}(1-p_{c})))}\right]$
$\displaystyle\geq\frac{n_{i}}{2}\left[1-\frac{1}{3-2p_{c}}+o(1)\right]$
$\displaystyle\geq n_{i}\frac{1-p_{c}}{3-2p_{c}}+o(n_{i}).$

Dividing by $n_{i}$ yields:

$\displaystyle\mathbb{E}[d_{T^{\mathrm{o}}_{i}}]\geq\frac{1-p_{c}}{3-2p_{c}}+o(1).$
∎

Now, we argue that having this constant lower bound for the diversity when
leaving $i$ guarantees a constant lower bound for the expectation of
$\mathrm{EF}_{i}$.

###### Lemma 15

For $0\leq i\leq n$,

$\Pr[\mathrm{EF}_{i}\geq 1\mid
N_{i},d_{T^{\mathrm{o}}_{i}}]\geq\frac{p_{c}}{8}d_{T^{\mathrm{o}}_{i}},$

###### Proof

Let $i$ be a normal fitness level. Suppose $F_{i}=0$, that is
$\mathrm{Succ}_{i}=i+1$, which happens with probability $\frac{1}{2}$ by
Corollary 2. The probability that $x_{1}$ and $x_{2}$ are different at $i+2$
is $d_{T^{\mathrm{o}}_{i}}$ at time $T^{\mathrm{o}}_{i}$. At
$T^{\mathrm{in}}_{i+1}$, it is still $d_{T^{\mathrm{o}}_{i}}$. Suppose it is
the case. We want to lower bound the probability that an offspring of fitness
$i+1$ is generated by crossover before a copy of $x_{1}$ is generated, from
the moment when $x_{1}$ reaches $i+1$. Let us call this event $A$. When an
offspring with fitness larger than $i$ is generated, the probability that it
was generated by crossover is $p_{c}$. Conditioned on this, the probability
that the offspring has fitness higher than $i+1$ is the probability that bit
$i+1$ is set correctly, which is $\frac{1}{2}$. Hence, $\Pr(A)\geq p_{C}/2$.
Conditioned on $A$, the probability that the crossover that realized $A$ also
gets the extra free-rider is $\frac{1}{2}$. Hence,

$\displaystyle\Pr[\mathrm{EF}_{i}\geq 1\mid N_{i},d_{T^{\mathrm{o}}_{i}}]$
$\displaystyle\geq\Pr(x^{T^{\mathrm{in}}_{\mathrm{Succ}_{i}}}_{1_{\mathrm{Succ}_{i}+1}}\neq
x^{T^{\mathrm{in}}_{\mathrm{Succ}_{i}}}_{2_{\mathrm{Succ}_{i}+1}})\Pr(\mathrm{Succ}_{i}=i+1)\Pr(A)\frac{1}{2}$
$\displaystyle\geq\frac{p_{c}}{8}d_{T^{\mathrm{o}}_{i}}.$ ∎

We conclude the proof of Theorem 3.1 by using the law of total expectation
which gives $\mathbb{E}[\mathrm{EF}_{i}\mid
N_{i}]\geq\frac{p_{c}(1-p_{c})}{12-8p_{c}}$, together with Lemma 5, which can
be applied for $m_{n}=\frac{p_{c}(1-p_{c})}{12-8p_{c}}$. ∎

This bound is optimized for $p_{c}\approx 0.6$, which is experimentally the
optimal static crossover value. However, our proof naturally suggests an
adaptive mechanism for the crossover probability, which is to set $p_{c}=1$
when the population is not consolidated, and $p_{c}=0$ otherwise. Indeed, in
Lemma 14, we see that the lower bound for the diversity decreases with
$p_{c}$. This is intuitive, as crossover hinders the accumulation of diversity
when in the consolidated phase: if a crossover is made between two individuals
with Hamming distance $d$, the resulting offspring is at distance lower than
$d$ from both its parents with overwhelming probability, and thus will not be
accepted. Conversely, the lower bound for the probability to get an extra
free-rider conditional on $d_{T^{o}_{i}}$ in the non-consolidated phase is
increasing in $p_{c}$. Even if this bound is not tight, this is again
intuitive, as the more crossover one does, the more trials one gets to obtain
an extra free-rider.

##  4 Conclusion

In this work, we examined the connection between population diversity and
progress on the LeadingOnes problem by the $(\mu+1)$ GA. We have shown that
the naturally evolving diversity for any $\mu=o(\sqrt{n}/\log n)$ is not
enough to improve the runtime by more than a $(1+o(1))$ factor. On the other
hand, even for $\mu=2$ simple tie-breaking in favor of diversity leads to so
much diversity in the population that the runtime decreases by a constant
factor.

There are many question that we had to leave open. The most interesting is
what happens for $\mu=\Omega(\sqrt{n})\cap o(n/\log n)$. We conjecture that
the vanilla version can not create enough diversity to give a constant factor
speed-up, even though the average Hamming distance between parents increases
further. We conjecture further that the problem is not that differences in
bits are never created, but instead the problem is that they also get lost
again. So, if there was a way of preventing these differences to get lost, we
may even hope for algorithms which get extra free riders on _most_ fitness
levels, which could lead to asymptotically optimization time $o(n^{2})$. We
believe that this is a very interesting setting to explore more systematically
potential diversity-preserving mechanisms.

Disclosure of Interests. The author do not have conflicting interests.

## References

  * [1] Böttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Parallel Problem Solving from Nature, PPSN 2010. pp. 1–10. Springer (2010)
  * [2] Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Transactions on Evolutionary Computation 22, 720–732 (2018)
  * [3] Dang, D.C., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation 22(3), 484–497 (2017)
  * [4] Dang, D., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation 22, 484–497 (2018)
  * [5] Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567, 87–104 (2015)
  * [6] Doerr, B., Echarghaoui, A., Jamal, M., Krejca, M.S.: Lasting diversity and superior runtime guarantees for the $(\mu+1)$ genetic algorithm. CoRR abs/2302.12570 (2023)
  * [7] Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425, 17–33 (2012)
  * [8] Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673–697 (2012)
  * [9] Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017. pp. 777–784. ACM (2017)
  * [10] Doerr, B., Neumann, F. (eds.): 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
  * [11] Doerr, C.: Complexity theory for discrete black-box optimization heuristics. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization pp. 133–212 (2020)
  * [12] Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276, 51–81 (2002)
  * [13] Friedrich, T., Kötzing, T., Radhakrishnan, A., Schiller, L., Schirneck, M., Tennigkeit, G., Wietheger, S.: Crossover for cardinality constrained optimization. In: Genetic and Evolutionary Computation Conference, GECCO 2022\. pp. 1399–1407. ACM (2022)
  * [14] Jansen, T., Wegener, I.: On the analysis of evolutionary algorithms – a proof that crossover really can help. In: European Symposium on Algorithms, ESA 1999\. pp. 184–193. Springer (1999)
  * [15] Jansen, T., Wegener, I.: Real royal road functions—where crossover provably is essential. Discrete applied mathematics 149(1-3), 111–125 (2005)
  * [16] Jorritsma, J., Lengler, J., Sudholt, D.: Comma selection outperforms plus selection on onemax with randomly planted optima. In: Genetic and Evolutionary Computation Conference (GECCO) (2023)
  * [17] Kötzing, T., Sudholt, D., Theile, M.: How crossover helps in pseudo-Boolean optimization. In: Proc. of GECCO’11. pp. 989–996. ACM (2011)
  * [18] Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623–642 (2012)
  * [19] Lehre, P.K., Yao, X.: Crossover can be constructive when computing unique input-output sequences. Soft Computing 15, 1675–1687 (2011)
  * [20] Lengler, J.: Drift analysis. In: Theory of Evolutionary Computation, pp. 89–131. Springer (2020)
  * [21] Lengler, J., Opris, A., Sudholt, D.: Analysing equilibrium states for population diversity. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 1628–1636 (2023)
  * [22] Lengler, J., Opris, A., Sudholt, D.: A Tight $O(4^{k}/p_{c})$ Runtime Bound for a $(\mu+1)$ GA on Jumpk for Realistic Crossover Probabilities. In: Proceedings of the Genetic and Evolutionary Computation Conference. p. to appear (2024)
  * [23] Neumann, F., Oliveto, P.S., Rudolph, G., Sudholt, D.: On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation. pp. 1587–1594 (2011)
  * [24] Oliveto, P.S., He, J., Yao, X.: Analysis of population-based evolutionary algorithms for the vertex cover problem. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). pp. 1563–1570 (2008). https://doi.org/10.1109/CEC.2008.4631000
  * [25] Oliveto, P.S., Sudholt, D., Witt, C.: Tight bounds on the expected runtime of a standard steady state genetic algorithm. Algorithmica pp. 1–56 (2022)
  * [26] Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovǎc (1997)
  * [27] Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17(3), 418–435 (2012)
  * [28] Sudholt, D.: How crossover speeds up building block assembly in genetic algorithms. Evolutionary Computation 25, 237–274 (2017)
  * [29] Sudholt, D.: The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. Theory of evolutionary computation: Recent developments in discrete optimization pp. 359–404 (2020)
  * [30] Whitley, D.: Next generation genetic algorithms: a user’s guide and tutorial. Handbook of metaheuristics pp. 245–274 (2019)
  * [31] Witt, C.: Runtime analysis of the ($\mu$ \+ 1) EA on simple pseudo-Boolean functions. Evolutionary Computation 14, 65–86 (2006)
  * [32] Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing 22(2), 294–318 (2013)