1

An Analytic Expression of Relative Approximation
Error for a Class of Evolutionary Algorithms

arXiv:1511.03483v3 [cs.NE] 24 Nov 2016

Jun He

Abstract—An important question in evolutionary computation
is how good solutions evolutionary algorithms can produce. This
paper aims to provide an analytic analysis of solution quality in
terms of the relative approximation error, which is defined by the
error between 1 and the approximation ratio of the solution found
by an evolutionary algorithm. Since evolutionary algorithms are
iterative methods, the relative approximation error is a function
of generations. With the help of matrix analysis, it is possible
to obtain an exact expression of such a function. In this paper,
an analytic expression for calculating the relative approximation
error is presented for a class of evolutionary algorithms, that is,
(1+1) strictly elitist evolution algorithms. Furthermore, analytic
expressions of the fitness value and the average convergence rate
in each generation are also derived for this class of evolutionary
algorithms. The approach is promising, and it can be extended
to non-elitist or population-based algorithms too.

I. I NTRODUCTION
Evolutionary algorithms (EAs) have been widely used to
find good solutions to hard optimization problems. Many
experimental results claim that EAs can obtain good quality
solutions quickly. Nevertheless, from the viewpoint of the
N P -hard theory, no efficient algorithm exists for solving NPhard combinatorial optimization problems at the present and
possibly for ever. Therefore it is unlikely that EAs are efficient
in solving hard combinatorial optimization problems too.
Instead of searching for the exact solution to hard optimization
problems, it is more reasonable to expect that EAs are able to
find some good approximate solutions efficiently.
It is necessary to answer the question of how good solutions
EAs can produce to hard optimization problems in terms
of the approximation ratio. Current work focuses on the
approximation ratio of the solution found by an EA within
polynomial time. The research has attracted a lot of interests
in recent years. Various combinatorial optimization problems
have been investigated, including the minimum vertex cover
problem [1], [2], the partition problem [3], the set cover
problems [4], the minimum label spanning tree problem [5],
and many others.
This paper studies the approximation ratio of EAs from a
different viewpoint. It aims to estimate the relative approximation error of the best solution found by an EA in each
generation, but without considering whether the EA is an
approximation algorithm or not. The problem in this paper
is described as follows: Given an EA for maximizing a fitness
function f (x), let fopt be the optimal fitness and Ft the
expected fitness value of the best solution found in the tth
This work was supported by EPSRC under Grant No. EP/I009809/1
Jun He is with Department of Computer Science, Aberystwyth University,
Aberystwyth SY23 3DB, United Kingdom, Email: jun.he@aber.ac.uk

generation. The approximation ratio of the tth generation
solution is Ft /fopt . The approximation ratio of the optimal
solution is 1. The relative approximation error is
Et = 1 −

Ft
.
fopt

(1)

In [6], Et is called the performance ratio. In order to avoid
confusion with the approximation ratio, it is renamed the
relative approximation error. The relative approximation error
Et is a function of t. Our main research question is to find an
upper bound β(t) on the error Et .
The perfect answer is to obtain a function β(t) in a closed
form such that Et = β(t). For (1+1) strictly elitist EAs, such
an analytic expression has been constructed in this paper using
matrix analysis. To the best of our knowledge, this is the first
result of expressing the relative approximation error (also the
fitness value and the average convergence rate) in a closed
form for a class of EAs.
The paper is arranged as follows: Section II reviews the
links to related work. Section III defines the relative approximation error. Sections IV and VII conduct a case study.
Section V introduces Markov modelling. Section VI makes
a theoretical analysis. Section IX summarizes the paper.
II. L INKS

TO RELATED WORK

The relative approximation error belongs to the convergence
rate study of EAs, which can be traced back to 1990s [7]–[9].
This paper only investigates EAs for discrete optimisation,
although the converegnce rate of EAs for continuous optimization [10]–[12] is also important. EAs belong to iterative
methods. A fundamental question in iterative methods is the
convergence rate, which can be formalised as follow [9]. Since
the tth generation solution is a random variable, we let pt
be a vector representing its probability distribution over the
search space, π a vector such that π(Sopt ) = 1 for the optimal
solution set Sopt and π(Snon ) = 0 for the non-optimal solution
set Snon . The convergence rate problem asks the question how
fast pt converges to π. The goal is to obtain a bound β(t) such
that k pt −π k≤ β(t), where k · k is a norm. There are various
ways to assign the norm. For example, if the tth generation
solution is a binary string x1 · · · xn and the optimal solution
is 1 · · · 1, the norm is set to be the Hamming distance:
X
|1 − xi |.
(2)
k pt − π k=
i

