arXiv:1704.04366v1 [] 14 Apr 2017

Runtime Analysis
of the (1 + (λ, λ)) Genetic Algorithm
on Random Satisfiable 3-CNF Formulas∗
Maxim Buzdalov

Benjamin Doerr

April 17, 2017

Abstract
The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013,
showed a surprisingly good performance on so me optimization problems. The theoretical analysis so far was restricted to the OneMax
test function, where this GA profited from the perfect fitness-distance
correlation. In this work, we conduct a rigorous runtime analysis of
this GA on random 3-SAT instances in the planted solution model
having at least logarithmic average degree, which are known to have
a weaker fitness distance correlation.
We prove that this GA with fixed not too large population size
again obtains runtimes better than Θ(n log n), which is a lower bound
for most evolutionary algorithms on pseudo-Boolean problems with
unique optimum. However, the self-adjusting version of the GA risks
reaching population sizes at which the intermediate selection of the
GA, due to the weaker fitness-distance correlation, is not able to distinguish a profitable offspring from others. We show that this problem
can be overcome by equipping the self-adjusting GA with an upper
limit for the population size. Apart from sparse instances, this limit
can be chosen in a way that the asymptotic performance does not
worsen compared to the idealistic OneMax case. Overall, this work
shows that the (1 + (λ, λ)) GA can provably have a good performance
on combinatorial search and optimization problems also in the presence of a weaker fitness-distance correlation.
∗

An extended abstract of this report will appear in the proceedings of the 2017 Genetic
and Evolutionary Computation Conference (GECCO 2017).

1

1

Introduction

The (1 + (λ, λ)) genetic algorithm (GA) was fairly recently introduced by
Doerr, Doerr, and Ebel [8]. It builds on the simple idea to first generate
from a single parent individual several offspring via standard-bit mutation
with higher-than-usual mutation rate, to select the best of these, and to
perform a biased crossover with the parent to reduce the destructive effects
of the high mutation rate. This use of crossover with the parent as repair
mechanism is novel in evolutionary discrete optimization.
The so far moderate number of results on this GA show that it has some
remarkable properties. A mathematical runtime analysis on the OneMax
test function class [4, 5, 7, 9] shows that the right√parameter setting leads to
an optimization time of slightly better than O(n log n). This is remarkable
as all previous runtime analyses of evolutionary algorithms on the OneMax
test function class showed that these algorithms needed at least Ω(n log n)
fitness evaluations. The result is remarkable also in that it is the first time
that crossover was rigorously shown to give an asymptotic runtime improvement for a simple test function. A third noteworthy property of this GA is
that a simple self-adjusting choice of the offspring population size λ inspired
by the 1/5-th rule from continuous optimization could further improve the
runtime to Θ(n). Again, this is the first time that a 1/5-th rule type dynamic
parameter choice could be proven useful in discrete evolutionary optimization. These mathematical analyses are complemented by an experimental
investigation on the OneMax test function, on linear functions with random weights, and on royal road functions. Further, Goldman and Punch [11]
in the analysis of their parameter-less population pyramid algorithm also
used the (1 + (λ, λ)) GA as comparison, and it performed well on random
MAX-SAT instances.
It is clear that the intermediate selection of the best mutation offspring
becomes most effective if there is a strong fitness-distance correlation. The
OneMax function, by definition, has a perfect fitness-distance correlation.
So the question has to be asked to what degree the positive results for OneMax remain true in optimization problems with a weaker fitness distance
correlation. To study this question, we analyze the performance of the
(1 + (λ, λ)) GA on random satisfiable 3-SAT instances in the planted solution model. For these, the fitness-distance correlation can be scaled via
the instance density. In works [10,15], the analysis of the performance of the
(1 + 1) EA on these instances has shown that when the clause-variable ratio
is m/n = Ω(n), then the following strong fitness-distance correlation holds
apart from an exponentially small failure probability: For any two search
points x, y which are least half as good as a random search point and such
2

that they differ in one bit, the fitness and the distance are perfectly correlated in that the one closer to the optimum has a fitness larger by Θ(m/n).
From this, one could easily derive an O(n log n) optimization time of the
(1 + 1) EA. However, when the clause-variable ratio is only logarithmic, this
strong fitness-distance correlation is far from being satisfied. Therefore, only
the much weaker condition could be shown that each pair (x, y) as above
shows a Θ(m/n) fitness advantage of the closer search point with probability 1 − n3 . This was enough to show that with high probability (over the
joint probability space of instance and algorithm) the (1 + 1) EA finds the
optimum in O(n log n) iterations.
Our results: We conduct a rigorous runtime analysis of the (1+(λ, λ)) GA
(with mutation rate p = λ/n and crossover bias c = 1/λ linked to the population size λ as recommended in [4]), on the same type of random 3-SAT
instance (see Section 2 for the details) as regarded in [10,15]. We observe that
the weaker fitness-distance correlation of low-density instance indeed poses a
problem for the (1 + (λ, λ)) GA when the population size (and thus the mutation rate) is high. In this case, the mutation offspring are distant enough
so that the weak fitness-distance correlation prevents the (1 + (λ, λ)) GA to
detect an individual closer to the optimum than the typical offspring. For
the (1 + (λ, λ)) GA with static value of λ, our experiments and informal
considerations suggest that in this case the (1 + (λ, λ)) GA, for large enough
n, reverts to the behavior similar to the (1 + 1) EA, however, the constant in
O(n log n) is proportional to 1/λ, just like it happens for OneMax. Things
are worse when the self-adaptive version of the (1 + (λ, λ)) GA is used. In
this case, the low probability to find an improving solution lets the value
of λ further increase as governed by the 1/5-th rule parameter adaptation.
Consequently, the probability to select a profitable individual out of the mutation offspring population further decreases and this negative effect becomes
stronger. The result is that λ quickly reaches the allowed maximum of n and
the performance approaches the one of the (1 + 1) EA with the cost of one
iteration n times higher than usual.
On the positive side, we make precise that these negative effect can be
overcome in most cases by an appropriate choice of λ. We show that when
λ is asymptotically smaller that the fourth root of the density, then the
probability to find an improving solution is asymptotically the same as for
the optimization of OneMax.
Consequently, when the density is ω(log2 n),
√
an expected optimization time
then we can still use λ = log n and obtain
√
(number of fitness evaluations) of O(n log n). Note that in this work, we
do not try to p
achieve the later improvement of this runtime guarantee [7]
by a factor Θ( log log log n/ log log n) though we are optimistic that such a
guarantee can be shown with mildly more effort. For a logarithmic instance
3

density, the smallest regarded here and in [10,15], for any ε > 0 with a choice
of λ = log0.25−ε n we still obtain a runtime of O(n log0.75+ε n) and beat the
O(n log n) performance the (1 + 1) EA has on these instances.
For the self-adjusting version, √
where a typical run of the (1+(λ, λ)) GA on
OneMax uses λ-values of up to n, we show that adding an upper limit up
to which the value of λ can at most grow, overcomes this difficulties sketched
above. The runtime increase incurred by such a limit is again manageable. If
the upper limit is λ and it depends on the instance density as λ = o((m/n)4 ),
then the runtime of the self-adjusting (1 + (λ, λ)) GA is



