<figure><img src="image_1.png" /></figure>

HAL
open science

# Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise

Alexandra Ivanova, Denis Antipov, Benjamin Doerr

► To cite this version:

Alexandra Ivanova, Denis Antipov, Benjamin Doerr. Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise. Genetic and Evolutionary Computation Conference (GECCO 2023), Jul 2023, Lisbonne, Portugal. hal-04097238

HAL Id: hal-04097238

https://hal.science/hal-04097238

Submitted on 15 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Larger Offspring Populations Help the
(1 + (λ, λ)) Genetic Algorithm to Overcome
the Noise

Alexandra Ivanova

Denis Antipov

HSE University, Skoltech
Moscow, Russia

The University of Adelaide
Adelaide, Australia

Benjamin Doerr

Laboratoire d'Informatique (LIX),
CNRS, École Polytechnique,
Institut Polytechnique de Paris
Palaiseau, France

May 9, 2023

**Abstract**

Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. In particular, larger offspring population sizes often lead to strong robustness. We analyze to what extent the (1 + (λ, λ)) genetic algorithm is robust to noise. This algorithm also works with larger offspring population sizes, but an intermediate selection step and a non-standard use of crossover as repair mechanism could render this algorithm less robust than, e.g., the simple (1 + λ) evolutionary algorithm. Our experimental analysis on several classic benchmark problems shows that this difficulty does not arise. Surprisingly, in many situations this algorithm is even more robust to noise than the (1 + λ) EA.

# 1 Introduction

Evolutionary algorithms (EAs) are general-purpose optimization heuristics. The facts that (i) they use a large amount of independent randomness and
(ii) they do not exploit strongly the precise problem definition (they are so-
called black-box optimizers) make it easy to believe that they are robust
to all kinds of disturbances and, in fact, this has been observed multiple
times [BDGG09, JB05].

In this work, we concentrate on the most common stochastic disturbance,
namely that the access to the objective function is prone to small stochastic
errors. This is known as *noisy function evaluations*. We also restrict our-
selves to optimization in discrete search spaces, more precisely, to the search
space $\Omega = \{0, 1\}^n$ of bit strings of length $n$, which is the most common repre-
sentation in discrete evolutionary optimization. Since our focus is on gaining
a solid understanding on how robust certain EAs are to noise, we restrict our
analyses on classic benchmark problems. In this direction, most previous
research results are mathematical runtime analyses, some however enriched
with experimental investigations. We refer to the introduction of [Sud21] for
a detailed account of the existing literature and describe here only the most
relevant previous works.

The first mathematical runtime analysis of an EA in the presence of
noise was conducted by Droste [Dro04]. It showed that the (1 + 1) EA can
optimize the ONEMAX benchmark in polynomial time when noise appears
with rate $O(\frac{\log n}{n})$. If the noise rate is asymptotically larger, superpolynomial
 runtimes result.

Gießen and Kötzing [GK16] were the first to analyze the robustness of
the simple population-based ($\mu$ + 1) EA and (1 + $\lambda$) EA. For both, they
were able to show much stronger runtime guarantees than for (1 + 1) EA
when the population size was large. For example, they showed that for the
one-bit noise with any rate $q \in (0, 1)$ the runtime of the (1 + $\lambda$) EA on
ONEMAX is $O(\frac{n^2\lambda}{q})$ if the population size $\lambda$ is at least $\max\{12/q, 24\}n \ln(n)$.
Although this result does not work well for small noise rates $q = o(1)$, for all
constant rates it shows that the polynomial runtime can be obtained with
population size of order $\Omega(n \log(n))$. This is larger than the runtime of the
(1 + $\lambda$) EA on ONEMAX without noise shown in [JJW05] and [DK15], that
is, $\Theta(n \log(n) + n \frac{\lambda \log^+ \log^+(\lambda)}{\log^+(\lambda)})$, where $\log^+(x)$ stands for $\max\{1, \log(x)\}$.
However, it is significantly better than the exponential runtime of the (1 + 1) EA
for such large noise rates.

For the LEADINGONES benchmark, they could show a quadratic run-
time for the (1 + 1) EA only for a noise rate $q \le 1/(6en^2)$, whereas for
the (1 + $\lambda$) EA with $72 \ln(n) \le \lambda = o(n)$ they showed this guarantee for
all $q \le 0.028/n$. The very tight lower bounds proven in [Sud21] show that
this discrepancy is real, namely, that the (1 + $\lambda$) EA with moderate popu-
lation size can indeed stand much higher noise levels than the (1 + 1) EA.
Sudholt [Sud21] also greatly extended the upper bound of [GK16] showing now, in particular, that a quadratic runtime is obtained when $\lambda \ge qn$ and $\lambda \ge 4.92 \ln(n)$. While no lower bounds were proven for the $(1 + \lambda)$ EA, the experiments in [Sud21] indicate that there is a clear threshold behavior so that the runtime explodes when the noise is too large, where “too large” depends on the population size $\lambda$. We note that when there is no noise and $\lambda$ is at most polynomial in $n$, then the expected runtime of the $(1 + \lambda)$ EA on LEADINGONES is $\Theta(n^2 + \lambda n)$ [JJW05].

In this work, we continue the research direction started in [GK16] and continued in [Sud21] by regarding how robust the $(1 + (\lambda, \lambda))$ GA is to noise. The $(1 + (\lambda, \lambda))$ GA is a genetic algorithm proposed first in [DDE15]. Its main feature is that in each generation, it first generates $\lambda$ mutation offspring from the unique parent individual with a generally high mutation rate. It selects the best of these (“mutation winner”) and creates $\lambda$ new offspring via a biased uniform crossover between the parent and the mutation winner. Here the bias is such that bit values are more often taken from the parent. The best of these crossover offspring is the new parent individual unless the old parent is strictly better (in this case, the old parent is kept). This setup allows to use a higher mutation rate in the first phase, increasing the rate of exploration, since the biased crossover used in the second phase can act as repair mechanism and undo possible destruction from the more aggressive mutation. That this idea can indeed work out has been shown several times, most notably in the first works [DDE15, DD18], where a small, but superconstant runtime gain on ONEMAX was shown (namely, the $O(\max\{\frac{n \log(n)}{\lambda}, \frac{n\lambda \log \log(\lambda)}{\log(\lambda)}\})$ runtime was shown, which with the right choice of $\lambda$ is by an $\Omega(\sqrt{\log(n)})$ factor smaller than the best possible runtime of the mutation-based EAs), in [BD17] for (easy) random SAT instances, and in [ADK22] with significant performance gains on jump functions. It is also worth mentioning that despite the $(1 + (\lambda, \lambda))$ GA relying on a strong correlation between the fitness and the distance to the optimum, it has the same $\Theta(n^2)$ runtime as most population-based algorithms on LEADINGONES, where this correlation is weak [ADK19]. That the main working principle of the $(1 + (\lambda, \lambda))$ GA can also be exploited in multi-objective optimization, was shown in [DHP22].

