1

Mixed Strategy May Outperform Pure Strategy: An
Initial Study
Jun He, Wei Hou, Hongbin Dong, Feidun He

arXiv:1303.3154v3 [cs.NE] 22 Apr 2014

Abstract
A pure strategy metaheuristic is one that applies the same search method at each generation of the algorithm. A mixed strategy
metaheuristic is one that selects a search method probabilistically from a set of strategies at each generation. For example, a classical
genetic algorithm, that applies mutation with probability 0.9 and crossover with probability 0.1, belong to mixed strategy heuristics.
A (1+1) evolutionary algorithm using mutation but no crossover is a pure strategy metaheuristic. The purpose of this paper is
to compare the performance between mixed strategy and pure strategy metaheuristics. The main results of the current paper are
summarised as follows. (1) We construct two novel mixed strategy evolutionary algorithms for solving the 0-1 knapsack problem.
Experimental results show that the mixed strategy algorithms may find better solutions than pure strategy algorithms in up to
77.8% instances through experiments. (2) We establish a sufficient and necessary condition when the expected runtime time of
mixed strategy metaheuristics is smaller that that of pure strategy mixed strategy metaheuristics.

I. I NTRODUCTION
In the last three decades, metaheuristics have been widely applied in solving combinatorial optimisation problems [1, 2].
Metaheuristics include, but are not restricted to, Ant Colony Optimization (ACO), Genetic Algorithms (GA), Iterated Local
Search (ILS), Simulated Annealing (SA), and Tabu Search (TS) [3]. Different search strategies have been developed in these
metaheuristics. Each search strategy has its own advantage. Therefore it is a natural idea to combine the advantages of several
search strategies together. This leads to hybrid metaheuristics [4] such as hyper-heuristic [5] and memetic algorithm [6].
Mixed strategy metaheuristics [7] belong to the family of hybrid metaheuristics. They are inspired from the game theory
[8]. A pure strategy metaheuristic is one that applies the same search method at each generation of the algorithm. A mixed
strategy metaheuristic is one that selects a search method probabilistically from a set of strategies at each generation. For
example, a search strategy may be mutation or crossover. Thus a classical genetic algorithm, that applies mutation with
probability 0.9 and crossover with probability 0.1, belong to mixed strategy heuristics. A (1+1) evolutionary algorithm using
mutation but no crossover is a pure strategy metaheuristic. Previously mixed strategy evolutionary programming, integrating
several mutation operators, has been designed for numerical optimization [9]. Experimental results show that mixed strategy
evolutionary programming outperforms pure strategy evolutionary programming with a single mutation operator [10].
The first goal of this paper is to conduct an empirical comparison of the performance between mixed strategy and pure
strategy evolutionary algorithms (EAs for short) on the 0-1 knapsack problem. Here the performance is measured by the best
fitness value found in 500 generations. In experiments, two novel mixed strategy EAs are proposed to solve the 0-1 knapsack
problem.
The second but more important goal is to provide a theoretical answer to the question: when do mixed strategy metaheuristics
outperform pure strategy metaheuristics? In theoretical analysis, the performance of a metaheuristic is measured by the expected
number of total fitness evaluations to find an optimal solution (called the expected runtime).
Despite the popularity of hybrid metaheuristics in practice, the theoretic work on hybrid metaheuristics is very limited [11].
One result is based on the asymptotic convergence rate [12]. The asymptotic convergence rate is how fast an iteration algorithm
converge to the solution per iteration [13]. It is proven in [12] that any mixed strategy (1+1) EA (consisting of several mutation
operators) performs no worse than the worst pure strategy EA (using a single mutation operator). If mutation operators are
mutually complementary, then it is possible to design a mixed strategy (1+1) EA better than the best pure strategy (1+1) EA.
Another result is based on the runtime analysis of selection hyper-heuristics [11]. It shows that mixing different neighbourhood
or move acceptance operators can be more efficient than using stand-alone individual operators in some cases. But the discussion
is restricted to simple (1+1) EAs for simple problems such as the OneMax and GapPath functions.
This paper is different from our previous work [12] in two points. The expected runtime is employed to theoretically
measure the performance of metaheuristics, while the asymptotic convergence rate is used in [12]. The current paper discuss
population-based metaheuristics while [12] only analysed (1+1) EAs.
The rest of this paper is organized as follows. Section II gives experimental results that show mixed strategy may outperform
pure strategy. Section III provides the sufficient and necessary condition when mixed strategy may outperform pure strategy
in general. Section IV concludes the paper.
Jun He is with Department of Computer Science, Aberystwyth University, Ceredigion, SY23 3DB, UK. Email: jun.he@aber.ac.uk.
Wei Hou and Hongbin Dong are with College of Computer Science and Technology, Harbin Engineering University, Harbin, 150001, China
Feidun He is with School of Information Science and Technology, Southwest Jiaotong University, Chengdu, Sichuan, 610031, China

