On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best

1]Dogan<EMAIL_ADDRESS>1]Andrei<EMAIL_ADDRESS>1]Pietro S<EMAIL_ADDRESS>2]Carsten<EMAIL_ADDRESS>
[1]The University of Sheffield
[2]Technical University of Denmark

We analyse the impact of the selective pressure for the global optimisation capabilities of steady-state EAs. For the standard bimodal benchmark function we rigorously prove that using uniform parent selection leads to exponential runtimes with high probability to locate both optima for the standard ($\mu$+1) EA and ($\mu$+1) RLS with any polynomial population sizes.

On the other hand, we prove that selecting the worst individual as parent leads to efficient global optimisation with overwhelming probability for reasonable population sizes. Since always selecting the worst individual may have detrimental effects for escaping from local optima, we consider the performance of stochastic parent selection operators with low selective pressure for a function class called  TruncatedTwoMax where one slope is shorter than the other. An experimental analysis shows that the EAs equipped with inverse tournament selection, where the loser is selected for reproduction and small tournament sizes, globally optimise efficiently and effectively escape from local optima of  TruncatedTwoMax with high probability. Thus they identify both optima efficiently while uniform (or stronger) selection fails in theory and in practice. We then show the power of inverse selection on function classes from the literature where populations are essential by providing rigorous proofs or experimental evidence that it outperforms uniform selection equipped with or without a restart strategy. We conclude the paper by confirming our theoretical insights with an empirical analysis of the different selective pressures on standard benchmarks of the classical MaxSat and Multidimensional Knapsack Problems.

§ INTRODUCTION

In natural evolution, the better individuals adapt to the environment,
the more likely it is that they are selected for reproduction – that they generate offspring [13].
canonical generational genetic algorithms (GAs) rely on this concept to efficiently evolve populations of candidate solutions [20, 22].
Generational evolutionary algorithms (EAs) model natural evolution by using the current population to create a completely new population of the same size in each generation (i.e., all individuals die by the end of their generation). The more individuals of the current population are fit  (i.e., have high objective function value), the more likely they are to generate offspring for the next generation. These offspring will be part of the next population independently of their fitness but the probability they will reproduce, in turn, depends on how fit they are compared to the rest of the population.
All the commonly used selection operators in generational EAs and GAs (such as e.g., fitness proportional, tournament, ranking and comma selection) rely on this described property of natural evolution to increase the average fitness of the population over time.
Roughly speaking, the probability that fit individuals are selected for reproduction and produce a surviving offspring in generational EAs and GAs is commonly referred to as selective pressure. The higher the selective pressure, the faster diversity is lost due to the best individuals taking over the population (i.e., takeover time).
On the other hand, it is well understood that sufficiently high selective pressure is required for the population of a generational EA to evolve effectively [7]. In particular, if the selective pressure is not high enough, then generational EAs will require exponential time to optimise any function with unique optimum [28].

