arXiv:1607.06641v3 [cs.NE] 12 Jun 2017

Optimal resampling for the noisy OneMax problem
Jialin Liu

Michael Fairbank

Diego Pérez-Liébana

Simon M. Lucas

University of Essex
Colchester CO4 3SQ
United Kingdom
jialin.liu@essex.ac.uk

University of Essex
Colchester CO4 3SQ
United Kingdom
m.fairbank@essex.ac.uk

University of Essex
Colchester CO4 3SQ
United Kingdom
dperez@essex.ac.uk

University of Essex
Colchester CO4 3SQ
United Kingdom
sml@essex.ac.uk

Abstract—The OneMax problem is a standard benchmark
optimisation problem for a binary search space. Recent work
on applying a Bandit-Based Random Mutation Hill-Climbing
algorithm to the noisy OneMax problem showed that it is
important to choose a good value for the resampling number
to make a careful trade off between taking more samples in
order to reduce noise, and taking fewer samples to reduce the
total computational cost. This paper extends that observation by
deriving an analytical expression for the running time of the Random Mutation Hill-Climbing algorithm with resampling applied
to the noisy OneMax problem, and showing both theoretically
and empirically that the optimal resampling number increases
with the number of dimensions in the search space.
Index Terms—Noisy OneMax, resampling, Random Mutation
Hill-Climber (RMHC)

I. I NTRODUCTION
Evolutionary Algorithms (EA) have been widely used in
both continuous and discrete domains [1], [2], [3].
Resampling1 has proved to be a powerful tool in improving
the local performance of EAs in noisy optimisation [3], [4],
[5], and different resampling rules have been applied to a
variety of EAs in continuous noisy optimisation, as studied
in [6], [7]. Akimoto et al. [8] concluded that the running time
for an adapted algorithm using resampling to solve a problem
with additive Gaussian noise is similar to the runtime in the
noise-free case when multiplying by a factor log n, where n
is the problem dimension.
Previous work on solving the OneMax problem [9] has
concentrated on using a (1+1)-Evolution Algorithm (EA) [10],
[11]. The OneMax problem with One-bit noise (exactly one
uniformly selected bit changes with probability p ∈ (0, 1)
due to the noise) has been studied previously by Droste [10].
Qian et al. [11] claimed that resampling wasn’t beneficial in
optimising OneMax with additive Gaussian noise using (1+1)EA. Recently, Liu et al. [12], [13] applied a bandit-based
RMHC to the noisy OneMax problem, and showed that it was
important to choose an optimal resampling number, so as to
compromise the reduction in sampling noise against the cost
of doing so.
The main contribution of this work is the analysis of the
optimal resampling number in the OneMax problem, in the
presence of additive Gaussian noise. We show that the optimal
resampling number increases with the problem dimension.
1 In this paper, “resampling” refers to the multiple re-evalutions of a
solution.

The paper is structured as follows. Section II provides a
brief review of the related work and describes our noisy
OneMax problem. Section III explains the modified Random
Mutation Hill-Climbing algorithm used in the noisy context.
Section IV analyses the optimal resampling number in the
defined noisy OneMax problem. Experimental results are
presented and discussed in Section V. Finally, Section VI
concludes the work.
II. BACKGROUND
This section is organised as follows. Section II-A presents
the original Random Mutation Hill-Climbing algorithm and
its relation to (1+1)-EA. Section II-B recalls the OneMax
problem, then a noisy variant of OneMax problem is defined
in Section II-C. More related literatures in solving different
noisy variants of OneMax problems are discussed in Section
II-D
A. Random Mutation Hill-Climbing
The Random Mutation Hill-Climbing (RMHC), also called
Stochastic Hill Climbing, is a derivative-free optimisation
method mostly used in discrete domains [14], [15]. RMHC
can also be seen as an evolutionary algorithm in which
there is a population of just one individual, and at each
generation a child genome is formed from the current (best-sofar) individual by mutating exactly one gene, chosen uniformly
at random. After mutation, the mutated child genome replaces
its parent if its fitness value is improved or equivalent. In other
words, RMHC randomly selects a neighbour candidate in the
search space (where neighbour means it differs in exactly
one gene) and updates its current candidate using a fitnesscomparison-based method.
Borisovsky and Eremeev [16] proved that under some
conditions, RMHC outperforms other EAs in terms of the
probability of finding an anytime solution on several problems
including OneMax.
(1+1)-EA is a variant of RMHC, the only difference being
that every gene of the current individual’s genome mutates
with a certain probability at each generation.2 (1+1)-EA has
been widely used in both discrete and continuous optimisation
problems [16]. A variant of (1+1)-EA is the closely related
2 However note that some communities refer to RMHC as “(1+1)Evolutionary Algorithm (EA)”, but we will avoid that description.