2

II. E VIDENCE

FROM

E XPERIMENT: M IXED S TRATEGY M AY O UTPERFORM P URE S TRATEGY

This section conducts an empirical comparison of the performance between mixed strategy EAs and pure strategies EAs. A
classical NP-hard problem, the 0-1 knapsack problem [14], is used in the empirical study.
A. Evolutionary Algorithms for the 0-1 Knapsack Problem
The 0-1 knapsack problem is described as follows:
maximize
subject to

Pn
vi xi ,
Pi=1
n
i=1 wi xi ≤ C,

where vi > 0 is the value of item i, wi > 0 the weight of item i, and C > 0 the knapsack capacity.

1 if item i is selected in the knapsack,
xi =
0 otherwise.
A solution is represented by a vector (a binary string) ~x = (x1 , · · · , xn ). If a solution ~x violates the constraint, then it is called
infeasible. Otherwise it is called feasible.
There are several ways to handle the constrains in the knapsack problem [15]. The method of repairing infeasible solutions
is used in the paper since it is more efficient than other methods [16]. Its idea is simple: if an infeasible solution is generated,
then it will be repaired to a feasible solution. The repairing procedure is described as follows:
input
Pn ~x;
if i=1 xi wi > C then
~x is infeasible;
while (~x is infeasible) do
i =: select an item from the knapsack;
setP
xi = 0;
n
if i=1 xi wi ≤ C then
~x is feasible;
end if
end while
end if
output ~x.
There are different select methods in the repairing procedure. Two of them are described as follows.
1) Random repair: select an item from the knapsack at random and remove it from the knapsack.
2) Greedy repairing: sort all items according to the order of the ratio vi /wi , then select the item with the smallest ratio
and remove it from the knapsack.
The fitness function is defined as
n
X
xi vi , if ~x is feasible,
f (~x) =
i=1

Thanks to the repairing method, no need to define the fitness for infeasible solutions.
A pure strategy EA for solving the 0-1 knapsack problem is described as follows.
input a fitness function;
generation counter t ← 0;
initialize population Φ0 ;
an archive keeps the best solution in Φ0 ;
while t is less than a threshold do
children population Φt+1/2 ← mutated from Φt ;
if a child is an infeasible solution then
then repair it into a feasible solution;
end if
new population Φt+1 ← selected from Φt , Φt+1/2 ;
update the archive if the best solution in Φt+1 is better than it;
t ← t + 1;
end while
output the maximum of the fitness function.
A mixed strategy EA for solving the 0-1 knapsack problem is almost the same as the above algorithm, except one
place:
choose a mutation operator probabilistically;

3

children population Φt+1/2 ← children mutated from Φt .
The description of mutation operators is given in the next subsection. The selection operator is the same in pure strategy and
mixed strategy EAs. A mixed strategy then means a probability distribution of choosing mutation operators.
B. Pure Strategy and Mixed Strategy Evolutionary Algorithms
Four pure strategy EAs are constructed based on four different mutation operators. The first mutation operator is standard
bitwise mutation. It is independent on the 0-1 knapsack problem. The related EA is denoted by PSb.
1
• Bitwise Mutation. Flip each bit xi to 1 − xi with probability n .
The second mutation operator is problem-specific. It is based on heuristic knowledge: an item with a bigger value is more
likely to appear in the knapsack. The related EA is denoted by PSv.
• Mutation based on values. If a bit xi = 0, then flip it to 1 with probability
v
Pn i
.
(1)
j=1 vj
If a bit xi = 1, then flip it to 0 with probability

1/v
Pn i
.
j=1 1/vj

(2)

The third mutation operator is based on heuristic knowledge too: an item with a smaller weight is more likely to appear in
the knapsack. The corresponding EA is denoted by PSw.
• Mutation based on weights. If a bit xi = 0, then flip it to 1 with probability

If a bit xi = 1, then flip it to 0 with probability

1/wi
Pn
.
j=1 1/wj
w
Pn i

j=1

wj

(3)

.

(4)

The fourth mutation operator is constructed from heuristics knowledge: first calculate the ratio between the value and weight
for each item:
vi
.
(5)
ri =
wi
Then an item with a bigger ratio is more likely to appear in the knapsack. The related EA is denoted by PSr.
• Mutation based on the ratio between value and weight. If a bit xi = 0, then flip it to 1 with probability
r
Pn i
.
(6)
j=1 rj
If a bit xi = 1, then flip it to 0 with probability

1/r
Pn i
.
j=1 1/rj

(7)

