Theoretical Analysis of Stochastic Search Algorithms
Per Kristian Lehre

Pietro S. Oliveto

School of Computer Science,

Department of Computer Science,

University of Birmingham,

University of Sheffield,

Birmingham, UK

Sheffield, UK

September 5, 2017

arXiv:1709.00890v1 [cs.NE] 4 Sep 2017

Abstract
Theoretical analyses of stochastic search algorithms, albeit few, have always existed since
these algorithms became popular. Starting in the nineties a systematic approach to analyse
the performance of stochastic search heuristics has been put in place. This quickly increasing
basis of results allows, nowadays, the analysis of sophisticated algorithms such as populationbased evolutionary algorithms, ant colony optimisation and artificial immune systems. Results
are available concerning problems from various domains including classical combinatorial and
continuous optimisation, single and multi-objective optimisation, and noisy and dynamic optimisation. This chapter introduces the mathematical techniques that are most commonly
used in the runtime analysis of stochastic search heuristics. Careful attention is given to the
very popular artificial fitness levels and drift analyses techniques for which several variants are
presented. To aid the reader’s comprehension of the presented mathematical methods, these
are applied to the analysis of simple evolutionary algorithms for artificial example functions.
The chapter is concluded by providing references to more complex applications and further
extensions of the techniques for the obtainment of advanced results.

1

Introduction

Stochastic search algorithms, also called randomised search heuristics, are general purpose
optimisation algorithms that are often used when it is not possible to design a specific algorithm
for the problem at hand. Common reasons are the lack of available resources (e.g., enough
money and/or time) or because of an insufficient knowledge of the complex optimisation
problem which has not been studied extensively before. Other times, the only way of acquiring
knowledge about the problem is by evaluating the quality of candidate solutions.
Well-known stochastic search algorithms are random local search and simulated annealing.
Other more complicated approaches are inspired by processes observed in nature. Popular
examples are evolutionary algorithms (EAs) inspired by the concept of natural evolution, ant
colony optimisation (ACO) inspired by ant foraging behaviour and artificial immune systems
(AIS) inspired by the immune system of vertebrates.
The main advantage of stochastic search heuristics is that, being general purpose algorithms, they can be applied to a wide range of applications without requiring hardly any
knowledge of the problem at hand. Also, the simplicity for which they can be applied implies
that practitioners can use them to find high quality solutions to a wide variety of problems
without needing skills and knowledge of algorithm design. Indeed, numerous applications report high performance results which make them widely used in practice. However, through
experimental work and applications it is difficult to understand the reasons for these successes.
In particular, given a stochastic search algorithm, it is unclear on which kind of problems it
will achieve good performance and on which it will perform poorly. Even more crucial is the
lack of understanding of how the parameter settings influence the performance of the algorithms. The goal of a rigorous theoretical foundation of stochastic search algorithms is to
answer questions of this nature by explaining the success or the failure of these methods in
practical applications. The benefits of a theoretical understanding are threefold: (a) guiding
the choice of the best algorithm for the problem at hand, (b) determining the optimal parameter settings, and (c) aiding the algorithm design, ultimately leading to the achievement of
better algorithms.

1

Theoretical studies of stochastic optimisation methods have always existed, albeit few, since
these algorithms became popular. In particular, the increasing popularity gained by evolutionary and genetic algorithms in the seventies led to various attempts at building a theory for
these algorithms. However, such initial studies attempted to provide insights on the behaviour
of evolutionary algorithms rather than estimating their performance. The most popular of
these theoretical frameworks was probably the schema theory introduced by Holland [13] and
made popular by Goldberg [11]. In the early nineties a very different approach appeared
to the analysis of evolutionary algorithms and consequently randomised search heuristics in
general, driven by the insight that these heuristics are indeed randomised algorithms, albeit
general-purpose ones, and as such they should be analysed in a similar spirit to that of classical randomised algorithms [25]. For the last 25 years this field has kept growing considerably
and nowadays several advanced and powerful tools have been devised that allow the analysis of the performance of involved stochastic search algorithms for problems from various
domains. These include problems from classical combinatorial and continuous optimisation,
dynamic optimisation and noisy optimisation. The generality of the developed techniques,
has allowed their application to the analyses of several families of stochastic search algorithms
including evolutionary algorithms, local search, metropolis, simulated annealing, ant colony
optimisation, artificial immune systems, particle swarm optimisation, estimation of distribution algorithms amongst others.
The aim of this chapter is to introduce the reader to the most common and powerful tools
used in the performance analysis of randomised search heuristics. Since the main focus is the
understanding of the methods, these will be applied to the analysis of very simple evolutionary
algorithms for artificial example functions. The hope is that the structure of the functions and
the behaviour of the algorithms are easy to grasp so the attention of the reader may be mostly
focused on the mathematical techniques that will be presented. At the end of the chapter
references to complex applications of the techniques for the obtainment of advanced results
will be pointed out for further reading.

2 Computational Complexity of Stochastic Search
Algorithms
From the perspective of computer science, stochastic search heuristics are randomised algorithms although more general than problem specific ones. Hence, it is natural to analyse
their performance in the classical way as done in computer science. From this perspective an
algorithm should be correct, i.e., for every instance of the problem (the input) the algorithm
halts with the correct solution (i.e., the correct output) and it should be efficient in terms of
its computational complexity i.e., the algorithm uses the computational resources wisely. The
resources usually considered are the number of basic computations to find the solution (i.e.,
time) and the amount of memory required (i.e., space).
Differently from problem-specific algorithms, the goal behind general-purpose algorithms
such as stochastic search heuristics is to deliver good performance independently of the problem
at hand. In other words, a general-purpose algorithm is “correct” if it visits the optimal solution
of any problem in finite time. If the optimum is never lost afterwards, then a stochastic search
algorithm is said to converge to the optimal solution. In a formal sense the latter condition
for convergence is required because most search heuristics are not capable of recognising when
an optimal solution has been found (i.e., they do not halt). However, it suffices to keep track
of the best found solution during the run of the algorithm, hence the condition is trivial to
satisfy. What is particularly relevant and can make a huge difference on the usefulness of a
stochastic search heuristic for a given problem is its time complexity. In each iteration the
evaluation of the quality of a solution is generally far more expensive than its other algorithmic
steps. As a result, it is very common to measure time as the number of evaluations of the
fitness function (also called objective function) rather than counting the number of basic
computations. Since randomised algorithms make random choices during their execution, the
runtime of a stochastic search heuristic A to optimise a function f is a random variable TA,f .
The main measure of interest is:
1. The expected runtime E [TA,f ]: the expected number of fitness function evaluations until
the optimum of f is found;
For skewed runtime distributions, the expected runtime may be a deceiving measure of
algorithm performance. The following measure therefore provides additional information.

2

Figure 1: An efficient search heuristic (blue) versus and inefficient search heuristic (red) for a given
instance.
2. The success probability in t steps Pr (TA,f ≤ t): the probability that the optimum is
found within t steps.
Just like in the classical theory of efficient algorithms the time is analysed in relation to
growing input length and usually described using asymptotic notation [3]. A search heuristic
A is said to be efficient for a function (class) f if the runtime grows as polynomial function
of the instance size. On the other hand, if the runtime grows as an exponential function, then
the heuristic is said to be inefficient. See Figure 1 for an illustrative distinction.

3

Evolutionary Algorithms

A general framework of an evolutionary algorithm is the (µ+λ) EA defined in Algorithm
1. The algorithm evolves a population of µ candidate solutions, generally called the parent
population. At each generation an offspring population of λ individuals is created by selecting
individuals from the parent population uniformly at random and by applying a mutation
operator to them. The generation is concluded by selecting the µ fittest individuals out of the
µ + λ parents and offspring. Algorithm 1 presents a formal definition.

Algorithm 1 (µ+λ) EA
1: Initialisation:
Initialise P0 = {x(1) , . . . , x(µ) } with µ individuals chosen uniformly a random from {0, 1}n ;
t ← 0;
2: for i = 1, . . . , λ do
3:
Selection for Reproduction: Choose x ∈ Pt uniformly at random;
4:
Variation: Create y (i) by flipping each bit in x with probability pm ;
5: end for
6: Selection for Replacement
Create the new population Pt+1 by choosing the best µ individuals out of
{x(1) , . . . , x(µ) , y (1) , . . . , y (λ) };
7: t ← t + 1; Continue at 2;
In order to apply the algorithm for the optimisation of a fitness function f : {0, 1}n → R,
some parameters need to be set. The population size µ, the offspring population size λ and
the mutation rate pm . Generally pm = 1/n is considered a good setting for the mutation
rate. Also, in practical applications a stopping criterion has to be defined since the algorithm
does not halt. A fixed number of generations or a fixed number of fitness function evaluations
are usually decided in advance. Since the objective of the analysis is to calculate the time
required to reach the optimal (approximate) solution for the first time, no stopping condition
is required, and one can assume that the algorithms are allowed to run forever. The + symbol
in the algorithm’s name indicates that elitist truncation selection is applied. This means that
the whole population consisting of both parents and offspring are sorted according to fitness
and the best µ are retained for the next generation. Some criterion needs to be decided in
case the best µ individuals are not uniquely defined. Ties between solutions of equal fitness
may be broken uniformly at random. Often offspring are preferred over parents of equal

