Novel Analysis of Population Scalability in Evolutionary Algorithms
Jun He∗
Department of Computer Science
Aberystwyth University, Aberystwyth, SY23 3DB, U.K.

arXiv:1108.4531v4 [cs.NE] 10 May 2013

Tianshi Chen
Institute of Computing Technology
Chinese Academy of Sciences, Beijing 100190, China
Boris Mitavskiy
Department of Computer Science
Aberystwyth University, Aberystwyth, SY23 3DB, U.K.
February 19, 2018

Abstract
Population-based evolutionary algorithms (EAs) have been widely applied to solve various optimization problems. The question of how the performance of a population-based EA depends on the population size arises naturally. The performance of an EA may be evaluated by different measures, such as
the average convergence rate to the optimal set per generation or the expected number of generations to
encounter an optimal solution for the first time. Population scalability is the performance ratio between a
benchmark EA and another EA using identical genetic operators but a larger population size. Although
intuitively the performance of an EA may improve if its population size increases, currently there exist
only a few case studies for simple fitness functions. This paper aims at providing a general study for
discrete optimisation. A novel approach is introduced to analyse population scalability using the fundamental matrix. The following two contributions summarize the major results of the current article. (1)
We demonstrate rigorously that for elitist EAs with identical global mutation, using a lager population
size always increases the average rate of convergence to the optimal set; and yet, sometimes, the expected
number of generations needed to find an optimal solution (measured by either the maximal value or the
average value) may increase, rather than decrease. (2) We establish sufficient and/or necessary conditions
for the superlinear scalability, that is, when the average convergence rate of a (µ + µ) EA (where µ ≥ 2)
is bigger than µ times that of a (1 + 1) EA.

1

Introduction

Population-based evolutionary algorithms (EAs) have been widely applied to tackle a variety of optimization
problems. A wide number of approaches is available to design efficient population-based EAs. Using a
population delivers many benefits [1]. A commonly accepted intuitive hunch is that the performance of such
an EA may improve if its population size increases. Nonetheless, sometimes an intuitive rule of thumb may
be bridgeable, hence a rigorous analysis is highly desirable. Currently there are only a few case studies for
simple fitness functions, but no general result has been established so far.
Population scalability describes the relationship between the performance of an EA and its population
size. The actual meaning of a population-based EA should be interpreted as a family of EAs using identical
genetic operators but different population sizes. Considering a benchmark EA and another EA in the family
with a population size larger than the benchmark EA, population scalability (scalability for short) is measured
∗ Corresponding

author. jun.he@ieee.org

1

intuitively as the ratio,
scalability =

performance of a benchmark EA
.
performance of an EA with a larger population size

(1)

To make use of the above formula, it is necessary to clarify the meaning of the “performance” of an EA.
Since EAs are iterative methods, the following two measures are fundamental in evaluating their performance
from both, theoretical and practical points of view.
Convergence rate: the rate of an EA converging to the optimal set per generation [2, 3]. The convergence
rate is a measure applicable in both, numerical and discrete optimization problems.
Expected number of generations: the average number of generations needed to encounter an optimal
solution for the first time 1 . This measure is not suitable for numerical optimization, where an EA
usually needs an infinite number of generations to find an exact solution.
To simplify the analysis, a (1 + 1) EA plays the role of the benchmark EA in the paper. Another EA
is a (µ + µ) EA where µ (≥ 2) is the population size (an integer). Furthermore EAs under consideration
satisfy the following conditions: (1) they are applied to tackle discrete optimization problems; (2) they are
convergent; (3) genetic operators include mutation and selection only; and (4) genetic operators are selected
in the same fashion at every generation.
The problem of population scalability is rather challenging in the theory of population-based EAs. In
order to estimate population scalability, it is necessary to acquire the exact value of the convergence rate or
the expected number of generations it takes to reach an optimal solution for both, (1 + 1) and (µ + µ) EAs.
The difficulty is that the convergence rate depends on the initial population and varies from one generation
to another; and the expected number of generations depends on the initial populations. Furthermore the
search spaces corresponding to the (1 + 1) and (µ + µ) EAs have different dimensions. Therefore the notion
of population scalability should be based on the “overall” performance of an EA, but how does one define
the “overall” performance?
Convergent EAs can be modelled via absorbing Markov chains [4, 5], and one of the most elegant aspects of the theory of absorbing Markov chains revolves around the notion of the fundamental matrix,
{N (X, Y )}X, Y are transient states where N (X, Y ) is the expected number of visits to the transient state X
starting with a transient states Y prior to absorption.
Clearly given a (1 + 1) EA and a (µ + µ) EA (where µ ≥ 2), it is impossible to make an “entrywise”
comparison between their fundamental matrices (the expected number of visits) since the dimensions of the
corresponding matrices are different. Instead, such a comparison should be based on a non negative-valued
function of the matrix, such as the spectral radius or a matrix norm of the fundamental matrix from the
viewpoint of mathematics. The spectral radius of a matrix is the maximum of the absolute values of its
eigenvalues.
This paper focuses on the spectral radius ρ(N). In section 3 we show that 1/ρ(N) is the average rate of
convergence to the optimal set; and ρ(N) is a ”max-min” value related to the expected number of visits to
a transient state. Population scalability is measured rigorously in terms of the ratio of the spectral radii of
the corresponding fundamental matrices:
spectral radius of the fundamental matrix of the (1 + 1) EA
.
spectral radius of the fundamental matrix of the (µ + µ) EA

(2)

The aim of the current article is to compare the average convergence rate towards an optimal solution
(i.e. an absorbing set of states) of the corresponding Markov transition matrices modelling a (µ + µ) EA and
a (1 + 1) EA. This makes the paper very different from the majority of prior research trends, that study the
expected number of generations. This work addresses the following two fundamental questions.
1. Does the average convergence rate increase as the population size does, and, if so, then under what
kind of circumstances does this take place? Intuitively this seems trivial, since a (µ + µ) EA employs
more individuals than a (1 + 1) EA does, nonetheless, a proof is required to confirm this.
1 In EAs (but never in iterative methods), the performance is also evaluated by the expected number of fitness evaluations
needed to find an optimal solution. Since in a (µ + µ) EA, the number of fitness evaluations per generation is fixed to µ, so the
expected number of fitness evaluations = µ× the expected number of generations. Therefore it is sufficient to study population
scalability using the number of generations.

2

2. As the population size increases from 1 to µ, under what kind of circumstances does the average
convergence rate increase by a factor bigger than µ? This is another intuitive principle, since the
number of individuals employed by a (µ + µ) EA is µ times that by the corresponding (1 + 1) EA.
The paper is organized as follows: A review of previous related research is given in Section 2. Convergence
rate and population scalability are formally introduced in Section 3. Section 4 aims at answering the first
question stated above while Section 5 aims at answering the second one. Sections 6 and 7 are devoted to the
case studies of non-bridgeable and bridgeable fitness landscapes. Finally, Section 8 concludes the paper and
discuss other types of EAs.

2

Related Work

The study of population scalability in evolutionary computation can be traced to early 1990s. Goldberg et al.
[6] presented a population sizing equation to show how a large population size helps an EA to distinguish
between good and bad building blocks on some test problems. Mühlenbein and Schlierkamp-Voosen [7]
studied the critical (minimal) population size that can guarantee convergence to the optimum. An adoptive
scheme to control the population size has been proposed in Arabas et al. [8] and the effectiveness of the
proposed methodology has been validated through an empirical study. A review of various techniques to
control EA’s parameters where an adjustment of the population size has been emphasized as an important
research issue appears in Eiben et al. [9]. A link between the population size and the quality of the solution
has been exhibited in Harik et al. [10] via an analogy between one-dimensional random walks and EAs. While
the approximate population sizing models proposed in the investigations mentioned above may shed some
light on deciding a “promising” population size, the effectiveness of the models has been validated only via
various case studies based upon specific optimization problems.
There do exist a few rigorous results about population scalability. As one of the earliest rigorous analysis,
He and Yao [11] investigated how the expected hitting time of EAs varies as the population size increases.
A while later He and Yao [12] exhibited a link between population scalability and parallelism. A study of
the population scalability of the (1 + µ) EA on three pseudo-Boolean functions, Leading-Ones, One-Max
and Suf-Samp appears in Jansen et al. [13]. Lässig and Sudholt [14] presented a runtime analysis of a
(1 + µ) EA with an adaptive offspring size µ on several pseudo-Boolean functions. An analysis of how the
running time of a (µ + 1) EA on the Sphere function scales up with respect to the problem size n appears
in Jägersküpper and Witt [15]. In Jansen and Wegener [16] it has been shown that the running time of
the (µ + 1) EA with a crossover operator on the Real Royal Road function is polynomial on average, while
that of an EA with mutation and selection only is exponentially large with an overwhelming probability. A
rigorous run-time analysis of the (µ + 1) EA on a specific pseudo-Boolean function has been carried out in
Witt [17, 18]. A rigorous runtime analysis of selecting the population size with respect to the (µ + 1) EA
on several pseudo-Boolean functions appears in Storch [19]. A runtime analysis of both (1 + µ) and (µ + 1)
EA on some instances of Vertex Covering Problems is provided in Oliveto et al. [20]. A run-time analysis
of (µ + 1) EAs with diversity-preserving mechanisms on the Two-Max problem has been implemented in
Friedrich et al. [21]. An upper bound on the number of generations it takes a (µ + µ) EA to encounter an
optimal solution for the first time on the two well-known unimodal problems, Leading-Ones and One-Max,
has been obtained in [22]. The effect of population size in evolutionary multi-objective optimization has been
considered in Giel and Lehre [23]. It has been shown that only the population-based EA is successful, while
all the other individual-based algorithms fail on a specified class of pseudo-Boolean functions. Nonetheless,
all of the available theoretical results are mainly restricted to several simple algorithms for tackling specific
problems. In other words, the up-to-date knowledge is limited to case studies only [24].
In contrast with the previous investigations, the current paper aims at drawing general results that apply
to all discrete optimisation problems. The study is based on the fundamental matrix of the Markov chain
modelling an EA. Such an approach can be traced back to an early work on asymptotic convergence properties
of EAs in Fogel [25] and it has been applied to analysing elitist EAs in He and Yao [5].

3

3

Evolutionary Algorithms, Absorbing Markov Chains and Population Scalability

3.1