In the current paper, the norm is set to be the relative
approximation error k pt − π k= 1 − Ft /fopt .
According to [13], there are two approaches to analyse the
convergence rate of EAs for discrete optimization. The first

2

approach is based on the eigenvalues of the transition submatrix associated with an EA. Suzuki [7] derived a lower bound
of convergence rate for simple genetic algorithms through
analysing eigenvalues of the transition matrix. Schmitt and
Rothlauf [14] found that the convergence rate is determined
by the second largest eigenvalue of the transition matrix. The
approach used in the current paper is the same as that in [7],
[14]. All are based on analysing the powers and eigenvalues
of the transition matrix. The other approach is based on
Doeblin’s condition [9], [15]. Using the minorisation condition
in Markov chain theory, He and Kang [9] proved that for the
EAs with time-invariant genetic operators, the convergence
rate can be upper-bounded by ǫt where ǫ ∈ (0, 1).
The research in this paper is also linked to fixed budge
analysis. Jansen and Zarges [16], [17] proposed fixed budget
analysis. It aims to find lower and upper bounds βlow (b)
and βup (b) such that βlow (b) ≤ fb ≤ βup (b) usually for a
fixed budget b. They investigated two algorithms: random local
search and the (1+1) EA and obtained such bounds on several
pseudo-Boolean optimization problems.
The convergence rate study can implement the same task as
fixed budget analysis does. Provided that 1 − fb /fopt ≤ β(b),
it is trivial to derive fb ≥ fopt (1 − β(b)). Nevertheless, there
are significant differences between the convergence rate study
and fixed budget analysis.
• The convergence rate study has existed in EAs for more
than two decades [7]–[9]. Fixed budget analysis was
recently proposed by Jansen and Zarges [17].
• The convergence rate study focuses on estimating the
error k pt − π k, where the norm k · k can be chosen
as the absolute error fopt − Ft , relative error 1 − Ft /fopt
or Hamming distance. Fixed budget analysis aims at
bounding fb for a fixed budget b (that is a fixed number
of generations) [17].
• In the convergence rate study, the upper bound β(t)
on k pt − π k usually is an exponential function or
combination of linear functions of t [9]. In fixed budget
analysis, the bound β(b) on fb may not be an exponential
function of b [17].
• In the convergence rate, the bound on k pt − π k holds
for all t. But in fixed budget analysis, the bound on fb
often is estimated for a fixed budget b [17].
• Matrix analysis is widely used in the convergence rate
study [7], [14], but it is not used in fixed budget analysis.
III. R ELATIVE APPROXIMATION

ERROR , FITNESS VALUE
AND AVERAGE CONVERGENCE RATE

Consider a maximization problem, that is, max{f (x); x ∈
S} where S is a finite set, and fopt > f (x) ≥ 0. For the
sake of analysis, let S = {0, 1, · · · , L} denote the set of all
solutions. We assume that
fmax = f (0) > f (1) ≥ · · · ≥ f (L) = fmin .
S is split into two subsets: the optimal solution set Sopt = {0}
and the set of non-optimal solutions Snon = {1, · · · , L}.
An EA for solving the above problem is regarded as an
iterative procedure: initially construct a population of solutions