More recently introduced evolutionary algorithms, typically referred to as steady-state GAs [39, 37] (or steady-state EAs according to whether they use crossover or not [41]), rely on elitist selection (often referred to also as cut, truncation or plus selection)  between consecutive generations.
Differently to canonical ones, steady-state algorithms (EAs or GAs) evolve overlapping populations. They create an offspring population of smaller size (i.e. $\lambda$) compared to the parent population (of size $\mu>\lambda$) and the worst individuals from the union of both populations (i.e. of total size $\mu$+$\lambda$) are removed to obtain a new population of the same size as that of the parent population for the next generation.
This considerable change in the evolutionary process means that the best genotypes do not disappear from the population in the next generation
even if they do not reproduce. Such a difference implies that, if elitism is used, it is not crucial that better individuals have higher probabilities of reproducing for a population to evolve effectively.
In particular, from the point of view of the  survival of the fittest [14, 34], elitism makes the choice of how parents are selected for reproduction irrelevant (i.e.,  the probability that the best $\mu-\lambda$ individuals will be in the next generation is 1).
From this point of view, the choice of the parent selection mechanism becomes arbitrary.
While when steady-state evolutionary algorithms were originally introduced in the genetic algorithm community individuals were ranked and selected with a bias towards the top [39, 37], indeed nowadays
parents are commonly selected uniformly at random for reproduction in steady-state EAs and GAs[This is probably due to the fact that the German evolution strategies  community, where continuous optimisation though was the main focus, used uniform parent selection in ($\mu+\lambda$) ESs [2].
While for the mentioned reasons this clearly makes sense, very successful steady-state GAs may still apply some parent selective pressure such as the binary tournament selection used in Chu and Beasley's GA.  [6].] [41, 19, 12, 8, 36, 29].

From a different perspective, the parent selection operator may considerably impact the overall performance of the algorithm (i.e., the expected time for the global optimum to be found).
In particular, we argue that the selective pressure commonly used in steady-state EAs is too high
because, the higher the probability of selecting better individuals, the quicker the population is taken over by the best one, hence the faster premature convergence [20, 35] occurs.

Such a problem was already argued shortly after the introduction of steady-state GAs to the community [21].
However, the only solutions considered to avoid premature convergence with overlapping populations were either to increase the population
size or to use multiple populations (niching).

In this paper we analyse the impact of parent selection on the performance of steady-state EAs for global optimisation.
To this end, we consider the performance of the well studied ($\mu$+1) EA for the standard bimodal benchmark  function . The function has been used in the theory of  evolutionary computation to evaluate the exploration capabilities of EAs in discrete search spaces because, since the optima are located very far away from each other, it is very challenging to evolve a population that contains both of them [19, 35, 30, 31].

In particular, has often been used to evaluate the performance of diversity enhancing mechanisms for the ($\mu$+1) EA because, without such mechanisms, the algorithm has been proven to be unable to identify both optima of the function in polynomial time with high probability if the population size is at most sublinear (i.e. $\mu=o(n/\log n)$) [19].

However, no proof is available that the algorithm would not be efficient using larger population sizes. Our first result is the proof that it is not. In particular, we show that the ($\mu$+1) EA and the ($\mu$+1) RLS with standard uniform parent selection cannot identify both optima of in polynomial time with 1 - $o(1)$ probability for any population of polynomial size.

The previous analysis from the literature assumed pessimistically that the population has nearly optimised both branches when the takeover occurs.
Our analysis reveals that the takeover occurs much earlier: not long after initialisation. Hence, the negative effects of premature convergence are emphasised: while displays local and global optima at opposite extremities of the search space, since the takeover occurs very early it may negatively affect the algorithm on much larger classes of multimodal functions.

On the other hand, we also prove that it is not necessary to use diversity enforcing mechanisms for the two algorithms to identify both optima of : decreasing the selective pressure suffices!
As a proof of concept we decrease it to a minimum by always selecting the worst individual of the population as parent (breaking ties uniformly at random).
We prove that such a decrease leads the algorithms to the efficient global optimisation of for reasonable population sizes
i.e., the expected runtime is $O(\mu n \log n)$ with
$\mu=\Omega(n^{1+\epsilon})$ for the ($\mu$+1) RLS and
$\mu=\Omega(n^{1+2\epsilon})$ for the ($\mu$+1) EA.

However, while we are arguing for low selective pressures, in general we do not recommend selecting the worst individual for reproduction as it may have serious detrimental effects for the global optimisation capabilities of steady-state EAs.
For example, if the worst individual of the population is stuck on a local optimum, then it will be selected for reproduction until it manages to escape.
For some local optima this may be prohibitive, and even require super-polynomial time. To tackle this problem  we

consider the usage of stochastic parent selection operators that do not deterministically select the worst individual of the population.
To this end, we consider tournament selection with (small) tournament sizes where the loser of the tournament is chosen for reproduction[We use inverse tournament for simplicity of implementation. The same results can be achieved with Inverse Rank Selection.].
Thus, we increase the selective pressure while still keeping it lower than that of uniform selection.

To evaluate the performance of the algorithm at escaping from local optima, we modify such that one slope is shorter than the other and call the resulting function class TruncatedTwoMax$_k$ where the parameter $k$ defines the height of the local optima.

A corollary of our first result shows that the with standard uniform selection will only identify one of the peaks with high probability and this will be the lower one with probability at least $1/2 - o(1)$.

An experimental analysis confirms that Inverse Elitist selection is very effective for the global optimisation of and that for TruncatedTwoMax with a probability of approximately 1/2 it gets stuck on the lower branch unless an unlikely takeover happens before. On the other hand, the experiments reveal that Inverse Tournament Selection is able to escape from the local optima, hence is efficient for both and TruncatedTwoMax with approximately linear population sizes.

Although the benchmark function is commonly used to evaluate the exploration capabilities of population based EAs, a single trajectory algorithm with a restart strategy suffices to optimise the function very efficiently.
Hence, we also evaluate the performance of the Inverse Elitist and Inverse Tournament Selection on benchmark functions that have previously been used in the literature to highlight problem characteristics where populations are essential.
In particular, problem classes where single trajectory EAs fail with overwhelming probability (w.o.p.),
hence restart strategies are also ineffective.
To this end, we pick the multimodal  function SufsAmp (which we generalise and prefer to call )
previously used in the literature to highlight fitness landscape characteristics where the use of offspring populations is essential
[25]
and a bimodal function class, that we call , which has been used in the literature to
highlight circumstances where parent populations are essential [41].
For both functions a single trajectory gets stuck on a local optimum w.o.p. and restarts will not help to reduce the runtime to polynomial in the problem size.
On the other hand, the respective population based EAs (i.e., (1+$\lambda$) EA for and the
for  ) can efficiently identify the global optimum by avoiding the local optima.
However, if the fitness values of the local and global optima are swapped appropriately, then the opposite effects can be shown: the single trajectory algorithms are effective while the population-based algorithms get stuck w.o.p.
Our contributions are the following. Concerning , we rigorously prove that the with Inverse Tournament Selection efficiently identifies all of the many optima of the function, hence also the global one independent of which optimum is set to have the maximal value.
Concerning  we rigorously prove that the with inverse binary tournaments can find
the global optimum efficiently just like the with uniform selection.
Additionally, we show experimentally that, while the w.o.p. gets trapped in one optimum and the uniform selection on the other,
the  Inverse Tournament Selection algorithms identify both optima with reasonable probability, hence can optimise the function efficiently independent of which local optimum is defined to be the optimal one.

We conclude the paper by comparing experimentally the inverse selection operators against standard uniform selection for well studied benchmark instances of two NP-Hard problems, MaxSat and the Multidimensional knapsack problem (MKP).
While for the MaxSat instances, independent runs of single trajectory algorithms outperform the population based EAs, such a strategy is detrimental for MKP[For MaxSat we implemented a with deterministic crowding where offspring only compete with their parent. The difference in performance with $\mu$ parallel (1+1) EAs should be minimal and not noticeable.].
On the other hand, for both problems the inverse selection algorithms outperform uniform selection with statistical significance i.e., better solutions are found with higher probability.

The rest of the paper is structured as follows.
In the next section we introduce the and together with the different selection operators and the other algorithms that we will consider in the paper. We also present the and function classes and some tools for the analyses.
In Section <ref> we prove that standard uniform selection or higher selective pressure does not allow the efficient global optimisation of independent of the population size.
In Section <ref> we prove that the algorithm becomes efficient if the worst individual is selected for reproduction.
In Section <ref> we present an experimental analysis providing evidence that inverse tournament selection with small tournament sizes is preferable to the previously considered selection operators for the optimisation of and .
In Section <ref> we show the superiority of the inverse selection operators over uniform selection for problems where populations are essential and where restart strategies of single trajectory algorithms fail w.o.p.
In Section <ref> we confirm our theoretical intuitions with an experimental analysis of the considered algorithms for the two NP-Hard problems.
We finish with a discussion and some conclusions.

§ PRELIMINARIES

We will consider the well-studied described in Algorithm <ref>. The algorithm starts by selecting $\mu$ individuals chosen uniformly at random. Then at each iteration an individual is selected from the population (parent selection) and an offspring is generated by mutating each bit of the selected individual with probability $p$
(in this paper we will use the standard mutation rate $p=1/n$). Then, the worst individual is removed from the population breaking ties randomly.
We will also consider its random local search variant called that flips exactly one bit per
mutation (instead of using the mutation rate p).

Sample $\mu$ search points from $\{0,1\}^n$ independently and uniformly at random and put them into the multiset $P$.

$t \gets 1, 2, \dots$
Pick $x\in P$ according to the parent selection operator.
Create $y$ by flipping each bit of $x$ independently with probability $1/n$.
Remove $\arg\min\{f(z)\,\mid\,z\in P\cup\{y\}\}$  from $P$, breaking ties randomly.

Our aim is to analyse how the parent selection operator affects the global optimisation performance of the algorithm.
Different definitions have been provided in the literature to refer to the global optimisation of multimodal optimisation problems.
Some researchers use the term to refer to the goal of identifying one single global optimum, while others refer to the identification of multiple optimal solutions and even to a collection of global and local optima. We refer to [32] for an overview of the available definitions in the literature.
While the insights provided in this paper apply to any of these definitions, in this paper we refer to global optimisation as the task of identifying one global optimum.
In particular, all the benchmark problems considered in this paper have only one global optimum (for either optimum may be designated to be the global one but, in order for an algorithm to identify it with high probability, it is necessary to visit both).
We will consider the following operators enumerated from highest to lowest selective pressure:

* $K$-Tournament selection: Select $K$ individuals uniformly at random from the population and choose the winner (i.e., best) of the tournament as parent;

* Uniform Selection: choose the parent uniformly at random from the population;

* Inverse $K$-Tournament selection: Select $K$ individuals uniformly at random and choose the loser (i.e., worst) of the tournament as parent;

* Inverse Elitist Selection: choose the parent with worst fitness from the population breaking ties uniformly at random.

with deterministic crowding

Sample $\mu$ search points from $\{0,1\}^n$ independently and uniformly at random and put them into the multiset $P$.

$t \gets 1, 2, \dots$
Pick $x\in P$ uniformly at random.
Create $y$ by flipping each bit of $x$ independently with probability $1/n$.
If $f(y) \geq f(x)$  then remove  $x$ from $P\cup\{y\}$, else keep $P$.

Apart from comparing different selective pressures for the , we will also consider the use of diversity mechanisms from the literature for which good global exploration capabilities have been proven.
In particular, if the use of problem specific knowledge is not allowed, then deterministic crowding is the best diversity mechanism that has been analysed for the benchmark problem we consider in the first part of this paper.
The using deterministic crowding is described in Algorithm <ref>. It optimises  in $O(\mu n \log n)$ fitness evaluations with probability at least $1-2^{-\mu}$. The difference with the standard is that offspring only compete with their parent rather than with the whole population.
The algorithm closely resembles $\mu$ parallel (1+1) EAs since the individuals explore the landscape independently.
Indeed a (1+1) EA with a simple restart strategy optimises with the same probability if $\mu$ is the number of performed restarts or parallel runs.
The (1+1) EA is obtained from Algorithm <ref> by setting $\mu=1$ and preferring the offspring to the parent when breaking ties.
Other theoretically studied diversity mechanisms are either ineffective (genotype diversity), detrimental (fitness diversity) or require problem knowledge to be made efficient (fitness sharing and clearing[Fitness sharing has only been proven to be efficient for if the knowledge that it is a unitation function is  exploited by the sharing function [19, 30]. Without problem knowledge, hence using the Hamming distance for the sharing function, it has been experimentally shown that fitness sharing does not make the efficient for  [30]. Similar argumentations also hold for Clearing which requires large population sizes and an appropriate niching radius to optimise the function efficiently [31].]) for  [19, 35, 30, 31] hence we do not consider them in this paper.

We are interested in the optimisation (here: maximisation) of the function,
which is defined as $\twomax:\{0,1\}^n\to\R, x\mapsto \left\lvert n/2-\ones{x}\right\rvert$. This function
has two global optima,
the all-ones and the all-zeros string. Leading to each optimum, there is
a so-called branch of perfect fitness-distance correlation:

if $\ones{x}>n/2$ then the fitness
is $n/2$ minus the Hamming distance to the all-ones string and we say that $x$ is on the right-hand branch; analogously
for $\ones{x}<n/2$, the Hamming distance to the all-zeros string is considered and we say that $x$ is on the so-called left-hand branch. A search point with $n/2$ ones, having
fitness $0$ is said to be in the valley. The goal of our analyses is to evaluate whether the EAs can identify both optima of in expected polynomial time (i.e., the number of fitness function evaluations is polynomial with respect to the problem size $n$).
The function is depicted in Figure <ref>.

(orange) and (thick blue) functions.

We also consider the following generalisation
of :

\begin{equation*}
\truncatedtwomax(x)
= \left\{
\begin{array}{rl}
\twomax(x) & \text{if } |x|_1 \geq n/2 -k, \\
0 & \text{otherwise.}
\end{array} \right.
\end{equation*}

The parameter $k$ defines the height of the left branch, from 0 (i.e., no left branch) to $n/2$ (i.e., ).
The lower the parameter value, the easier is the optimisation of the function because
the likelihood that individuals on the local optima take over the population decreases.
The function is depicted in Figure <ref>.

In our analyses we will need the following useful estimates for the probability function
as well as the density of the binomial distribution with parameters $n$ and $p$.

Let $X\sim\Bin(n,p)$, $q=1-p$ and suppose $np\ge 1$. For all $h \ge 3/(nq)$ it holds that

\[
\prob{X = np + h} \le \frac{1}{\sqrt{2\pi p q n}} e^{-\frac{h^2}{2pqn} + \frac{h}{qn} + \frac{h^3}{p^2n^2}}
\]

Also, for all $h\ge 0$ where $np+h$ is an integer less than $n$, it holds that

\[
\prob{X = np + h} \ge \frac{1}{\sqrt{2\pi p q n}} \
e^{-\frac{h^2}{2pqn} - \frac{h^3}{2q^2n^2} - \frac{h^4}{3p^3n^3} -\frac{h}{2pn} - \frac{1}{12(np+h)}
- \frac{1}{12(nq-h)}}
\]

Finally, if $pqn=\omega(1)$, $h>0$, $h=\omega(\sqrt{pqn})$, $h=o((pqn)^{2/3})$ as well as $np+h\le n$ then

\[
\prob{X\ge np + h} = (1\pm o(1)) \frac{\sqrt{pqn}}{h\sqrt{2\pi}} e^{-\frac{h^2}{2pqn}}
\]

As a corollary from the previous lemma, we obtain  the following
asymptotically tight estimate for the case of the symmetrical binomial distribution, ,

Let $X\sim\Bin(n,1/2)$. Then for all $h=o(n^{2/3})$ such that $n/2+h\in \{n/2,\dots,n\}$ it holds that

\[
\prob{X = n/2 + h} = (1\pm o(1)) \frac{\sqrt{2}}{\sqrt{\pi n}} e^{-\frac{2h^2}{n}}
\]

as well as

\[
\prob{X\ge n/2 + h} = (1\pm o(1)) \frac{\sqrt{n}}{h\sqrt{8\pi}} e^{-\frac{2h^2}{n}}
\]

In particular, the corollary will be used to analyse the maximum order statistic with respect to the number
of one-bits in a uniform
population of $\mu$ individuals. Related results can be found in [16]; however,
we find the bounds based on [4] presented above more convenient to use.

The following two theorems,  an additive variant of the
classical Chernoff-Hoeffding inequality and the artificial fitness levels theorem with tail
probabilities, will be used in Section <ref> for the analysis of the .

Let $X_1,\ldots,X_n$ be independent random variables taking values in $[0,1]$.
Let $X=\sum_{i=1}^{n}X_i$. Then for all $\lambda\geq 0$,
$\prob{X\geq E[X] + \lambda}\leq \exp(-\frac{2\lambda^2}{n})$ and $\prob{X\leq
E[X] - \lambda}\leq \exp(-\frac{2\lambda^2}{n})$.

Finally, we  make use of the following artificial fitness levels theorem with tail probabilities.

Consider an algorithm $\mathcal{A}$ maximising some
function $f$ and a partition of the search space into non-empty sets $A_1,\dots,A_m$. Assume
that the sets form an $f$-based partition, ,
for $1\le i<j\le m$  and all $x\in A_i$, $y\in A_j$ it holds $f(x)<f(y)$.
We say that $\mathcal{A}$  is in $A_i$ or on level $i$ if the best search point created so far
is in $A_i$.

If $p_i$ is a lower bound
on the probability that a step of $\mathcal{A}$ leads from level $i$ to some higher level,
of previous steps, then for any $\delta>0$,
the first hitting time of $A_m$, starting from level $k$, is at most

\[
\sum_{i=k}^{m-1} \frac{1}{p_i} + \delta
\]

with probability at least $1-e^{-\frac{\delta}{4}\cdot \min\{\frac{\delta}{s}, h\}}$, for any
$s\ge \sum_{i=k}^{m-1} \frac{1}{p_i^2}$
and $h = \min\{p_i \mid i=k,\dots,m-1\}$.

For the remainder of the paper we will use
with overwhelming probability (w.o.p.) to mean with probability $1-2^{-n^{\Omega(1)}}$.

§ TOO HIGH SELECTIVE PRESSURE FAILS

It is known from previous work that the standard (using uniform parent selection) with high probability
fails to find both optima of if $\mu=o(n/\log n)$ [19].
More precisely, with probability $1- o(1)$
there will be within any polynomial amount of time no step where the current population contains
both optima. The ideas behind the analysis in [19] can briefly be summarized as follows:

* With overwhelming probability the initial population contains none of the two optima.

* As every generation creates exactly one new individual, there is a first point in time where
exactly one of the optima, say the all-ones string, is created and added to the population.

* The take-over time for the all-ones string is $O(\mu\log \mu)=o(n)$ if the all-zeroes string is not found
in between. With probability $1-o(1)$ the take-over time is still $o(n)$.

* Pessimistically assuming all individuals from the branch leading to the all-zeros string to have only
a single-one bit, the probability of creating the all-zeros string by mutation is still at most $1/n$.
With high probability this step does not happen during the take-over time.

* Hence, with high probability after $o(n)$ steps the whole population consists of copies
of one optimum only, and in no step before has
the other optimum been in the population. The probability of creating
the opposite optimum by mutation is $1/n^n$, which w.o.p.
does not happen within
any polynomial number of steps.

Our analysis will considerably improve the result from [19]. First of all, we show
that even with arbitrarily large polynomial population sizes $\mu$ the algorithm will fail to find both optima. Second,
we show that the whole population will be on one branch of in very early stages of the optimisation, ,
soon after initialisation. Hence, diversity is lost much earlier than in the final improving steps
that are pessimistically considered in [19].

In a nutshell, the proof idea for the following theorem is to consider the uniform initialization
procedure of the and to analyse the probability of so-called outliers. More formally, an outlier is an individual $x^*$
from the initial population that has
the largest distance $\card{\ones{x^*}-n/2}$ from the points in the valley $n/2$ and also has
a significantly larger distance to the valley than all other individuals. Again, an argument
about the take-over time then shows that with high probability the whole population will be descendants of the outlier after
$O(\mu\log \mu n^{\epsilon})$ steps. Here we use the family tree technique by Witt [41] to show
that offspring of other individuals would have to
make an exceptionally large progress within the take-over time to catch up to the level of the best. After the
population has been taken over by descendants of the outlier,
steps that
mutate individuals to accepted individuals from the opposite branch are superpolynomially unlikely
due to the large distance of the outlier's fitness to the valley.

Let $\mu\le n^{k}$ for an arbitrary constant $k\ge 0$ as well
as $\mu=\omega(1)$ and consider the on .
Let $\epsilon>0$ be an arbitrary constant.
Then with probability $1-o(1)$, all individuals are on one branch
before the $\twomax$-value reaches $n/2+c\sqrt{n}(\log n+\log \mu)$, for
some sufficiently large constant $c>0$, and
the worst $\twomax$-value  in the population
is $n/2+\Omega(n^{1/2-\epsilon})$
at the time one branch dies out. This implies time $2^{\Omega(n^{1/2-\epsilon})}$
with probability at least $1-2^{-\Omega(n^{1/2-\epsilon})}$ to create
an individual from that branch again.

To prove Theorem <ref>, we will essentially look into random variables $X_i$,
where $1\le i\le \mu$,
following the Binomial distribution with parameters $n$ and $1/2$. These variables describe the number
of one-bits in the $\mu$ uniformly initialized individuals. Since we are only interested in the distance of this
number to the valley $n/2$, we introduce
$D_i\coloneqq \abs{ \onenorm{x_i} - n/2}$ for $i\in\{1,\dots,\mu\}$ and relate these
to $X_i$.
The probability distribution
of $D_i$ equals the one of $X_i-n/2$, conditioned on $X_i\ge n/2$. Also, $1/2 \le  \Prob(X_i\ge n/2)\le 1/2+O(1/\sqrt{n})$,
so for $a\ge 0$

\[(2-o(1)) \prob{X_i\ge n/2+ a} \le   \prob{D_i \ge a} \le (2+o(1))\prob{X_i\ge n/2 +a}.\]

In the following, we will analyse the probability of an outlier, , an individual
that has a $D$-value significantly larger than the standard deviation
$\sigma=\sqrt{n/4}$  of the binomial distribution $\Bin(n,1/2)$.
$D_{(1)}\ge \dots \ge D_{(\mu)}$ be  the order statistics of the $D_i$ (for convenience, index $(1)$
denotes the largest order statistic here, in contrast to the customary use in the literature). We shall
also use the random variables $(i)$, where $i\in\{1,\dots,\mu\}$, to denote the index of the $i$th order statistic.

We recall the assumptions  $\mu\le n^k$ for some constant $k\in\N$ and $\mu=\omega(1)$
from the main theorem, where the latter is mostly for convenience of proof. Our first result
shows a lower bound on $D_{(1)}$, the largest order statistic, that holds with high probability.

There is a $\ell^*=\sqrt{n \bigl((1/2-1/(8k))\ln \mu-\Theta(\log\log \mu)\bigr)}$ such that

$\prob{D_{(1)}\ge \ell^*} = 1-o(1).$

Let $\ell^*$ be the solution for $h$
of the equality

\[
\frac{\sqrt{n}}{h\sqrt{8\pi}}e^{-2h^2/n} = \frac{\mu^{-1+1/(4k)}}{2}.\]

We first prove the asymptotic expression given for $\ell^*$ in the statement of the lemma.
We write
\[\ell^*=\sqrt{n ((1/2-1/(8k))\ln \mu- c(n)\ln \ln\mu)}\]

for a function $c(n)$, , $c(n)$ stands for the $\Theta(\log\log \mu)$-term in the claimed
divided by $\ln\ln \mu$.

\begin{align*}
\frac{\sqrt{n}}{\ell^*\sqrt{8\pi}}e^{-2(\ell^*)^2/n}  &  =
\frac{\sqrt{n} \mu^{-1+1/(4k)} e^{2c(n)\ln\ln \mu}}{\ell^*\sqrt{8\pi} }   =
\frac{\sqrt{n}(\ln\mu)^{2c(n)} }{\sqrt{n \bigl((1/2-1/(8k))\ln \mu-c(n)\ln\ln \mu\bigr)} \sqrt{8\pi}}  \mu^{-1+1/(4k)} \\
& = \frac{1}{\sqrt{8\pi\left(\left( \frac{1}{2}-\frac{1}{8k}\right)(\ln \mu)^{1-4c(n)}-\frac{c(n)\ln\ln \mu}{(\ln \mu)^{4c(n)}}\right)} }  \mu^{-1+1/(4k)}
\end{align*}

the fraction equals $1/2$ for some choice of $c(n)$ that converges to the constant $1/4$, as can be seen
from solving

\[
\sqrt{8\pi\left(\frac{1}{2}-\frac{1}{8k}\right)(\ln \mu)^{1-4c(n)}} = 2
\]

for $c(n)$ and exploiting that $\frac{c(n)\ln\ln \mu}{(\ln \mu)^{4c(n)}}=o(1)$ thanks to our assumption $\mu=\omega(1)$.

By Lemma <ref>, we have for any of the random variables $X_i \sim \Bin(n,1/2)$
$\prob{X_i\ge n/2+\ell^*} \ge (1-o(1))\mu^{-1+1/(4k)}/2$ and therefore
$\prob{D_i \ge \ell^*} \ge (1-o(1))\mu^{-1+1/(4k)}$. Using the independence of the random variables, the probability
at there is at least one $i\in\{1,\dots,\mu\}$ with this property is therefore at least

\[
1-\left(1-\mu^{-1+1/(4k)}\right)^\mu = 1-o(1).
\]

While the previous lemma established the existence of a high extremal
value for the $D_i$, the next lemma shows that the maximum order
statistic with high probability actually is an outlier, more precisely,
that it is almost $\sqrt{n}$ larger than the second-largest $D$-value.

With probability $1-o(1)$, there exists $\delta^*=O(n^{1/2-\epsilon})$ for an arbitrary constant $\epsilon>0$
such that $D_{(1)}-D_{(2)}\geq \delta^*$.

To prove Lemma <ref>, we need to show for all $D_i\neq D_{(1)}$ that they are
significantly smaller than $D_{(1)}$. However, this does not imply the lemma yet since
there may be more than one variable taking the maximum value. Hence,
we first prove the following auxiliary statement, showing that
the largest order statistic is unique with high probability.

Assume $D_{(1)}\ge \ell^*$ and let $i$ be an index such that $D_i=D_{(1)}$.
Then with probability $1-o(1)$ it holds that $D_{j}<D_{i}$ for all $j\neq i$.

The main idea of the proof is to exploit that the first bound (on the probability value) and the second bound (on the
distribution) in Corollary <ref>
are within a ratio of $\Theta(h/n)$, making it unlikely for any other individual to hit exactly the value of $D_{(1)}$.
For a moment, we consider the random $D_i$ without the condition
$D_{(1)}\ge \ell^*$.

According to Lemma <ref>, we have
$\ell^*=\Theta(\sqrt{n\log \mu})$.
We already know that $\Prob(D=\ell^*)=(2+o(1))\Prob(X_i\ge n/2+\ell^*)$ and obtain
from the first inequality in Corollary <ref> that

\begin{align*}
\Prob(D_i = \ell^*) = O\,\Bigl(\frac{\polylog \mu}{\mu^{1-1/(4k)}\sqrt{n}}\Bigr) %\\
O\,\Bigl(\frac{\polylog \mu}{\mu n^{1/4}}\Bigr) ,
\end{align*}

where we used $\mu^{1/(4k)}\le n^{1/4}$. Also, for values $k\ge \ell^*$
we clearly have $\Prob(D=k)\le \Prob(D=\ell^*)$ by the monotonicity of the binomial

We now consider the generation of the $\mu$ random
$D_i$-values as a stochastic process, assuming that
$D_i$ is generated at time $i$. Note that our condition
$D_{(1)}\ge \ell^*$ is equivalent to that there exists a (random) $i\in\{1,\dots,\mu\}$ such that
$D_i\ge \ell^*$. Let $T$ denote the smallest such $i$. For $j<T$ is clearly
holds $D_j<\ell^*\le D_{(1)}$. After time $T$, the
condition $D_{(1)}\ge \ell^*$ is satisfied so that each of the $D_{T+1},\dots,D_{\mu}$ is conditioned
on being at most $D_{(1)}$. Since even $\prob{D_j\le \ell^*} = 1-o(1)$, the conditional probability
is only by a factor $1+o(1)$ larger than the unconditional one.
Hence, it is sufficient to show that
the values $D_{T+1},\dots,D_{\mu}$ unconditionally  with high probability are less than $D_{(1)}$.

By the above calculations,
for all $i>T$, we get

\[
\Prob(D_i=D_{(1)}) =
O\,\Bigl(\frac{\polylog \mu}{\mu n^{1/4}}\Bigr).
\]

Now a union bound over the $\mu-T$ variables yields the desired result.

We now prove the outlier property of the largest order statistic.
Lemma <ref>
We recall that $\ell^*=\Theta(\sqrt{n\log \mu})$.
By using the second inequality of Corollary <ref>,
we note that for $\delta^*=O(n^{1/2-\epsilon})$ and any $i\in\{1,\dots,\mu\}$ it holds that
$C\prob{D_i\geq\ell^*}=(1\pm o(1))\prob{D_i\geq\ell^*-\delta^*}$,

\begin{equation*}
\exp\left(\frac{4\ell^*\delta}{n}-\frac{2\delta^2}{n}\right)
\end{equation*}

\begin{align*}
&\prob{D_{(1)}-\delta\leq D_i < D_{(1)} \mid D_{(1)}\geq\ell^*\wedge
D_i<D_{(1)}}\leq\prob{D_i\geq\ell^*-\delta\wedge D_i<\ell^*\mid D_i<D_{(1)}}\\
&=(1+o(1))(C-1)\prob{D_i\geq\ell^*} =O(1/\mu)\mu^{1/(4k)} n^{-\epsilon} = O(\mu^{-1}n^{-\epsilon/2})\enspace, %\\
\end{align*}

where the first inequality follows from exploiting the condition
that $D_{(1)}\geq\ell^*$
and the fact that $\Prob([x-a,x])$ is decreasing in $x$
for any positive constant $a$ and $x-a$ being larger than the mode.
In the second inequality we used $\Prob(A\mid B)\leq\Prob(A)/\Prob(B)$

\begin{equation*}
\Prob(D<D_{(1)})\geq
\Prob(D_{(1)}\geq\ell^*)\Prob(D<D_{(1)}\mid D_{(1)}\geq\ell^*)=1-o(1)\enspace,
\end{equation*}

which follows from Lemma <ref> and Lemma <ref>.
The equalities then follow from bound on $C$ derived above, the
fact $\prob{D_i\ge \ell^*}\le \mu^{-1+1/(4k)}$ and sufficiently large $k$.

Hence, we have that the unconditional probability

\begin{equation*}
\Prob\left(D_{(1)}-\delta\leq D < D_{(1)}\right)
\leq\frac{o(1/\mu)}{(1-o(1))}
\end{equation*}

Now, by a union bound, the probability that there exists some $j\neq (1)$ such that
$D_{(1)}-\delta\leq D_j < D_{(1)}$ is $o(1)$. In particular, the probability
of $D_{(2)}$ being in this interval is $o(1)$.

Lemma <ref>, which establishes the outlier in the initial population
is now crucial to show that the outlier will take over the whole population with high probability
before the rest of the population can catch up to the outlier. The following
lemma makes this take-over effect formal.

If the best individual in a population optimising has a fitness value
$\Omega(n^{\epsilon})$ larger than the second best for some
$\epsilon=\Omega(1)$, then the population will be taken over by individuals from
the best solution's branch whose fitness values are all at least as good as the
initial best fitness in $n^{\epsilon/4} \mu \log{\mu} $ generations w.o.p.

Using a standard analysis of take-over times (, [19, 41]) it takes an expected number of
$\Theta(\mu \log \mu)$
generations until the population is taken
over by solutions from the best individual's branch, unless an equal or better search point
on the opposite branch is sampled. Using Markov's inequality and analyzing the probability
of failing to take over within $n^{\epsilon/4}$ phases of length $\Theta(\mu \log \mu)$ each,
we obtain that the take-over time is $O(n^{\epsilon/4} \mu \log{\mu})$ w.o.p.

We now use the well-known family tree technique [41] for the analysis of the
to show that the offspring of any other individual than the initially best
with high probability cannot catch up to the fitness of the initially best.
The family tree of any initial solution will not
reach a depth larger than $n^{\epsilon/2}$ in
$n^{\epsilon/4} \mu \log{\mu}$ generations w.o.p.
according to Lemma 2 in [41].
Let us call a path with any node which has Hamming
distance at least $3 n^{\epsilon/2}$ to its root a
bad path. The probability of observing a particular bad path
of length $\ell$ in a tree of depth smaller than
$n^{\epsilon/2}$ is at most $(1/\mu)^\ell e^{- 3n^{\epsilon/2}}$. Using
a union bound over all paths of length at most $n^{\epsilon/2}$
that can be observed in $n^{\epsilon/4} \mu \log{\mu}$ generations of the ,
we upper bound the probability of sampling a solution which has $3n^{\epsilon/2}$ more 1-bits than its root by,

\[
\sum^{n^{\epsilon/2}}_{\ell=1} \binom{n^{\epsilon/4} \mu \log{\mu}}{\ell} (1/\mu)^\ell e^{- 3n^{\epsilon/2}}\leq n^{\epsilon/2} e^{n^{\epsilon/3}} e^{- 3n^{\epsilon/2}}=2^{-\Omega(n)}.
\]

The probability that a bad path will not be observed in the family tree
of any solution in the initial population can be shown to be exponentially
small by using a union bound once again. Hence, no offspring of the individuals
different from the best one will reach the fitness of the best with high probability.

We put everything together to prove our main result:

Theorem <ref>
According to Lemma <ref>,
$D_{(1)}-D_{(2)}=\Omega(n^{1/2-\epsilon})$ with probability $1-o(1)$.
We assume this to happen. Hence, Lemma <ref> can be applied,
such that  after
$n^{1/8} \mu \log{\mu} $ generations one branch will have died with probability $1-o(1)$. Moreover,
the lemma shows that the whole population after this time will be at least as good as the initially best one, which proves
that the worst  $\twomax$-value will be at least $n/2+D_{(1)} = n/2+\Omega(n^{1/2-\epsilon})$  at the time one branch dies out.

Finally, using the family tree technique in the same way as
for Lemma <ref>, we note
that the best -value in the population
will not increase by more than $n^{1/8}\log \mu$ in $n^{1/8} \mu \log{\mu} $ generations
with probability $1-o(1)$. Using that
$D_{(1)}=O(\sqrt{n}(\log \mu+\log n))$ with probability $1-o(1)$ (which follows
from simple Chernoff and union bounds), we obtain
that with probability $1-o(1)$,  the best $\twomax$-value is $O(n/2+c\sqrt{n}(\log n+\log \mu))$ at the time
one branch dies out, as claimed in the theorem statement.

We can straightforwardly
generalize Theorem <ref> to TruncatedTwoMax if the maximum fitness of the
truncated branch lies well above the best fitness reached after a branch has taken over. The theorem considers a -value of $n/2+c \sqrt{n}\log (\mu n)$, so
in principle we only have to choose $k$ slightly larger than the offset $c \sqrt{n}\log (\mu n)$. For convenience, we formulate
our corollary with $k = \omega(\sqrt{n}\log n)$.

Let $\mu\le n^{k'}$ for an arbitrary constant $k'\ge 0$ as well
as $\mu=\omega(1)$ and consider the on TruncatedTwoMax with $k = \omega(\sqrt{n}\log n)$. Let $\epsilon>0$ be
an arbitrary constant. Then with probability
$1/2-o(1)$ the whole population is on the truncated branch before the global optimum is reached, and
conditional on this event the optimisation time is $2^{\Omega(n^{1/2-\epsilon})}$

§.§ RLS Mutation

We can obtain a result analogous to Theorem <ref>
also for the
which differs from the only in the mutation operator. Basically,
the only difference is in the analysis of take-over times, which originally
refer to the time until the whole population descends from a certain individual and
is at least as good as it. For the using
standard-bit mutation,
the $O(\mu \log \mu)$ bound is based on the fact that an individual can produce
a copy of itself with probability $(1-1/n)^n \approx e^{-1}$. This is not the case
for the one-bit mutation of the , which either improves or degrades individuals' fitness. Nevertheless, we can use the same type of analysis
if the best and second-best individual are sufficiently large apart and the offspring of the best
do not become worse than the offspring of the second-best within a certain period of time.

More formally, let $x^*$ be the initially best individual and let after $t$ generations
the set $D_t$ denote the individuals in the population at time $t$ that are offspring of $x^*$.
Given $\card{D_t}=k<\mu$, the probability of choosing from $D_t$ is $k/\mu$ and, if this happens and the offspring
is accepted, it holds $\card{D_{t+1}}=k+1$. Hence, assuming all these offspring to be accepted, the time
until the whole population descends from $x^*$ has expected value $O(\mu \log \mu)$. Note that this does not imply
that all descendants are at least as good as $x^*$ in fitness.

Let $R^*$ be the other $\mu-1$ individuals from the initial population.
Offspring of $x^*$ are guaranteed to be accepted in the proposed time of expected $O(\mu\log \mu)$ generations

* no offspring of individuals in $R^*$ reaches fitness at least $(D_{(1)} + D_{(2)})/2$

* no offspring of $x^*$ has fitness less than $(D_{(1)}+D_{(2)})/2$

For either event to fail, the  progress must be at least $(D_{(1)}- D_{(2)})/2$ in at least one lineage
of one of the $\mu$ family trees stemming from the individuals of the initial population. Using Lemma <ref>
to bound the depth of each family tree by $n^{\epsilon/2}$ and observing that the progress along any lineage
due to one-bit mutation is bounded by the length of the lineage, we obtain a progress of at most
$n^{\epsilon/2}$ with probability $1-o(1)$ during the takeover time. This is clearly smaller than
the bound $(D_{(1)}- D_{(2)})/2 = n^{\epsilon/2}$ that results from uniform initialization
according to Lemma <ref> with probability $1-o(1)$. Hence, we have obtained the following result:

Let $\mu\le n^{k}$ for an arbitrary constant $k\ge 0$ as well
as $\mu=\omega(1)$ and consider the on .
With probability $1-o(1)$, all individuals are on one branch
before the $\twomax$-value reaches $n/2+c\sqrt{n}(\log n+\log \mu)$, for
some sufficiently large constant $c>0$, and
the worst $\twomax$-value  in the population
is $n/2+\Omega(n^{1/2-\epsilon})$
at the time one branch dies out. If this happens, individuals
from the other branch cannot be generated any more.

§ LOW SELECTIVE PRESSURE SUCCEEDS

In this section we will show that reducing the selection pressure to
its minimum by always picking the worst parent for reproduction makes the efficient at locating both optima of with reasonable population sizes.
In the following section we will argue why such a strategy is not sufficient for efficient global optimisation in general, and propose necessary corrections.
We begin by analysing the standard bit mutation version, the , and afterwards we consider the
RLS version. At the core of both proofs is the analysis of the stochastic process $D_t$ which keeps
track of the difference between the number of individuals with more $1$-bits and more $0$-bits.
The crucial observation is that, with inverse elitist parent selection, $D_t$ performs a fair
random walk which starts close to $0$ and, for large enough $\mu$, cannot reach w.o.p. any of the two
boundaries ($\mu$ or $-\mu$) before both optima are found.

For any arbitrarily small constant $\epsilon>0$, the

with inversely elitist parent selection and
$\mu=\Omega(n^{1+\epsilon})$ finds both optima of in $O(\mu n\log{n})$ fitness
function evaluations with probability $1-e^{-\Omega(n^{\epsilon})}$.

We will follow the same proof idea and the definition of relevant step
as in Theorem <ref>, however, since RLS cannot create copies, the
number $\mathcal{K}$ of relevant steps in a run  is bounded from above by
$\mu\cdot n$ because a solution is improved in each relevant step and each
individual can be improved at most $n$ times. We will denote the actual
iteration number of the $k$th relevant step as $\pi_k \in [T]$.	At every
relevant step $k$, the difference $D_k:=|P_{0}^{\pi_k}|-|P_{1}^{\pi_k}|$ either
increases or decreases by two with equal probability $1/2$. Formally,
$D_{k+1}-D_{k} \sim 2 \cdot \Bernoulli(\frac{1}{2})-1$ and consequently $D_k -
D_0 \sim 2 \cdot \Bin(k,\frac{1}{2})-k$.
As in the , the initial $D_0$ satisfies $\prob{|D_0| <
\mu^{\frac{1}{2}+\epsilon}}=\exp\left( -\Omega(\mu^{2\epsilon})\right)$.
Therefore, for any relevant step $k$,

\begin{align*}
&\prob{|D_k|=\mu \quad \big| \quad |D_0| <
\mu^{\frac{1}{2}+\epsilon}}\leq \prob{|D_k|-|D_0|\geq
\mu-\mu^{\frac{1}{2}+\epsilon}}\leq \prob{D_k-D_0\geq \mu-\mu^{\frac{1}{2}+\epsilon}}\\
&= \prob{2\cdot X -k\geq
\mu-\mu^{\frac{1}{2}+\epsilon}}= \prob{ X \geq \frac{\mu-\mu^{\frac{1}{2}+\epsilon}+k}{2}}= \prob{ X
\geq
\frac{\mu-\mu^{\frac{1}{2}+\epsilon}}{2}+E[X]}\\
1+\epsilon}} \right)\right)=\exp\left(-\Omega\left(n^{\epsilon}\right)\right)
\end{align*}