3

fitness. In the latter case if µ = λ = 1 are set, then the standard (1+1) EA is obtained, a very
simple and well studied evolutionary algorithm. On the other hand if some stochastic selection
mechanism was used instead of the elitist mechanism and a crossover operator was added as
variation mechanism, then Algorithm 1 would become a genetic algorithm (GA) [11]. Given
the importance of the (1+1) EA in this chapter, a formal definition is given in Algorithm 2.

Algorithm 2 (1+1) EA
1: Initialisation:
Initialise x(0) uniformly a random from {0, 1}n ;
t ← 0;
2: Variation:
Create y by flipping each bit in x(t) with probability pm = 1/n;
3: Selection for Replacement
4: if f (y) ≥ f (x(t) ) then
5:
x(t+1) ← y
6: end if
7: t ← t + 1; Continue at 2;
The algorithm is initialised with a random bitstring. At each generation a new candidate
solution is obtained by flipping each bit with probability pm = 1/n. The number of bits that
flip can be represented by a binomial random variable X ∼ Bin(n, p) where n is the number of
bits (i.e., the number of trials) and p = 1/n is the probability of a success (i.e. a bit actually
flips), while 1 − p = 1 − 1/n is the probability of a failure (i.e., the bit does not flip). Then, the
expected number of bits that flip in one generation is given by the expectation of the binomial
random variable, E [X] = n · p = n · 1/n = 1.
The algorithm behaves in a very different way compared to the random local search (RLS)
algorithm that flips exactly one bit per iteration. Although the (1+1) EA flips exactly one
bit in expectation per iteration, many more bits may flip or even none at all. In particular,
the (1+1) EA is a global optimiser because there is a positive probability that any point in
the search space is reached in each generation. As a consequence, the algorithm will find the
global optimum in finite time. On the other hand, RLS is a local optimiser since it gets stuck
once it reaches a local optimum because it only flips one bit per iteration.
The probability that a binomial random variable X ∼ Bin(n, p) takes value j (i.e., j bits
flip) is
!
n j
Pr (X = j) =
p (1 − p)n−j .
j
Hence, the probability that the (1+1) EA flips exactly one bit is
!   
n−1 
n−1
n
1
1
1
Pr (X = 1) =
·
· 1−
= 1−
≥ 1/e ≈ 0.37
n
n
n
1
So the outcome of one generation of the (1+1) EA is similar to that of RLS only approximately
1/3 of the generations. The probability that two bits flip is exactly half the probability that
one flips:
!  
n−2
2
n
1
1
Pr (X = 2) =
1−
2
n
n
 2 
n−2
n(n − 1) 1
1
=
1−
2
n
n

n−1
1
1
1−
≈ 1/(2e)
=
2
n
On the other hand the probability no bits flip at all is:
!
n
Pr (X = 0) =
(1/n)0 · (1 − 1/n)n ≈ 1/e
0
The latter result implies that in more than 1/3 of the iterations no bits flip. This should be
taken into account when evaluating the fitness of the offspring, especially for expensive fitness
functions.

4

Figure 2: A linear unitation block of length m starting at position m + k and ending at position
k. A linear unitation block of length n is the Onemax function.
In general, the probability that i bits flip decreases exponentially with i:
!

n−i

n−i
1
1
1
1
n
1
= · 1−
≈
Pr (X = i) =
· i · 1−
n
n
i!
n
i! · e
i
In the worst case all the bits may need to flip to reach the optimum in one step. This
event has probability 1/nn . Since, this is always a lower bound on the probability of reaching
the optimum in each generation, by a simple waiting time argument an upper bound of O(nn )
may be derived for the expected runtime of the (1+1) EA on any pseudo-Boolean function
f : {0, 1}n → R. It is simple to design an example trap function for which the algorithm
actually requires Θ(nn ) expected steps to reach the optimum [10]. This simple result further
motivates why it is fundamental to gain a foundational understanding of how the runtime of
stochastic search heuristics depends on the parameters of the problem and on the parameters
of the algorithms.

4

Test Functions

Test functions are artificially designed to analyse the performance of stochastic search algorithms when they face optimisation problems with particular characteristics. These functions
are used to highlight characteristics of function classes which may make the optimisation process easy or hard for a given algorithm. For this reason they are often referred to as toy
problems. The analysis on test functions of simple and well understood structure has allowed
the development of several general techniques for the analysis. Afterwards these techniques
have allowed to analyse the same algorithms for more complicated problems with practical applications such as classical combinatorial optimisation problems. Furthermore, in recent years
several standard techniques originally developed for simple algorithms have been extended to
allow the analyses of more realistic algorithms. In this section the test functions that will be
used as example functions throughout the chapter are
Pintroduced.
The most popular test function is Onemax (x) := n
i=1 xi which simply counts the number
of one-bits in the bitstring. The global optimum is a bitstring of only one-bits. Onemax is
the easiest function with unique global optimum for the (1+1) EA [5].
A particularly difficult test function
Q for stochastic search algorithms is the needle-in-ahaystack function. Needle(x) := n
i=1 xi consists of a huge plateau of fitness value zero
apart from only one optimal point of fitness value one represented by the bitstring of only
one-bits. This function is hard for search heuristics because all the search points apart from
the optimum have the same fitness. As a consequence, the algorithms cannot gather any
information about where the needle is by sampling search points.
Both Onemax and Needle (as defined above) have the property that the function values
only depend on the number of ones in the bitstring. The class of functions with this property
is called functions of unitation
!
n
X
Unitation(x) := f
xi
i=1

5

Figure 3: A gap unitation block of length m starting at position m + k and ending at position k.
A gap unitation block of length n − 1 is the Needle function.
Throughout this chapter, functions of unitation will be used as a general example class to
demonstrate the use of the techniques that will be introduced. For simplicity of the analysis,
the optimum is assumed to be the bitstring of only one-bits.
For the analysis the function of unitation will be divided into three different kinds of subblocks: linear blocks, gap blocks and plateau blocks. Each block will be defined by its length
parameter m (i.e. the number of bits in the block) and by its position parameter k (i.e., each
block starts at bitstrings with m + k zeroes and ends at bitstrings with k zeroes). Given a
unitation function it is divided into sub-blocks proceeding from left to right from the all-zeroes
bitstring towards the all-ones bitstring. If the fitness increases with the number of ones, then
a linear block is created. The linear block ends when the function value stops increasing with
the number of ones.

a|x| + b if k < n − |x| ≤ k + m
Linear(|x|) =
0
otherwise.
See Figure 2 for an illustration.
If the fitness function decreases with the number of ones, then a gap block is created. The
gap block ends when the fitness value reaches for the first time a higher value than the value
at the beginning of the block.

a if n − |x| = k + m
Gap(|x|) =
0 otherwise.
See Figure 3 for an illustration.
If the fitness remains the same as the number of ones in the bitstrings increases, then a
plateau block is created. The block ends at the first point where the fitness value changes.

a if k < n − |x| ≤ k + m
Plateau(|x|) =
0 otherwise.
See Figure 4 for an illustration.
By proceeding from left to right the whole search space is subdivided into blocks. See
Figure 5 for an illustration. Let the unitation function be subdivided into r sub-functions
f1 , f2 , . . . fr , and let Ti be the runtime for an elitist search heuristic to optimise each subfunction fi . Then by linearity of expectation, an upper bound on the expected runtime of an
elitist stochastic search heuristic for the unitation function is:
" r
#
r
X
X
E [T ] ≤ E
Ti =
E [Ti ] .
i=1

i=1

Hence, an upper bound on the total runtime for the unitation function may be achieved by
calculating upper bounds on the runtime for each block separately. Once these are obtained,
summing all the bounds yields an upper bound on the total runtime. Attention needs to be
put when calculating upper bounds on the runtime to overcome a plateau block when this is
followed by a gap block because points straight after the end of the plateau will have lower
fitness values, hence will not be accepted. In these special cases, the upper bound for the

6

Figure 4: A plateau unitation block of length m starting at position m + k and ending at position
k.