Φ0 ; then given the tth generation population Φt , generate a
new population Φt+1 in a probabilistic way. This procedure
is repeated until an optimal solution is found. This paper
investigates a class of (1+1) elitist EAs which are described
in Algorithm 1. This kind of EAs is very popular in the
theoretical analysis of EAs.
Algorithm 1 A (1+1) Strictly Elitist EA
1: set t ← 0;
2: Φ0 ← choose a solution from S = {0, 1, · · · , L};
3: while Φt is not an optimal solution do
4:
Ψt ← mutate Φt ;
5:
if f (Ψt ) > f (Φt ) then
6:
Φt+1 ← select Ψt ;
7:
else
8:
Φt+1 ← select Φt ;
9:
end if
10:
t ← t + 1;
11: end while
The expression Φt = x means the tth generation individual
Φt at state x where Φt is a random variable and x its
value taken from S. The fitness of Φt is denoted by f (Φt ).
Since f (Φt ) is a random variable, we consider its expectation
def
Ft = E[f (Φt )]. The approximation ratio of the tth generation
individual is Ft /fopt . The approximation ratio of the optimal
solution is 1.
Definition 1: The relative approximation error of the tth
generation individual is defined by
Et = 1 −

Ft
.
fopt

(3)

There is a link between the relative approximation error
and the fitness value. From the definition of the relative
approximation error, we know that the fitness value in the
tth generation equals to
Ft = fopt (1 − Et ).

(4)

There is a link between the relative approximation error
and average convergence rate [18]. From the definition of the
(geometric) average of the convergence rate of an EA for t
generations, we get

1/t
 1/t
fopt − Ft
Et
def
Rt = 1 −
=1−
.
(5)
fopt − f0
E0
IV. E XAMPLE
Given Ft , Et and Rt , which is the best option to measure
the performance of an EA? We use a simple experiment to
show their advantage and disadvantage. Consider the problem
of maximizing a pseudo-Boolean function f (x) where x =
x1 · · · xn is a binary string. Three test functions are used in
the experiment.
OneMax function fone (x) = |x|,
square function fsqu (x) = |x|2 ,
logorithmic function flog (x) = ln(|x| + 1),

3

fone
fsqu
flog

Ft

15
10

0
10

20

30

t
Fig. 1.

fone
fsqu
flog

1

Et

fone
fsqu
flog

0.4

0.2

0

0

10

20

30

t
Fig. 3.

Average convergence rate Rt .

V. M ARKOV

CHAIN MODELLING FOR
ELITIST EA S

def

Fig. 2 presents the relative approximation error Et , which
converges to 0. From the figure, we observe that for any t, Et
on flog is smaller than that on fone , then smaller than that on
fsqu .

0.5

0
10

20

30

t
Fig. 2.

•

ri,j = Pr(Φt+1 = i | Φt = j),

Fitness value Ft .

0

•

Rt = 0.25 on fone . The EA converges as fast as an
exponential decay: Et = 0.75t E0 .
Rt converges to 0.25 on fsqu but its value is larger
than 0.25 . The EA converges faster than the exponential
decay: Et ≤ 0.75tE0 .
Rt converges to 0.25 on flog but its value is smaller
than 0.25 . The EA converges slower than the exponential
decay: Et ≥ 0.75tE0 .

(1+1) STRICTLY

This section introduces Markov chain modelling for (1+1)
strictly elitist EAs. It follows the Markov chain framework
described in [18], [20].
Genetic operators in EAs can be either time-invariant or
time-variant [9], [21]. This paper only considers time-invariant
operators. Such an EA can be modelled by a homogeneous
Markov chain with transition probabilities

5

0

•

Rt

where |x| = x1 + · · · + xn . A (1+1) EA is used for solving
the optimisation problem. This EA is also called randomised
local search.
Onebit Mutation. Given a binary string, chose one bit at
random and then flip it.
Elitist Selection. Choose the best from the parent and child
as the next parent.
Onebit mutation is chosen for the sake of demonstrating
that the average convergence rate Rt may equal to a constant,
according to the theory of the average convergence rate [18].
The three functions are the easiest to the (1+1) EA among
all pseudo-Boolean functions whose optimum is unique at
1 · · · 1 according to the theory of the easiest and hardest
functions [19].
In the experiment, we set n = 4. This small value is chosen
for the sake of displaying matrices in Section VII in one
column. The initial solution is set to 0000. We run the EA
108 times. The EA stops after 35 generations for each run.
Fig. 1 demonstrates the fitness value Ft which is averaged
over 108 runs. The figure shows that Ft converges to 4 on
fone , 16 on fsqu and ln 5 on flog . But it is not clear how Ft
is close to fopt , and how fast Ft converges to fopt .