where $X\sim \Bin(k,\frac{1}{2})$ and in the last step we  used
the observation that $k\leq \mu\cdot n$ and the assumption that
$\mu=\Omega(n^{1+\epsilon})$. Using the above bound and the union bound over
$k\in[\mathcal{K}]$ we get our final result:

\[
\prob{\forall k \in [\mathcal{K}] \quad |D_k|\neq \mu
\quad \big| \quad |D_0|  < \mu^{\frac{1}{2}+\epsilon}}\geq 1- \mu \cdot n
\cdot \exp\left(-\Omega\left(n^{\epsilon}\right)\right)= 1-
\exp\left(-\Omega\left(n^{\epsilon}\right)\right)
\]

Thus, with probability $1-
\exp\left(-\Omega\left(n^{\epsilon}\right)\right)$,  $|D_k|<\mu$ for all $k$ and
the population is not taken over by any of the branches before all the solutions
reach the optimal fitness.

§ NOT TOO HIGH, NOR TOO LOW PRESSURE: EXPERIMENTAL SUPPLEMENTS

It is easy to see that the Inverse Elitist selection operator considered in the previous section
may struggle to identify the global optimum if the worst individual is trapped on a low quality local optimum. In such a case it will be selected until it escapes which may require prohibitive time.

In this section we present an experimental analysis of the using the selection operators considered in the previous sections (i.e., too high and extremely low selective pressure) together with a range of intermediate selective pressures that are higher than Inverse Elitist but still considerably lower than Uniform selection. To achieve such pressures we implement Inverse Tournament selection as defined in Section 2 with small tournament sizes[Naturally the same selection probabilities can be achieved with rank selection.].
Our aim is to show that the latter operator is preferable to both Uniform and Inversely Elitist selection because it has low premature convergence for and it can effectively escape from local optima as experiments for will show.