“(1+1)-Evolutionary Strategy (ES)” [17], which uses a selfadaptive mutation step-size and is applicable to real-valued
search spaces.
Despite its simplicity, RMHC often competes surprisingly
well with more complex algorithms [18], especially when deployed with random restarts. For instance, Lucas and Reynolds
evolved Deterministic Finite Automata (DFA) [14], [15] using
a multi-start RMHC algorithm with very competitive results,
outperforming more complex evolutionary algorithms, and for
some classes of problems also outperforming the state of the
art Evidence-Driven State Merging (EDSM) [19] algorithms.
B. OneMax problem
The OneMax problem [9] is a standard benchmark optimisation problem for a binary search space and has been deeply
studied in the previous literatures [2], [20], [21]. The objective
is to maximise the number of 1s occurring in a binary string,
i.e., for a given n-bit string x, the fitness function to maximise
for that string is given by
f (x) =

n
X

xi ,

(1)

i=1

where xi denotes the ith bit in the string x, and is either 1 or
0.
C. Noisy OneMax
In this work, we study a noisy variant of the OneMax
problem, where the fitness function is corrupted by some
additive unbiased normally distributed noise with constant
variance, formalised in (2).
f 0 (x) = f (x) + N (0, σ 2 ),

(2)

with N (0, σ 2 ) denoting a Gaussian noise, with mean 0 and
variance σ 2 . From now on, we will use f 0(i) (x) to denote the
ith call to noisy fitness function on x. At each call, the noise
is independently sampled from N (0, σ 2 ) and takes effect after
the true fitness is evaluated.
There is a variety of noise models for the OneMax problem,
as described in the next section. To avoid confusion, the term
“noisy OneMax” refers to (2), the noisy variant used in this
paper. Also, the “noisy” refers to the noise in the fitness
function’s ability to read the true fitness of the genome; not
the mutations which are deliberately applied to the genome,
which could be interpreted as a second kind of “noise”.
D. Related work
Different noise models for the OneMax problem have been
studied before.
a) Proportionate selection is noise invariant: Our noise
model is the same as the one used in [22]. Miller and
Goldberg [22] used a GA with µ parents and λ offsprings, and
proved that increasing noise level did not affect selection pressure for Genetic Algorithms (GA) using fitness-proportionate
selection, in which each individual survives with a probability
proportional to its fitness divided by the average fitness in the
population [22], [23].

b) Resampling does not add benefit in low dimension:
Qian et al. [11] applied (1+1)-EA using mutation probability
1
and at most 100 resamplings to a 10-bit noisy OneMax
p = 10
problem corrupted by additive Gaussian noise with variance
100 ((2) with σ 2 = 100), and concluded that resampling
wasn’t beneficial for the (1+1)-EA in optimising the noisy
OneMax problem. In their model, resampling had the effect of
lowering the variance of the noise to 1, which is exactly as big
as the lower bound of the differences between distinct noisefree fitness values. With that level of resampling and problem
dimension, the problem is still difficult to solve. We present,
later in this paper, our application of RMHC using larger
resampling numbers in noisy OneMax, with noise variance
σ 2 = 1 and do observe that resampling adds a significant
benefit when the dimension is above 10 (Section V).
c) Solving high dimension noisy OneMax: Sastry et
al. [24] designed a fully parallelised, highly-efficient compact Genetic Algorithm (cGA) to solve very high dimension
problems, and compared it to RMHC on a noisy OneMax
problem using noise variance depending linearly on the length
of string, to allow for more difficult problems, for the reason
that a randomly initiated n-bit string has fitness variance
n
4 . RMHC without resampling performed poorly when the
problem dimension is higher than 10, 000.
d) Noise takes effect before the evaluation: Droste [10]
defined a One-bit noise model for the OneMax problem, in
which during every fitness evaluation of the bit-string x, there
was exactly one uniformly-chosen random bit mis-read with
probability p0 . Hence the measured noisy fitness values are
equivalent to replacing the Gaussian noise term in (2) by
an appropriate discrete random variable taking values from
{−1, 0, 1}. Under this scheme, Droste showed that (1+1)EA with mutation probability p = n1 could optimise a nbit OneMax problem corrupted by One-bit noise, with high
probability, in polynomial time if p0 is O( log(n)
n ).
III. R ANDOM M UTATION H ILL -C LIMBING IN NOISY
CONTEXT