log n
.
O n · max 1,
λ
Hence already for densities asymptotically larger than log4 n, we obtain
the linear runtime that is valid for the ideal OneMax fitness landscape for
densities at least logarithmic.
Techniques employed: Our main result that λ = o((m/n)1/4 ) suffices
for the well-functioning of the (1+(λ, λ)) GA on our random 3-SAT instances
of density m/n is based on a different fitness-distance correlation result than
those used in [10, 15]. Whereas the latter require that with good probability
all neighbors of a given solution (not excessively far from the optimum) have
a fitness advantage or disadvantage of order m/n (depending on whether
they are closer to the optimum or further away), we require this condition
only for a certain fraction of the neighbors. This relaxation will not be a
problem since it only reduces the probability that the (1 + (λ, λ)) GA finds a
certain improvement by a constant factor (being an elitist algorithm, we do
not need to care about fitness losses). On the positive side, this relaxation
(i) allows us to extend the fitness-distance correlation requirement to all
vertices in the λ-neighborhood instead of only all direct neighbors and (ii)
gives us that this correlation property with probability 1 − exp(−Ω(n)) holds
for all vertices (not excessively far from the optimum). Consequently, the
performance results we show hold for all but an exponentially small fraction of
the input instances. This fitness-distance correlation result also implies that
the result of [10] for logarithmic densities holds in the same strong version
as the one for linear densities, namely that on all but an exponentially small
fraction of the input instances the expected runtime is O(n log n).
To prove our fitness-distance correlation result, we use McDiarmid’s bounded
differences version [13] of the Azuma martigale concentration inequality in
a novel way. To reduce the maximum influence of the independent basic
random variables on the discrete quantity of interest, we replace this quantity by a larger continuous function in a way that the influence of each basic
4

random variable is significantly reduced. We are not aware of this type of argument being used before, either in evolutionary computation or randomized
algorithms in general.

2

Preliminaries

In this section, we define the notation, algorithms, and problems we regard
in this work. Our notation is standard. We write [a..b] to denote the set
of all integers in the real interval [a; b]. We write [r] to denote the integer
closest to the real number r, rounding up in case of ties.

2.1

The k-CNF SAT Problem

Consider a set V of n Boolean variables V = {x1 , x2 , . . . , xn }. A clause C
over V is the logical disjunction of exactly k literals, C = l1 ∨ l2 . . . ∨ lk , and
each literal li is either a variable xj or its negation ¬xj . A k-CNF formula F
is a logical conjunction of exactly m clauses F = C1 ∧C2 ∧. . .∧Cm . A k-CNF
formula F is satisfiable if and only if there is an assignment of truth values to
the variables such that every clause contains at least one true literal, i.e., the
whole expression F evaluates to true. We shall only regard the case k = 3,
but we have no doubts that the main claims are true for the general case as
well.
We consider random 3-CNF formulas consisting of m clauses of length
k = 3 over the n variables in V . We take the usual assumption that each
clause consists of distinct variables. This assumption is very natural since
any clause of length 3 that contains repeating variables can be immediately
reduced to an equivalent clause of length 2 or, alternatively, to a tautology.
However, we explicitly allow repeated clauses in F .
Let Ωn,m be the finite set of all 3-CNF formulas over n variables and
m clauses. We work in the so-called planted solution model. Hence there
is a target assignment x∗ and F is a formula chosen uniformly at random
among all formulas in Ωn,m which are satisfied by x∗ . We refer to [10, 15] for
a justification of this model and a discussion how it relates to other random
satisfiability problems.
We shall, without loss of generality, assume that the planted solution is
∗
x = (1, . . . , 1). This is justified by the fact that we only regard unbiased
algorithms, that is, algorithms that treat bit positions and the bit values 0
and 1 symmetrically. Hence these algorithms cannot profit from “knowing”
the optimal solution. A random formula in this model can be constructed by
m times (with replacement) choosing a random clause satisfied by x∗ , that
5

is, a random clause among all clauses containing at least one positive literal.
Note that such a random formula may have other satisfying assignment than
x∗ . Nevertheless, we denote the structural distance, which is the Hamming
distance here, of a solution x to the planted solution x∗ by d(x) = |{i : xi =
0}|. When talking about fitness-distance correlation and related concepts,
we shall always refer to this distance.

2.2

3-CNF and Evolutionary Algorithms

An assignment of true/false values to a set of n Boolean variables can be
represented by a bit string x ∈ {0, 1}n such that xi = 1 if and only if
the i-th variable is having the value true. For a length-m formula F on
n variables, we define the fitness function f = fF : {0, 1}n → [0..m] via
f (x) = |{C ∈ F | C is satisfied by x}|, the number of clauses satisfied by
the assignment represented by x. If F is satisfiable, the task of finding a
satisfying assignment reduces to the task of maximizing f .
In [10], it is proven that when m/n > c ln n for sufficiently large constant
c, the runtime of the (1 + 1) EA is O(n log n) with probability polynomially
close to one. One of the key concepts of the proof is the fitness-distance
correlation. In the case of logarithmic density, this concept can be formulated
as follows:
Lemma 1 (Lemma 4 from [10]). Let 0 < ε < 21 . Assume that m/n > c ln n
for sufficiently large constant c. Then there exist two constants c1 and c2
such that, for any two solutions x1 and x2 such that
• they are different in exactly one bit;
• this bit is set to 1 in x2 ;
• the structural distance d(x1 ) from x1 to the planted solution is at most
(1/2 + ε)n;
we have c1 m/n ≤ f (x2 ) − f (x1 ) ≤ c2 m/n with probability at least 1 − n−3 .

2.3

The (1 + (λ, λ)) Genetic Algorithm

The (1 + (λ, λ)) Genetic Algorithm, or the (1 + (λ, λ)) GA for short, was
proposed by Doerr, Doerr and Ebel in [9]. Its main working principles are (i)
to use mutation with a higher-than-usual mutation rate to speed up exploration and (ii) crossover with the parent to diminish the destructive effects of
this mutation. Two versions of the algorithm were proposed, one with static
parameters and one with a self-adjusting parameter choice.
6