Relative approximation error Et .

i, j ∈ S.

According to the strictly elitist selection, transition probabilities satisfy

 ≥ 0, if f (i) > f (j),
≥ 0, if i = j,
(6)
ri,j =

= 0, otherwise.

Let R denote the transition submatrix which represents
transition probabilities among non-optimal states {1, · · · , L}.
It is a L × L matrix, given as follows:


r1,1 r1,2 r1,3 · · · r1,L−1 r1,L
 0
r2,2 r2,3 · · · r2,L−1 r2,L 


 0
0
r3,3 · · · r3,L−1 r3,L 
R=
(7)
.
 ..

..
..
..
..
 .

.
.
.
.
0

0

0

···

0

rL,L

Let pt (i) = Pr(Φt = i) denote the probability of Φt at state
i and the vector
def

Fig. 3 illustrates the average convergence rates Rt , which
converges to 0.25. From the figure, we see the difference of
the average convergence rate on the three functions.

qt = (pt (1), pt (2), · · · , pt (L))T .
Here notation v is a column vector and vT the row with the
transpose operation.

4

For any t ≥ 1, the probability pt (i) (where i ∈ Snon ) equals
to
Pr(Φt = i) =

X

Pr(Φt = i | Φt = j) Pr(Φt−1 = j)

j∈Snon

=

X

pt−1 (i)ri,j .

i∈Snon

It can be represented by matrix iteration
qt = Rqt−1 = Rt q0 .

Lemma 1 (Lemma 1.2 in [22]): Let R = [ri,j ] be a nonsingular upper triangular matrix with unique diagonal entries.
Denote the entries of the matrix power Rt by [ri,j|t ]. For
P
any t ≥ 1, if ri,j|t = jk=i pi,j,k (rk,k )t−1 , then ri,j|t+1 =
Pj
t
k=i pi,j,k (rk,k ) .
Proof: Since Rt+1 = Rt · R, ri,l|t = 0 if l < i (because
t
R is upper triangular) and rl,j = 0 if l > j (because Rt is
upper triangular), we have

(8)

Let e(i) = fopt − f (i) denote the fitness error between the
optimal solution and each non-optimal solution and the vector
def

eT = (e(1), e(2), · · · , e(L)).

ri,j|t+1 =

VI. A N

ANALYTIC EXPRESSION OF RELATIVE
APPROXIMATION ERROR

This section gives an analytic expression of the relative
approximation error for (1+1) strictly elitist EAs. The analysis
is based on an existing result in matrix analysis [22], [23].
From (9), we see that calculating Et becomes a mathematical problem of expressing the matrix power Rt once the
initial probability distribution q0 and the fitness error eT are
known. For (1+1) strictly elitist EAs, the matrix R is an
upper triangular, and then it is feasible to express matrix Rt
explicitly in terms of its entries in a closed form [22].
For the sake of simplicity, matrix R is assumed to satisfy
the following condition:
• Unique condition: transition probabilities ri,i 6= rj,j if
i 6= j.
If transition probabilities ri,i = rj,j for some i 6= j, a similar
discussion can be conducted but will be given in a separate
paper.
Definition 2: The power factors of R, [pi,j,k ] (where
i, j, k = 1, · · · , L), are recursively defined as follows:
pj,j,j =rj,j ,
pi,j,k =0,
Pj−1
pi,l,k rl,j
pi,j,k = l=k
,
rk,k − rj,j
j−1
X
pi,j,l ,
pi,j,j =ri,j −

k < i or k > j,

(10)
(11)

i ≤ k < j,

(12)

i < j.

(13)

l=i

Lemmas 1 and 2 show how to calculate the matrix power
Rt . For the sake of completeness, their proofs [22] are given
here.

(14)

Pj
t−1
From the assumption: ri,j|t =
, and
k=i pi,j,k (rk,k )
noting that pi,l,k = 0 if k > l, we have
ri,j|t+1 =

j
X

rl,j

l=i

(9)

From formula (9), we see that Et is determined by the initial
distribution q0 , matrix power Rt , fitness error eT and optimal
fitness value fopt . Only Rt is a function of t, so it plays the
most important role in determining the relative approximation
error.