When RMHC is applied to the noisy OneMax fitness function (2), a mutation of the k th gene refers to flipping the k th bit
of the string. The standard deviation of the second term in (2)
(the explicit noise term) is of the same order of magnitude
as the noise in the first term of (2) (the OneMax fitness
term) introduced by mutations from the RMHC algorithm.
This extremely poor signal-to-noise ratio would cause major
problems for hill-climbing strategies such as RMHC. Hence,
we use RMHC with resampling, applied to the noisy OneMax
problem, so as to try to reduce the unwanted variance, and to
allow the hill climber to work.
A. Noise-free case
Algorithm 1 recalls the generic RMHC, without any resampling. This is suitable for noise-free problems.
Here we have assumed the fitness value of the best-so-far
genome could be stored after each cycle. If, alternatively, no
space was allocated to store that fitness value, or if fitness

Algorithm 1 Random Mutation Hill-Climbing algorithm
(RMHC). No resampling is performed
.
Require: n ∈ N∗ : genome length (problem dimension)
Require: X : search space
Require: f : X 7→ R: fitness function
1: Randomly initialise a genome x ∈ X
2: bestF itSoF ar ← f (x)
3: N ← 1
. Total evaluation count so far
4: while time not elapsed do
5:
Uniformly randomly select k ∈ {1, . . . , n}
6:
y ← new genome by mutating the k th gene of x
7:
F ity ← f (y)
8:
N ←N +1
. Update evaluation count
9:
if F ity ≥ bestF itSoF ar then
10:
x←y
. Update the best-so-far genome
11:
bestF itSoF ar ← F ity
12:
end if
13: end while
14: return x

evaluations can only be made by directly comparing two individuals, then the best-so-far genome’s fitness would need to
be re-evaluated at each generation, thus raising the algorithm’s
“evaluation count”, N , by a factor of approximately 2.
B. Noisy case
The previous RMHC algorithm (Algorithm 1) was applicable to deterministic fitness functions. Algorithm 2 extends this
RMHC algorithm to be applicable to noisy fitness functions.
It achieves this extension by using resampling, so that each
genome is evaluated multiple times, so as to reduce the effect
of noise which might interfere with hill climbing.
Additionally, if the statistics of the best-so-far genome can
be stored, instead of comparing directly the fitness values
of the offspring to the fitness of the parent (the best-so-far
genome), the average fitness value of the best-so-far genome
in the history is compared at each generation (line 11 of
Algorithm 2).
IV. A NALYSIS OF OPTIMAL RESAMPLING NUMBER IN
NOISY O NE M AX PROBLEM
This section analyses the application of the modified RMHC
algorithm (Algorithm 2) to the noisy OneMax problem, with
fixed noise level, by describing it as a Markov process.
Several variants of Algorithm 2 are considered in Section
IV-B, including analysis of varying the resampling number,
and of the effect of storing a statistic of the best-so-far genome
versus not storing it. The benefit of storing the statistics of
the best-so-far genome is illustrated in Section IV-B. Section
IV-C derives an expression for the length of Markov chain
that represents the learning algorithm, and the optimal level
of resampling is calculated and displayed, in Section IV-D.
We restrict the analysis in this section to a fixed noise level
σ 2 = 1. This noise level is a significant challenge for RMHC,
as the difference between the parent’s fitness and the one of the

Algorithm 2 RMHC modified to include resampling, suitable
for the noisy case. f 0(i) (x) denotes the ith call to the noisy
fitness function on search point x.
Require: n ∈ N∗ : genome length (problem dimension)
Require: X : search space
Require: f : X 7→ R: fitness function
Require: r ∈ N∗ : Resampling number
1: Randomly initialise a genome x ∈ X
2: bestF itSoF ar ← 0
3: M ← 0
. Evaluation count for the latest best-so-far
genome
4: N ← 0
. Total evaluation count so far
5: while time not elapsed do
6:
Uniformly randomly select k ∈ {1, . . . , n}
7:
y ← new genome
by mutating the k th gene of x
Pr
1
0(i)
8:
F itx ← r Pi=1 f (x)
r
9:
F ity ← 1r i=1 f 0(i) (y)
10:
N ← N + 2r
. Update evaluation count
ar×M +F itx ×r
11:
averageF itnessx ← bestF itSoFM
+r
12:
if F ity ≥ averageF itnessx then
13:
x←y
. Update the best-so-far genome
14:
bestF itSoF ar ← F ity
15:
M ←r
16:
else
17:
bestF itSoF ar ← averageF itnessx
18:
M ←M +r
19:
end if
20: end while
21: return x