The results presented in this section are based on performing 1000 independent
runs for each combination of problem size and algorithm parameters, and
observing whether the ($\mu$+1) EA is able to construct both optima during the
search process. The presented figures estimate the probability that the
algorithms find both optima by the proportion of the independent runs which do
so. Additionally, a 95% confidence interval is displayed as a shaded region
around the estimated probabilities.

Proportion of independent runs finding both peaks on for various combinations of parent selection
operators, mutation operators (solid: RLS$_1$, dotted: standard bit mutation), and problem sizes.

We start by examining the success probability of the analysed selection
operators on for small problem sizes.
Figure <ref> compares the performance of
Inverse Elitist and Uniform parent selection operators for various population
and problem sizes. As expected, Uniform parent selection requires a larger
population size than Inverse Elitist parent selection in order to achieve the
same probability of finding both peaks; for the considered problem sizes, $\mu
= n^{1.5}$ appears sufficient for the combination of Inverse Elitist parent
selection and RLS mutation to achieve a high probability of discovering both
peaks, while SBM mutation requires a slightly larger population size, and
Uniform parent selection requires a significantly larger population size.

Proportion of independent runs finding both peaks on ($n=200$) for various combinations of parent selection
and mutation operators (solid: RLS$_1$, dotted: standard bit mutation).