Figure 5: An illustration of how the search space of a unitation function may be subdivided into
blocks of the three kinds.
Plateau block needs to be multiplied by the upper bound for the Gap block to achieve a
correct upper bound on the runtime to overcome both blocks. In the remainder of the chapter
upper and lower bounds for each type of block will be derived as example applications of the
presented runtime analysis techniques. The reader, will then be able to calculate the runtime
of the (1+1) EA and other evolutionary algorithms for any such unitation function.
By simply using waiting time arguments it is possible to derive upper and lower bounds
on the runtime of the (1+1) EA for the Gap block. Assuming that the algorithm is at the
beginning of the gap block then to reach the end it is sufficient to flip m zero-bits into one-bits
and leave the other bits unchanged. On the other hand it is a necessary condition to flip at
least m zero-bits because all search points achieved by flipping less than m zero-bits have a
fitness value of zero and would not be accepted by selection. Given that there are m + k
zero-bits available at the beginning of the block, the following upper and lower bounds on the
probability of reaching the end of the block follows
! 
! 
m

m

m
m
(m + k)e
1
1
m+k
m+k
1
m+k
1
≤
≤p≤
≤
.
nm
e
m
n
e
m
n
nm
k

k
Here the outer inequalities are achieved by using nk
≤ nk ≤ en
for k ≥ 1. Then by
k
simple waiting time arguments, the expected time for the (1+1) EA to optimise a Gap block
of length m and position k is upper and lower bounded by
!−1
!−1

m

m
nm
m+k
m+k
nm
≤
nm ≤ E [T ] ≤ enm
≤e
.
(m + k)e
m
m
m+k

5

Tail Inequalities

The runtime of a stochastic search algorithm A for a function (class) f is a random variable
TA,f and the main goal of a runtime analysis is to calculate its expectation E [TA,f ]. Sometimes
the expected runtime may be particularly large, but there may also be a high probability that
the actual optimisation time is significantly lower. In these cases a result about the success
probability within t steps, helps considerably the understanding of the algorithm’s performance.
In other occasions it may be interesting to simply gain knowledge about the probability that
the actual optimisation time deviates from the expected runtime. In such circumstances tail

7

E [X]
Figure 6: The expectation of a random variable and its probability distribution. The tails are
highlighted in red.
inequalities turn out to be very useful tools by allowing to obtain bounds on the runtime
that hold with high probability. An example of the expectation of a random variable and its
probability distribution are given in Figure 6.
Given the expectation of a random variable, which often may be estimated easily, tail
inequalities give bounds on the probability that the actual random variable deviates from its
expectation [25, 24]. The most simple tail inequality is Markov’s inequality. Many strong tail
inequalities are derived from Markov’s inequality.
Theorem 1 (Markov’s Inequality). Let X be a random variable assuming only non-negative
values. Then for all t ∈ R+ ,
Pr(X ≥ t) ≤

E [X]
.
t

The power of the inequality is that no knowledge about the random variable is required
apart from it being non-negative.
Let X be a random variable indicating the number of bits flipped in one iteration of the
(1+1) EA. As seen in the previous section, one bit is flipped per iteration in expectation, i.e.,
E [X] = 1. One may wonder what is the probability that more than one bit is flipped in one
time step. A straightforward application of Markov’s Inequality reveals that in at least half
of the iterations either one bit is flipped or none:
Pr (X ≥ 2) ≤

E [X]
1
=
2
2

Similarly, one may want to gain some information on how many ones are contained in the
bitstring at initialisation, given that in expectation there are E [X] = n/2 (here X is a binomial
random variable with parameters n and p = 1/2). An application of Markov’s inequality yields
that the probability of having more than (2/3)n ones at initialisation is bounded by
Pr (X ≥ (2/3)n) ≤

E [X]
n/2
=
= 3/4
(2/3)n
(2/3)n

(1)

Since X is binomially distributed it is reasonable to expect that, for large enough n, the actual
number of obtained ones at initialisation would be more concentrated around the expected
value. In particular while the bound is obviously correct, the probability that the initial
bitstring has more than (2/3)n ones is much smaller than 3/4. However, to achieve such a
result more information about the random variable should be required by the tail inequality
(i.e., that it is binomially distributed). An important class of tail inequalities used in the
analysis of stochastic search heuristics are Chernoff bounds.
Theorem 2 (Chernoff Bounds).
variables taking
P Let X1 , X2 , . . . Xn be independent random
Pn
values in {0, 1}. Define X = n
X
,
which
has
expectation
E(X)
=
Pr(X
i
i = 1).
i=1
i=1
−E[X]δ 2

(a) Pr(X ≤ (1 − δ)E [X]) ≤ e 2
for 0 ≤ δ ≤ 1.

E[X]
eδ
(b) Pr(X > (1 + δ)E [X]) ≤ (1+δ)
for δ > 0.
1+δ
An application of Chernoff bounds reveals that the probability that the initial bitstring
has more
Pn than (2/3)n one-bits is exponentially small in the length of the bitstring. Let
X =
i=1 Xi be the random variable summing up the random values Xi of each of the n

8

Am
Am−1
..
.
Fitness
A3
A2
A1

Figure 7: A partition of the search space satisfying the conditions of an f -based partition.
bits. Since each bit is initialised with probability 1/2, it holds that Pr(Xi = 1) = 1/2 and
E [X] = n/2. By fixing δ = 1/3 it follows that (1 + δ)E [X] = (2/3)n and finally by applying
inequality (b),

n/2  n/2
e1/3
29
Pr(X > (2/3)n) ≤
<
30
(4/3)4/3
In fact an exponentially small probability of deviating from n/2 by a constant factor of the
search space c/n for any constant c > 0 may easily be obtained by Chernoff bounds.

6

Artificial Fitness Levels (AFL)

The artificial fitness levels technique is a very simple method to achieve upper bounds on the
runtime of elitist stochastic optimisation algorithms. Albeit its simplicity, it often achieves
very good bounds on the runtime.
The idea behind the method is to divide the search space of size 2n into m disjoint fitnessbased partitions A1 , . . . Am of increasing fitness such that f (Ai ) < f (Aj ) ∀i < j. The union of
these partitions should cover the whole search space and the level of highest fitness Am should
contain the global optimum (or all global optima if there is more than one).
Definition 3. A tuple (A1 , A2 , . . . , Am ) is an f -based partition of f : X → R if
1. A1 ∪ A2 ∪ · · · ∪ Am = X
2. Ai ∩ Aj = ∅ for i 6= j
3. f (A1 ) < f (A2 ) < · · · < f (Am )
4. f (Am ) = maxx f (x)
For functions of unitation, a natural way of defining a fitness-based partition is to divide
the search space into n + 1 levels, each defined by the number of ones in the bitstring. For the
Onemax function, where fitness increases with the number of ones in the bitstring, the fitness
levels would be naturally defined as Ai := {x ∈ {0, 1}n | Onemax(x) = i}.

6.1

AFL - Upper Bounds

Given a fitness-based partition of the search space, it is obvious that an elitist algorithm using
only one individual will only accept points of the search space that belong to levels of higher or
equal fitness to the current level. Once a new fitness level has been reached, the algorithm will
never return to previous levels. This implies that each fitness level has to be left at most once
by the algorithm. Since in the worst case all fitness levels are visited, the sum of the expected
times to leave all levels is an upper bound on the expected time to reach the global optimum.
The artificial fitness levels method simplifies this idea by only requiring a lower bound si on
the probability of leaving each level Ai rather than asking for the exact probabilities to leave
each level.

9

Theorem 4 (Artificial Fitness Levels). Let f : X → R be a fitness function, A1 . . . Am a
fitness-based partition of f and s1 . . . sm−1 be lower bounds on the corresponding probabilities
of leaving the respective fitness levels for a level of better fitness.
Then the expected runtime
P
of an elitist algorithm using a single individual is E [TA,f ] ≤ m−1
i=1 1/si .
The artificial fitness level method will now be applied to derive an upper bound on the
expected runtime of (1+1) EA for the Onemax function. Afterwards, the bound will be
generalised to general linear blocks of unitation.
Theorem 5. The expected runtime of the (1+1) EA on Onemax is O(n ln n).
Proof. The artificial fitness levels method will be applied to the n + 1 partitions defined by
the number of ones in the bitstring, i.e., Ai := {x ∈ {0, 1}n | Onemax(x) = i}. This means
that all bitstrings with i ones and n − i zeroes belong to fitness level Ai . For each level Ai , the
method requires a lower bound on the probability of reaching any level Aj where j > i. To
reach a level of higher fitness it is necessary to increase the number of ones in the bitstring.
However, it is sufficient to flip a zero into a one and leave the remaining bits unchanged. Since
the probability of flipping a bit is 1/n and there are n − i zeroes that may be flipped, a lower
bound on the probability to reach a level of higher fitness from level Ai is:

n−1
1
1
n−i
si ≥ (n − i) · · 1 −
≥
n
n
en
where (1−1/n)n−1 is the probability of leaving n−1 bits unchanged and the inequality follows
because (1 − 1/n)n−1 ≥ 1/e for all n ∈ N.
Then by the artificial fitness levels method (Theorem 4),