Algorithm 1 : The (1 + (λ, λ)) GA with fixed integer population size λ
1: x ← UniformRandom({0, 1}n )
. Initialization
2: for t ← 1, 2, 3, . . . do
. Optimization
3:
p ← λ/n
. Mutation probability
4:
c ← 1/λ
. Crossover probability
5:
` ∼ B(n, p)
. Mutation strength
6:
for i ∈ [1..λ] do
. Phase 1: Mutation
7:
x(i) ← Mutate(x, `)
8:
end for
9:
x0 ← UniformRandom({x(j) | f (x(j) ) = max{f (x(i) )}})
10:
for i ∈ [1..λ] do
. Phase 2: Crossover
(i)
0
11:
y ← Crossover(x, x , c)
12:
end for
13:
y ← UniformRandom({y (j) | f (y (j) ) = max{f (y (i) )}})
14:
if f (y) ≥ f (x) then
. Selection
15:
x←y
16:
end if
17: end for
The fixed-parameter version is outlined in Algorithm 1. It uses the following two variation operators.
• `-bit mutation: The unary mutation operator Mutate(x, `) creates
from x ∈ {0, 1}n a new bit string y by flipping exactly ` bits chosen
randomly without replacement.
• biased uniform crossover: The binary crossover operator Crossover(x, x0 , c)
with crossover bias c ∈ [0, 1] constructs a new bit string y from two
given bit strings x and x0 by choosing for each i ∈ [1..n] the second
argument’s value (yi = x0i ) with probability c and setting yi = xi otherwise.
The (1 + (λ, λ)) GA has three parameters, the mutation rate p, the
crossover bias c, and the offspring population size λ. After randomly initializing the one-element parent population {x}, in each iteration the following
steps are performed:
• In the mutation phase, λ offspring are sampled from the parent x by
applying λ times independently the mutation operator Mutate(x, `),
where the step size ` is chosen at random from the binomial distribution
B(n, p). Consequently, each offspring has the distribution of standard
7

bit mutation with mutation rate p, but all offspring have the same
Hamming distance from the parent.
• In an intermediate selection step, the mutation offspring with maximal fitness, called mutation winner and denoted by x0 , is determined
(breaking ties randomly).
• In the crossover phase, λ offspring are created from x and x0 using via
the biased uniform crossover Crossover(x, x0 , c).
• Elitist selection. The best of the crossover offspring (breaking ties randomly and ignoring individuals equal to x) replaces x if its fitness is at
least as large as the fitness of x.
Throughout this paper we use the mutation rate p = λ/n and the crossover
bias c = 1/λ as recommended and justified in [9, Sections 2 and 3] and [4, Section 6].
For this (1 + (λ, λ)) GA, a first runtime analysis [9] was conducted on the
OneMax test function
n

OneMax : {0, 1} → Z; x 7→

n
X

xi .

i=1

It was shown that for arbitrary λ, possibly being a function of n, the expected
optimization time (number of fitness evaluations until the optimum is evalun
}). This expression
is minimized
ated for the√first time) is O(max{nλ, n log
λ
√
for λ = Θ( log n), giving an upper bound of O(n log n). The analysis,
on which we will build on in this work, uses the fitness level method [16].
Roughly speaking, the arguments are that in an iteration starting with an
individual x with fitness distances d = d(x) = n − OneMax(x) (i) with
probability Ω(min{1, dλ2 /n}) the mutation winner is less than ` fitness levels
worse than the parent, and that (ii) in this case with constant probability the
crossover winner is better than the parent. Consequently, the expected number of iterations needed to gain an improvement from x is O(max{1, n/dλ2 }).
Summing over all d and noting that one iteration uses 2λ fitness evaluations
gives the claim.
This result is interesting in that this is the first time that crossover was
proven to bring an asymptotic speed-up for a simple fitness landscape like
OneMax. Previously, a constant improvement was shown to be possible
for OneMax using crossover [14]. Note that all mutation-based algorithms
that treat bit positions and bit values symmetrically need at least Ω(n log n)
fitness evaluations, as this is the unary unbiased black-box complexity of
OneMax [12].
8

The (1 + (λ, λ)) GA, which in principle nothing more than a (1 + 1) EA
with a complicated mutation operator, in experiments showed a performance
superior to the one of the classic (1 + 1) EA on OneMax (showing also
that the constants hidden in the asymptotic notation are small), on linear
functions and on royal road functions [9] as well as on maximum satisfiability
instances [11].
Subsequently, the runtime analysis on OneMax was improved [7] and
the tight bound of Θ(max{n log n/λ, nλ p
log log λ/ log λ}) was shown for all
values of λ ≤ n.pThis is minimized to Θ(n log n log log log n/ log log n) when
setting λ = Θ( log n log log n/ log log log n).
Already in [9], it was observed that a dynamic choice of the parameter
λ can reduce the runtime to linear. For this, a fitness dependent choice of
n
e suffices. This seems to be the first time that a superλ = d n−OneMax(x)
constant speed-up was provably obtained by a dynamic parameter choice
(see [2] for a result showing that also the (1+λ) EA can profit from a dynamic
choice offspring population size when optimizing OneMax). Since a fitnessdependent choice as above is unlikely to be guessed by an algorithm user,
also a self-adjusting variant setting λ success-based according to a 1/5-th
rule was proposed in [9]. That this indeed closely tracks the optimal value
of λ and gives a runtime of O(n) was later shown in [5]. The self-adjusting
version of the (1 + (λ, λ)) GA is described in Algorithm 2.
The main idea of the self-adjusting (1 + (λ, λ)) GA is as follows. If
an iteration leads to an increase of the fitness, indicating that progress is
easy, then the value of λ is reduced by a constant factor F > 1. If an
iteration did not produce a fitness improvement, then λ is increased by a
factor of F 1/4 . Consequently, after a series of iterations with an average
success rate of 1/5, the algorithm ends up with the initial value of λ. Needless
to say, λ can never drop below 1 and never rise above n (when using the
recommended mutation rate λ/n). Since we will later regard a self-adaptive
version with different upper limit, we formulated Algorithm 2 already with
the additional parameter λ as upper limit. Hence the self-adaptive (1 +
(λ, λ)) GA as proposed in [9] uses λ = n. We also note that whenever λ
should be interpreted as an integer (e.g. when the population size of the
current iteration needs to be determined), the value λ0 = [λ] rounded to the
closest integer is taken instead.

2.4

Chernoff Bounds and McDiarmid’s Inequalities

In this section we describe the tools from the probability theory which we
use in this paper.
Suppose X1 , . . . , Xn are independent random variables taking values in
9

Algorithm 2 : The (1 + (λ, λ)) GA with self-adjusting λ ≤ λ
1: F ← constant ∈ (1; 2)
. Update strength
2: U ← 5
. The 5 from the “1/5-th rule”
3: x ← UniformRandom({0, 1}n )
4: for t ← 1, 2, 3, . . . do
5:
p ← λ/n, c ← 1/λ, λ0 ← [λ], ` ∼ B(n, p)
6:
for i ∈ [1..λ0 ] do
. Phase 1: Mutation
(i)
7:
x ← Mutate(x, `)
8:
end for
9:
x0 ← UniformRandom({x(j) | f (x(j) ) = max{f (x(i) )}})
10:
for i ∈ [1..λ0 ] do
. Phase 2: Crossover
11:
y (i) ← Crossover(x, x0 , c)
12:
end for
13:
y ← UniformRandom({y (j) | f (y (j) ) = max{f (y (i) )}})
14:
if f (y) > f (x) then
. Selection and Adaptation
15:
x ← y, λ ← max{λ/F, 1}
16:
else if f (y) = f (x) then
17:
x ← y, λ ← min{λF 1/(U −1) , λ}
18:
else
19:
λ ← min{λF 1/(U −1) , λ}
20:
end if
21: end for
{0, 1}. Let X denote their sum, and let µ = E[X] denote the sum’s expected
value. Then, for any δ > 0, the following bounds are known as (simplified
multiplicative) Chernoff bounds.
Pr[X ≥ (1 + δ)µ] ≤ e−

δ2 µ
3

− δµ
3

Pr[X ≥ (1 + δ)µ] ≤ e

Pr[X ≤ (1 − δ)µ] ≤ e−

0 < δ ≤ 1;
1 ≤ δ;

,

δ2 µ
2

,

,

0 < δ < 1.