offspring is always 1 in our model. This motivates resampling,
since resampling a candidate solution r times can reduce the
variance of the noise by a factor of 1r . The extension of this
analysis to the general σ would be straightforward.
A. Markov chain description for noisy OneMax
We consider a n-bit OneMax problem with constant variance Gaussian noise, σ 2 = 1. Throughout this section, we
summarise the n-bit OneMax state vector by a single scalar
number, i, equal to the number of ones in the n-bit string. As
the RMHC algorithm makes mutations to the full bit string,
the compressed state-representation, i, will change by ±1. The
transition probabilities for the change in i are dependent only
on the scalar i. Hence the evolution of the variable i is modeled
by a Markov process.
After each mutation is initially made by the RMHC algorithm, the fitness of that mutated bit string is evaluated using
(2), and the RMHC algorithm will either accept or reject that
mutation.
Let pT A , pF A , pT R and pF R denote the probability of true
acceptance, false acceptance, true rejection and false rejection,
respectively, for the RMHC algorithm to accept or reject
any given mutation. These four probabilities depend on the
resampling strategy employed by the RMHC algorithm, and

are derived in Section IV-B. However, since complementary
probability pairs must sum to one, we do generally have that,
pF A

=

1 − pT A ,

(3)

pF R

=

1 − pT R .

(4)

Assuming these acceptance and rejection probabilities are
known, we can then derive the Markov state transition probabilities as follows:
For any state scalar i ∈ {0, 1, . . . , n − 1}, the corresponding
OneMax bit string has i ones and (n − i) zeros. Therefore the
probability of uniformly randomly choosing a zero bit is n−i
n .
Hence, for RMHC to make an improvement to the genome, it
must randomly choose one of these zero bits and that mutation
must be accepted. Therefore the transition probability from
state i to state i + 1 in one generation is:
n−i
pT A .
(5)
n
Similarly, for RMHC to make the genome worse, it must
choose a one bit (with probability ni ) and flip it to a zero, and
that mutation must be accepted, with probability pF A . Hence
we obtain
P[St+1 = i + 1|St = i] =

i
pF A .
(6)
n
For an RMHC mutation to make no progress in the genome,
the mutation must be rejected. This could mean a one bit
is chosen (with probability ni ) and rejected (with probability
pT R ), or it could be that a zero bit is chosen (with probability
n−i
n ) and rejected (with probability pF R ). Hence we obtain
P[St+1 = i − 1|St = i] =

i
n−i
pT R +
pF R .
(7)
n
n
The probabilities given by (5)-(7) appear on the three arrows
emanating from the central node “i” in the Markov chain
shown in Fig.1. The Markov chain’s absorption state is state
n, since the OneMax problem is solved and terminates as soon
as i = n is reached.
P[St+1 = i|St = i] =

B. Rejection and acceptance probabilities for noisy OneMax
problem with RMHC
The Markov Process described in the previous subsection
relied upon knowledge of the acceptance and rejection probabilities pT R and pT A , which are dependent on the RMHC
resampling method chosen.
We discuss three RMHC resampling cases here, and calculate the corresponding acceptance/rejection probabilities. We
consider three separate cases:
1) No resampling, no statistic of the best-so-far genome
is stored: If no statistic of the best-so-far genome is stored,
the best-so-far one needs to be re-evaluated once at each
generation in the case without resampling.
First we assume that the newly generated genome y is better
than the current genome x, i.e. f (y) > f (x), where this fitness
function is the noise-free version given by (1). Since f (x) is
the true fitness of string x, we have f (x) = i, the number
of ones in string x. Since the two genomes x and y are

evaluated using the noisy fitness function (2), and since we are
comparing x and y without resampling or storing the statistics
of the best-so-far genome, the probability of true acceptance
is
pT A

=

P(f 0 (y) > f 0 (x)|f (y) = i + 1, f (x) = i)

= P(ωy + 1 > ωx ) = P(ωy − ωx > −1).
where ωy and ωx are independent samples from N (0, 1), thus
ωy − ωx ∼ N (0, 2). Then,
pT A

= P(ωy − ωx > −1) = P(ωy − ωx ≤ 1)
1 1
1
= CDFGaussian(0,2) (1) = + erf ( ).
2 2
2

(8)

Respectively, if the newly generated genome y is worse than
the current genome x, i.e. f (y) < f (x), when comparing two
genomes without resampling or storing the statistics of the
best-so-far genome, the probability of true rejection is
pT R

= P(f 0 (y) < f 0 (x)|f (y) = i − 1, f (x) = i)
= P(ωy − 1 < ωx ) = P(ωy − ωx < 1) = pT A . (9)