E T(1+1)

EA,Onemax



≤

m−1
X

n−1
X

1/si ≤

i=0

n
X
1
en
= en
= O(n ln n).
n−i
i
i=1

i=0

Theorem 6. The expected runtime of the (1+1)-EA for a linear block of length m ending at
position k is O(n ln((m + k)/k)).
Proof. Apply the artificial fitness levels method where each partition Ai consists of the bitstrings in the block with i zeroes. Then the probability of leaving a fitness level is bounded
by si ≥ i/n · (1 − 1/n)n−1 ≥ i/en. Given that at most m fitness levels need to be left and that
the block starts at position m + k and ends at position k, by Theorem 4 the expected runtime
is:
!


k+m
k+m
k+m
k
X en
X 1
X 1 X
1
m+k
E [T ] ≤
≤ en
≤ en
−
≤ en ln
i
i
i
i
k
i=1
i=1
i=k+1

6.2

i=k+1

AFL - Lower Bounds

Recently Sudholt introduced an artificial fitness levels method to obtain lower bounds on the
runtime of stochastic search algorithms [35]. Since lower bounds are aimed for, apart from
the probabilities of leaving each fitness level, the method needs to also take into account the
probability that some levels may be skipped by the algorithm.
Theorem 7. Consider a fitness function f : X → R and A1 . . . Am a fitness-based partition
of f . Let ui be the probability of starting in level Ai , si be an upper bound on the probability
of leaving Ai and pi,j be an upper bound on the probability of jumping from level Ai to level
Aj . If there exists some 0 < χ ≤ 1 such that for all j > i
pi,j ≥ χ ·

m−1
X

pi,k ,

k=j

then the expected runtime of an elitist algorithm using a single individual is
E [TA,f ] ≥ χ ·

m−1
X
i=1

10

ui

m−1
X
j=i

1
sj

The method will first be illustrated for the (1+1) EA on the Onemax function. Afterwards,
the result will be generalised to general linear blocks of unitation.
Theorem 8. The expected runtime of the (1+1) EA on Onemax is Ω(n ln n).
Proof. Apply the artificial fitness levels method on the n+1 partitions defined by the number of
ones in the bitstring, i.e., Ai := {x ∈ {0, 1}n | Onemax(x) = i}. This means that all bitstrings
with i ones and n − i zeroes belong to fitness level Ai . To apply the artificial fitness levels
method, bounds on si and χ need to be derived. An upper bound on the probability of leaving
fitness level Ai is simply si ≤ (n−i)/n because it is a necessary condition that at least one zero
flips to reach a better fitness level. The bound follows because each bit flips with probability
1/n and there are n − i zeroes available to be flipped. In order to obtain
P an upper bound on χ,
the method requires a lower bound on pi,j and an upper bound on m−1
k=j pi,k . For the lower
bound on pi,j notice that in order to reach level Aj , it sufficient to flip j − i zeroes out of the
n − i zeroes available and leave all the other bits unchanged. Hence the following bound is
obtained:
! 
n−(j−i)
j−i 
n−i
1
1
pij ≥
1−
j−i
n
n
For an upper bound on the sum, notice that to reach any level Ak k ≥ j from level Ai it is
necessary to flip at least j − i zeroes out of the n − i available zeroes. So,
! 
n−1
j−i
X
n−i
1
pi,k ≤
j−i
n
k=j

and for χ := 1/e the condition of Theorem 7 is satisfied as follows:
pi,j ≥

n−(j−i) n−1

n−1
X
X
1
·
1−
pi,k ≥ χ ·
pi,k
n
k=j

k=j

By Eq. (1), the probability that the initial search point has less than (2/3)n 1-bits is at
least
(2/3)n

X

ui ≥ 1 −

i=1

3
4

The statement of Theorem 7 now yields
  n−1
X n−1
X 1
1
E [TA,f ] ≥
·
ui
e
sj
i=1
j=i


 
(2/3)n
n−1
X
X
1
>
·
ui 
e
i=1

j=(2/3)n

  

1
3
≥
· 1−
e
4

n−1
X
j=(2/3)n

1
sj

n
n−j

n/3
n X
1
≥
·
.
4e
j
j=1

It now follows that E [TA,f ] = Ω(n log n).
Similarly the following result may also be proved for linear blocks of unitation functions
by defining the fitness partitions as Ai := {x : n − |x| = k + m − i} for 0 ≤ i ≤ m.
Theorem 9. The expected runtime of the (1+1)-EA for a linear block of length m ending at
position k is Ω(n ln((m + k)/k)).

11

6.3

Level-based analysis of non-elitist populations

A weakness with the classical artificial fitness level technique is that it is limited to search
heuristics that only keep one solution, such as the (1+1) EA, and it heavily relies on the
selection mechanism to use elitism. [4] recently introduced the so-called level-based analysis,
a generalisation of fitness level theorems for non-elitist evolutionary algorithms which is also
applicable to search heuristics with populations, and using higher arity operators such as
crossover.
Their theorem applies to any algorithm that can be expressed in the form of Algorithm 3,
such as genetic algorithms [4] and estimation of distribution algorithms UMDA [7]. The
main component of the algorithm is a random operator D which given the current population
Pt ∈ X λ returns a probability distribution D(Pt ) over the search space X . The next population
Pt+1 is obtained by sampling individuals independently from this distribution.

Algorithm 3 Population-based algorithm with independent sampling
1: Initialisation:
t ← 0; Initialise Pt uniformly at random from X λ .
2: Variation and Selection:
3: for i = 1 . . . λ do
Sample Pt+1 (i) ∼ D(Pt )
4: end for
5: t ← t + 1; Continue at 2
In contrast to classical fitness-level theorems, the level-based theorem (Theorem 10) only
assumes a partition (A1 , . . . , Am+1 ) of the search space X , and not an f -based partition
Sm+1 (see
Definition 3). Each of the sets Aj , j ∈ [m+1] is called a level, and the symbol A+
:=
j
i=j+1 Ai
denotes the set of search points above level Aj . Given a constant γ0 ∈ (0, 1), a population
+
P ∈ X λ is considered to be at level Aj with respect to γ0 if |P ∩A+
j−1 | ≥ γ0 λ and |P ∩Aj | < γ0 λ
meaning that at least a γ0 fraction of the population is in level Aj or higher.
Theorem 10 ([4]). Given any partition of a finite set X into m non-overlapping subsets
(A1 , . . . , Am+1 ), define T := min{tλ | |Pt ∩ Am+1 | > 0} to be the first point in time that
elements of Am+1 appear in Pt of Algorithm 3. If there exist parameters z1 , . . . , zm , z∗ ∈ (0, 1],
δ > 0, and a constant γ0 ∈ (0, 1) such that for all j ∈ [m], P ∈ X λ , y ∼ D(P ) and γ ∈ (0, γ0 ]
it holds

+
(C1) Pr y ∈ A+
j | |P ∩ Aj−1 | ≥ γ0 λ ≥ zj ≥ z∗

+
+
(C2) Pr y ∈ A+
j | |P ∩ Aj−1 | ≥ γ0 λ and |P ∩ Aj | ≥ γλ ≥ (1 + δ)γ, and


16m
δ 2 γ0
2
with a =
, ε = min{δ/2, 1/2} and c = ε4 /24
(C3) λ ≥ ln
a
acεz∗
2(1 + δ)
then
!
m
X
2
1
E [T ] ≤
mλ(1 + ln(1 + cλ)) +
.
cε
zj
j=1
The theorem provides an upper bound on the expected optimisation time of Algorithm 3
if it is possible to find a partition (A1 , . . . , Am+1 ) of the search space X and accompanying
parameters γ0 , δ, z1 , . . . , zm , z∗ such that conditions (C1), (C2), and (C3) are satisfied. Condition (C1) requires a non-zero probability zj of creating an individual in level Aj+1 or higher
if there are already at least γ0 λ individuals in level Aj or higher. In typical applications,
this imposes some conditions on the variation operator. The condition is analogous to the
probability sj in the artificial fitness level technique. Condition (C2) requires that if in addition there are γλ individuals at level Aj+1 or better, then the probability of producing an
individual in level Aj+1 or better should be larger than γ by a multiplicative factor 1 + δ. In
typical applications, this imposes some conditions on the strength of the selective pressure in
the algorithm. Finally, condition (C3) imposes minimal requirements on the population size
in terms of the parameters above.
As an example application of the level-based theorem, the (µ, λ) EA is analysed, which is
the non-elitist variant of the (µ + λ) EA shown in Algorithm 1. The two algorithms differ in
the selection step (line 6) where the new population Pt+1 in (µ, λ) EA is chosen as the best µ
individuals out of {y1 , . . . , yλ } and breaking ties uniformly at random. While the (µ + λ) EA

12

