Hyper-heuristics Can Achieve Optimal Performance
for Pseudo-Boolean Optimisation∗

arXiv:1801.07546v1 [] 23 Jan 2018

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker
Department of Computer Science
University of Sheffield
Sheffield, S1 4DP
United Kingdom

Abstract
Selection hyper-heuristics are randomised search methodologies which choose and execute heuristics
from a set of low-level heuristics. Recent research for the LeadingOnes benchmark function has shown
that the standard Simple Random, Permutation, Random Gradient, Greedy and Reinforcement Learning
selection mechanisms show no effects of learning. The idea behind the learning mechanisms is to continue to exploit the currently selected heuristic as long as it is successful. However, the probability that a
promising heuristic is successful in the next step is relatively low when perturbing a reasonable solution
to a combinatorial optimisation problem. In this paper we generalise the ‘simple’ selection-perturbation
mechanisms so success can be measured over some fixed period of time τ , rather than in a single iteration.
We present a benchmark function where it is necessary to learn to exploit a particular low-level heuristic,
rigorously proving that it makes the difference between an efficient and an inefficient algorithm. For
LeadingOnes we prove that the Generalised Random Gradient, and the Generalised Greedy Gradient
hyper-heuristics achieve optimal performance, while Generalised Greedy, although not as fast, still outperforms Random Local Search. The performance of the former two hyper-heuristics improves as the
number of operators to choose from increases, while that of the Generalised Greedy hyper-heuristic does
not. Experimental analyses confirm these results for realistic problem sizes and shed some light on the
best choices of the parameter τ in various situations.

1

Introduction

Many successful applications of randomised search heuristics to real-world optimisation problems have been
reported. Despite these successes, it is still difficult to decide which particular search heuristic is a good
choice for the problem at hand and what parameter settings should be used. In particular, while it is well
understood that each heuristic will be efficient on some classes of problems and inefficient on others [23],
very little guidance is available explaining how to choose an algorithm for a given problem. The high level
idea behind the field of hyper-heuristics is to overcome this difficulty by evolving the search heuristic for the
problem rather than choosing one in advance (or applying several arbitrary ones until a satisfactory solution
is found). The overall goal is to automate the design and the tuning of the algorithm and parameters for
the optimisation problem, hence achieving a more generally applicable system.
Hyper-heuristics are usually classified into two categories: selection hyper-heuristics and generation hyperheuristics [5]. The former repeatedly select from a set of low-level heuristics to create new solutions for the
problem, while the latter generate new heuristics from components of existing heuristics. The low-level
heuristics can be further classified as either construction heuristics, which build a solution incrementally,
or perturbation heuristics, which start with a complete solution and try to iteratively improve the current
solution.
An extended abstract of this manuscript has appeared at the 2017 Genetic and evolutionary Computation Conference
(GECCO 2017) [15].
∗

1

Despite the numerous successes for NP-hard optimisation problems, including scheduling [6, 7, 10],
timetabling [21], vehicle routing [3], cutting and packing [16], the theoretical understanding of selection
hyper-heuristics is very limited. Some insights into the behaviour of selection heuristics have been achieved
via landscape analyses [17, 18, 19]. Concerning their performance, [14] presented the first runtime analysis of
selection-perturbation hyper-heuristics. They considered a Simple Random hyper-heuristic [6] that at each
step randomly chooses between low-level heuristics and presented an example benchmark function class,
called GapPath, where it is necessary to use more than one low-level heuristic to optimise the problem.
Similar results have also been presented by [11].
A comparative time-complexity analysis of selection hyper-heuristics has recently been presented by [1].
They considered several common selection mechanisms, namely Simple Random, Permutation, Random
Gradient and Greedy [6, 7] and analysed their performance on the standard LeadingOnes benchmark
function when using a low-level heuristic set consisting of a 1-bit flip and a 2-bit flip operator (i.e., the
same set previously considered by [14]). The runtime analysis results show that the four ‘simple’ selection
mechanisms have the same asymptotic runtime, while experimental trials indicate that the runtimes are
practically equivalent. Recently, additive Reinforcement Learning selection was, under mild assumptions,
also shown to often have asymptotically equivalent performance to Simple Random selection, including for
the same problem setting (i.e., LeadingOnes selecting between 1-bit and 2-bit mutation operators) [2].
In particular, the results indicate that selection mechanisms such as additive Reinforcement Learning and
Random Gradient do not learn to exploit the more successful low-level heuristics and end up having the
same performance as Simple Random selection.
The main idea behind the learning mechanisms considered above is to continue to exploit the currently
selected heuristic as long as it is successful. Unlike construction heuristics, where iterating a greedy move
on a currently successful heuristic may work for several consecutive construction steps, the probability that
a promising heuristic is successful in the next step is relatively low when perturbing a reasonable solution to
a combinatorial optimisation problem.
In this paper, we generalise the ‘simple’ selection-perturbation learning mechanisms analysed by [1]
so success can be measured over some fixed period of time τ (i.e., Exploitation Stage), rather than in a
single iteration. Since the Simple Random and Permutation mechanisms do not use any feedback from the
optimisation process (i.e., do not attempt to learn), we only generalise the Greedy and the Random Gradient
learning mechanisms.
We first show that the learning period τ of the generalised hyper-heuristics is necessary, by presenting
an example function, Generalised GapPath with Traps (GGPT), inspired by the GapPath function of [14].
We initially show that the generalised hyper-heuristics are efficient on GapPath, before generalising the
function such that it is necessary to learn to prefer one operator over another. Then we add points of high
non-optimal fitness throughout the function, and show that the ‘simple’ mechanisms fail on the function
with overwhelming probability, while proving that the generalised hyper-heuristics find the global optimum
of the function with overwhelming probability, given a sufficiently large learning period τ = Ω(n3 ).
Afterwards we use the LeadingOnes (LO) benchmark function to show that the hyper-heuristics can
be surprisingly fast. We first give exact runtime results for the ‘simple’ mechanisms on LO, proving that
2
2
they all have expected runtime ln(3)
2 n + o(n ), confirming what was suggested by the experimental analysis
of [1]. This result indicates that all the ‘simple’ mechanisms essentially choose operators at random in each
iteration, and perform worse than the single operator that always flips 1-bit (i.e., RLS) which has a runtime
on LO of 12 n2 . We then prove upper bounds on the same function for the Generalised Random Gradient
(GRG) and Generalised Greedy (GG) hyper-heuristics. We rigorously prove that both the generalised hyperheuristics have a better runtime than RLS up to lower order terms for appropriately chosen values for the
parameter τ . Furthermore, the GRG hyper-heuristic can achieve the proven best possible runtime up to
lower order terms for an algorithm using just two mutation operators, 1+ln(2)
n2 + o(n2 ), for τ that satisfies
4
1
the GG hyper-heuristic,
we show that for a
both τ = ω(n) and τ ≤ ( 2 − ǫ)n ln(n), for ǫ = Θ(1). Concerning


arctan(2)
n2 + o(n2 ) ≈ 0.47797n2 + o(n2 ).
learning period τ ∈ ω(n) ∩ o(n2 ), its runtime is at most ln(5)
8 +
4
The tightness of the upper bound is shown by proving a matching runtime for an ideal Greedy algorithm
which performs a Decision Stage ‘for free’ in every iteration. This proves that GG is not as fast as GRG for
LO, but is still faster than either of its low-level heuristics applied alone.
Next we introduce a new hyper-heuristic, that we call Generalised Greedy Gradient (GGG), which com-

2

Algorithm 1 Simple Selection Hyper-heuristic [6, 7, 1]
1: Choose s ∈ S uniformly at random
2: while stopping conditions not satisfied do
3:
Choose h ∈ H according to the learning mechanism
4:
s′ ← h(s)
5:
if f (s′ ) > f (s) then
6:
s ← s′
bines the learning ideas of both the GRG and GG hyper-heuristics. In particular, it uses the Decision Stage
of GG and the Exploitation Stage of GRG. We show that it is just as efficient as the other generalised
hyper-heuristics on GapPath, and GGPT for τ = Ω(n3 ) w.o.p.. Furthermore it requires lower learning
periods τ to match the performance of GRG for LO.
Since all the presented results consider hyper-heuristics that choose between only two operators, we
present an analysis of the hyper-heuristics for LeadingOnes when they are allowed to choose between
k = o(n) operators. We first show that including more operators is detrimental to the performance of the
‘simple’ mechanisms. On the other hand, we prove that the performance of the GRG hyper-heuristic improves
as the number of available operators to choose from increases. In particular, when using k operators, GRG
is faster than the best possible performance achievable by using only k − 1 operators, for k = o(n).
We conclude the paper with an experimental analysis of the hyper-heuristics for realistic problem sizes.
The experiments confirm that all generalised hyper-heuristics outperform the single operators and that GRG
and GGG are faster than GG on LO. For two operators, it is shown how proper choices for the parameter τ can
lead to the near optimal performance, while a relationship between the performance of the hyper-heuristics
and the problem size n is suggested. For hyper-heuristics that are able to choose between more than two
operators, the experiments show that the performance of GRG and GGG improves with more operators
with appropriate choices of τ . The performance of the GG hyper-heuristic is worsened by including more
operators, yet it still outperforms RLS.
The rest of the paper is structured as follows. In Section 2, we formally introduce the hyper-heuristic
framework together with the ‘simple’ selection hyper-heuristics and the generalised ones. In Section 3 we
present the runtime results for the ‘simple’ and generalised hyper-heuristics on the GapPath and GGPT
functions. In Section 4 we analyse the ‘simple’ and generalised hyper-heuristics on the LeadingOnes
benchmark function. In Section 5 we introduce and theoretically analyse the Generalised Greedy Gradient
hyper-heuristic. In Section 6 we present the results for hyper-heuristics that choose between more than two
operators. Section 7 presents the experimental analysis. In the conclusion we present a discussion and some
avenues for future work.
Compared to its conference version [15] this manuscript has been considerably extended. The results of
Section 4 have been generalised for any values of τ less than ( 21 − ǫ)n ln n, for ǫ = Θ(1) and n2 for GRG and
GG respectively. In general, the results have been considerably strengthened. In particular, compared to the
extended abstract, in the present manuscript we prove that GRG and GGG achieve optimal runtimes for
LO. Section 5 and Section 6 are completely new additions, while a more comprehensive set of experiments
is included in Section 7.

2

Preliminaries

Let S be a finite search space, H a set of low-level heuristics and f : S → R+ a cost function. Algorithm 1
shows the pseudocode representation for a ‘simple’ selection hyper-heuristic as used in previous theoretical
analyses [1].
The following learning mechanisms have been commonly used in the literature to solve combinatorial
optimisation problems [6, 7]: Simple Random, which selects a low-level heuristic independently with
probability ph in each iteration (usually ph = 1/|H|, i.e., uniformly at random); Permutation, which
generates a random ordering of low-level heuristics and returns them in that sequence when called by the
hyper-heuristic; Greedy, which applies all available low-level heuristics in parallel and returns the best
found solution; Random Gradient, which randomly selects a low-level heuristic, and keeps using it as long

3

as it obtains improvements.
[1] analysed the runtime of these four ‘simple’ mechanisms1 for the LeadingOnes benchmark function,
choosing between flipping either one, or two, randomly chosen bits of the bit string (H = {1BitFlip, 2BitFlip}).
We derive the exact runtimes in Section 4. It was shown experimentally by [1] that all mechanisms have the
same performance as just choosing low-level heuristics at random. By making a heuristic selection decision in
every iteration without taking past performance into account, the ‘simple’ mechanisms do not have enough
time to learn which operator is preferable at the current optimisation stage.
In this paper we generalise the ‘simple’ mechanisms to allow a longer time period to decide whether a
low-level heuristic is currently successful or not, aiming to maintain the intrinsic ideas of the ‘simple’ learning
mechanisms while generalising sufficiently to allow learning to take place. In particular, we consider:
Generalised Greedy (GG), where all low-level heuristics are tested on the same candidate solution
until an improvement is found (Decision Stage). The improvement (chosen uniformly at random if there
are multiple ones) is then accepted, and the corresponding operator is run for a fixed period of time τ
(Exploitation Stage).
Generalised Random Gradient (GRG), where a low-level heuristic is chosen uniformly at random
(Decision Stage) and run for a period of fixed time τ . If an improvement is found before the end of the
period, then a new period of time τ is immediately initialised (Exploitation Stage). If the chosen operator
fails to provide an improvement in τ iterations, a new operator is chosen at random.

3

Learning is Necessary

In this section we consider the GapPath function (GP) previously introduced by [14] as an example to show
that applying multiple low-level heuristics may be necessary. We prove that the generalised hyper-heuristics
are also efficient on the problem. We then generalise the GP function to make one operator useful more
often than the other, and add points of very high non-optimal fitness along the path that ‘trap’ algorithms
that have not learned to prefer one operator to the other. The result will be that the ‘simple’ mechanisms
fail w.o.p., while the generalised hyper-heuristics can find the global optimum efficiently w.o.p..

3.1

GapPath