Two novel mixed strategy EAs are designed in the experiments. One is to set a fixed probability distribution of choosing
mutation operators for all generations. The algorithm is called static, denoted by MSs.
• statically mixed strategy: choose each mutation operator based on a fixed probability, for example, (0.25, 0.25, 0.25, 0.25)
for the four pure strategies.
The other is to dynamically adjust the probability distribution of choosing mutation operators. If a better solution is generated
by applying a mutation operator this generation, then the operator will be chosen with a higher probability. This kind of mixed
strategy EAs is called dynamic, denoted by MSd.
• dynamically mixed strategy: The updating procedure of the mixed strategy is the same as that in [9]. For each individual
in population Φt+1 , update its mixed strategy as follows. If the individual’s parent generates a child via mutation PS and
the child is selected into population Φt+1 , then assign the probabilities of choosing mutation PS and other mutation PS’
to be
Pt+1 (P S) = Pt (P S) + 1−Pt4(P S) ,
′
Pt+1 (P S ′ ) = Pt (P S ′ ) − Pt (P4 S ) , P S ′ 6= P S,
Otherwise assign
S)
Pt+1 (P S) = Pt (P S) − Pt (P
,
4
′
Pt+1 (P S ′ ) = Pt (P S ′ ) + 1−Pt4(P S ) ,

P S ′ 6= P S,

4

C. Experiments
Experiments are conducted on different types of instances of the 0-1 knapsack problem. According to the correlation between
values and weights, the instances of the problem are classified into three types [14, 15]: given two positive parameters A and
B,
1) uncorrelated knapsack: vi and wi uniformly random in [1, A];
2) weakly correlated knapsack: wi uniformly random in [1, A]; and vi uniformly random in [wi − B, wi + B] (if for some
j, vi ≤ 0, then the random generation procedure should be repeated until vi > 0);
3) strongly correlated knapsack: wi uniformly random in [1, A]; and vi = wi + B;
n
n
In the experiments, A and r are set to be A = 20
and B = 20
.
Based on the capacity, the instances of the knapsack problem are classified into two types [14, 15]:
1) restrictive capacity knapsack: the knapsack capacity is small, where C = 2A.
P
2) average capacity knapsack: the knapsack capacity is large, where C = 0.5 ni=1 wi .
Hence we will compare two mixed strategy EAs and four pure strategy EAs on six different types of instances below:
1) uncorrelated and restrictive capacity knapsack,
2) weakly correlated and restrictive capacity knapsack,
3) strongly correlated and restrictive capacity knapsack,
4) uncorrelated correlated and average capacity knapsack,
5) weakly correlated and average capacity knapsack,
6) strongly correlated and restrictive average capacity knapsack.
Furthermore the experiments are split into two groups based on the repairing method: (1) greedy repair, (2) random repair.
The experiment setting is described as follows. For each type of the 0-1 knapsack problem, three instances with 100, 250
and 500 items are generated at random. The population size is set to 10. The maximum of generations is 500. The initial
population is chosen at random.
Tables I and II give the experimental results. The number in the table is the best fitness values found in 500 generations. It
is averaged over 10 independent runs for each instance.
GREEDY REPAIR : THE BEST FITNESS VALUE FOUND IN

n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500

TABLE I
500 GENERATIONS , AVERAGED OVER 10 RUNS FOR EACH INSTANCE

uncorrelated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
285
300
279
281
283
277
1609
1655
1601
1539
1528
1513
5625
5703
5515
5794
5140
5504
weakly correlated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
342
353
331
289
306
325
1651
1695
1583
1514
1668
1650
5319
5545
5161
4595
4810
4710
strongly correlated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
671
683
678
662
655
665
4126
4261
4212
4170
5023
3980
15273
15537
14959
15226
15367
14179
uncorrelated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
295
299
293
292
288
295
1616
1650
1616
1619
1583
1609
5751
5958
5670
5963
5601
5663
weakly correlated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
387
395
355
344
362
349
1976
2014
2009
1924
1997
1956
7284
7505
6839
6966
7048
7049
strongly correlated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
716
730
718
721
714
716
4372
4409
4301
4220
4135
4218
15525
15868
15746
15819
15552
14828

Following a simple calculation, we see that the dynamically mixed strategy EA, MSd, is the best in 77.8% instances and
equally the best in 2.8% instances. If we compare the statically mixed strategy EA with the four pure strategies, then we see
that MSs is better than the four pure strategy EAS in 36.1% instances (marked in italic type in the tables).

5

RANDOM REPAIR : THE BEST FITNESS VALUE FOUND IN

n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500
n
100
250
500

TABLE II
500 GENERATIONS , AVERAGED OVER 10 RUNS FOR EACH INSTANCE