Figure <ref> compares the performance of
Tournament and Inverse Tournament parent selection operators with that of
Inverse Elitist and Uniform parent selection operators for a fixed problem size
and varying population sizes. Generally, modest Inverse Tournament sizes (such
as $k=3$) are sufficient to achieve similar-or-better probability of
discovering both optima compared to Inverse Elitist parent selection when using
RLS mutation, and can even outperform Inverse Elitist parent selection when
using standard bit mutation. As expected, the higher selective pressure of the
traditional Tournament selection results in faster takeover by a single
branch, and hence a lower probability of finding both optima.

Proportion of independent runs finding both peaks on ($n=200$, $k=80$) for various combinations of parent selection
operators and mutation operators (solid: RLS$_1$, dotted: standard bit mutation).

For , where the left branch terminates at an earlier local
optimum, Figure <ref> shows that with
sufficiently high population sizes, Inverse Elitist parent selection is only
able to find both peaks with probability at most $1/2$, while the other parent
selection mechanisms are able to achieve higher probabilities of finding both
peaks compared to the non-truncated setting of
Figure <ref>. Additionally, Inverse
Tournament Selection suffers a runtime penalty in this setting: when the time
comes to remove from the population the local optimum on the truncated branch,
larger tournament sizes result in higher waiting times to select a
suitable parent to mutate. This is particularly pronounced when the population
size only provides a moderate (rather than high) probability of finding both
peaks. If the population is almost entirely on the truncated branch when that
local optimum is the lowest-fitness individual in the population, selecting a
parent from the other branch could require up to $O(\mu^{s})$ iterations, where
$s$ is the employed Inverse Tournament size, and would need to be repeated many
times to restore a reasonable probability of an iteration making progress
toward the global optimum. We conclude that small (i.e., constant) inverse tournament
sizes should be used in practice.

For the problems considered up to now, the use of single trajectory algorithms coupled with restart strategies suffice for efficient optimisation.
In the following sections we consider problems from the literature where restart strategies are ineffective.

§ WHERE POPULATIONS ARE ESSENTIAL BECAUSE RESTART STRATEGIES FAIL

In the previous sections we have shown that decreasing the selective pressure below uniform, increases the exploration capabilities of the . Essentially lower selective pressure increases the takeover time, effectively allowing the population to explore the two slopes of . However, when multiple slopes can be identified with high probability at initialisation as for , then single trajectory algorithms with appropriate restart strategies can be just as, or even more, effective.

In this section we consider two benchmark function classes from the literature originally designed
to highlight circumstances where populations are essential and single trajectory algorithms fail w.o.p.

The two function classes have different characteristics. The first
one,  SufSamp, was introduced to show situations when offspring populations outperform
single trajectory algorithms [25]. The function consists of a main steep path
leading to the global optimum with many branching points located at regular intervals. At each such
point a branch leading towards a different local optimum may be followed. While single
trajectory algorithms are tricked into following one of the branches, algorithms using large enough
offspring populations can identify the steeper slope by sampling many solutions around each
branching point.  We will refer to this function using a more descriptive name: .
The other function class, TwoGradients, is inspired by one designed to highlight when the
use of parent populations is essential [41]. It consists of two different paths: an
easier one for hillclimbers leading to local optima and a slower one which leads to the global
optimum. While single trajectory algorithms quickly optimise the easier path, the slower progress of
parent populations on the easy path allows the to follow the not-so-steep gradient to the
global optimum.