Therefore, for this situation of RMHC with no resampling
and no storage of the best-so-far fitness, we can for example
find the probability of transferring from state i to state i + 1,
as follows:
n−i
pT A
(by (5))
n 

n−i 1 1
1
=
+ erf ( )
(by (8)).
n
2 2
2

P[St+1 = i + 1|St = i] =

2) When comparing two genomes using r resamplings
without storing the statistics of the best-so-far genome: If each
genome can be re-evaluated r > 1 times, i.e., r resamplings
are used, but still no statistic of the best-so-far genome is
stored, F itx and F ity are compared at each generation (lines
8 and 9 of Algorithm 2). Therefore, the variance of F itx and
F ity , given x and y, are 1r . Then,
pT A

= P(F ity > F itx |f (y) = i + 1, f (x) = i)
= P(ωy0 + 1 > ωx0 ) = P(ωy0 − ωx0 > −1).

where ωy0 and ωx0 are independent samples from N (0, 1r ), thus
ωy − ωx ∼ N (0, 2r ). Then,
pT A

=
=

P(ωy0 − ωx0 > −1) = P(ωy0 − ωx0 ≤ 1)
√
1 1
r
CDFGaussian(0, r2 ) (1) = + erf (
). (10)
2 2
2

Similarly, pT R = pT A holds in this case.
The probability of transferring from √state i to state i + 1
r
1
1
in one generation is n−i
n ( 2 + 2 erf ( 2 )), larger than the
probability in the previous case without resampling (Section
IV-B1).
Therefore, the probability of true acceptance is improved
by resampling genomes.

i
n pT R

pF R

+

n−i+1
pT A
n

...

0

n−i
n pF R
n−i
n pT A

i-1

i+1

i
i
n pF A

...

n

i+1
n pF A

Fig. 1: Markov states and transitions in a noisy OneMax problem. Markov state “i” refers to a OneMax bit-string with i ones
and n − i zeros in the string.

3) When comparing two genomes using r > 1 resamplings
and the statistics of the best-so-far genome: Additionally, if
one has access to averageF itness, the average fitness value
of the best-so-far genome, and M , the number of times that
the best-so-far genome has been evaluated, by line 11 of
Algorithm 2
bestF itSoF ar × M + F itx × r
,
M +r
(11)
with r > 1. Therefore, the variance of averageF itnessx ,
given x, is M1+r . The variance of F ity , given y, is 1r .
The probability of true acceptance is
averageF itnessx ←

pT A = P(F ity > averageF itnessx |f (y) = i + 1, f (x) = i)
= P(ωy0 + 1 > ωx00 ) = P(ωy0 − ωx00 > −1).
where ωy0 and ωx00 are independent samples from N (0, 1r ) and
M +2r
N (0, M1+r ), respectively. Thus, ωy0 − ωx00 ∼ N (0, r(M
+r) ).
Then,
pT A

=

P(ωy0 − ωx00 > −1)

=

P(ωy0 − ωx00 ≤ 1)

=

CDFGaussian(0, M +2r ) (1)
r(M +r)
s
1 1
r(M + r)
+ erf (
)
2 2
2(M + 2r)

=

we consider the second case discussed previously in Section
IV-B2.
The Markov chain length can be found by defining the
notation T(l→m) to mean the expectation of the number of
generations required to get from a Markov state with value
i = l to a Markov state with value i = m.
By considering the three arrows that emanate from the
central i node in Fig.1, we can form an algebraic expression
for T(i→i+1) , as follows:
n−i
pT A
n


i
n−i
+
pT R +
pF R 1 + T(i→i+1)
n
n

i
(13)
+ pF A 1 + T(i−1→i+1) .
n
The three terms in (13) correspond to the three arrows from
node i in Fig.1, pointing to nodes i+1, i and i−1, respectively.
Since it is always necessary to go from state i − 1 to i + 1
via their middle state i, we can form the relationship
T(i→i+1) =

T(i−1→i+1) ≡ T(i−1→i) + T(i→i+1) .

(12)

Similarly, pT R = pT A holds in this case.
The probability of transferring q
from state i to state i + 1 in
r(M +r)
n−i 1
1
one generation is n ( 2 + 2 erf ( 2(M
+2r) )) with M ≥ r >
1, larger than the probabilities in the previous cases (Sections
IV-B1 and IV-B2).
Therefore, the probability of true acceptance is improved by
resampling genomes and storing the statistics of the best-so-far
genome. However, the trade-off between the total evaluations
and the accuracy needs to be considered.
C. Markov chain analysis
Now that we have described the Markov chain in Section
IV-A, and derived the acceptance and rejection probabilities
for the noisy OneMax problem in Section IV-B, we next
derive an analytical expectation for the full trajectory length
for solving the noisy OneMax problem, using RMHC with
resamplings, starting from a bit string full of zeros. To simplify
analysis, no stored statistic is considered (M = 0), thus