What was not clear so far, and what is the focus of this work, is how robust the $(1 + (\lambda, \lambda))$ GA is to noise. The fact that in both phases of the algorithm $\lambda$ individuals are generated in parallel could mean that the algorithm inherits the robustness of the $(1 + \lambda)$ EA. On the other hand, the more complicated setup and in particular the intermediate selection step could also render the algorithm less robust. We note that there is no general rule that more complicated algorithms are less robust, but the fact that problem-specific
algorithms, which usually are much more complex than simple evolution-
ary algorithms, are often not robust at all, points into this direction. We
also feel that the analysis of the (1 + (λ, λ)) GA on easy random SAT in-
stances [BD17] suggests that this algorithm could be less robust. We note
that the random SAT instances regarded there roughly give rise to fitness
landscapes that resemble slightly disturbed ONEMAX instances. However,
not the same results as in [DDE15] could be shown, but certain adjustments
to the algorithm where necessary to let it cope with the slightly more rugged
fitness landscape of the random SAT instances.

Our main finding in this work is that these potential problems do not
come true. We conduct an experimental analysis of the robustness ques-
tion on the benchmarks ONEMAX, LEADINGONES, and JUMP. These are
the most common benchmarks in discrete evolutionary optimization, each
with very different characteristics. They are known to show very differ-
ent behaviors of the (1 + (λ, λ)) GA in the noise-free setting: Compared to
simple mutation-based EAs such as the (1 + 1) EA or the (1 + λ) EA, the
(1 + (λ, λ)) GA has a small advantage on ONEMAX (with various ways to
set the parameters [DDE15, DD18, ABD22]), a huge advantage on JUMP
(when used with suitable parameters [ADK22] or automated parameter
choices [ABD21, AD20]), and neither a significant advantage or disadvan-
tage on LEADINGONES [ADK19].

On all three benchmarks, our experiments indicate that the
(1 + (λ, λ)) GA has a good performance also in the presence of noise. Sim-
ilar to the (1 + λ) EA, roughly a logarithmic population size suffices. On
LEADINGONES, both algorithms show a similar robustness, but for many
settings, in particular, the easier ones, the (1 + (λ, λ)) GA suffers from the
fact that each iteration is twice as costly (that is, requires 2λ fitness evalu-
ations instead of λ). This fits to the observation made already in [ADK19]
that the working principle of the (1 + (λ, λ)) GA is not effective on this
problem. For the ONEMAX problem, also both algorithms show similar per-
formance patterns, but in addition the (1 + (λ, λ)) GA keeps its advantage
over the (1 + λ) EA for logarithmic population sizes. On jump functions,
the (1 + (λ, λ)) GA with the right parameters keeps its huge advantage (e.g.,
a speed-up by factor of 100 for jump functions with problem size 2⁷ = 128
and gap size k = 3) over the (1 + λ) EA for all noise intensities up to con-
stant noise rates). A more detailed analysis on ONEMAX shows that already
relatively small population sizes suffice to obtain robustness. For problems
size n = 1024, the best results against constant-rate noise were obtained for
population sizes between 5 and 10.

All these results indicate that the (1 + (λ, λ)) GA, despite its more com-
plicated layout with two selection steps and a non-standard use of crossover,
is highly robust against noise, even of high intensity, and this already from moderate population sizes on.

This works is organized as follows. In the next section, we introduce the benchmarks, the noise model, and the algorithms regarded in this work. In Sections 3 to 5, we describe our experimental results on the ONEMAX, LEADINGONES, and JUMP benchmarks. A conclusion is presented in Section 6.

# 2 Problem Setting

## 2.1 Benchmark Problems

In this paper we consider several pseudo-Boolean benchmark functions to investigate the robustness of the EAs to noise on different landscapes. All these functions are defined on a set of bit strings of length $n$ and return a real value.

The first function we consider is the famous ONEMAX benchmark, which it returns the number of one-bits in its argument. More formally,

$$ \text{ONEMAX}(x) = \sum_{i=1}^{n} x_i. $$

ONEMAX has a clear fitness gradient towards optimum and thus it is often studied to understand how different algorithms perform on easy problems. While very simple, in fact, the simplest problem with unique global optimum in several respects [DJW12, Sud13, Wit13], this benchmark has nevertheless led to many important insights, e.g., on how optimal mutation rates could look like [Müh92], how the selection pressure on non-elitist algorithms influences the runtime [Leh10, Leh11], or that some natural EAs have enormous difficulties even with this simple benchmark [OW15, DK20]. Simple mutation-based EAs (with the parameters set appropriately) solve the ONEMAX problem in time $O(n \log n)$ [Müh92, GKS99, JJW05, Wit06, AD21], which is best-possible for a unary unbiased black-box algorithm [LW12]. Interestingly, also for many more complex algorithms such as ant-colony optimizers or estimation-of-distribution algorithms no better runtime than $O(n \log n)$ on ONEMAX could be shown [NSW09, SW19, DLN19, Wit19, DK20].

The second function we consider in this paper is LEADINGONES. This function, first proposed by Rudolph [Rud97], returns the length of the longest
prefix consisting only of one-bits in the argument. Formally, it is defined by

$$ \text{LEADINGONES}(x) = \sum_{i=1}^{n} \prod_{j=1}^{i} x_j. $$

This function is still considered to be easy for most standard EAs. Due to the low correlation between fitness and the distance to the optimum (e.g., we have all sub-optimal fitness levels in distance one from the optimum), the typical runtimes are higher than on ONEMAX, namely quadratic for many algorithms (when the parameters are set right) [Rud97, DJW02, JJW05, Wit06, GS08, BDN10, DNSW11, Sud13, Doe19, DLN19]. However, due to the low fitness-distance correlation, noise can have a drastic effect on the runtime, misleading the algorithms from good solutions [Sud21].

Finally, we test the algorithms on the $JUMP_k$ function. This function from [DJW02] has a positive integer parameter $k$ and is formally defined as follows.

$$ JUMP_k = \begin{cases} \text{ONEMAX}(x) + k, & \text{if } \text{ONEMAX}(x) \notin (n-k, n), \\ n - \text{ONEMAX}(x), & \text{otherwise.} \end{cases} $$

This function generally imitates ONEMAX, but it has a valley of low fitness in a ball of radius $k-1$ around the optimum. Hence, it has a set of local optima in distance $k$ from the global one. This function is often used to analyze the ability of evolutionary algorithms to escape local optima [DJW02, DLMN17, COY18, HS18, RW20, Doe21, BBD21, Doe22, LOW23, DDLS23]. Also, it is one of the few examples where crossover was shown to lead to super-constant speed-ups [JW02, FKK$^{+}$16, DFK$^{+}$18, WVHM18, RA19, DEJK23].