always retains the best µ individuals in the population (hence the name elitist), the (µ, λ) EA
always discards the old individuals x(1) , . . . , x(µ) .
At first sight, it may appear as if the (µ, λ) EA cannot be expressed in the form of Algorithm
3. The µ individuals x(1) , . . . , x(µ) that are kept in each generation are not independent due to
the inherent sorting of the offspring. However, taking a different perspective, the population
of the algorithm at time t could also be interpreted as the λ offspring y (1) , . . . , y (λ) . In this
alternative interpretation, the new population is now created by sampling uniformly at random
among the µ best individuals in the population, and applying the mutation operator. The
operator D in Algorithm 3 can now be defined as in Algorithm 4.

Algorithm 4 Operator D corresponding to (µ, λ) EA
1: Selection:
Sort the population Pt = (y (1) , . . . , y (λ) ) such that f (y (1) ) ≥ f (y (2) ) ≥ . . . ≥ f (y (λ) ).
Select x uniformly at random among {y (1) , . . . , y (µ) }.
2: Variation (mutation):
Create x0 by flipping each bit in x with probability χ/n.
3: return x0
The following lemma will be useful when estimating the probability that the mutation
operator does not flip any bit positions.
Lemma 11. For any δ ∈ (0, 1) and χ > 0, if n ≥ (χ + δ)(χ/δ) then

χ n
1−
≥ (1 − δ)e−χ .
n
Proof. Note first that ln(1 − δ) < −δ, hence


n
nδ
− 1 (χ − ln(1 − δ)) ≥ n +
− (χ + δ) ≥ n.
χ
χ
By making use of the fact that (1 − 1/x)x−1 ≥ 1/e and simplifying the exponent n as above


1−


χ−ln(1−δ)
χ (n/χ)−1
χ n
≥ 1−
≥ (1 − δ)e−χ .
n
n

The expected optimisation time of the (µ, λ) EA on Onemax can now be expressed in
terms of the mutation rate χ/n and the problem size n assuming some constraints on the
population sizes µ and λ. The theorem is valid for a wide range of mutation rates χ/n. In the
classical setting of χ = 1, the expected optimisation time reduces to O(nλ ln λ).
Theorem 12. The expected optimisation time of the (µ, λ) EA with bitwise mutation rate
χ/n where χ ∈ (0, n/2), and population sizes µ and λ satisfying for any constant δ ∈ (0, 1)




24576n(n + 1)
λ
1+δ
4
≥
eχ ,
and λ ≥ 2 χ ln
µ
1−δ
δ e
δ7 χ
on Onemax is for any n ≥ (χ + δ)/(χ/δ) no more than


eχ ln(n + 2)
1536n
λ
ln(λ)
+
+ O(nλ).
δ5
χ(1 − δ)
Proof. Apply the level-based theorem with the same m := n + 1 partitions as in the proof of
Theorem 8. Since the parameter δ is assumed to be some constant δ ∈ (0, 1), it also holds
that the parameters a, ε, and c are positive constants. The parameters γ0 , z1 , . . . , zm , and z∗
will be chosen later.
To verify that conditions (C1) and (C2) hold for any j ∈ [m], it is necessary to estimate
the probability that operator D produces a search point x0 with j + 1 one-bits when applied
to a population P containing at least γ0 λ individuals, each having at least j one-bits (formally
|P ∩ A+
j−1 | ≥ γ0 λ). Such an event is called a successful sample.
Condition (C1) asks for bounds zj for each j ∈ [m] on the probability that the search
point x0 returned by Algorithm 4 contains j + 1 one-bits. First chose the parameter setting
γ0 := µ/λ. This parameter setting is convenient, because the selection step in Algorithm 4

13

always picks an individual x among the best µ = γ0 λ individuals in the population. By the
assumption that |P ∩ A+
j−1 | ≥ γ0 λ, the algorithm will always select an individual x containing
at least j + i one-bits for some non-negative integer i ≥ 0.
Assume without loss of generality, that the first j bit-positions in the selected individual
x are one-bits, and let k, j < k ≤ n, be any of the other bit positions. If there is a zero-bit in
position k or if i ≥ 2, then a successful sample occurs if the mutation operator flips only bit
position k. If there is a one-bit in position k, and if i = 1, then the step is still successful if
the mutation operator flips none of the bit positions. Since the probability of not flipping a
position is higher than the probability of flipping a position, i.e., 1−χ/n ≥ χ/n, the probability
of a successful sample is therefore in both cases at least
(n − j)(χ/n)(1 − χ/n)n−1 .

(2)

By Lemma 11, the probability above is at least zj := (n − j)(χ/n)e−χ (1 − δ). The parameter
z∗ is chosen to be the minimal among these probabilities, i.e. z∗ := (χ/n)e−χ (1 − δ).
Condition (C2) assumes in addition that γλ < µ individuals have fitness j + 1 or higher.
In this case, it suffices that the selection mechanism picks one of the best γλ individuals
among the µ individuals, and that none of the bits are mutated in the selected individual.
The probability of this event is at least
γλ
γλ −χ
(1 − χ/n)n ≥
e (1 − δ)
µ
µ
Hence, to satisfy condition (C2), it suffices to require that
γλ
exp(−χ)(1 − δ) ≥ γ(1 + δ),
µ
which is true whenever
λ
≥
µ



1+δ
1−δ



eχ .

To check condition (C3), notice that ε = δ/2, and c = δ 4 /384, hence
a=
acεz∗ ≥

δ 2 (λ/µ)
δ 2 eχ
≥
, and
2(1 + δ)
2(1 − δ)
δ2 χ
δ7 χ
cε =
2n
1536n

Condition (C3) is now satisfied, because the population size λ is required to fulfil




4(1 − δ)
2
16m
24576mn
ln
≤
ln
≤λ
a
acεz∗
δ 2 eχ
δ7 χ
All conditions are satisfied, and the theorem follows.

6.4

Conclusions

The artificial fitness levels method was first described by Wegener [37]. The original method
was designed for the achievement of upper bounds on the runtime of stochastic search heuristics
using only one individual such as the (1+1) EA. Since then, several extensions of the method
have been devised for the analysis of more sophisticated algorithms. Sudholt introduced the
method presented in Section 7 for the obtainment of lower bounds on the runtime [35]. In
an early study, [38] used a potential function that generalises the fitness level argument of
[37] to analyse the (µ+1) EA. His analysis achieved tight upper bounds on the runtime of the
(µ+1) EA on LeadingOnes and Onemax by waiting for a sufficient amount of individuals
of the population to take over a given fitness level Ai before calculating the probability to
reach a fitness level of higher fitness. Chen et al. extended the analysis to offspring populations by analysing the (N +N ) EA, also taking into account the take over process [2]. Lehre
introduced a general fitness-level method for arbitrary population-based EAs with non-elitist
selection mechanisms and unary variation operators [20]. This technique was later generalised
further into the level-based method presented in Section 6.3 [4]. The method allows the analysis of sophisticated non-elitist heuristics such as genetic algorithms equipped with mutation,
crossover and stochastic selection mechanisms, both for classical as well as noisy and uncertain
optimisation [6].

14

Figure 8: An illustration of the drift ∆ at time step k of a process represented by the random
variable X and a distance function d.

7

Drift Analysis

Drift analysis is a very flexible and powerful tool that is widely used in the analysis of stochastic
search algorithms. The high level idea is to predict the long term behaviour of a stochastic
process by measuring the expected progress towards a target in a single step. Naturally, a
measure of progress needs to be introduced, which is generally called a distance function. Given
a random variable Xk representing the current state of the process at step k, over a finite set
of states S, a distance function d : S → R+
0 is defined such that d(Xk ) = 0 if and only if Xk
is a target point (e.g., the global optimum). Drift analysis aims at deriving the expected time
to reach the target by analysing the decrease in distance in each step, i.e., d(Xk+1 ) − d(Xk ).
The expected value of this decrease in distance, ∆k = E [d(Xk+1 ) − d(Xk ) | Xk ] is called the
drift. See Figure 8 for an illustration. If the initial distance from the target is d(X0 ) and a
bound on the drift ∆ (i.e., the expected improvement in each step) is known, then bounds on
the expected runtime to reach the target may be derived.

7.1

Additive Drift Theorem

The additive drift theorem was introduced to the field of evolutionary computation by He
and Yao [12]. The theorem allows to derive both upper and lower bounds on the runtime of
stochastic search algorithms. Consider a distance function Yk = d(Xk ) indicating the current
distance, at time k, of the stochastic process from the optimum. The theorem simply states
that if at each time step k, the drift is at least some value −ε (i.e., the process has moved
closer to the target) then the expected number of steps to reach the target is at most Y0 /ε.
Conversely if the drift in each step is at most some value −ε, then the expected number of
steps to reach the target is at least Y0 /ε.
Theorem 13 (Additive Drift Theorem). Given a stochastic process X1 , X2 , . . . over an interval [0, b] ⊂ R and a distance function d : S → R+
0 such that d(Xk ) = 0 if and only if X
contains the target. Let Yk = d(Xk ) for all k, define T := min{k ≥ 0 | Yk = 0}, and assume
E [T ] < ∞.
Verify the following conditions:
(C1+) ∀k