Furthermore, reusing (3) and (4), i.e. pF A = (1−pT A ), pF R =
(1 − pT R ), together with pT R = pT A from Section IV-B, we
get:
n−i
T(i→i+1) =
pT A
n



n−i
i
pT A +
(1 − pT A ) 1 + T(i→i+1)
+
n
n

i
+
(1 − pT A ) 1 + T(i−1→i) + T(i→i+1) .
(14)
n
Solving 14 for T(i→i+1) , which appears three times in that
equation, we get:
T(i→i+1) =

n
i(1 − pT A )
T(i−1→i) +
.
(n − i)pT A
(n − i)pT A

(15)

This is a recursive equation that defines the ith term in
terms of the (i − 1)th term. To terminate this recursion, an
explicit expression for T(0→1) can be found by considering
the number of generations required to get from i = 0 (i.e. a
string with all zeros in it) to i = 1 (i.e. a string with exactly
one 1 in it). This is given by
1
T(0→1) =
.
(16)
pT A

(15) and (16) form a recursion that easily can be unrolled
computationally, and it gives us the exact theoretical number of
transitions to traverse from one Markov state i to the adjacent
Markov state i + 1. Therefore to calculate the total number of
generations required to solve the noisy OneMax problem from
an initial Markov state i = 0, we need to calculate T(0→n) .
This can be expanded by adding all of the intermediate state
transitions to get
T(0→n) = T(0→1) + · · · + T(n−1→n)

(17)

(17) completes the theoretical analysis of the number of
steps required by RMHC to solve the noisy OneMax problem,
from an initial bit string of zeros. Note that each term of this
sum needs a solution to the recursive equations given by (15)
and (16), but with careful caching, the whole sum can be
evaluated in O(n) steps.
It’s notable that even though the above Markov chain analysis was aimed at Case 2 (Section IV-B2, i.e. with resampling
and no statistic stored), it also holds when there is no resampling, i.e., r = 1 (the first case detailed in Section IV-B1). In
both cases, pT A is deterministic given the resampling number
r. However, Case 3 (Section IV-B3) is not as straightforward
to analyse, because in that case that the average fitness value
(averageF itnessx ) depends on the evaluation number
(M ),
q
r(M +r)
1
1
and M is stochastic. Hence, pT A = 2 + 2 erf ( 2(M +2r) )
(12) changes at each generation of RMHC. Case 3 has not
been analysed in this paper, but it would be interesting to do
so in the future.

Fig. 2: Exact expectation of the number of fitness evaluations
required by RMHC to solve the noisy OneMax problem, using
different resampling numbers. The initial OneMax strings
were all zeros, and the RMHC algorithm did not store the
fitness of the best-so-far genome (case 2 described in Section
IV-B2). These curves were computed using (15)-(18), and pT A
defined by (10). The grey circle on each curve indicates the
optimal resampling number, which increases with the problem
dimension.

D. Analytical results of RMHC in noisy OneMax problem
At each generation of the actual RMHC algorithm, 2r
fitness-function evaluations are required, so that the total
number of fitness evaluations required to solve the noisy
OneMax problem is
2rT(0→n) .
(18)
This result is shown graphically in Fig.2, with various number
of resamplings (r) and problem dimension (n), under the
assumption that no statistic is stored for the fitness of the
best-so-far genome (case 2 described in Section IV-B2).
As can be seen from the location of the minima in Fig.2,
indicated by the small grey circles, the optimal resampling
number increases with the problem dimension. The exact optimal number of resamplings to make in different dimensions
is displayed in Fig.3.
V. E XPERIMENTAL RESULTS
To supplement the theoretical results of the previous and
to prove the benefit of storing statistics of the best-so-far
genome at each generation, we apply first RMHC on the
OneMax problem in a noise-free case (Fig.4), then evaluate
the performance of RMHC on the OneMax problem with the
presence of constant variance Gaussian noise (Fig.5). Each
experiment was repeated 100 times, initialised by an all zeros
string. The following may be observed from the figures:

Fig. 3: Exact theoretical optimal resampling number required
by RMHC, to solve the noisy OneMax problem, without
storing a statistic of the fitness of the best-so-far genome (case
2 described in Section IV-B2).