The GapPath function is defined as follows [14]:
(
ZM(x)
if Ridge(x) mod 3 = 1
GP(x) :=
ZM(x) + 2nRidge(x) otherwise
Pn
where ZM(x) := i=1 (1 − xi ), and Ridge(x) := i if x = 1i 0n−i , and 0 otherwise.
The function consists of a short path which corresponds to all search points of the form 1i 0n−i . The path
contains gaps where the function values are inferior to the rest of the path. Such gaps consist of all path
points where i ≡ 1 (mod 3). As a result of these gaps, an algorithm that only uses either the 1BitFlip or
the 2BitFlip operator will have infinite expected runtime, since it is necessary to alternate the operators
in order to make progress on the path. [14] prove that the runtime of the Simple Random mechanism,
initialised on the 0n bit
and usingonly the 1BitFlip and 2BitFlip operators with probability p and
 string
3
n2
−3n2
for any probability p ∈ (0, 1). In the following two theorems we
+ 3(1−p)p
1 − p respectively, is n6(1−p)
show that the generalised hyper-heuristics are also efficient on GapPath when choosing between the same
two operators.
Theorem 1 The expected runtime of the Generalised Greedy hyper-heuristic, when initialised on the 0n bit
string, for GapPath is n3 /3 + 2n2 /3 + 2τ n/3 − τ .
Proof: The GP function is optimised by requiring multiple repetitions of 1-bit and 2-bit consecutive
improvements. There is only one possible successful move at each point on the path and only the use of the
correct operator will lead to an improvement.
1 Throughout

the paper, bounds on the runtimes of the considered ‘simple’ mechanisms refer to the number of fitness
evaluations performed by Algorithm 1 using these mechanisms.

4

If a 1-bit improvement is necessary, the success probability of the 1BitFlip operator is 1/n, implying
n expected 1-bit mutations before an improvement is found (by standard waiting time arguments). During
this time, n 2-bit mutations will be performed in parallel, as the Generalised Greedy hyper-heuristic applies
both operators during the Decision Stage.
When a 2-bit improvement is necessary, the success probability of the 2BitFlip operator is 1/n · 1/n · 2
(since two specific bits must be flipped, but can be chosen in either order) implying n2 /2 expected 2-bit
mutations before an improvement is found. The same number of 1-bit mutations will be evaluated in parallel.
After an operator has succeeded, the Generalised Greedy hyper-heuristic will deterministically apply
the successful operator (on its own) for another τ iterations (the Exploitation Stage), during which no
improvement can occur (due to the nature of the GP function), before starting the next Decision Stage.
Initially, a 2-bit improvement is required. The expected number of fitness function evaluations needed
to reach the first point on the path 110n−2 from the 0n bit string is 2 · n2 /2 = n2 , which will be followed by
τ non-improving steps. The next improvement will then occur by the 1BitFlip operator after an expected
2n steps, followed by τ unsuccessful 1-bit flips. Hence, the expected time to optimise the first three bits is
n2 + τ + 2n + τ = n2 + 2n + 2τ .
This three bit pattern occurs a total of n/3 times before the optimum is reached, and since the global
optimum is reached just before the final Exploitation Stage starts, the total expected runtime is E(TGG ) =
n/3 · (n2 + 2(n + τ )) − τ = n3 /3 + 2n2 /3 + 2τ n/3 − τ .

Theorem 2 The expected runtime of the Generalised Random Gradient hyper-heuristic, when initialised on
the 0n bit string, for GapPath is at most n3 /3 + 2n2 /3 + 4τ n/3 − τ .
Proof: The Generalised Random Gradient hyper-heuristic chooses a mutation operator uniformly at random, and applies it for a period of τ iterations. If an improvement is produced, a new period of τ iterations
using the same operator is started immediately.
Let T1 and T2 respectively be the number of iterations before a 1-bit or a 2-bit improvement is constructed
when it is possible to do so. If the appropriate operator i is chosen (i.e., with probability 1/2), it may succeed
with probability pi in each iteration, or it may fail during all τ iterations with probability (1 − pi )τ in which
case the random choice is repeated. If the other operator is chosen, τ iterations are wasted before the random
choice is repeated. Combined, using qi := 1 − pi for brevity:
!
!
τ
X
1
1
k−1
τ
kqi pi + qi (τ + E(Ti )) + (τ + E(Ti ))
E(Ti ) =
2
2
k=1
!
τ
X
=
kqik−1 p + qiτ E(Ti + τ ) + τ
(1)
=

k=1
∞
X
j=0

=

∞
X

k=1

τ
X

(k +

jτ )qijτ +k−1 pi

k=1

kqik−1 pi

!

+τ +

!

+

τ qijτ

!

τ qiτ
1
τ qiτ
=
+
τ
+
.
1 − qiτ
pi
1 − qiτ

(2)

(3)

A simple rearrangement yields (1), and applying it recursively to the qijτ E(Ti + jτ ) terms yields (2). As
the inner sums are contiguous, a rearrangement in (3) simplifies the expression to an expectation of a
geometrically-distributed variable and a sum of an infinite geometric series. As the expected number of
τ qiτ
qiτ
periods of time τ where the correct operator is applied but does not produce an improvement is 1−q
τ , 1−q τ is
i
i
a lower bound on the number of iterations where a correct operator is applied before a success (i.e., 1/pi ) and
τ qτ
τ + 1−qi τ is an upper bound on 1/pi . Substituting these bounds into Eq. (3) yields 2/pi ≤ E(Ti ) ≤ 2/pi + τ .
i
After an improvement is constructed, the successful operator will run for an additional τ iterations while
not being able to construct the next improvement. To reach the optimum from 0n , improvements must be
constructed by alternating 2-bit and 1-bit mutations n/3 times, while the final τ -iteration Exploitation Stage
is unnecessary. The total expected optimisation time is therefore:
n
(E(T1 ) + E(T2 ) + 2τ ) − τ ≤ n3 /3 + 2n2 /3 + 4τ n/3 − τ.
3
5



3.2

Generalising GapPath

Having shown that the generalised hyper-heuristics are efficient on GP, we now introduce a function class
on which it is necessary for the hyper-heuristics to learn which operator to use, if they are to be efficient.
We will prove that the proposed generalised hyper-heuristics outperform the ‘simple’ mechanisms.
Let n be of the form n = d(2k + 1) for some d, k ∈ N.
(
ZM(x)
if Ridge(x) ∈ Sk
GGPk (x) :=
ZM(x) + 2nRidge(x)
otherwise
where Sk = {c(2k + 1) + 1 − 2β | c, β ∈ N : c ≤ d, β ≤ k}, and ZM(x) and Ridge(x) defined as in Section 3.
This function is similar to the GapPath function, but requires k consecutive 2-bit successes after the 1-bit
improvement is successfully executed at search points of the form 1(c−1)(2k+1) 0n−((c−1)(2k+1)) for 0 ≤ c ≤ d.
Hence learning to use 2-bit flips often leads to improved performance.
We modify the GGPk function by inserting a ‘trap’ point (point of high non-optimal fitness) at a random
position within each group of k 2-bit flips. These ‘trap’ points can be reached by a 1-bit mutation, while
the next path point remains reachable only by a 2-bit mutation, and are local optima for both mutation
operators. If a ‘trap’ point is ever constructed, the algorithm will not be able to reach the global optimum.
Since there is a finite probability for any mechanism to construct a ‘trap’ point, the expected runtimes will
all be infinite by the law of total probability. Hence, we consider the success probabilities for the ‘simple’
mechanisms and generalised hyper-heuristics on this modified function (denoted GGPT).
Theorem 3 Starting at 0n , all of the ‘simple’ selection mechanisms will fail to find the global optimum on
GGPT in finite time, with probability at least 1 − n−Ω(n) .
Proof: We will show that when each mechanism is at a point from which a ‘trap’ point is accessible, it will
construct the ‘trap’ point before the next path point with probability 1−O(1/n). If this holds, as there are at
least n/(2k + 1) = Ω(n) points from which a ‘trap’ point is accessible, the ‘simple’ mechanisms will therefore
construct a ‘trap’ point before reaching the global optimum with probability 1 − O(1/n)Ω(n) = 1 − n−Ω(n) .
The Greedy mechanism applies both mutation operators in one iteration. The probability that a ‘trap’
point is constructed via a 1-bit mutation is 1/n, while the probability that the next path point is constructed
is 2/n2 . If both are constructed, the mechanism accepts the ‘trap’ point as it has higher fitness. The
1/n
probability that a ‘trap’ point is constructed before the next path point is therefore at least 1/n+2/n
2 =
2
1 − n+2 = 1 − O(1/n).
The Permutation mechanism, following a two-bit success leading to a point from which a ‘trap’ point
is accessible, will perform 1-bit and 2-bit mutations in this order. The probability that a ‘trap’ point is
constructed over two iterations is thus 1/n, while the probability that the next path point is constructed
over two iterations is (1 − 1/n) · 2/n2 . The probability that a ‘trap’ point is constructed before the next path
1/n
1/n
2
point is therefore 1/n+(1−1/n)2/n
2 = 1/n+2/n2 + n2 +4n+2−4/n = 1 − O(1/n).
The Simple Random mechanism constructs a ‘trap’ point with probability 1/(2n), and the next path
point with probability 1/n2 . The probability that a ‘trap’ point is constructed before the next path point is
1/(2n)
2
therefore at least 1/(2n)+1/n
2 = 1 − n+2 = 1 − O(1/n).
The Random Gradient mechanism behaves equivalently to the Simple Random mechanism, unless it
manages to construct an improvement by a two-bit mutation immediately following another two-bit improvement. The probability that an individual ‘trap’ point is skipped in this manner is 1 − 2/n2 = O(1/n),
and thus the probability that the Random Gradient constructs the ‘trap’ point before the next path point
is (1 − O(1/n))2 = 1 − O(1/n).

On the other hand, the following theorem shows that with sufficiently large τ , the generalised hyper-heuristics
can avoid the traps w.o.p..
Theorem 4 Starting at 0n for τ = Ω(n3 ), the Generalised Random Gradient hyper-heuristic will find the
kn3
4τ n
+ 2(2k+1)
+ O(n2 ) steps with probability at least
global optimum of GGPT (with constant k) in at most 2k+1
6

1 − 2−Ω(n) . However, for τ = O(n2 ), the Generalised Random Gradient hyper-heuristic will fail to reach the
global optimum of GGPT in finite time with probability at least 1 − 2−Ω(n) .
Proof: The Generalised Random Gradient hyper-heuristic avoids making a decision inside the two-bit
region if it is able to construct k−1 two-bit improvements within τ iterations each. The probability of success
for a 2-bit mutation is 2/n2 ; the probability of no successes in τ steps is (1 − 2/n2 )τ and the probability of
(at least) one success in a period of τ steps is this value subtracted from 1. Thus, the probability that all
k−1
k − 1 two-bit improvements are found in time is 1 − (1 − 2/n2 )τ
.

cn2 k−1
For τ = cn2 , where c is a constant, the probability of the required k−1 successful periods is 1 − 1 − 2/n2
=

(1 − e−2c − o(1))k−1 = Θ(1), and so the probability of failing to do so is at least constant. If another random
Decision Stage is performed inside the region of two-bit improvements, a ‘trap’ point is accessible via a 1-bit
mutation from the point at which the decision occurs with probability at least 1/(k − 1) = Ω(1) (as traps
are placed uniformly at random inside these regions), and is found by the Generalised Random Gradient
2
hyper-heuristic with probability at least 1/2 · (1 − 1/n)cn ≥ 1/4. Thus, the probability that the no ‘trap’
point is constructed in a single region of k two-bit improvements is at most a constant smaller than one,
which means that over the n/(2k + 1) such regions, the probability that a ‘trap’ point is constructed is at
least 1 − 2−Ω(n) .
For τ = cn3 , where c is a constant, the probability that all T = (k−1)·n/(2k+1) = Θ(n) two-bit successes

cn3 T
are constructed within τ iterations is at least 1 − 1 − 2/n2
= (1−e−2cn)T ≥ 1−T e−2cn = 1−e−Ω(n)
by applying a union bound. Thus, with overwhelming probability, the algorithm is not trapped, and the
expected optimisation time is


k
n
4τ n
kn3
n + 2τ + n2 + 2τ =
E(TGRG | no trap) ≤
+
+ O(n2 ),
2k + 1
2
2k + 1 2(2k + 1)
with the 2τ terms corresponding to using the wrong operator for, in expectation, one period of τ iterations
at the start of the phase, and using the successful operator for τ iterations while the next improvement can
only be constructed by the other operator.

The following theorem can be proven using a similar approach.
Theorem 5 Starting at 0n for τ = Ω(n3 ), the Generalised Greedy hyper-heuristic will find the global optin3
2τ n
+ 2k+1
+ O(n2 ) steps with probability at least 1 − 2−Ω(n) .
mum of GGPT (with constant k) in at most 2k+1
2
However, for τ = O(n ), the Generalised Greedy hyper-heuristic will fail to reach the global optimum of
GGPT in finite time with probability at least 1 − 2−Ω(n) .
Proof: The Generalised Greedy hyper-heuristic avoids making a decision inside the two-bit region if and
only if it can produce k − 1 two-bit improvements within τ iterations following the first two-bit improvement.
Let X be a binomially-distributed random variable with parameters p = 2/n2 (the success probability of the
two-bit mutation operator) and τ trials, and thus E(X) = 2τ /n2 . We note that the probability distribution
of X up to k − 1 is identical to that of the number of two-bit improvements constructed during the Decision
Stage, while X ≥ k − 1 corresponds to constructing all remaining k − 1 improvements.
For τ = cn2 , we note that the probability of constructing exactly zero improvements during the τ
2
iterations is at least (1 − 2/n2 )cn ≥ e−2c − O(1/n2 ) = Ω(1). If another Decision Stage is performed inside
the region of two-bit improvements, a ‘trap’ point is accessible via a 1-bit mutation from the point at which
the decision occurs with probability at least 1/(k − 1) = Ω(1) (as traps are placed uniformly at random inside
these regions), and is found by the Greedy mechanism with probability at least (1/n)/(1/n + 2/n2 ) ≥ 1/4.
Thus, the probability that the Generalised Greedy hyper-heuristic does not construct a ‘trap’ point in a
single region of k two-bit improvements is at most a constant smaller than one, which means that over the
n/(2k + 1) such regions, the probability that a ‘trap’ point is constructed is at least 1 − 2−Ω(n) .
For τ = cn3 , where c is a constant, E(X) = 2cn. Applying a Chernoff bound, we note that the probability
of observing fewer than cn successes in τ steps is at most e−Ω(n) , and if n is sufficiently large, cn > k. Thus,
with overwhelming probability, a decision step does not occur inside a single two-bit region, and by a union
7

bound, does not occur inside any of the n/(2k + 1) two-bit regions in the bit string. Thus, with overwhelming
probability, the algorithm is not trapped, and the expected optimisation time is
E(TGG | no trap) ≤


n
2τ n
n3
2n + τ + n2 + τ =
+
+ O(n2 ).
2k + 1
2k + 1 2k + 1


We point out that, if the function values were inverted such that the ‘trap’ points had optimal fitness, and
the 1n bit string did not, then the generalised hyper-heuristics would fail to find any of the global optima
(w.o.p), while the ‘simple’ mechanisms would succeed (w.o.p). It is not surprising that learning mechanisms
fail on a function especially designed to deceive them.

4

Hyper-Heuristics Are Faster

In this section we show that the generalised hyper-heuristics can outperform low-level heuristics, even
when the latter are efficient for the problem at hand. We consider the LeadingOnes function, LO(x) :=
Pn Q i
i=1
j−1 xj , which counts the number of consecutive one-bits in a bit string before the first zero-bit.
It is well known that the standard (1+1)-EA and RLS algorithms on LeadingOnes have expected
2
2
2
runtimes of e−1
2 n − o(n ) and 0.5n fitness function evaluations respectively [4]. In the following we show
that the generalised hyper-heuristics are more efficient.
We first introduce a lower bound on the runtime of all algorithms which use only the 1BitFlip and
2BitFlip operators. Since the 1BitFlip operator has a success probability of n1 while the 2BitFlip
· 2 = (2n − 2i − 2)/n2 where i = LO(x), it is easy to see that for the first n/2 leading
operator of n1 · n−i−1
n
ones the 2BitFlip operator is more effective, while the 1BitFlip operator is preferable afterwards. Hence,
the expected runtime of an algorithm using these operators in such a way gives a trivial lower bound on all
stochastic unbiased algorithms using only the same two operators. This can be easily proved following the
approach used for the (1+1)-EA by [4].
Theorem 6 ([4]) The expected time needed to find the optimum of LeadingOnes given random initialisation is
n
1X
An−i ,
E(T ) = T n =
2 i=1

where An−i is the expected time needed to find an improvement given a solution with fitness i.

Theorem 7 The best possible expected runtime on LeadingOnes for a stochastic, unbiased algorithm using
only the 1BitFlip and 2BitFlip operators is 1+ln(2)
n2 + O(n) ≈ 0.42329n2 + O(n).
4
Proof: We partition the analysis into two phases: Phase 1, where the 2BitFlip operator is used for the
first half of the search, and Phase 2, where the 1BitFlip operator is used for the second half of the search.
Phase 1 The 2BitFlip operator is stochastic and unbiased, so the result from Theorem 6 holds for this
phase.
To find the expected runtime for this phase, we can consider every point LO(x) ≥ n2 to be optimal. That
n2
, we can consider, for i ≥ n/2, An−i = 0.
is, while for 0 ≤ i < n/2, An−i = 2n−2i−2
Hence, we note that for Phase 1,
E(T1 ) =

n/2−1
n−1
n−1
1X
n2
1 X
1 X n2
An−i =
=
2 i=0
2 i=0 2n − 2i − 2
2
2k
k=n/2

=

n2
4

n−1
X

k=n/2


1
n2 
Hn−1 − Hn/2−1 ,
=
k
4

8

where Hx is the xth Harmonic number, which can be bounded by
ln(n + 1) + γ −

1
1
≤ Hn ≤ ln(n + 1) + γ −
,
n+1
2(n + 1)

and γ is the Euler-Mascheroni constant (γ ≈ 0.57722 . . . ). Hence,

3  n2
n2
·
≤ E(T1 ) ≤ ln(2) +
,
ln(2) ·
4
2n
4
i.e.,
ln(2) 2
n + O(n).
E(T1 ) =
4
Phase 2 The runtime for Phase 2 can be calculated using Theorem 6 with An−i = n for i ≥ n/2. Similarly
to Phase 1, we state An−i = 0 for i < n/2.
n/2
n−1
1
1X
1X
n2
n = · n · n/2 =
E(T2 ) =
An−i =
.
2 i=0
2 j=1
2
4

Hence, the total expected runtime is:
E(T ) = E(T1 ) + E(T2 ) =

ln(2) 2
1
1 + ln(2) 2
n + O(n) + n2 =
n + O(n).
4
4
4


The rest of the section is structured as follows. In Subsection 4.1 we show that the ‘simple’ hyper-heuristic
mechanisms all perform equivalently to Simple Random for LeadingOnes, up to lower order terms. In
Subsection 4.2 we show that the generalised hyper-heuristics are much faster.

4.1

‘Simple’ Mechanisms

In this section we show that the standard ‘simple’ selection mechanisms all have the same runtime on LeadingOnes. The following theorem derives the runtime for the Simple Random mechanism. The subsequent
corollary extends the result to all the other ‘simple’ mechanisms.
Theorem 8 The expected runtime of the Simple Random mechanism on LeadingOnes for p ∈ (0, 1) is
1
2
2
4(1−p) ln ((2 − p)/p) n + o(n ). If p = 0 the expected runtime is infinite. If p = 1, the expected runtime is
2
0.5n .
Proof: If p = 0, only the 2BitFlip operator is used. There is a finite probability of reaching the point
1n−1 0, which cannot be improved by using the 2BitFlip operator. Hence, by the law of total probability,
the expected runtime is infinite.
2
If p = 1, only
Pnthe 1BitFlip operator is used, resulting in exactly RLS, which has expected runtime 0.5n .
E(Tp ) = 12 i=1 An−i , where An−i is the expected time needed to find an improvement given a solution
with fitness i, and the algorithm is initialised with a search point chosen uniformly at random. In each iteration, the 1BitFlip operator is chosen with probability p; the 2BitFlip operator is chosen with probability
1 − p. Hence, (An−i )−1 = p · n1 + (1 − p) · 2n−2i−2
, and
n2
An−i =

1
p
n

+

(1−p)(2n−2i−2)
n2

=

n2
2(1 − p)(n − i − 1) + np

The total expected runtime is
n−1
n
n2
n2 X
1
1X
=
2 i=0 2(1 − p)(n − i − 1) + np
2
(2p − 2)k + (2 − p)n
k=1
!
!
n + (2−p)n
n2
n2 ln((2 − p)/p)
2p−2
ln
+ o(n2 ),
=
+
o(1)
=
(2−p)n
2(2p − 2)
4(1 − p)

E(T ) =

2p−2

9

(4)

(5)

where Equation 4 hbecomes
Equation
5i via the fact that


Pn
n+bn/a
1
1
+ o(1) with a = 2p − 2 and b = 2 − p.

k=1 a·k+b·n = a ln
bn/a
When p = 0.5 (i.e., equal chance of choosing each operator in each iteration), the standard Simple Random
2
2
mechanism has expected runtime ln(3)
2 n + o(n ). The runtime improves with increasing p, hence the optimal
choice is p = 1.
Corollary 9 The expected runtime of the Permutation, Greedy and Random Gradient mechanisms on
2
2
LeadingOnes is ln(3)
2 n + o(n ).
Proof: For the Greedy and Permutation mechanisms, let pi = 1/n + (1 − 1/n)(2n − 2i − 2)/n2 be the
probability that at least one improvement is constructed in respectively one or two iterations. To upper bound
the optimisation time, we note that the difference between 2/pi (i.e., the waiting time for an improvement
to be constructed in terms of fitness evaluations) and the An−i waiting times used to prove Theorem 8 is
at most constant, and thus the difference between these mechanisms and Simple Random expected times is
limited to lower-order terms. We note that with probability at most 2/n2 , both mutations considered are
improvements; in such a case, we can consider an improvement step to be made in 0 iterations. As this
occurs at most a constant number of times in expectation, and the maximum waiting time for any improving
step is O(n), the lower-bound differs from the upper bound by at most an O(n) term. Thus, the expected
runtime of these mechanisms is also ln(3)/2 · n2 + o(n2 ).
For the Random Gradient mechanism, we note that the probability that an operator, when repeated
following a success, is successful again is at most 2/n. Since there are at most n improvements to be made
throughout the search space, the expected number of repeats which produce an improvement is at most
2. When not repeating a successful operator, the Random Gradient mechanism behaves identically to the
Simple Random mechanism. Its expected runtime is therefore at least the runtime of the Simple Random
mechanism less an O(n) term, and at most the runtime of the Simple Random mechanism plus n (as there
are at most n iterations where the mechanisms differ in operator selection). Thus, its expected runtime is
also ln(3)/2 · n2 + o(n2 ).


4.2

Generalised Hyper-heuristics

In this section we present a rigorous theoretical analysis of the generalised hyper-heuristics on LeadingOnes.
We start by introducing some important tools which will be used in the analyses.
Theorem 10 Wald’s Equation [22, 9] Let T be a random variable with bounded expectation and let
X1 , X2 , . . . be non-negative random variables with E(Xi |T ≥ i) ≤ C. Then
#
" T
X
Xi ≤ E[T ] · C.
E
i=1

Theorem 11 Additive Drift Theorem [12, 20] Let {Xt }t≥0 be a Markov process over a finite set of
states S, and g : S → R+
0 a function that assigns a non-negative real number to every state. Let the time to
reach the optimum be T := min{t ≥ 0 : g(Xt ) = 0}. If there exists δ > 0 such that at any time step t ≥ 0
and at any state Xt ≥ 0 the following condition holds:
E(∆(t)|g(Xt ) > 0) = E(g(Xt ) − g(Xt+1 )|g(Xt ) > 0) ≥ δ,
then
E(T |X0 ) ≤
and
E(T ) ≤

g(X0 )
δ

E(g(X0 ))
.
δ

Theorem 12 Variable Drift Theorem [13] Let (Xt )t≥0 be a stochastic process over some state space S ⊆
{0} ∪ [xmin , xmax ], where xmin > 0. Let h(x) be an integrable, monotone increasing function on [xmin , xmax ]
10

such that E(Xt − Xt+1 | Xt ≥ xmin ) ≥ h(Xt ). Then it holds for the first hitting time T := min{t | Xt = 0}
that
Z X0
xmin
1
E(T | X0 ) ≤
+
dx.
h(xmin )
xmin h(x)
4.2.1

Generalised Random Gradient

The following theorem considers the Generalised Random Gradient hyper-heuristic. The theorem allows us
to show that the expected runtime of the hyper-heuristic for the function is the optimal runtime that may
be achieved by using two operators. This result will be highlighted in Corollary 15 and depicted in Figure 1.
Theorem 13 The
 expected runtime of the Generalised Random Gradient hyper-heuristic on LeadingOnes
with τ ≤ 12 − ǫ n ln(n), for ǫ = Θ(1), is at most



τ
τ
0.5
w 2τ + e n M (1) + e2 n (1−(j−1)/w) M
2
X
n
1−j/w
n 
 + o(n2 )
τ
τ
2 j=1
(e n + e2 n (1−j/w) − 2)w
where M (x) := min( nτ , x), for any w ∈ Ω(1) ∩ o



n
exp(2τ /n)



.

Proof: For the purpose of this proof, we partition the optimisation process into w chunks based on the
value of the LeadingOnes fitness function: during chunk j, the LO value of the current solution is at least
(j − 1)n/w and less than j · n/w. After all the w chunks have been completed, the global optimum, with an
LO value of n, will have been found.
We upper-bound the expectation of the runtime T of the Generalised Random Gradient hyper-heuristic
on LO by the sum of the expected values of Tj , the runtimes on each chunk of the optimisation process,
plus the times taken to begin a chunk. As our analysis
Pw of E(Tj ) requires the chunk to start with a random
choice of mutation operator, we bound E(T ) ≤ j=1 (E(Tj ) + E(Sj+1 )) where Sj+1 is a random variable
denoting the expected number of iterations between the first solution in chunk j +1 being constructed and the
following random operator choice. We will later show that with proper parameter choices, the contribution
of the Sj+1 terms can be bounded by o(n2 ), and therefore does not affect the leading constant in the overall
bound.
Let us now consider Tj , the number of iterations the hyper-heuristic spends in chunk j. Recall that
a mutation operator is selected uniformly at random, and is allowed to run until it fails to produce an
improvement for τ sequential iterations. Let Nj be a random variable denoting the number of random
operator choices the hyper-heuristic performs during chunk j, and Xj,1 , . . . , Xj,Nj be the number of iterations
PNj
Xj,k , and by applying Wald’s
the hyper-heuristic runs each chosen operator for. In which case, Tj = k=1
equation (Theorem 10), using E(Xj ) to denote an upper bound on all E(Xj,k ) in chunk j:
E(Tj ) =

PNj

k=1 E(Xj,k )

≤ E(Nj )E(Xj ).

(6)

To bound E(Nj ), the expected number of times the random operator selection is performed during chunk
j, we lower-bound the expected number of improvements found following the operator selection, and apply
the Additive Drift Theorem [12] to find the expected number of random operator selections occurring before
a sufficient number of improvements have been found to enter the next chunk.
Let F1 and F2 denote the events that the 1BitFlip and 2BitFlip operators fail to find an improvement
during τ iterations. For the 1BitFlip operator, this event occurs with probability P (F1 ) = (1 − 1/n)τ
τ
τ
throughout the process, which is within [e− n − 1/n, e− n ]. For the 2BitFlip operator, recall that during
chunk j, the ancestor individual has at most jn/w − 1, and at least (j − 1)n/w, one bits, and thus:
τ

τ

P (F2 ) ≤ (1 − 2 · (1/n) · (n − (jn/w − 1) − 1)/n) ≤ e−2 n (1−j/w) ,
τ
P (F2 ) ≥ (1 − 2(1/n)(n − (j − 1)n/w − 1)/n)

τ
2(1 − (j − 1)/w)
2τ
> 1−
≥ e− n (1−(j−1)/w) − 1/n.
n
11

We note that a geometric distribution with parameter p = P (F1 ) can be used to model the number of
improvements that the 1BitFlip operator finds prior to failing to find an improvement for τ iterations; the
expectation of this distribution is (1 − p)/p = 1/p − 1. Combined over both operators, the expected number
of improvements Dj produced following a single random operator selection during chunk j, E(Dj ), is greater
than:




1
2τ
1
1
1
τ
−1 +
− 1 ≥ e n /2 + e n (1−j/w) /2 − 1,
2 P (F1 )
2 P (F2 )
by inserting the upper bounds on P (F1 ) and P (F2 ). We use this expectation as the drift in the Additive
Drift Theorem to upper-bound E(Nj ). Recall that each chunk consists of advancing through at most n/w
fitness values; as bits beyond the leading ones prefix and the first zero bit remain uniformly distributed, at
most n/(2w) improvements by mutation are required in expectation. If each step of a random process in
expectation contributes E(Dj ) improvements by mutation, then the expected number of steps required to
complete chunk j is at most:
E(Nj ) ≤

n
n/(2w)
≤ τ
2τ
(1−j/w)
E(Dj )
n
n
(e + e
− 2)w

(7)

by the Additive Drift Theorem.
To bound E(Xj ), the expected number of iterations before a selected mutation operator fails to produce
an improvement for τ iterations, we apply Wald’s equation: let S be the number of improvements found
by the operator before it fails, and W1 , . . . , WS be the number of iterations it took to find each of those
improvements; then, once selected, the 1BitFlip operator runs for:
E(Xj | 1-bit) = τ +

S
X

E(Wk ) = E(S)E(W1 | S ≥ 1, 1-bit)

k=1

where τ accounts for the iterations immediately before failure, and the sum for the iterations preceding each
constructed improvement. Recall that E(S) = 1/P (F1 ) − 1 by the properties of the geometric distribution,
and observe that E(W1 | S ≥ 1) = E(W1 | W1 ≤ τ ) ≤ min(τ, E(W1 )). Using a waiting time argument for
E(W1 ) being equal to the reciprocal of the improvement probability for the 1BitFlip operator, we get (with
a similar argument for the two-bit mutation operator):
E(Xj | 1-bit) ≤ τ + (1/P (F1 ) − 1) min(τ, n),
E(Xj | 2-bit) ≤ τ + (1/P (F2 ) − 1) min (τ, n/(2(1 − j/w))) .
Combining these conditional expectations with lower bounds on P (F1 ) and P (F2 ) yields
E(Xj ) ≤ 1/2 · E(Xj | 1-bit) + 1/2 · E(Xj | 2-bit)
≤τ+

min(τ, n/(2 − 2j/w))
min(τ, n)
,
+
τ
2τ
2(e− n − 1/n) 2(e− n (1−(j−1)/w) − 1/n)

(8)

which can be simplified to:


min( nτ , 1/(2 − 2j/w))
min( nτ , 1)
n 2τ
+
E(Xj ) ≤
+ −τ
2τ
2 n
e n − 1/n e− n (1−(j−1)/w) − 1/n

τ 
τ

τ
2τ
n 2τ
+ O(1)
+ e n min
, 1 + e n (1−(j−1)/w) min
, (2 − 2j/w)−1
≤
2 n
n
n
using a/(b − c/n) = a/b + ac/(b2 n − bc) = a/b + O(1/n), where a, b, and c are constants with respect to n,
to limit the contributions of the −1/n terms in denominators to lower-order terms.
Finally, we can bound the overall runtime of the hyper-heuristic. Recall that Sj denotes the number
of iterations the hyper-heuristic spends in chunk j while using the random operator chosen during chunk
j − 1, and as E(Sj ) ≤ max (E(Xj | 1-bit), E(Xj | 2-bit)) < 2E(Xj ) = O (n exp(2τ /n)), and since w =

12

 P

w
n
2
o exp(2τ
j=1 E(Sj+1 ) = o(n ). Substituting the bounds (7) and (8) into (6) yields the theorem
/n) ,
statement:


w
w
X
X
E(Nj )E(Xj ) + o(n2 )
(E(Tj ) + E(Sj+1 )) ≤ 
E(T ) ≤
j=1

j=1

w

n2 X
≤ o(n2 ) +
×
2
j=1

2τ
n

2τ

τ
n

+ e min( nτ , 1) + e n (1−(j−1)/w) min
τ

2τ

(e n + e n (1−j/w) − 2)w



τ
0.5
n , 1−j/w



.


We can use this result to get a tight upper bound on the runtime of the simple Random Gradient mechanism.
We know the bound is tight by Theorem 8.
Corollary 14 The expected runtime of the Generalised Random Gradient hyper-heuristic on LeadingOnes,
1
with τ = 1 (i.e., ǫ = 21 − n ln
n ), is at most
ln(3) 2
n + o(n2 ).
2
Proof: We constrain w = ω(log(n)) ∩ o(n). Note that for τ = 1, we have min(τ /n, 1) = min(τ /n, 0.5/(1 −
j/w)) = 1/n. For w = ω(log(n)), we have e2/w = 1 + o(1).
If we plug in τ = 1 into our result, we obtain


1
1
w
n2 X n2 + e n · n1 + e2 n (1−(j−1)/w) · n1 
E(T ) ≤
+ o(n2 )
1
1
2 j=1
(e n + e2 n (1−j/w) − 2)w


2
1
w
n X e n + e2/w · e n (1−j/w) − 2 + 4 
+ o(n2 )
=
1
2
2 j=1
(e n + e n (1−j/w) − 2)w


w
4
1
n X 1
 + o(n2 )
+ ·
=
2 j=1 w w e n1 + e n2 (1−j/w) − 2

  exp(1/n)+2  

w
ln exp(2/n)
X
4
n
1
 + o(n2 ) = 
 n2 + o(n2 )
= 
· 1
2
2 j=1 w e n + e n (1−j/w) − 2
2 − exp(1/n)
=

ln(3) 2
n + o(n2 ).
2


We can also find parameter settings leading to the best-possible runtime, up to lower order terms, using
only the 1BitFlip and 2BitFlip operators, from Theorem 7. In [15], the authors looked at the parameter
setting τ = cn for constant c, and hence could not prove the optimal runtime.
Corollary 15 The expected runtime of the Generalised
Random Gradient hyper-heuristic on LeadingOnes,

with τ that satisfies both τ = ω(n) and τ ≤ 21 − ǫ n ln(n), for ǫ = Θ(1), is at most
1 + ln(2) 2
n + o(n2 ).
4





n
o(1)
.
exp(2τ /n) ∩ n
0.5
M ( 1−j/w ). Since we have

Proof: We constrain w ∈ ω(log n) ∩ o

Consider first the terms M (1) and
τ = ω(n), it is easy to see that M (1) = 1. For
0.5
0.5
0.5
M ( 1−j/w
), it is important to note that for the first half of the search, M ( 1−j/w
) = 1−j/w
, and in the second

13

0.5
0.5
half of the search, M ( 1−j/w
) = O(w) = no(1) (excluding the case when j = w in which M ( 1−j/w
)=

n

o(1)

). Note that

τ
n

2τ /n·1/w

τ
n

=

1/w

= ω(1) and e
= o(n ) = 1 + o(1). Hence:



2τ
τ
0.5
w 2τ + e n M (1) + e n (1−(j−1)/w) M
2
X
n
1−j/w
n 
 + o(n2 )
E(T ) ≤
τ
τ
2 j=1
(e n + e2 n (1−j/w) − 2)w



τ
2τ
0.5
w 2τ + e n + e2τ /n·1/w · e n (1−j/w) M
2
X
n
1−j/w
n 
 + o(n2 )
=
τ
τ
2
(1−j/w)
n
n
2 j=1
(e + e
− 2)w



τ
2τ
0.5
(1−j/w)
w 2τ
M 1−j/w
n2  X n + e n + e n
 + o(n2 )
=
τ
τ
2 j=1
(e n + e2 n (1−j/w) − 2)w





2τ
τ
0.5
w
n + e n (1−j/w) M
2τ
e
2
−
2
X
1−j/w
n 
1 
n +2

+
=
τ
τ
τ
τ
2 j=1 w e n + e2 n (1−j/w) − 2
e n + e2 n (1−j/w) − 2
+ o(n2 )



 τ

2τ
0.5
w
n + e n (1−j/w) M
2
e
X
1−j/w − 2
n 
1 
 + o(n2 ).
=
τ
τ
2 j=1 w
e n + e2 n (1−j/w) − 2

The exponential terms will dominate the summation term (since nτ = ω(1)). When j > w2 , we note that
w
exp(τ /n) > exp( 2τ
n (1 − j/w)) and this term will dominate the other. Vice versa for j < 2 , and at j = w/2,
the two values are equal. Hence, we can split the sum into two sections:



 τ

2τ
0.5
w
n + e n (1−j/w) M
e
−
2
2
X
1−j/w
1 
n 
 + o(n2 )
E(T ) ≤
τ
τ
2 j=1 w
e n + e2 n (1−j/w) − 2



!
2τ
 τ
w/2−1
0.5
(1−j/w)
w
2
2
X
· 1−j/w
n
n
n2  X 1 e n
1
e
n
+


=
+
τ
2τ
2
w
2w
2
w en
e n (1−j/w)
j=1
j=w/2+1

2

+ o(n )




w/2
2
X
n 
1  n2
1 + ln(2)
=
+
+ o(n2 ) =
n2 + o(n2 ).
4 j=1 w − j
4
4

Note that at j = w, the respective ‘dominating terms’ are exp(τ /n) and exp(2τ /n(1 − w/w)) = 1, and
0.5
) = nτ < 12 ln(n). Hence, exp(τ /n) will dominate.

M ( 1−j/w
4.2.2

Generalised Greedy

The following results regarding the runtime of the Generalised Greedy hyper-heuristic can be proved using
similar techniques and calculations to those used in the analysis of the Generalised Random Gradient hyperheuristic but applying the Variable Drift Theorem [13] instead of the Additive Drift Theorem.
To simplify the presentation of the proofs, we will use 2 as a bound on the expected increase in fitness
value following a successful mutation throughout the process. As the bits following the first zero-bit in any
individual remain uniformly distributed throughout the process, this expectation would be correct if the bit
string was of infinite length. We note that the law of total expectation can be used to prove that this overestimation will only affect lower-order terms in the derived runtimes, e.g. by using that the free-riders are
overwhelmingly unlikely to span to the end of the bit string while the parent individual has fitness at most
n − log2 n, and that a trivial upper bound for Generalised Greedy on the last k ≤ n bits is k(2n + τ ) = o(n2 ).
We begin by stating a lemma on the expected time and progress for a combined Decision and Exploitation
Stage.
14

Lemma 16 Let i = LeadingOnes(x(t) ) < n − 1, and Y (t) = n − i be the distance of the Generalised Greedy
hyper-heuristic’s current solution at the start of the t’th Decision Stage to the LeadingOnes optimum, and
let τ = o(n2 ). Then,
E(Y (t) − Y (t+1) | Yt ≥ 2) =

2 · τ · (5n2 − (8i + 8)n + 4(1 + i)2 )
+ 2 − o(1),
n2 (3n − 2i − 2)

and in expectation, the next Decision Stage begins after
τ+

2n2
3n − 2i − (4 −

2(i+1)
n )

fitness evaluations.
Proof: We look at the expected number of fitness evaluations for the Decision and Exploitation Stage,
given the starting position LO(x) = i.
During the Decision Stage, the hyper-heuristic will run both operators until one of them is successful
(i.e., makes an improvement in the fitness). The expected number of fitness evaluations for this to happen
is given by:



−1
1
2n − 2i − 2
E(TDSi ) = 2 · 1 − 1 −
1−
n
n2
2n2
2n3
=
.
=
3n2 − 2in + 2i − 4n + 2
3n − 2i − (4 − 2(i+1) )
n

The probability of the Decision Stage choosing each operator, given by the ‘First Hit Probability’ is
1/n
(2n−2i−2)/n2
n
2n−2i−2
1/n+(2n−2i−2)/n2 = 3n−2i−2 for the 1BitFlip operator and 1/n+(2n−2i−2)/n2 = 3n−2i−2 for the 2BitFlip
operator. It is possible for both operators to succeed in one iteration; for our analysis, we note that this
= O(1) times throughout the optimisation process, and opt to ignore
happens an expected O(n2 )· n1 · 2n−2i−2
n2
any progress made by such Decision and Exploitation Stages, accounting for this by adding a lower-order
O(τ + n) term to the expected runtime.
In the Exploitation Stage, the operator which succeeded during the Decision Stage runs for τ steps.
Throughout the two stages, the function value will increase. We can upper-bound the total increase by
keeping i constant throughout (i.e., using the value from the Decision Stage), and lower-bound it by applying
a high-probability bound on the number of observed LeadingOnes improvements. The highest success
2
2
probability occurs when using the 2BitFlip operator at i = 0; i.e 2n−2
n2 < n . Since τ = o(n ), we can use
Chernoff bounds to bound the number of successes in τ steps as o(n) with probability 1 − 2−Ω(n) (i.e., the
probability of Ω(n) successes in τ steps is at most 2−Ω(n) ). Hence, we can bound the progress from below
by considering i + o(n). The probability of each operator being chosen will remain the same, since this is
based on the original value of i at the Decision Stage.
Hence, the expected progress of the Exploitation Stage in τ iterations is at most


1
2n − 2i − 2 2n − 2i − 2
n
· +
·
2·τ ·
3n − 2i − 2 n 3n − 2i − 2
n2
2 · τ · (5n2 − (8i + 8)n + 4(1 + i)2 )
=
n2 (3n − 2i − 2)
and at least




1
2n − 2(i + o(n)) − 2
2n − 2i − 2
n
· +
·
2·τ ·
3n − 2i − 2
n
3n − 2i − 2
n2
2
2
2 · τ · (5n − (8i + 8)n + 4(1 + i) )
− o(1).
=
n2 (3n − 2i − 2)


using 2 to bound the expected fitness change of an accepted mutation.
15

Summing the expected progress and expected number of fitness evaluations performed in both stages
yields the Lemma statement.
We further note that for LO(x) = n − 1, the decision step takes an expected 2n iterations and will
conclude the optimisation process.

As the number of iterations spent in the decision step is not deterministic and not identically distributed
over the optimisation process, we cannot directly apply the Variable Drift Theorem [13] to bound the expected
runtime for the Generalised Greedy hyper-heuristic. However, we can upper bound the runtime through an
application of Wald’s Equation (Theorem 10). By splitting the analysis into w chunks, we can upper bound
the expected times for a Decision and Exploitation Stage within each chunk. We will then use the Variable
Drift Theorem to bound the expected number of Decision and Exploitation Stages required to optimise each
segment, and combine the two results to upper bound the total expected runtime.
The significance of the following Theorem will be highlighted in Corollary 19 and depicted in Figure 1.
Theorem 17 The expected runtime of the Generalised Greedy hyper-heuristic on LeadingOnes with τ =
o(n2 ) is at most



 Z kn
w
X
w
2w
1
τ

di + o(n2 )
n
+
2
2
(k−1)n 2τ ·(5n −(8i+8)n+4(1+i) )
3w − 2k n
+2
2
w
k=1

n (3n−2i−2)




2
for any w = o min n, nτ
.

Proof: Let LeadingOnes(x) = i denote the current state. We divide the analysis into w chunks of length
2
n/w (for w = o( nτ )). We can bound the expected time for a Decision and Exploitation Stage (using the
result from Lemma 16) in the kth chunk, where (k − 1)n/w ≤ i ≤ kn/w − 1, by


τ
2n2
2w

 +τ ≤
· n.
+
3w − 2k n
3n − 2i − 4 − 2(i+1)
n

We can make this claim since we know w = o(n).
Within each chunk, we will use the Variable Drift Theorem to bound the number of expected
Decision


2w
and Exploitation Stages, by looking at the drift that happens in a ‘D+E’ Stage, i.e., at most 3w−2k + nτ · n
steps. We note that there may be some minor overlap between chunks, although at most, this will result in
the addition of τ · w = o(n2 ) iterations throughout the search.
We have seen that,
E(Yt − Yt+1 | Yt ) =

2 · τ · (5n2 − (8i + 8)n + 4(1 + i)2 )
+ 2 − o(1) = h(n − i) = h(x).
n2 (3n − 2i − 2)

We consider Xt = 0 to be the end of the chunk. Let xmin = 1 represent the point kn
w − 1, and we note
xmin
n
=
O(
).
that h(x
)
τ
min
Hence, by the Variable Drift Theorem, the expected runtime of the kth chunk is


τ
2w
n·
+
E(Tk ) ≤
3w − 2k n




Z kn
w −1
xmin 
1


+ o(1) di +
2τ ·(5n2 −(8i+8)n+4(1+i)2 )
(k−1)n
h(x
min )
+
2
w
n2 (3n−2i−2)
 Z kn

w
τ
1
2w
n
di + O(max{τ, n}).
+
≤
2
2
(k−1)n 2τ ·(5n −(8i+8)n+4(1+i) )
3w − 2k n
+2
w
n2 (3n−2i−2)

16

The total expected runtime, by Wald’s equation will be at most equal to the sum of
expected
 the 
 runtimes
n2
of each chunk, plus some lower-order terms amounting to at most O(max{τ, n}) · o min n, τ
= o(n2 ).
Thus,
!
w
X
E(T ) ≤
E(Tk ) + o(n2 ).
k=1


The upper bound delivered by the theorem holds for any subquadratic value of τ . This will indicate that
the Generalised Greedy hyper-heuristic is not very sensitive to the parameter τ for LeadingOnes (as seen
in Corollary 19). As a result, the parameter should be easy to set in practice as confirmed by experiments
in Section 7.
We can now use this result to tightly upper bound the runtime of the simple Greedy mechanism (when
τ = 0, the two mechanisms act equivalently). We know this bound is tight by Corollary 9.
Corollary 18 For τ = 0, the expected runtime of the Generalised Greedy hyper-heuristic is at most
ln(3) 2
n + o(n2 ).
2
Proof: We constrain w ∈ ω(1) ∩ o(n). Inserting the relevant parameters into the equation will give:



 Z kn
w
X
w
2w
1
τ

di + o(n2 )
E(T ) ≤
n
+
2
2
(k−1)n 2τ ·(5n −(8i+8)n+4(1+i) )
3w − 2k n
+2
w
k=1
n2 (3n−2i−2)
!


kn
Z
w
X
w
1
2w
n
=
di + o(n2 )
(k−1)n 2
3w − 2k
w
k=1

w 
X
ln(3) 2
1
2
+ o(n2 ) =
n + o(n2 )
=n ·
3w − 2k
2
k=1

for w = ω(1).

We can also find parameter settings leading to the best runtime that can be achieved for the Generalised
Greedy hyper-heuristic.
Corollary 19 For τ ∈ ω(n) ∩ o(n2 ) the expected runtime of the Generalised Greedy hyper-heuristic is at
most


ln(5) arctan(2)
n2 + o(n2 ).
+
8
4
Proof: We constrain w = o(n). For τ ∈ ω(n) ∩ o(n2 ), we have:
τ 
2w
τ
τ
+ = +o
.
3w − 2k n
n
n
τ 
2τ · (5n2 − (8i + 8)n + 4(1 + i)2 )
2τ (5n2 − 8in + 4i2 )
.
+
2
=
+
o
n2 (3n − 2i − 2)
n2 (3n − 2i − 2)
n

17

Hence, we can simplify the expected runtime of the hyper-heuristic:



 Z kn
w
X
w
2w
1
τ

E(T ) ≤
di + o(n2 )
+
n
2
2
(k−1)n 2τ ·(5n −(8i+8)n+4(1+i) )
3w − 2k n
+
2
2
w
k=1
n (3n−2i−2)
!
Z kn
w
2
X
w
n (3n − 2i − 2)
=
τ
di + o(n2 )
(k−1)n 2τ (5n2 − 8in + 4i2 )
w
k=1
!


Z kn
w
2 X
w
n
3n − 2i − 2
n2 1
1
2
=
di
+
o(n
)
=
ln(5)
+
arctan(2)
+ o(n2 )
(k−1)n 5n2 − 8in + 4i2
2
2
4
2
w
k=1


ln(5) arctan(2)
=
n2 + o(n2 ).
+
8
4

We now analyse an ‘ideal’ algorithm which will provide a theoretical lower bound for the Generalised Greedy
hyper-heuristic. This hyper-heuristic is sped-up by getting the result of the Decision Stages for ‘free’ in every
iteration, and uses this result to decide which operator to apply.
Theorem 20 The ideal greedy algorithm which performs the Decision Stage ‘for free’ in every iteration has
runtime:


ln(5) arctan(2)
n2 + o(n2 ).
+
E(T ) =
8
4
Proof: The probability of the Decision Stage choosing each operator is
2

(2n−2i−2)/n
1/n+(2n−2i−2)/n2

1/n
1/n+(2n−2i−2)/n2

=

n
3n−2i−2

for

2n−2i−2
3n−2i−2

for the 2BitFlip operator. It is possible for both
=
the 1BitFlip operator and
operators to succeed in one iteration; for our analysis, we note that this happens an expected O(n2 ) · n1 ·
2n−2i−2
= O(1) times throughout the optimisation and we constrain this to an o(n2 ) term. Using Theorem
n2
6, we have:
−1
n−1 
n
1 X
1
2n − 2i − 2 2n − 2i − 2
E(T ) = ·
· +
·
2 i=0 3n − 2i − 2 n 3n − 2i − 2
n2


n−1
ln(5) arctan(2)
1 X (3n − 2i − 2)n2
n2 + o(n2 ).
=
+
= ·
2 i=0 (2n − 2i − 2)2 + n2
8
4

Hence, the upper bound provided in Corollary 19 is tight.

5

A New Hyper-heuristic: Generalised Greedy Gradient

We now consider a new mechanism, called Generalised Greedy Gradient (GGG), which combines the Decision
Stage idea of the Generalised Greedy hyper-heuristic i.e., where all operators are run in parallel and the first
to make a fitness improvement is chosen, and applies this operator choice to the gradient-based Exploitation
Stage of the Generalised Random Gradient hyper-heuristic i.e., the chosen operator is run for a period of τ
steps, and each fitness improvement resets the period of τ . The idea is to combine the learning aspects of
the two hyper-heuristics to create a hyper-heuristic that chooses the best operator and exploits this choice.
In this section we will prove that the Generalised Greedy Gradient hyper-heuristic can solve the GapPath
and GGPT efficiently in a similar way to GRG and GG. We also show that the GGG hyper-heuristic can
achieve the same optimal performance on LeadingOnes as GRG by using shorter learning periods τ .

5.1

GapPath and GGPT

We first introduce runtime results for the GGG hyper-heuristic on the GapPath and GGPT functions
considered in Section 3, which show that the hyper-heuristic can learn to use a given operator in a similar
18

way to the other generalised hyper-heuristics.
Theorem 21 Starting at 0n , the expected runtime of the Generalised Greedy Gradient hyper-heuristic on
GapPath is
n3
2n2
2τ n
+
+
− τ.
3
3
3
Proof: The GGG hyper-heuristic will act equivalently to GG on GapPath; that is, it will run the Greedy
operator Decision Stage and deterministically choose the unique operator which will give a success. Then
the mechanism will waste τ iterations, since it cannot enact any improvements in this Exploitation Stage
with the selected operator. Hence, the runtime is equivalent to the result from Theorem 1.

Theorem 22 Starting at 0n for τ = Ω(n3 ), the Generalised Greedy Gradient hyper-heuristic will find the
3
2τ n
2
+ (k+1)n
global optimum of GGPT (with constant k) in at most 2k+1
2(2k+1) + O(n ) steps with probability at least
1 − 2−Ω(n) . However, for τ = O(n2 ), the Generalised Random Gradient hyper-heuristic will fail to reach the
global optimum of GGPT in finite time with probability at least 1 − 2−Ω(n) .
Proof: Initially, a 1BitFlip improvement is necessary before the first 2BitFlip flip. For τ = Ω(n3 ),
similarly to Theorem 5, this will take time 2n + τ to account for the wasted iterations. The GRG hyper2
heuristic will then run the Greedy Decision Stage to choose the 2BitFlip operator in time 2 · n2 = n2 . The
Exploitation Stage will continue with this operator to find the remaining necessary 2BitFlip improvements
and avoid the ‘trap’ point with probability 1 − 2−Ω(n) , as per Theorem 4. The time for the remaining k − 1
2
improvements will be (k−1)n
+ τ to account for the wasted iterations at the end.
2
n
times to account for each run of 2BitFlip flips necessary to find
This process must be repeated 2k+1
the global optimum. Hence, the expected running time will be


k−1 2
n
2
2n + τ + n +
n +τ
2k + 1
2

which gives the result.
However, if τ = O(n2 ), a similar argument to Theorem 4 can be made. That is, for τ = cn2 , where

cn2 k−1
=
c is a constant, the probability of the required k − 1 successful periods is 1 − 1 − 2/n2

(1 − e−2c − o(1))k−1 = Θ(1), and so the probability of failing to do so is at least constant. If another
random Decision Stage is performed inside the region of two-bit improvements, a ‘trap’ is accessible via a
1-bit mutation from the point at which the decision occurs with probability at least 1/(k − 1) = Ω(1) (as
traps are placed uniformly at random inside these regions), and is found by the Random Gradient mech2
anism with probability at least 1/2 · (1 − 1/n)cn ≥ 1/4. Thus, the probability that the no ‘trap’ point is
constructed in a single region of k two-bit improvements is at most a constant smaller than one, which means
that over the n/(2k+1) such regions, the probability that a ‘trap’ point is constructed is at least 1−2−Ω(n) . 
We have seen that the Generalised Greedy Gradient hyper-heuristic performs similarly to the two previous
generalised hyper-heuristics on the GapPath series of functions. By learning to favour 2-bit flips it performs
efficiently.

5.2

LeadingOnes

We now prove that the Generalised Greedy Gradient mechanism can lead to improved performance on the
LeadingOnes benchmark function compared to the Generalised Random Gradient hyper-heuristic. The
result will be highlighted in Corollary 25 and a comparative performance with the other hyper-heuristics will
be depicted in Figure 1.
Theorem
23 The runtime of the Generalised Greedy Gradient hyper-heuristic on LeadingOnes, with τ ≤

1
2 − ǫ n ln(n), ǫ = Θ(1), is at most
X
w
3w − 2j + 2
n2
·
E(T ) ≤ o(n2 ) +
2
3w − 2j
j=1
19




τ
2τ

0.5
· (3w − 2j) + w · e n · M (1) + (2(w − j + 1)) · e n (1−(j−1)/w) · M ( 1−j/w
)




2τ
τ
w w · e n + 2(w − j) · e n (1−j/w)


n
where M (x) := min( nτ , x), for w = o exp(2τ
/n) .
2w +

τ
n

Proof: We partition the optimisation process into w chunks based on the value of the LeadingOnes
fitness function: during chunk j, the LO value of the current solution is at least (j − 1)n/w and less than
j · n/w.
We follow the proof for the Generalised Random Gradient on LeadingOnes, in which we upper bounded
the final runtime by the sum of the expected values of Tj , the runtime of each chunk of the process, plus the
times taken
P to begin a chunk. Since the analysis of E(Tj ) requires an operator choice, we bound the runtime
E(T ) ≤ w
j=1 (E(Tj ) + E(Sj+1 )), where Sj+1 is a random variable denoting the expected number of fitness
evaluations between the first solution in chunk j + 1 being constructed and the first operator
decision of

1
chunk j beginning.
We
note
again
(with
the
same
parameter
combinations
i.e.,
τ
≤
−
ǫ
n
ln(n),
ǫ = Θ(1),
2


n
2
w = o exp(2τ
/n) ), the contribution of the Sj+1 terms can be bounded by o(n ).
We let Nj denote the number of operator decisions within chunk j, and Xj,1 , . . . , Xj,NJ the number of
fitness function evaluations within the Decision Stage and the Exploitation Stage of the chosen operator.
PNj
Xj,k , and by Wald’s equation, using E(Xj ) to denote an upper bound on all E(Xj,k ) in
Then Tj = k=1
chunk j,
E(Tj ) ≤ E(Nj )E(Xj ).

We can upper-bound E(Nj ), the number of Decision Stages in chunk j, by lower-bounding the expected
number of improvements found from the Decision and Exploitation Stage of the chosen operator, and using
the Additive Drift Theorem to find the expected number of operator selections required to enter the next
chunk.
Recall from the proof of Theorem 13 that, denoting F1 and F2 as the events that the 1BitFlip and
2BitFlip operators fail to find an improvement during τ iterations:
τ

e− n −

τ
1
≤ P (F1 ) ≤ e− n ;
n

2τ

e− n (1−(j−1)/w) −

2τ
1
≤ P (F2 ) ≤ e− n (1−j/w) .
n

After each Decision Stage, an operator will be chosen. We use the First Hit Probability to look at the
probability of each operator being chosen:
P (C1 ) =
Note that in chunk j, with

1
n

+

(j−1)n
w

1
n
2(n−i−1)
n2

=

−1≤i≤

n
;
3n − 2i − 2

jn
w

P (C2 ) =

2n − 2i − 2
.
3n − 2i − 2

− 1, we can bound the two probabilities:

w
w
≤ P (C1 ) ≤
;
3w − 2j + 2
3w − 2j

2w − 2j
2w − 2j + 2
≤ P (C2 ) ≤
.
3w − 2j
3w − 2j + 2

We look at finding a lower bound for E(Dj ), the expected number of improvements Dj produced following
an operator Decision and Exploitation Stage. Since we are looking for a lower bound, we use the lower bound
for the probability of choosing each operator, and an upper bound for the number of improvements given
the chosen operator. Note there is 1 improvement from the Decision Stage.




1
1
− 1 + P (C2 ) ·
−1
E(Dj ) ≥ 1 + P (C1 ) ·
P (F1 )
P (F2 )




w
2w − 2j
1
1
≥1+
−
1
+
−
1
·
3w − 2j + 2
exp(− nτ )
3w − 2j exp(− 2τ
n (1 − j/w))
τ
w
2(w − j) 2τ (1−j/w)
· en +
·en
≥
3w − 2j + 2
3w − 2j
τ
2τ
2(w − j)
w
· en +
· e n (1−j/w) .
≥
3w − 2j + 2
3w − 2j + 2
20

In each chunk, in expectation, we require n/(2w) fitness improvements to exit the chunk. If each random
operator decision leads to more E(Dj ) improvements, by the Additive Drift Theorem, the expected number
of steps required to complete chunk j, E(Nj ) satisfies:
E(Nj ) ≤
≤

n/(2w)
n
≤
·
E(Dj )
2w

1
w
3w−2j+2

n(3w − 2j + 2)
·
2w



τ
n

·e +

2(w−j)
3w−2j+2

2τ

· e n (1−j/w)

.
2τ
(1−j/w)

1
τ
n

w · e + 2(w − j) · e n

We now look at bounding E(Xj ), an upper bound on the number of fitness function evaluations for a
Decision and Exploitation Stage within chunk j.
The worst case expected time for the duration of the Decision Stage in chunk j is

−1


2(w − j)
2n2 w
1
1−
=
E(TDSj ) ≤ 2 · 1 − 1 −
n
nw
(3w − 2j)n − 2(w − j)
2nw
=
+ o(n).
3w − 2j
The small order term will be omitted for brevity, but note that it makes no difference to the leading constant
on the asymptotically significant term.
We can also upper-bound E(Xj |C{1,2} ), the expected iterations before a selected operator fails to produce
an improvement within τ iterations. Using, for each operator,
E(Xj |C1 ) ≤ τ + (1/P (F1 ) − 1) · min(τ, n)
E(Xj |C2 ) ≤ τ + (1/P (F2 ) − 1) · min(τ, 0.5n/(1 − j/w)).
Hence:
E(Xj ) ≤ E(TDSj ) + P (C1 ) · E(Xj |C1 ) + P (C2 ) · E(Xj |C2 )
2w − 2j + 2 min(τ, n/(2 − 2j/w))
w
min(τ, n)
2nw
+
+τ +
·
·
τ
3w − 2j
3w − 2j e− n − 1/n 3w − 2j + 2 e− 2τ
n (1−(j−1)/w) − 1/n
2w − 2j + 2 min(τ, n/(2 − 2j/w))
w
min(τ, n)
2nw
.
+
+τ +
· −τ
· − 2τ (1−(j−1)/w)
≤
n
3w − 2j
3w − 2j e
3w − 2j
− 1/n
− 1/n
e n

≤

which can be simplified to
E(Xj ) ≤ o(n) +

n
·
3w − 2j




τ 
τ
τ
τ
2τ
0.5
(1− j−1
)
n
n
w
2w + (3w − 2j) + we min
min
.
, 1 + (2w − 2j + 2)e
,
n
n
n 1 − j/w
Finally, we bound the overall expected runtime of the hyper-heuristic. We have:


w
w
X
X
(E(Tj ) + E(Sj+1 )) ≤ 
E(Nj )E(Xj ) + o(n2 )
E(T ) ≤
j=1

and hence

j=1

X
w
3w − 2j + 2
n2
·
E(T ) ≤ o(n ) +
2
3w − 2j
j=1
2



2τ

τ

2w + nτ (3w − 2j) + we n min( nτ , 1) + (2(w − j + 1))e n (1−



τ
2τ
w w · e n + 2(w − j) · e n (1−j/w)

j−1
w )

0.5
)
min( nτ , 1−j/w




 .


When we set τ = 0, the hyper-heuristic reduces to the simple Greedy mechanism, and the following
corollary provides a tight runtime upper bound. We know it is tight from Corollary 9.
21

Corollary 24 When τ = 0 (i.e., ǫ =
heuristic is at most

1
2 ),

the expected runtime of the Generalised Greedy Gradient hyperln(3) 2
n + o(n2 ).
2

Proof: We constrain w = ω(1) ∩ o(n2 ). When τ = 0, we have


w
w
n2 X 2(3w − 2j + 2)
2w
n2 X 3w − 2j + 2
=
·
·
·
E(T ) ≤
2 j=1 3w − 2j
w (w + 2(w − j))
2 j=1 (3w − 2j)2
=

ln(3) 2
n + o(n2 ).
2


The following corollary shows that we can find parameter values such that the GGG hyper-heuristic can
match the optimal performance of the GRG hyper-heuristic (Corollary 15) with the best possible runtime
from Theorem 7.
Corollary 25 For τ that satisfies both τ = ω(n) and τ ≤ ( 21 − ǫ)n ln(n), for ǫ = Θ(1), the expected runtime
of the Generalised Greedy Gradient hyper-heuristic is at most
1 + ln(2) 2
n + o(n2 ).
4




n
exp(2τ /n) .
0.5
Consider first the terms M (1) and M ( 1−j/w
). Since we have τ = ω(n), we have nτ = ω(1); it is
0.5
), it is important to note that for the first half of the search,
easy to see that M (1) = 1. For M ( 1−j/w
0.5
0.5
0.5
M ( 1−j/w ) = 1−j/w , and in the second half of the search, M ( 1−j/w
) = O( nτ ) = O(ln n) for any constant
0.5
τ
c > 0 (there is a special case when j = w in which M ( 1−j/w ) = n = O(ln n)). Note also that nτ = ω(1),
e2τ /n·1/w = o(n1/w ) = 1 + o(1), 3w−2j+2
3w−2j = 1 + o(1).

Proof: We constrain w ∈ ω(ln n) ∩ o

Hence, the runtime will become:
E(T ) ≤ o(n2 ) +



2w +

τ
n

w 
n2 X
(1 + o(1))·
·
2 j=1


2τ
τ

0.5
· (3w − 2j) + w · e n + (2(w − j + 1)) · e2τ /n·1/w e n (1−j/w) · M ( 1−j/w
)



τ
2τ
w w · e n + 2(w − j) · e n (1−j/w)

n2
·
= o(n2 ) +
 2
w 
X
2w +



τ
2τ
0.5
· (3w − 2j) + w · e n + (2(w − j + 1)) · e n (1−j/w) · M ( 1−j/w
) 



2τ
τ
n + 2(w − j) · e n (1−j/w)
w
w
·
e
j=1
w 
n2 X 1
= o(n2 ) +
·
·
2 j=1 w
!
2τ
τ
0.5
)
w · e n + 2(w − j + 1) · e n (1−j/w) · M ( 1−j/w
2w + nτ · (3w − 2j)
+
τ
τ
2τ
2τ
w · e n + 2(w − j) · e n (1−j/w)
w · e n + 2(w − j) · e n (1−j/w)
!
2τ
τ
0.5
w 
w · e n + 2(w − j + 1) · e n (1−j/w) · M ( 1−j/w
) 
n2 X 1
2
·
·
.
= o(n ) +
2τ
τ
2 j=1 w
w · e n + 2(w − j) · e n (1−j/w)
τ
n

22

Runtime (/n2 )

0.60
GG
GRG
GGG
RLS

0.50

2Opt

0.40
0

5

10

15

20

25

30

35

40

45

50

τ (/n)
Figure 1: The leading constants in the theoretical upper bounds on the average number of fitness function
evaluations required by the Generalised Greedy, Generalised Random Gradient, and Generalised Greedy
Gradient hyper-heuristics to find the LeadingOnes optimum (w = 100, 000).
Note that the exponential terms will dominate the summation term (since nτ = ω(1)). When j > w2 , we note
that w · exp(τ /n) = ω(2(w − j + 1) · exp( 2τ
n (1 − j/w))) and this term will dominate the other. Vice versa for
j < w2 . We consider j = w/2 as a special case.
!
τ
2τ
0.5
w 
2 X
w · e n + 2(w − j + 1) · e n (1−j/w) · M ( 1−j/w
) 
1
n
·
·
E(T ) ≤ o(n2 ) +
τ
2τ
2 j=1 w
w · e n + 2(w − j) · e n (1−j/w)


2τ
w/2−1
0.5
n (1−j/w) ·
2
X
e
1 2(w − j + 1)
n 
1−j/w

·
·
·
= o(n2 ) +
2τ
2
w
2(w
−
j)
n (1−j/w)
e
j=1


2τ
τ
w
2
2
X
n
n
n 
(2w + 2)e
1 e 
n
+
·
·
· τ
+
2τ
2w
2
w en
2w · e n
j=w/2+1




w/2−1
w
2
2
2
X 1
X
n
0.5  n
n 
1
= o(n2 ) +
+
·
·
+
·
2
w
1
−
j/w
2w
2
w
j=1
j=w/2+1

=

since

2(w−( w
2 )+1)
2(w−( w
2 ))

=

w/2 
X

n2
·
4 j=1

2w+2
2w

1
w−j



+

n2
+ o(n2 ) =
4

= 1 + o(1).



1 + ln(2)
4



n2 + o(n2 ).



Figure 1 shows the relevant theoretical upper bounds for the Generalised Greedy, Generalised Random
Gradient and Generalised Greedy gradient hyper-heuristics from Theorem 13, Theorem 17, and Theorem
23. The results for the Generalised Greedy Gradient are better than the results for the Generalised Random
Gradient at each value of τ , although they are essentially indistinguishable within the context of Figure 1.
The two hyper-heuristics seem to quickly tend towards the optimal results of Corollary 15 and Corollary 25,
and this would be seen by considering τ values that satisfy both τ = ω(n) and τ ≤ ( 12 −ǫ)n ln(n), for ǫ = Θ(1).

23

6

Increasing the Choice of Low-level Heuristics

Runtime analyses of hyper-heuristics are easier if the algorithms can only choose between two operators.
However, in realistic contexts, hyper-heuristics have to choose between many more operators.
In this section, we consider the previously analysed generalised hyper-heuristics, yet extend the set H of
low-level heuristics to be of size k = o(n) i.e., |H| = k. We extend upon the previous analysis by considering
the k operators as k different mutation operators, each flipping between 1 and k indistinct bits uniformly
at random respectively. This would more accurately represent hyper-heuristic approaches employed for
real-world problems, as opposed to setting k = 2 for the purposes of the analysis.
As before, we consider the LeadingOnes benchmark function. We will rigorously show that the performance of the ‘simple’ mechanisms deteriorates as the number of operators (k) increases. On the other hand,
we prove decreasing upper bounds on the runtime of the Generalised Random Gradient hyper-heuristic as the
number of operators increases. Since the Decision Stage of the Generalised Greedy hyper-heuristic (and the
Generalised Greedy Gradient) hyper-heuristic makes the analysis very complex, we present an experimental
analysis of these hyper-heuristics in Section 7.
We first derive the best possible runtime achievable by any hyper-heuristic using k = o(n) operators.
Before we prove this result we introduce the following two helpful lemmata.
Lemma 26 The probability of improvement from an operator which flips m indistinct bits in a bit-string on
the LeadingOnes benchmark function, at the state LO(x) = i, is
m−1

n−i−1
1
+ O(n−2 ).
P (impm ) = m · ·
n
n
Proof: In the context of the LeadingOnes benchmark function, the way to make an improvement is to
flip the first 0-bit after the leading 1-bits, whilst keeping the prefix leading 1-bits unflipped. Although it is
possible to make improvements by flipping and re-flipping the same bit in some combination (with probability
Θ( n12 )), the operators are likely to make a fitness improvement by flipping the first 0-bit (with probability
1/n, which can occur within any of the m bit-flips), and using the remaining m − 1 flips within the suffix
)m−1 ). Hence we can say that the probability of an improvement when
n − i − 1 bits (with probability ( n−i−1
n
flipping k bits is

m−1
1
n−i−1
P (impm ) = m · ·
+ O(n−2 ).
n
n


We can leave the formula in this state since all analyses will consider the use of the 1BitFlip operator.
Since this always has an improvement probability of 1/n on LeadingOnes, any lower-order terms in other
operators will not affect the leading constants if it is chosen sufficiently often. We also note that through a
simple calculation, the 1BitFlip operator is always the best choice in the second half of the search space
n
2 ≤ i < n.
Lemma 27 Consider two indistinct bitflip operators flipping a and b bits respectively, with b > a. Then
operator a outperforms b (excluding i = n − 1) when
 1/(b−a) !
b
− 1.
i<n 1−
a
This follows simply from Lemma 26. In particular, an operator flipping m bits outperforms an operator
n
flipping m − 1 bits when i < m
− 1.
Theorem 28 The best-possible runtime on LeadingOnes for a mechanism using k = o(n) operators,
(1, . . . , k) bitflips, is


n/k−1
k−1
X
X n/x−1
1
1
1 X
 ± o(n2 ).
+
E(Tk,opt ) =


1
n−i−1 x−1
1
n−i−1 k−1
2
x
·
·
k
·
·
x=1 i=n/(x+1)
i=0
n
n
n
n
24

n
Proof: From Lemma 27, we can say the mBitFlip operator is optimal during the time when m+1
≤i≤
n
n
−
1
(unless
m
=
k,
in
which
case
it
is
optimal
for
0
≤
i
≤
−
1).
Since
the
1BitFlip
operator
has
m
k
success probability O(n−1 ), and is chosen with the same probability as all other operators, the leading term
in any success probability is O((nk)−1 ) = ω(n−2 ) and any O(n−2 ) terms are insignificant. Thus, they can
be grouped into a lower order o(n2 ) term.
Hence, by standard waiting time arguments, coupled with Theorem 6, we can show that the optimal
runtime when using k operators is


n/x−1
n/k−1
k−1
X
X
X
1
1
1
 ± o(n2 ).
+
E(Tk,opt ) = 


n−i−1 x−1
1
n−i−1 k−1
1
2
x· ·
·
x=1
i=0 k ·
n

i=n/(x+1)

n

n

n


1+ln(2) 2
1 2
2
n
,
E(T
)
=
n
≈
0.42329n
,
In particular,
taking
limits
as
n
→
∞,
we
have
E(T
)
=
2,opt
1,opt
2
4




ln(2)
ln(3)
ln(2)
ln(3)
3721
1
2
2
2
2
n ≈ 0.40525n , E(T5,opt ) = 11520 + 2 − 4
n ≈ 0.39492n .
E(T3,opt ) = 3 + 2 − 4
This result gives a theoretical lower bound on the expected runtime of any algorithm using the k operators
on LeadingOnes. We can see that including further operators can improve the runtime.

6.1

‘Simple’ Mechanisms

We will now see how the simple learning mechanisms (Simple Random, Permutation, Greedy and Random Gradient) perform when tasked with choosing between k operators (i.e., (1, . . . , k) bitflips). We will
show that incorporating more operators is detrimental to the performance of the ‘simple’ mechanisms on
LeadingOnes.
We again start by stating the expected runtime of the Simple Random mechanism, and use this as a
basis for the other three mechanisms.
Recall that the standard Simple Random mechanism chooses each operator uniformly at random in each
iteration (i.e., with probability 1/k when using k operators).
Theorem 29 The runtime of the Simple Random mechanism on LeadingOnes with k = o(n) operators,
(1, . . . , k) bitflips, is
n−1
1X
1
E(TSR|k ) =
− o(n2 ).

1
n−i−1 m−1
2 i=0 1 · Pk
m=1 m · n ·
k
n

Proof: We have seen previously that the probability of an improvement when flipping m indistinct bits is
m−1

n−i−1
1
+ O(n−2 ).
P (impm ) = m · ·
n
n

We can use this claim again since, with a sub-linear number of operators, so long as the 1BitFlip operator
is used, any u.a.r. choice of operators will give an improvement probability in each iteration of ω(n−2 ).
The probability of an improvement in a single iteration is
!
m−1

k
1 X
1
n−i−1
−1
−2
(An−i ) = ·
m· ·
+ O(n )
k m=1
n
n
!
m−1
 

k
1
1
1 X
1
n−i−1
−2
x· ·
+ O(n ) = Ω
=
+ ·
kn k m=2
n
n
n
and hence

An−i =

1
1
k

·

We can use Theorem 6 to give the result:

Pk

m=1 m ·

n−1
n−1
1X
1X
E(T ) =
An−i =
2 i=0
2 i=0

1
n

·


n−i−1 m−1
n

− o(n).

1
1
k

·

Pk

m=1

25

m·

1
n

·


n−i−1 m−1
n

− o(n2 ).


Corollary 30 The expected runtime of the Permutation, Greedy and Random Gradient mechanisms on
LeadingOnes with k = o(n) operators, (1, . . . , k) bitflips, is
E(Tk ) =

n−1
1X
2 i=0

1
1
k

·

Pk

m=1

m·

1
n

·

Proof: For the Greedy and Permutation mechanisms, let


n−i−1 m−1
n


pi = P (imp1 ) + (1 − P (imp1 )) · P (imp2 ) + · · · + 
=

k
X

m=1

=

k
X

m=1



m−1
Y

1
·
n



n−i−1
n

j−1 !

1
(1 − o(1)) · m · ·
n



n−i−1
n

m−1



j=1

1−j·



k−1
Y
j=1

± o(n2 ).



(1 − P (impj )) · pk

·m· 1 ·
n
!



n−i−1
n

m−1




be the probability that at least one improvement is constructed in respectively 1, . . . , k iterations. To move
from the second equation to the third, we note that Pimpj = O( n1 ) and
Qm−1
1 o(n)
= 1 − o(1). To upper bound the optimisation time, we note that
j=1 (1 − Pimpj ) = (1 − O( n ))
the difference between k/pi (i.e., the waiting time for an improvement to be constructed in terms of fitness
evaluations) and the An−i waiting times used to prove Theorem 29 is at most constant, and thus the difference
between these mechanisms and Simple Random expected times is limited to lower-order terms. We note that
with probability at most k(k − 1)/n2 , at least two mutations (of the k) considered are improvements; in such
a case, we can consider all but one of the improvement steps to be made in 0 iterations. As this occurs at
most a sublinear number of times in expectation, and the maximum waiting time for any improving step is
O(n), the lower-bound differs from the upper bound by at most an o(n2 ) term. Thus, the expected runtime
Pn−1
1
± o(n2 ).
of these mechanisms is also 21 i=0 1 Pk
n−i−1 m−1
1
)
m=1 m· n ·(
k·
n
For the Random Gradient mechanism, we note that the probability that an operator, when repeated
following a success, is successful again is at most k/n. Since there are at most n improvements to be made
throughout the search space, the expected number of repeats which produce an improvement is at most
k = o(n). When not repeating a successful operator, the Random Gradient mechanism behaves identically
to the Simple Random mechanism. Its expected runtime is therefore at least the runtime of the Simple
Random mechanism less an o(n2 ) term, and at most the runtime of the Simple Random mechanism plus n
(as there are at most n iterations where the mechanisms differ in operator selection). Thus, its expected
Pn−1
1
runtime is also 12 i=0 1 Pk
± o(n2 ).

n−i−1 m−1
1
)
m=1 m· n ·(
k·
n
Note that the expected runtimes from Theorem 29 and Corollary 30 increase as k increases, suggesting that
incorporating more operators is detrimental to the performance of the ‘simple’ mechanisms.
In particular,
 √
 √  the
2
3 2
2
2
results for using 1, 2 and 3 operators respectively are 12 n2 , ln(3)
n2 ≈
n
≈
0.54931n
and
arctan
2
4
2
0.65281n2.

6.2

Generalised Random Gradient

We present a rigorous theoretical analysis of the runtime of the Generalised Random Gradient hyper-heuristic
on LeadingOnes using k ≥ 2 operators. The derived upperbound on the expected runtime decreases with
k.

26

Theorem 31 The expected runtime of the Generalised Random Gradient hyper-heuristic on LeadingOnes
for τ ≤ k1 − ǫ n ln(n), ǫ = Θ(1) with k = o(n) operators, (1, . . . , k) bitflips, is at most:
i 
hP


τ
k
1
τ
mn
(1−(j−1)/w)m−1
w
· M m(1−j/w)
m−1
m=1 e
n2 X  k · n +
 ± o(n2 ).
i

hP
·
τ
m−1
k
2 j=1
(1−j/w)
m
n
−k
w
m=1 e


n
where M (x) := min( nτ , x), for any w ∈ Ω(1) ∩ o exp(kτ
/n) .
Proof: We follow the proof idea for the Generalised Random Gradient hyper-heuristic for two operators
(Theorem 13). That is, we partition the optimisation process into w chunk based on the value of the
LeadingOnes fitness function: during chunk j, the LO value of the current solution is at least (j − 1)n/w
and less than j · n/w. After all w chunks have been completed, the global optimum, with an LO value of n,
will have been found.
We upper-bound the expectation of the runtime T of the Generalised Random Gradient hyper-heuristic
on LO by the sum of the expected values of Tj , the runtimes on each chunk of the optimisation process,
plus the times taken to begin a chunk. As our analysis
of E(Tj ) requires the chunk to start with a random
P
choice of mutation operator, we bound E(T ) ≤ w
(E(T
j ) + E(Sj+1 )) where Sj+1 is a random variable
j=1
denoting the expected number of iterations between the first solution in chunk j +1 being constructed and the
following random operator choice. We will later show that with proper parameter choices, the contribution
of Sj+1 terms can be bounded by o(n2 ), and therefore does not affect the leading constant in the overall
bound.
Let us now consider Tj , the number of iterations the hyper-heuristic spends in chunk j. Recall that
a mutation operator is selected uniformly at random, and is allowed to run until it fails to produce an
improvement for τ sequential iterations. Let Nj be a random variable denoting the number of random
operator choices the hyper-heuristic performs during chunk j, and Xj,1 , . . . , Xj,Nj be the number of iterations
PNj
Xj,k , and by applying Wald’s
the hyper-heuristic runs each chosen operator for, in which case Tj = k=1
equation (Theorem 10), using E(Xj ) to denote an upper bound on all E(Xj,k ) in chunk j:
PNj
E(Xj,k ) ≤ E(Nj )E(Xj ).
(9)
E(Tj ) = k=1
To bound E(Nj ), the expected number of times the random operator selection is performed during chunk
j, we lower-bound the expected number of improvements found following operator selection, and apply the
Additive Drift Theorem [12] to find the expected number of random operator selections occurring before a
sufficient number of improvements have been found to enter the next chunk.
Recall from Lemma 26 that the improvement probability for a mBitFlip operator is

m−1
n−i−1
1
+ O(n−2 ).
P (impm ) = m · ·
n
n

We note again that since the 1BitFlip operator is used, we can omit the O(n−2 ) terms, and they will fall
into a o(n2 ) term in the final result.
Let Fm denote the event that the mBitFlip operator fails to find an improvement during τ iterations.
τ
This will occur with probability P (Fm ) = (1 − P (impm )) . Within chunk j, the ancestor individual has at
most jn/w − 1, and at least (j − 1)n/w , one bits. Hence:

m−1 !τ

m−1 !τ
j
1
1 n − (jn/w − 1) − 1
1−
≤ 1−m·
P (Fm ) ≤ 1 − m ·
n
n
n
w
≤ e−

P (Fm ) ≥

mτ
n

(1−j/w)m−1

1
1−m·
n

≥ e−

mτ
n



;

n − ((j − 1)n/w) − 1
n

(1−(j−1)/w)m−1

−

m−1 !τ

1
.
n
27

≥

1
1−m·
n


m−1 !τ
j−1
1−
w

We note that a geometric distribution with parameter p = P (Fm ) can be used to model the number of
improvements that the mBitFlip operator finds prior to failing to find an improvement for τ iterations; the
expectation of this distribution is (1 − p)/p = 1/p − 1. Combined over all k operators, the expected number
of improvements Dj produced following a single random operator selection during chunk j, E(Dj ), is greater
than:
!


k
k
X
1
1
1 X mτ (1−j/w)m−1
−1
E(Dj ) ≥
e n
−1 ≥
k
P
(F
)
k
m
m=1
m=1
by inserting the upper bounds for P (Fm ). We use this expectation as the drift in the Additive Drift Theorem
to upper-bound E(Nj ). Recall that each chunk consists of advancing through at most n/w fitness values;
as bits beyond the leading ones prefix and the first zero bit remain uniformly distributed, in expectation
n/(2w) improvements by mutation are required. If each step of a random process in expectation contributes
E(Dj ) improvements by mutation, the expected number of steps required to complete chunk j is at most:
E(Nj ) ≤
by the Additive Drift Theorem.

n/(2w)
k n
≤ · · P
k
E(Dj )
2 w

m=1 e

1
mτ
n

(1−j/w)m−1



(10)
−k

To bound E(Xj ), the expected number of iterations before a selected mutation operator fails to produce
an improvement for τ iterations, we apply Wald’s equation: let S be the number of improvements found
by the operator before it fails, and W1 , . . . , WS be the number of iterations it took to find each of those
improvements. Then, once selected, the mBitFlip operator runs for:
E(Xj |m) = τ +

S
X

E(Ws ) = E(S)E(Wm | S ≥ 1)

s=1

where τ accounts for the iterations immediately before failure, and the sum for the iterations preceding each
constructed improvement. Recall that E(S) = 1/P (Fm ) − 1 by the properties of the geometric distribution,
and observe that E(Wm | S ≥ 1) = E(Wm | Wm ≤ τ ) ≤ min(τ, E(Wm )). Using a waiting time argument for
E(Wm ) being equal to the reciprocal of the improvement probability for the mBitFlip operator, we get:




1
1


− 1 · min τ,
E(Xj | m) ≤ τ +

m−1 
P (Fm )
m · n1 · n−(jn/w−1)−1
n
!


1
n
=τ+
− 1 · min τ,
mτ
m−1
m(1 − j/w)m−1
e− n (1−(j−1)/w)
− n1


j−1 m−1
mτ
n
+ O(1).
≤ τ + e n (1− w )
· min τ,
m(1 − j/w)m−1
Combining these conditional expectations yields


k
k 
X
X
1
n
1 mτ (1− j−1 )m−1
n
w
E(Xj ) ≤
· min τ,
+ O(k)
· E(Xj | m) ≤ τ +
·e
k
k
m(1 − j/w)m−1
m=1
m=1

!
k 
X
τ
1 mτ (1− j−1 )m−1
τ
1
w
≤n
· min
+ O(k)
+
·e n
,
n m=1 k
n m(1 − j/w)m−1
!

k 
X
j−1 m−1
mτ
1
n kτ
τ
(1−
)
w
e n
+ O(k).
+
,
≤
· min
k
n
n m(1 − j/w)m−1
m=1

28

(11)

Runtime (/n2 )

0.60
2-op
3-op
4-op
5-op

0.50

0.40
0

5

10

15

20

25

30

35

40

45

50

τ (/n)
Figure 2: The leading constants in the theoretical upper bounds on the average number of fitness function
evaluations required by the k-operator Generalised Random Gradient hyper-heuristic to find the LeadingOnes optimum (w = 100, 000).
Finally, we return to bounding the overall runtime of the hyper-heuristic. Recall that Sj denoted the
number of iterations the algorithm spends in chunk j while using the random operator chosen during chunk
j − 1, and as E(Sj ) ≤ max (E(Xj | mBitFlip))m=1,...,k < kE(Xj ) = O (n exp(kτ /n)), and since w =
 P

w
n
2
o exp(kτ
j=1 E(Sj+1 ) = o(n ). Substituting the bounds (10) and (11) into (9) yields the theorem
/n) ,
statement:


w
w
X
X
(E(Tj ) + E(Sj+1 )) ≤ 
E(Nj )E(Xj ) + o(n2 )
E(T ) ≤
j=1

j=1

w
X
1
n
×
·
≤ o(n2 ) +
2
w
j=1
2

kτ
n

+

i
h mτ

j−1 m−1
1
τ
n (1− w )
e
,
·
min
m=1
n m(1−j/w)m−1

P
.
j m−1
mτ
k
n (1− w )
−k
m=1 e

Pk


Figure 2 shows the relevant theoretical upper bounds for the k-operator variant of the Generalised
Random Gradient hyper-heuristic from Theorem 31. The upper bounds found by the hyper-heuristics with
more operators are better than the ones with less operators. In particular, the upper bounds for the any
hyper-heuristic with k-operators outperform the best possible runtime for any hyper-heuristic with less than
k operators. We depict this result for k = 3 and k = 5 in Figure 3.

7

Experimental Results

In the previous sections we have proven that the generalised hyper-heuristics are extremely fast for the
LeadingOnes benchmark function for large enough problem sizes n. In this section we present some
experimental results for the generalised hyper-heuristics in order to shed light on their performance for
realistic problem sizes. All parameter combinations have been simulated 10,000 times.

7.1

Two Low-level Heuristics (k = 2)

We first consider the generalised hyper-heuristics using two operators only (i.e., 1BitFlip and 2BitFlip),
and look at the impact of the parameter τ and problem size n.
Figure 4 shows the runtimes for the three generalised hyper-heuristics on LeadingOnes for n = 10, 000
and n = 50, 000, illustrating the effect τ has on the runtime.
29

0.44
2-op
3-op

0.43

Runtime (/n2 )

Runtime (/n2 )

0.44

2Opt

0.42
0.41
0.40

0

10

20

30

40

50

4-op
5-op
0.42
0.40
0.38

4Opt
0

10

20

τ (/n)

30

40

50

τ (/n)

Figure 3: A comparison of the optimal runtimes of the Generalised Random Gradient hyper-heuristic with
k-operators against the leading constant in the theoretical upper bound of the runtime of the Generalised
Random Gradient hyper-heuristic with k + 1-operators; for k = 2 and k = 4.

Runtime (/n2 )

0.6
0.55
RLS

0.5

Gen. Greedy
Gen. Random Gradient
Gen. Greedy Gradient

0.45
0.4

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

τ (/(n ln(n)))
Figure 4: Average number of fitness function evaluations required by the hyper-heuristics with k = 2
operators to find the LeadingOnes optimum for n = 10, 000 (solid), n = 50, 000 (dashed).
For the Generalised Greedy hyper-heuristic, we see that for the larger problem size, the runtimes improve
slightly. The figure suggests that for a sufficiently large τ the hyper-heuristic outperforms RLS; in particular,
for every value of τ greater than approximately 0.3n ln n (for n = 50, 000 this value is 162, 297). Also, for
every τ ≥ n ln n the runtime of the GG hyper-heuristic does not change much confirming the robustness of
the hyper-heuristic to the choice of τ , indicated by Corollary 19.
The Generalised Random Gradient hyper-heuristic performance seems more dependent on the choice
of τ . It is worth noting that as the problem size increases, for τ ≈ 0.55n ln(n), the runtime seems to be
n2 + o(n2 ) ≈ 0.42329n2). For well
approaching the optimal performance proven in Corollary 15 (i.e., 1+ln(2)
4
chosen τ values, the hyper-heuristic beats the runtime of RLS, and also the experimental runtime for the
recently presented k-bit mutation algorithm with self-adjusting k, of 0.450n2, for the given parameter choices
[8]2 . As τ increases past 0.6n2 , we see a detriment in the performance of the hyper-heuristic; it is worth
noting, however, that for n = 50, 000, it is required that τ > 1.5n ln(n) = 811, 483 to be worse than the RLS
expected runtime of 0.5n2 , indicating that the parameter is very robust.
The Generalised Greedy Gradient hyper-heuristic showcases similar performance reliance on τ as the
Generalised Random Gradient hyper-heuristic. The GGG hyper-heuristic, however, does have improved
performance over the GRG hyper-heuristic for both values of n, suggesting that incorporating the Decision
2 We did not perform an experimental comparison with this algorithm as it is unclear how to set the various parameters for
a fair comparison.

30

τ = 0.25n ln n
τ = 0.5n ln n
τ = 0.6n ln n
τ = 0.75n ln n

Runtime (/n2 )

0.55

0.5

0.45

0.4 2
10

103

104

105
n

106

107

108

Figure 5: Average number of fitness function evaluations required for the Generalised Random Gradient
hyper-heuristic with k = 2 operators to find the LeadingOnes optimum as the problem size n increases.

Runtime (/n2 )

0.60
0.55
RLS

0.50

2-op
3-op
4-op
5-op

0.45
0.40

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

τ (/(n ln(n)))
Figure 6: Average number of fitness function evaluations required by the Generalised Random Gradient
hyper-heuristic to find the LeadingOnes optimum, n = 100, 000.
Stage of the GG hyper-heuristic has a positive effect on the runtime.
Figure 5 shows the effects of increasing the problem size n for a variety of fixed τ values, for the GRG
hyper-heuristic. We can see that an increased problem size leads to faster runtimes. The performance
difference between the τ values decreases with increased n, suggesting that further increasing n would lead
to similar, optimal performance for a large range of values, as suggested by Corollary 15. For n = 108 , the
runtime for τ = 0.6n ln n is ≈ 0.4271n2, only slightly deviated from the optimal value of ≈ 0.4232n2.

7.2

More Than Two Low-level Heuristics (k ≥ 2)

We now consider the generalised hyper-heuristics using k operators, (1, . . . , k) bitflips, and look at the impact
of the parameter τ .
Figure 6 shows the runtimes for the Generalised Random Gradient hyper-heuristic when choosing from
2 to 5 separate mutation operators on LeadingOnes, for a problem size of n = 100, 000.
We see that incorporating more operators can be beneficial to the performance of the GRG hyper31

Runtime (/n2 )

0.60
2-op
3-op
4-op
5-op

0.55

0.50

0.45

0

2

4

6

8

10

12

14

16

18

20

22

24

τ (/n)
Figure 7: Average number of fitness function evaluations required by the Generalised Greedy hyper-heuristic
to find the LeadingOnes optimum, n = 100, 000.

Runtime (/n2 )

0.54
0.52
0.50
0.48
2-op
4-op

0.46
0

50

100

150

200

250

300

350

400

450

500

550

600

650

3-op
5-op
700

750

τ (/n)
Figure 8: Average number of fitness function evaluations required by the Generalised Greedy hyper-heuristic
to find the LeadingOnes optimum, n = 100, 000.
heuristic. Whilst the 2-operator hyper-heuristic achieves a best performance of approximately 0.44n2 , the
5-operator hyper-heuristic achieves a best performance of around 0.425n2. It is, however, important to set
τ optimally to achieve the best performance. For 0 ≤ 0.35n ln(n) ≤ τ and τ ≥ 1.5n ln(n), the 2-operator
hyper-heuristic outperforms the others; however, it is unable to achieve a better optimal performance. The
results suggest that the more operators that are incorporated in the hyper-heuristic, the shorter the range
of τ values for which it performs the best, in comparison with the hyper-heuristics with fewer operators.
Figure 7 shows the runtimes for the Generalised Greedy hyper-heuristic when choosing from 2 to 5
separate mutation operators on LeadingOnes, for a problem size of n = 100, 000.
Unlike the Generalised Random Gradient hyper-heuristic the Generalised Greedy, like the ‘simple’ mechanisms (see Theorem 29, Corollary 30), displays a detrimental performance when more operators are included.
Unlike the GRG hyper-heuristic, which exploits a high-performing operator while running for a shorter time
with low-performing operators, the GG hyper-heuristic runs each chosen operator for a fixed period of time.
Involving more operators means a lower chance of choosing the best operator in the Decision Stage.
Figure 8 shows the runtimes for the Generalised Greedy hyper-heuristic when choosing from 2 to 5 separate mutation operators on LeadingOnes, for a problem size of n = 100, 000, for a much larger range of
32

Runtime (/n2 )

0.60
0.55
RLS

0.50

2-op
3-op
4-op
5-op

0.45
0.40

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

τ (/(n ln(n)))
Figure 9: Average number of fitness function evaluations required by the Generalised Greedy Gradient
hyper-heuristic to find the LeadingOnes optimum, n = 100, 000.
τ values. We can see that the performance of the 2-operator hyper-heuristic remains the best performing
hyper-heuristic. Although the performance of the 5-operator hyper-heuristic is the worst, it is worth noting
than even this operator outperforms the runtime of the single operator algorithm RLS (i.e., 0.5n2 ). For
this hyper-heuristic, the detriment in performance between τ = 50n and τ = 750n is approximately 0.01n2 ,
confirming that the Generalised Greedy hyper-heuristic is robust to the choice of τ .
Figure 9 shows the runtime for the Generalised Greedy Gradient hyper-heuristic on LeadingOnes for
n = 100, 000.
While the hyper-heuristic displays similar performance to the GRG hyper-heuristic, we note that the
best performance of each k outperforms the respective selection for the GRG hyper-heuristic with the same
k. This suggests that, while the Decision Stage can be detrimental in the case of the GG hyper-heuristic,
the Exploitation Stage idea can correct for poor operator choices, leading to better performance. We can
see, for example, that the best performance of the 5-operator variation of the GGG hyper-heuristic, for
τ ≈ 0.62n ln(n), achieves a performance of approximately 0.418n2, outperforming the best possible 2-operator
runtime, shown in Corollary 25, of ≈ 0.423n2 .

8

Conclusion

The field analysing theoretically the performance of hyper-heuristics is growing. Previous results have shown
that the ‘simple’ learning mechanisms applied in combinatorial optimisation applications show no signs of
learning on LeadingOnes and perform equivalently to choosing operators at random, up to lower order
terms. We generalised the existing learning mechanisms to allow success to be measured over a longer period
of time, τ , rather than in a single iteration, and proved that these generalised hyper-heuristics are faster
than all standard evolutionary and local-search algorithms for LeadingOnes.
To apply the generalised hyper-heuristics, a value for the learning period τ is required. Although our
results indicate that τ is a fairly robust parameter (i.e., for n = 10, 000 all generalised hyper-heuristics
achieved faster experimental runtimes than that of the (1+1) EA for all tested values of τ between 1 and
1,000,000), setting it appropriately will lead to optimal performance. Concerning the Generalised Random
Gradient hyper-heuristic, clearly τ must be large enough to have at least a constant expected number of
successes within τ steps, if the hyper-heuristic has to learn about the operator performance. Obviously,
setting large values of τ may lead to large runtimes, since switching operators requires Ω(τ ) steps. Similar
considerations may also be made for the Generalised Greedy hyper-heuristic that experiments indicate is even
more robust to the choice of τ . Concerning the negative effects that may occur for too large values of τ , the
GapPath function can be considered as a worst-case scenario for the generalised hyper-heuristics, because

33

the operator has to change after every success. Nevertheless, we have proved that the hyper-heuristics are
asymptotically just as efficient as the ‘simple’ mechanisms for values of τ as large as O(n2 ).
The Generalised Greedy Gradient hyper-heuristic, which combines Generalised Greedy’s Decision Stage
with Generalised Random Gradient’s Exploitation Stage, can achieve even better performance than either
hyper-heuristic.
We finally have rigorously shown that the performance of the ‘simple’ mechanisms deteriorates as the
choice of operators (choosing from k ≥ 2) increases, while the performance of the Generalised Random
Gradient hyper-heuristic improves with a larger choice.
Several directions can be explored in future work. On one hand, we will analyse the hyper-heuristics’
performance on a broader class of problems, including classical ones from combinatorial optimisation, and
generalise the hyper-heuristics further by allowing the algorithms to automatically learn how to adapt τ . Finally, more sophisticated hyper-heuristics, such as the choice function approach [6] that have shown superior
performance in practical applications, should be analysed.

References
[1] F. Alanazi and P. K. Lehre. Runtime analysis of selection hyper-heuristics with classical learning mechanisms.
In 2014 IEEE Congress on Evolutionary Computation (CEC), pages 2515–2523. Springer, July 2014.
[2] Fawaz Alanazi and Per Kristian Lehre. Limits to learning in reinforcement learning hyper-heuristics. In Evolutionary Computation in Combinatorial Optimization (EvoCOP 2016), pages 170–185, Cham, 2016. Springer
International Publishing.
[3] Shahriar Asta and Ender Özcan. An apprenticeship learning hyper-heuristic for vehicle routing in HyFlex. In
IEEE Symposium on Evolving and Autonomous Learning Systems (EALS 2014), pages 65–72. IEEE, 2014.
[4] Süntje Böttcher, Benjamin Doerr, and Frank Neumann. Optimal fixed and adaptive mutation rates for the
leadingones problem. In Parallel Problem Solving from Nature (PPSN XI), pages 1–10, Berlin, Heidelberg, 2010.
Springer.
[5] Edmund K Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and
Rong Qu. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society,
64(12):1695–1724, 2013.
[6] Peter Cowling, Graham Kendall, and Eric Soubeiga. A hyperheuristic approach to scheduling a sales summit.
In Practice and Theory of Automated Timetabling III, pages 176–190, Berlin, Heidelberg, 2001. Springer.
[7] Peter Cowling, Graham Kendall, and Eric Soubeiga. Hyperheuristics: A tool for rapid prototyping in scheduling
and optimisation. In Applications of Evolutionary Computing: EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN Kinsale, Ireland, April 3–4, 2002 Proceedings, pages 1–10, Berlin, Heidelberg, 2002. Springer.
[8] Benjamin Doerr, Carola Doerr, and Jing Yang. k-bit mutation with self-adjusting k outperforms standard
bit mutation. In Parallel Problem Solving from Nature (PPSN XIV), pages 824–834. Springer International
Publishing, 2016.
[9] Benjamin Doerr and Marvin Künnemann. How the (1+λ) evolutionary algorithm optimizes linear functions.
In Genetic and Evolutionary Computation Conference, GECCO ’13, Amsterdam, The Netherlands, July 6-10,
2013, pages 1589–1596, 2013.
[10] Jonathon Gibbs, Graham Kendall, and Ender Özcan. Scheduling english football fixtures over the holiday period
using hyper-heuristics. In Parallel Problem Solving from Nature (PPSN XI), pages 496–505, Berlin, Heidelberg,
2010. Springer.
[11] Jun He, Feidun He, and Hongbin Dong. Pure strategy or mixed strategy? In Evolutionary Computation in
Combinatorial Optimization: 12th European Conference (EvoCOP 2012), pages 218–229, Berlin, Heidelberg,
2012. Springer.
[12] Jun He and Xin Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57–85, 2001.
[13] Daniel Johannsen. Random combinatorial structures and randomized search heuristics. PhD thesis, Universita̋t
des Saarlandes, Postfach 151141, 66041 Saarbra̋cken, 2010.
[14] Per Kristian Lehre and Ender Özcan. A runtime analysis of simple hyper-heuristics: To mix or not to mix
operators. In Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, FOGA XII ’13,
pages 97–104, New York, NY, USA, 2013. ACM.

34

[15] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. On the runtime analysis of generalised selection
hyper-heuristics for pseudo-boolean optimisation. In Proceedings of the Genetic and Evolutionary Computation
Conference, GECCO ’17, pages 849–856, New York, NY, USA, 2017. ACM.
[16] Eunice López-Camacho, Hugo Terashima-Marin, Peter Ross, and Gabriela Ochoa. A unified hyper-heuristic
framework for solving bin packing problems. Expert Systems with Applications, 41(15):6876–6889, 2014.
[17] İbrahim Maden, S. Uyar, and Ender Özcan. Landscape analysis of simple perturbative hyperheuristics. In 15th
International Conference on Soft Computing, pages 16–22. Mendel, 2009.
[18] Gabriela Ochoa, Rong Qu, and Edmund K. Burke. Analyzing the landscape of a graph based hyper-heuristic for
timetabling problems. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation,
GECCO ’09, pages 341–348, New York, NY, USA, 2009. ACM.
[19] Gabriela Ochoa, José Antonio Vázquez-Rodrı́guez, Sanja Petrovic, and Edmund Burke. Dispatching rules for
production scheduling: a hyper-heuristic landscape analysis. In IEEE Congress on Evolutionary Computation.,
pages 1873–1880. IEEE, 2009.
[20] P. S. Oliveto and Xin Yao. Runtime analysis of evolutionary algorithms for discrete optimization. In Anne Auger
and Benjamin Doerr, editors, Theory of Randomized Search Heuristics: Foundations and Recent Developments,
pages 21–52. World Scientific, 02 2011.
[21] Ender Özcan, Mustafa Misir, Gabriela Ochoa, and Edmund K. Burke. A reinforcement learning - great-deluge
hyper-heuristic for examination timetabling. Applied Metaheuristic Computing, 1(1):39–59, 2010.
[22] Abraham Wald. On cumulative sums of random variables. Ann. Math. Statist., 15(3):283–296, 09 1944.
[23] David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE Transactions on
Evolutionary Computation, 1(1):67–82, 1997.

35