Formalization of EAs

Without loss of generality, consider the problem of maximizing a fitness function f (x).
max f (x),

x ∈ D,

subject to constraints,

where f (x) is a fitness function, and D is its domain (a finite set). For instance, D is the set of all Boolean
formulas in the satisfiability problem [26], or the set of all possible vertex covers in the vertex cover problem
[20]. Arrange the values of the fitness function in the order from high to low, that are called fitness levels.
To alleviate the complexity of theoretical analysis, suppose that all constraints in the above problem have
been removed through a constraint handling method. Under this circumstance, all solutions in D are thought
to be feasible. Practical and theoretical analysis of constraint handling in evolutionary computation may be
found in [27, 28], for instance.
We consider an EA that makes use of an extra archive for keeping the best found solution. The archive
itself is not involved in generating a new population. The general design of a (µ + µ) EA with an archive
is described in Algorithm 1. In the description, t denotes the generation counter. Φt = (φt,1 , · · · , φt,µ )
represents the population at the tth generation, where φt,1 , · · · , φt,µ are µ individuals. Φt+1/2 denotes the
offspring population generated via mutation from the population Φt .
Algorithm 1 A (µ + µ) EA with an Archive (where µ is the population size)
1: input: fitness function;
2: generation counter t ← 0;
3: initialize Φ0 ;
4: an archive keeps the best solution in Φ0 ;
5: while (no optimal solution is found) do
6:
Φt+1/2 ← each individual in Φt generates a child by mutation;
7:
evaluate the fitness of each individual in Φt+1/2 ;
8:
Φt+1 ← selected from Φt , Φt+1/2 ;
9:
update the archive if the best solution in Φt+1 is better than it;
10:
t ← t + 1;
11: end while
12: output: the maximum of the fitness function.
The initial population is selected at random in such a way that any possible population may be chosen
with a positive probability. Rather general definitions of mutation and selection operators appear below.
• A mutation operator is represented via an S (1) by S (1) Markov transition probability matrix the entries
of which are given as
PM (x, y) = P (φt+1/2 = y | φt = x), x, y ∈ S (1) .
Here PM (x, y) denotes the probability of going from x to y. φt is an individual in the tth generation
population and φt+1/2 the child of φt after mutation. S (1) = D is called the space of individuals.
Individuals φt and φt+1/2 represent random variables, while x and y denote their states.
• A selection operator is represented via an S (µ) × S (µ) by S (µ) probability transition matrix, the entries
of which are introduced below:
PS (X, Y ; Z) = P (Φt+1 = Z | Φt = X, Φt+1/2 = Y ),

X, Y, Z ∈ S (µ) .

Here PS (X, Y ; Z) represents the probability of selecting µ individuals from populations X and Y
(children of X) and then forming the next parent population Z. Φt is the tth generation population,
Φt+1/2 the population of children of Φt after mutation, and Φt+1 is the (t + 1)th generation population.
Q
S (µ) is the Cartesian product µi=1 S (1) , called a space of populations if µ ≥ 2. Populations Φt ,
4

Φt+1/2 and Φt+1 are random variables, while X, Y, Z denotes their states in the space of populations.
Superscripts (1) and (µ) are used to distinguish between the space of individuals and space of populations.
A natural requirement on the selection operator is that all the individuals in Z must come from these in
X or in Y . If Z contains an individual that is neither an individual of X nor of Y , then the probability
of going from X and Y to Z is 0.
The stopping criterion is that the algorithm will terminate once an optimal solution is found. This
criterion is assumed only for the sake of convenience of the theoretical analysis. Apparently, we can simply
ignore what happens after an EA encounters an optimal solution. EAs considered in the paper are convergent.
Starting from any initial population, an EA can find an optimal solution after a finite number of generations.
The mathematical framework introduced above incorporates a wide class of EAs as it doesn’t assume any
implementation details. Table 1 summarizes the special notation appearing in the paper.
(1)

and (µ)
S (1)
S (µ)
x, y, z
X, Y, Z
(1)
Sopt
(1)
Snon
(µ)
Sopt
(µ)
Snon
(µ)
Ssame (x)
(µ)
Shigh (x)
(µ)
Sbridge (x)
(µ)
P (X, Sset (x))
xρ
Φt
Φt+1/2
qt (X)
qt
m(X)
Qx,x

distinguish between a (1 + 1) EA and a (µ + µ) EA when necessary
the set of individuals
Q
the set of populations of size µ, = Cartesian product µi=1 S (1)
individuals, also called states in S (1)
populations, also called states in S (µ)
the set of individuals that are optimal
the set of individuals that are not optimal
the set of populations that contain at least one optimal individual
the set of populations that contain no optimal individual
the set of populations the best individual of which is x
the set of populations with best individual’s fitness > f (x)
the set of populations that contain x’s bridgeable point
(µ)
the probability of going from X to the set Sset (x)
(1)
= arg max P (x, x) among all non-optimal states x ∈ Snon
th
the population at the t generation
the offspring population of Φt after mutation
the probability that Φt = X
the vector to represent the probabilities of Φt in all non-optimal states
the expected number of generations needed to find an optimal solution when
starting from X
(µ)
the transition probability submatrix within the set Ssame (x)
Table 1: Notation Table

3.2

Absorbing Markov Chains and their Fundamental Matrices

The discussion in the subsection follows the general analytic framework of the absorbing Markov chains for
analysing EAs initiated in He and Yao [5]. According to the stopping criterion, an EA halts once an optimal
solution is found. So if Φt = X is an optimal state, we let Φt+1 = Φt+2 = · · · = X for all the future states.
Thus the sequence {Φt , t = 0, 1, · · · } can be modelled by an absorbing Markov chain 2 . Let P be its transition
matrix, having entries
P (X, Y ) = P (Φt+1 = Y | Φt = X), X, Y ∈ S.
Individuals or populations are called states when we speak about the corresponding Markov chains. For the
Markov chains modelling convergent EAs, an optimal state is always an absorbing state while a non-optimal
state is always a transient state.
2 An absorbing Markov chain is a Markov chain where starting from every state, the chain can reach an absorbing state. An
absorbing state is a state from which it is impossible to leave[29, p.416].

5

The probability of going from X to a set Sset is denoted by
P (X, Sset ) = P (Φt+1 ∈ Sset | Φt = X).
The transition matrix of an absorbing Markov chain P can be written in the following canonical form.


I O
P=
,
(3)
∗ Q
where I is the identity matrix indicating transitions within the optimal set, and O denotes the zero matrix
(apparently representing transitions from optimal to non-optimal states, as discussed above). The matrix Q
denotes transitions within non-optimal states. The part ∗ represents transitions from the non-optimal states
to the optimal ones.
Perhaps the most elegant part of the theory of absorbing Markov chains revolves around the notion of a
fundamental matrix.
Definition 1. [29, Definition 11.3] The matrix N = (I − Q)−1 is called the fundamental matrix, where its
entry N (X, Y ) gives the expected number of visits to a transient state X starting from a transient state Y
before being absorbed.
The expected number of visits has a direct link to the the expected number of generations needed to
encounter an optimal solution for the first time.
Lemma 1. [29, Theorem 11.5] Let m(X) denote the expected number of generations needed to encounter an
optimal solution for the first time when starting from a transient state X. Then
X
m(X) =
N (X, Y ).
(4)
Y ∈Snon

In the paper we consider two special values of the expected number of generations it takes to reach an
optimum solution. The first one is the maximum value of the expected number of generations, given as
X
max{m(X); X ∈ S} = max{
N (X, Y ); X ∈ S}.
(5)
Y ∈Snon

The above value is the supreme of the expected number of generations it takes to reach an optimal solution
among all possible initializations.
The second one is the average value of the expected number of generations it takes to reach an optimum
over all of the transient states, given as
1
| Snon |

X

X∈Snon

m(X) =

1
| Snon |

X

N (X, Y ),

(6)

X,Y ∈Snon

where | Snon | denotes the cardinality of the set of transient states. The above value is achieved when
the initial population is chosen uniformly at random from the set of all transient states. Analogously, an
alternative notion of the expected number of generations it takes to encounter an optimal individual for the
first time when any population (not necessarily one containing no optimal individual) is selected uniformly
at random is given as follows:
1 X
m(X).
|S|

(7)

X∈S

3.3

Average Convergence Rate

In this subsection, we introduce the notion of the average convergence rate. The convergence rate of an EA
measures how fast Φt converges to the optimal set per generation. In EAs, it is formally defined by the
conditional probability of an EA converging to the optimal set, that is
P (Φt ∈ Sopt | Φt−1 ∈ Snon ) = 1 − P (Φt ∈ Snon | Φt−1 ∈ Snon ).
6

We denote the probability that Φt is at a transient state X by
qt (X) = P (Φt = X).
Write all transient states in a vector form 3 : (X1 , X2 , · · · )T . Then the vector
qt = (qt (X1 ), qt (X2 ), · · · )T
denotes the probabilities of Φt in all transient states. The corresponding Markov chain is then represented
by a matrix iteration:
qTt+1 = qTt Q, or qt+1 = QT qt .

(8)

Since the EA is initialized at random so that every possible population is selected with a positive probability (for instance, uniformly at random), each state can be chosen as an initial state with a positive probability.
This means that q0 (X) > 0 for all X ∈ Snon . We denote this by q0 > 0.
Write the probability of Φt being in the transient set in the 1-norm for 4 .
k qt k1 = P (Φt ∈ Snon ).
Since the EA is initialized at random, k qt k1 = P (Φt ∈ Snon ) > 0.
Since P (Φt−1 ∈ Sopt , Φt ∈ Snon ) = 0, the conditional probability of staying within the non-optimal set in
the tth generation is
P (Φt ∈ Snon | Φt−1 ∈ Snon )
P (Φt−1 ∈ Snon , Φt ∈ Snon )
P (Φt−1 ∈ Snon )
P (Φt−1 ∈ Sopt , Φt ∈ Snon ) + P (Φt−1 ∈ Snon , Φt ∈ Snon )
=
P (Φt−1 ∈ Snon )
P (Φt ∈ Snon )
=
P (Φt−1 ∈ Snon )
k qt k1
.
=
k qt−1 k1

=

Thus, the geometric mean of the conditional probabilities of staying within the non-optimal set for t
generations is
t
Y

!1/t