ri,l|t rl,j .

l=i

Then the relative approximation error Et can be represented
by
eT Rt q0
eT qt
=
.
Et =
fopt
fopt

j
X

=

j
X

l
X

pi,l,k (rk,k )t−1

k=i

(rk,k )t−1

k=i

Notice that
j
X

rl,j pi,l,k =

j
X

rl,j pi,l,k .

(15)

l=k

j−1
X

rl,j pi,l,k + rj,j pi,j,k .

(16)

l=k

l=k

Then substituting the sum in (16) by (12) in Definition 2, we
have
j
X
rl,j pi,l,k = pi,j,k (rk,k − rj,j ) + rj,j pi,j,k
l=k

= pi,j,k rk,k .

(17)

Pj

Finally (15) is simplified as ri,j|t+1 = k=i pi,j,k (rk,k )t .
This is the required conclusion.
Lemma 2 (Theorem 1.3 in [22]): Let R = [ri,j ] be a nonsingular upper triangular matrix with unique diagonal entries.
For any t ≥ 0,
ri,j|t+1 =

j
X

pi,j,k (rk,k )t−1 =

j
X

pi,j,k (rk,k )t .

(18)

k=i

k=i

Proof: According to (10), (11) and (13) in Definition 2,
we see that (18) is true for t = 1. Then by induction, (18) is
true for all t > 1 from Lemma 1.
The above lemma gives an analytic expression of the matrix
power Rt . Given a L ×L matrix R, the time complexity of
calculating Rt is 2 L+2
+ L(t − 3) in terms of the number
3
of multiplication and divisions [22].
For the sake of notation, e(i) is denoted by ei and q0 (i) by
qi . Define coefficients
PL PL
def
i=1
j=i ei pi,j,k qj
ck =
,
k = 1, · · · , L,
(19)
fopt
where ck is independent of t.
Theorem 1: If R = [ri,j ] is a non-singular upper triangular
matrix with unique diagonal entries, then for any t ≥ 1, the
relative approximation error Et is expressed by
Et =

L
X

k=1

ck λt−1
k ,

(20)

5

where λk = rk,k are eigenvalues of matrix R.
Proof: From (9), we know
Et =

eT Rt q0
eT Rt q0
=
.
fopt
fopt

(21)

Using (18), we get
eT Rt q0 =

j
L X
L X
X

ei pi,j,k (rk,k )t−1 qj .

Matrix R is

(22)

i=1 j=1 k=i

According to Definition 2, pi,j,k = 0 if k < i or k > j and
pi,j,k = 0 if i > j, then
eT Rt q0 =

L X
L X
L
X

Each subset Si is regarded as a state i.
Transition probabilities ri,j = Pr(Φt ∈ Si | Φt−1 ∈ Sj ) are
given by
 j
if j = i + 1,
 4,
(28)
ri,j =
1 − 4j , if j = i,

0,
otherwise.


0.750
0.000

0.000
0.000

=

t−1

(rk,k )

L X
L
X

ei pi,j,k qj .

(23)

Using ck , (21) is rewritten as
Et =

L
X

(29)

Choose the initial probability distribution in the non-optimal
set to be
q0 = (0, 0, 0, 1)T .

ck (rk,k )t−1 .

(24)

k=1

The conclusion then is proven.
This theorem shows the relative approximation error is
represented as a linear combination of exponential functions
(λk )t (where k = 1, · · · , L).
From the relationship between Ft and Et and that between
Rt and Et , we get the following corollaries.
Corollary 1: The fitness value Ft equals to
Ft = fopt (1 −

L
X

ck (λk )t−1 ).

(25)

k=1

Corollary 2: The average convergence rate Rt equals to
!1/t
L
X
f
opt
Rt = 1 −
.
(26)
ck (λk )t−1
fopt − f0
k=1

In practice, the relative approximation error is calculated as
follows:
1: given an initial probability distribution p0 , the fitness error
e and matrix R;
2: calculate power factors [pi,j,k ] where i, j, k = 1, · · · , L
using Definition 2;
3: calculate coefficients [ck ] (where k = 1, · · · , L) using
(19);
4: calculate the relative approximation error Et using Theorem 1.

