The Benefit of Sex in Noisy Evolutionary Search
Tobias Friedrich, Timo Kötzing, Martin Krejca, and Andrew M. Sutton

arXiv:1502.02793v1 [] 10 Feb 2015

Friedrich-Schiller-Universität Jena, 07743 Jena, Germany
February 11, 2015
Abstract
The benefit of sexual recombination is one of the most fundamental questions both in population
genetics and evolutionary computation. It is widely believed that recombination helps solving difficult
optimization problems. We present the first result, which rigorously proves that it is beneficial to use
sexual recombination in an uncertain environment with a noisy fitness function. For this, we model
sexual recombination with a simple estimation of distribution algorithm called the Compact Genetic
Algorithm (cGA), which we compare with the classical µ + 1 EA. For a simple noisy fitness function with
additive Gaussian posterior noise N (0, σ 2 ), we prove that the mutation-only µ + 1 EA typically cannot
handle noise in polynomial time for σ 2 large enough while the cGA runs in polynomial time as long as
the population size is not too small. This shows that in this uncertain environment sexual recombination
is provably beneficial. We observe the same behavior in a small empirical study.

1

Introduction

Heuristic optimization is widely used in artificial intelligence for solving hard optimization problems, for
which no efficient problem-specific algorithm is known. Such problems are typically very large, noisy and
heavily constrained and cannot be solved by simple textbook algorithms. The inspiration for heuristic
general-purpose problem solvers often comes from nature. A well-known example is simulated annealing,
which is inspired from physical annealing in metallurgy. The largest and probably most successful class,
however, are biologically-inspired algorithms, especially evolutionary algorithms.
Evolutionary and genetic algorithms. Evolutionary Algorithms (EAs) were introduced in the 1960s and
have been successfully applied to a wide range of complex engineering and combinatorial problems [10, 22, 2].
Like Darwinian evolution in nature, evolutionary algorithms construct new solutions from old ones and select
the fitter ones to continue to the next iteration. The construction of new solutions from old ones, so-called
reproduction, can be asexual (mutation of a single individual) or sexual (crossover of two individuals). An
EA which uses sexual reproduction is typically called Genetic Algorithm (GA). Since the beginning of EAs, it
has been argued that GAs should be more powerful than pure EAs which use only asexual reproduction [12].
This was debated for decades, but theoretical results and explanations on crossover are still scarce. There are
some results for simple artificial test functions, where it was proven that a GA asymptotically outperforms
an EA without crossover [15, 16, 33, 28, 23, 19] and the other way around [27]. However, these artificial test
functions are typically tailored to the specific algorithm and proof technique and the results give little insight
on the advantage of sexual reproduction on realistic problems occurring in artificial intelligence. There are
also a few theoretical results for problem-specific algorithms and representations, namely coloring problems
inspired by the Ising model [30] and the all-pairs shortest path problem [8]. For a nice overview of different
aspects where populations and sex are beneficial for optimization of static fitness functions, see [26].
Noisy search. Heuristic optimization methods are typically not used for simple problems, but for rather
difficult problems in uncertain environments. Evolutionary algorithms are very popular in settings including
1

uncertainties; see [4] for a survey on examples in combinatorial optimization, but also [17] for an excellent
survey also discussing different sources of uncertainty. Uncertainty can be modeled by a probabilistic fitness
function, that is, a search point can have different fitness values each time it is evaluated. One way to deal
with this is to replace fitness evaluations with an average of a (large) sample of fitness evaluations and then
proceed as if there was no noise. We take a different route, accept the noise, and try to analyze how much
noise can be overcome by EAs without further modifications. To do this in a rigorous manner, we assume
additive posterior noise, that is, each time the fitness value of a search point is evaluated, we add a noise
value drawn from some distribution. This model was studied in evolutionary algorithms without crossover
in [13, 29, 6, 11].
Our results on graceful scaling. It has been observed that evolutionary algorithms benefit from sexual
recombination on simple static problems. It has also been observed that evolutionary algorithms (EAs) work
in uncertain environments. The important question, whether and how sexual recombination helps EAs on
noisy problems, remained open so far. We introduce the concept of graceful scaling (Def. 1) to measure how
well a black-box optimization algorithm can handle noise. We first prove a sufficient condition for when a
noise model is intractable for optimization by a the classical (µ + 1)-EA (Theorem 5) and show that this
implies that this simple asexual algorithm does not scale gracefully for large Gaussian noise (Corollary 6).
On the other hand, we study the compact GA (cGA), which strongly relies on recombination, and prove that
this sexual algorithm can handle noise gracefully (Theorem 11). These asymptotic results are complemented
and matched by corresponding experiments (Section 4). We observe empirically that especially the noiseoblivious variant of the cGA, which has no knowledge of properties of the added noise, performs especially
well. This confirms our theoretical finding that sexual recombination is especially powerful in uncertain
environments.
Biological motivation. Another motivation for our work comes from a biological perspective. The exact analysis of sexual recombination in both natural biological populations and in evolutionary computation
is extremely difficult. In the field of population genetics, researchers often study the effects of recombination
by describing the dynamics of natural selection on a freely recombining population under linkage equilibrium
in terms of the change in allele frequencies. Recently, several researchers have noticed a connection between
these models and optimization algorithms such as EDAs [20] from the evolutionary computation community
and the Multiplicative Weights Update Algorithm (MWUA) [1] also known from statistical machine learning [5, 3]. The cGA is an EDA that tracks allele frequencies by simulating a population of K individuals
undergoing gene pool recombination [21] where offspring are produced essentially by performing crossover
with all K individuals as parents. In this way, the cGA is reasonably similar to models used in population
genetics for studying sexual recombining populations, and thus we hope that our results can illuminate some
of the utility of crossover in the presence of noisy signals for adaptation.