## 2.2 Noise Model

We focus on the bitwise prior noise model. In this model we have a noise rate $q$ and the noise affects the individual before we evaluate its fitness by flipping each bit independently with probability $q/n$.

The choice of $q$ in our experimental setup is mostly guided by the following theoretical results considering this noise model which have been mentioned in the introduction. In [GK16] it was shown that the runtime of the (1 + 1) EA on ONEMAX is $O(n \log(n))$ (that is, same as without noise) if $q = O(\frac{1}{n})$, it is at most polynomial in $n$ if $q = O(\frac{\log(n)}{n})$ (for more precise bounds in this case see Corollary 14 in [DNDD$^{+}$18]), and it is super-polynomial if $q = \omega(\frac{\log(n)}{n})$.

For this reason we consider $q = \frac{\ln(n)}{n}$, since it is the borderline value between the polynomial and super-polynomial runtimes of the (1 + 1) EA.
We also consider higher noise rates such as $q = \frac{1}{6e} \approx 0.061$, which is a relatively small constant<fnref n="1" />, and $q = 1$, which is considered as a very high noise rate.

In [Sud21] it was shown that the runtime of the (1 + 1) EA on LEADINGONES with the bitwise noise is $\Theta(n^2) \cdot e^{\Theta(\min\{qn^2, n\})}$, which implies that any noise rate $q = \omega(\frac{\log(n)}{n^2})$ yields a super-polynomial runtime. Hence, we chose the same noise rates for our empirical investigation on LEADINGONES. We use the same noise rates for the experiments on JUMP.

Some clues on how the non-trivial offspring population helps the optimization can be found in the results for the one-bit prior noise model, where we flip exactly one bit chosen uniformly at random with probability $q$ (which is also called the *noise rate*) each time before evaluating fitness. For this noise model it was shown in [GK16] that if we use the (1 + $\lambda$) EA, then with $\lambda \ge \min\{12/q, 24\}n \ln(n)$ we can get a runtime of $O(n^2\lambda/q)$ for any noise rate in (0, 1). It was also shown in [Sud21] that the runtime of the (1 + $\lambda$) EA on LEADINGONES with the one-bit noise is $O(n^2) \cdot e^{O(qn/\lambda)}$, which means that the larger population sizes can help to overcome large noise rates. We are, however, not aware of any theoretical results for the population-based EAs for the bitwise noise model.

## 2.3 Algorithms

In this paper we focus on the influence of the offspring population size on the runtime in a noisy environment. Hence, we consider two algorithms which create more than one offspring in each iteration. To minimize the effect of the parent population, all considered algorithms store only one individual and use it as a parent in each iteration. Due to the noisy environment, the fitness of this individual is recalculated in each iteration when we decide whether we should replace it with its offspring. This is a common practice and avoids that a single extreme noise event has a long-lasting impact on the optimization process [DHK12].

By the *runtime* of an algorithm we understand the number of fitness evaluations made by the algorithm until it finds the optimal solution and accepts it as the current individual. We note that in practice it is hard to determine such a moment, since even if we find an individual with the best fitness, it might appear as sub-optimal individual due to noise. However, our main goal is to find the influence of the non-trivial offspring populations on

<footnote n="1">¹The choice of this constant was guided by our preliminary theoretical analysis of the (1 + ($\lambda$, $\lambda$)) GA, from which we concluded that with noise rates up to this one we are very likely to have a beneficial mutation in the mutation winner.</footnote>
the algorithm performance, hence in our experiments we use the knowledge of the true fitness of individuals to detect the moment of finding the truly best individual.

### 2.3.1 The $(1 + \lambda)$ EA

We first consider a classic elitist mutation-based algorithm, the $(1 + \lambda)$ EA. This algorithm stores only one individual $x$, which is initialized with a random bit string. In each iteration we create $\lambda$ new individuals by flipping each bit of $x$ independently with probability $\frac{1}{n}$. We evaluate the fitness of all offspring and choose the one with the best value (the ties are broken uniformly at random). If the fitness of the chosen individual is not worse than the fitness of the current individual, we replace the current individual with the chosen one. The pseudo-code of the $(1 + \lambda)$ EA is shown in Algorithm 1. The typical runtime behavior of the $(1 + \lambda)$ EA is that for moderate population sizes, it has the same asymptotic runtime as the the $(1 + 1)$ EA (this is called “linear speed-up” because the number of iterations reduces by a factor of $\lambda$), but after a certain “cut-off point” the total work to solve a problem increases significantly [JJW05, NW07, DK13, DK15].

<caption>**Algorithm 1:** The $(1 + \lambda)$ EA maximizing a pseudo-Boolean function $f: \{0, 1\}^n \to \mathbb{R}$.</caption>