E [Yk+1 − Yk | Yk > 0] ≤ −ε

(C1−) ∀k

E [Yk+1 − Yk | Yk > 0] ≥ −ε

Then,
1. If (C1+) holds for an ε > 0, then E [T | Y0 ] ≤ b/ε.
2. If (C1−) holds for an ε > 0, then E [T | Y0 ] ≥ Y0 /ε.
An Example application of the additive drift theorem follows concerning the (1+1) EA for
plateau blocks of functions of unitation of length m positioned such that k > n/2 + εn.
Theorem 14. The expected runtime of the (1+1)-EA for a plateau block of length m ending
at position k > n/2 + εn is Θ(m).
Proof. The additive drift theorem will be applied to derive both upper and lower bounds
on the expected runtime. The starting point is a bitstring X0 with m + k zeroes and the
target point is a bitstring Xt with k zeroes. Choose to use the natural distance function

15

ε

Yk = d(Xk )

0

b

Figure 9: An illustration of the condition of the Additive Drift Theorem. If the expected distance
to the optimum decreases of at least ε at each step (i.e., condition C1+), then an upper bound on
the runtime is achieved. If the distance decreases of at most ε at each step (i.e., condition C1-),
then a lower bound on the runtime is obtained.
Yt = d(Xt ) := n − |Xt | that counts the number of zeroes in the bitstring. Subtract k from
the distance such that target points with k zeroes have distance 0 and the initial point has
distance m. As long as points on the plateau are generated, they will be accepted because all
plateau points have equal fitness. Given that each bit flips with probability 1/n, and at each
step the current search point has Yt zeroes and n − Yt ones, the drift is
∆t := E [Yt − Yt+1 | Yt > 0] =

Yt
n − Yt
2 · Yt
−
=
−1
n
n
n

A lower bound on the drift is obtained by considering that as long as the end of the plateau
has not been reached there are always at least k zeroes that may be flipped (i.e., Yt ≥ k).
Accordingly for an upper bound, at most m + k zeroes may be available to be flipped (i.e.,
Yt ≤ m + k). Hence,
2(m + k)
2k
− 1 ≤ ∆t ≤
−1
n
n
Then by additive drift analysis (Theorem 13),
E [T | Y0 ] ≤

m
mn
=
= O(m)
(2k)/n − 1
2k − n

and

m
mn
=
= Ω(m)
2(m + k)/n − 1
2(m + k) − n
where the last equalities hold as long as k > n/2 + εn.
E [T | Y0 ] ≥

Note again that if the plateau block is followed by a gap block, then an upper bound
on the expected time to optimise both blocks is achieved by multiplying the upper bounds
obtained for each block. This is necessary because points in the gap will not be accepted by
the (1+1) EA.

7.2

Multiplicative Drift Theorem

In the additive drift theorem the worst case decrease in distance is considered. If the expected
decrease in distance changes considerably in different areas of the search space, then the
estimate on the drift may be too pessimistic for the obtainment of tight bounds on the expected
runtime.
Drift analysis of the (1+1) EA for the classical Onemax function will serve as an example
of this problem. Since the global optimum is the all-ones bitstring and the fitness increases
with the number of ones a natural distance function is Yt = d(Xt ) = n − Onemax(Xt ) which
simply counts the number of zeroes in the current search point. Then the distance will be zero
once the optimum is found. Points with less one-bits than the current search point will not be
accepted by the algorithm because of their lower fitness. So the drift is always positive, i.e.,
∆t ≥ 0 and the amount of progress is the expected number of ones gained in each step. In
order to find an upper bound on the runtime, a lower bound on the drift is needed (i.e., the
worst case improvement). Such worst case occurs when the current search point is optimal
except for one 0-bit. In this case the maximum decrease in distance that may be achieved in
a step is Yt − Yt+1 = 1 and to achieve such progress it is necessary that the algorithm flips the
zero into a one and leaves the other bits unchanged. Hence, the drift is

n−1
1
1
1
1−
≥
:= ε
∆t ≥ 1 ·
n
n
en

16

Since the expected initial distance is E [Y0 ] = n/2 due to random initialisation, the drift
theorem yields
E [Y0 ]
n/2
E [T | Y0 ] ≤
=
= e/2 · n2 = O(n2 )
ε
1/(en)
In Section 6 it was proven that the runtime of the (1+1) EA for Onemax is Θ(n ln n), hence
a bound of O(n2 ) is not tight. The reason is that on functions such as Onemax the amount
of progress made by the algorithm depends crucially on the distance from the optimum. For
Onemax in particular, larger progress per step is achieved when the current search point
has many zeroes that may be flipped. As the algorithm approaches the optimal solution
the amount of expected progress in each step becomes smaller because search points have
increasingly more one-bits than zero-bits in the bitstring. In such cases a distance function
that takes into account these properties of the objective function needs to be used. For
Onemax a correct bound is achieved by using a distance function that is logarithmic in the
number of zeroes i, i.e., Yt = d(Xt ) := ln(i + 1) where a 1 is added to i in the argument of the
logarithm such that the global optimum has distance zero (i.e., ln(1) = 0). With such distance
measure, the decrease in distance when flipping a zero and leaving the rest of the bitstring
unchanged is


1
1
ln(i + 1) − ln(i) = ln 1 +
≥
i
2i
where the last inequality holds for all i ≥ 1. Since it is sufficient to flip a zero and leave
everything else unchanged to obtain an improvement, the drift is
i
1
1
·
=
:= ε
en 2i
2en
Given that the maximum possible distance is Y0 ≥ ln(n + 1), the drift theorem yields
∆t ≥

E [T ] ≤

Y0
= 2en · ln(n + 1) = O(n ln n).
1/(2en)

The multiplicative drift theorem was introduced as a handy tool to deal with situations
as the one described above where the amount of progress depends on the distance from the
target.
Theorem 15 (Multiplicative Drift Theorem [8]). Let {Xt }t∈N0 be random variables describing
a Markov process over a finite state space S ⊆ R. Let T be the random variable that denotes
the earliest point in time t ∈ N0 such that Xt = 0. If there exist δ, cmin , cmax > 0 such that for
all t < T ,
1. E [Xt − Xt+1 | Xt ] ≥ δXt and
2. cmin ≤ Xt ≤ cmax ,
then



2
cmax
· ln 1 +
δ
cmin
The following derivation of an upper bound on the runtime of the (1+1) EA for linear
blocks illustrates the multiplicative drift theorem.
E [T ] ≤

Theorem 16. The expected time for the (1+1)-EA to optimise a linear unitation block of
length m ending at position k is O(n ln((m + k)/k))
Proof. Let Xt be the number of zero-bits in the bitstring at time step t, representing the
distance from the end of the linear block. By remembering that increases in distance are not
accepted due to elitism, the expected decrease in distance at time step can be bounded by


Xt
1
E [Xt+1 |Xt ] ≤ Xt − 1 ·
= Xt 1 −
en
en
simply by considering that if a zero-bit is flipped and nothing else then the distance decreases
by 1. Then the drift is:


1
1
E [Xt − Xt+1 |Xt ] ≥ Xt − Xt 1 −
=
Xt := δXt
en
en
By fixing k = cmin ≤ Xt ≤ cmax = m + k the multiplicative drift theorem yields


2
cmax
E [T ] ≤ · ln 1 +
= 2en ln(1 + (m + k)/k) = O(n ln((m + k)/k))
δ
cmin

17

By fixing 1 = cmin ≤ Xt ≤ cmax = n an O(n ln n) bound on the expected runtime of the
(1+1) EA for Onemax is achieved.

7.3

Variable Drift Theorem

The multiplicative drift theorem is applicable when the drift of a stochastic process is linear
with respect to the current position. However, in some stochastic processes, the drift is nonlinear in the current position, i.e.,
E [Xt − Xt+1 | Xt ≥ xmin ] ≥ h(Xt )

(3)

for some function h. The following variable drift theorem provides bounds on the expectation
and the tails of the hitting time distribution of such processes, given some assumptions about
the function h.
Theorem 17 (Corollary 1 in [22]). Let (Xt )t≥0 , be a stochastic process over some state space
S ⊆ {0} ∪ [xmin , xmax ], where xmin ≥ 0. Let h : [xmin , xmax ] → R+ be a differentiable function.
Then the following statements hold for the first hitting time T := min{t | Xt = 0}.
(i) If E [Xt − Xt+1 | Xt ≥ xmin ] ≥ h(Xt ) and h0 (x) ≥ 0, then
Z X0
xmin
1
E [T | X0 ] ≤
+
dy.
h(xmin )
xmin h(y)
(ii) If E [Xt − Xt+1 | Xt ≥ xmin ] ≤ h(Xt ) and h0 (x) ≤ 0, then
Z X0
1
xmin
+
dy.
E [T | X0 ] ≥
h(xmin )
h(y)
xmin
(iii) If E [Xt − Xt+1 | Xt ≥ xmin ] ≥ h(Xt ) and h0 (x) ≥ λ for some λ > 0, then