Since for both function classes,
single trajectory algorithms are attracted w.o.p.
to the local optima, even restarts do not allow them to identify the global optimum in polynomial time. Apart from proving that the with the inverse selection operators optimises the problems efficiently, in this section we will also show, either through rigorous proofs or by experimental evidence, that it outperforms the same algorithm using uniform selection: the inverse selection algorithms can identify all the optima with high probability, hence optimise the functions efficiently independently of which local optimum is designated to be the global one. On the other hand, single trajectory algorithms and the uniform selection can be trapped w.o.p.

according to which optimum is the global one and even restarts cannot help them to optimise the functions efficiently.

§.§ A Function Class with Two Slopes

In the previous subsection we considered a function with many different slopes and only one global optimum.
We showed that inverse binary selection makes the efficient for the function by allowing it to explore all the slopes one at a time, while all other considered evolutionary algorithms require exponential time w.o.p.
In this subsection we study a function class with two different slopes that have to be explored in parallel. This function class was originally introduced by

to illustrate problem characteristics where large parent populations are essential [41]. More precisely, he defined
a function called $f$ where the w.o.p.
reaches a local optimum which needs exponential
time to escape from,
while the classical with uniform parent selection and population size $\mu\ge n/\!\ln(en)$
finds the global optimum in expected polynomial time.
Overall, according to which of the two optima is the  global one, parent populations may be either essential or detrimental w.o.p. (i.e., restarts do not change the outcome).
Our aim in this subsection is to show that  by using inverse tournament selection, the can efficiently identify both optima with high probability either in a single run (large tournaments) or via restarts (smaller tournaments).

We first prove that the function with the original global optimum
can also be optimized efficiently by the with inverse parent selection (here inverse binary tournament selection)
and a sufficiently large population. Afterwards we will show experimentally that both optima can be identified already for not too large population and tournament sizes i.e., the algorithm is preferable to the and the with uniform selection.

For simplicity, we do not use the original definition $f$
from [41] here, but a version that still allows for an exponential performance difference
using considerably shorter proofs. We remark that the simplified version does not allow a proof of polynomial time
in expectation  but still a polynomial time bound that occurs w.o.p.
efficient optimisation w.o.p.
Although we think that the with
inverse binary tournament selection and appropriate $\mu$ indeed has expected polynomial runtime on the original function $f$,
we do not find the additional proof overhead  that would be necessary for such a result appropriate.

The function we study is adapted from [41] and is a weighted sum of
two independent optimisation problems defined on disjoint subspaces of $\{0,1\}^n$. On the last
$\ell\coloneqq n^{1/3}$ bits, the well-known LeadingOnes problem has to be solved, more precisely
for $x=(x_1,\dots,x_n)$
we define $\LSO(x)\coloneqq \sum_{i=1}^{\ell} \prod_{j=1}^{i} x_{n-\ell+j}$ as the number of
leading suffix ones value. On the first $m\coloneqq n-\ell$ bits, a problem has be be solved, hence
we define $\PO(x)\coloneqq \sum_{i=1}^{m} x_i$ as the number of prefix ones. The function
is then defined by

\[
\sufpar(x)
\coloneqq \begin{cases}
n^2 \LSO(x) + \PO(x) & \text{if $\PO(x)\le 2m/3$}\\
n^2 \ell - m - 1 + \PO(x) & \text{otherwise}.
\end{cases}
\]

The function $\sufpar$ has a global optimum at $\LSO(x)=\ell$ and $\PO(x)=2m/3$. To reach this, it is  typically required
that the number of leading suffix ones is maximized before the number of prefix ones grows beyond $2m/3$. Any search point
where $\PO(x)> 2m/3$ is better than any search point with non-optimal $\LSO$-value. Hence, if number of prefix
ones is increased faster than the leading suffix ones and a PO-value of $2m/3$ is exceeded before optimising the suffix
then the function leads to a local optimum at $\PO(x)=m$. This local optimum is a trap since at least
$m/3$ prefix ones have to be flipped to reach the global optimum from there.

We now show (similarly to the original result from [41]) that the w.o.p.
fails to optimize $\sufpar$ efficiently.

With probability at least $1-2^{-\Omega(n^{1/3})}$, the needs time $2^{\Omega(n\log n)}$ to
optimize $\sufpar$.

The main idea is to show that w.o.p.

the reaches a so-called bad search point
where $\PO(x)\ge 3m/4$ and $\LSO(x)<\ell$. From all bad search points, it is necessary to flip at least
$m/12=\Omega(n)$ bits simultaneously to reach the global optimum. The probability of this is at most
$1/(m/12)!=2^{-\Omega(n\log n)}$ and according to a union bound,
with probability $1-2^{-\Omega(n\log n)}$ this does not happen in $2^{cn\log n}$ iterations if $c$ is chosen
as a sufficiently small constant.

To show that a bad search point is reached w.o.p.,
we study the growth of
the $\PO$-value carefully. First of all, by Chernoff bounds with probability $1-2^{-\Omega(n)}$, it
holds $\PO(x_0)\ge m/3$ for the initial search point $x_0$. Moreover,
$\prob{\LSO(x_0)\ge \ell/4} = 2^{-\ell/4}$ since this event requires to initialize the first $\ell/4$ suffix to all ones.

We assume $\PO(x_0)\ge m/3$ and $\LSO(x)\le \ell/4$ to happen, which altogether happens
with probability $1-2^{-\Omega(n)} - 2^{-\Omega(\ell)} = 1-2^{-\Omega(n^{1/3})}$. Next, we note
from the definition of $\sufpar$ that the $\PO$-value can only decrease in steps increasing the
$\LSO$-value. Finally, we note that the number of leading suffix ones can increase by
more than one when the leftmost zero in the suffix flips. More precisely, it increases by the number
of so-called free-riders, the bits being random after the leftmost suffix zero. It is well known
that the number of free-riders is stochastically bounded by a geometric distribution with parameter $1/2$.

We claim that it is
sufficient to observe the following set of four events in a phase of length $s\coloneqq 3em$ to create a bad search point,
pessimistically assuming that no bad search is created before:

* There are at least $m/2$ $\PO$-increasing steps,

* there are at most $\ell/4$ $\LSO$-increasing steps,

* the total number of prefix bits flipped in at most $\ell/4$ $\LSO$-increasing steps is
at most $\ell/2$,

* the total number of free-riders in at most $\ell/4$ $\LSO$-increasing steps is at most $\ell/3$.

If all these events together happen, the number of prefix ones increases  to
at least $m/3 + m/2 - \ell/2 \ge 3m/4$ and the number of leading suffix ones to at most $\ell/4 +
\ell/4 + \ell/3 < \ell$, which  corresponds to a bad search point. Hence, we only have to verify that
each of the four events happens with probability at least $1-2^{-\Omega(n^{1/3})}$, from which the theorem
follows via a union bound.

The first event happens with probability $1-2^{-\Omega(m)}$ according to Chernoff bounds since each of the $s=3em$ steps flips
one of the least $m/4$ zero-bits with probability at least $(m/4)(1/n)(1-1/n)^{n-1} \ge 1/(5e)$ for $n$ large enough. The second
event occurs with probability $1-2^{-\Omega(\ell)}$ by Chernoff bounds
since the probability of an $\LSO$-increasing step is $1/n$, resulting
in an expected number of at most $3e$ such steps. The third event is also shown to occur with
probability $1-2^{-\Omega(\ell)}$ via Chernoff bounds since each of the $m$ prefix bits is flipped independently
with probability $1/n$. Finally, using Chernoff bounds for the geometric distribution, also the probability
of the fourth event is bounded by $1-2^{-\Omega(\ell)}$.

We now present the positive result, showing that the both with uniform and inverse binary tournament
selection optimize $\sufpar$ efficiently for sufficiently large $\mu$.

Let $\mu=\sqrt{n}$. Then the both with uniform and with inverse binary tournament parent selection
optimize $\sufpar$ in time $O(n^{2.15})$ with probability $1-2^{-\Omega(n^{0.15})}$.

The proof strategy is again inspired by the corresponding result for the function $f$ in [41]. We
consider a phase of length $s\coloneqq 22\ell n^{1.15}$ and show that w.o.p.
the number of leading suffix ones rises to its maximum $\ell$ before
an individual with at least $2m/3$ prefix ones is created. From there the global optimum is reachable within $O(n^{2.15})$
generations w.o.p.

In more detail, we first consider the growth of the potential $L$, defined as the maximum number of leading suffix ones
within the population. During this analysis, we assume that no individual with more than $2m/3$ prefix ones is created within the phase.
As we will prove below,
this assumption is valid for $s$ generations with probability $1-2^{-\Omega(n^{0.98{\color{black}\overline{3}}})}$. Given a current potential $L$, we call an individual
top if it has $L$ or more leading suffix ones. We consider the grow of the number of top individuals, noting that this number is non-decreasing
since only individuals of lowest fitness are removed and the factor $n^2$ in the definition of $\sufpar$  gives higher fitness to
individuals with more leading suffix ones regardless of the prefix ones. Let $T$ be the number of top individuals. The probability
of increasing this number by choosing and cloning such an individual is at least
$\frac{T}{\mu}(1-1/n)^n \ge \frac{T}{2e\mu}$ for uniform parent selection and
at least $\frac{T^2}{\mu^2}(1-1/n)^n \ge \frac{T^2}{2e\mu^2}$ for inverse binary tournament selection since it suffices to choose two top individuals
for the tournament. Hence, by standard argument for takeover times as in [41], the expected time
to reach $\mu$ top individuals is at most

\[
2e\mu\sum_{T=1}^\mu 1/T \le 2e\mu(\ln \mu+1)
\]

for uniform

\[
2e\mu^2\sum_{T=1}^\mu 1/T^2 \le 2e\mu^2 \frac{\pi^2}{6} \le 9\mu^2
\]