This section applies Theorem 1 to the example in Section IV. The example is chosen for the sake of illustration.
Nevertheless Theorem 1 covers all (1 + 1) strictly elitist EAs
on any function under the unique condition.
We consider the OneMax function fone (x) first. The set
{0, 1}4 is split into 5 subsets
i = 0, 1, · · · , 4.

[pi,j,k ] which is

Using Definition 2, we calculate matrix
given by

0.750 1.500
2.250
0.000 −1.000 −3.000
[p1,j,k ] = 
0.000 0.000
0.750
0.000 0.000
0.000


3.000
−6.000
,
3.000 
0.000


0.000 0.000
0.000
0.500 1.500
3.000 
,
0.000 −0.750 −3.000
0.000 0.000
0.000



0.000
0.000
[p2,j,k ] = 
0.000
0.000

0.000
0.000
[p3,j,k ] = 
0.000
0.000

0.000
0.000
0.000
0.000

0.000
0.000
0.250
0.000


0.000
0.000
,
1.000
0.000


0.000
0.000
[p4,j,k ] = 
0.000
0.000

0.000
0.000
0.000
0.000

0.000
0.000
0.000
0.000


0.000
0.000
.
0.000
0.000

Using (19), we calculate coefficients ck (where k =
1, · · · , 4), given by
(0.750, 0.000, 0.000, 0.000).
Recall transition probabilities rk,k (where k = 1, · · · , 4) are
(0.750, 0.500, 0.250, 0.000).

VII. E XAMPLE ( CONTINUED )

Si = {x; |x| = i},


0.000
0.000

1.000
0.000

eT = (1, 2, 3, 4).

i=1 j=i

k=1

0.000
0.750
0.250
0.000

The fitness error ei = i for i = 1, · · · , 4. The fitness error
vector is

ei pi,j,k (rk,k )t−1 qj

i=1 j=1 k=1

L
X

0.500
0.500
0.000
0.000

(27)

Using (20), we calculate the relative approximation error Et ,
given by
Et = 0.75t.

(30)

Furthermore, using Corollary 1, we calculate the fitness
value Ft , given by
Ft = 4(1 − 0.75t ).

(31)

6

And using Corollary 2, we calculate the average convergence
rate Rt , given by
(32)

This means that Et decays as fast as an exponential function:
Et = 0.75t E0 .
The analysis of the quadratic function fsqu (x) and logarithmic function flog (x) is almost the same as that of the
OneMax function, except the fitness error vector e. The results
are summarised in Table I. Notice that the expressions for
quadratic and logarithmic functions are more complex than
that for the OneMax function.
Fig. 4 demonstrates the fitness value Ft . Fig. 5 presents
the relative approximation error Et . Fig. 6 illustrates the
average convergence rates Rt . The theoretical predictions are
consistent to the experimental results, labelled by f ∗ .

Rt

Rt = 1 − (0.75t )1/t = 0.25.

fone
fsqu
flog
∗
fone
∗
fsqu
∗
flog

0.4

0.2

0

0

10

20

Fig. 6.

Average convergence rate Rt .

Then the relative approximation error equals to
Et =

fone
fsqu
flog
∗
fone
∗
fsqu
∗
flog

15

Ft

10
5
0
0

10

20

30

t
Fig. 4.

Fitness value Ft .

fone
fsqu
flog
∗
fone
∗
fsqu
∗
flog

Et

1

0.5

0
0

10

20

30

eT UR̃t U∗ q0
.
fopt

(34)

Let ẽT = eT U and q̃0 = U∗ q0 , then the relative
approximation error can be rewritten as follows,
Et =

ẽT R̃t q̃0
.
fopt

(35)

Since R̃ is an upper triangular matrix, the analysis of Et
becomes the problem of expressing the matrix power R̃t . If
R̃ is an upper triangular matrix with unique diagonal entries,
Theorem 1 can be applied directly. If this does not hold, a
similar analysis can be conduced (but in a separate paper).
Therefore, in theory it is feasible to apply the approach to
non-elitist or population-based EAs too.
Furthermore, even if exact transition probabilities are unknown, it is still possible to apply the method to bounding
the relative approximation error. The idea is simple. We
construct an upper triangular matrix S = [si,j ] so that the
matrix iteration using S is slower than that using S. That is
eT St q0 ≥ eT Rt q0 . For example, the simplest matrix S is

 1 − rj,j , if j = i + 1,