uncorrelated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
167
170
161
160
155
166
850
876
852
842
810
846
2550
2675
2440
2513 3
2496
2426
weakly correlated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
236
242
230
229
226
222
1066
1134
1046
1058
1098
1067
3947
4071
3719
3741
3713
3815
strongly correlated and restrictive capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
405
416
403
405
389
408
2171
2204
2188
2273
2138
2205
7028
7078
6981
6883
6958
6946
uncorrelated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
225
234
218
231
212
231
1236
1266
1197
1208
1070
1263
4669
4697
4443
4674
3922
4716
weakly correlated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
295
311
290
294
292
304
1520
1530
1497
1491
1374
1519
5641
5769
5300
5525
4999
5710
strongly correlated and average capacity knapsacks
MSs
MSd
PSb
PSv
PSw
PSr
476
493
479
483
470
493
2650
2716
2613
2610
2586
2721
10156
10285
10119
10131
10065
10393

Experimental results show mixed strategy EAs outperform pure strategy EAs in up tp 77.8% instances, but not always.
Naturally it raises the question: under what condition, a mixed strategy EA may outperform a pure strategy EA. This question
is seldom answered rigorously before.
III. S UPPORT

OF

T HEORY: M IXED S TRATEGY M AY O UTPERFORM P URE S TRATEGY

In this section, we conduct a theoretical comparison of the performance between mixed strategy metaheuristics and pure
strategy metaheuristics.
A. Meta-heuristics and Markov Chains
Without lose of generality, consider the problem of maximising a fitness function:
maximize f (x),

(8)

where x is a variable and its definition domain is a finite set.
The metaheuristics considered in the paper are formalised as Markov chains. Initially construct a population of solutions
Φ0 ; from Φ0 , then generate a new population of solutions Φ1 ; from Φ1 , then generate a new population of solutions Φ2 , and
so on. This procedure is repeated until a stopping condition is satisfied. A sequence of populations is then generated
Φ0 → Φ1 → Φ2 → · · · .
An archive is used for recording the best found solution so far. The archive is not involved in generating a new population. In
this way, the best found solution is preserved for ever (called elitist). The metaheuristics algorithm with an archive is described
below. In the algorithm, the number of fitness evaluations for each generation is invariant.
set counter t to 0;
initialize a population Φ0 ;
an archive keeps the best solution in Φ0 ;
while the archive is not an optimal solution do
a new population Φt+1 is generated from Φt ;
update the archive if the best solution in Φt+1 is better than it;
counter t is increased by 1;
end while

6

The procedure of generating Φt+1 from Φt can be represented by transition probabilities among populations:
P (X, Y ) := P (Φt+1 = Y | Φt = X),

(9)

where populations Φt , Φt+1 are variables and X, Y are their values (also called states). The transition probabilities P (X, Y )
form the transition matrix of a Markov chain, denoted by P.
Definition 1. If a transition matrix P for generating new populations is independent of t, then it is called a pure strategy. A
mixed strategy is a probability distribution of choosing a pure strategy from a set of strategies.
In theory, the stopping criterion is that the algorithm halts once an optimal solution is found. It is taken for the convenience
of analysing the first time of finding an optimal solution (called hitting time). If Φt includes an optimal solution, then assign
Φt = Φt+1 = Φt+2 = · · ·
for ever. As a result, the population sequence {Φt } is formulated by a homogeneous Markov chain [17].
Since a state in the optimal set is always absorbing, so the transition matrix P can be written in the canonical form,


I O
P=
,
(10)
R Q
where I is a unit matrix, O a zero matrix and Q a matrix for transition probabilities among non-optimal populations. R denotes
the transition probabilities from non-optimal populations to optimal populations.
Let m(X) denote the expected number of generations needed to find an optimal solution when Φ0 is at state X for the first
time (thereafter it is abbreviated by the expected hitting time). Clearly for any initial population X in the optimal set, m(X)
is 0. Let (X1 , X2 , · · · ) represent all populations in the non-optimal set and the vector m
~ denote their expected hitting times
respectively
m
~ = (m(X1 ), m(X2 ), · · · )T .
Since the number of fitness evaluations for each generation is invariant, the total number of fitness evaluations (called
runtime) equals to the expected hitting time × the number of fitness evaluations of a generation.
The following theorem [18, Theorem 11.5] shows that the expected hitting time can be calculated from the transition matrix.
Theorem 1 (Fundamental Matrix Theorem). The expected hitting time is given by
m
~ = (I − Q)−1~1,

(11)

where ~1 is a vector all of whose entries are 1, the matrix N = (I − Q)−1 is called the fundamental matrix.
Two special values of the expected hitting time are often used to evaluate the performance of metaheuristics. The first value
is the average of the expected hitting time, given by
1 X
m̄ =
m(X).
(12)
|S|
X∈S

where S denotes the set of all populations. The average corresponds to the case when the initial population is chosen at random.
The second value is the maximum of the expected hitting time, given by
max{m(X); X ∈ S},

(13)