P (Φs ∈ Snon | Φs−1 ∈ Snon )

s=1

=



k qt k1
k q0 k1

1/t

.

(9)

Next we define the average convergence rate for t generations based on the geometric mean above.
Definition 2. The average rate of convergence to the optimal set for t generations is
1−

t
Y

!1/t

P (Φs ∈ Snon | Φs−1 ∈ Snon )

s=1

.

Now we consider the limit of the rate as t increases towards +∞.
Lemma 2. The average rate of convergence to the optimal set for t generations satisfies
1 − lim

t→+∞

t
Y

!1/t

P (Φs ∈ Snon | Φs−1 ∈ Snon )

s=1

= 1 − ρ(Q).

3 v represents a column vector and the transpose notation, vT , allows to represent this column vector in the form of a row
vector. The vector v is also P
denoted by [v(X)] and its entry v(X) by [v]X .
Pn
n
4 For a vector v, k v k =
1
i=1 | vi |. For a square matrix A = [Aij ], k A k1 = max1≤j≤n
i=1 |Aij |.

7

Proof. (1) From the matrix iteration qt = QT qt−1 , we get
k qt k1 ≤k (QT )t k1 k q0 k1 .
Since the EA is initialized at random, and q0 > 0, the average rate of convergence to the optimal set
after t iterations satisfies

1/t
k qt k1
1/t
1−
≥ 1− k (QT )t k1 .
k q0 k1
According to the Gelfand’s spectral radius formula 5 , as t → +∞,
1 − lim

t→+∞



k qt k1
k q0 k1

1/t

1/t

≥ 1 − lim k (QT )t k1 = 1 − ρ(QT ) = 1 − ρ(Q).
t→+∞

(10)

(2) Since Q ≥ 0, according to the Perron-Frobenius theorems [30, p.670], ρ(Q) is an eigenvalue of Q (and
also QT ) and the corresponding eigenvector v ≥ 0. In particular,
ρ(Q)v = QT v.
Let min q0 denote the minimum value of all the entries in the vector q0 . Since q0 > 0, min q0 > 0 as
well. Normalize the vector v so that 6 k v k∞ = min q0 . We split q0 into two parts,
q0 = v + w,
where w ≥ 0. Thus, since w ≥ 0 and Q ≥ 0, we deduce that
qt = QT qt−1 = (QT )t q0 = (QT )t (v + w) ≥ (QT )t v = (ρ(Q))t v.
It follows then that


k qt k1
k q0 k1

1/t

≥ ρ(Q)



k v k1
k q0 k1

1/t

→ ρ(Q)

as t → +∞. The inequality is equivalent to the one below:
1 − lim

t→+∞



k qt k1
k q0 k1

1/t

≤ 1 − ρ(Q).

The desired conclusion follows by combing the inequality above with Inequality (10) and Equality (9).
Definition 3. The average rate of convergence to the optimal set is
1 − lim

t→+∞

t
Y

!1/t

P (Φs ∈ Snon | Φs−1 ∈ Snon )

s=1

= 1 − ρ(Q).

The “average” is the geometric mean that is taken over all generations under the condition of randomized
initialization 7 .
5 Gelfand’s spectral radius formula says that for any induced matrix norm k A k, its spectral radius ρ(A) = lim
t 1/t
t→∞ k A k
[30, p.619].
6 For a vector v, k v k = max
∞
i=1,··· ,n | vi |.
7 The rate is similar to another average rate of convergence based on the logarithmic mean [31, p.73], − ln ρ(Q). The difference
between the two notions of rate is not particularly significant [32]

8

3.4

The Spectral Radius of the Fundamental Matrix

Given a (1 + 1) EA and a (µ + µ) EA (where µ ≥ 2), it is impossible to make an “entrywise” comparison
of their fundamental matrices (the expected number of visits) since their dimensions are different. Instead,
the comparison should be based on a measure of all entries. The spectral radius or matrix norms of the
fundamental matrix thus play the role of such a measure.
In this subsection we discuss the spectral radius of the fundamental matrix. First we show that 1/ρ(N)
equals the average convergence rate. This can be seen from the following lemma.
Lemma 3. The spectral radii of the transition probability submatrix Q and the fundamental matrix N are
related as follows:
ρ(N) = (1 − ρ(Q))−1 .
(11)
Proof. From the definition of the fundamental matrix, it follows that λ is an eigenvalue of Q if and only if
(1 − λ)−1 is an eigenvalue of N.
Since Q is non-negative, according to Perron-Frobenius Theorems [30, p.670], ρ(Q) is an eigenvalue of Q
such that
ρ(Q) ≥| λ |,
where λ is any eigenvalue of Q.
On the other hand, (1 − ρ(Q))−1 is an eigenvalue of N and satisfies
1
1
1
≥
≥
,
1 − ρ(Q)
1− | λ |
|1−λ|
so that (1 − ρ(Q))−1 is the spectral radius of N.
Next the lemma below shows that ρ(N) is a “max-min” value related to the expected number of visits to
transient states.
Lemma 4. The spectral radius of the fundamental matrix equals
P
X∈Snon N (Y, X)q0 (X)
min
ρ(N) = max
,
q0
q0 (Y )
Y :q0 (Y )6=0

(12)

where q0 (X) = P (Φ0 = X) is the probability that the initial population Φ0 is at the state X and N (Y, X) is
the expected number of visits to the state X starting from the state Y .
Proof. The lemma is a direct application of the Collatz-Wielandt formula 8 .
ρ(N) = ρ(NT ) = max
q0

= max
q0

[NT q0 ]Y
Y :q0 (Y )6=0 [q0 ]Y
P
min

min

X∈Snon

Y :q0 (Y )6=0

N (Y, X)q0 (X)
,
q0 (Y )

which is the conclusion.
Eventually, the lemma below establishes lower and upper bounds on the spectral radius of the fundamental
matrix.
Lemma 5. The spectral radius of the fundamental matrix satisfies the following inequality:
min m(X) ≤ ρ(N) ≤ max m(X).

X∈Snon

X∈Snon

8 The

(13)

”max-min” version of the Collatz-Wielandt formula claims that for a nonnegative square matrix A = [Aij ], its spectral
[Ax]
radius ρ(A) = maxx∈N g(x), where g(x) = min1≤i≤n,xi 6=0 [x] i and the set N = {x; x ≥ 0 with x 6= 0} [30, p670]. There
i
exists a ”min-max” version of the Collatz-Wielandt formula, which is applicable too.

9

Proof. The lemma is a direct consequence of the following fact 9 : given any n × n non-negative A = [aij ],
its spectral radius satisfies the inequalities
min
i

n
X

aij ≤ ρ(A) ≤ max
i

j=1

n
X

ai,j .

j=1

Indeed, substituting N in place of A yields the desired conclusion.

3.5

Matrix Norms of the Fundamental Matrix

Matrix norms 10 can be used as a measure of the expected number of visits. The ∞-norm of the fundamental
matrix is given as
X
k N k∞ = max
N (X, Y ).
(14)
X∈Snon

Y ∈Snon

Lemma 6. The ∞-norm of the fundamental matrix equals k N k∞ = maxX∈Snon m(X).
Proof. This follows immediately from the definition of the matrix ∞-norm and Lemma 1.
The definition and the lemma above provide us with two equivalent interpretations of k N k∞ . k N k∞
is the maximal value of the expected number of visits to the set of transient states among all possible
initializations. This is equivalent to saying that k N k∞ is the maximal value of the expected number of
generations to reach the optimal set among all possible starting transient states.
The a-norm of the fundamental matrix is defined as
X
1
N (X, Y ).
(15)
k N ka =
| Snon |
X,Y ∈Snon

Lemma 7. The ∞-norm of the fundamental matrix is alternatively described as follows:
k N ka =

1
| Snon |

X

m(X).

(16)

X∈Snon

Proof. This is an immediate consequence of the definition of the matrix a-norm and lemma 1.
The definition and the lemma above reveal the following two equivalent meanings of k N ka . k N ka is
the average value of the expected number of visits to the set of transient states among all possible initial
transient states. k N ka is the average value of the expected number of generations it takes to reach the
optimal set among all possible initial transient states.

3.6

Population Scalability

Given a (1 + 1) EA and a (µ + µ) EA (where µ ≥ 2) that exploit an identical mutation operator to optimize
the same fitness function, population scalability is measured by the ratio between their performances. As
discussed in previous sections, there are different approaches to evaluate the performance of an EA and,
hence, there are several ways to measure population scalability.
Definition 4. Population scalability under the spectral radius of the fundamental matrix is
1 − ρ(Q(µ) )
ρ(N(1) )
=
ρ(N(µ) )
1 − ρ(Q(1) )
average convergence rate of the (µ + µ) EA
.
=
average convergence rate of the (1 + 1) EA

ρ-scalability(µ) =

(17)
(18)

9 The fact is given in [30, Exercise 8.2.7]. The result in Exercise 8.2.7 is stated only for positive matrices, yet an identical
argument that replaces the Collatz-Wielandt formula for positive matrices by the Collatz-Wielandt formula for non-negative
matrices shows that the same fact holds for all non-negative
matrices.
Pn
Pn
10 For a square matrix A = [A ], k A k = max
∞
ij
j=1 |Aij | and k A ka = ( i,j=1 |Aij |)/n.
1≤i≤n

10

Definition 5. Population scalability under the ∞-norm of the fundamental matrix is
k N(1) k∞
k N(µ) k∞
maximum value of expected numbers of generations of the (1 + 1) EA
=
.
maximum value of expected numbers of generations of the (µ + µ) EA

∞-scalability(µ) =

(19)
(20)

Definition 6. Population scalability under the a-norm of the fundamental matrix is
k N(1) ka
k N(µ) ka
average value of expected numbers of generations of the (1 + 1) EA
=
,
average value of expected numbers of generations of the (µ + µ) EA

a-scalability(µ) =

(21)
(22)

where the average is taken over all of the transient states, excluding the absorbing state(s).
If considering the average over all the states, an alternative definition is given by
(1)

â-scalability(µ) =

| Snon | k N(1) ka
.
(µ)
(µ)
| Snon | k N ka

(23)