Suppose now that the Xi may take values in [−1, 1], however, such that
for some κ > 0 we have Pr[Xi = 0] ≥ 1 − κ for all i ∈ [1..n]. For this
situation, we prove the following corollary from the Bernstein’s inequality,
which seems to be rarely used in the theory of evolutionary computation.
Pr[X ≤ µ − δ] ≤ max{exp(−δ 2 /4κn), exp(− 83 δ)}

(1)

Proof. By the assumption that Pr[Xi = 0] ≥ 1 − κ, we have Var[Xi ] ≤ κ and
thus Var[X] ≤ κn. Hence Bernstein’s [3] inequality (see also [1, Theorem
10

1.12ff]) yields
Pr[X ≤ E[X] − δ] ≤ exp(−δ 2 /(2 Var[X] + 43 δ))
≤ exp(−δ 2 /2 max{2 Var[X], 43 δ})
= max{exp(−δ 2 /4κn), exp(− 83 δ)}.
Suppose X1 , . . . , Xn are arbitrary independent random variables, and assume the function f defined over the product of the domains of the Xi satisfies
sup
x1 ,x2 ,...,xn ,x̂i

|f (x1 , . . . , xn ) − f (x1 , . . . , x̂i , . . . , xn )| ≤ ci

for all 1 ≤ i ≤ n. Then, for all δ > 0, the following McDiarmid’s inequalities [13] hold.
2
c2
i=1 i

− Pn2δ

Pr[f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )] ≥ +δ] ≤ e

3

2
c2
i=1 i

− Pn2δ

Pr[f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )] ≤ −δ] ≤ e

;

(2)

.

Almost Like OneMax:
Conditions for the (1 + (λ, λ)) GA
to Behave Well on a Random 3-CNF Formula

In this section, we formulate and prove conditions which are enough for the
(1 + (λ, λ)) GA to have local fitness-distance correlation.
In the Doerr, Neumann and Sutton paper [10], two results were proven.
When the clause density m/n is Ω(n), then a strong fitness distance correlation is exhibited. Apart from an exponentially small failure probability, the
random instance is such that any possible one-bit flip leads to a fitness gain
or loss (depending on whether the distance decreases or not) of Θ(m/n). In
particular, the fitness function is such that there are no misleading one-bit
flips. On such a function, the classic “multiplicative drift with the fitness”
proof for OneMax can be imitated and easily yields an O(n log n) optimization time (in expectation and with high probability) [10, Theorem 2].
For smaller clause densities m/n = Ω(log n), with probability 1 − o(1),
taken over both the random 3-CNF formula and the random decisions of the
optimization process, also an O(n log n) optimization time is observed [10,
Theorem 3]. The difference to the previous setting is that now there may
11

be misleading one-bit flips, however, they are rare enough that a typical run
does not encounter them.
In both these theorems, the (1 + 1) EA with mutation rate 1/n is regarded. Consequently, with constant probability exactly one bit is flipped.
This together with the fitness-distance correlations exhibited is exploited to
compute the drift. In contrast to this, the (1 + (λ, λ)) GA uses larger mutation rates, meaning that the typical distance between parent and offspring is
larger. In addition, it does not need to estimate whether parent or offspring
is closer to the optimum, but it needs to select among several offspring the
one with slightly smaller distance.
For example, in the case λ = 10 consider a certain point in time when the
parent individual has already a decent fitness. Then most offspring in the
mutation phase will have a genotypic distance that is worse than that of the
parent by a margin of 10. An offspring which has flipped a single bit which
is missing in the parent will have a distance of 8. To be successful, this 20%
advantage has to be visible for the (1 + (λ, λ)) GA via a sufficiently strong
fitness-distance correlation.
The common sense suggests that the bigger the λ is, the more problems
the algorithm should have in detecting a “good” offspring. On the other
hand, the bigger the clause density m/n is, the simpler it should be for the
algorithm to handle bigger values of λ, as the problem becomes more similar
to OneMax.
First, we investigate how the average fitness of a search point at a distance
d from the optimum looks like, and how a difference of two such values
behaves asymptotically depending on the difference between distances.
Lemma 2. The probability for a random 3-CNF clause C, consisting of distinct variables and satisfied by the planted assignment x∗ , to be also satisfied
by an assignment x with the Hamming distance d = d(x) from x∗ , is


6 · n3 + n−d
3

.
P (n, d) =
7 · n3

Proof. There are n3 ways to choose a set of three different variables. For
three fixed variables, there are 7 ways to choose their signs in a way that the
resulting clause is satisfied byx∗ . Hence the set C ∗ of all clauses satisfied by
x∗ has cardinality |C ∗ | = 7 · n3 . For a clause C ∈ C ∗ to be not satisfied by x,
∗
we need that C
 contains
 at least one variable in which x and x differ; there
n
n−d
are exactly 3 − 3 such sets of three variables. For each such set, there
is exactly one way of setting their signs in such a way that the resulting
clause is not satisfied by x (and these signs make the clause satisfied by
12

x∗ ). Consequently, there are exactly
satisfied by x, giving the claim.



n
3

−

n−d
3



clauses in C ∗ which are not

Lemma 3. If n−d = Θ(n) and ` = o(n), then P (n, d)−P (n, d+`) = Θ(`/n).
Proof. From Lemma 2, we compute


n−d
− n−d−`
3
3

P (n, d) − P (n, d + `) =
n
3

3(n − d)2 ` − 3(n − d − 1)`2 − 6(n − d)` + `3 + 2`
n(n − 1)(n − 2)
2
Θ(n ) · ` + Θ(n) · `2 + `3 ± o(n2 )
=
= Θ(`/n),
Θ(n3 )

=

where we used that n`2 = o(n2 `) and `3 = o(n2 `), which both follow from
the assumption ` = o(n).
Corollary 1. Consider a random 3-CNF formula on n variables and m
clauses with the planted assignment x∗ . The expected fitness favg (d) of any
search point x with the Hamming distance d = d(x) from x∗ is


6 · n3 + n−d
3

favg (d) = m ·
.
7 · n3
For n − d = Θ(n) and ` = o(n), we have