The maximum corresponds to the case when the initial population is chosen at the worst state.
The population set S is divided into two parts: Snon denotes the set of all populations which don’t include any optimal
solution and Sopt the set of all populations which include at least one optimal solution.
B. Drift Analysis
Drift analysis is used for bounding the expected hitting time of metaheuristics [19]. In drift analysis, a distance function
d(X) is a non-negative function. Let (X1 , X2 , · · · ) represent all populations in the non-optimal set and d~ denote the vector
(d(X1 ), d(X2 ), · · · )T .
Definition 2. Let P be the Markov chain associated with ametaheuristic and d(X) be a distance function. For a non-optimal
population X, the drift at state X is
X
∆(X) := d(X) −
d(Y )P (X, Y ).
Y ∈Snon

The drift represents the one-step progress rate towards the global optima. Since the Markov chain {Φt ; t = 0, 1, · · · } is
homogeneous, the above drift is independent of t.

7

The following theorem is a variant of the original drift theorem [17, Theorems 3 and 4].
Theorem 2 (Drift Analysis Theorem). (1) If the drift satisfies that ∆d(X) ≥ 1 for any state X, and ∆d(X) > 1 for some
state X, then the expected hitting time satisfies that m(X) ≤ d(X) for any initial population X, and m(X) < d(X) for some
initial population X.
(2) If the drift satisfies that ∆d(X) ≤ 1 for any state X, and ∆d(X) < 1 for some state X, then the expected hitting time
satisfies that m(X) ≥ d(X) for any initial population X, and m(X) > d(X) for some initial population X.
Proof: We only prove the first conclusion. The second conclusion can be proven in a similar way.
The notation ≻ is introduced in the proof as follows: given two vectors ~a = [ai ] and ~b = [bi ], if for all i, ai ≥ bi and for
some i, ai > bi , then write it by ~a ≻ ~b. Similarly given two matrices A = [aij ] and B = [bij ], if for all i, j, aij ≥ bij and for
some pair i, j, aij > bij , then write it by A ≻ B.
Let ~1 denote the vector whose entries are 1, ~0 the vector whose entries are 0 and O a matrix whose entries are 0. The
condition of the theorem can be rewritten in an equivalent vector form:
d~ − Qd~ = ~1 + ~e,
where ~e ≻ ~0.
Then we have
d~ − Qd~ − ~1 − ~e = ~0,
(I − Q)−1 (d~ − Qd~ − ~1 − ~e) = ~0,
(I − Q)−1 (d~ − Qd~ − ~1) = (I − Q)−1~e.
Now let’s bound the right-hand side. Since ~e ≻ ~0, so entry ej > 0 for some j. P is a transition matrix, Q ≻ O and the
spectral radius of Q are less than 1, so N = (I − Q)−1 ≻ O. Since no eigenvalue of N is 0, for the j-column of N, at least
one entry is greater than 0 (otherwise 0 will be an eigenvalue of N). Thus entry nij > 0 for some i. Then nij ej > 0 and
(I − Q)−1~e ≻ ~0.
Hence we get
(I − Q)−1 (d~ − Qd~ − ~1) ≻ ~0,
d~ ≻ (I − Q)−1~1.
From the Foundational Matrix Theorem, we know that
(I − Q)−1~1 = m.
~
Then we get d~ ≻ m.
~ This inequality implies the conclusion of the theorem.
The following consequence is directly derived from the Fundamental Matrix Theorem.
Corollary 1. Let the distance function d(X) = m(X), then the drift satisfies ∆(X) = 1 for any state X in the non-optimal
set.
Proof: From the Fundamental Matrix Theorem: (I − Q)m
~ = ~1. Then we write it in the entry form and it gives ∆(X) = 1
for any state X in the non-optimal set.
C. One Pure Strategy is Inferior or Equivalent to another Pure Strategy
In the subsection, we investigate the case that it is impossible to design a mixed strategy better than a pure strategy. Consider
two metaheuristics: one using a pure strategy PS1 (PS1 for short) and another using a pure strategy PS2 (PS2 for short). Let
m
~ P S1 be the vector representing the expected hitting times with respect to PS1 and the distance function d(X) = mP S1 (X).
For PS1, denote its corresponding drift at state X by ∆P S1 (X):
X
∆P S1 (X) = d(X) −
PP S1 (X, Y )d(Y ),
Y ∈Snon

where PP S1 (X, Y ) represents the transition probability from x to Y . According to Corollary 1, the drift ∆P S1 (X) = 1 for
all X in the non-optimal set.
For PS2, denote the corresponding drift at state x by ∆P S1 (X):
X
PP S2 (X, Y )d(Y ).
∆P S2 (X) = d(X) −
Y ∈Snon

First we propose the “inferior” condition.

8