ri,i ,
if j = i,
(36)
si,j =

0,
otherwise.

This issue will be discussed in a separate paper.

t
Fig. 5.

30

t

IX. C ONCLUSIONS

Relative approximation error Et .

In this paper, the solution quality of an EA is measured by
the relative approximation error, that is
VIII. E XTENSION
This section devotes to an extension from (1+1) strictly
elitist EAs to non-elitist or population-based EAs.
Many non-elitist or population-based EAs can be modelled
by homogeneous Markov chains but matrices R are not
upper triangular. Given any matrix R, according to Schur’s
triangularisation theorem (in textbook [24, p508]), there exists
an upper triangular matrix R̃ and unitary matrix U such that
R = UR̃U∗ . Then the matrix iteration (8) can be rewritten
as follows,
qt = Rt q0 = UR̃t U∗ q0 .

(33)

Et = 1 −

Ft
.
fopt

(37)

Then an analytic expression of the relative approximation error
Et is presented for any (1+1) strictly elitist EAs on any fitness
function. Provided that transition probabilities ri,i 6= rj,j for
any i 6= j, the formula is given by
Et =

L
X

ck λt−1
k ,

(38)

k=1

where λk = rk,k (where k = 1, · · · , L) are eigenvalues of
transition submatrix R and ck are coefficients.

7

TABLE I
A NALYTIC EXPRESSIONS OF Ft , Et AND Rt

IN THE EXAMPLE .

function

Ft

fone = |x|
fsqu = |x|2
flog = ln(|x| + 1)

4 × (1 − 0.75 × 0.75t−1 )
16 × (1 − 1.313 × 0.75t−1 + 0.375 × 0.5t−1 )
ln(5) × (1 − 0.416 × 0.75t−1 − 0.120 × 0.5t−1 − 0.033 × 0.25t−1 )
Et

fone = |x|
fsqu = |x|2
flog = ln(|x| + 1)

0.75 × 0.75t−1
1.313 × 0.75t−1 − 0.375 × 0.5t−1
0.416 × 0.75t−1 + 0.120 × 0.5t−1 + 0.033 × 0.25t−1

fone = |x|
fsqu = |x|2
flog = ln(|x| + 1)

0.25
1 − (1.313 × 0.75t−1 − 0.375 × 0.5t−1 )1/t
1 − (0.416 × 0.75t−1 + 0.120 × 0.5t−1 + 0.033 × 0.25t−1 )1/t

Rt

The above formula is also useful to fixed budget analysis.
Since the exact expression of the fitness value Ft is
!
L
X
(39)
ck (λk )t−1 ,
Ft = fopt 1 −
k=1

a good bound on Ft should be represented in the form of a
combination of exponential functions of t.
The work is a further development of the average convergence rate [18]. The exact expression of the average convergence rate Rt is
!1/t
L
X
f
opt
Rt = 1 −
ck (λk )t−1
.
(40)
fopt − f0
k=1

The approach is promising. Using Schur’s triangularization
theorem, it is feasible to make a similar analysis for non-elitist
or population-based EAs if they are modelled by homogeneous
Markov chains.
Our next work is to present a closed form for (1+1) strictly
elitist EAs whose transition matrices are upper triangular but
diagonal entries are not unique.
Acknowledgement:
The work was supported by the EPSRC under Grant
EP/I009809/1.
R EFERENCES
[1] 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, vol. 13, no. 5, pp. 1006 –1029, 2009.
[2] T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt, “Approximating covering problems by randomized search heuristics using
multi-objective models,” Evolutionary Computation, vol. 18, no. 4, pp.
617–633, 2010.
[3] C. Witt, “Worst-case and average-case approximations by simple randomized search heuristics,” in Proceedings of the 22nd Annual Conference on Theoretical Aspects of Computer Science. Springer-Verlag,
2005, pp. 44–56.
[4] Y. Yu, X. Yao, and Z.-H. Zhou, “On the approximation ability of
evolutionary optimization with application to minimum set cover,”
Artificial Intelligence, no. 180-181, pp. 20–33, 2012.
[5] X. Lai, Y. Zhou, J. He, and J. Zhang, “Performance analysis of
evolutionary algorithms for the minimum label spanning tree problem,”
IEEE Transactions on Evolutionary Computation, vol. 18, no. 6, pp.
860–872, 2014.