favg (d) − favg (d − `) = Θ(m`/n).
Proof. Follows trivially from the definition of fitness, Lemmas 2 and 3, and
linearity of expectation.
As we see, the average fitness values demonstrate a good fitness-distance
correlation. However, the actual fitness values of concrete search points may
deviate quite far apart from the average values when the concrete 3-CNF
formula is fixed. To show a good performance of the (1 + (λ, λ)) GA, we
now show a stronger fitness-distance correlation for offspring from the same
parent. For a number λ to be made precise later, we define the following.
Definition 1. Consider a search point x with a distance d > 0 from the
planted assignment x∗ . Let ` ∈ [1..λ].
• The set X`− := X`− (x) of `-bad offsping is the set of all search points
produced from flipping in x exactly ` bits which coincide in x and x∗ .
13

• The set X`+ := X`+ (x) of `-good offspring is the set of all search points
produced from flipping in x exactly ` bits of which at least one is different in x and x∗ .
• The point x is well-behaved if for all ` ∈ [1..λ]
(i) there are at most |X`− |/λ elements x− ∈ X`− such that f (x) −
f (x− ) ≤ favg (d) − favg (d + ` − 1), and

(ii) there are at most |X`+ |/2 elements x+ ∈ X`+ such that f (x) −
f (x+ ) ≥ favg (d) − favg (d + ` − 1).
The motivation for this definition is that whenever the current search
point x is well-behaved, the selection inside the mutation phase of the (1 +
(λ, λ)) GA is able to distinguish with good probability an offspring with
one of the missing bits guessed right from the offspring with no missing bit
flipped.
Lemma 4. Assume x is the current best solution of the (1 + (λ, λ)) GA,
f (x) < m, x is well-behaved and the current value of λ satisfies λ ≤ λ for
an integer λ. Then, whenever at least one good offspring appears at the
mutation phase, the (1 + (λ, λ)) GA will choose one of them with at least
constant probability as mutation winner.
Proof. Assume that, in the current step, ` was sampled from B(n, λ/n) in
such a way that ` ≤ λ. As the median of B(n, λ/n) is at most dλe, and
dλe ≤ λ as λ is integer, this happens with probability of at least 1/2.
Assume that among the [λ] offspring created in the mutation phase, g ≥ 1
are `-good and [λ]−g are `-bad. The probability that all `-bad offspring have
a fitness value below f (x) − (favg (d(x)) − favg (d(x) + ` − 1)) is at least