for inverse binary tournament selection. We assume that $n$, and thereby $\mu$, is large enough so that $2e\mu(\ln\mu+1) \le 9\mu^2$ holds. Given $\mu$ top
individuals and pessimistically assuming the $L$-value has not increased in the meantime, the probability of increasing the $L$-value
is at least $1/n$ since only the leftmost suffix zero has to flip. Hence, altogether, the expected time to increase the
$L$-value is at most $9\mu^2+n=10n$ by our choice
of $\mu$ and the
expected time to reach $\ell$ suffix ones in all individuals
is at most $10\ell n+9\mu^2 \le 11\ell n$ (still assuming no individual with at least $2m/3$ prefix ones). By applying Markov's inequality
and repeating this argumentation for $n^{0.15}$ subphases of length $20\ell n$, we obtain
that the probability of reaching $\ell$ suffix ones for all
individuals within
$22\ell n^{1.15} = O(n^{1.484})$ generations is at least  $1-2^{-\Omega(n^{0.15})}$. From this point on the algorithm proceeds as if
it was optimising on the $m$ prefix bits only. Adjusting the preceding analysis (using $m$ instead of $\ell$ improvements, each pessimistically
happening with probability at least $1/(2en)$),
the remaining time to reach the global
optimum is easily bounded by $O(m n^{1.15})=O(n^{2.15})$ with probability $1-2^{-\Omega(n^{0.15})}$.

It remains to prove that within $s$ generations no individual with at least $2m/3$ prefix ones is created w.o.p.

For this purpose,
we use a straightforward generalization of the family tree argument from [41], pessimistically assuming that each vertex in the tree at time $t$ twice
has the chance of $1/\mu$ to receive a new child. This caters for the inverse
binary tournament selection and increases the bound on the depth from Lemma 2 in [41]
only by a factor of $2$; hence the probability that the depth $D(t)$ at time $t$ is $6t/\mu$ or bigger is $2^{-\Omega(t/\mu)}$. We use this statement
with $t\coloneqq s$, implying that the probability of the depth being at least $d^*\coloneqq 22\ell n^{1.15}/\mu = 22n^{0.98\overline{3}}$ is  $2^{-\Omega(n^{0.98{\color{black}\overline{3}}})}$. Hence,
in order to reach $2m/3$ prefix ones within $s$ steps, either the tree must have depth greater than $d^*$, or it must contain a so-called bad path of length
at most $d^*$ along which the number of prefix ones is increased by at most $m/12$. Here we assume
that all initial individuals have at most $7m/12$ prefix ones, which
happens with probability $1-2^{-\Omega(n)}$ by Chernoff bounds and a union bound over $\sqrt{n}$ individuals.

The probability
of increasing the number of ones by at least $m/12 = \Omega(n)$
on a fixed path of length $d^*=o(n)$ in the family tree is $2^{-\Omega(n)}$ by Chernoff bounds since such a path
is an independent sequence of mutations without selection. Only if this increase happens, the path is bad.
By considering all possible paths in a union bound,
the probability of a bad path emerging in $s$ generations is at most

\begin{align*}
\sum_{k=1}^{d^*} \binom{s}{k} \left(\frac{2}{\mu}\right)^k 2^{-\Omega(n)} & = \sum_{k=1}^{d^*} \binom{d^*\mu}{k} \left(\frac{2}{\mu}\right)^k
2^{-\Omega(n)} \\
& \le \sum_{k=1}^{d^*} \left(\frac{ed^*\mu}{k}\right)^k \left(\frac{2}{\mu}\right)^k 2^{-\Omega(n)} = \sum_{k=1}^{d^*} \left(\frac{2ed^*}{k}\right)^k 2^{-\Omega(n)}  \\
& \le d^* \left(\frac{2ed^*}{d^*}\right)^{d^*} 2^{-\Omega(n)}  \le 2^{O(d^*)} 2^{-\Omega(n)} = 2^{-\Omega(n)},
\end{align*}

where the first inequality used the well-known estimate $\binom{n}{k}\le (en/k)^k$, the second one
that the terms of the sum are monotone increasing within the considered range of $k$ and the final
estimation that $d^*=o(n)$.
Summing up all failure probabilities in a union bound completes the proof.

§ DISCUSSION

In the previous sections we have shown several advantages of using lower selective pressure than uniform for standard steady-state EAs i.e., that only use mutation.
In this section we present a discussion of how previous literature has argued that uniform parent selection induces too high selective pressure also in steady-state GAs that use crossover as well as mutation.

Striving for a good balance between exploration and exploitation has arguably been the hottest topic in evolutionary computation since its conception.
Already in his seminal book, John Holland introduced and analysed two forms of reproductive schemes to serve as a basis for the field of genetic algorithms [22].
One was the canonical generational model, where $\mu$ individuals were selected according to fitness proportional selection and the offspring replaced the entire population, independent of their quality.
The other scheme used overlapping generations where only one new offspring was created in each generation: an individual was selected for reproduction with fitness proportional selection and an individual was removed uniformly at random
from the parent population to make space for the new offspring. Hence, individuals would have an expected lifetime of $\mu$ generations rather than only one generation as in generational models. The idea was that if the average fitness of the population didn't change much over the lifetime of an individual $i$, then the expected number of offspring of that individual would be the same as in the generational model (i.e., $f(i) / \bar{f}$, which was the basis for Holland's schema theorem).

In practice, the average fitness of the population changes  over the lifetime of individuals in the overlapping model. An empirical study by Kenneth De Jong showed how the use of overlapping generations introduced genetic drift (i.e., faster takeover times) which increased in severity with the decrease in size of the offspring population (i.e., $\lambda=1$ leads to the most severe genetic drift) [15]. As a result, the generational model was preferred by researchers and became the standard as well as the backbone of the canonical genetic algorithm [20]. Since fitness proportional selection was applied to select parents, fitness-scaling functions had to be used to distinguish between individuals and avoid premature convergence once all the population had similar fitness values.