Z X0
xmin
1
Pr (T ≥ t | X0 ) < exp −λ t −
−
dy
.
h(xmin )
xmin h(y)
(iv) If E [Xt − Xt+1 | Xt ≥ xmin ] ≤ h(Xt ) and h0 (x) ≤ −λ for some λ > 0, then


Z X0
eλt − eλ
λxmin
λ
Pr (T < t | X0 > 0) < λ
exp −
−
dy .
e −1
h(xmin )
xmin h(y)
To illustrate the variable drift theorem, an upper bound on the optimisation time of the
(1+1) EA on the class of linear functions with bounded coefficients will be derived. More
formally, this class of functions contains any function of the form
f (x) :=

n
X

wi xi ,

i=1

with bounded, positive coefficients w1 , . . . , wn ∈ (wmin , wmax ) where 0 < wmin < wmax .
The drift function h in this example turns out to be linear, hence the multiplicative drift
theorem could have been applied instead.
Theorem 18. The expected optimisation time of the (1+1) EA on linear functions is less
than t(n) := en(ln(n) + ln(wmax /wmin ) + 1), and the probability that the optimisation time
exceeds t(n) + ren for any r ≥ 0 is no more than e−r .
Proof. Define the distance Xt at time k to be the function value that “remains” at time k,
i.e.,
!
!
n
n
n


X
X
X
(t)
(t)
Xt :=
wi −
wi xi
=
wi 1 − xi
,
i=1

i=1

i=1

(t)

where xi is the i-th bit in the current search point at time t. For any i ∈ [n], assume that the
mutation operator flipped only bit position i, and no other bit positions, an event denoted by
(t)
the symbol Ei . If xi = 0, then bit position i flipped from 0 to 1 and the distance reduced by
(t)
wi . Otherwise, if xi = 1, then bit position i flipped from 1 to 0, the new search point was not
(t)
accepted, and the distance reduced by 0. Hence, the distance always reduces by wi (1 − xi )

18

drift away from target
target

a

b
no large jumps
towards target

start

Figure 10: An illustration of the two conditions of the Negative-Drift Theorem.
when event Ei occurs. Using the law of total probability, and noting that the distance can
never increase, one obtains
E [Xt − Xt+1 | Xt = r] ≥

n
X

Pr (Ei | Xt = r) E [Xt − Xt+1 | Ei ∧ Xt = r]

i=1

≥

 
n−1 X
n


1
1
r
(t)
.
1−
wi 1 − xi
≥
n
n
en
i=1

Therefore E [Xt − Xt+1 | Xt ] ≥ h(Xt ) for the function h(x) = x/en which has derivative
h0 (x) = 1/en. By Theorem 17 part (i), it follows that
Z X0
xmin
1
E [T | X0 ] ≤
+
dy
h(xmin )
h(y)
x
Z min
nwmax
wmin
en
=
+
dy
h(wmin )
y
wmin
= en + en(ln(nwmax ) − ln(wmin ))
= en(ln(n) + ln(wmax /wmin ) + 1) =: t(n).
Furthermore, Theorem 17 part (iii) with λ := 1/en gives for any r ≥ 0
Pr (T ≥ t(n) + enr) ≤ e−r .

7.4

Negative-Drift Theorem

The drift theorems presented in previous subsections are designed to prove polynomial bounds
on the runtime of stochastic search algorithms. For this a positive drift towards the optimum
is required. On the other hand, a negative drift indicates that the stochastic process moves
away from the optimum in expectation at each step. In such a case it is unlikely that the
algorithm is efficient for the function it is attempting to optimise. Rather, an exponential
lower bound on the runtime could probably be proved. The negative-drift theorem is the
standard technique used for the purpose.
Apart from a negative drift, the theorem also requires a second condition showing that
large jumps are unlikely. The intuitive reason for this second condition is that if large jumps
were possible, then the algorithm could maybe be able to jump to the optimum even if in
expectation it is drifting away. For technical reasons also large jumps heading away from the
optimum need to be excluded (see [30]).
Theorem 19 (Negative-Drift Theorem). Let Xt , t ≥ 0 be the random variables describing
a Markov process over the state space S and denote the increase in distance in one step
Dt (i) := (Xt+1 − Xt |Xt = i) for i ∈ S and t ≥ 0. Suppose there exists an interval [a, b] of the
state space and three constants δ, ε, r > 0 such that for all t ≥ 0 the following conditions hold:
1. ∆t (i) = E [Dt (i)] ≥ ε for a < i < b
2. Pr (|Dt (i)|) = j) ≤

1
(1+δ)j−r

for i > a and j ≥ 1

Then there exists a constant c∗ such that for T := min{t ≥ 0 : Xt ≤ a|X0 ≥ b} it holds
∗
P r(T ≤ 2c (b−a) ) = 2−Ω(b−a) .
The following theorem is an example application showing exponential runtime of the
(1+1) EA for the Needle function.

19

Theorem 20. Let η > 0 be constant. Then there is a constant c > 0 such that with probability
1 − 2−Ω(n) the (1+1) EA on Needle creates only search points with at most n/2 + ηn ones
in 2cn steps.
Proof. Apply the negative-drift theorem and set the interval [a, b] as a := n/2 − 2γn zeroes
and b := n/2 − γn zeroes, with γ a positive constant. By Chernoff bounds the probability
that the initial random search point has less than n/2 − γn zeroes is e−Ω(n) , implying that the
algorithm starts outside the interval [a, b] as desired. The remainder of the proof shows that
the two conditions of the drift theorem hold.
Since the interval is a plateau, all created points have the same fitness and are accepted.
Given that the current search point has i zeroes and that each bit is flipped with probability
1/n, the drift is
n−i
i
n − 2i
∆t (i) =
− =
≥ 2γ := ε
n
n
n
where the last inequality is achieved because in the interval there are always at least b zeroes,
i.e., i ≥ n/2 − γn. Concerning the second condition for standard bit mutation, the probability
of flipping j bits decreases exponentially with the number of bits j
! 
 j j
 j−1
j
n
1
n
1
1
Pr (|∆t (i)| ≥ j) ≤
≤
≤
≤
j
n
j!
j!
2
and the condition holds for δ = r = 1. By the negative drift theorem the optimum is found
within 2c∗(b−a) = 2cn steps with probability at most 2−Ω(b−a) = 2−Ω(n) .
The proof can be generalised to plateau blocks of functions of unitation positioned such
that k + m < (1/2 − ε)n.
Theorem 21. The time for the (1+1) EA to optimise a plateau block of length m at position
such that k + m < (1/2 − ε)n is at least 2Ω(m) with probability at least 1 − 2−Ω(m) .
Proof. The proof follows the same arguments as the proof of Theorem 20 by setting b := m + k
zeroes and a := k zeroes.

7.5

Conclusions

Drift analysis dates back to 1892 when it was applied for the analysis of stability equilibria in
ordinary differential equations [23]. The first use of drift techniques for the runtime analysis
of stochastic search heuristics was performed by Sasaki and Hajek to analyse simulated annealing on instances of the maximum matching problem [34]. Drift analysis was applied in a
considerable number of applications in evolutionary computation after He and Yao introduced
the additive drift technique to the field [12]. Several extensions for the analysis of more sophisticated algorithms and processes have been since devised. The multiplicative drift method
introduced in Section 7.2 is due to Doerr et al. [8]. An improved version introduced by Doerr
and Goldberg allows to derive bounds also on the probability to deviate from the expected
runtime. Witt recently introduced a multiplicative drift theorem to achieve lower bounds on
the runtime [39]. While the multiplicative drift theorem may only be used when the drift is
linear, a variable drift theorem was introduced to deal with cases where the expected progress
is non-linear [18] with respect to the current position. A general variable drift theorem with
tail bounds was introduced in [22]. This theorem subsumes most existing drift theorems, and
a special case of this theorem was given in Section 7.3 (see Theorem 17).
Oliveto and Witt proposed the negative-drift theorem presented in Section 7.4 to derive
exponential lower bounds on the runtime of randomised search heuristics [29]. This theorem
was the main tool used in the first analysis of the standard simple genetic algorithm (SGA)
[31, 32]. Finally, Lehre extended the negative drift theorem to allow a systematic analysis of
population-based heuristics using non-elitist selection mechanisms [19].