[λ]−g 
λ−1
1
1
1−
≥ 1−
≥ e−1 .
λ
λ
The probability of, say, the first `-good offspring to have a fitness value above
f (x) − (favg (d(x)) − favg (d(x) + ` − 1)) is at least 1/2. Thus, the probability
that the (1 + (λ, λ)) GA chooses an offspring which is not `-bad, whenever
it exists, is at least e−1 /4.
Now we show that for all sufficiently small values of λ, all interesting
search points x are well-behaved with an overwhelming probability. In a
sense, this is the core of the main result of this paper.

14

Theorem 1. If λ is an integer satisfying λ = o(min{n, (m/n)1/4 }), then with
probability e−ω(n) (taken over possible 3-CNF formulas satisfying the planted
assignment x∗ ) all x with n − d(x) = Θ(n) are well-behaved.

Proof. There are 2n possible search points x in total (including the search
points which are too far from the optimum), and for every search point
2λ = O(n) statements about sets X`− (x) and X`+ (x) need to be proven. So
by a union bound, it is enough to prove that for each ` ∈ [1..λ] and each x
with probability e−ω(n) the sets X`− (x) and X`+ (x) are as in the definition of
well-behaved.
For the remainder of this proof, we fix an x and a value of `. Let d := d(x).
We prove only the statement on X − (x). The statement on X + (x) can be
proven in the same way and then even yields a sharper bound as required in
Definition 1.
For convenience, we use the short-hand notation X − = X`− (x). For
an x− ∈ X − , the fitness loss f (x) − f (x− ) is a random variable which is
determines by the random formula F . We denote by f − = favg (d + `) the
average value of f (x− ) and by f = = favg (d + ` − 1) the threshold value from
Definition 1. We use an indicator random variable V (x− ) for the event that
x− violates the fitness constraint in Definition 1, that is,
(
1, f (x) − f (x− ) ≤ favg (d) − f = ,
−
V (x ) :=
0, otherwise.
The statement we want to prove is equivalent to
#
"
−
X
|X
|
< e−ω(n) .
Pr
V (x− ) >
λ
x− ∈X −

(3)

This expression calls for one of the Chernoff bounds to be applied. However, the resulting bounds are not strong enough for our aim to be achieved.
For this reason, we introduce a new random variable, Ṽ (x− ), which is less
sensitive to the change of a single clause in the random instance. Let
f ≡ = (f − + f = )/2. Then


f (x) − f (x− ) ≥ favg (d) − f ≡ ;
0,
−
=
avg (d)−f )
Ṽ (x− ) := f (x)−f (x f =)−(f
, favg (d) − f ≡ ≥ f (x) − f (x− ) ≥ favg (d) − f = ;
−f ≡


1,
f (x) − f (x− ) ≤ favg (d) − f = .

As Ṽ (x− ) ≥ V (x− ) with probability one, it is enough to show, instead
of (3), that
"
#
−
X
|X |
Pr
Ṽ (x− ) >
< e−ω(n) .
(4)
λ
x− ∈X −
15

P
For brevity, we write Ṽ Σ := x− ∈X − Ṽ (x− ). We interpret the random
variable Ṽ Σ as a function of the independent uniformly distributed random
variables C1 , . . . , Cm which define the random formula F . Recall that, by
Corollary 1, f = − f − = Θ(m/n), and so is f = − f ≡ . Thus replacing a single
Ci in F by Ci0 introduces a change of at most 2/(f = − f ≡ ) = Θ(n/m) in
the value Ṽ (x− ), however, only for those x− for which x and x− differ in
one of the at most 6 variables contained in Ci ∪ Ci0 (for all other x− , the
value of Ṽ (x− ) does not change).
Thenumber of the
former
kind of x− is at

P
P
5
5
≤
− n−d−(i+1)
= i=0 n−d−(i+1)
most n−d
− n−d−6
= i=0 n−d−i
`−1
`
`
`
`


n−d−1
n−d
`
−
Σ
6 `−1 = 6 ` n−d = |X |·Θ(`/n). The maximum change of Ṽ inflicted
by changing one clause hence is |X − | · O(`/m).
We use this statement to apply McDiarmid’s inequality, see (2), and obtain
i
h
h i 
h ii
h
Pr Ṽ Σ > |X − |/λ = Pr Ṽ Σ > E Ṽ Σ + |X − |/λ − E Ṽ Σ


h i2 
−
Σ
 2 |X |/λ − E Ṽ

≤ exp −

−
2
m · (|X | · O(`/m))





 2 
E[Ṽ Σ ]
m
·
1
−
λ
|X − |



= exp −Ω 
 .
2
2
`λ

(5)

To complete this bound, we need to show that the term (1−λE[Ṽ Σ ]/|X − |)
is at least some positive constant. To do this with the least effort, we introduce the random variable V (x− ) defined by
(
1, f (x) − f (x− ) ≤ favg (d) − f ≡ ,
V (x− ) =
0, otherwise
for all x− ∈ X − , and observe that it dominates Ṽ (x− ). Consequently, we
have E[Ṽ (x− )] ≤ E[V (x− )] = Pr[f (x)−f (x− ) ≤ favg (d)−f ≡ ]. By symmetry,
these probabilities are identical for all x− ∈ X − . As E[f (x− )] = f − , f ≡ −
f − = Θ(m/n), and E[f (x) − f − ] = Θ(`m/n), the bound from (1) gives
Pr[f (x) − f (x− ) ≤ favg (d) − f ≡ ]
= Pr[f (x) − f (x− ) ≤ E[f (x)] − E[f (x− )] + f − − f ≡ ]
= Pr[f (x) − f (x− ) ≤ E[f (x) − f (x− )] − Θ(m/n)]
≤ max{exp(−Ω(m2 /n2 )/(12`m/n)), exp(−(3/8)Ω(m/n))}
= max{exp(−Ω(m/`n)), exp(−Ω(m/n))}
= exp(−Ω(m/`n)).
16

Note that f (x) − f (x− ) is the sum of m independent random variables
describing the influence of each of the m random clauses on this expression.
With probability at least 1 − 3`/n, a random clause contains none of the λ
variables x and x− differ in. In this case, the clause contributes equally to
f (x) and f (x− ), hence zero to the difference.
To finish this part, we shall note that we can estimate the subtrahend in
the term (1 − λE[Ṽ Σ ]/|X − |) as follows:
P
P
−
−
E[Ṽ Σ ]
x− ∈X − E[Ṽ (x )]
x− ∈X − E[V (x )]
=
≤
λ·
λ
·
λ
·
|X − |
|X − |
|X − |
= λ · E[V (x− )] = λ · exp(−Ω(m/`n)) ≤ λ · exp(−Ω(m/λn)).
By the theorem statement, we safely assume that λ = o((m/n)1/4 ). This
allows further refining the estimation:
  

  
m 1/4
m 3/4
λ · exp(−Ω(m/λn)) = o
· exp −ω
= o(1),
n
n
which means that 1 − λE[Ṽ Σ ]/|X − | = 1 − o(1). Consequently, from (5) we
obtain



h
i
m
Σ
−
Pr Ṽ > |X |/λ ≤ exp −Ω
≤ e−ω(n) ,
`2 λ2

where the second estimate follows from ` ≤ λ and λ = o((m/n)4 ). This
finished the proof.
Now we are ready to prove the main result of this section.
Theorem 2. Consider solving random 3-CNF formulas with planted solutions on n variables and m clauses by the (1+(λ, λ)) GA, where m/n > c log n
for large enough constant c. If there exists some integer λ = o(min{n, (m/n)1/4 })
such that, during the entire run of the (1 + (λ, λ)) GA, λ ≤ λ, and the algorithm starts from a random assignment, then with probability 1 − o(1), taken
both over the random 3-CNF formulas and the algorithm decisions, the algorithm will demonstrate, in every point, the same progress, divided by at most
constant, as the same algorithm optimising OneMax on n variables.
Proof. With the exponentially small probability of failure, the algorithm
starts in a search point which is at most (1/2 + ε) · n bits apart from the
planted assignment for a constant ε > 0. Thus, the n − d(x) = Θ(n) condition is satisfied for the initial search point, which enables Lemma 3 and its
numerours corollaries. This means that the initial point is well-behaved by
Theorem 1.
17

With a well-behaved parent, due to Lemma 4, the mutation phase selects
an offspring which contains one of the missing bits with the probability,
which is at most a constant factor worse than the probability of the same
happening with OneMax. With probability of at least 1 − (1 − 1/(e`))` ≥
1 − (1 − 1/(eλ))λ ≥ 1 − e−1/e , one of the missing bits from the parent, which
is found in the chosen offspring, gets recombined with the parent and thus
produces an assignment which is one bit closer to the optimum. Finally, by
Lemma 1, this assignment has a better fitness than the parent, thus it is
accepted with probability at least 1 − n−3 . On the other hand, if no good
bits were found, the same lemma ensures that an assignment which is more
distant from the optimum is not accepted with the same probability. This
means that the new parent still satisfies the n − d(x) = Θ(n) condition,
thus it is well-behaved. Repeated application of this paragraph, until the
optimum is found, proves the theorem.
As a consequence, for logarithmic clause density (m/n = Θ(log n)) the
upper bound on λ, in order for the (1 + (λ, λ)) GA to work consistently, is
o((log n)1/4 ).

4

Running Time of the Adaptive (1+(λ, λ)) GA
with Constrained λ on OneMax

In this section, we prove the bounds on the running time on OneMax of the
adaptive version of the (1 + (λ, λ)) GA, provided that the adaptation of the
population size λ uses the 1/5-th rule, but keeps λ ≤ λ for some λ, which is
possibly a function of the problem size n.
In [9], it was shown
pthat the optimal value of λ, given the current fitness
∗
value f (x), is λ =
n/(n − f (x)). The 1/5-th rule, as seen in experiments [9], tends to keep λ close to this optimum value, and this effect has
been proven in [5].
When λ is bounded, the overall algorithm run can be split into roughly
two phases. The first phase is when the adaptation largely determines the
value of λ, which follows from the deserved λ∗ being (much) less than λ. The
second phase starts when λ finally hits the λ, and while λ∗ grows, the actual
λ has to stay close to λ.
As a consequence, the runtime of the first phase is, roughly, the same
as the runtime of the adaptive (1 + (λ, λ)) GA on the same range of fitness
values, and the runtime of the second phase is, again roughly, the same as
the runtime of the fixed-size (1 + (λ, λ)) GA on the same range of fitness
values. We formalize these ideas in the proof of the following theorem.
18

Theorem 3. The expected running time of the adaptive (1 + (λ, λ)) GA on
OneMax, where the population size parameter λ is bounded from above by
some λ = λ(n), is O(n · max(1, (log n)/λ)).
Proof. We consider two stages of the optimization process. The first stage
starts when the optimization starts and ends when the distance to optimum
d(x), which is n − f (x), first becomes at most bn/(2λ2 )c. The second stage
starts at this point and ends when the optimization ends. We show that the
runtime of the first stage is O(n), and the runtime of the second stage is
O(n(log n)/λ).
First stage Here, we basically repeat the proof of [6, Theorem 5], with the
following corrections:
• The original proof
uses a threshold for the λ, which is C0 · λ∗ for the
p
optimal λ∗ = n/(n − f (x)) and a certain large enough constant C0 .
Above this threshold, the probability for the algorithm to find the next
meaningful bit, and thus to improve the best seen fitness, is so high,
that the random process of changing λ drifts strong enough towards
decreasing λ. Here, we need to change this threshold to min(λ, C0 · λ∗ ),
where λ is the constraint on the population size. Note that the notation
λ means a different thing in [6] (in that paper, it is a synonym of C0 ·λ∗ ).
• Claim 2.1 still reads and is proven in the same way, however, whenever
C0 · λ∗ · F t/4 exceeds our constraint λ, instead of the exact population
size, we start talking about its upper bound.
• Claim 2.2 refers to Lemma 6, which may stop working if population
size hits the λ. However, just at the same moment of time, it is no
longer possible to increase the population size, so the drift of λ towards
greater values stops, but its negative counterpart remains available to
the algorithm. This means that the expected progress of the random
walk of logF λ still becomes negative whenever λ exceeds either λ (in
our notation) or C0 · λ∗ , and is still separated from zero by a constant.
This means that the upper bound on the running time of the adaptive
(1 + (λ, λ)) GA on the interval f (x) ∈ [bn/(2λ2 )c..n], which is O(n), can
be translated without any major change to the adaptive version with the
constrained population size.
Second stage Similarly to the proof of [6, Theorem 5], we split the process
in phases. Each phase starts just after a new fitness level is reached and ends
19

with selecting an individual with the fitness value strictly greater than the
one of the parent. As the adaptation will necessarily drop λ by the adaptation
strength factor of F right before the phase starts, the initial value for the λ
is λ0 ≤ λ/F .
We differentiate between short and long phases. A short phase always
satisfies λ < λ. In exactly the same way as in [6, Theorem 5, Claim 1], we
are able to prove that the expected running time of a short phase is O(λ).
A long phase necessary has at least one iteration, at the end of which
λ = λ. What is more, the equality λ = λ holds until the very end of this
phase, as the only possibility for λ to drop down is generation of an individual
strictly better than its parent, which signifies the end of the phase. For
convenience, we split every long phase in an initial phase, which proceeds
until λ = λ, and a main phase, which maintains λ = λ.
The running time of every initial phase is O(λ), as for short phases. This
means that the common runtime of all short and initial phases altogether,
since d(x) ≤ bn/(2λ2 )c, can be estimated as n/(2λ2 ) · O(λ) = O(n/(2λ)) =
O(n), because, for every fixed algorithm run, every long or short phase corresponds to exactly one unique f (x).
All main phases feature λ = λ, which means their common runtime is
at most the same as the runtime of the (1 + (λ, λ)) GA with fixed λ = λ.
This means it can be estimated in exactly the same way as in [7, Theorem
2, upper bound, third phase], which gives a bound of O(n(log n)/λ). This
bound determines the runtime of the second stage.
This theorem, although being interesting on its own, can be also applied
to solving random 3-SAT problems instead of OneMax, provided λ is small
enough to satisfy the conditions of Theorem 2, and keeping in mind that this
bound on the expected runtime holds, in the case of 3-SAT, with probability
1 − o(1).
It follows particularly that an upper bound of Θ(log n) on the population size still brings the linear runtime of the adaptive (1 + (λ, λ)) GA on
OneMax. Recall that,
√ when the adaptation is not limited, the population
size grows up to Θ( n) towards the last iterations of the algorithm. The
new result shows that such large population sizes are not really necessary for
the success on OneMax, although the corresponding insight could be seen
already in [7].

5

Experiments

Although theoretical results give us certain insights about how powerful our
adaptation schemes are, they, at least in their current form, may be not
20

enough to persuade practitioners whether they are of any use in solving
practical problems. To complement our theoretical research, we conducted
a series of experiments, which appear to demonstrate that application of
our ideas and proposals yields immediate and noticeable response on feasible
problem sizes.

5.1

Results for OneMax

The first experiment was dedicated to evaluation of performance for fixed-size
(1 + (λ, λ)) GA, as well as unlimited and constrained adaptation schemes, on
the OneMax problem. Similar experiments had been also performed in [9].
In this paper, we evaluated much larger problem sizes, which helped revealing
subtle differences in behaviour of various algorithms. We also evaluated more
fixed population sizes systematically, and we also included the version of the
(1 + (λ, λ)) GA with constrained adaptation (λ ≤ 2 log(n + 1)).
We considered problem sizes to be powers of two, from 24 to 224 . The
fixed population sizes were chosen to be λ ∈ [2..20], to cover various ranges
of behaviour. For the adaptive (1 + (λ, λ)) GA schemes, the unlimited one
(denoted as λ ≤ n) and the logarithmically constrained one (denoted as
λ ≤ 2 ln n, in fact, the upper limit is 2 log(n + 1)) were included in the comparison. We also ran the (1 + 1) EA. For every combination of the algorithm
and the problem size, 100 runs were executed, and the median number of
function evaluations is reported. As it is shown in [7], the runtimes of the
fixed-size (1 + (λ, λ)) GA are well concentrated, and the same thing holds
experimentally for the adaptive versions, the median plots are representative
for demonstrating trends and differences for this problem.
The results are presented in Fig. 1. The abscissa axis, logarithmically
scaled, represents the problem size, while the ordinate axis, linearly scaled,
represents the median number of function evaluations, divided by the problem size. In these axes, the Θ(n log n) algorithms produce a straight line
with the angle of α > 0 to the abscissa axis, and the Θ(n) algorithms produce√a horizontal line. Algorithms of intermediate complexities, such as
Θ(n log n), produce the plots, whose shapes depend on exponents at the
logarithmic parts.
Several phenomena, which has been previously shown only theoretically,
can be seen in Fig. 1 as experimental plots for the first time. For instance,
it can be seen that the fixed-size versions of the (1 + (λ, λ)) GA demonstrate
a slightly superlinear behaviour at small sizes, and then switches at certain
threshold to a strictly Θ(n log n) behaviour. This behaviour follows from the
Θ(min(n log n/λ, nλ log log λ/ log λ)) bound proven in [7]. In fact, we can
even observe something similar to the 1/λ quotient: all fixed-size plots have
21

λ=2
λ=3
λ=4
λ=5
λ=6
λ=7
λ=8
λ=9
λ = 10
λ = 11
λ = 12
λ = 13
λ = 14
λ = 15
λ = 16
λ = 17
λ = 18
λ = 19
λ = 20
λ ≤ 2 ln n
λ≤n
(1+1) EA

45

Evaluations / problem size

40
35
30
25
20
15
10

24

25

26

27

28

29

210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
Problem size

Figure 1: Plots of median runtimes on OneMax
different inclines, seem to originate at the same point (which is slightly above
the lower left corner of the plot), and the ratio at n = 224 is approximately
27 for λ = 4 and approximately 50 for λ = 2, which is quite close to the 2x
difference.
The lower envelope of the fixed-size plots should exactly correspond to
the optimal fixed population size as a function of the problem size. We can
clearly see that it behaves like a convex upwards function. Although it is
impossible, at this scale, to determine√the precise p
shape of the function (i.e.
to spot the difference between the Θ( x) and Θ( x log log x/ log x), which
corresponds to the difference between the original estimation in [9] and the
refined estimation in [7]), it is clearly seen that this envelope is significantly
sublinear, that is, the difference between
Θ(n log n) and the actual runtime of
p
the optimal tuning (which is Θ(n log n log log log n/ log log n)) is seen from
experiments.
Finally, both adaptive versions demonstrate easy-to-see linear runtime,
with a quotient of approximately 11 for the unlimited adaptation, and of
approximately 12.5 for the logarithmically constrained adaptation. Thus,
our result shows that bounding the population size by a logarithmic bound
not only preserves the asymptotics of the runtime, but also changes the
absolute performance only very little. The difference between the adaptive
and the optimally fixed-size versions can be, again, clearly seen from the
experimental data.
22

λ=2
λ=3
λ=4
λ=5
λ=6
λ=7
λ=8
λ=9
λ = 10
λ = 11
λ = 12
λ = 13
λ = 14
λ = 15
λ = 16
λ = 17
λ = 18
λ = 19
λ = 20
λ ≤ 2 ln n
λ≤n
(1+1) EA

40
38
36

Evaluations / problem size

34
32
30
28
26
24
22
20
18
16
14
27

28

29

210

211

212

213
214
Problem size

215

216

217

218

219

220

Figure 2: Plots of median runtimes on random 3-CNF formulas with planted
solutions

5.2

Results for Random 3-CNF Formulas

The second experiment was dedicated to solving random 3-CNF formulas
with planted solutions. The same set of algorithms was considered. We took
the problem sizes again in the form of 2t , where t ∈ [7..20]. The rise of the
lower bound is due to the fact that, at sizes 26 and below, difficult formulas
became too often to appear, and studying the behaviour of the (1+(λ, λ)) GA
on such formulas is not a scope of this research. The upper bound is chosen
for performance reasons. We have evaluated the performance of the unlimited
adaptive (1 + (λ, λ)) GA only for sizes up to 216 , because this algorithm was
computationally the most expensive for evaluation, for the reasons which are
discussed below. The number of clauses m was a function of the problem
size: m(n) = b4n log nc.
The results are presented in Fig. 2. The trends seen here are quite similar
to the ones for OneMax (see Fig. 1), with two notable exceptions.
First, we see that the constrained adaptive (1 + (λ, λ)) GA – even with
the logarithmic adaptation constraint, which has not (yet) been proven to
be helpful – manages to perform better than all fixed-size variations. However, its runtime is not linear here, which may indicate that the logarithmic
constraint is too big to be convenient for this problem.
Second, and the most noticeable, the (1 + (λ, λ)) GA with unlimited
23

213
211

λ

29
27
25
23
21
20

21

22

23
p
n/d

24

25

26

Figure 3: Example runs with unconstrained λ, n = 213
adaptation performs even worse than the plain (1 + 1) EA.√The reasons for
this behavior is that the values of population size λ = Θ( n), common at
the latest stages of optimization, which also dictate the mutation probability, interfere in bad ways with the problem. In other words, conditions of
Theorem 2 are severely violated, which destroys the adaptation logic of the
(1 + (λ, λ)) GA.
We performed an additional series of runs, where for each iteration of
each run we recorded the distance to the optimum d(x) of the currently best
individual x, as well as the value of λ. The sizes to be considered were n = 2t
for t ∈ [13..16], and the number of clauses m was, again, m(n) = b4n log nc.
For every problem size, we made five runs. The plots for dependencies
pof λ
on d = d(x) are presented on Fig. 3–6. For convenience, the values of n/d
were taken instead of d(x) to use with the abscissa axis, and
p both axes are
logarithmic. In these coordinates, the optimal λ = λ(d) = n/d values form
a straight line, which is drawn in black color on every plot.
p
Fig. 3–6 demonstrate that for distances which satisfy n/d ≥ log n, the
plots stay in a certain stripe around the optimal values for λ. However,
for smaller distances, adaptation starts to diverge, and values of λ tend to
be greater than necessary. The last iterations sometimes feature very large
population sizes. In Table 1, medians for the maximum λ values, as well as

24

213
211

λ

29
27
25
23
21
20

21

22

23

p

24

25

26

27

n/d

Figure 4: Example runs with unconstrained λ, n = 214

213
211

λ

29
27
25
23
21
20

21

22

23

24
p
n/d

25

26

Figure 5: Example runs with unconstrained λ, n = 215

25

27

216
213

λ

210
27
24
21
20

21

22

23

24
p
n/d

25

26

27

28

Figure 6: Example runs with unconstrained λ, n = 216
Table 1: Medians of maximum λ values for
log2 n
n
median
13 8192 2109.99
14 16384 4747.47
15 32768 10681.82
16 65536 27945.01

unconstrained adaptation
IQR
2589.63
4236.71
11148.18
19246.74

interquartile ranges, which were seen in the main experiment, are presented.
These values suggest that maximum λ tends to be Θ(n).

6

Conclusion

The runtime analysis of the (1 + (λ, λ))-GA conducted in this work shows
that the GA can cope with a weaker fitness-distance correlation than the
perfect one of the OneMax test function, the only example mathematically
analyzed before. However, a weaker fitness-distance correlation requires that
the population size λ is not taken too large, as otherwise the strong mutation
rate of λ/n creates offspring that are too far from each other for the GA to
find the best one (in terms of distance to the optimum) in the intermediate
selection step.
26

Our recommendation on how to use the (1 + (λ, λ))-GA therefore is to
first try a moderate size constant λ, say λ = 5 or λ = 10. If this leads to
an improved performance, than larger values of λ can be tried. For the selfadjusting version of the GA, we generally recommend using an upper limit
for the value which λ can take. For first experiments, this value should be
taken around the best static value for λ and then slowly increased.
We remark that the main part of the body of the GA, namely the generation of y from x, can be used as a mutation operator also in other algorithms.
We have no experience with this approach so far, but are optimistic that it
can give good results as well.

Acknowledgments
This research was started when Maxim Buzdalov stayed at École Polytechnique in May 2016 supported by a grant from the French Consulate in Russia (bourse Metchnikov). Maxim Buzdalov was also financially supported by
the Government of Russian Federation, Grant 074-U01. This research also
benefited from the support of the “FMJH Program Gaspard Monge in optimization and operations research”, and from the support to this program
from EDF.

References
[1] A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc.,
River Edge, NJ, USA, 2011.
[2] G. Badkobeh, P. K. Lehre, and D. Sudholt. Black-box complexity of parallel search with distributed populations. In Proceedings of Foundations
of Genetic Algorithms, pages 3–15. ACM, 2015.
[3] S. Bernstein. On a modification of Chebyshev’s inequality and of the
error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math. 1,
4(5):38–49, 1924.
[4] B. Doerr. Optimal parameter settings for the (1 + (λ, λ)) genetic algorithm. In Proceedings of Genetic and Evolutionary Computation
Conference, pages 1107–1114. ACM, 2016. Full version available at
http://arxiv.org/abs/1604.01088.
[5] B. Doerr and C. Doerr. Optimal parameter choices through selfadjustment: Applying the 1/5-th rule in discrete settings. In Proceedings
27

of Genetic and Evolutionary Computation Conference, pages 1335–1342,
2015.
[6] B. Doerr and C. Doerr. Optimal parameter choices through selfadjustment: Applying the 1/5-th rule in discrete settings, 2015.
[7] B. Doerr and C. Doerr. A tight runtime analysis of the (1 + (λ, λ)) genetic algorithm on onemax. In Proceedings of Genetic and Evolutionary
Computation Conference, pages 1423–1430, 2015.
[8] B. Doerr, C. Doerr, and F. Ebel. Lessons from the black-box: fast
crossover-based genetic algorithms. In Proceedings of Genetic and Evolutionary Computation Conference, pages 781–788, 2013.
[9] B. Doerr, C. Doerr, and F. Ebel. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 567:87–104,
2015.
[10] B. Doerr, F. Neumann, and A. M. Sutton. Improved runtime bounds
for the (1+1) EA on random 3-CNF formulas based on fitness-distance
correlation. In Proceedings of Genetic and Evolutionary Computation
Conference, pages 1415–1422, 2015.
[11] B. W. Goldman and W. F. Punch. Parameter-less population pyramid.
In Proceedings of Genetic and Evolutionary Computation Conference,
pages 785–792, 2014.
[12] P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623–642, 2012.
[13] C. McDiarmid. On the method of bounded differences. Surveys in
Combinatorics, 141:148–188, 1989.
[14] D. Sudholt. Crossover speeds up building-block assembly. In Proceedings
of Genetic and Evolutionary Computation Conference, pages 689–696,
2012.
[15] A. M. Sutton and F. Neumann. Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas. In Proceedings of Parallel Problem Solving from Nature, volume
8672 of Lecture Notes in Computer Science, pages 942–951. Springer,
2014.

28

[16] I. Wegener. Methods for the analysis of evolutionary algorithms on
pseudo-Boolean functions. In S. Sarker, X. Yao, and M. Mohammadian,
editors, Evolutionary Optimization, pages 349–369. Kluwer, Dordrecht,
2002.

29