1 $x \leftarrow$ random bit string of length $n$;
2 **while** not terminated **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;**for** $i \in [1..\lambda]$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x^{(i)} \leftarrow$ a copy of $x$;
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Flip each bit in $x^{(i)}$ with probability $\frac{1}{n}$;
6 &nbsp;&nbsp;&nbsp;&nbsp;**end**
7 &nbsp;&nbsp;&nbsp;&nbsp;$x' \leftarrow \arg\max_{z \in \{x^{(1)},...,x^{(\lambda)}\}} f(z)$;
8 &nbsp;&nbsp;&nbsp;&nbsp;**if** $f(x') \ge f(x)$ **then**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow x'$;
10 &nbsp;&nbsp;&nbsp;&nbsp;**end**
11 **end**

### 2.3.2 The $(1 + (\lambda, \lambda))$ GA

The $(1 + (\lambda, \lambda))$ GA is a crossover-based algorithm which also stores only one individual $x$ (initialized with a random bit string). This algorithm has three parameters: the population size $\lambda$, the mutation rate $p$ and the crossover
bias $c$. Each iteration of the $(1 + (\lambda, \lambda))$ GA consists of two phases. The first phase is the *mutation phase*, which starts with the choice of a number $\ell$ from the binomial distribution $\text{Bin}(n, p)$. Then we create $\lambda$ offspring, each by flipping exactly $\ell$ bits in $x$ (these bits are chosen uniformly at random). This can be interpreted as generating $\lambda$ offspring via the standard bit mutation with rate $p$, but conditional on that all of them have the same number of flipped bits. Then we choose the offspring with the best fitness as the mutation winner $x'$ (all ties are broken uniformly at random).

In the second phase, called the *crossover phase*, we create another $\lambda$ offspring by applying a crossover operator to $x$ and $x'$. This crossover operator chooses each bit from $x'$ with probability $c$ and from $x$ with probability $(1-c)$ (each bit is chosen independently from others). The best crossover offspring is chosen as the crossover winner $y$. If $y$ has a fitness which is not worse than the fitness of $x$, we replace $x$ with $y$. The pseudo-code of the $(1 + (\lambda, \lambda))$ GA is shown in Algorithm 2

<caption>**Algorithm 2:** The $(1 + (\lambda, \lambda))$ GA maximizing a pseudo-Boolean function $f: \{0, 1\}^n \to \mathbb{R}$.</caption>

1 $x \leftarrow$ random bit string of length $n$;
2 **while** *not terminated* **do**
3 &nbsp;&nbsp;&nbsp;**Mutation phase:**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Choose $\ell \sim \text{Bin}(n, p)$;
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $i \in [1..\lambda]$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x^{(i)} \leftarrow$ a copy of $x$;
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Flip $\ell$ bits in $x^{(i)}$ chosen uniformly at random;
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x' \leftarrow \arg \max_{z \in \{x^{(1)}, \dots, x^{(\lambda)}\}} f(z)$;
10 &nbsp;&nbsp;&nbsp;**Crossover phase:**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $i \in [1..\lambda]$ **do**
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Create $y^{(i)}$ by taking each bit from $x'$ with probability $c$ and from $x$ with probability $(1-c)$;
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y \leftarrow \arg \max_{z \in \{y^{(1)}, \dots, y^{(\lambda)}\}} f(z)$;
15 &nbsp;&nbsp;&nbsp;**if** $f(y) \ge f(x)$ **then**
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow y$;
17 &nbsp;&nbsp;&nbsp;**end**
18 **end**

The authors who first proposed the $(1 + (\lambda, \lambda))$ GA in [DDE15] recommend to use $p = \frac{\lambda}{n}$ and $c = \frac{1}{\lambda}$. This setting assumes quite a strong mu-
tation strength, therefore, the mutation offspring have a lot of bits flipped from the right position to the wrong one. However, this also maximizes our chances that in the best individual there is at least one beneficial bit flip. Then the biased crossover has a good chance to keep the beneficial bits and undo the destructive bit flips. We note that this setting works well for ONEMAX [DDE15] and LEADINGONES [ADK19], but the most effective regime for JUMP$_k$ is obtained when $p = c = \sqrt{\frac{k}{n}}$ and $\lambda = \frac{1}{\sqrt{n}}\sqrt{\frac{n}{k}}$, as it was shown in [ADK22].

# 3 Results for OneMax

In this section we show the results of the $(1 + (\lambda, \lambda))$ GA and the $(1 + \lambda)$ EA optimizing a noisy ONEMAX function. We start with a discussion of what is the optimal population size for these algorithms in the presence of noise.

We considered two different problem sizes $n = 2^7$ and $n = 2^{10}$. We ran the $(1 + \lambda)$ EA and the $(1 + (\lambda, \lambda))$ GA with standard parameters $p = \frac{\lambda}{n}$ and $c = \frac{1}{\lambda}$ using all population sizes $\lambda \in [2..30]$ and tracked the mean runtime and its standard deviation over 128 runs for each setting. We used a setting without noise as a baseline and two different noise rates $q = \frac{\ln(n)}{n}$ and $q = \frac{1}{6e}$. The results of the experiments are provided in Figure 1.

The data in the plots suggests that with too small values of $\lambda$ the runtime of both algorithms is extremely large, especially for the large noise rates. The optimal choice of $\lambda$ for the $(1 + (\lambda, \lambda))$ GA for all noise rates seems to be $\lambda = 7$ for $n = 128$ and $\lambda = 8$ for $n = 1024$. For the $(1 + \lambda)$ EA it is not so clear, which values of $\lambda$ are better due to the larger standard deviations of the runtimes, but it seems like $\lambda = 8$ for $n = 128$ and $\lambda = 10$ for $n = 1024$ is the most balanced choice for all noise rates. The observation that this value is slightly larger for both algorithms for $n = 1024$ compared with $n = 128$ makes us assume that the optimal value of $\lambda$ grows with the growth of $n$, but very slowly. We also note that choosing $\lambda$ slightly smaller than these optimal values can drastically increase the runtime, while the choice of a too large $\lambda$ is not so critical.

In this section we also compare the runtimes of the $(1 + \lambda)$ EA and the $(1 + (\lambda, \lambda))$ GA with standard parameters $p = \frac{\lambda}{n}$ and $c = \frac{1}{\lambda}$ for varying problem size $n$. We made 100 runs of each algorithm for problems sizes $\{2^5, \dots, 2^{14}\}$, for which the runs took a reasonable time. We show the results of our experiments in Figure 2, where we normalize the runtimes by $n \ln(n)$, which is asymptotically the same as the runtime of both algorithms with logarithmic $\lambda$. This normalization allows us to better show how the ratio of
<figure><img src="image_3.png" /><figcaption>Figure 1: Mean runtimes (number of fitness evaluation) and their standard deviation of 128 runs of the $(1 + (\lambda, \lambda))$ GA with standard parameters $p = \frac{\lambda}{n}$, $c = \frac{1}{\lambda}$ and the $(1 + \lambda)$ EA with different noise rates on ONEMAX with varying population size $\lambda$ for the problem sizes $n = 2^7$ and $n = 2^{10}$.</figcaption></figure>

the runtimes changes with the growth of the problem size. We use the same noise rates $q = \frac{\ln(n)}{n}$ and $q = \frac{1}{6e}$ as before, and also use the setting without noise ($q = 0$) as a baseline and a setting with a very strong noise, $q = 1$. For
the population size we took $\lambda = \ln(n)$, which is close to the optimal value observed in the previous experiment for both $n = 128$ and $n = 1024$. We also took a slightly smaller population size, $\lambda = \ln(n)/2$, and significantly larger one, $\lambda = \sqrt{n}$.

The results of the experiments show that both algorithms withstand all noise rates up to $q = \frac{1}{6e}$, when the population size is at least $\ln(n)$. For $q = 1$, however, it is necessary to use $\lambda = \sqrt{n}$ to obtain a reasonable runtime. A smaller population size $\lambda = \frac{\ln(n)}{2}$ yields a poor performance of both algorithms when the noise rate is $\frac{1}{6e}$, but it makes both algorithms sustainable to the smaller noise rate $q = \frac{\ln(n)}{n}$. When the population size is equal for both algorithms and less than $\sqrt{n}$, then the $(1 + (\lambda, \lambda))$ GA always has an advantage over the $(1 + \lambda)$ EA. This means that its more complex mechanics do not render it unstable under noise, while maintaining its better performance which was observed in the setting with no noise. On large population size $\lambda = \sqrt{n}$ the $(1 + \lambda)$ EA becomes better than the $(1 + (\lambda, \lambda))$ GA on sufficiently large problem sizes for all noise levels, except $q = 1$.

We also note that at $q = \frac{1}{6e}$ the $(1 + (\lambda, \lambda))$ GA is more effective with $\lambda = \ln(n)$ than with larger $\lambda = \sqrt{n}$, while for the $(1 + \lambda)$ EA it is already better to choose $\lambda = \sqrt{n}$ than $\lambda = \ln(n)$. This observation indicates for this particular noise rate that the core mechanisms of the $(1 + (\lambda, \lambda))$ GA which rely on the intermediate selection are more robust to noise than the simple mechanisms of the $(1 + \lambda)$ EA, which needs a larger population size to reduce the effect of the noise.

# 4 Results for LeadingOnes

In this section we discuss our results for the LEADINGONES benchmark.

As in Section 3, we recorded the runtime of the algorithms for different noise levels and different population sizes. We took the same noise rates $q = 0$, $q = \frac{\ln n}{n}$, $q = \frac{1}{6e}$ and $q = 1$. We also considered the same population sizes as for ONEMAX, that are, $\lambda = \frac{\ln(n)}{2}$, $\lambda = \ln(n)$ and $\lambda = \sqrt{n}$, but we also added the value $\lambda = \frac{n}{2}$. This additional value is motivated by the results in [Sud21], which show that the expected runtime of the $(1 + \lambda)$ EA on LEADINGONES with prior one-bit noise with rate $q$ is $O(n^2) \cdot e^{O(qn/\lambda)}$. Hence, with $q = \Omega(1)$ we need to use $\lambda = \Omega(n)$ to make the exponential factor a constant. Since the one-bit noise model with rate $q$ is very similar to the bitwise noise model with the same rate, we assumed that we also need a linear value of $\lambda$ to be robust to the constant noise rates. For the $(1 + (\lambda, \lambda))$ GA we used the standard parameters, which are $p = \frac{\Delta}{n}$ and $c = \frac{1}{\lambda}$. We made 100 runs for each setting on problem sizes from $\{2^3, \dots, 2^9\}$, on
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>Figure 2: Mean runtimes (number of fitness evaluation) and their standard deviation over 100 runs of the $(1 + (\lambda, \lambda))$ GA with standard parameters $p = \frac{\lambda}{n}$, $c = \frac{1}{\lambda}$ and the $(1 + \lambda)$ EA on ONEMAX with noise rates $q \in \{0, \frac{\ln(n)}{n}, \frac{1}{6e}, 1\}$ with varying problem size $n$ normalized by $n \ln n$.</figcaption></figure>

which they did not take too much time. The results of the experiment are shown in Figure 3, where the runtimes are normalized by $n^2$ (which is the suggested asymptotic runtime from [Sud21]) so that it was easier to see how the ratio between them changes with the problem size.

We observe that for increasing noise intensities, increasing population sizes are necessary to obtain a runtime which is not much larger than $n^2$ for the considered $n$. Once the population size is too small, the runtime
drastically increases.

Comparing the (1 + λ) EA with the (1 + (λ, λ)) GA we see that in most settings the (1 + λ) EA has a better performance than the (1 + (λ, λ)) GA. However, the advantage is usually at most a factor of two. This fits to the observation made in [ADK19] that the (1 + (λ, λ)) GA does not gain from its working principles on a problem like LEADINGONES. So the higher cost of one iteration (twice as much as for the (1 + λ) EA with same population size) does not amortize, but leads to twice as large runtimes. We note that for settings where the algorithms suffer strongly from the noise (that are, the logarithmic values of λ with $q = \frac{\ln(n)}{n}$ and $q = \frac{1}{6e}$ and all sub-linear values of λ with $q = 1$), the advantage of the (1 + λ) EA vanishes.

# 5 Results for Jump

In this section we study the performance of the (1 + (λ, λ)) GA, the (1 + λ) EA, and the (1 + 1) EA on JUMP functions.

We used jump functions with gap size $k = 3$, since for larger values a prohibitively large number of iterations was required to find the optimum. We took the same noise rates as in Sections 3 and 4. Since there are no results on the runtime of the considered algorithms on JUMP in the presence of noise, we used the following parameters. For the (1 + (λ, λ)) GA we used the non-standard parameters recommended for this problem in [ADK22], that is, $p = c = \sqrt{\frac{k}{n}}$. We considered two different population sizes, $\lambda = \ln(n)$, which showed a good performance on ONEMAX, and $\lambda = \frac{(\sqrt{n})^{k-1}}{(\sqrt{k})^k}$ also recommended for $JUMP_k$ in [ADK22]. We used the same population sizes for the (1 + λ) EA for a fair comparison (in terms of the same order of the number of fitness evaluations made in each iteration). We run the algorithms with different noise rates on the problem sizes from {2³, ..., 2⁷}, on which it was possible to do in a reasonable time. The results are shown in Figure 4. This time we do not normalize the plots due to the large difference in the runtimes, but we use a logarithmic scaling for Y axis.

We can see from the plots that the performance of the (1 + 1) EA drops drastically with the growth of the noise rate, while the performance of both population-based EAs is not significantly affected by the noise for both considered population sizes (except for the large noise rate $q = 1$). This also implies that the relation between the runtimes of the (1 + λ) EA and (1 + (λ, λ)) GA stays the same in the presence of noise as without, namely, the runtime of the (1 + (λ, λ)) GA is significantly smaller. To support this observation, for each algorithm, each problem size and each non-zero noise
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /><figcaption>Figure 3: Mean runtimes (number of fitness evaluation) and their standard deviation over 100 runs of the $(1 + (\lambda, \lambda))$ GA with standard parameters $p = \frac{\lambda}{n}$, $c = \frac{1}{\lambda}$ and the $(1 + \lambda)$ EA with noise rates $q \in \{0, \frac{\ln(n)}{n}, \frac{1}{6e}, 1\}$ on LEADINGONES with noise rates $q \in \{0, \frac{\ln(n)}{n}, \frac{1}{6e}\}$ with varying problem size $n$ normalized by $n^2$. Note that the both plots for the non-zero noise rate have a logarithmic vertical axis scale.</figcaption></figure>

rate we run statistical tests comparing them with the runtimes for $q = 0$. We use Students' t-test, which suits our study of mean values, but since this test requires the distribution of the values to be normal, we complement it with non-parametric Wilcoxon rank sum test. The obtained $p$-values are
<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Figure 4: Mean runtimes (number of fitness evaluation) and their standard deviation over 100 runs of the $(1 + (\lambda, \lambda))$ GA with non-standard parameters recommended for JUMP $p = c = \sqrt{\frac{k}{n}}$, the $(1 + \lambda)$ EA and the $(1 + 1)$ EA on JUMP$_k$ with parameter $k = 3$ with varying problem size $n$.</figcaption></figure>

shown in Tables 1 in and 2. These p-values are more than $0.05/3 \approx 0.016$ in the most cases for the population-based algorithms except for the case when $q = 1$. Note that we apply the Bonferroni correction and divide the standard threshold value 0.05 by three, since we use the same samples for $q = 0$ in each of three hypotheses for each algorithm setting and each problem size.
<table><caption>Table 1: *p*-values for the experimental results in Figure 4 for the (1 + 1) EA and the (1 + λ) EA. In the second column we denote Student's t-test by T and Wilcoxon ranksum test by W</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Test</th><th colspan="3">(1 + 1) EA</th><th colspan="6">(1 + λ) EA</th></tr><tr><th>q = <sup>ln(n)</sup>/<sub>n</sub></th><th>q = <sup>1</sup>/<sub>6e</sub></th><th>q = 1</th><th colspan="3">λ = ln(n)</th><th colspan="3">λ = <sup>√n<sup>k-1</sup></sup>/<sub>√k</sub></th></tr></thead><tbody><tr><td rowspan="2">8</td><td>T</td><td>0.323</td><td>0.356</td><td>0.266</td><td>0.308</td><td>0.567</td><td>0.072</td><td>0.323</td><td>0.356</td><td>0.266</td></tr><tr><td>W</td><td>0.499</td><td>0.199</td><td>0.374</td><td>0.247</td><td>0.599</td><td>0.124</td><td>0.499</td><td>0.199</td><td>0.374</td></tr><tr><td rowspan="2">16</td><td>T</td><td>7.83 · 10<sup>-3</sup></td><td>0.544</td><td>1.16 · 10<sup>-10</sup></td><td>0.381</td><td>0.667</td><td>5.29 · 10<sup>-3</sup></td><td>0.890</td><td>0.234</td><td>0.029</td></tr><tr><td>W</td><td>5.27 · 10<sup>-3</sup></td><td>0.494</td><td>4.61 · 10<sup>-12</sup></td><td>0.302</td><td>0.645</td><td>0.018</td><td>0.953</td><td>0.269</td><td>0.067</td></tr><tr><td rowspan="2">32</td><td>T</td><td>3.13 · 10<sup>-6</sup></td><td>2.80 · 10<sup>-4</sup></td><td>4.66 · 10<sup>-22</sup></td><td>0.293</td><td>0.439</td><td>1.03 · 10<sup>-10</sup></td><td>0.566</td><td>0.321</td><td>0.045</td></tr><tr><td>W</td><td>1.66 · 10<sup>-6</sup></td><td>2.36 · 10<sup>-4</sup></td><td>1.35 · 10<sup>-33</sup></td><td>0.639</td><td>0.930</td><td>9.03 · 10<sup>-13</sup></td><td>0.318</td><td>0.151</td><td>0.131</td></tr><tr><td rowspan="2">64</td><td>T</td><td>1.11 · 10<sup>-8</sup></td><td>6.40 · 10<sup>-9</sup></td><td>-</td><td>0.015</td><td>0.020</td><td>1.02 · 10<sup>-18</sup></td><td>0.171</td><td>0.171</td><td>3.20 · 10<sup>-6</sup></td></tr><tr><td>W</td><td>3.44 · 10<sup>-8</sup></td><td>5.11 · 10<sup>-8</sup></td><td>-</td><td>0.063</td><td>0.074</td><td>9.05 · 10<sup>-28</sup></td><td>0.125</td><td>0.125</td><td>4.22 · 10<sup>-5</sup></td></tr><tr><td rowspan="2">128</td><td>T</td><td>8.34 · 10<sup>-12</sup></td><td>6.64 · 10<sup>-18</sup></td><td>-</td><td>0.526</td><td>0.023</td><td>-</td><td>0.261</td><td>0.196</td><td>-</td></tr><tr><td>W</td><td>1.12 · 10<sup>-16</sup></td><td>9.25 · 10<sup>-19</sup></td><td>-</td><td>0.524</td><td>0.016</td><td>-</td><td>0.346</td><td>0.122</td><td>-</td></tr></tbody></table>
<table><caption>Table 2: *p*-values for the experimental results in Figure 4 for the (1 + (λ, λ)) GA. In the second column we denote Student's t-test by T and Wilcoxon ranksum test by W</caption><thead><tr><th rowspan="3">n</th><th rowspan="3">Test</th><th colspan="6">(1 + (λ, λ)) GA</th></tr><tr><th colspan="3">λ = ln(n)</th><th colspan="3">λ = <sup>√n</sup>/<sub>k</sub><sup>k-1</sup></th></tr><tr><th>q = <sup>ln(n)</sup>/<sub>n</sub></th><th>q = <sup>1</sup>/<sub>6e</sub></th><th>q = 1</th><th>q = <sup>ln(n)</sup>/<sub>n</sub></th><th>q = <sup>1</sup>/<sub>6e</sub></th><th>q = 1</th></tr></thead><tbody><tr><td rowspan="2">8</td><td>T</td><td>0.468</td><td>0.640</td><td>4.31 · 10<sup>-7</sup></td><td>8.92 · 10<sup>-3</sup></td><td>0.480</td><td>2.21 · 10<sup>-12</sup></td></tr><tr><td>W</td><td>0.494</td><td>0.243</td><td>4.36 · 10<sup>-6</sup></td><td>0.021</td><td>0.341</td><td>1.68 · 10<sup>-10</sup></td></tr><tr><td rowspan="2">16</td><td>T</td><td>2.41 · 10<sup>-4</sup></td><td>0.017</td><td>2.43 · 10<sup>-13</sup></td><td>1.15 · 10<sup>-3</sup></td><td>0.172</td><td>2.69 · 10<sup>-11</sup></td></tr><tr><td>W</td><td>1.55 · 10<sup>-4</sup></td><td>0.023</td><td>1.51 · 10<sup>-14</sup></td><td>0.021</td><td>0.653</td><td>2.00 · 10<sup>-10</sup></td></tr><tr><td rowspan="2">32</td><td>T</td><td>0.086</td><td>0.718</td><td>4.20 · 10<sup>-14</sup></td><td>0.716</td><td>0.328</td><td>1.12 · 10<sup>-9</sup></td></tr><tr><td>W</td><td>0.274</td><td>0.920</td><td>8.18 · 10<sup>-23</sup></td><td>0.980</td><td>0.472</td><td>2.02 · 10<sup>-9</sup></td></tr><tr><td rowspan="2">64</td><td>T</td><td>0.114</td><td>0.056</td><td>3.68 · 10<sup>-15</sup></td><td>0.350</td><td>0.160</td><td>1.90 · 10<sup>-3</sup></td></tr><tr><td>W</td><td>0.401</td><td>0.227</td><td>6.26 · 10<sup>-33</sup></td><td>0.333</td><td>0.199</td><td>9.60 · 10<sup>-3</sup></td></tr><tr><td rowspan="2">128</td><td>T</td><td>0.052</td><td>1.71 · 10<sup>-3</sup></td><td>-</td><td>0.557</td><td>0.433</td><td>0.013</td></tr><tr><td>W</td><td>0.047</td><td>2.45 · 10<sup>-3</sup></td><td>-</td><td>0.822</td><td>0.894</td><td>0.130</td></tr></tbody></table>
# 6 Conclusion

In this work, we conducted the first experimental analysis on how robust the $(1 + (\lambda, \lambda))$ GA is to bit-wise prior noise. Our results for various noise intensities $q$ on the classic ONEMAX, LEADINGONES, and JUMP benchmark show that from a logarithmic offspring population size $\lambda$ on, the $(1 + (\lambda, \lambda))$ GA is very robust to noise and can stand even constant noise rates, i.e., bit-wise noise with per-bit error rate $\Theta(1/n)$. On the ONEMAX and JUMP problems, where this algorithm was previously shown to outperform the $(1 + \lambda)$ EA, it keeps this advantage also in the presence of noise. Together with the result of [ADK19], indicating that the $(1 + (\lambda, \lambda))$ GA on problems that are unsuitable for its main working principle can fall back to the $(1 + \lambda)$ EA, this work suggests that the $(1 + (\lambda, \lambda))$ GA is an interesting alternative to comparable mutation-based EAs.

In this first work on the robustness of the $(1 + (\lambda, \lambda))$ GA to noise, we could not yet derive clear recommendations on the choice of the parameters. On the positive side, our results suggest that often simple adhoc choices like a logarithmic or a linear population size $\lambda$ do a good job. At the same time, it is clear that the recommendations from the noise-less case cannot simply be reused (this would be $o(\log n)$ for ONEMAX, which appears too small in our experiments). Generally speaking, our experiments show that larger population sizes are preferable with increasing noise, but that too large population sizes can be wasteful. So determining the optimal value for this parameter is an interesting open problem. Given such functional relations can be difficult to determine via experiments, a mathematical runtime analysis might be the right tool here (where we admit that such analyses can be highly nontrivial as witnessed by the fact that a good understanding of how the $(1 + 1)$ EA and the $(1 + \lambda)$ EA optimize LEADINGONES in the presence of noise was only obtained very recently [Sud21]).

# Acknowledgements

This work was supported by RFBR and CNRS, project number 20-51-15009, by a public grant as part of the Investissements d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH and by the Australian Research Council (ARC), grant DP190103894.
References

[ABD21] Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution. In *Genetic and Evolutionary Computation Conference, GECCO 2021*, pages 1115–1123. ACM, 2021.

[ABD22] Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. Fast mutation in crossover-based algorithms. *Algorithmica*, 84:1724–1761, 2022.

[AD20] Denis Antipov and Benjamin Doerr. Runtime analysis of a heavy-tailed $(1 + (\lambda, \lambda))$ genetic algorithm on jump functions. In *Parallel Problem Solving From Nature, PPSN 2020, Part II*, pages 545–559. Springer, 2020.

[AD21] Denis Antipov and Benjamin Doerr. A tight runtime analysis for the $(\mu + \lambda)$ EA. *Algorithmica*, 83:1054–1095, 2021.

[ADK19] Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. A tight runtime analysis for the $(1 + (\lambda, \lambda))$ GA on LeadingOnes. In *Foundations of Genetic Algorithms, FOGA 2019*, pages 169–182. ACM, 2019.

[ADK22] Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. A rigorous runtime analysis of the $(1 + (\lambda, \lambda))$ GA on jump functions. *Algorithmica*, 84:1573–1602, 2022.

[BBD21] Riade Benbaki, Ziyad Benomar, and Benjamin Doerr. A rigorous runtime analysis of the 2-MMAS$_{ib}$ on jump functions: ant colony optimizers can cope well with local optima. In *Genetic and Evolutionary Computation Conference, GECCO 2021*, pages 4–13. ACM, 2021.

[BD17] Maxim Buzdalov and Benjamin Doerr. Runtime analysis of the $(1 + (\lambda, \lambda))$ genetic algorithm on random satisfiable 3-CNF formulas. In *Genetic and Evolutionary Computation Conference, GECCO 2017*, pages 1343–1350. ACM, 2017.

[BDGG09] Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella, and Walter J. Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. *Natural Computing*, 8:239–287, 2009.
[BDN10] S¨untje B¨ottcher, Benjamin Doerr, and Frank Neumann. Op- timal fixed and adaptive mutation rates for the LeadingOnes problem. In *Parallel Problem Solving from Nature, PPSN 2010*, pages 1–10. Springer, 2010.

[COY18] Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. Fast artifi- cial immune systems. In *Parallel Problem Solving from Nature, PPSN 2018, Part II*, pages 67–78. Springer, 2018.

[DD18] Benjamin Doerr and Carola Doerr. Optimal static and self- adjusting parameter choices for the (1 + (λ, λ)) genetic algo- rithm. *Algorithmica*, 80:1658–1709, 2018.

[DDE15] Benjamin Doerr, Carola Doerr, and Franziska Ebel. From black- box complexity to designing new genetic algorithms. *Theoretical Computer Science*, 567:87–104, 2015.

[DDLS23] Benjamin Doerr, Arthur Dremaux, Johannes Lutzeyer, and Aur´elien Stumpf. How the move acceptance hyper-heuristic copes with local optima: drastic differences between jumps and cliffs. In *Genetic and Evolutionary Computation Conference, GECCO 2023*. ACM, 2023. To appear.

[DEJK23] Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, and Martin S. Krejca. Lasting diversity and superior runtime guar- antees for the (µ+1) genetic algorithm. *CoRR*, abs/2302.12570, 2023.

[DFK$^{+}$18] Duc-Cuong Dang, Tobias Friedrich, Timo K¨otzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. Escaping local optima using crossover with emergent diversity. *IEEE Transactions on Evolutionary Computation*, 22:484–497, 2018.

[DHK12] Benjamin Doerr, Ashish Ranjan Hota, and Timo K¨otzing. Ants easily solve stochastic shortest path problems. In *Genetic and Evolutionary Computation Conference, GECCO 2012*, pages 17–24. ACM, 2012.

[DHP22] Benjamin Doerr, Omar El Hadri, and Adrien Pinard. The (1 + (λ, λ)) global SEMO algorithm. In *Genetic and Evolutionary Computation Conference, GECCO 2022*, pages 520–528. ACM, 2022.
[DJW02] Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. *Theoretical Computer Science*, 276:51–81, 2002.

[DJW12] Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. *Algorithmica*, 64:673–697, 2012.

[DK13] Benjamin Doerr and Marvin Künnemann. Royal road functions and the $(1 + \lambda)$ evolutionary algorithm: Almost no speed-up from larger offspring populations. In *Congress on Evolutionary Computation, CEC 2013*, pages 424–431. IEEE, 2013.

[DK15] Benjamin Doerr and Marvin Künnemann. Optimizing linear functions with the $(1 + \lambda)$ evolutionary algorithm—different asymptotic runtimes for different instances. *Theoretical Computer Science*, 561:3–23, 2015.

[DK20] Benjamin Doerr and Martin S. Krejca. Significance-based estimation-of-distribution algorithms. *IEEE Transactions on Evolutionary Computation*, 24:1025–1034, 2020.

[DLMN17] Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. Fast genetic algorithms. In *Genetic and Evolutionary Computation Conference, GECCO 2017*, pages 777–784. ACM, 2017.

[DLN19] Duc-Cuong Dang, Per Kristian Lehre, and Phan Trung Hai Nguyen. Level-based analysis of the univariate marginal distribution algorithm. *Algorithmica*, 81:668–702, 2019.

[DNDD$^{+}$18] Raphaël Dang-Nhu, Thibault Dardinier, Benjamin Doerr, Gau-tier Izacard, and Dorian Nogneng. A new analysis method for evolutionary optimization of dynamic and noisy objective functions. In *Genetic and Evolutionary Computation Conference, GECCO 2018*, pages 1467–1474. ACM, 2018.

[DNSW11] Benjamin Doerr, Frank Neumann, Dirk Sudholt, and Carsten Witt. Runtime analysis of the 1-ANT ant colony optimizer. *Theoretical Computer Science*, 412:1629–1644, 2011.

[Doe19] Benjamin Doerr. Analyzing randomized search heuristics via stochastic domination. *Theoretical Computer Science*, 773:115–137, 2019.
[Doe21] Benjamin Doerr. The runtime of the compact genetic algorithm on Jump functions. *Algorithmica*, 83:3059–3107, 2021.

[Doe22] Benjamin Doerr. Does comma selection help to cope with local optima? *Algorithmica*, 84:1659–1693, 2022.

[Dro04] Stefan Droste. Analysis of the (1+1) EA for a noisy OneMax. In *Genetic and Evolutionary Computation Conference, GECCO 2004*, pages 1088–1099. Springer, 2004.

[FKK$^{+}$16] Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck. Fast building block assembly by majority vote crossover. In *Genetic and Evolutionary Computation Conference, GECCO 2016*, pages 661–668. ACM, 2016.

[GK16] Christian Gießen and Timo Kötzing. Robustness of populations in stochastic environments. *Algorithmica*, 75:462–489, 2016.

[GKS99] Josselin Garnier, Leila Kallel, and Marc Schoenauer. Rigorous hitting times for binary mutations. *Evolutionary Computation*, 7:173–203, 1999.

[GS08] Walter J. Gutjahr and Giovanni Sebastiani. Runtime analysis of ant colony optimization with best-so-far reinforcement. *Methodology and Computing in Applied Probability*, 10:409–433, 2008.

[HS18] Václav Hasenöhrl and Andrew M. Sutton. On the runtime dynamics of the compact genetic algorithm on jump functions. In *Genetic and Evolutionary Computation Conference, GECCO 2018*, pages 967–974. ACM, 2018.

[JB05] Yaochu Jin and Jürgen Branke. Evolutionary optimization in uncertain environments – a survey. *IEEE Transactions on Evolutionary Computation*, 9:303–317, 2005.

[JJW05] Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. On the choice of the offspring population size in evolutionary algorithms. *Evolutionary Computation*, 13:413–440, 2005.

[JW02] Thomas Jansen and Ingo Wegener. The analysis of evolutionary algorithms – a proof that crossover really can help. *Algorithmica*, 34:47–66, 2002.
[Leh10] Per Kristian Lehre. Negative drift in populations. In *Parallel Problem Solving from Nature*, PPSN 2010, pages 244–253. Springer, 2010.

[Leh11] Per Kristian Lehre. Fitness-levels for non-elitist populations. In *Genetic and Evolutionary Computation Conference, GECCO 2011*, pages 2075–2082. ACM, 2011.

[LOW23] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. When move acceptance selection hyper-heuristics outperform Metropolis and elitist evolutionary algorithms and when not. *Artificial Intelligence*, 314:103804, 2023.

[LW12] Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. *Algorithmica*, 64:623–642, 2012.

[Müh92] Heinz Mühlenbein. How genetic algorithms really work: mutation and hillclimbing. In *Parallel Problem Solving from Nature*, PPSN 1992, pages 15–26. Elsevier, 1992.

[NSW09] Frank Neumann, Dirk Sudholt, and Carsten Witt. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. *Swarm Intelligence*, 3:35–68, 2009.

[NW07] Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. *Theoretical Computer Science*, 378:32–40, 2007.

[OW15] Pietro S. Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. *Theoretical Computer Science*, 605:21–41, 2015.

[RA19] Jonathan E. Rowe and Aishwaryaprajna. The benefits and limitations of voting mechanisms in evolutionary optimisation. In *Foundations of Genetic Algorithms*, FOGA 2019, pages 34–42. ACM, 2019.

[Rud97] Günter Rudolph. *Convergence Properties of Evolutionary Algorithms*. Verlag Dr. Kováč, 1997.

[RW20] Amirhossein Rajabi and Carsten Witt. Self-adjusting evolutionary algorithms for multimodal optimization. In *Genetic and Evolutionary Computation Conference, GECCO 2020*, pages 1314–1322. ACM, 2020.
[Sud13] Dirk Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. *IEEE Transactions on Evolutionary Computation*, 17:418–435, 2013.

[Sud21] Dirk Sudholt. Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial. *Algorithmica*, 83:976–1011, 2021.

[SW19] Dirk Sudholt and Carsten Witt. On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. *Algorithmica*, 81:1450–1489, 2019.

[Wit06] Carsten Witt. Runtime analysis of the ($\mu$ + 1) EA on simple pseudo-Boolean functions. *Evolutionary Computation*, 14:65–86, 2006.

[Wit13] Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. *Combinatorics, Probability & Computing*, 22:294–318, 2013.

[Wit19] Carsten Witt. Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax. *Algorithmica*, 81:632–667, 2019.

[WVHM18] Darrell Whitley, Swetha Varadarajan, Rachel Hirsch, and Anirban Mukhopadhyay. Exploration and exploitation without mutation: solving the jump function in $\Theta(n)$ time. In *Parallel Problem Solving from Nature, PPSN 2018, Part II*, pages 55–66. Springer, 2018.