In 1985 James Baker reported experiments where the selection probability of individuals was allocated according to their rank in the population rather than according to their fitness relative to the population's average fitness.
Rank-based selection not only resolved the scaling problems due to fitness proportional selection (which had previously also been avoided by Brindle's Tournament selection [21]) but, more importantly, allowed for an easy way to control the selective pressure and keep it constant throughout the optimisation process [39]. Rank selection allows to explicitly set the expected number of offspring of each individual as a function of their rank in the population.
Baker's intention was to slow down convergence to achieve more accurate optimisation. With the introduction of the Genitor (GENetic ImplemenTOR) algorithm, the first of what Syswerda termed “steady-state” GAs [38],
the opportunity to use steady-state schemes to gain control over the conflict between exploration and exploitation was also envisaged. Whitley states that “It can be argued that there are only two primary factors in genetic search: population diversity and selective pressure. These two factors are inversely related [...] As selective pressure is increased, the search focuses on the top individuals in the population, but because of this “exploitation” genetic diversity is lost. Reducing the selective pressure (or using larger population sizes) increases “exploration” because more genotypes and thus more schemata are involved in the search [...] [Hence] selective pressure and population diversity should be controlled as directly as possible [...] Selective pressure can be simply controlled by allocating reproductive trials according to rank” [39].

However, the envisaged balance between exploration and exploitation was never achieved with the Genitor algorithm or other steady-state GAs because

the same parent selection operators as used in generational schemes were adopted (typically rank selection with a bias of at least 1.5 in Genitor and fitness-proportional selection by Syswerda)
while at the same time low quality individuals were deleted for replacement (the worst in Genitor, exponential inverse ranking in Syswerda's version).
Naturally, these choices led to considerably greater genetic drift than that witnessed by De Jong (when, in his overlapping GA, he deleted random individuals)
as pointed out by an excellent theoretical analysis of the takeover times of various selection operators by Goldberg and Deb [21].

In this paper we have shown how the steady-state scheme can indeed be used to largely reduce the exploration/exploitation conflict.

While decreasing the selective pressure to uniform or even lower is indeed impractical (if not impossible) in generational schemes [7], it can be easily implemented in steady-state algorithms.

In particular, the artificially introduced elitism in steady-state GAs protects the best individuals so long as better ones are not identified. Hence, there is no hurry to exploit the best individuals before they disappear: as long as they really are good, they will not be removed from the population.
This simple insight sheds light on how the conflict between exploration and exploitation may be largely reduced with steady-state schemes: there is no need for a perfect balance between exploration and exploitation. Exploration may proceed for as long as desired because the best individuals will always be waiting to be exploited as long as better solutions are not identified first.
In particular, steady-state algorithms allow for the selective pressure to be reduced to low levels that are impossible to achieve with the generational model.
This is indeed the distinguishing power of steady-state EAs and what makes overlapping generations special.

In this paper we have provided theoretical and empirical evidence of the advantages that can be gained by exploiting this insight.

To the best of our knowledge no previous studies of reducing the parent selective pressure below uniform have been undertaken.
We have recently discovered that the insight presented in this paper to avoid premature convergence (i.e., preventing the best individuals from reproducing) was briefly mentioned by Bäck and Hoffmeister in 1991 and termed "left extinctive selection" [1]. However, they deemed that the idea might not have any practical relevance and, to the best of our knowledge, was abandoned (the idea is indeed impractical in the context of the ($\mu,\lambda)$ generational GAs	they were using in this particular work: a steady-state scheme is required). On the other hand,  studies on replacement strategies to reduce genetic drift have been undertaken which led to smaller takeover times than in standard steady-state GAs [33, 5].

§ CONCLUSION

In this paper we have analysed the effects of decreasing the parent selection pressure of a standard steady-state EA well below the commonly used uniform selection and have shown the benefits of this decrease without requiring any further algorithmic sophistication.
In particular, we first

proved that the and evolving populations of arbitrary polynomial size
via uniform parent selection, or via operators with higher selective pressure, fail
to identify both optima of the benchmark function with high probability.
On the other hand, we proved that the algorithms are efficient at locating both optima for reasonable population sizes
if Inverse Elitist selection is used instead. An experimental analysis explains why Inverse Tournament selection with small tournament sizes
is even more powerful for global optimisation: for the tested problem sizes it has higher success probabilities for and is capable of
escaping local optima of . In particular, in order to escape from local optima some probability of not selecting the worst individuals is crucial.

Afterwards we analysed the impressive performance of the low selective pressure algorithms for more sophisticated multi-modal problems generalised from  previously used benchmark functions from the literature which we named RidgeWithBranches and TwoGradients.
The two functions have different characteristics. The former consists of a series of local optima that should be identified one at a time, while the latter consists of two gradients with different steepnesses which should be optimised in parallel.
While the Inverse Tournament is efficient for all the problems, we are not aware of any other algorithm, with or without diversity, that can efficiently optimise all the three function classes , RidgeWithBranches and TwoGradients. In fact we are not aware of any other algorithm that is effective for RidgeWithBranches alone. The latter is an exemplary benchmark function to highlight the explorative capabilities of steady-state EAs with low selective pressure: the algorithm explores one branch at a time, identifying one local optimum after another, and only abandoning each one if it does not turn out to be the global optimum.

The last section of the paper presented an experimental analysis of the algorithms for the classical MaxSat and Multidimensional Knapsack problems.
For both problems the inverse selection operators outperform uniform selection. However, for the MaxSat instances single trajectory algorithms with restarts outperform all the population based EAs, while for the knapsack instances the opposite is true.

We conclude with a final comment regarding the optimisation time of the inverse selection algorithms.
We have presented very effective algorithms for multi-modal optimisation with minimal sophistication (i.e., no additional parameters compared to basic EAs).
For all the problems considered in this paper, we see no reason to use a selection operator with higher pressure than inverse tournaments of constant size.
For difficult multi-modal problems with many optima, extremely fast global optimisation cannot reasonably be expected.
For easier unimodal problems, the selective pressure may be increased by simply decreasing the population size (i.e., if the problem is easy, then large populations are not necessary).
For instance, consider the simple OneMax problem. The expected runtime of the inverse tournament is $O(\mu n \ln n)$ which is the same asymptotic expected runtime of the algorithm using uniform selection and deterministic crowding as diversity mechanism [19].
The expected runtime can be reduced to the best achievable via standard bit mutation-only (i.e.,   $O(n \ln n)$) simply by reducing the population size to a constant (i.e., effectively increasing the selective pressure).
Furthermore, we believe that the standard ($\mu$+1) GA (i.e., with crossover)  coupled with inverse tournament selection with constant tournament and population sizes is faster than any standard bit mutation-only evolutionary algorithm for OneMax.
This result may be proven by simply re-calculating the takeover times in the analysis of [9]. In particular, also the result that the algorithm is faster than any unary unbiased
search heuristic, if identical copies of parents are not re-evaluated, holds.
Indeed, future work should explore theoretically and experimentally the effects of lower selective pressure on more sophisticated algorithms using crossover, more advanced mutation operators [10, 11, 18], and problem-tailored ones [26, 27].

The authors would like to thank the members of the EC-Theory group in the UK for initial discussions regarding the analysis of
steady-state EAs with large population sizes for TwoMax.
A special thank you also goes to Christian Gießen for his collaboration in the preliminary versions of this paper.
Part of this work was funded by the EPSRC under grant agreement N. EP/M004252/1.

[1]
T. Bäck and F. Hoffmeister.
A survey of evolution strategies.
In R.K Belew and L.B. Booker, editors, Proceedings of the Fourth
International Conference on Genetic Algorithms, pages 92–99. Morgan
Kaufmann, 1991.

[2]
T. Bäck, F. Hoffmeister, and HP. Schwefel.
A survey of evolution strategies.
In Proceedings of the Fourth International Conference on Genetic
Algorithms, pages 2–9. Morgan Kaufmann, 1991.

[3]
J. E. Beasley.
Or-library: distributing test problems by electronic mail.
Journal of the operational research society, 41(11):1069–1072,
http://people.brunel.ac.uk/ mastjjb/jeb/info.html.

[4]
B. Bollobas.
Random Graphs.
Academic Press, London - New York, 1985.

[5]
Jürgen Branke, Massimo Cutaia, and Heinrich Dold.
Reducing genetic drift in steady state evolutionary algorithms.
In Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO 1999), pages 68–74. Morgan Kaufmann, 1999.

[6]
P.C. Chu and J.E. Beasley.
A genetic algorithm for the multidimensional knapsack problem.
Journal of Heuristics, 4(1):63–86, 1998.

[7]
D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre.
Level-based analysis of genetic algorithms and other search
IEEE Transactions on Evolutionary Computation, 22(5):707–719,

[8]
D. Corus and P. S. Oliveto.
Standard steady state genetic algorithms can hillclimb faster than
mutation-only evolutionary algorithms.
IEEE Transactions on Evolutionary Computation, 22(5):720–732,

[9]
D. Corus and P. S. Oliveto.
On the benefits of populations for the exploitation speed of standard
steady-state genetic algorithms.
Algorithmica, pages –, 2020.
In press (Online).

[10]
D. Corus, P. S. Oliveto, and D. Yazdani.
Fast artificial immune systems.
In Proceedings of the International Conference on Parallel
Problem Solving from Nature (PPSN XV), volume 11102 of Lecture Notes in
Computer Science (LNCS), pages 67–78. Springer, 2018.

[11]
D. Corus, P. S. Oliveto, and D. Yazdani.
Artificial immune systems can find arbitrarily good approximations
for the NP-hard number partitioning problem.
Artificial Intelligence, 247:180–196, 2019.

[12]
D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre,
P. S. Oliveto, D. Sudholt, and A. M. Sutton.
Escaping local optima using crossover with emergent diversity.
IEEE Transactions on Evolutionary Computation, 22(3):484–497,

[13]
C. Darwin.
On the origin of the species.
John Murray., 1859.

[14]
C. Darwin.
The Variation of Animals and Plants under Domestication.
John Murray., 1868.

[15]
K. De Jong and J. Sarma.
Generation gaps revisited.
In Proceedings of Foundations of Genetic Algorithms II (FOGA
1993), pages 19–28, 1993.

[16]
A. de Perthuis de Laillevault, B. Doerr, and C. Doerr.
Money for nothing: Speeding up evolutionary algorithms through better
In Proceedings of the Genetic and Evolutionary Computation
Conference, (GECCO 2015), pages 815–822. ACM Press, 2015.

[17]
B. Doerr.
Analyzing randomized search heuristics: Tools from probability
In B. Doerr and A. Auger, editors, Theory of Randomized Search
Heuristics: Foundations and Recent Developments, pages 1–20. World
Scientific, 2011.

[18]
B. Doerr, H. Ph. Le, R. Makhmara, and T. D. Nguyen.
Fast genetic algorithms.
In Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO 2017), pages 777–784, 2017.

[19]
T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt.
Analysis of diversity-preserving mechanisms for global exploration.
Evolutionary Computation, 17(4):455–476, 2009.

[20]
D. E. Goldberg.
Genetic Algorithms in Search, Optimization and Machine
Addison-Wesley Longman, 1989.

[21]
D. E. Goldberg and K. Deb.
A comparative analysis of selection schemes used in genetic
In Proceedings of Foundations of Genetic Algorithms I (FOGA
1991), pages 69–93, 1991.

[22]
J. H. Holland.
Adaptation in natural and artificial systems: an introductory
analysis with applications to biology, control, and artificial intelligence.
MIT press, 1992.

[23]
S. Holm.
A simple sequentially rejective multiple test procedure.
Scandinavian Journal of Statistics, 6(2):65–70, 1979.

[24]
H. H. Hoos and T. Stützle.
Satlib: An online resource for research on sat.
SAT, 2000:283–292, 2000.

[25]
T. Jansen, K. A. De Jong, and I. Wegener.
On the choice of the offspring population size in evolutionary
Evolutionary Computation, 13(4):413–440, 2005.

[26]
H. Kautz and B. Selman.
Domain-independent extension to gsat: Solving large structured
satisfiability problems.
In Proceedings of the Thirteenth International Joint Conference
on Artificial Intelligence (IJCAI'93), pages 290–295, 1993.

[27]
H. Kautz and B. Selman.
Pushing the envelope: planning, propositional logic, and stochastic
In Proceedings of the Thirteenth National Conference on
Artificial Intelligence (AAAI'96), pages 1194–1201, 1996.

[28]
P. K. Lehre.
Negative drift in populations.
In Proceedings of the International Conference on Parallel
Problem Solving from Nature (PPSN XI), volume 6328 of Lecture Notes in
Computer Science (LNCS), pages 244–253, 2010.

[29]
J. Lengler.
A general dichotomy of evolutionary algorithms on monotone functions.
In Proceedings of the International Conference on Parallel
Problem Solving from Nature (PPSN XV)), volume 11101 of Lecture Notes
in Computer Science (LNCS), pages 3–15. Springer, 2018.

[30]
P. S. Oliveto, D. Sudholt, and C. Zarges.
On the benefits and risks of using fitness sharing for multimodal
Theoretical Computer Science, 773:53–70, 2018.

[31]
E. Covantes Osuna and D. Sudholt.
Analysis of the clearing diversity-preserving mechanism.
In Proceedings of Foundations of Genetic Algorithms (FOGA
2017), pages 55–63. ACM Press, 2017.

[32]
M. Preuss.
Multimodal Optimization by Means of Evolutionary Algorithms.
Natural Computing Series. Springer, 2015.

[33]
J. Smith.
On replacement strategies in steady state evolutionary algorithms.
Evolutionary Computation, pages 29–59, 2007.

[34]
H. Spencer.
The principles of biology.
Williams and Norgate, 1864.

[35]
D. Sudholt.
The benefits of population diversity in evolutionary algorithms: A
survey of rigorous runtime analyses.
In B. Doerr and F. Neumann, editors, Theory of Randomized Search
Heuristics in Discrete Search Spaces, pages 359–404. Springer, 2019.

[36]
A. Sutton.
Crossover can simulate bounded tree search on a fixed-parameter
tractable optimization problem.
In Proceedings of the Genetic and Evolutionary Computation
Conference (GECCO 2018), pages 1531–1538. ACM Press, 2018.

[37]
G. Syswerda.
Uniform crossover in genetic algorithms.
In Proceedings of the Third International Conference on Genetic
Algorithms, pages 2–9, 1989.

[38]
G. Syswerda.
A study of reproduction in generational and steady-state genetic
In Proceedings of Foundations of Genetic Algorithms I (FOGA
1991), pages 94–101, 1991.

[39]
D. Whitley.
The genitor algorithm and selection pressure: why rank-based
allocation of reproductive trials is best.
In Proceedings of the Third International Conference on Genetic
Algorithms, pages 116–121, 1989.

[40]
F. Wilcoxon.
Individual comparisons by ranking methods.
Biometrics Bulletin, 1(6):80–83, 1945.

[41]
C. Witt.
Runtime analysis of the ( $\mu$ + 1) ea on simple pseudo-boolean
Evolutionary Computation, 14(1):65–86, 2006.

[42]
C. Witt.
Fitness levels with tail bounds for the analysis of randomized search
Information Processing Letters, 114(1-2):38–41, 2014.