Definition 3. If the drift of PS1 and that of PS2 satisfy ∆P S1 (X) ≥ ∆P S2 (X) for any state X, and ∆P S1 (X) > ∆P S2 (X)
for some state X, then we call PS2 is inferior to PS1.
We consider the mixed strategy metaheuristic derived from PS1 and PS2 (MS for short) at the population level: the probability
of choosing a search strategy is the same for all individuals. Suppose population Φt is at state X, we denote the probability
of choosing PS1 by PX (P S2) and the probability of choosing PS1 by PX (P S2). The sum PX (P S1) + PX (P S2) = 1.
Lemma 1. If PS2 is inferior to PS1, then for any mixed strategy metaheuristics derived from PS1 and PS2, the expected hitting
time of MS satisfies that mMS (X) ≥ mP S1 (X) for any initial population X, mMS (X) > mP S1 (X) for some state X.
Proof: Let ∆MS (X) denote the drift associated with MS. For any state X, the drift of MS is
X
∆MS (X) =d(X) −
PMS (X, Y )d(Y )
Y ∈Snon

=PX (P S1)[d(X) −

X

PP S1 (X, Y )d(Y )]

X

PP S2 (X, Y )d(Y )]

Y ∈Snon

+PX (P S2)[d(X) −

Y ∈Snon

=PX (P S1)∆P S1 (X) + PX (P S2)∆P S2 (X).
Since PS2 is inferior to PS1, we know that ∆P S1 (X) ≥ ∆P S2 (X) for any state X, and ∆P S1 (X) > ∆P S2 (X) for some
X. Therefore ∆P S1 (X) = 1 ≥ ∆MS (X) for any state X, and ∆P S1 (X) = 1 > ∆MS (X) for some state X.
Applying the Drift Analysis Theorem, we get the conclusion: the expected hitting time satisfies that mMS (X) ≥ mP S1 (X)
for any initial population X, and mMS (X) > mP S1 (X) for some initial population X.
From the above lemma, we infer two corollaries.
Corollary 2. If PS2 is inferior to PS1, then for any mixed strategy MS derived from PS1 and PS2, its average of the expected
hitting time is greater than that of PS1.
Proof: According to the above lemma, the expected hitting time satisfies that mMS (X) ≥ mP S1 (X) for any initial
population X, and mMS (X) > mP S1 (X) for some initial population X. From the definition of average,
1 X
m̄ =
m(X),
|S|
X∈S

then we get m̄MS > m̄P S1 .
Corollary 3. If PS2 is inferior to PS1, then for any mixed strategy MS derived from PS1 and PS2, its maximum of the expected
hitting time is not less than that of PS1.
Proof: According to the above lemma, the expected hitting time satisfies that mMS (X) ≥ mP S1 (X) for any initial
population X. Then we get
max{mMS (X); X ∈ S} ≥ max{mP S1 (X); X ∈ S}
and prove the conclusion.
Next we propose the “equivalent” condition.
Definition 4. If the drift of PS1 and that of PS2 satisfy ∆P S1 (X) = ∆P S2 (X) for any state X, then we call PS1 is equivalent
to PS2.
The following lemma is direct corollary of the Drift Analysis Theorem.
Lemma 2. If PS2 is equivalent to PS1, then for any mixed strategy MS derived from PS1 and PS2, its the expected hitting
time satisfies that mMS (X) = mP S1 (X) for any initial population X.
D. One Pure Strategy is Complementary to Another Pure Strategy
In the subsection, we investigate the case that it is possible to design a mixed strategy better than a pure strategy. We propose
the “complementary” condition. Like the previous subsection, the distance function d(X) = mP S1 (X).
Definition 5. If the drift of PS1 and that of PS2 satisfy ∆P S1 (X) < ∆P S2 (X) for some state X, then we call PS2 is
complementary to PS1.
Lemma 3. If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2, and its the
expected hitting time satisfies that mMS (X) ≤ mP S1 (X) for any initial population X, and mMS (X) < mP S1 (X) for some
initial population X.

9

Proof: First we construct a mixed strategy derived from PS1 and PS2. The construction follows a well-known principle:
at one state, if a pure strategy has a better performance than the other at a state, then the strategy should be applied with a
higher probability at that state.
1) When Φt is at state X, if the drift ∆P S1 (X) is greater than the drift ∆P S2 (X), then the probability of choosing PS1
is set to 1, that is, PX (P S1) = 1.
2) When Φt is at state X, if the drift ∆P S1 (X) equals to the drift ∆P S2 (X), then the probability of choosing PS1 is set
to any value between [0, 1], that is, 0 ≤ PX (P S1) ≤ 1.
3) Since PS2 is complementary to PS1, so there exists one state X such that the drift ∆P S2 (X) is larger than the drift
∆P S1 (X). When Φt is at such a state X, then the probability of choosing PS2 is set to any value greater than 0, that
is, 0 < PX (P S2) ≤ 1.
In this way a mixed strategy MS is constructed from PS1 and PS2.
Next we bound the drift of the mixed strategy. For any state X, the drift of the mixed strategy is
X
∆MS (X) =d(X) −
PMS (X, Y )d(Y )
Y ∈Snon