An essential part of the definitions above is that both EAs must adopt identical mutation operators. This
ensures that the comparison is meaningful. Nonetheless, it is impossible for the selection operators to be
identical. Indeed even if the selection operators are of the same type, for example roulette wheel selection,
the conditional probabilities determining the actual selection operators are never identical under distinct
population sizes.
The following questions are fundamental when studying population scalability.
1. As the population size increases from 1 to µ (where µ ≥ 2), is the scalability (µ) > 1?
If the population scalability is not bigger than 1, then we say that the (µ + µ) EA has no scalability
with respect to the (1 + 1) EA.
2. As the population size increases from 1 to µ (where µ ≥ 2), is the scalability (µ) > µ?
If the population scalability is greater than µ, then we say that the (µ+µ) EA has superlinear scalability
with respect to the (1 + 1) EA.
Population scalability is different from the relationship between the performance of an EA and its population size discussed in previous references such as [13]. There the comparison of the two EAs is carried out
in terms of the big O notation. The difference is clearly demonstrated through the following question:
maximum value of expected number of generations for the (1 + 1) EA
< 1?
maximum value of expected numbers of generations for the (µ + µ) EA
Within the framework in Jansen et al. [13], the question may be reformulated as
maximum value of expected numbers of generations of (1 + 1) EA
= O(1)?
maximum value of expected numbers of generations of (µ + µ) EA
Here O(1) is big O notation. Nonetheless, there is a drawback in using the big O notation when studying
population scalability. For example, O(1) does not distinguish between the case when the expected number
of generations the (1 + 1) EA takes to reach an optimum for the first time is 100 times that the (µ + µ) EA
takes, and the case when the expected number of generations the (1 + 1) EA takes is 1/100 times that the
(µ + µ) EA takes. In this sense, population scalability analysis is different from the work in Jansen et al. [13].
The notion of population scalability is similar to that of the speedup widely used when analysing parallel
algorithms. Nonetheless, population scalability doesn’t depend on the number of parallel computing processors. There is a link between superlinear population scalability and superlinear speedup in parallel EAs. If

11

each individual is assigned to a processor, then EAs turn into parallel EAs. Under this circumstance, superlinear scalability implies superlinear speedup if ignoring the communication cost. An interesting question in
parallel EAs is when and how superlinear speedup phenomenon happens [33, 34, 35].
There is an essential difference between the notions of population scalability and that of No Free Lunch
Theorems [36]. Population scalability compares the performance of two EAs that exploit identical genetic
operators but different population sizes to optimize the same fitness function, while the No Free Lunch
Theorems compare the average performance of the two EAs over all possible fitness functions.

4

Analysis of Population Scalability for Elitist EAs using Global
Mutation

4.1

Elitist Selection and Global Mutation

This section focuses on investigating elitist EAs that adopt global mutation and elitist selection operators.
The corresponding definitions appear below.
Definition 7. A mutation operator is called global if any individual can reach the optimal set via mutation
after a single iteration.
Definition 8. A selection operator is called elitist if the best parent individual is replaced by the best child
individual only in case when the best child individual is fitter. There is no restriction on selecting non-best
individuals and any selection strategy can be applied.
Global mutation guarantees that the optimal set is reachable starting from any initial state, while elitist
selection aims at maintaining the best solution found over time. An alternative elitist operator is to replace
the best parent individual by a child with a better or equal fitness [5]. In the current paper we do not consider
such a variant.
Now let’s emphasize two virtuous properties for mutation and elitist selection. The first property is called
the mutation property. It compares the probability of going from a population to a higher fitness level with
the probability of going from an individual to a higher fitness level.
(µ)

Lemma 8. Suppose X = (x1 , · · · , xµ ) ∈ Snon is a population with x1 = x being one of the best individuals.
Then the following mutation property holds for elitist EAs: for i = 1, · · · , µ, and µ ≥ 2,
(µ)

(1)

PM (X, Shigh (X)) ≥ PM (xi , Shigh (x)),
(µ)

PM (X, Shigh (X)) ≤

µ
X

(1)

PM (xi , Shigh (x)),

(24)
(25)

i=1

(µ)

where Shigh (x) denotes the set consisting of all populations whose best individual’s fitness is higher than f (x).
Furthermore, if a mutation operator is global, then the inequalities above are strict.
Proof. Notice that the event of going from X to a higher fitness level can be alternatively expressed as the
event that at least one of individuals xi goes to a higher fitness level.
Since mutation is performed independently, so that for µ ≥ 2 the probability of going from X to a higher
fitness level is
(µ)
PM (X, Shigh )

=1−

µ
Y

(1)