2

Preliminaries

Let F be a family of pseudo-Boolean functions (Fn )n∈N where each Fn is a set of functions f : {0, 1}n → R.
Let D be a family of distributions (Dv )v∈R such that for all Dv ∈ D, E(Dv ) = 0. We define F with additive
posterior D-noise as the set F [D] := {fn + Dv : fn ∈ Fn , Dv ∈ D}.
Definition 1. An algorithm A scales gracefully with noise on F [D] if there is a polynomial q such that, for
all gn,v = fn + Dv ∈ F [D], there exists a parameter setting p such that A(p) finds the optimum of fn using
at most q(n, v) calls to gn,v .
In the remainder of the paper, we will study a particular function class (OneMax) and a particular noise
distribution (Gaussian, parametrized by the variance). Let σ 2 ≥ 0. We define the noisy OneMax function
om[σ2 ] : {0, 1}n → R := x 7→ kxk1 + Z where kxk1 := |{i : xi = 1}| and Z is a normally distributed random
variable Z ∼ N (0, σ 2 ) with zero mean and variance σ 2 .
The following proposition gives tail bounds for Z by using standard estimates of the complementary error
function [34].
2

Proposition 2. Let Z be a zero-mean Gaussian random variable with variance σ 2 . For all t > 0 we have


2
2
1
1
t
√
Pr (Z < −t) = erfc
≤ e−t /(2σ )
2
2
σ 2
and asymptotically for large t > 0,
Pr (Z < −t) =

σ −t2 /(2σ2 )
1
√
e
.
1 + o(1) 2πt