=PX (P S1)[d(X) −

X

PP S1 (X, Y )d(Y )]

X

PP S2 (X, Y )d(Y )]

Y ∈Snon

+PX (P S2)[d(X) −

Y ∈Snon

=PX (P S1)∆P S1 (X) + PX (P S2)∆P S2 (X).
Based on the construction of the mixed strategy, the analysis of the drift is classified into three cases.
1) ∆P S1 (X) > ∆P S2 (X): in this case, the probability of choosing PS1 is 1, that is, PX (P S1) = 1. Thus the drift satisfies:
∆MS (X) = ∆P S1 (X).
2) ∆P S1 (X) = ∆P S2 (X): in this case, the drift satisfies: ∆MS (X) = ∆P S1 (X).
3) ∆P S1 (X) < ∆P S2 (X): in this case, the probability of choosing PS2 is greater than 0, that is, PX (P S2) > 0. Thus the
drift satisfies: ∆MS (X) < ∆P S1 (X).
Summarising all three cases, we see that the drift of the mixed strategy satisfies: ∆MS (X) ≥ ∆P S1 (X) = 1 for any state
X, and ∆MS (X) > ∆P S1 (X) = 1 for some state X.
Finally applying the Drift Analysis Theorem, we come to the conclusion: the expected hitting time satisfies: mMS (X) ≤
mP S1 (X) for any initial population X, and mMS (X) < mP S1 (X) for some initial population X.
From the above lemma, we draw two results about the average and maximum of the expected hitting times.
Corollary 4. If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2 and its average
of the expected hitting time is less than that PS1.
Proof: According to the above lemma, the expected hitting time satisfies: mMS (X) ≤ mP S1 (X) for any initial population
X, and mMS (X) < mP S1 (X) for some initial population X. From the definition
1 X
m(X),
m̄ =
|S|
X∈S

then we get m̄MS < m̄P S1 .
Corollary 5. If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2 and its
maximum of the expected hitting time is no more than that PS1.
Proof: According to the above lemma, the expected hitting time satisfies: mMS (X) ≤ mP S1 (X) for any initial population
X. Then we get
max{mMS (X); X ∈ S} ≤ max{mP S1 (X); X ∈ S}
and prove the conclusion.
E. Complementary Strategy Theorem
Combining Lemmas 1, 2 and 3 together, we obtain our main result about mixed strategy metaheuristics. It gives an answer
to the question: under what condition, mixed strategy metaheuristics may outperform pure strategy metaheuristics.
Theorem 3 (Complementary Strategy Theorem). Consider two metaheuristics: one using pure strategy PS1 and another using
pure strategy PS2. The condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy
MS derived from PS1 and PS2 such that: mMS (X) ≤ mP S1 (X) for any initial population X, and mMS (X) < mP S1 (X)
for some initial population X.

10

Furthermore the condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy
MS derived from PS1 and PS2 such that: the expected runtime of MS is no more than that of PS1 for any initial population
X, and less than that of PS1 for some initial population X.
Proof: Given PS1 and PS2, their relation is classified into exact three exclusive types: PS2 is inferior, or equivalent, or
complementary to PS1. Thus combining Lemmas 1, 2 and 3 together, we get the desired first conclusion.
Since the expected runtime equals to the expected hitting time × the number of fitness evaluations of a generation, we
obtain the second conclusion.
The theorem can be explained intuitively as follows.
1) If one pure strategy is inferior to another pure strategy, then it is impossible to design a mixed strategy with a better
performance. So mixed strategy metaheuristics doesn’t always outperform pure strategy metaheuristics.
2) If one pure strategy is complementary to another one, then it possible to design a mixed strategy better than the pure
strategy. But it does not mean all mixed strategies will outperform the pure strategy.
3) The construction of a better mixed strategy metaheuristics should follow a general principle: if using a pure strategy has
a better progress rate (in terms of the drift) than that using the other at a state, then the strategy should be applied with a
higher probability at that state. This principle is general, but the design of a better mixed strategy is strongly dependent
on the problem.
For the average of the expected hitting time, we may obtain a similar consequence after combining Corollaries 2, 4 and
Lemma 2 together.
Corollary 6. The condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy MS
derived from PS1 and PS2 and its average of the expected hitting time is less than than that of PS1.
But the sufficient and necessary condition for the maximum of the expected hitting time is more complex.
F. An Example
Consider an instance of the 0-1 knapsack problem: the value of items v1 = n and vi = 1 for i = 2, · · · , n, the weight of
items w1 = n and wi = 1 for i = 2, · · · , n. The capacity C = n. The fitness function is

if s1 = 1, s2 = · · · sn = 0,
 n,
Pn
s
,
if s1 = 0,
(14)
f (x) =
i
i=1