•

•
•

due to the noise, far more fitness evaluations are required
to find the optimum in the noisy case than in the noisefree context;
the higher dimension problem required more fitness evaluations to reach the optimum;
in dimensions ≤ 10, no resampling leads to a reduction
in the number of required fitness evaluations;

Fig. 4: Empirical number of evaluations consumed by RMHC
in the noise-free OneMax problem. No resampling is required
in the noise-free case. Each experiment is repeated 100 times
initialised by an all zeros string. The standard error is too tiny
to be seen.

(a) Empirical number of evaluations consumed by RMHC in the
noisy OneMax problem, across different resampling numbers, without
storing a statistic of the best-so-far genome. This empirically-obtained
data is equivalent to the theoretical results shown in Fig.2.

TABLE I: The expectation of fitness evaluation number required to reach the optimum ((15) and (16)) in the noisy
OneMax problem on dimension 10 and the empirical average
fitness evaluations consumed in 10, 000 trials.
r
1
2
3
4
5
10

•
•

Expected #evaluations
205.8283
238.5264
276.3340
317.9576
362.4065
612.2250

Empirical #evaluations
205.1998
239.7504
274.9920
317.8848
363.2520
611.0060

in higher dimensions (n > 10), the optimal amount of resampling required increases with the problem dimension;
in higher dimensions (n  10), the evaluation number is
significantly reduced by using the stored statistic.

Additionally, Fig.5 clearly shows the benefit of storing the
average fitness value and the current evaluation number of
the best-so-far genome at the end of each generation (case 3
described in Section IV-B3).
A. Validation of Theoretical results
To validate the theoretical results and equations of Section
IV, Table I demonstrates a very close match between the
theoretically obtained number of evaluations (derived from
(15)-(18)) and the equivalent empirically calculated numbers
(i.e. those found by actually running the RMHC algorithm
repeatedly and averaging). This table hopefully validates the
accuracy of our theoretical derivations and our numerical
implementation.
A further confirmation is shown by the equivalence of the
curves shown in Fig.5a to those shown in Fig.2.

(b) Empirical number of evaluations consumed by RMHC in the
noisy OneMax problem, across different resampling numbers, using
the stored statistic method. Fewer fitness evaluations are consumed
compared to the case without stored statistic (shown in the above
figure). Here the n = 1000 curve is truncated on the left, showing
missing data points, because in those cases an optimum was not
reached within 107 fitness evaluations, when using low resampling
numbers (r = 1, 2, 3, 4, 5).

Fig. 5: Performance of RMHC in the noisy OneMax problem
with different numbers of resamplings. The maximal budget
is 107 fitness evaluations. Note that the y-axis is the logarithm
of the evaluation number. Each experiment was repeated 100
times, initialised by an all-zeros string. The standard error is
too tiny to be seen. In the noisy case, the optimal resampling
number increases with the problem dimension.

VI. C ONCLUSION
This paper presents a noisy OneMax problem with additive
constant variance Gaussian noise and analyses the optimal
resampling number required by the Random Mutation Hill
Climber (RMHC) to handle the noise.
The number of fitness evaluations required by RMHC to
find the optimal solution in the noisy OneMax problem varies
with the resampling number. In a very low-dimensional noisy
OneMax problem (dimension 10, hence the string only has
1024 possible values), the optimal value may be found by
a random walk, and resampling can be counterproductive in
these cases (it leads to the remarkable growth of the number of
evaluations required to find the optimum as shown in Fig.5).
However, in higher dimensions, resampling to reduce the noise
is of critical importance, and makes the difference between
success and failure. The optimal level of resampling increases
with the dimension in the search space (as shown empirically
in Fig.2, and analytically in Fig.3). This is an interesting result,
which for this particular benchmark problem, is in conflict
with the observation by Qian et al. in [11] that resampling
was not beneficial.
RMHC is simple but efficient. The success of (µ-λ)-GA,
of which (1+1)-EA can be seen as a variant, depends on one
or more parameters, such as the size of the population, λ,
the number of parents, µ, and the crossover and mutation
operators. RMHC does not have such details to adjust and is
therefore simpler to apply. Due to its efficiency and simplicity
RMHC should be considered as a useful tool for expensive
optimisation tasks.
R EFERENCES
[1] H. Muhlenbein, “How genetic algorithms really work: I. mutation and
hill climbing. parallel problem solving from nature 2. b. manderick,”
1992.
[2] S. Droste, T. Jansen, and I. Wegener, “On the analysis of the (1+1)
evolutionary algorithm,” Theoretical Computer Science, vol. 276, no. 1,
pp. 51–81, 2002.
[3] D. V. Arnold and H.-G. Beyer, “A general noise model and its effects
on evolution strategy performance,” Evolutionary Computation, IEEE
Transactions on, vol. 10, no. 4, pp. 380–391, 2006.
[4] H.-G. Beyer, The Theory of Evolution Strategies. Springer Science &
Business Media, 2013.
[5] S. Astete-Morales, M.-L. Cauwet, J. Liu, and O. Teytaud, “Simple
and cumulative regret for continuous noisy optimization,” Theoretical
Computer Science, vol. 617, pp. 12–27, 2016.