(1 − PM (xi , Shigh (x)),

i=1

implying that for i = 1, · · · , µ,
(µ)

(1)

PM (X, Shigh (X)) ≥ PM (xi , Shigh (x)).
The inequality for µ ≥ 2
(µ)

PM (X, Shigh (X)) ≤

µ
X
i=1

12

(1)

PM (xi , Shigh (x))

follows trivially from the fact that the probability of a union of events is always bounded above by the sum
of the probabilities of the constituent events.
Moreover, it is easy to see that the above inequalities are strict if the mutation operator is global.
Elitist selection insures that the best individual in a population will either enter a higher fitness level or
remain unchanged, thereby never getting worse. This phenomenon is called the elitist selection property and
it can be reformulated as follows.
Lemma 9. Given a population X the best individual of which is x, the elitist selection property implies that
(µ)

(µ)
P (X, Ssame
(x)) + P (X, Shigh (x)) = 1,

(26)

(µ)

where Ssame (x) denotes the set consisting of all populations the best individual of which is x.

4.2

Transition Matrices of Elitist EAs
(1)

First consider the (1 + 1) elitist EA. Arrange all states in Snon in the order of their fitness from high to low
(where the individuals at the same fitness level may be arranged in any order), and write them in a vector
form (x1 , x2 , x3 , · · · )T , where f (x1 ) ≥ f (x2 ) ≥ f (x3 ) ≥ · · · .
Thanks to the elitist selection property discussed in the previous section, the best individual never enters
a lower fitness level meaning that for any individuals x and y with f (y) ≤ f (x), the entry of the Markov
transition matrix that stands for the probability of going from an individual x to an individual y,
P (x, y) = 0.
It follows then that the transition matrix Q(1) is lower triangular
form:

P (x1 , x1 )
0
0 ···
P (x2 , x1 ) P (x2 , x2 ) 0 · · ·
(1)
Q =
..
..
..
..
.
.
.
.

and can be written in the following

0
0
(27)
.
..
.

The following simple fact now follows naturally from the definition of eigenvalues and spectral radius [30,
p.490].
Lemma 10. Given transition matrix Q(1) and let xρ be the state such that
(1)
xρ = arg max{P (x, x); x ∈ Snon
}.

(28)

ρ(Q(1) ) = P (xρ , xρ ).

(29)

Then the spectral radius
Here P (x, x) is the probability of the Markov chain remaining in state x. The above lemma shows that
the spectral radius of a Markov transition submatrix, that models a (1 + 1) EA (restricted to the non-optimal
states), is the maximal self-transition probability of a non-optimal state remaining unchanged in the next
generation.
(µ)
Next we consider a (µ + µ) EA (where µ ≥ 2). Arrange all populations in Snon in the order of the fitness
of their best individual from high to low (where populations with the same best individual are arranged
together in an arbitrary order), and write them in a vector form: (X1 , X2 , · · · )T . If x1 , x2 , · · · denote the
corresponding best individuals, then their fitness decreases: f (x1 ) ≥ f (x2 ) ≥ · · · .
Once again, thanks to the elitist selection property, the best individual in a population never revisits any
state at a lower fitness level. Thus the probability of going from population X (with the best individual x)
(µ)
(µ)
to population Y that is not in the set Ssame (x) or Shigh (x) is 0. It follows then that the matrix Q(µ) is a
block lower triangular matrix, that can be written in the form:


(µ)
O
O ···
Qx1 ,x1
 (µ)

(µ)
Qx2 ,x2 O · · · ,
Q
Q(µ) = 
(30)
 x1 ,x2

..
..
..
..
.
.
.
.
13

(µ)

where O denotes a zero matrix and Qx,y is the submatrix consisting of transition probabilities from the
(µ)
(µ)
(µ)
states in Ssame (x) to the states in Ssame (y). In particular, Qx,x is the submatrix consisting of transition
(µ)
probabilities within the set Ssame (x).
The following lemma is an extension of Lemma 10 for the case when µ ≥ 2.
(µ)

Lemma 11. Let Qx,x denote the diagonal block submatrix as in (30), that represents transitions within the
(µ)
set Ssame (x), then
ρ(Q(µ) ) = max ρ(Q(µ)
x,x ).

(31)

(1)

x∈Snon

Proof. The proof is based on a simple fact [30, Exercise 7.1.4]: if A is a block lower triangular matrix such
that


A1,1
O
,
(32)
A=
A2,1 A2,2
then λ is an eigenvalue of A if and only if λ is an eigenvalue of A1,1 or A2,2 . Thus ρ(A) = max{ρ(A1,1 ), ρ(A2,2 )}.
Let A = Q(µ) (see the matrix (30)), then
ρ(Q(µ) ) = max ρ(Q(µ)
x,x )
(1)

x∈Snon

as claimed.
The following lemma provides lower and upper bounds on the spectral radius of the transition probability
(µ)
submatrix Qx,x.
(µ)

Lemma 12. The spectral radius of the transition submatrix Qx,x satisfies
min
(µ)

X∈Ssame (x)

(µ)
P (X, Ssame
(x)) ≤ ρ(Q(µ)
x,x ) ≤

max
(µ)

X∈Ssame (x)

(µ)
P (X, Ssame
(x)).

(33)

(µ)

Proof. The proof is the same as that of Lemma 5. Indeed, substituting Qx,x in place of A yields the desired
conclusion.

4.3

ρ-Scalability Always Happens for Elitist EAs Exploiting Global Mutation

An intuitive reason behind the use of population-based EAs is that a larger population size is likely to increase
the convergence rate. The following proposition proves that this is, indeed, the case.
Theorem 1. Suppose a (1 + 1) elitist EA and a (µ + µ) elitist EA (where µ ≥ 2) exploit identical global
mutation operator to maximize the same fitness function. Then
ρ-scalability(µ) > 1.
(1)

Proof. For the (1 + 1) elitist EA, let xρ ∈ Snon be an individual such that ρ(Q(1) ) = P (xρ , xρ ).
Likewise, for a (µ + µ) elitist EA, Lemma 11 says that
ρ(Q(µ) ) = max ρ(Q(µ)
x,x ).
(1)

x∈Snon

(1)

(1)

Since the set Snon is finite, there exists an x ∈ Snon such that
ρ(Q(µ) ) = ρ(Q(µ)
x,x ).
(µ)

Consider the transition probability matrix Qx,x for such an x.
(µ)
According to Lemma 12, the spectral radius ρ(Qx,x ) is bounded above as
ρ(Q(µ)
x,x ) ≤

max
(µ)

X∈Ssame (x)

14

(µ)
P (X, Ssame
(x)).

(34)

(µ)

Thus there exists an X = (x1 , x2 , · · · , xµ ) in the set Ssame (x) where x1 = x, and the above inequality
holds for this specific X,
(µ)
ρ(Q(µ)
x,x ) ≤ P (X, Ssame (x)).
Combining the inequality above with the elitist selection property (26),
(µ)

(µ)
P (X, Shigh (x)) + P (X, Ssame
(x)) = 1,

yields
(µ)

ρ(Q(µ)
x,x ) ≤ 1 − P (X, Shigh (x)).

(35)

Now the global mutation property tells us that, for µ ≥ 2,
(µ)

(1)

P (X, Shigh (x)) > P (x, Shigh (x)) = 1 − P (x, x).
Recall that P (xρ , xρ ) is the maximal self-transition probability so that
(µ)

P (X, Shigh (x)) ≥ 1 − P (xρ , xρ ) = 1 − ρ(Q(1) ).
Substituting this bound into Inequality (35) yields
(1)
ρ(Q(µ)
).
x,x ) < ρ(Q
(µ)

Recalling (34): ρ(Q(µ) ) = ρ(Qx,x ), we deduce that
ρ(Q(µ) ) < ρ(Q(1) ),
so that ρ-scalability(µ) > 1. Thereby establishing the desired conclusion.

4.4

∞-Scalability May Not Happen for Elitist EAs using Global Mutation

Another intuitive reason behind the use of population-based EAs is that a larger population size is likely to
shorten the expected number of generations. Unfortunately sometimes this is wrong. The following example
shows that increasing the population size increases, rather than reduces, the maximum of the expected
number of generations for an EA to find an optimal solution. Equivalently, ∞-scalability(µ) < 1 for any
µ ≥ 2.
The fitness function is given in Table 2.
state
fitness

x0
5

x1
4

x2
3

x3
2

x4
1

Table 2: Fitness function.
Consider the following (µ + µ) EA (=(1 + µ) EA): the best individual is replicated by µ copies and each
copy generates a child via mutation; the best individual is replaced only when a child is better than it. The
mutation transition probabilities P (x, y), x, y = x0 , · · · , x4 are given in Table 3, where ǫ ≥ 0 is a sufficiently
small constant (the size of ǫ will be discussed later). When ǫ > 0, the mutation operator is global.
First, set ǫ = 0. The maximal value of the expected number of generations for the (1 + 1) EA to
encounter the optimal individual x0 is the time when the EA starts from x4 . According to the probability
transition matrix above, it takes 2 time steps (with probability 1) to reach the optimal state along the road
x4 → x3 → x0 (with probability 0.5), while it takes 3 time steps along the road x4 → x2 → x1 → x0 (also
with probability 0.5). Thus, by definition of the expectation,
m(1) (x4 ) = 2 · 0.5 + 3 · 0.5 = 2.5.

15

state
x0
x1
x2
x3
x4

x0
1 − 4ǫ
1 − 4ǫ
ǫ
1 − 4ǫ
ǫ

x1
ǫ
ǫ
1 − 4ǫ
ǫ
ǫ

x2
ǫ
ǫ
ǫ
ǫ
0.5

x3
ǫ
ǫ
ǫ
ǫ
0.5 − 3ǫ

x4
ǫ
ǫ
ǫ
ǫ
ǫ

Table 3: Mutation transition probability matrix.
The maximal value of the expected number of generations for the (2 + 2) to reach a population containing the
optimal individual x0 is the time when the EA starts from (x4 , x4 ). Because of the elitist selection, the only
possible offspring population is (x3 , x3 ) or (x2 , x2 ). Since the event of going from (x4 , x4 ) to (x3 , x3 ) happens
only if both x4 s mutate into x3 , the probability of this event is 0.5 · 0.5 = 0.25. Consequently, the probability
that the event of going from (x4 , x4 ) to (x2 , x2 ) happens is 1 − 0.25 = 0.75. Thus, according to the mutation
probability transition matrix, the EA reaches the optimum along the road (x4 , x4 ) → (x3 , x3 ) → (x0 , x0 ) with
probability 0.25, while it does so along the road (x4 , x4 ) → (x2 , x2 ) → (x1 , x1 ) → (x0 , x0 ) with probability
0.75, so that
m(2) (x4 , x4 ) = 2 · 0.25 + 3 · 0.75 = 2.75.
This demonstrates explicitly that the maximal value of the expected number of generations that the (1+1)
EA needs to reach an optimum is shorter than that the (2 + 2) EA needs, since
m(1) (x4 ) = 2.5 < m(2) (x4 , x4 ) = 2.75.

(36)

Furthermore, the reasoning above generalizes to the case when µ > 2 and shows that
m(µ) (x4 , . . . , x4 ) = 2 · 0.5µ + 3 · (1 − 0.5µ ),
thereby demonstrating that m(µ) (x4 , . . . , x4 ) is a strictly increasing function of the population size µ (increasing the population size also increases the maximal value of the expected number of generations).
Now observe that
m(1) (x4 ) − m(µ) (x4 , x4 )
is a continuous function of ǫ so that for small enough ǫ Inequality (36) as well as the conclusion in the
paragraph above still hold. Moreover, notice that the continuity argument implies that the elitist selection
can also be alleviated to certain non-elitist selection (non-best individuals may replace the parent individual
but with tiny probabilities) so that all the same conclusions remain valid.

4.5

a-Scalability and â-Scalability May Not Happen for Elitist EAs using Global
Mutation

The following modification of the example in the previous subsection shows that increasing the population
size may increase, rather than reduce, the average value of the expected number of generations, regardless of
whether the population is chosen uniformly at random from the set of all transient states or from the set of
all possible states. Equivalently, a-scalability(µ) < 1 and â-scalability(µ) < 1 for some µ ≥ 2.
The fitness function is given in Table 4.
state
fitness

x0
5

x1
4

x2
3

x3
2

xi (i = 4, · · · , 103)
1

Table 4: Fitness function.
Consider the following (µ + µ) EA (=(1 + µ) EA): the best individual is replicated by µ copies and each
copy generates a child via mutation; the best individual is replaced only when a child is better than it. The

16

state
x0
x1
x2
x3
xi (i ≥ 4)

x0
1 − 4ǫ
1 − 4ǫ
ǫ
1 − 4ǫ
ǫ

x1
ǫ
ǫ
1 − 4ǫ
ǫ
ǫ

x2
ǫ
ǫ
ǫ
ǫ
0.5

x3
ǫ
ǫ
ǫ
ǫ
0.5 − 3ǫ

xi (i ≥ 4)
0.01ǫ
0.01ǫ
0.01ǫ
0.01ǫ
0.01ǫ

Table 5: Mutation transition probability matrix.
mutation transition probabilities appear in Table 5, where ǫ ≥ 0 is a sufficiently small constant just as in the
previous example.
The only difference from the previous example is that now there are 100 “bad” states with the same largest
expected number of generations (rather than only a single state, as in the previous example), compared with
only 4 “good” states with a smaller expected number of generations. Thus the average value of the expected
number of generations is almost the same as the maximal value of the expected number of generations. The
parameter ǫ can be chosen sufficiently small and also elitist selection can be alleviated according to the same
type of continuity argument as in the previous example, of course, to show that the (1 + 1) EA outperforms
the (2 + 2), (3 + 3) or (4 + 4) EA.

5

General Studies: Conditions for Superlinear ρ-Scalability to Take
Place

5.1

General Condition for Superlinear ρ-Scalability to Take Place

In the current subsection we present a rather general sufficient and necessary condition for superlinear scalability to take place that applies to both elitist and non-elitist EAs. The condition is based on the concept of
a “road”. Intuitively, a road is a transition path between two states X and Y . A rigorous definition appears
below [37].
Definition 9. Given two states X, Y ∈ S (µ) , if there exists k states X0 = X → X1 → · · · → Xk = Y such
that
P (X0 , X1 ) · · · P (Xk−1 , Xk+1 ) > 0,
then {X0 , · · · , Xk } is called a road from X to Y . We also say that k is the length of the road. We write
road(X, Y, k) to denote the set of all roads from X to Y having length k.
(µ)

(µ)

Let P (road(X, Sopt (x), k)) denote the probability of going from X to the set Sopt (x) via “roads” of length
k.
A general sufficient and necessary condition for superlinear scalability to take place appears in the following
theorem. The theorem is largely based on the classical Gelfand’s spectral radius formula.
Theorem 2. Suppose we are given a (1+1) EA and a (µ+µ) EA (where µ ≥ 2) that exploit identical mutation
operator to maximize the same fitness function. For the (µ + µ) EA, supperlinear scalability happens if and
(µ)
only if there exists some k > 0 and for X ∈ Snon ,

k
(µ)
P (road(X, Sopt , k) ) > 1 − 1 − µ(1 − ρ(Q(1) )) .

(37)

Proof. (1) The proof that the condition is sufficient.
(µ)
Suppose Inequality (37) holds for all populations X in the set Snon . It follows from the assumption that

k
(µ)
max P (Φk ∈ Snon
| Φ0 = X) < 1 − µ(1 − ρ(Q(1) ) .
(µ)

X∈Snon

17

Rewriting the inequality above in terms of the ∞-norm, we obtain,

k
k (Q(µ) )k k∞ < 1 − µ(1 − ρ(Q(1) ) .

(38)

Since the spectral radius of a matrix is not bigger than its maximum norm [30, p.619],
ρ((Q(µ) )k ) ≤k (Q(µ) )k k∞ ,
so that

1/k

1/k 
ρ(Q(µ) ) = ρ((Q(µ) )k )
.
≤ k (Q(µ) )k k∞

Combining Inequality (38) with the above inequality yields


ρ(Q(µ) ) < 1 − µ 1 − ρ(Q(1) ) ,
1 − ρ(Q(µ) )
> µ.
1 − ρ(Q(1) )

This means that superlinear scalability takes place.
(2) The proof that the condition is necessary.
(µ)
Suppose Inequality (37) does not hold. This means that for any k > 0, there exists some X ∈ Snon such
that

k
(µ)
P (road(X, Sopt , k) ) ≤ 1 − 1 − µ(1 − ρ(Q(1) ) .
(39)
It follows then that for any k > 0


k
(µ)
P (Φk ∈ Sopt | Φ0 = X) ≤ 1 − 1 − µ(1 − ρ(Q(1) )) ,

k
(µ)
| Φ0 = X) ≥ 1 − µ(1 − ρ(Q(1) )) ,
P (Φk ∈ Snon

and this, in turn, implies that


k
(µ)
| Φ0 = Y ) ≥ 1 − µ(1 − ρ(Q(1) )) .
max P (Φk ∈ Snon
(µ)

Y ∈Snon

Rewriting the inequality above in terms of the ∞-norm we deduce that,

k
k (Q(µ) )k k∞ ≥ 1 − µ(1 − ρ(Q(1) )) .

Taking the limit as k → +∞, and applying Gelfand’s spectral radius formula, we obtain:
ρ(Q(µ) ) = lim

k→∞

so that



k (Q(µ) )k k∞

1/k

ρ(Q(µ) ) ≥ 1 − µ(1 − ρ(Q(1) )),
1 − ρ(Q(µ) )
≤ µ.
1 − ρ(Q(1) )
This means that no superlinear scalability takes place.

18

,

5.2

Sufficient and Necessary Condition for Superlinear ρ-Scalability to Happen
for Elitist EAs

The sufficient and necessary condition for the superlinear scalability to occur that has been established in
Theorem 2 can be reformulated in a more explicit fashion when dealing with elitist EAs. We call this
reformulation “road through bridge”. A detailed analysis is provided in the current subsection.
Definition 10. An individual y is called a bridgeable point of an individual x if y satisfies the following
conditions:
1. the fitness of x is larger than that of y: f (x) ≥ f (y);
(1)

2. the probability of going from x to the set Shigh (x) via mutation is smaller than that from y to the same
(1)

set Shigh (x).
(1)

(1)

(40)

PM (x, Shigh (x)) ≤ PM (y, Shigh (x)).

The term “bridgeable point” is motivated by the following intuitive notion: y may serve as a “bridge” for
x to step towards a higher fitness level.
To achieve superlinear scalability, it is important for elitist EAs to go through some “bridgeable point”.
Intuitively there are two types of roads going from a state towards a higher fitness level. One is the road
going from its current fitness level directly towards the higher fitness level; another type is the road through
some bridgeable point before reaching a higher fitness level.
(µ)
Given a population X the best individual of which is x and a population Y in the set Shigh (x), the roads
from X to Y can be classified into two categories:
• Road through bridge {X0 = X, X1 , · · · , Xk−1 , Xk = Y }: at least one of the intermediate populations
X1 , · · · , Xk−1 contains a bridgeable point of x.
• Road over gap {X0 = X, X1 , · · · , Xk−1 , Xk = Y }: none of the intermediate populations X1 , · · · , Xk−1
contains a bridgeable point of x.
(µ)

(µ)

Let P (road(X, Shigh (x), k) through bridge) denote the probability of going from X to the set Shigh (x) via
“roads through bridge” of length k.
(µ)
(µ)
Likewise, let P (road(X, Shigh (x), k) over gap) denote the probability of going from X to the set Shigh (x)
via “roads over gap” of length k.
The following theorem provides a sufficient and necessary condition for superlinear scalability to occur in
case of elitist EAs in terms of the ”road through bridge”.
Theorem 3. Suppose we are given a (1 + 1) elitist EA and a (µ + µ) elitist EA (where µ ≥ 2) that exploit
identical mutation operator to maximize the same fitness function. Consider an individual xρ such that
(1)
xρ = arg max{P (x, x); x ∈ Snon
}.

For the (µ + µ) EA, supperlinear ρ-scalability happens if and only if the following road through bridge
(1)
(µ)
condition holds: there exists some k > 0, such that for any x ∈ Snon and any X ∈ Ssame (x),
(µ)

(µ)

P (road(X, Shigh (x), k) over gap) + P (road(X, Shigh (x), k) through bridge)
k

>1 − (1 − µ(1 − P (xρ , xρ )) .

(41)

Proof. For the (1 + 1) elitist EA, Lemma 10 tells us that
ρ(Q(1) ) = P (xρ , xρ ).
For the (µ + µ) EA, from Lemma 11, it follows that
ρ(Q(µ) ) = max ρ(Q(µ)
x,x ).
(1)

x∈Snon

19

(1)

(1)

Since the set Snon is finite, there is some x ∈ Snon such that
ρ(Q(µ) ) = ρ(Q(µ)
x,x ).

(42)
(µ)

Thanks to elitist selection, Inequality (41) is equivalent to saying that for any X ∈ Ssame (x)

k
(µ)
P (road(X, Shigh (x), k) > 1 − 1 − µ(1 − ρ(Q(1) ) .

The desired conclusion now follows directly from Theorem 2 applied to the Markov transition submatrix
(µ)
(µ)
(µ)
(µ)
(µ)
Qx,x and replacing Snon and Sopt in Theorem 2 by Ssame (x) and Shigh (x) respectively.

5.3

Necessary Condition for Superlinear ρ-Scalability to Happen for Elitist EAs

The following theorem informs us further that the existence of a “road through bridge” is a necessary
(µ)
condition for superlinear scalability to take place. Let Sbridge (x) denote the set of all populations which
contain a bridgeable point of x.
Theorem 4. Suppose we are given a (1 + 1) elitist EA and a (µ + µ) elitist EA (where µ ≥ 2) that exploit
identical mutation operator to maximize the same fitness function. Consider an individual xρ such that
(1)
xρ = arg max{P (x, x); x ∈ Snon
}.

Let Xρ = (xρ , · · · , xρ ). If for some population size µ ≥ 2, and for any k > 0
(µ)

P ( Road(Xρ , Shigh (xρ ), k) through bridge) = 0,

(43)

then no supperlinear ρ-scalability ever takes place for such a µ.
Proof. For the (1 + 1) elitist EA, from Lemma 10,
ρ(Q(1) ) = P (xρ , xρ ).
(µ)

For a (µ + µ) elitist EA (where µ ≥ 2), consider the Markov transition probability submatrix Qxρ ,xρ .
(µ)
(µ)
(µ)
(µ)
Split the set Ssame (xρ ) into two subsets: Sbridge (xρ ) and Ssame (xρ ) \ Sbridge (xρ ).
From the condition of the theorem, for any k > 0,
(µ)

P (Road(Xρ , Shigh (xρ ), k) through bridge) = 0,
(µ)

(µ)

(µ)

so that the probability of going from any state in the set Ssame (xρ ) \ Sbridge (xρ ) to the set Sbridge (xρ ) is 0.
(µ)

Hence the matrix Qxρ ,xρ is reducible. We write it in the following form

 (µ)
Q̂xρ ,xρ O
,
∗
∗∗
(µ)

(µ)

(µ)

where Q̂xρ ,xρ represents the transition probability submatrix within the set Ssame (xρ ) \ Sbridge (xρ ). The ∗
(µ)

(µ)

part represents transition probabilities from the set Sbridge (xρ ) to the set Ssame (xρ ), and the part labelled
with the ∗∗ symbol stands for the transition probabilities within the set
For any population X = (x1 , · · · , xµ ) in the set
“bridgeable point” of xρ , we have

(µ)
Ssame (xρ )

(1)

\

(µ)
Sbridge (xρ ).

(µ)
Sbridge (xρ ),

(1)

since none of its individuals is a

PM (x, Shigh (xρ )) ≤ PM (xρ , Shigh (xρ )) = 1 − ρ(Q(1) ).
According to the mutation property (25), for any µ > 2,
(µ)

P (X, Shigh (xρ )) < µ(1 − ρ(Q(1) )).
20

O denotes a zero matrix.

(µ)

(µ)

Since the inequality holds for any population in the set Ssame (xρ ) \ Sbridge (xρ ), we have
min

(µ)

(µ)
(µ)
X∈Ssame (xρ )\Sbridge (xρ ))

(µ)
P (X, Ssame
(xρ ) \ Sbridge (xρ )) ≥ 1 − µ(1 − ρ(Q(1) )).

According to Lemma 12,
(1)
)).
ρ(Q̂(µ)
xρ ,xρ ) ≥ 1 − µ(1 − ρ(Q
(µ)

Since ρ(Q(µ) ) ≥ ρ(Q̂xρ ,xρ ), we deduce that
1 − ρ(Q(µ) ) ≤ µ(1 − ρ(Q(1) )),
which means that no superlinear ρ-scalability takes place.
From the theorem, we deduce two necessary conditions for superlinear ρ-scalability to happen as follows.
First of all, bridgeable point(s) must exist. Furthermore, bridgeable point(s) must be preserved during
selection. Consequently, if there is no population diversity, then there is no superlinear ρ-scalability.

6
6.1

Case Study 1: No Superlinear ρ-Scalability on Non-bridgeable
Fitness Landscapes
Superlinear ρ-Scalability Never Happens to Non-bridgeable Fitness Landscapes

Definition 11. Given a fitness function f (x), we say that the fitness landscape assocated with a (1 + 1) EA
is non-bridgeable meaning that for any two non-optimal states x and y, if x has a better fitness than y (that
(1)
is f (x) ≥ f (y)), then starting from x, the EA has a larger probability to enter a higher fitness level, Shigh (x)
(1)

than starting from y (and arriving at the same subset Shigh (x)), that is
(1)

(1)

PM (x, Shigh (x)) > PM (y, Shigh (x)).
In terms of the average convergence rate, using a population delivers no superlinear scalability if the
fitness landscape associated with the (1 + 1) EA is non-bridgeable. The following theorem demonstrates this.
Proposition 1. Suppose we are given a (1 + 1) elitist EA and a (µ + µ) elitist EAs (where µ ≥ 2) that exploit
identical mutation operator for maximizing the same fitness function. If the fitness landscape associated with
the (1 + 1) EA is non-bridgeable, then no superlinear ρ-scalability happens.
Proof. Let xρ be an individual such that
(1)
xρ = arg max{P (x, x); x ∈ Snon
},

and Xρ = (xρ , · · · , xρ ). It is easy to see there is no bridgeable point for Xρ , so that for k > 0
(µ)

P (Road(Xρ , Shigh (xρ ), k) through bridge) = 0.
The desired conclusion now follows directly from Theorem 4.
Analogous results have been established under ∞-scalability and a-scalability for non-bridgeable fitness
landscapes which are called monotonic fitness landscapes in He and Chen [38].

21

6.2

An Example of Non-bridgeable Fitness Landscapes

Consider the average capacity 0-1 knapsack problem [39], described as follows: let x be a binary string
(s1 , · · · , sn ) ∈ {0, 1}n,
max
x

n
X

vi si

subject to

n
X

wi si ≤ C,

i=1

i=1

Pn
where vi is the value of the i-th item, wi its weight and C = 0.5 i=1 wi is the capacity.
Consider the instance where the values and the weights of the items vi = wi = 1 for i = 1, · · · , n, and
C = 0.5n. The fitness function for this instance is similar to the One-Max function.
 Pn
Pn
si ,
if
i=1 si ≤ 0.5n,
i=1
f1 (x) =
(44)
infeasible, otherwise.
An individual is represented by a binary string. The (µ + µ) EA for the instance uses the following
mutation and selection operators.
• Randomised Initialisation: generate µ feasible solutions (individuals) at random.
• Bitwise Mutation: given a string x, flip each bit independently with flipping probability 1/n. If an
individual generates an infeasible offspring, the offspring is rejected immediately, while the parent is
automatically transferred into the intermediate population of children after mutation.
• Elitist Selection: any elitist selection operator will do.
The fitness landscape associated with the (1 + 1) EA is non-bridgeable. According to Proposition 1,
superlinear ρ-scalability never happens, meaning that using a population does not increase the average
convergence rate. Similar results have been established before in terms of the expected number of generations
it takes to reach the optimum for the One-Max problem. Sudholt [40] proved that the (1+1) EA is the best EA
to tackle this problem. Jansen et al. [13] also analysed the relationship between the runtime and population
size but under the big O notation.

7

Case Study 2: Superlinear ρ-Scalability on Bridgeable Fitness
Landscapes

7.1

Superlinear ρ-Scalability May Happen on Certain Bridgeable Fitness Landscapes

Definition 12. Given a fitness function f (x), we say that the fitness landscape associated with a (1 + 1) is
bridgeable if there exit two non-optimal states x and y where x has a better fitness than y (that is f (x) ≥ f (y))
(1)
while the probability of entering a higher fitness level Shigh (x) starting from the state x is not less than that
starting from y, that is
(1)

(1)

PM (x, Shigh (x)) ≤ PM (y, Shigh (x)).
Proposition 2 below investigates a particular scenario where “roads through bridge” exist on bridgeable fitness landscapes, thereby demonstrating that the use of a population may be helpful when coping
with bridgeable fitness landscapes in the sense that superlinear scalability could be achieved under certain
conditions.
Proposition 2. Suppose we are given a (1 + 1) elitist EA and a (µ + µ) elitist EAs (where µ ≥ 2) that
exploit identical mutation operator to maximize the same fitness function. Suppose that the fitness landscape
associated with (1 + 1) EA is bridgeable. Assume further, that the following conditions hold:
1. Fitness diversity preservation: given Φt = X and Φt+1/2 = Y , if there exists one or more individuals in
X or Y whose fitness is less than that of the best individual of X, then at least one of these individuals
must be selected into the next population with positive probability.
22

2. Existence of bridgeable points: let xρ be a state at the 2nd highest fitness level. We require that
P (xρ , xρ ) = max P (z, z).
(1)

z∈Snon

All other states at lower fitness levels are bridgeable points of xρ . The probability of going from a
bridgeable point y to the optimal set via mutation is larger than that from xρ by a factor of µ:
(1)

(1)

PM (y, Sopt ) ≥ µPM (x, Sopt ).

(45)

3. Pass through bridgeable points: The probability of going from the xρ above to the set of bridgeable
points via mutation is large enough in the following sense:
(1)

(1)

PM (xρ , Sbridge (xρ )) ≥ µPM (xρ , Sopt ).

(46)

Then superlinear ρ-scalability happens for such a µ.
Proof. For the (µ + µ) EA, let X be any population in the non-optimal set. Now consider the probability
of going from X to the optimal set in two generations. It is convenient to analyze two complementary cases
according to the different types of the population X.
Case 1 The population X = (xρ , xρ , . . . , xρ ) consists of the repeated copies of the fittest individual xρ : .
From Conditions (45) and (46), the probability of going from X to the optimal set in two generations is
greater than
(µ)

(µ)

(µ)

P (Φt+2 ∈ Sopt | Φt+1 ∈ Sbridge (xρ )) · (P (Φt+1 ∈ Sbridge (xρ ) | Φt = X)
(1)

≥ µ2 (P (xρ , Sopt ))2
= µ2 (1 − P (xρ , xρ ))2 .
Case 2 A population X = (x1 , · · · , xµ ) that contains at least one bridgeable point of xρ (recall condition
2).
From Condition (46), the probability of going from X to the optimal set in two generations is greater
than
(µ)

(µ)

(µ)

P (Φt+2 ∈ Sopt | Φt+1 ∈ Sopt ) · P (Φt+1 ∈ Sopt | Φt = X)
(1)

≥ µ(P (xρ , Sopt ))
= µ(1 − P (xρ , xρ ))
≥ µ2 (1 − P (xρ , xρ ))2 .
Thus, after examining the two mutually exhaustive cases above, we deduce that for all populations X in
the non-optimal set,
(µ)

P (Φt+2 ∈ Sopt | Φt = X) ≥ µ2 (1 − P (xρ , xρ ))2
> 1 − (1 − µ(1 − P (xρ , xρ ))2 .
The inequality above shows that the road through bridge condition (41) holds implying that the superlinear
scalability takes place thanks to theorem 3.

7.2

An Example of Bridgeable Fitness Landscapes

Consider another instance of the average capacity 0-1 knapsack problem: the value of the item v1 = n while
the remaining items have values vi = 1 for i = 2, · · · , n; the weight of the item w1 = n − 1, while the weights

23

of the remaining items wi = 1 for i = 2, · · · , n. The capacity C = n − 1. The fitness function resembles a
fully deceptive function [11].

if s1 = 1, s2 = · · · = sn = 0;
 n,
Pn
s
,
if s1 = 0;
(47)
f2 (x) =
i=2 i

infeasible, otherwise.

An individual is represented by a binary string. The (µ + µ) EA for the instance uses the following
mutation and selection operators.
• Randomised Initialisation: generate µ feasible solutions (individuals) at random.
• Bitwise Mutation: given a binary string x, flip each bit independently with probability 1/n. If an
individual generates an infeasible offspring, the offspring is rejected immediately and the parent is
transferred into in the population of children.
• Elitist Proportional Selection: the best individual is replaced if the best child individual is fitter,
while the non-best individuals are selected from the two populations X and Y (disregarding the best
individual) via fitness proportional selection.
Notice that the self-transition probability, P (x, x), is maximal when x = (0, 1, · · · , 1). The unique optimal
solution having the highest fitness level, n, is (1, 0, · · · , 0). The unique solution having the second highest
fitness level, namely n − 1, is x = (0, 1, · · · , 1). All the other feasible individuals (solutions) are bridgeable
points of x.
The event of going from x = (0, 1, · · · , 1) to (1, 0, · · · , 0) via mutation occurs if and only if all of the bits
are flipped. The probability of this event happening is
 n
1
(1)
PM (x, Sopt ) =
.
n

The event of going from any other feasible state y (except (1, 0, · · · , 0) and (0, 1, · · · , 1)) to (1, 0, · · · , 0)
happens if and only if the first bit is flipped, all the other 1-valued bits are flipped and all the other 0-valued
bits are unchanged. Let | y | denote the number of 1-valued bits in y. Since y is a feasible solution but except
(1, 0, · · · , 0) and (0, 1, · · · , 1) so that | y |< n − 1. The probability of this event happening is:
(1)
PM (y, Sopt )

n−|y|−1  |y|+1

1
1
.
= 1−
n
n

The event of going from the only individual x = (0, 1, · · · , 1) at the second highest fitness level to the set
of bridgeable points happens if and only if the first bit is not flipped and at least one of the other bits is
flipped. The probability of this event is then
(1)
PM (x, Sbridge (x))

=



1
1−
n

 n−1
n−k−1
X n − 1  1 k 
1
1−
.
n
n
k
k=1

Thus, conditions (45) and (46) hold for any population size µ ≤ n implying that superlinear ρ-scalability
happens for µ ≤ n.

8
8.1

Conclusions and Discussions
Conclusions

A novel approach, based on the fundamental matrix of absorbing Markov chains, is introduced to study
population scalability of EAs. The spectral radius and matrix norms of the fundamental matrix are used as a
measure of the performance of an EA. The reciprocal of the spectral radius 1/ρ(N) is the average convergence
rate interpreted through the notion of the geometric mean. The ∞-norm k N k∞ is the maximum value of
24

the expected number of generations to encounter an optimum solution for the first time. The a-norm k N ka
is the average value of the expected number of generations to encounter an optimum solution for the first
over all transient initial states. Three different notions of population scalability are proposed in the paper:
ρ-scalability (based on the spectral radius of the fundamental matrix), ∞-scalability (based on the ∞-norm
of the fundamental matrix) and a-scalability (based on the a-norm of the fundamental matrix).
The main results of the paper may be summarized in two parts.
1. Theorem 1 shows that ρ-scalability always happens for elitist EAs using global mutation. For a
population-based EA using identical mutation, the average convergence rate of a (µ + µ) EA (where
µ ≥ 2) is always larger than that of the (1 + 1) EA. Nonetheless, a-scalability and ∞-scalability may
not take place. Using a larger population size sometimes will increase, rather than reduce, the expected
number of generations to encounter an optimal solution for the first time (when measured either in
terms of the maximum value or the average value). This fact is counterintuitive to the commonly
accepted “rule of thumb” in evolutionary computation.
2. Theorems 2, 3 and 4 provide sufficient and/or necessary conditions for the superlinear ρ-scalability to
take place. The conditions indicate that for the elitist EAs optimizing the same fitness function and
using identical mutation operators, the average convergence rate of a (µ + µ) EA (where µ ≥ 2) is more
than µ times that of the corresponding (1 + 1) EA if and only if the probability of passing through the
“roads through bridge” is sufficiently large for the (µ + µ) EA.
In order to illustrate the theoretical findings above, two cases studies are provided in the paper. The first
case study shows that the average convergence rate of a (µ + µ) EA (where µ ≥ 2) is never larger than µ
times that of the (1 + 1) EA on any non-bridgeable fitness landscapes. The second one illustrates that the
average convergence rate of a (µ + µ) EA (where µ ≥ 2) might be larger than µ times that of the (1 + 1) EA
on certain bridgeable fitness landscapes.
The notion of population scalability is not intended to compare the performance of the corresponding
(1 + 1) and (µ + µ) EAs on all instances of a given combinatorial optimization problem such as, for instance,
the 0-1 knapsak problem, at once. Indeed, as we have seen in Subsections 6.2 and 7.2, for the same pair
of the corresponding (1 + 1) and (µ + µ) EAs, population scalability may take place on one instance, and,
simultaneously, not on another instance of the 0-1 knapsak problem, so that it is meaningless to consider
population scalability on all instances at once.
While the approach based on the notion of the fundamental matrix is rather virtuous for analysing and
understanding the notion of population scalability of EAs, it is unlikely to be practical when it comes to
calculating ρ-population scalability for a specified pair of EAs optimizing a given fitness function. This is
due to the fact that the fundamental matrix is usually difficult to compute. Likewise the calculation of
∞-scalability and a-scalability is not an easy job.
There are still many open questions some of which are listed below. Can we pin down any insightful
sufficient and/or necessary conditions that the expected number of generations that a (µ + µ) EA (where
µ ≥ 2) takes to encounter an optimal solution for the first time is greater than that the corresponding (1 + 1)
EA (measure by either the average value or maximum value) does? Can we address the same question in
terms of the superlinear scalability? How to determine the threshold of the population size when an EA loses
its superlinear scalability? Is there any feasible approach to calculating or, at least, estimating the population
scalability?

8.2

Discussions: Other Types of EAs

The condition that the EAs are convergent is not necessary. If an EA is not convergent, then ρ(Q(µ) ) = 1.
In this case, the corresponding notion of the population scalability is revised as follows:

ρ(N(1) )

if ρ(Q(1) ) < 1,
 ρ(N(µ) ) ,
(48)
ρ-scalability(µ) =
+∞,
if ρ(Q(1) ) = 1, ρ(Q(µ) ) < 1,


indefined, if ρ(Q(1) ) = 1, ρ(Q(µ) ) = 1.
If a mutation operator is not global, we can easily revise it exploiting mixed strategy [32]. We apply this
mutation operator with the probability 1 − ǫ and apply a global mutation with the probability ǫ for a small
ǫ > 0. Evidently, the mixed strategy mutation operator obtained in this manner is global.
25

Crossover is widely used in EAs. Since a (1 + 1) EA doesn’t include any crossover operator, it is not an
appropriate candidate as the benchmark EA. Instead, a (2 + 2) EA with crossover would play the role of the
benchmark EA. Thus, the notion of scalability would then be revised accordingly:
ρ-scalability(µ) =

ρ(N(2) )
.
ρ(N(µ) )

(49)

The EAs above can still be modelled by absorbing Markov chains and Theorem 2 is applicable.
Nonetheless, it seems rather difficult to apply the fundamental matrix approach to EAs that exploit
time-dependent genetic operators.

Acknowledgements
We would especially like to thank Professor Günter Rudolph who has been involved in initializing the research
issue of population scalability. This work is supported by the EPSRC under Grant EP/I009809/1 and
National Natural Science Foundation of China under Grant 61170081.

References
[1] A. Prügel-Bennett. Benefits of a population: five mechanisms that advantage population-based algorithms. IEEE Transactions on Evolutionary Computation, 14(4):500–517, 2010.
[2] J. Suzuki. A Markov chain analysis on simple genetic algorithms. IEEE Transactions on Systems, Man
and Cybernetics, 25(4):655–659, 1995.
[3] J. He and L. Kang. On the convergence rate of genetic algorithms. Theoretical Computer Science, 229
(1-2):23–39, 1999.
[4] G. Rudolph. Finite Markov chain results in evolutionary computation: a tour d’horizon. Fundamenta
Informaticae, 35(1):67–89, 1998.
[5] J. He and X. Yao. Towards an analytic framework for analysing the computation time of evolutionary
algorithms. Artificial Intelligence, 145(1-2):59–97, 2003.
[6] D.E. Goldberg, K. Deb, and J.H. Clark. Genetic algorithms, noise, and the sizing of populations.
Complex Systems, 6:333–362, 1992.
[7] H. Mühlenbein and D. Schlierkamp-Voosen. The science of breeding and its application to the breeder
genetic algorithm (BGA). Evolutionary Computation, 1(4):335–360, 1993.
[8] J. Arabas, Z. Michalewicz, and J. Mulawka. GAVaPS-a genetic algorithm with varying population size.
In Proceedings of the IEEE Conference on World Congress on Computational Intelligence, pages 73–78.
IEEE, 1994.
[9] A.E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE
Transactions on Evolutionary Computation, 3(2):124–141, 1999.
[10] G. Harik, E. Cantú-Paz, D.E. Goldberg, and B.L. Miller. The gambler’s ruin problem, genetic algorithms,
and the sizing of populations. Evolutionary Computation, 7(3):231–253, 1999.
[11] J. He and X. Yao. From an individual to a population: An analysis of the first hitting time of populationbased evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):495–511, 2002.
[12] J. He and X. Yao. Analysis of scalable parallel evolutionary algorithms. In Proceedins of 2006 IEEE
World Congress on Computational Intelligence, pages 427–434, Vancouver, Canada, July 2006. IEEE
Press.

26

[13] T. Jansen, K.A. de Jong, and I. Wegener. On the choice of the offspring population size in evolutionary
algorithms. Evolutionary Computation, 13(4):413–440, 2005.
[14] J. Lässig and D. Sudholt. Adaptive population models for offspring populations and parallel evolutionary
algorithms. In Hans-Georg Beyer and William B. Langdon, editors, Proceedings of the 11th International
Workshop Foundations of Genetic Algorithms, pages 181–192, Schwarzenberg, Austria, 2011. ACM.
[15] J. Jägersküpper and C. Witt. Rigorous runtime analysis of a (µ+ 1) ES for the sphere function. In
Hans-Georg Beyer and Una-May O’Reilly, editors, Proceedings of the 2005 Conference on Genetic and
Evolutionary Computation, pages 849–856, Washington DC, USA, 2005. ACM.
[16] T. Jansen and I. Wegener. Real royal road functions–where crossover provably is essential. Discrete
Applied Mathematics, 149(1-3):111–125, 2005.
[17] C. Witt. Runtime analysis of the (µ+ 1) ea on simple pseudo-Boolean functions. Evolutionary Computation, 14(1):65–86, 2006.
[18] C. Witt. Population size versus runtime of a simple evolutionary algorithm. Theoretical Computer
Science, 403(1):104–120, 2008.
[19] T. Storch. On the choice of the parent population size. Evolutionary Computation, 16(4):557–578, 2008.
[20] P. S. Oliveto, J. He, and X. Yao. Analysis of the (1+1)-EA for finding approximate solutions to vertex
cover problems. IEEE Transactions on Evolutionary Computation, 13(5):1006 –1029, 2009.
[21] 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.
[22] 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, 39(5):1092–1106, 2009.
[23] O. Giel and P.K. Lehre. On the effect of populations in evolutionary multi-objective optimisation.
Evolutionary Computation, 18(3):335–356, 2010.
[24] P.S. Oliveto, J. He, and X. Yao. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281–293,
2007.
[25] D.B. Fogel. Asymptotic convergence properties of genetic algorithms and evolutionary programming:
analysis and experiments. Cybernetics and Systems, 25(3):389–407, 1994.
[26] Y. Zhou, J. He, and Q. Nie. A comparative runtime analysis of heuristic algorithms for satisfiability
problems. Artificial Intelligence, 173(2):240–257, 2009.
[27] C. Coello and A. Carlos. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art. Computer Methods in Applied Mechanics and
Engineering, 191(11-12):1245–1287, 2002.
[28] Y. Zhou and J. He. A runtime analysis of evolutionary algorithms for constrained optimization problems.
IEEE Transactions on Evolutionary Computation, 11(5):608–619, 2007.
[29] C.M. Grinstead and J.L. Snell. Introduction to Probability. American Mathematical Society, 1997.
[30] C.D. Meyer. Matrix analysis and applied linear algebra: solutions manual. SIAM, 2000.
[31] R.S. Varga. Matrix Iterative Analysis. Springer, 2009.
[32] J. He, F. He, and H. Dong. Pure strategy or mixed strategy? In Jin-Kao Hao and Martin Middendorf, editors, Evolutionary Computation in Combinatorial Optimization (LNCS 7245), pages 218–229.
Springer, 2012.
27

[33] D. Andre and J.R. Koza. A parallel implementation of genetic programming that achieves superlinear
performance. Information Sciences, 106(3-4):201–218, 1998.
[34] E. Alba and M. Tomassini. Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary
Computation, 6(5):443–462, 2002.
[35] E. Alba. Parallel evolutionary algorithms can achieve superlinear performance. Information Processing
Letters, 82(1):7–13, 2002.
[36] D.H. Wolpert and W.G. Macready. No free lunch theorems for optimization. IEEE Transactions on
Evolutionary Computation, 1(1):67–82, 1997.
[37] J. He, L. Kang, and Y. Chen. Convergence of genetic evolution algorithms for optimization. International
Journal of Parallel, Emergent and Distributed Systems, 5(1):37–56, 1995.
[38] J. He and T. Chen. A general analysis of evolutionary algorithms for hard and easy fitness functions.
CoRR, abs/1203.6286, 2012.
[39] S. Martello and P. Toth. Knapsack Problems. John Wiley & Sons, Chichester, 1990.
[40] D. Sudholt. General lower bounds for the running time of evolutionary algorithms. In Proceedings of
Parallel Problem Solving from Nature–PPSN XI, pages 124–133. Springer, 2011.

28