[6] J. He and X. Yao, “An analysis of evolutionary algorithms for finding
approximation solutions to hard optimisation problems,” in Proceedings
of IEEE 2003 Congress on Evolutionary Computation. IEEE Press,
2003, pp. 2004–2010.
[7] J. Suzuki, “A Markov chain analysis on simple genetic algorithms,”
IEEE Transactions on Systems, Man and Cybernetics, vol. 25, no. 4,
pp. 655–659, 1995.
[8] ——, “A further result on the markov chain model of genetic algorithms
and its application to a simulated annealing-like strategy,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 28,
no. 1, pp. 95–102, 1998.
[9] J. He and L. Kang, “On the convergence rate of genetic algorithms,”
Theoretical Computer Science, vol. 229, no. 1-2, pp. 23–39, 1999.
[10] G. Rudolph, “Local convergence rates of simple evolutionary algorithms
with Cauchy mutations,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 4, pp. 249–258, 1997.
[11] ——, “Convergence rates of evolutionary algorithms for a class of
convex objective functions,” Control and Cybernetics, vol. 26, pp. 375–
390, 1997.
[12] ——, “Convergence rates of evolutionary algorithms for quadratic
convex functions with rank-deficient hessian,” in Adaptive and Natural
Computing Algorithms. Springer, 2013, pp. 151–160.
[13] L. Ming, Y. Wang, and Y.-M. Cheung, “On convergence rate of a class of
genetic algorithms,” in Proceedings of 2006 World Automation Congress.
IEEE, 2006, pp. 1–6.
[14] F. Schmitt and F. Rothlauf, “On the importance of the second largest
eigenvalue on the convergence rate of genetic algorithms,” in Proceedings of 2001 Genetic and Evolutionary Computation Conference,
H. Beyer, E. Cantu-Paz, D. Goldberg, Parmee, L. Spector, and D. Whitley, Eds. Morgan Kaufmann Publishers, 2001, pp. 559–564.
[15] L. Ding and L. Kang, “Convergence rates for a class of evolutionary
algorithms with elitist strategy,” Acta Mathematica Scientia, vol. 21,
no. 4, pp. 531–540, 2001.
[16] T. Jansen and C. Zarges, “Fixed budget computations: A different
perspective on run time analysis,” in Proceedings of the 14th Annual
Conference on Genetic and Evolutionary Computation. ACM, 2012,
pp. 1325–1332.
[17] ——, “Performance analysis of randomised search heuristics operating
with a fixed budget,” Theoretical Computer Science, vol. 545, pp. 39–58,
2014.
[18] J. He and G. Lin, “Average convergence rate of evolutionary algorithms,”
IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp.
316–321, 2016.
[19] J. He, T. Chen, and X. Yao, “On the easiest and hardest fitness
functions,” IEEE Transactions on Evolutionary Computation, vol. 19,
no. 2, pp. 295–305, 2015.
[20] J. He and X. Yao, “Towards an analytic framework for analysing the
computation time of evolutionary algorithms,” Artificial Intelligence, vol.
145, no. 1-2, pp. 59–97, 2003.
[21] G. Rudolph, “Finite Markov chain results in evolutionary computation:
a tour d’horizon,” Fundamenta Informaticae, vol. 35, no. 1, pp. 67–89,
1998.
[22] W. Shur, “A simple closed form for triangular matrix powers,” Electronic
Journal of Linear Algebra, vol. 22, pp. 1000–1003, 2011.

8

[23] C. Huang, “An efficient algorithm for computing powers of triangular
matrices,” in Proceedings of the 1978 ACM Annual Conference-Volume
2. ACM, 1978, pp. 954–957.
[24] C. Meyer, Matrix Analysis and Applied Linear Algebra. SIAM, 2000.