8

Final Overview

This chapter has presented the most commonly used techniques for the time complexity analysis of stochastic search heuristics. Example applications have been shown concerning simple
evolutionary algorithms on classical test problems. The same techniques have allowed the obtainment of time complexity results on more sophisticated function classes, such as standard

20

combinatorial optimisation problems. The reader is referred to [27] for an overview of such advanced results concerning evolutionary algorithms and ant colony optimisation. Several other
techniques have been used to analyse stochastic search heuristics, such as typical runs, family
trees, martingales, probability generating functions and branching processes. For an introduction to these tools for the analysis of evolutionary algorithms, the reader is referred to a recent
extensive monograph [14] which covers a more extensive set of techniques than is possible
in this book chapter. Apart from EAs and ACO for discrete single-objective optimisation,
several other aspects of stochastic search optimisation have been investigated theoretically,
such as simulated annealing, evolution strategies for continuous optimisation, particle swarm
optimisation, memetic algorithms, and multi-objective optimisation techniques. These topics
are overviewed in [1]. Significant results have been achieved recently that have not yet been
covered in monographs and edited book collections. Amongst these, certainly worth mentioning are the recent considerable advances in black box optimisation [21, 9], which may be
regarded as a complementary line of research to runtime analysis. Rather than determining
the time required by a given heuristic for a problem class, black box optimisation focuses on
determining the best possible performance achievable by any search heuristic for that class
of problems. A recent interesting variation to classical runtime analysis is to determine the
expected solution quality achieved by a stochastic search heuristic if it is only allowed a predefined budget [17]. Fixed budget computation analyses are driven by the consideration that in
practical applications only a predefined amount of resources are available and the hope is to use
such resources at best to achieve solutions of the highest quality. Recent years have witnessed
considerable advances in the theory of artificial immune systems (AISs). Results concerning
standard AISs, such as the B-Cell algorithm, for classical combinatorial optimisation problems have appeared [15, 16] together with analyses of sophisticated AIS operators such as
stochastic ageing mechanisms [28]. Complexity analyses of parallel evolutionary algorithms
[36] and genetic programming [26] have also recently appeared. Finally, systematic work has
been carried out in unifying theories of evolutionary algorithms and population genetics [33].

9

Acknowledgement

The research leading to these results has received funding from the European Union Seventh
Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE) and by
the EPSRC under grant agreement no EP/M004252/1 (RIGOROUS).

References
[1] A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics. World Scientific
Review, 2011.
[2] T. Chen, J. He, G. Sun, G. Chen, and X. Yao. A new approach for analyzing average time
complexity of population-based evolutionary algorithms on unimodal problems. IEEE
transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the
IEEE Systems, Man, and Cybernetics Society, 39(5):1092–106, Oct. 2009.
[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms.
MIT Press, 2001.
[4] D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre. Level-based analysis of genetic
algorithms and other search processes. In Proceedings of the 13th International Conference
on Parallel Problem Solving from Nature (PPSN XI), volume 8672 of Lecture Notes in
Computer Science, pages 912–921. Springer, 2014.
[5] D. Corus, J. He, T. Jansen, P. E. Oliveto, D. Sudholt, and C. Zarges. On easiest functions
for somatic contiguous hypermutations and standard bit mutations. In Proceedings of the
2015 conference on Genetic and evolutionary computation - GECCO ’15, pages 1399–
1406. ACM Press, 2015.
[6] D.-C. Dang and P. K. Lehre. Efficient Optimisation of Noisy Fitness Functions with
Population-based Evolutionary Algorithms. In Proceedings of the 2015 ACM Conference
on Foundations of Genetic Algorithms XIII - FOGA ’15, pages 62–68, New York, New
York, USA, Jan. 2015. ACM Press.
[7] D.-C. Dang and P. K. Lehre. Simplified runtime analysis of estimation of distribution
algorithms. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference, GECCO ’15, pages 513–518, New York, NY, USA, 2015. ACM.

21

[8] B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In
IEEE Congress on Evolutionary Computation (CEC ’10), pages 1967–1974, 2010.
[9] B. Doerr and C. Winzen. Reducing the arity in unbiased black-box complexity. Theoretical
Computer Science, 545:108–121, 2014.
[10] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm.
Theoretical Computer Science, 276:51–81, 2002.
[11] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning.
Addison-Wesley, Reading, 1989.
[12] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms.
Artificial Intelligence, 127(1):57–85, 2001.
[13] J. Holland. Adaptation in natural and Artificial Systems. University of Michigan Press,
Ann Arbor, 1975.
[14] T. Jansen. Analyzing Evolutionary Algorithms. The Computer Science Perspective.
Springer, 2013.
[15] T. Jansen, P. S. Oliveto, and C. Zarges. On the analysis of the immune-inspired B-cell
algorithm for the vertex cover problem. In Proc. of ICARIS, pages 117–131. Springer,
2011.
[16] T. Jansen and C. Zarges. Computing longest common subsequences with the B-cell
algorithm. In Proc. of ICARIS, pages 111–124. Springer, 2012.
[17] T. Jansen and C. Zarges. Reevaluating immune-inspired hypermutations using the fixed
budget perspective. IEEE Trans. Evolut. Comput., 18(5):674–688, 2014.
[18] D. Johannsen. Random combinatorial structures and randomized search heuristics. PhD
thesis, Univesity of Saarland, Germany, 2012.
[19] P. K. Lehre. Negative drift in populations. In PPSN (1), pages 244–253, 2010.
[20] P. K. Lehre. Fitness-levels for non-elitist populations. In Proceedings of the 13th annual
conference on Genetic and evolutionary computation - GECCO ’11, page 2075, New York,
New York, USA, July 2011. ACM Press.
[21] P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623–
642, 2012.
[22] P. K. Lehre and C. Witt. Concentrated hitting times of randomized search heuristics with
variable drift. In Proc. of 25th International Symposium on Algorithms and Computation
- ISAAC 2014, pages 686–697, 2013.
[23] A. M. Lyapunov. The General Problem of the Stability if Motion (in Russian). Kharkov
Mathematical Society, 1892.
[24] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and
Probabilistic Analysis. Cambridge University Press, Cambridge, 2005.
[25] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press,
Cambridge, 1995.
[26] F. Neumann, U.-M. OReilly, and M. Wagner. Computational complexity analysis of
genetic programming - initial results and future directions. In R. Riolo, E. Vladislavleva,
and J. H. Moore, editors, Genetic Programming Theory and Practice IX, pages 113–128.
Springer, 2011.
[27] F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization –
Algorithms and Their Computational Complexity. Springer, 2010.
[28] P. S. Oliveto and D. Sudholt. On the runtime analysis of stochastic ageing mechanisms.
In GECCO ’14: Proceedings of the 2014 annual conference on Genetic and evolutionary
computation, pages 113–120, 2010.
[29] P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369–386, 2011.
[30] P. S. Oliveto and C. Witt. Erratum: Simplified drift analysis for proving lower bounds
in evolutionary computation. Technical Report arXiv:1211.7184, arXiv preprint, 2012.
[31] P. S. Oliveto and C. Witt. On the runtime analysis of the simple genetic algorithm.
Theoretical Computer Science, 545:2–19, 2014.

22

[32] P. S. Oliveto and C. Witt. Improved time complexity analysis of the simple genetic
algorithm (in press). Theoretical Computer Science, 2015.
[33] T. Paixao, G. Badkobeh, N. Barton, D. Corus, D.-C. Dang, T. Friedrich, P. K. Lehre,
D. Sudholt, A. M. Sutton, and B. Trubenová. Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology, 383:28 – 43, 2015.
[34] G. H. Sasaki and B. Hajek. The time complexity of maximum matching by simulated
annealing. Journal of the Association for Computing Machinery, 35(2):387–403, 1988.
[35] D. Sudholt. General lower bounds for the running time of evolutionary algorithms. In
Proceedings of the 11th International Conference on Parallel Problem Solving from Nature
(PPSN XI), volume 6238 of Lecture Notes in Computer Science, pages 124–133. Springer,
2010.
[36] D. Sudholt. Parallel evolutionary algorithms (to appear). In J. Kacprzyk and W. Pedrycz,
editors, Handbook of Computational Intelligence, pages –. Springer, 2015.
[37] I. Wegener. Methods for the analysis of evolutionary algorithms. In R. Sarker and X. Yao,
editors, Evolutionary Optimization, pages 125–141. Kluwer Academic, New York, 2002.
[38] C. Witt. Runtime analysis of the (µ+1) ea on simple pseudo-boolean functions. Evolutionary Computation, 14(1):65–86, 2006.
[39] C. Witt. Optimizing linear functions with randomized search heuristics - the robustness
of mutation. In C. Dürr and T. Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 420–431, Dagstuhl, Germany, 2012. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik.

23