infeasible , otherwise.
For the four pure EAs described in the previous section, it is easy to verify that
1) PSr is equivalent to PSb,
2) PSw is inferior to PSb,
3) PSv is complementary to PSb.
Applying the Completerary Strategy Theorem, we know that
1) combining PSr with PSb will not shorten the expected runtime;
2) combining PSw will PSb will not shorten the expected runtime too;
3) but combining PSv with PSb may reduce the expected runtime.
IV. C ONCLUSIONS
The main contribution of the paper is the Complementary Strategy Theorem. From the theoretical viewpoint, the theorem
provides an answer to the question: under what condition, mixed strategy metaheuristics may outperform pure strategy
metaheuristics. The theorem asserts that given two metaheuristics where one uses a pure strategy PS1 and the other uses
a pure strategy PS2, the condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed
strategy MS derived from PS1 and PS2 such that: the expected runtime of MS is no more than that of PS1 for any initial
population X, and less than that of PS1 for some initial population X. To the best of our knowledge, no similar sufficient and
necessary condition was rigorously established based on the runtime analysis of hybrid metaheuristics before. This is a step
to understand hybrid metaheuristics in theory.
Besides the above theoretical analysis, experiments are also implemented. Experimental results demonstrate that mixed
strategy EAs may outperform pure strategy EAs on the 0-1 knapsack problem in up to 77.8% instances. In the experiments,
the performance of an EA is measured by the fitness function value of the archive after 500 generations.
It should be mentioned that a huge gap exists between empirical and theoretical studies. In experiments, the optimal solution
is usually unknown in most instances, then the expected runtime is unavailable; in theory, it is difficult to analyse the best
solution found in 500 generations or in any fixed generations.
Acknowledgement: This work is supported by the EPSRC under Grant EP/I009809/1, the National Natural Science
Foundation of China under Grant 60973075 and Ministry of Industry and Information Technology under Grant B0720110002.

11

R EFERENCES
[1] F. Glover and G. A. Kochenberger, Handbook of Metaheuristics. Springer, 2003.
[2] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics. Springer, 2010.
[3] C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM
Computing Surveys, vol. 35, no. 3, pp. 268–308, 2003.
[4] C. Blum, A. Roli, and M. Sampels, Hybrid Metaheuristics: an Emerging Approach to Optimization. Springer, 2008.
[5] E. Burke, G. Kendall, J. Newall, E. Hart, P. Ross, and S. Schulenburg, “Hyper-heuristics: An emerging direction in modern
search technology,” in Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. Springer, 2003, pp. 457–474.
[6] F. Neri, C. Cotta, and P. Moscato, Handbook of memetic algorithms. Springer, 2011, vol. 379.
[7] J. He and X. Yao, “A game-theoretic approach for designing mixed mutation strategies,” in Proceedings of the 1st
International Conference on Natural Computation, LNCS 3612, L. Wang, K. Chen, and Y.-S. Ong, Eds. Changsha,
China: Springer, August 2005, C1, pp. 279–288.
[8] P. Dutta, Strategies and Games: Theory and Practice. MIT Press, 1999.
[9] H. Dong, J. He, H. Huang, and W. Hou, “Evolutionary programming using a mixed mutation strategy,” Information
Sciences, vol. 177, no. 1, pp. 312–327, 2007.
[10] L. Shen and J. He, “A mixed strategy for evolutionary programming based on local fitness landscape,” in Proceedings of
2010 IEEE Congress on Evolutionary Computation. Barcelona, Spain: IEEE Press, 2010, C1, pp. 350–357.
[11] P. K. Lehre and E. Özcan, “A runtime analysis of simple hyper-heuristics: To mix or not to mix operators,” in Proceedings
of FOGA 2013, 2013.
[12] J. He, F. He, and H. Dong, “Pure strategy or mixed strategy?” in Evolutionary Computation in Combinatorial Optimization
(LNCS 7245), J.-K. Hao and M. Middendorf, Eds. Springer, 2012, C1, pp. 218–229.
[13] R. Varga, Matrix Iterative Analysis. Springer, 2009.
[14] S. Martello and P. Toth, Knapsack Problems. Chichester: John Wiley & Sons, 1990.
[15] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed. New York: Springer Verlag,
1996.
[16] J. He and Y. Zhou, “A comparison of GAs using penalizing infeasible solutions and repairing infeasible solutions II:
Avarerage capacity knapsack,” in Proceedings of the 2nd International Symposium on Intelligence Computation and
Applications, L. Kang, Y. Liu, and S. Y. Zeng, Eds. Wuhan, China: Springer, September 2007, C1, pp. 102–110.
[17] 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.
[18] C. Grinstead and J. Snell, Introduction to Probability. American Mathematical Society, 1997.
[19] J. He and X. Yao, “Drift analysis and average time complexity of evolutionary algorithms,” Artificial Intelligence, vol.
127, no. 1, pp. 57–85, 2001.