Definition 3. Let x, y ∈ {0, 1}n. Without loss of generality, suppose kxk1 − kyk1 = ℓ ≥ 0. Since om[σ2 ] is
a function of unitation, the probability that it misclassifies y as superior to x depends only on the so-called
phenotypic distance ℓ. We define Φ : [n] ∪ {0} → [0, 1] as
(
1/2
ℓ = 0,
Φ(ℓ) =
Pr(E | kxk1 − kyk1 = ℓ) ℓ > 0;
where E is the event that om[σ2 ] (x) < om[σ2 ] (y).
Lemma 4. For any 0 ≤ ℓ < n, Φ(ℓ) > Φ(ℓ + 1). Moreover, assuming σ 2 > 0,
Φ(ℓ) ≤


1
1 − Ω(σ −2 )
2

Proof. Let x and y be chosen arbitrarily from the set of all length-n binary strings pairs with kxk1 − kyk1 = ℓ
for any ℓ ∈ [n]. The event that om[σ2 ] incorrectly classifies y as superior to x is equivalent to the event
om[σ2 ] (x) < om[σ2 ] (y).
Pr(om[σ2 ] (x) < om[σ2 ] (y)) = Pr (ℓ + (Z1 − Z2 ) < 0) ,

where Z1 , Z2 ∼ N (0, σ 2 ) are independent identically distributed. Letting Z ∗ := Z1 − Z2 , we have Z ∗ ∼
N (0, 2σ 2 ) and Φ(ℓ) = Pr(Z ∗ < −ℓ). Furthermore, Φ(ℓ + 1) = Pr(Z ∗ < −(ℓ + 1)) < Pr(Z ∗ < −ℓ) = Φ(ℓ).
2
2
2
Finally, Pr (Z ∗ < −ℓ) ≤ (1/2)e−ℓ /(4σ ) ≤ (1/2)e−1/(4σ ) where we have applied Proposition 2. The claim
follows from the bound 1 − x > e−x/(1−x) .
A sequence of events {En } is said to hold with high probability (w.h.p.) if limn→∞ Pr(En ) = 1.

2.1

Algorithms

Algorithms that operate in the presence of noise often depend on a priori knowledge of the noise intensity
(measured by the variance). In such cases, the following scheme can always be used to transform such
algorithms into one that has no knowledge of the noise character. Suppose A(σ 2 ) is an algorithm that solves
a noisy function with variance at most σ 2 within Tδ (σ 2 ) steps with probability at least 1−δ. A noise-oblivious
scheme for A is as follows.
Algorithm 1: Noise-oblivious scheme for A
1
2
3
4

i ← 0;
repeat until solution found
Run A(2i ) for Tδ (2i ) steps;
i ← i + 1;

Claim. Suppose fn,v ∈ F [D] is a function with unknown variance v. Fixing n, assume Tδ grows at least
linearly, but uniformly so. Then for any s ∈ Z+ , the noise-oblivious scheme optimizes fn,v in at most Tδ (2s v)
steps with probability at least 1 − δ s .
3

Proof. By the assumptions on Tδ , for all c, x, cTδ (x) ≤ Tδ (cx) and so by induction, for any k ∈ N,
Pk
i
k+1
). Let phase i be the i-th time in the for loop of Algorithm 1. We pessimistii=0 Tδ (2 ) ≤ Tδ (2
cally suppose that the noise-oblivious scheme has not found a solution by phase log v − 1. Then for the next
s phases, the proposed variance is at least 2log v = v and P
the probability that one of these phases is successful
log v+s−1
is at least 1 − δ s . The total number of steps is at most i=0
Tδ (2i ) ≤ Tδ (2s v).

The (µ + 1)-EA, defined in Algorithm 2, is a simple mutation-only evolutionary algorithm that maintains
a population of µ solutions and uses elitist survival selection.
Algorithm 2: The (µ + 1)-EA
1
2
3
4
5
6
7

t ← 1;
Pt ← µ elements of {0, 1}n u.a.r.;
while termination criterion not met do
Select x ∈ Pt u.a.r.;
Create y by flipping each bit of x w/ probability 1/n;
Pt+1 ← Pt ∪ {y} \ {z} where f (z) ≤ f (v)∀v ∈ Pt ;
t ← t + 1;

The compact genetic algorithm (cGA) [14] is a genetic algorithm that maintains a population of size K
implicitly in memory. Rather than storing each individual separately, the cGA only keeps track of population
allele frequencies and updates these frequencies during evolution. Offspring are generated according to
these allele frequencies, which is similar to what occurs in a sexually-recombining population. Indeed, the
offspring generation procedure can be viewed as so-called gene pool recombination introduced by Mühlenbein
and Paaß [21] in which all K members participate in recombination. Since the cGA evolves a probability
distribution, it is also a type of estimation of distribution algorithm (EDA). The correspondence between
EDAs and models of sexually recombining populations has already been noted [20], and Harik et al. [14]
demonstrate empirically that the behavior of the cGA is equivalent to a simple genetic algorithm at least on
simple problems.
The first rigorous analysis of the cGA is due to Droste [9] who gave a general runtime lower bound for
all pseudo-Boolean functions, and a general upper bound for all linear pseudo-Boolean functions. Defined
in Algorithm 3, the cGA maintains for all times t ∈ N a frequency vector (p1,t , p2,t , . . . , pn,t ) ∈ [0, 1]n . In
the t-th iteration,
 independently nfrom this distribution where Pr(x = z) =
 xQand y are sampled
Q two strings
(1
−
p
)
for all z ∈ {0, 1} . The cGA then compares the objective
×
p
Pr(y = z) =
i,t
i,t
i : zi =0
i : zi =1
values of x and y, and updates the distribution by advancing pi,t toward the component of the winning string
by an additive term.
Algorithm 3: The compact GA
1
2
3
4
5
6
7
8
9
10
11
12

t ← 1;
p1,t ← p2,t ← · · · ← pn,t ← 1/2;
while termination criterion not met do
for i ∈ {1, . . . , n} do
xi ← 1 w/ prob. pi,t , xi ← 0 w/ prob. 1 − pi,t
for i ∈ {1, . . . , n} do
yi ← 1 w/ prob. pi,t , yi ← 0 w/ prob. 1 − pi,t

if f (x) < f (y) then swap x and y for i ∈ {1, . . . , n} do
if xi > yi then pi,t+1 ← pi,t + 1/K;
if xi < yi then pi,t+1 ← pi,t − 1/K;
if xi = yi then pi,t+1 ← pi,t ;
t ← t + 1;

4

3

Results

We derive rigorous bounds on the optimization time, defined as of the first hitting time of the process to the
true optimal solution (1n ) of om[σ2 ] , on a mutation-only based approach and the compact genetic algorithm.

3.1

Mutation-based Approach

In this section we consider the (µ + 1)-EA. We will first, in Theorem 5, give a sufficient condition for when a
noise model is intractable for optimization by a (µ + 1)-EA. Then we will show that, in the case of additive
posterior noise sampled from a Gaussian distribution, this condition is fulfilled if the noise is large enough,
showing that the (µ + 1)-EA cannot deal with arbitrary Gaussian noise (see Corollary 6).
Theorem 5. Let µ ≥ 1 and D a distribution on R. Let Y be the random variable describing the minimum
over µ independent copies of D. Suppose
Pr(Y > D + n) ≥

1
.
2(µ + 1)

Consider optimization of OneMax with reevaluated additive posterior noise from D by (µ + 1)-EA without crossover. Then, for µ bounded from above by a polynomial, the optimum will not be evaluated after
polynomially many iterations w.h.p.
Proof. For all t and all i ≤ n let Xit be the random variable describing the proportion of individuals in the
population of iteration t with exactly i 1s. Let c = 800, b = 20, a = (c − 1)/c and a′ = (c − 2)/c. We show
by induction on t that
∀t, ∀i ≥ an : E[Xit ] ≤ ban−i .

In other words, the expected number of individuals with i 1s is decaying exponentially with i after an. This
will give the desired result with a simple union bound over polynomially many time steps.
The claim holds at the start of the algorithm with an application of Hoeffding’s Inequality for the number
of 1s in a random individual. Fix some value t and suppose the claim holds for that t. Let some value i ≥ an
be given and let x = ban−i . We will now show E[Xit+1 ] ≤ x by considering one generation of the (µ + 1)-EA
without crossover.
We distinguish four cases depending on whether an individual with less than a′ n 1s has been selected for
reproduction, with i − k 1s for some k with 1 ≤ k ≤ n/c, with exactly i 1s or with strictly more than i 1s.
For each of these cases we estimate the number of individuals that can be chosen to reproduce, as well as
the probability for such an individual to produce an offspring with exactly i 1s. The following table gives
upper bounds for both values in all four cases; we will justify all these values below.
′

<an
=i−k
=i
>i

Proportion
1
xbk
x
x/(b − 1)

Probability
2−Ω(n ln n)
(2/c)k
1/e + 1/(c − 1)
1

Clearly the proportion of individuals with < a′ n 1s is bounded from above by 1; for such an individual
with m 0s, at least half of these 0s need to flip, which has a probability of at most 2m /nm/2 = 2−Ω(n ln n) ,
using m ≥ n/c. For any k < n/c, we get a bound of xbk for the number of individuals with exactly i − k 1s
from the induction hypothesis; as these individuals have at most 2n/c many 0s, the probability of flipping
at least k of these to 1 is ≤ (2/c)k . For an individual with exactly i 1s to create an offspring with exactly i
1s, we can either not flip any bit (with a probability tending to 1/e) or we flip as many 1s as 0s; flipping k
1s has a probability of at most 1/c (as i ≥ an), thus we can bound the probability of creating an offspring
with exactly i 1s by
∞
X
c−k = 1/e + 1/(c − 1).
1/e +
k=1

5

With a similar geometric sum we get that the number of individuals with > i 1s is, using the induction
hypothesis, at most x/(b − 1).
From the table we can now deduce that the probability of producing an offspring with exactly i 1s in
iteration t is at most
k !
∞ 
X
1
1
1
2b
2−O(n ln n) + x
+
+
+
e c−1 b−1
c
k=1

−n/c

Using x ≥ b
we see that 2
choice of b and c, we have

−O(n ln n)

has asymptotically no impact on the sum. Furthermore, from our

1
1
1
1
+
+
+
< 1/2.
e c − 1 b − 1 c/(2b) − 1

Thus, we have that we get less than x/2 individuals with exactly i 1s in expectation, while the premise of
the theorem gives that any individual has a probability of at least 1/2 to die in any given iteration. This
shows that E[Xit+1 ] cannot go above x.
We apply Theorem 5 to show that large noise levels make it impossible for the (µ + 1)-EA to efficiently
optimize.
Corollary 6. Consider optimization of om[σ2 ] by (µ + 1)-EA without crossover. Suppose σ 2 ≥ n3 and µ
bounded from above by a polynomial in n. Then the optimum will not be evaluated after polynomially many
iterations w.h.p.
Proof. We set up to use Theorem 5. Let D ∼ N (0, σ 2 ) and let Y be the minimum over µ independent
copies of D. We want to bound Pr(Y > D + n). To that end we let t1 < 0 and t1 < t0 be such that
Pr(D < t0 ) = 0.75/µ and Pr(D < t1 ) = 1.5/µ. Let A be the event that Y > t1 and t0 − n < D < t1 − n and
let B be the event that Y > t0 and D < t0 − n. Clearly, the events A and B are disjoint and are contained
in the event that Y > D + n. From the asymptotic bounds stated in Proposition 2 and the lower bound
on σ 2 we see that t0 − n ≥ t0 (1 + n−0.5 ); similarly, t0 (1 + n−0.5 ) ≤ t1 − n ≤ t0 (1 − n−0.5 ). This gives that
Pr(D < t0 − n) and Pr(t0 − n < D < t1 − n) are both asymptotically 0.75/µ, as they would be without the
“−n”-terms; this uses the bound on µ. Thus, we have asymptotically
Pr(Y > D + n) ≥ Pr(A) + Pr(B)

µ

µ
1.5
0.75
0.75
0.75
1−
1−
+
≥
µ
µ
µ
µ
1
≥
.
2(µ + 1)
The last step uses the bound 1 − x > exp(−x/(1 − x)).

3.2

Compact GA

Let T ⋆ be the optimization time of the cGA on om[σ2 ] , namely, the first P
time that it generates the underlying
n
“true” optimal solution 1n . We consider the stochastic process Xt = n− i=1 pi,t and bound the optimization
⋆
time by T = inf{t > 0 : Xt = 0}. Clearly T ≤ T since the cGA produces 1n in the T -th iteration almost
surely. However, T ⋆ and T can be infinite when there is a t < T ⋆ where pi,t = 0 since the process can never
subsequently generate any string x with xi = 1. To circumvent this, Droste [9] estimates E(T ⋆ ) conditioned
on the event that T ⋆ is finite, and then bounds the probability of finite T ⋆ . In this paper, we will prove that
as long as K is large enough, the optimization time is finite (indeed, polynomial) with high probability.
The following lemma is due to von Bahr and Esseen [32] and states an exact equality for the first absolute
moment of a random variable Z in terms of its characteristic function ϕZ (t) = E(eitZ ).

6

Lemma 7 (special case of Lemma 2 of [32]). Let Z be a random variable with E(|Z|) < ∞. Then
Z
1 ∞
E(|Z|) =
(1 − R(ϕZ (t))) /t2 dt,
π −∞
where R(z) is the real part of z ∈ C.
Lemma 8. Let 0 < a < 1 be a constant.
independent,


1
Zi = −1


0

Consider a random variable Z = Z1 + Z2 + · · · + Zn , each Zi

with probability pi (1 − pi ),
with probability pi (1 − pi ),
with probability 1 − 2pi (1 − pi );
√
with a ≤ pi ≤ 1 for every i ∈ {1, . . . , n}. Then Pr(Z = 0) ≥ 1/(4 n), and
!
n
X
p
pi .
E(|Z|) ≥ a 2/n n −
i=1

Proof. Let ξ = |Z1 | + |Z2 | + · · · + |Zn |. Then ξ is distributed as a Poisson-Binomial distribution with each
success probability equal to 2pi (1 − pi ) and
Pr(Z = 0) =

n
X

k=0



k
Pr(ξ = k)
2−k
k/2

k
k/2



= 0 if k ≡ 1 (mod 2). This is the joint probability that exactly k of the Zi variables are nonzero,

k
and exactly half of these are selected to be negative, the other half positive. Since k/2
vanishes at odd i,
we can write
 
⌊n/2⌋
X
2k −2k
Pr(Z = 0) =
Pr(ξ = 2k)
2
.
k

where

k=0

2k


2k

is the k-th central binomial coefficient, for which we have the well-known bound √2 4k ≤
write
⌊n/2⌋
X
1
1
Pr(Z = 0) ≥ Pr(ξ = 0) +
Pr(ξ = 2k) √ ≥ √ Pr(ξ is even),
2 n
2
k
k=1
k

2k
k


, so we can
(1)

1
since 2√1 n ≤ 2√
≤ 1. To finish the proof, note that for any integer random variable X, Pr(X is even) =
k
(1 + G(−1))/2, where G(z) = E(z X ) is the probability generating
function for X. For a Poisson-Binomial
Q
distribution with success probabilities q1 , q2 , . . . , qn , G(z) = ni=1 (1 − qi + qi z), so,
!
n
Y
1
(1 − 2qi ) .
1+
Pr(ξ is even) =
2
i=1

Finally, since qi = 2pi (1 − pi ) ≤ 1/2 for all i ∈ {1, . . . , n}, Pr(ξ is even) ≥ 1/2 and the claimed bound on
Pr(Z = 0) follows from (1).
We now bound the first absolute moment of Z from below. For every S ⊆ [n], denote as ES the event
that |Zi | = 1 ⇐⇒ i ∈ S. We first calculate the expectation of |Z| conditioned on these events. Since the

7

probabilities pi are independent,
E(eitZ | ES ) =
E(eitZ | ES ) =
=

n
Y

E(eitZj | ES )

j=1
n 
Y
j=1

Y

[j ∈ S]



eit
e−it
+
2
2



+ [j 6∈ S]



cos t = (cos t)|S|

j∈S

where [P ] is the Iverson bracket. So by Lemma 7,
Z
1 ∞ 1 − (cos t)|S|
E(|Z| | ES ) =
dt = g(|S|),
π −∞
t2
 −2⌈k/2⌉
where g(k) = 2⌈k/2⌉ 2⌈k/2⌉
2
. Again applying bounds on the central binomial coefficient, g(k) ≥
⌈k/2⌉
p
p
⌈k/2⌉ ≥ k/2. By the law of total expectation,
E(|Z|) =

n
X

k=1

g(k)

n
X
√
1 X
Pr(ES ) = E(ξ)/ 2n,
k
Pr(ES ) ≥ √
2n k=1 S⊆[n] : |S|=k
S⊆[n] : |S|=k

X

(2)

Since ξ follows a Poisson-Binomial distribution with the i-th success probability equal to 2pi (1 − pi ), and
every pi ≥ a,
!
n
n
X
X
pi .
2pi (1 − pi ) ≥ 2a n −
E(ξ) =
i=1

i=1

Substituting this inequality into (2) completes the proof.

Lemma 9. Consider the cGA optimizing om[σ2 ] and let Xt be the stochastic process defined above. Assume that there exists a constant a > 0 such √
that
 pi,t ≥ a for all i ∈ {1, . . . , n} and that Xt > 0, then
E (Xt − Xt+1 | Xt ) ≥ δXt where 1/δ = O σ 2 K n .
Proof. Let x and y be the offspring generated in iteration t and Zt = kxk1 − kyk1. Then Zt = Z1,t + · · ·+ Zn,t
where


−1 if xi = 0 and yi = 1,
Zi,t = 0
if xi = yi ,


1
if xi = 1 and yi = 0;

Let E denote the event that in line 8, the evaluation of om[σ2 ] correctly ranks x and y. Without loss of
generality, suppose kxk1 ≥ kyk1 . Then E(Xt+1 − Xt | Xt , E) = E(|Zt |)/K. On the other hand, if om[σ2 ] (x)
evaluates to at most om[σ2 ] (y) during iteration t, the roles above are swapped and E(Xt+1 − Xt | Xt ∧ E) =
−E(|Zt |)/K. By the law of total expectation,
E(Xt − Xt+1 | Xt ) =


E(|Zt |)
1 − 2 Pr(E) .
K

(3)

For any i ∈ [n], Pr(Zi,t = 1) = Pr(Zi,t = −1) = pi,t (1 − pi,t ) and Pr(Zi,t = 0) is the inverse. Since we have
assumed each pi,t ≥ a, we can apply Lemma 8 to obtain
!
n
X
p
p
pi,t = aXt 2/n.
E(|Zt |) ≥ a 2/n n −
(4)
i=1

To complete the proof, we substitute the inequality in Equation (4) into Equation (3) and use Lemma 4 to
bound Pr(E) = Φ(|kxk1 − kyk1 |) from above.
8

2
Lemma 10. Consider the cGA optimizing om[σ2√
] with σ > 0. Let 0 < a < 1/2 be an arbitrary constant and
′
2
T = min{t ≥ 0 : ∃i ∈ [n], pi,t ≤ a}. If K = ω(σ n log n), then for every polynomial poly(n), n sufficiently
large, Pr(T ′ < poly(n)) is superpolynomially small.

Proof. Let i ∈ [n] be arbitrary. Let {Yt : t > 0} be the stochastic process Yt = (1/2 − pi,t ) K. We first argue
that
Pr(xi 6= yi )
√
E(Yt | Y1 , . . . , Yt−1 ) ≤ Yt−1 − Ω(σ −2 )
.
(⋆)
n
Let x and y be the strings generated in iteration t of the cGA (lines 4 and 6 of Algorithm 3). We define
x̂ = (x1 , x2 , . . . , xi−1 , xi+1 , . . . xn ) to be the substring of x constructed by removing the i-th element and ŷ
similarly. Since each element of x and y is constructed independently, we can regard x̂, ŷ, xi , and yi to be
independent.
Note that E(Yt | Y1 , . . . , Yt−1 ) = Yt−1 + δt where δt ∈ {−1, 0, 1}. Define ℓ̂ = kx̂k1 − kŷk1 . We distinguish
between the two events that |ℓ̂| is nonzero or zero.
Case |ℓ̂| > 0. Suppose without loss of generality that ℓ̂ > 0 (i.e., kx̂k1 > kŷk1 ). So, δt = 0 if and only if
xi = yi . Moreover, δt = −1 only in the event that (a) xi = 1 and yi = 0 and x is accepted (in which case
ℓ = ℓ̂ + 1), or (b) xi = 0 and yi = 1 and x is not accepted (in which case ℓ = ℓ̂ − 1). Event (a) occurs only if
2
om[σ2 ] does not misclassify x andy, whereas event
 (b) occurs only if om[σ ] does misclassify x and y. Thus,
Pr(δt = −1) = Pr(xi = 1, yi = 0) 1 − Φ(ℓ̂ + 1) + Pr(xi = 0, yi = 1)Φ(ℓ̂ − 1).

Similarly, δt = 1 only in the event that (a) xi = 1 and yi = 0 but x is not accepted because x and y
were misclassified by om[σ2 ] , or (b) xi = 0 and yi = 1 and x is accepted because om[σ2 ] ranked x and
y correctly. Thus, Pr(δt = 1) = Pr(xi = 1, yi = 0)Φ(ℓ̂ + 1) + Pr(xi = 0, yi = 1)(1 − Φ(ℓ̂ − 1)). Since
Pr(xi = 1, yi = 0) = Pr(xi = 0, yi = 1) = Pr(xi 6= yi )/2,


E(δt ) = P r(δt = 1) − Pr(δt = −1) = − Pr(xi 6= yi ) Φ(ℓ̂ − 1) − Φ(ℓ̂ + 1) < 0,
where we apply Lemma 4. We conclude that in this case,

E(Yt | ℓ̂ 6= 0, Y1 , . . . , Yt−1 ) = Yt−1 + E(δt ) < Yt−1 .
Case ℓ̂ = 0. In this case, if xi = yi , then x = y and there is zero drift. Otherwise, xi > yi and so kxk1 −kyk1 =
1, or yi > xi and kyk1 − kxk1 = 1. The drift in this case only depends on whether or not om[σ2 ] misclassifies
x and y. In particular, Pr(δt = −1) = Pr(xi = 1, yi = 0)(1 − Φ(1)) + Pr(xi = 0, yi = 1)(1 − Φ(1)), and
Pr(δt = 1) = Pr(xi = 1, yi = 0)Φ(1) + Pr(x1 = 0, yi = 1)Φ(1). By Lemma 4,
E(δt ) = Pr(δt = 1) − Pr(δt = −1)
= − Pr(xi 6= yi )(1 − 2Φ(1))

≤ −Ω(σ −2 ) Pr(xi 6= yi ).

For this case, E(Yt | ℓ̂ = 0, Y1 , . . . , Yt−1 ) = Yt−1 + E(δt ) ≤ Yt−1 − Ω(σ −2 ) Pr(xi 6= yi ).
Applying the law of total expectation, E(Yt | Y1 , . . . , Yt−1 ) is bounded above by
Yt − Ω(σ −2 ) Pr(xi 6= yi ) Pr(ℓ̂ = 0).
It remains to bound Pr(ℓ̂ = 0) = Pr(kx̂k1 = kŷk1 ).


+1
Zj = 0


−1

9

We define a random variable Z = Z2 + · · · + Zn where
if xj > yj ,
if xj = yj ,
if xj < yj .

√
So Pr(kx̂k1 = kŷk1 ) = Pr(Z = 0) ≥ 1/(4 n − 1) by Lemma 8 since 0 ≤ Pr(xj > yj ) = Pr(xj < yj ) =
pj (1 − pj ) ≤ 1/2 for all j ∈ {2, . . . , n}, proving the claim in (⋆).
Note that {Yt : t ∈ N} is a Markov chain on {−K/2, −K/2 + 1, . . . , K/2 − 1, K/2} with Y1 = 0. Let
T = min{t : Yt > (1/2 − a)K}. In any iteration, if xi = yi , then Yt = Yt−1 . Thus, for an estimate of the
upper bounds of T , we can ignore self-loops in the chain.
More formally, let {Ŷt : t ∈ N} be the restriction of Yt to iterations such that Yt 6= Yt−1 . Similarly, let
T̂ = min{t : Ŷt > (1/2 − a)K}. The random variable T stochastically dominates the random variable T̂ since
removing equal moves can only make the process hit faster, i.e., ∀t ∈ N, Pr(T > t) ≥ Pr(T̂ > t). Due to the
above arguments,
E(Ŷt | Ŷ1 , . . . , Ŷt−1 ) = E(Ŷt | xi 6= yi , Ŷ1 , . . . , Ŷt−1 )
= Ŷt − E(δt | xi 6= yi )
√
≤ Ŷt − Ω(σ −2 / n.

By a refinement to the negative drift
√ theorem of Oliveto and Witt [25, 24] (cf Theorem 3 of [18]), since
Y1 = Ŷ1 = 0 and |Ŷt − Ŷt+1 | = 1 < 2, for all s ≥ 0,


(1/2 − a)K|ǫ|
Pr(T ≤ s) ≤ Pr(T̂ ≤ s) ≤ s exp −
,
32
√
√
with ǫ = −Ω(σ −2 / n). Since K = ω(σ 2 n log n), Pr(T ≤ s) = sn−ω(1) .
So, for any polynomial s = poly(n), with probability superpolynomially close to one, Ys has not yet
reached a state larger than (1/2 − a)K, and so pi,t > a for all 1 ≤ t ≤ s. As this holds for arbitrary i,
applying a union bound retains a superpolynomially small probability that any of the n frequencies have
gone below a by s = poly(n) steps.
Theorem √
11. Consider the cGA optimizing om[σ2 ] with variance σ 2 > 0 for any constant √
c ≥ 0. If
2
K = ω(σ n log n), then with probability 1 − o(1), the cGA finds the optimum after O(Kσ 2 n log Kn)
steps.
Proof. We will consider the P
drift of the stochastic process {Xt : t ∈ N} over the state space S ⊆ {0} ∪
n
[xmin , xmax ] where Xt = n − i=1 pi,t . Hence, xmin = 1/K.
Fix a constant 0 < a < 1/2. We say the process has failed by time t if there exists some s ≤ t
and some i ∈ [n] such that pi,s ≤ a. Let T = min{t ∈ N : Xt = 0}. Assuming the process never fails,
by Lemma 9, √the drift of {Xt : t ∈ N} in each step is bounded by E (Xt − Xt+1 | Xt = s) ≥ δXt where
1/δ = O σ 2 K n . Hence, by tail bounds for the multiplicative drift theorem (see Doerr and Goldberg [7]),
−r
Pr (T ≥ (ln(X
√ 1 /xmin ) + r) /δ) ≤ e . Choosing r = d ln n for any constant d > 0, the probability that
T = Ω(Kσ 2 n log Kn) is at most n−d .
√
Letting E be the event that the process has not failed by√O(Kσ 2 n log Kn) steps, by the law of total
probability, the hitting time of Xt = 0 is bounded by O(Kσ 2 n log Kn) with probability (1 − n−d ) Pr(E) =
1 − o(1) where we can apply Lemma 10 to bound the probability of E.

4

Experiments

In Section 3 we proved that the cGA scales gracefully with noise (see Def. 1) on a simple noisy pseudoBoolean function, whereas a mutation-only EA fails when the noise variance is too high. In this section,
we seek to compare the performance of the cGA with a baseline hillclimber that uses explicit resampling to
reduce the noise variance.
Our baseline hillclimber is called resampling randomized local search (reRLS). For a particular variance
σ 2 , reRLS estimates the true objective function value by performing O(σ 2 log n) function calls for each search
point [31]. It then hillclimbs on the estimated true objective function by flipping a single bit in each iteration
and accepting points with equal or better estimated objectives. Both reRLS and the cGA require knowledge
10

of the true noise variance to collect enough samples (reRLS) or to set K properly (cGA). We also investigate
the performance of these approaches in the corresponding noise oblivious setting as defined in Section 2.1.
(NO-reRLS and NO-cGA).
We measure the performance of each procedure by the number of calls to the objective function until the
true optimum 1n is generated. This performance metric is standard in the field of evolutionary computation
because typically objective function evaluation is the most costly operation in terms of computation time.
For the cGA, this is twice the number of iterations through the while loop in Algorithm 3. For reRLS, this
is the number of iteration times the number of resamples necessary to obtain a suitable estimate of the true
objective function value.
The performance of each algorithm is plotted fixing n = 100 and controlling the variance in Figure 1.
For each procedure and variance value we run each algorithm 100 times until the true optimum is found
and collect the number of calls to the objective function for each run. The median run times and
√ their
interquartile ranges are plotted. We also plot the performance as a function of n (fixing σ 2 = n) in
Figure 2. Both results are plotted on log-log plots; Thus the cGA variants are an order of magnitude faster
than the baseline.
Figures 4 and 3 correspond to figures 2 and 1, respectively, and depict the number of re-evaluations
((NO-)reRLS) per iteration or the value of K ((NO-)cGA) that was sufficient for the respective algorithm to
succeed. Note that the functions for the non-noise-oblivious algorithms have deterministic function values
whereas the ones for the noise-oblivious versions are random variables.

5

Conclusions

In this paper we have examined the benefit of sexual recombination in evolutionary optimization in an
uncertain environment. We introduce the concept of an algorithm scaling gracefully with noise. We rigorously
proved that mutation-only evolutionary algorithms do not scale gracefully in the sense that they cannot
optimize noisy functions in polynomial time when the noise intensity is sufficiently high. On the other hand,
we proved that a simple estimation of distribution algorithm that uses gene pool recombination can always
optimize noisy OneMax (om[σ2 ] ) in polynomial time, subject only to the condition that the noise variance
σ 2 is bounded by some polynomial in n.
A common way to handle noisy objective functions is to modify the optimization algorithm to perform
resampling in order to estimate the true value of the underlying objective function. We have also presented
empirical results that show the sexual recombination algorithm optimizes om[σ2 ] an order of magnitude
faster than a resampling hillclimber. Our results highlight the importance of understanding the influence
of different search operators in uncertain environments, and suggest that algorithms such as the compact
genetic algorithm that use sexual recombination are able to scale gracefully with noise.

11

σ2 =

√
n

109

number of evaluations of f

108

107

106

105

104
reRLS
NO-reRLS
cGA
NO-cGA

103
100

101

102

103

104

σ2
Figure 1: Median run time as a function of noise variance for n = 100, 100 runs at each point. Shaded area
denotes IQR.

12

n = 100
10

9

108

number of evaluations of f

107

106

105

104

103

102

101

reRLS
NO-reRLS
cGA
NO-cGA

100
100

101

102
n

Figure 2: Median run time as a function of n for σ 2 =
IQR.

13

103

√
n, 100 runs at each point. Shaded area denotes

σ2 =

√
n

number of re-evaluations per iteration or K

106

105

104

103

102

reRLS
NO-reRLS
cGA
NO-cGA
100

101

102

103

104

σ2
Figure 3: Median of number of re-evaluations per iteration or median of K as a function of noise variance
for n = 100, 100 runs at each point. Shaded area denotes IQR.

14

n = 100

number of re-evaluations per iteration or K

104

103

102

101

reRLS
NO-reRLS
cGA
NO-cGA

100

100

101

102
n

103

Figure 4: Median of number of re-evaluations per iteration or median of K as a function of n for σ 2 =
100 runs at each point. Shaded area denotes IQR.

15

√
n,

References
[1] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a metaalgorithm and applications. Theory of Computing, 8(1):121–164, 2012.
[2] Thomas Bäck, David B. Fogel, and Zbigniew Michalewicz, editors. Handbook of Evolutionary Computation. IOP Publishing Ltd., 1st edition, 1997.
[3] Nicholas H. Barton, Sebastian Novak, and Tiago Paixo. Diverse forms of selection in evolution and
computer science. Proceedings of the National Academy of Sciences, 111(29):10398–10399, July 2014.
[4] L. Bianchi, M. Dorigo, L. Gambardella, and W. Gutjahr. A Survey on Metaheuristics for Stochastic
Combinatorial optimization. Natural Computing, 8:239–287, 2009.
[5] Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. Algorithms, games, and
evolution. Proceedings of the National Academy of Sciences, 111(29):10620–10623, July 2014.
[6] B. Doerr, A. Hota, and T. Kötzing. Ants Easily Solve Stochastic Shortest Path Problems. In Proc. of
GECCO’12, pages 17–24, 2012.
[7] Benjamin Doerr and Leslie Ann Goldberg. Adaptive drift analysis. Algorithmica, 65(1):224–250, 2013.
[8] Benjamin Doerr, Edda Happ, and Christian Klein. Crossover can provably be useful in evolutionary
computation. Theor. Comput. Sci., 425:17–33, 2012.
[9] Stefan Droste. A rigorous analysis of the compact genetic algorithm for linear functions. Natural
Computing, 5(3):257–283, August 2006.
[10] Agoston E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2003.
[11] Matthias Feldmann and Timo Kötzing. Optimizing Expected Path Lengths with Ant Colony Optimization Using Fitness Proportional Update. In Proc. of FOGA’13, pages 65–74, 2013.
[12] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. AddisonWesley, 1989.
[13] W. Gutjahr and G. Pflug. Simulated Annealing for Noisy Cost Functions. Journal of Global Optimization, 8:1–13, 1996.
[14] Georges R. Harik, Fernando G. Lobo, and David E. Goldberg. The compact genetic algorithm. IEEE
Trans. on Evol. Comp., 3(4):287–297, 1999.
[15] Thomas Jansen and Ingo Wegener. The analysis of evolutionary algorithms – a proof that crossover
really can help. Algorithmica, 34(1):47–66, 2002.
[16] Thomas Jansen and Ingo Wegener. Real royal road functions—where crossover provably is essential.
Discrete Appl. Math., 149:111–125, 2005.
[17] Yaochu Jin and Jürgen Branke. Evolutionary optimization in uncertain environments—a survey. IEEE
Trans. on Evol. Comp., 9:303–317, 2005.
[18] Timo Kötzing. Concentration of first hitting times under additive drift. In Proc. of GECCO’14, pages
1391–1397, 2014.
[19] Timo Kötzing, Dirk Sudholt, and Madeleine Theile. How crossover helps in pseudo-boolean optimization.
In Proc. of GECCO ’11, pages 989–996, 2011.
[20] Heinz Mühlenbein and Gerhard Paaß. From recombination of genes to the estimation of distributions
I. Binary parameters. In Proc. of PPSN IV, pages 178–187. Springer-Verlag, 1996.
16

[21] Heinz Mühlenbein and Hans-Michael Voigt. Gene pool recombination in genetic algorithms. In MetaHeuristics, pages 53–62. Springer US, 1996.
[22] F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization – Algorithms and
Their Computational Complexity. Springer, 2010.
[23] Frank Neumann, Pietro S. Oliveto, Günter Rudolph, and Dirk Sudholt. On the effectiveness of crossover
for migration in parallel evolutionary algorithms. In Proc. of GECCO’11, pages 1587–1594, 2011.
[24] P. S. Oliveto and C. Witt. Erratum: Simplified drift analysis for proving lower bounds in evolutionary
computation. ArXiv e-prints, 2012.
[25] Pietro S. Oliveto and Carsten Witt. Simplified drift analysis for proving lower bounds in evolutionary
computation. Algorithmica, 59(3):369–386, 2011.
[26] Adam Prügel-Bennett. Benefits of a Population: Five Mechanisms That Advantage Population-Based
Algorithms. IEEE Trans. on Evol. Comp., 14:500–517, 2010.
[27] J. Neal Richter, Alden Wright, and John Paxton. Ignoble trails - where crossover is provably harmful.
In Proc. of PPSN ’08, pages 92–101, 2008.
[28] Tobias Storch and Ingo Wegener. Real royal road functions for constant population size. Theor. Comput.
Sci., 320:123–134, 2004.
[29] D. Sudholt and C. Thyssen. A Simple Ant Colony Optimizer for Stochastic Shortest Path problems.
Algorithmica, 64:643–672, 2012.
[30] Dirk Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO ’05,
pages 1161–1167, 2005.
[31] Olivier Teytaud. Private communication, 2015.
[32] Bengt von Bahr and Carl-Gustav Esseen. Inequalities for the r-th absolute moment of a sum of random
variables, 1 ≤ r ≤ 2. The Annals of Mathematical Statistics, 36(1):299–303, 1965.
[33] Richard A. Watson and Thomas Jansen. A building-block royal road where crossover is provably
essential. In Proc. of GECCO ’07, pages 1452–1459, 2007.
[34] Eric W Weisstein.
Erfc, 2015.
http://mathworld.wolfram.com/Erfc.html.

From

17

MathWorld–A

Wolfram

Web

Resource.