[6] S. Astete-Morales, J. Liu, and O. Teytaud, “Log-log convergence for
noisy optimization,” in International Conference on Artificial Evolution
(Evolution Artificielle). Springer, 2013, pp. 16–28.
[7] J. Liu, “Portfolio methods in uncertain contexts,” Ph.D. dissertation,
INRIA, 12 2015.
[8] Y. Akimoto, S. Astete-Morales, and O. Teytaud, “Analysis of runtime
of optimization algorithms for noisy functions over discrete codomains,”
Theoretical Computer Science, vol. 605, pp. 42–50, 2015.
[9] J. D. Schaffer and L. J. Eshelman, “On crossover as an evolutionarily
viable strategy,” in ICGA, vol. 91, 1991, pp. 61–68.
[10] S. Droste, “Analysis of the (1+1) EA for a noisy OneMax,” in Genetic
and Evolutionary Computation–GECCO 2004. Springer, 2004, pp.
1088–1099.
[11] C. Qian, Y. Yu, Y. Jin, and Z.-H. Zhou, “On the Effectiveness of
Sampling for Evolutionary Optimization in Noisy Environments,” in
Parallel Problem Solving from Nature–PPSN XIII. Springer, 2014,
pp. 302–311.
[12] J. Liu, D. Peŕez-Liebana, and S. M. Lucas, “Bandit-based random
mutation hill-climbing,” arXiv preprint arXiv:1606.06041, 2016.
[Online]. Available: http://arxiv.org/abs/1606.06041
[13] ——, “Bandit-based random mutation hill-climbing,” 2017 IEEE
Congress on Evolutionary Computation (IEEE CEC), 2017.
[14] S. M. Lucas and T. J. Reynolds, “Learning DFA: Evolution versus
Evidence Driven State Merging,” in Evolutionary Computation, 2003.
CEC’03. The 2003 Congress on, vol. 1. IEEE, 2003, pp. 351–358.
[15] ——, “Learning deterministic finite automata with a smart state labeling
evolutionary algorithm,” Pattern Analysis and Machine Intelligence,
IEEE Transactions on, vol. 27, no. 7, pp. 1063–1074, 2005.
[16] P. A. Borisovsky and A. V. Eremeev, “Comparing evolutionary algorithms to the (1+1)-EA,” Theoretical Computer Science, vol. 403, no. 1,
pp. 33–41, 2008.
[17] H.-G. Beyer, “Toward a theory of evolution strategies: On the benefits of
sex—the (µ/µ, λ) theory,” Evol. Comput., vol. 3, no. 1, pp. 81–111, Mar.
1995. [Online]. Available: http://dx.doi.org/10.1162/evco.1995.3.1.81
[18] M. Mitchell and J. H. Holland, When will a Genetic Algorithm Outperform Hill-Climbing? Morgan Kaufmann, 1993.
[19] O. Cicchello and S. C. Kremer, “Beyond EDSM,” in International
Colloquium on Grammatical Inference. Springer, 2002, pp. 37–48.
[20] B. Doerr and C. Winzen, “Memory-restricted black-box complexity of
OneMax,” Information Processing Letters, vol. 112, no. 1, pp. 32–34,
2012.
[21] C. Doerr and J. Lengler, “OneMax in black-box models with
several restrictions,” Algorithmica, pp. 1–31, 2016. [Online]. Available:
http://dx.doi.org/10.1007/s00453-016-0168-1
[22] B. L. Miller and D. E. Goldberg, “Genetic algorithms, selection schemes,
and the varying effects of noise,” Evolutionary Computation, vol. 4,
no. 2, pp. 113–131, 1996.
[23] M. Mitchell, An introduction to genetic algorithms. MIT press, 1998.
[24] K. Sastry, D. E. Goldberg, and X. Llora, “Towards billion-bit optimization via a parallel estimation of distribution algorithm,” in Proceedings
of the 9th annual conference on Genetic and evolutionary computation.
ACM, 2007, pp. 577–584.

