# A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive

Martin S Krejca, Carsten Witt

► To cite this version:

Martin S Krejca, Carsten Witt. A Flexible Evolutionary Algorithm with Dynamic Mutation Rate Archive. Algorithmica, 2025, 88 (1), pp.5. 10.1007/s00453-025-01345-5. hal-05533960

HAL Id: hal-05533960

https://hal.science/hal-05533960v1

Submitted on 3 Mar 2026

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
A Flexible Evolutionary Algorithm With
Dynamic Mutation Rate Archive

Martin S. Krejca¹* and Carsten Witt²

¹Laboratoire d'Informatique (LIX), CNRS, École Polytechnique,
Institut Polytechnique de Paris, 1 Rue Honoré d'Estienne d'Orves,
Palaiseau, 91120, Île-de-France, France.

²DTU Compute, Technical University of Denmark, Richard Petersens
Plads, Lyngby, DK-2800, Denmark.

*Corresponding author(s). E-mail(s): martin.krejca@polytechnique.edu;
Contributing authors: cawi@dtu.dk;

Abstract

We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using *k*-bit flip mutations. The algorithm adds successful mutation rates to an archive of promising rates that are favored in subsequent steps. Rates expire when their number of unsuccessful trials has exceeded a threshold, while rates currently not present in the archive can enter it in two ways: (i) via user-defined minimum selection probabilities for rates combined with a successful step or (ii) via a stagnation detection mechanism increasing the value for a promising rate after the current bit-flip neighborhood has been explored with high probability. For the minimum selection probabilities, we suggest different options, including heavy-tailed distributions.

We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the ONEMAX and JUMP functions, on general unimodal functions, on minimum spanning trees, and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.

**Keywords:** Theory, runtime analysis, evolutionary algorithm, parameter adaptation, archive

001

002

003

004

005

006

007

008

009

010

011

012

013

014

015

016

017

018

019

020

021

022

023

024

025

026

027

028

029

030

031

032

033

034

035

036

037

038

039

040

041

042

043

044

045

046
# 1 Introduction

The success of evolutionary algorithms (EAs) depends crucially on their parametriza-
tion [1]. At their core is the careful balance of exploration and exploitation. On the
one hand, an EA should find a, potentially locally, optimal solution if it is close by.
On the other hand, it should escape local optima and keep finding better solutions
within reasonable time.

To achieve this behavior, an EA needs to be flexible enough to consider solutions
that are at different distances from its current solutions. As there are many ways
to make such a choice, this has led to various approaches that have been studied
theoretically [1]. Some approaches consider a static distribution over the search radius
(known as *mutation rate*). Others adjust the mutation rate dynamically during the run.
Yet other approaches allow to accept worse solutions in order to search more locally
for alternative, better solutions. And some approaches do not work with multi-sets
of solutions but with distributions over solutions instead. We discuss some prominent
ideas in more detail in Section 2.

To the best of our knowledge, almost all of these approaches base their choice
for the next mutation rate on *ad hoc* knowledge, not exploiting the information from
previous iterations extensively. This means that recurring structures in the search
space are not necessarily well exploited. In contrast, approaches that do attempt to
incorporate knowledge from previous iterations are hard to analyze and there are much
fewer runtime results.

We propose a flexible EA (the *flex-EA*, *Algorithm 1*), which aims to satisfy both
needs. The flex-EA maintains an archive of mutation rates that were successful in the
past, called *active*. In each iteration, it picks a mutation rate based primarily on the
active rates, but it still considers all other rates, based on user-defined probabilities.
Successful rates are added to the archive while unsuccessful ones are discarded after a
certain amount of time, defined by the user. If an active rate is discarded, the flex-EA
falls back to stagnation detection [2], that is, it activates mutation rates successively 093
in increasing order. In contrast to classical stagnation detection though, the flex- 094
EA allows to switch to its prior behavior once other mutation rates are found to 095
be successful. Overall, the flex-EA switches flexibly between two modes of operation, 096
based on its recent history. 097
098
099
100

The flex-EA allows many of its parameters to be adjusted in order to incor- 101
porate problem-specific knowledge. However, in the absence of such knowledge, we 102
recommend to choose the probabilities of inactive rates according to a heavy-tailed 103
distribution – a common, general-purpose choice, first suggested by Doerr et al. [3], 104
also known as a power-law – and to choose the times for discarding active rates in the 105
same manner as done in stagnation detection [2]. Following these parameter recom- 106
mendations fixes all parameters of the flex-EA and eliminates the need of the user to 107
make any choices themselves. 108
109
110
111
112
113

We show the efficiency of the flex-EA by analyzing it on a diverse set of problems, 114
namely, on unimodal and on jump functions, on the minimum spanning tree problem, 115
and on hurdle-like functions with varying hurdle width. For all of these problems, the 116
performance of the flex-EA is close to or even better than the best known results for 117
stagnation detection and heavy-tailed mutation. 118
119
120
121
122

For unimodal functions (Section 5), the progress of the flex-EA is mainly deter- 123
mined by its probability to improve solutions locally (Theorem 4). For ONEMAX and 124
LEADINGONES of problem size $n$ and with the recommended parametrization, this 125
results in the common bounds of $O(n \log(n))$ and $O(n^2)$, respectively. As the flex-EA 126
is a unary unbiased algorithm [4], the result for ONEMAX is tight. 127
128
129
130

For the JUMP benchmark of problem size $n$ and gap size $k$ (Section 6), the rec- 131
ommended parametrization results for $k = o(n/\log n)$ in a bound of $(2 + o(1))\binom{n}{k}$ 132
(Theorem 7), which is optimal for unbiased algorithms with unary mutation, up to a 133
134
135
136
137
138
factor of 2 + o(1) [5]. For many other values of k, the result is a product of $\binom{n}{k}$ and a
factor that depends at most quadratically on k.

For the combinatorial problem of finding a minimum spanning tree on a graph
with $m$ edges (Section 7), we rely on the flexibility to incorporate problem-specific
knowledge, and we adjust the parameters such that the algorithm mainly makes
progress by flipping one or two edges into or out of solutions. With this choice, the flex-
EA has an expected runtime of $(1 + o(1))(m^2 \log(m))$ (Theorem 8), which matches
the best known bound [6].

Last, to showcase the benefit of an archive, we introduce a problem that features
many local optima separated by gaps of alternating widths (Section 8). Once the flex-
EA determines the necessary rates, it maintains them successfully until the global
optimum is found. It does so in an expected time that is faster by a poly-logarithmic
factor than heavy-tailed mutation and faster by a super-polynomial factor than stag-
nation detection (Theorem 9). Both heavy-tailed mutation and stagnation detection
are slowed down by requiring to find the correct mutation rate repeatedly, although
heavy-tailed mutation does this far more efficiently than stagnation detection.

Overall, our results show that the flex-EA has a great performance with the rec-
ommended parameter setting while effectively not requiring any parameter choices.
In settings with repeating local structures, this parametrization even outperforms the
operators it is based on. In the case of problem-specific knowledge, the flex-EA can
achieve results that match the best known bounds. For all of these settings, the state
space of the algorithm remains simple enough that a mathematical analysis is still
tractable.

**Extension.** An extended abstract of this paper was previously published at
GECCO '24 [7]. The current article extends this previous work by featuring all proofs
and by correcting several mistakes in the conference version that were based on par-
tially ignoring the impact of the global counter of the flex-EA in the conference version.
The version of the flex-EA in this article no longer features a global counter but separates explicitly between following stagnation detection and not following it. This adjustment mostly matches the assumptions made in the proofs of the conference version and leaves the results from the conference version thus largely unchanged.

## 2 Related Work

There exists a plethora of different operators for choosing good mutation rates [1]. We provide an overview on established concepts that are more closely related to the flex-EA. In particular, we only concern unary operators. Furthermore, we focus on single-trajectory algorithms that only maintain a single search point at a time and update it iteratively. Using populations and diversity-maintaining operators opens up for a new level of complexity in the design and analysis of EAs. In addition, this excludes estimation-of-distribution algorithms (EDAs) [8], which maintain a probability distribution over the search space instead of a single search point.

**Non-elitism.** A non-elitist algorithm is one in which worse solutions can be selected over better solutions. Although this approach does not directly change the mutation rate, it can affect the success of the current rate by creating solutions in a distance that is more favorable [9, 10]. This requires a careful balance of the selection probability of solutions. In comparison, the flex-EA is an elitist algorithm, i. e., it aims at finding mutation rates that are good for the currently best solution without modifying it.

**Static rate distributions.** A large class of EAs, most prominently the (1+1) EA, use a static distribution for selecting mutation rates. Since this distribution is fixed, it needs to accommodate all situations that may arise during optimization. The (1+1) EA uses a single rate that creates solutions with high probability locally around the current search point. This leads to long waiting times for escaping local optima [11].
Artificial immune systems (AISes) use operators that change solutions more drastically [12]. However, since this makes it harder to find local improvements, AISes often use additional operators that influence how large the changes to a solution actually are [13].

Arguably the best of both worlds is achieved by choosing the mutation rate according to a heavy-tailed distribution, as introduced by Doerr et al. [3] in their seminal paper. This approach, known as fast mutation, finds local improvements quickly and also has a good probability to use larger mutation rates to escape local optima. Since its inception, this approach has seen successful applications in a variety of theoretical works [5, 12, 14–23]. A drawback of fast mutation is that it never adjusts its distribution. Thus, to find improving solutions at larger distances, it exclusively relies on the decent probability of choosing a sufficiently large rate. Depending on the distance, this can result in long waiting times.

A different approach is taken by offline parameter tuning. In this setting, the aim is to find optimal parameters for a given algorithm. To this end, a popular strategy is to run different parametrizations on given problems and to then determine quickly which parametrization performs best and should thus be kept. Prominent examples are *irace* [24] and *SMAC* [25, 26]. The theoretical analysis of offline parameter tuning has not seen many contributions so far [27–30]. These papers consider the setting of finding the optimal mutation strength for standard bit mutation as well as *k*-bit flip mutation on different theoretical benchmarks. The methods studied are capable to find the optimal rate efficiently.

**Dynamic rate distributions.** Some algorithms change the distribution for choosing the mutation rate during the optimization process [31]. While this technically allows for complex distributions, to the best of our knowledge, most algorithms that fall into this category distribute the probability mass around a single rate.
A common approach is the 1/5 success rule (e.g., [32–34]), which increases the current rate if more than one fifth of the last tries with the current rate are successful, and it decreases it otherwise. While this approach automatically adjusts the rate to one for finding an improving solution, it forgets the previously used rate and, instead, aims to rediscover it if it becomes useful again later.

A more deterministic approach to a similar idea is stagnation detection [2, 35]. This operator starts with the smallest rate and picks it repeatedly until the algorithm is certain with high probability that it cannot find an improving solution with the current rate. It then increases the rate and repeats the process. This approach has the benefit that it can escape local optima very well. However, similar to the one-fifth success rule, the algorithm focuses on a single rate, meaning that it needs to rediscover previously good rates. This problem was addressed partially by adding a radius memory to the algorithm [6], which saves the last successful rate in order to re-use it. However, if more than a single previous rate are useful, this approach falls back to the problem of the initial algorithm.

Another, very recent approach [5] proposes to combine stagnation detection with fast mutation in the following way: The algorithm follows classic stagnation detection but does not always create a solution with the current mutation rate; it also has a chance of picking a mutation rate from a heavy-tailed distribution around the current rate. This proves very effective in escaping certain local optima where there are many improving solutions at a further distance [5]. The resulting runtime is better than that of classic stagnation detection and thus also than that of the flex-EA. However, we believe that this variant still has problems of re-using previously good rates, as it does not save them.

**Self-adaptation.** Self-adaptation augments solutions with a mutation rate that determines the rate to use when mutating the solution. Furthermore, the mutation rate of each solution is itself subject to mutation, following a different distribution than the
one for the solution. As a consequence, good mutation rates show up more frequently in
a population and thus guide the search. Self-adaptation has been studied theoretically
in a variety of contexts, often for non-elitist algorithms [36] but also from a multi-
objective perspective [37]. Self-adaptation can improve the tolerance of an algorithm
to noise [38], is beneficial for tracking dynamic optima [39], helps for problems of
unknown structure [40], and is capable of finding optimal parameter values [41]. The
main idea of the flex-EA is similar to self-adaptation in the sense that the flex-EA
also stores multiple beneficial mutation rates. However, in contrast to self-adaptation,
the flex-EA decouples the rates from the individuals, and it allows to choose *any* rate
at any point in time, although non-beneficial rates only have a low likelihood of being
chosen.

**Learning-based algorithms.** Doerr et al. [42] propose an algorithm that chooses its mutation rate according to a distribution that is adjusted over time. This adjustment follows the idea of reinforcement learning and incorporates information from many past iterations. A related concept are *hyper-heuristics*, e.g., [43, 44], which are algorithms that aim at selecting in each iteration an algorithm that is best suited for the current state. This choice is based on the previously observed performance of the algorithms to select from.

The flex-EA is similar to these approaches, with the main difference that it updates
its mutation rate distribution in a simpler way. This simplification allows a rigorous
analysis of the flex-EA on a wide variety of problems while still performing very well.

3 Preliminaries

The natural numbers $\mathbb{N}$ include 0. For $a, b \in \mathbb{R}$, let $[a..b] = [a,b] \cap \mathbb{N}$, and let $[a] = [1..a]$.
By $\log(\cdot)$ we denote the binary logarithm.

We consider pseudo-Boolean optimization, that is, for a given $n \in \mathbb{N}_{\ge 1}$, the opti-
mization of functions $f: \{0,1\}^n \to \mathbb{R}$. We call $f$ a *fitness function*, and we assume
that $n$ is given implicitly. When using big-O notation, we assume asymptotics in this
implicit $n$. Furthermore, we call each $\boldsymbol{x} \in \{0,1\}^n$ an *individual*, and $f(\boldsymbol{x})$ its *fitness*.
For each $i \in \mathbb{N}$, let $\boldsymbol{x}_i$ denote the value of $\boldsymbol{x}$ at position $i$. Last, let $|\boldsymbol{x}|_1$ be the number
of 1s of $\boldsymbol{x}$, and $|\boldsymbol{x}|_0$ its number of 0s.

For each $\boldsymbol{x}, \boldsymbol{y} \in \{0,1\}^n$, let $d_H(\boldsymbol{x}, \boldsymbol{y}) = |\{i \in \mathbb{N} \mid \boldsymbol{x}_i \neq \boldsymbol{y}_i\}|$ denote the Hamming
distance of $\boldsymbol{x}$ and $\boldsymbol{y}$. For each $r \in [n]$, we define the $r$-bit flip neighborhood of $\boldsymbol{x}$ to be
the set $\{\boldsymbol{y} \in \{0,1\}^n \mid d_H(\boldsymbol{x}, \boldsymbol{y}) = r\}$.

Given a fitness function $f$ and an algorithm $A$ optimizing $f$, we define the *runtime* of $A$ on $f$ as the (random) number of evaluations of $f$ until the first time that an optimum of $f$ is evaluated. To this end, we assume that each individual that $A$ creates is evaluated exactly once. For the flex-EA in Section 4, the runtime is essentially the number of iterations until an optimum is created for the first time (plus one, due to the initialization).

**3.1 Mathematical Tools**

In our proofs, we make use of the following established methods.

**3.1.1 Fitness Level Method**

The fitness level method was introduced by Wegener [45] for the analysis of evolution-
ary algorithms on a given fitness function $f$. It requires a partition $(L_i)_{i \in [m]}$ of the
search space $\{0,1\}^n$ (with $m, n \in \mathbb{N}_{\ge 1}$) such that the fitness increases in each level.
That is, for all $i \in [m-1]$ and all $\boldsymbol{x} \in L_i$ and $\boldsymbol{y} \in L_{i+1}$, it holds that $f(\boldsymbol{x}) < f(\boldsymbol{y})$.
We call such a partition a *fitness level partition* and its elements *fitness levels*.

The following theorem by Sudholt [46] is used in the proof of Theorem 4.

**Theorem 1** ([46, Theorem 2]). Let $f$ be a pseudo-Boolean function, let $m \in \mathbb{N}_{\ge 1}$, and let $(L_i)_{i \in [m]}$ be a fitness level partition of $f$. Let $A$ be an elitist search algorithm, and, for all $i \in [m-1]$, let $s_i$ denote a lower bound on the probability of $A$ creating a
new search point in $\bigcup_{j \in [i+1..m]} L_j$, provided that the best individual created so far by $A$ is in $L_i$. Then the expected optimization time of $A$ on $f$ (without the initialization) is at most $\sum_{i \in [m-1]} \frac{1}{s_i}$.

### 3.1.2 Partial Sums of Binomial Coefficients

The following lemma by Rajabi and Witt [6] is used in the proof of Theorem 6.

**Lemma 2** ([6, Lemma 1 (a)]). Let $n, k \in \mathbb{N}$ with $k \le \frac{n}{2}$. Then $\sum_{i \in [k]} \binom{n}{i} \le \frac{n-(k-1)}{n-(2k-1)} \binom{n}{k}$.

### 3.1.3 Drift Analysis

Drift analysis is the most prominent mathematical tool for analyzing evolutionary algorithms. It was introduced by He and Yao [47]. We use the following theorem by Doerr et al. [48] in the proof of Theorem 8, presented in a version close to the one by Kötzing and Krejca [49]. The tail bound can be found in [50] and [51].

**Theorem 3** ([48, Theorem 3]). Let $(X_t)_{t \in \mathbb{N}}$ be a Markov chain over $\mathbb{R}_{\ge 0}$, and let $T = \inf\{t \in \mathbb{N} \mid X_t < 1\}$. Suppose that there is a $\delta > 0$ such that it holds that $E[X_t - X_{t+1} | X_t] \cdot 1\{t < T\} \ge \delta X_t \cdot 1\{t < T\}$. Then $E[T] \le (1 + E[\ln(X_0)])/\delta$. Moreover, $\Pr[T \ge (E[\ln(X_0)] + r)] \le e^{-r}$.

## 4 The Flexible Evolutionary Algorithm

The flexible evolutionary algorithm (flex-EA, Algorithm 1) is an elitist (1 + 1)-type evolutionary algorithm choosing its mutation rate each iteration according to a probability distribution given by a probability vector (the frequency vector). The flex-EA updates its frequency vector in each iteration, aiming to give promising rates a high probability, while other rates have a user-defined, generally low probability. The frequency update is influenced by different factors. In the following, we first discuss the
high-level idea of the flex-EA and its different parts. Afterward, in Section 4.1, we propose good default choices for the various parameters of the algorithm. When applying these choices, the result is a basically parameter-less algorithm that can be thought of as a superposition of heavy-tailed mutation [3] and stagnation detection [2].

**High-level idea.** The update of the vector $p \in [0, 1]^n$ aims to give (mutation) rates a high probability if choosing them in the past succeeded in improving the fitness of the current solution. Such rates are called *active*, and they follow a uniform distribution, with a probability mass at most 1. All other rates are called *inactive*, and they have a low, user-defined probability to be selected. Initially, only rate 1 is active. If an active rate repeatedly fails to be successful, then the algorithm sets all rates to inactive and activates only a single rate. In this case, it enters a state called *stagnation detection*, resembling the known stagnation detection mechanism [2], explained in the following.

If a rate fails too often while in stagnation detection, the next higher rate is activated (after deactivating the current rate). If a rate is successful while in stagnation detection, then the current rate (which is the only active rate) becomes inactive and the successful rate becomes active. The algorithm then leaves the stagnation detection state, reverting back to its initial mode explained above.

In order to allow other rates to become active more easily during the run of the algorithm, each frequency has a user-defined lower bound. If a frequency would be set to a value less than its lower bound, it takes on its lower bound instead. This allows the flex-EA constantly to find new rates that are currently not exploited. In case that the active rates turn out to become bad, falling back to stagnation detection is a good alternative.

**The flex-EA in more detail.** Algorithm 1 shows the detailed flex-EA. The frequency vector is denoted by $p \in [0, 1]^n$, and the set of active rates (called the *archive*) by $A \subseteq [n]$. The lower bounds for each frequency are provided by the user to the flex-EA via the *lower-bound vector* $\ell \in [0, 1]^n$. We assume that $\sum_{i \in [n]} \ell_i \le 1$.
507 **Algorithm 1:** The flexible evolutionary algorithm (flex-EA) with given lower-bound vector $\ell$ and count bound vector $C$, maximizing a pseudo-Boolean function $f: \{0, 1\}^n \to \mathbb{R}$.
508
509
510 1 $t \leftarrow 0$;
511 2 $A^{(t)} \leftarrow \{1\}$;
512 3 stagDet $\leftarrow$ false;
513 4 **for** $i \in [n]$ **do** $c_i^{(t)} \leftarrow 0$;
514 5 $\boldsymbol{x}^{(t)} \leftarrow$ solution from $\{0, 1\}^n$ chosen uniformly at random;
515 6 **while** termination criterion not met **do**
516
517 7 $\boldsymbol{p}^{(t)} \leftarrow$ distribute probability mass, respecting $A^{(t)}$ and $\ell$ (Algorithm 2);
518 // Each inactive frequency is at its lower bound
519 8 choose $r \in [n]$ according to $\boldsymbol{p}^{(t)}$;
520 9 $\boldsymbol{y}^{(t)} \leftarrow$ copy $\boldsymbol{x}^{(t)}$ and flip $r$ bits uniformly at random in this copy;
521 10 **if** $f(\boldsymbol{y}^{(t)}) > f(\boldsymbol{x}^{(t)})$ **then**
522 11 $\boldsymbol{x}^{(t+1)} \leftarrow \boldsymbol{y}^{(t)}$;
523 12 $A^{(t+1)} \leftarrow$ **if** stagDet = false **then** $A^{(t)} \cup \{r\}$ **else** $\{r\}$;
524 13 $c_r^{(t+1)} \leftarrow 0$;
525 14 stagDet $\leftarrow$ false;
526 15 **else**
527
528 16 **if** $f(\boldsymbol{y}^{(t)}) = f(\boldsymbol{x}^{(t)})$ **then** $\boldsymbol{x}^{(t+1)} \leftarrow \boldsymbol{y}^{(t)}$;
529 17 **if** $r \in A^{(t)}$ **then**
530 18 $c_r^{(t+1)} \leftarrow c_r^{(t)} + 1$;
531 19 **if** $c_r^{(t+1)} \ge C_r$ **then**
532 20 $r' \leftarrow$ **if** stagDet = true and $r \ne n$ **then** $r + 1$ **else** 1;
533 21 $A^{(t+1)} \leftarrow \{r'\}$;
534 22 $c_{r'}^{(t+1)} \leftarrow 0$;
535 23 stagDet = true;
536 24 $t \leftarrow t + 1$;
537
538
539
540
541 Each rate $i \in [n]$ has a counter $c_i \in \mathbb{N}$ for counting its number of failed attempts
542 to improve the current solution while rate $i$ is active. If $c_i$ reaches a user-defined max-
543 imum $C_i \in \mathbb{R}_{\ge 0}$, all frequencies become inactive, and a single frequency is activated.
544
545 Note that each inactive frequency is at its lower bound. The maxima for the counters
546 are provided by the user as the count bound vector $C \in \mathbb{R}_{\ge 0}^n$. The moment a max-
547 imum is reached, the single new active frequency is chosen with respect to whether
548
549 the flex-EA is in stagnation detection mode or not. If it is not in stagnation detection
550
551
552
mode, the new active frequency is 1, initializing stagnation detection. If it is in stagnation detection mode, there is exactly a single active frequency $i \in [n]$, and the new active frequency is $i + 1$ (identifying $n + 1$ with 1). Regardless of which of these two cases occurs, whenever a counter reaches its maximum, the flex-EA enters stagnation detection mode.

The only way to leave stagnation detection mode is to improve the currently best solution. Whenever an improvement is found, the flex-EA adds the rate that led to this improvement to the archive. If this improvement is found during stagnation detection, the successful rate replaces the currently only active rate. If the improvement is found otherwise, the successful rate is added to all active rates instead. Regardless of which of these two cases occurs, whenever an improvement is found, the flex-EA leaves stagnation detection mode.

The update of the frequency vector is a bit involved, as frequencies may be capped by their respective lower bound. Note that the flex-EA aims to give each active frequency the same probability, whereas inactive frequencies remain at their lower bound. The total probability to distribute among the $|A| =: \varphi$ active frequencies is $1 - \sum_{i \in [n] \setminus A} \ell_i =: M$, as all inactive frequencies are at their respective lower bound. Hence, each active frequency should get a probability of $M/\varphi$. In order to account for the lower bounds of the active frequencies, the active frequencies are adjusted sequentially, starting with the largest lower bound, going to the smallest. If the lower bound of the first frequency is less than the intended value $M/\varphi$, then all active frequencies get this value. Otherwise, the first frequency is set to its lower bound, and the remaining probability mass is adjusted. This process is repeated. Consequently, when having already fixed $i \in [\varphi]$ frequencies, the remaining probability mass $M$ (which is different from the initial $M$) needs to be distributed only among $\varphi - i + 1$ frequencies.

**Algorithm 2** shows this approach algorithmically. We note that the algorithm is presented in a way that aims to easily understand the logic of the update. It is not
**Algorithm 2:** The algorithm that, given an index set $A \subseteq [n]$ and a lower-bound vector $\ell$ of size $n$, returns a frequency vector $p$ of size $n$ where all possible probability mass is distributed as evenly as possible over the frequencies with indices in $A$, respecting $\ell$.

1 $M \leftarrow 1 - \sum_{i \in [n] \setminus A} \ell_i$;

2 **for** $i \in [n] \setminus A$ **do** $p_i \leftarrow \ell_i$; // Each frequency is at least its lower bound

3 $\varphi \leftarrow |A|$;

4 $(S_i)_{i \in [\varphi]} \leftarrow A$ sorted in descending order by $\ell$;

5 **for** $i \in [\varphi]$ **do** // Aim for a uniform distribution of $M$, considering $(S_j)_{j \in [i..\varphi]}$

6 $\left| \left. \begin{array}{l} \text{if } \ell_{S_i} \le \frac{M}{\varphi - i + 1} \text{ then } \text{Check if a uniform distribution is not capped off} \\ \text{for } j \in [i..\varphi] \text{ do } p_{S_j} \leftarrow \frac{M}{\varphi - i + 1}; \end{array} \right| \right|$

7

8 **return** $p$;

9 **else** // Use the lower bound, update remaining mass

10 $p_{S_i} \leftarrow \ell_{S_i}$;

11 $M \leftarrow M - \ell_{S_i}$;

12 **return** $p$;

optimized for efficiency. A more efficient implementation would make use of a data structure for the archive that quickly allows to add and delete indices while keeping them ordered with respect to their lower bound. This can be achieved, for example, with a balanced search tree.

## 4.1 Recommended Parameter Choices

The flex-EA requires the user to provide $2n$ parameters, which can be daunting. Hence, we propose a recommendation that works well in many cases, as we prove in most of the following sections. For the lower-bounds vector $\ell$, we recommend to choose a heavy-tailed distribution, inspired by the fast-mutation operator [3]. For the count bound vector $C$, we recommend to choose the same values as for stagnation detection [2]. We explain both recommendations in more detail below and then briefly discuss the resulting algorithm.

**Heavy-tailed lower bounds.** Let $\beta \in (1, 2)$ (called the power-law exponent), and let $N: (1, 2) \to \mathbb{R}_{\ge 1}$ denote a normalization with $N: \alpha \mapsto \sum_{i \in [n]} i^{-\alpha}$. We recommend
for all $i \in [n]$ to choose

$$ \ell_i = \frac{1}{2N(\beta)} i^{-\beta}. \qquad (1) $$

Note that $\sum_{i \in [n]} \ell_i = \frac{1}{2}$. Hence, the flex-EA still has a probability mass of $\frac{1}{2}$ remaining to distribute among the active frequencies.

This recommendation follows the ideas of *fast mutation*, introduced in [3]. This mutation operator first chooses a rate $r \in [n]$ according to a heavy-tailed distribution and performs standard bit mutation afterward. That is, it flips each bit of a given individual independently with probability $\frac{r}{n}$. Doerr et al. [3] name the variant of the (1+1) EA that uses fast mutation the Fast (1+1) EA.

Doerr et al. [3] choose the heavy-tailed distribution because even large rates have a reasonable probability of at least $\frac{1}{n^2}$ of being chosen, due to $\beta < 2$. The authors show that the Fast (1+1) EA has a super-exponential runtime speed-up in the parameter $k$ compared to the classic (1+1) EA when optimizing $JUMP_k$, and the operator has seen great success in other settings (see also Section 2). Hence, we propose to also use it for the flex-EA.

**Stagnation detection bounds.** Let $R \in \mathbb{R}_{>1}$. We recommend

$$ C_i = \binom{n}{i} \ln(R) $$

for all $i \in [n]$ and call this the *standard-SD choice*.

This recommendation follows the ideas of *stagnation detection (SD)*, introduced by Rajabi and Witt [2]. In their paper, the authors introduce the algorithm $SD-RLS^r$, which is also a (1+1)-type elitist algorithm that performs the same mutation as the flex-EA but chooses its mutation rate differently in the following deterministic manner. The $SD-RLS^r$ starts with rate 1 and counts how many times it used this rate. It then uses rate 1 for at most $C_1$ iterations. If it is successful in finding a strictly improving solution during this time, the algorithm resets its counter. If rate 1 is not successful,
the SD-RLS<sup>r</sup> chooses rate 2 from now on, for a total of at most $C_2$ iterations. If it is successful during this time, it resets its counter and reverts back to rate 1. Otherwise, it picks the next-higher rate and adjusts the iteration limit according to the formula above. We note that the SD-RLS<sup>r</sup> only tries out rates up to ⌊n/2⌋, but the formula for the bounds generalizes to all values in [n].

Rajabi and Witt [2] choose the bounds above because this guarantees that if rate $r \in [n]$ is currently used and there is at least one solution in Hamming distance $r$ of the currently best solution, the SD-RLS<sup>r</sup> find this improvement with probability at least $1 - R^{-1}$, as the probability of not doing so is at most $(1 - (n/r)^{-1})^{C_r} \le R^{-1}$. Hence, the value $R$ determines how unlikely it is to fail in such a case. Since the flex-EA is in some aspects similar to the SD-RLS<sup>r</sup>, we recommend to copy its bounds.

**Discussion** When considering the flex-EA with heavy-tailed lower bounds and with the standard-SD choice, it has two parameter values left to choose, namely, the power-law exponent $\beta \in (1, 2)$ as well as the parameter $R \in \mathbb{R}_{>1}$. However, the exact choice of these parameters is typically not very relevant, as we show in this article. Doerr et al. [3] recommend to choose $\beta = \frac{3}{2}$. Since the flex-EA can act similarly to the algorithm discussed by Doerr et al. [3], we recommend this choice too. For the parameter $R$, Rajabi and Witt [2] show that a choice of $R \ge n^{4+\epsilon}$ for a small constant $\epsilon > 0$, with $R$ being a polynomial, is usually sufficient. We show in our results below that this is also the case for the flex-EA.

Since we provide recommendations for the only two parameter choices left, we consider the flex-EA to be an essentially parameter-less algorithm when following these recommendations. However, one needs to keep in mind that the flex-EA allows to choose its parameters $\ell$ and $C$ more flexibly, which can be a good choice if given extra information (see also Section 7).

732
733
734
735
736
# 5 Runtime on Unimodal Functions

We analyze the flex-EA on unimodal pseudo-Boolean functions, that is, functions $f: \{0, 1\}^n \to \mathbb{R}$ with a unique global optimum $z^* \in \{0, 1\}^n$ such that, for all $x \in \{0, 1\}^n \setminus \{z^*\}$, there is a $y \in \{0, 1\}^n$ with $d_H(x, y) = 1$ such that $f(x) < f(y)$. For each unimodal function $f$, we call the cardinality of the range of $f$ the number of fitness levels of $f$, and each set of all individuals of the same fitness a fitness level. Each individual (besides the global optimum) has at least one neighbor in a fitness level of better fitness.

The flex-EA optimizes unimodal functions efficiently in expectation if its parameters are chosen well. To this end, we rely exclusively on the lower bound of rate 1.

**Theorem 4.** Let $f$ be a unimodal fitness function with $L$ fitness levels. For all $j \in [L-1]$, let $q_j$ denote a lower bound on the probability that, given an individual $z$ in fitness level $j$, flipping a single bit in $z$ creates an offspring with strictly better fitness. Furthermore, consider the flex-EA with $\ell_1 > 0$.

Then the expected runtime of the flex-EA on $f$ is at most

$$1 + \ell_1^{-1} \sum_{j \in [L-1]} q_j^{-1}.$$

In particular, it is at most $1 + n(L-1)\ell_1^{-1}$.

*Proof.* We start with the first claim. The plus 1 is for initialization. For the remaining bound, we apply the fitness level method (Theorem 1). Let $j \in [L-1]$ be the fitness level of the current solution of the flex-EA. In order to leave level $j$, it is sufficient to choose rate 1 and then create an offspring with strictly better fitness. The probability of the former is $\ell_1$, and the one of the latter is at least $q_j$. Since these events are independent, the flex-EA leaves level $j$ with a probability of at least $\ell_1 q_j$. This concludes this case.
For the second claim, note that since $f$ is unimodal, there is always at least one improving solution that only requires a single bit to be flipped. Hence, it holds that $q_j \ge \frac{1}{n}$. Applying the first claim concludes the proof. □

**Theorem 4** leads to useful bounds on various functions. For example, the coarser bound at the end already leads to the common expected runtime of $O(n^2)$ for the LEADINGONES benchmark [52] if we assume a constant lower bound for rate 1, as is the case with heavy-tailed lower bounds. For functions where the probability of leaving a fitness level depends on the current state, we need to estimate these transition probabilities more carefully. Doing so leads to an expected runtime bound of $O(n \log n)$ for the well-known ONEMAX benchmark (Theorem 5), which we abbreviate as OM and which is defined as $OM: \{0, 1\}^n \to [0..n], \boldsymbol{x} \to |\boldsymbol{x}|_1$.

Since we require bounds for similar functions in the following sections, we introduce a slight generalization of ONEMAX and analyze it instead.

For all $k \in [0..n]$, let trimmed ONEMAX ($\text{trimOM}_k$, Figure 1a) be defined as

$$ \boldsymbol{x} \mapsto \begin{cases} k + \text{OM}(\boldsymbol{x}) & \text{if } |\boldsymbol{x}|_1 \le n-k, \\ n - \text{OM}(\boldsymbol{x}) & \text{else.} \end{cases} \qquad (2) $$

Note that $\text{trimOM}_k$ is a unimodal function with $n+1$ fitness levels. Its global optimum is achieved for all individuals with exactly $n-k$ 1s. The case $k=0$ results in ONEMAX. We get the following bound.

**Theorem 5.** Let $k \in [0..n]$. Consider the flex-EA with $\ell_1 > 0$ optimizing $\text{trimOM}_k$. Then the expected runtime is $O(\ell_1^{-1}n \log(n))$.

*Proof.* We apply Theorem 4 and use its notation. For all $j \in [n+1]$, let fitness level $j$ be composed of all individuals with a $\text{trimOM}_k$-value of $j-1$. We say that individuals with at most $n-k$ 1s are on the left branch of the function, and the other ones on the right branch.
<figure><img src="image_2.png" /><figcaption>(a) The trimOM<sub>k</sub> function (equation (2)) with parameter *k* ∈ [0..*n*]. It resembles the well-known JUMP function but without the global maximum at the all-1s string. Hence, each individual with exactly *n* − *k* 1s is a global optimum.</figcaption></figure>

<caption>(b) The TWO RATES function (equation (5)) with parameters *s* := (7/8)*n* − √*n* and *g* := (2/3) log *n*. The function follows a ONEMAX slope until the individuals have exactly *s* 1s. Afterward, improving solutions are at Hamming distances 2*g* and *g*, in alternating fashion, for a total range of √*n*. Then, the function continues with a ONEMAX slope. The unique global optimum is the all-1s string.</caption>

**Fig. 1:** The two benchmark functions trimOM<sub>k</sub> (equation (2)) and TWO RATES (equation (5)) that we introduce. The value *n* ∈ N<sub>≥1</sub> denotes the problem size. The plots above are just meant to convey a qualitative impression of each benchmark, not a numerically exact example. The *x*-axis denotes the number of 1s of the argument of the function.

Let *j* ∈ [*n*]. We bound *q*<sub>*j*</sub> with respect to whether the current individual is on the left or the right branch. If it is on the left branch, it has *j* − 1 − *k* 1s. If mutation flips any of the *n* − *j* + 1 + *k* 0s, then the result strictly improves the fitness. Hence, *q*<sub>*j*</sub> = *n*−*j*+1+*k*/*n*.

If the current individual is on the right branch, it has *n* − *j* + 1 1s. If mutation
flips any of these 1s, then the result strictly improves the fitness. Hence, *q*<sub>*j*</sub> = *n*−*j*+1/*n*.
Combining both cases, by Theorem 4 and disregarding the plus 1, we obtain an upper bound on the expected runtime of

$$ \ell_1^{-1} \sum_{j \in [n]} \left( \frac{n}{n-j+1+k} \cdot 1\{j \ge k+1\} + \frac{n}{n-j+1} \cdot 1\{j < k+1\} \right) \\ \le \ell_1^{-1} \cdot 2n \sum_{j \in [n]} j^{-1} = O(\ell_1^{-1} n \log(n)). \quad \square $$

We note that the flex-EA is a unary unbiased algorithm in the sense of Lehre and Witt [4], since it solely relies on k-bit flip mutation, which is a unary unbiased operator. Since unary unbiased algorithms have a lower bound of $\Omega(n \log n)$ on ONE-MAX, it follows for the flex-EA with $\ell_1 = \Theta(1)$ that the upper bound in Theorem 5 is asymptotically tight.

# 6 Runtime on Jump Functions

We consider the well-known JUMP benchmark, which, for all $k \in [n]$ is defined as

$$ x \mapsto \begin{cases} k + \text{OM}(x) & \text{if } |x|_1 \in [0..n-k] \cup \{n\}, \\ n - \text{OM}(x) & \text{else.} \end{cases} $$

This function is identical to trimmed ONE-MAX (trimOM$_k$) except that its unique global optimum is at the all-1s bit string. Consequently, the individuals with exactly $n-k$ 1s are all local optima. The set of all local optima is often called the plateau of the function. For elitist algorithms, in order to leave the plateau, exactly all $k$ 0s of an individual need to be changed into a 1, which requires, in expectation, at least $\binom{n}{k}$ tries for unbiased algorithms with unary mutation [5].

With Theorem 7, we show that the flex-EA with the recommended parameter choices optimizes JUMP in this time. Beforehand, we prove a runtime bound for a more general parametrization.
**Theorem 6.** Let $R \in \mathbb{R}_{>1}$ and $k \in [2..n]$. Consider the flex-EA on JUMP$_k$ with the standard-SD choice C with parameter R and with lower bounds $\ell$ such that $\ell_1, \ell_k > 0$ and $1 - \sum_{i \in [n]} \ell_i = \Theta(1)$. Let $L = (1 - \sum_{i \in [n] \setminus \{k\}} \ell_i)^{-1}$. Then the expected runtime is at most

$$O(n\ell_1^{-1} \log(nR)) + \binom{n}{k} \cdot \min \left\{ \ell_k^{-1}, L + \ell_k^{-1}(R^{-1/L} + R^{-\ell_1}) + O\left(\frac{k}{n-2k+3} \log(R)\right) \cdot \mathbf{1}\left\{k \le \frac{n}{2}\right\} + \frac{2^n}{\binom{n}{k}} \ln(R) \cdot \mathbf{1}\left\{k > \frac{n}{2}\right\} \right\}.$$

*Proof.* Let $T$ denote the runtime of the algorithm on JUMP$_k$. We split $T$ into the following two phases: Phase 1 considers the time until the current solution of the algorithm has a fitness of at least $n$, that is, the current solution is on the plateau or optimal. Phase 2 starts in the same iteration in which phase 1 stops, and it considers the time until the current solution is optimal. Let $T_1$ and $T_2$ denote the runtimes of the respective phases. By the linearity of expectation and by $T = T_1 + T_2$, it holds that $E[T] = E[T_1] + E[T_2]$. We consider the expectations of both phases separately.

**Phase 1.** Note that the time until the algorithm finds an optimum of trimOM$_k$ is an upper bound for $T_1$. Hence, the same is true for their expectations. By Theorem 5, we obtain $E[T_1] = O(\ell_1^{-1}n \log(n))$.

**Phase 2.** We make a case distinction with respect to the event $D$ that rate 1 is active in iteration $T_1$. In case it is not active, we bound the expected time for phase 2 by relying exclusively on $\ell_k$, which is a general upper bound for this phase. In case that rate 1 is active in iteration $T_1$, we wait until the counter of rate 1 exceeds its maximum. Afterward, the archive contains exactly one active rate, and activates rates in increasing order. We wait until rate $k$ is active and then estimate the time it takes to find the optimum.
967 Relying on rate $\ell_k$ (covering that event $\overline{D}$ occurs). Since the probability
968 for choosing rate $k$ is in each iteration at least $\ell_k$ and since the current individual
969 has exactly $k$ 0s, the probability to mutate it into the optimum when flipping $k$
970 bits is $\binom{n}{k}^{-1}$. Hence, in each iteration, the probability to create the optimum is at
971 least $\ell_k \binom{n}{k}^{-1} =: q$. Since each iteration has an independent chance to create the
972 optimum, $T_2$ follows a geometric distribution with a success probability of at least $q$.
973
974
975 Hence, $E[T_2 | \overline{D}] \le q^{-1} = \ell_k^{-1} \binom{n}{k}$.
976
977

978 We bound $\Pr[\overline{D}]$ from above by noting that a necessary condition for $\overline{D}$ is the
979 event $F$ that rate 1 (which is active in iteration 0) needs to fail $C_1$ consecutive times
980 to improve the current solution whenever rate 1 is being chosen (before iteration $T_1$).
981 Since we only consider iterations up to $T_1$, the probability that, when choosing rate 1,
982 it improves the current solution is at least $\frac{1}{n}$ because while the current solution is not
983 on the plateau, there is at least one improving solution within Hamming distance 1.
984 Thus, since rate 1 is chosen each iteration with probability at least $\ell_1$ and since
985 $C_1 = n \ln(R)$, we have $\Pr[F] \le (1 - \frac{\ell_1}{n})^{C_1} \le R^{-\ell_1}$. The bound for $\Pr[\overline{D}]$ follows from
986
987
988 $\Pr[\overline{D}] \le \Pr[F]$.
989
990
991
992
993

994 Rate 1 is active in iteration $T_1$ (event $D$ occurs). Let $T_{2,1}$ denote the first
995 iteration, starting in $T_1$, such that a counter reaches its limit or that we find the
996 optimum. To this end, it is sufficient to consider the first iteration $\tilde{T}_{2,1}$ until the counter
997 for rate 1 reaches its limit $C_1$ (or we find the optimum), noting that, intersected
998 with $D$, we have $T_{2,1} \le \tilde{T}_{2,1}$. In order for the counter for rate 1 to reach its limit, rate 1
999
1000 still needs to be chosen $m \in [C_1]$ times, since each time any rate but $k$ is chosen, it
1001 cannot find an improvement and the counter is thus increased. Since rate 1 is chosen
1002 in each iteration independently with probability at least $\ell_1$, it takes in expectation
1003 at most $\ell_1^{-1}$ iterations to increase the counter for rate 1 by one. Since we repeat this
1004
1005
1006
1007
1008 $m \le C_1$ times, it follows that $E[\tilde{T}_{2,1} | D] \le C_1 \ell_1^{-1}$ and thus $E[T_{2,1} | D] \le C_1 \ell_1^{-1}$.
1009
1010
1011
1012

1010
1011
1012
Let $T_{2,2}$ be the first time, starting in iteration $T_{2,1}$, that rate $k$ is active or we find the optimum. Since a counter reached its limit in $T_{2,1}$ and since rate 1 is active in iteration $T_{2,1}$ (as it is active in iteration $T_1$), it follows that there is exactly one rate active in the following iteration, which is either rate 1 or rate 2. Since no rate but rate $k$ can create the optimum in all following iterations and since only a single rate is active, as the algorithm is in stagnation detection mode, the counter of an active rate is always increased until rate $k$ becomes active. Let $L' = \sum_{i \in [n]} \ell_i$. Since active rate $i \in [k-1]$ is chosen independently with probability $1 - \sum_{j \in [n] \setminus \{i\}} \ell_j \ge 1 - L'$ during a single iteration and since $C_i = \binom{n}{i} \ln(R)$, it takes in expectation at most $(1-L')^{-1} \binom{n}{i} \ln(R) = \Theta(1) \binom{n}{i} \ln(R)$ iterations until rate $i+1$ is active. Since rates become active consecutively and since there are at most $k-1$ rates that need to become active before rate $k$ is active, it follows that $E[T_{2,1} | D] \le \Theta(1) \sum_{i \in [k-1]} \binom{n}{i} \ln(R)$. For $k \le \frac{n}{2}$, we obtain by Lemma 2

$$ 
\begin{aligned}
\sum_{i \in [k-1]} \binom{n}{i} \ln(R) &\le \frac{n-(k-2)}{n-(2k-3)} \binom{n}{k-1} \ln(R) \\
&= \frac{n-(k-2)}{n-(2k-3)} \frac{k}{n-k+1} \binom{n}{k} \ln(R) \\
&= O\left(\frac{k}{n-2k+3}\right) \binom{n}{k} \ln(R).
\end{aligned}
$$

For $k > \frac{n}{2}$, we obtain $\sum_{i \in [k-1]} \binom{n}{i} \ln(R) \le 2^n \ln(R)$.

Consequently, for $\gamma := O\left(\frac{k}{n-2k+3}\right) \binom{n}{k} \cdot 1\{k \le \frac{n}{2}\} + 2^n \cdot 1\{k > \frac{n}{2}\}$, it follows that $E[T_{2,2} | D] \le \gamma \ln(R)$.

Last, we bound the remaining time $T_{2,3}$, starting in iteration $T_{2,2}$, until the optimum is found. For bounding the expectation of $T_{2,3}$, we make a case distinction with respect to the event $S$ that the algorithm samples the optimum within the next $C_k = \binom{n}{k} \ln(R)$ iterations. If rate $k$ is active, the probability (unconditional on $S$) to create the optimum in a single iteration is $(1 - \sum_{i \in [n] \setminus \{k\}} \ell_i) \cdot \binom{n}{k}^{-1} = L^{-1} \binom{n}{k}^{-1}$. The process of creating the optimum, conditional on $S$, follows a truncated geometric
distribution [2] and is dominated by a geometric distribution with success probability $L^{-1} \binom{n}{k}^{-1}$, since the actual process stops after at most $C_k$ attempts. Hence, $E[T_{2,3} | D, S] \le L \binom{n}{k}$.

In the case that $S$ does not occur, we use the result from when we rely only on $\ell_k$ (noting that it is always applicable) and obtain $E[T_{2,3} | D, \bar{S}] \le \ell_k^{-1} \binom{n}{k}$.

Next, we trivially bound $\Pr[D, S] \le 1$ as well as $\Pr[D, \bar{S}] \le \Pr[\bar{S} | D]$. By the definition of $S$, the estimates above of finding the optimum in a single iteration, as well as that $\binom{n}{k} = C_k / \ln(R)$ due to the standard-SD choice, we have

$$ \Pr[\bar{S} | D] \le (1 - L^{-1} \binom{n}{k}^{-1})^{C_k} = (1 - L^{-1} (C_k / \ln(R))^{-1})^{C_k} \le e^{-\ln(R)/L} = R^{-1/L}. $$

Thus, we obtain overall

$$ E[T_2 | D] \le \frac{C_1}{\ell_1} + \gamma \ln(R) + L \binom{n}{k} + \ell_k^{-1} \binom{n}{k} R^{-1/L}. \quad (3) $$

**Concluding phase 2.** By $E[T_2] = E[T_2 | \bar{D}] \Pr[\bar{D}] + E[T_2 | D] \Pr[D]$, by equation (3) with the trivial bound $\Pr[D] \le 1$, and by $E[T_2 | \bar{D}] \Pr[\bar{D}] \le \ell_k^{-1} \binom{n}{k} R^{-\ell_1}$ from the beginning of the proof, we obtain the desired bound for $E[T_2]$, where we note that the term $C_1/\ell_1$ is subsumed by $E[T_1]$ in the overall runtime bound for $E[T]$. Since relying solely on $\ell_k$ is also a general upper bound for $E[T_2]$, we bound its expected value by the minimum of this case and the bound in the previous sentence. This concludes the proof. $\square$

Theorem 6 shows the intricate interplay of the parameters of the flex-EA. For $k > n/2$, the value of the lower bound for rate $k$ has a huge impact on the expected runtime, as it is better to choose rate $k$ due to its lower bound than to wait for it to become the solely active rate. The latter requires to wait in for a number of steps the order of at least the central binomial coefficient, which is exponential in $n$.
In contrast, if $k \le \frac{n}{2}$ is sufficiently small, the value $L$ of all probability mass put on rate $k$, except for the lower bounds, plays an important role, as it can speed up the process of choosing rate $k$. If the optimum is not found when rate $k$ is active, the algorithm uses the lower bound of rate $k$ again. However, choosing the parameter $R$ sufficiently large makes it unlikely that this case occurs.

The following theorem summarizes how the expected runtime improves with the recommended parameter choices. Up to a factor of $2+o(1)$, the result is asymptotically optimal if $k$ is sufficiently far away from $\frac{n}{2}$. The factor of 2 is a result of the lower-bound vector $\ell$, whose total probability mass adds up to $\frac{1}{2}$ in the recommended setting. Hence, even if rate $k$ is the only active rate, the probability of choosing it is only about $\frac{1}{2}$.

**Theorem 7.** Recall the definition of $N$ from equation (1). Let $\beta \in (1, 2)$ and $\varepsilon \in \mathbb{R}_{>0}$ be constants, let $R = n^{2N(\beta)(\beta+\varepsilon)}$, and let $k \in [2..n]$. Consider the flex-EA on $JUMP_k$ with the standard-SD choice $C$ with parameter $R$ and with heavy-tailed lower bounds $\ell$. Then the expected runtime is at most

$$ (1 + o(1)) \binom{n}{k} \cdot \min \left\{ 2N(\beta)k^{\beta}, \ 2 + O(n^{-\varepsilon}) \right. \\ \left. + O\left(\frac{k}{n-2k+3} \log(n)\right) \cdot 1\left\{k \le \frac{n}{2}\right\} + \frac{2^n}{\binom{n}{k}} \ln(R) \cdot 1\left\{k > \frac{n}{2}\right\} \right\}. $$

In particular, for $k = o(\frac{n}{\log(n)})$, this simplifies to $(2 + o(1))\binom{n}{k}$.

**Proof.** The first bound follows from Theorem 6. Due to the assumptions on $\ell$, it holds that $\ell_1^{-1} = 2N(\beta) = \Theta(1)$, that $\ell_k = \frac{1}{2N(\beta)}k^{-\beta}$, and that $1 - \sum_{i \in [n] \setminus \{k\}} \ell_i \ge \frac{1}{2}$. Furthermore, due to the choice of $R$, it follows that $O(n\ell_1^{-1} \log(nR)) = O(n \log(n))$. Since $k \ge 2$, the other summand is $\Omega(n^2)$, so the summand $O(n\ell_1^{-1} \log(nR))$ is of lower order. Moreover, since $L^{-1} \ge \frac{1}{2}$, it follows that $R^{-1/L} \le R^{-1/2} = n^{-N(\beta)(\beta+\varepsilon)} \le n^{-(\beta+\varepsilon)}$. Similarly, $R^{-\ell_1} = R^{-1/(2N(\beta))} = n^{-(\beta+\varepsilon)}$. Hence, $\ell_k^{-1}(R^{-1/L} + R^{-\ell_1}) \le 1150$
1151 $4N(\beta)k^\beta n^{-(\beta+\varepsilon)} \le 4N(\beta)n^{-\varepsilon} = O(n^{-\varepsilon})$. Substituting all of the values yields the
1152 desired result.
1153

1154 For the case $k = o(\frac{n}{\log(n)})$, note that $\frac{k}{n-2k+3} \log(n) = o(1)$. Hence, the second
1155 term in the minimum is $(2+o(1))\binom{n}{k}$. This term is smaller than the first term in the
1156 minimum, since $N(\beta) \ge 1$ as well as $k^\beta \ge 2$, concluding the proof. $\square$
1157
1158

1159

1160

1161

# 7 Benefits of the Rate Archive on Minimum Spanning Trees

1162

1163

1164

1165

1166

1167

1168

1169

1170

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187

1188

1189

1190

1191

1192

1193

1194

1195

1196

The prior works on SD-RLS<sup>r</sup> (i. e., RLS with a classical stagnation detection mechanism) in [2] and on SD-RLS<sup>m</sup>, a variant with a radius memory, in [6] include analyses of the algorithms on the classical minimum spanning tree (MST) problem. Interestingly, both stagnation detection algorithms find optimal solutions to the problem in efficient polynomial expected time (see detailed expressions below), which stands in contrast to the bound O(m<sup>2</sup>(log n + log w<sub>max</sub>)), where n is the number of vertices, m the number of edges and w<sub>max</sub> is the largest edge weight, from the seminal work [53] analyzing the (1+1) EA on the MST problem. It is well known [54] that the dependency of the bound on w<sub>max</sub> can be removed and that the runtime bound O(m<sup>3</sup> ln n) is obtained by studying the (1+1) EA on a rank-equivalent fitness function. However, even that bound is probably far from tight. Before that, polynomial bounds were only known for randomized local search algorithms with 1- and 2-bit flip neighborhoods, but not for globally searching algorithms.

In this section, we will analyze the flex-EA on the MST problem and prove results matching the best classical stagnation detection algorithm. The setting is as follows. Given is an undirected, weighted graph $G = (V, E)$, where $n = |V|$, $m = |E|$, and the weight of edge $e_i$, where $i \in [m]$, is a positive integer $w_i$. Let $c(x)$ denote the number of connected components in the subgraph described by the search point $x \in \{0, 1\}^m$, where for all $i \in [m]$, we have that $x_i = 1$ if and only if the graph implied by $x$ contains
edge $e_i$. The fitness function $f: \{0,1\}^m \to \mathbb{R}$ considered in [53], to be minimized, is defined by

$$f(x) := M^2(c(x) - 1) + M \left( \sum_{i \in [m]} x_i - (n-1) \right) + \sum_{i \in [m]} w_i x_i \quad (4)$$

for an integer $M \ge n^2 w_{\max}$, where $w_{\max}$ denotes the largest edge weight. Hence, $f$ returns the total weight of a given spanning tree and penalizes unconnected graphs as well as graphs containing cycles so that such graphs are always inferior than spanning trees. The authors of [2] showed that SD-RLS$^r$ starting with an arbitrary spanning tree finds an MST in $(1+o(1))(m^2 \ln m + (4m \ln m)E[S])$ fitness calls, where $E[S]$ is the expected number of strict improvements. The variant SD-RLS$^m$ with radius memory analyzed in [6] has an expected runtime of at most

$$(1+o(1))\left(\frac{m^2}{2}(1+\ln(\sum_{i \in [m]} r_i))\right) \le (1+o(1))(m^2 \ln m),$$

where $r_i$ is the rank of the $i$th edge in the sequence sorted by increasing edge weights. This holds since SD-RLS$^m$ for a sufficiently long time only flips two bits uniformly at random; then its stochastic search trajectory on the given MST instance is indistinguishable from an instance, where the $i$-largest weight from the original set $\{w_j\}_{j \in [m]}$ is replaced by the rank number $r_i$ [55]. Essentially, the bound for SD-RLS$^m$ is better by a factor of 2 than for the classical RLS$^{1,2}$ algorithm choosing uniformly at random a rate $r \in \{1,2\}$ and flipping $r$ bits uniformly. In fact, RLS$^{1,2}$ wastes every second step since 1-bit flips are never accepted on spanning trees.

We obtain Theorem 8 below. Choosing $\ell_1 = o(1)$, it matches the bound from [6]. While it does not improve the bound, which seems to be the best obtainable with the present methods, it shows the robustness of the flex-EA and features a simpler analysis
than in [6]. Finally, it assumes a uniform starting point instead of an initialization
with a spanning tree as in [6].

We note that the parameter settings for the $C_i$ and particularly the $\ell_i$ in Theorem 8 deviate from the recommended settings discussed in Section 4.1 and used earlier in this paper. In fact, we take a gray-box perspective here and use a minor amount of problem-specific knowledge to favor the small rates 1 and 2. Compared to the standard recommendations, we especially tone down $\ell_i$ for $i \ge 3$. This is important to show that the expected runtime is bounded as desired. If we were satisfied with a high-probability statement, then the conditions on $\ell_i$ for $i \ge 3$ could be relaxed.

**Theorem 8.** Consider an instance to the MST problem, modeled with the classical fitness function from [53] (equation (4)). Let the flex-EA with the following parameter settings run on this function:

• $C_i = cm^i \ln m$ for a sufficiently large constant $c > 0$ and $i \in \{1, 2\}$ (the other $C_i$ may be chosen arbitrarily),

• $\ell_1 = \omega(1/\log m)$ and $\ell_1 \le 1/2$,

• $\ell_2 = \Omega(1/(m^2 \log m))$, and $\ell_i = o(1/(m^5 \log^2 m))$ for $i \in [3..n]$.

Then with probability $1 - o(1)$, the runtime is at most

$$((1 - \ell_1)^{-1} + o(1)) \left( \frac{m^2}{2} \left( 1 + \ln \left( \sum_{i \in [m]} r_i \right) \right) \right) \le ((1 - \ell_1)^{-1} + o(1)) (m^2 \ln m),$$

where $r_i$ is the rank of the ith edge in the sequence sorted by increasing edge weights.

The expected runtime is bounded in the same way.

The main idea of the proof is to consider a phase of length $\Theta((1 - \ell_1)^{-1}m^2 \ln m)$ after finding the first spanning tree and to show that within the phase, the archive only contains rates 1 and 2 with high probability. Then the above-mentioned stochastic equivalence to RLS with a 2-bit flip neighborhood is applied.
Proof of Theorem 8. Similarly to the classical analysis of the (1+1) EA on the problem 1289
[53], we divide the run into three phases. The first two phases are considered jointly. 1290
They can find improvements in the 1-bit flip neighborhood by including edges (i. e., 1291
flipping zero-bits) and reducing the number of connected components or by reducing 1292
the number of edges from a fully connected subgraph by flipping one-bits. The expected 1293
number of 1-bit flips until the first phase is finished is bounded by $O(m \log m)$ in 1294
expectation, as shown in [53] using fitness-level arguments. Using tail bounds for fitness 1295
levels [56], this number is $c'm \ln m$ for some constant $c' > 0$ with probability $1 - 1300$
$O(1)$. As long as fitness improvements by 1-bit flips are still available, the expected 1301
time until choosing rate 1 is at most $1/\ell_1 = o(\log m)$, so both in expectation and 1302
with high probability after $o(m \log^2 m)$ steps a local optimum with respect to the 1- 1303
bit neighborhood has been reached and the current search point constitutes a (not 1304
necessarily minimum) spanning tree. If the constant $c$ from $C_1$ is chosen sufficiently 1305
large, then the counter $c_1^{(t)}$ does not exceed the threshold $C_1$ during the considered 1306
number of steps at rate 1 with probability at least $1 - o(1/m^2)$. Moreover, by a 1307
union bound, the probability that mutation rates higher than 2 are ever chosen in the 1308
considered period is 1309

$$O(m \log^2 m) \sum_{i=3}^{m} \ell_i = o\left(\frac{1}{m^3}\right), \qquad 1316$$

which we assume not to happen. Then no rates larger than 2 are in the archive $A^{(t)}$ 1319
at the end of the period. If rate 1 is present in the archive at that time, then we 1320
would like it to be removed since no more successes are possible at that rate. Then the 1321
counter $c_1^{(t)}$ exceeds its threshold after an expected number of $O(C_1/\ell_1) = O(m \ln^2 m)$ 1322
steps at rate 1, all of which are unsuccessful. If the stagnation detection flag is not 1323
active, subsequently the archive will be set to contain rate 2 only; otherwise rate 1 will 1324
be the only rate in the archive and this expected number of steps has to pass again 1325
until the archive consists of rate 2 only. Again, the probability of rates larger than 2 1326
entering the archive in between is $o(1/m^3)$ by the same arguments as above. 1327
1328
1329
1330
1331
1332
1333
1334
After the current search point constitutes a spanning tree for the first time, the final phase begins. Here only steps flipping an even number of bits can be accepted since disconnected graphs and graphs having more than $n-1$ edges lead to inferior fitness values. We now concentrate on 2-bit flips and aim at using multiplicative drift analysis (Theorem 3) with $g(x) = \sum_{i=1}^{m} x_i r_i$ as potential function, where $r_i$ is defined in the statement of the theorem. As shown in [55, Proof of Lemma 3], RLS flipping one or two bits uniformly at random behaves stochastically identically on the original fitness function $f$ and the function $g$, assuming a spanning tree as starting point. Hence, our plan is to choose a sufficiently large constant $c' > 0$ and to conduct the drift analysis conditional on the event that only rates 1 and 2 are chosen in a phase of predefined length $c'(1 - \ell_1)^{-1}m^2 \ln m = O(m^2 \ln^2 m)$, using $\ell_1 \le 1/2$. Note that in the phase, steps of rate 1 cannot be successful. The probability of only choosing rates at most 2 throughout this phase is at least

$$1 - O(m^2 \ln^2 m) \sum_{i=3}^{m} \ell_i = 1 - O\left(\frac{1}{m^2}\right).$$

In the following, we assume the phase to fulfill this property. We choose $c$ small enough to bound the probability of the error that $c_2^{(t)}$ exceeds its threshold $C_2$ by $O(m^{-2})$ and analyze the error case at the end of the proof.

Let $X^{(t)} := g(x_t) - g(x_{opt})$ for the current search point $x_t$ and an optimal search point $x_{opt}$. Recall that the flex-EA under the assumption of choosing only rates 1 and 2 behaves stochastically the same on the original fitness function $f$ and the potential function $g$. Moreover, we assume that only mutation rate 2 is used in every step of the considered phase. We obtain that $E[X^{(t)} - X^{(t+1)} | X^{(t)}] \ge X^{(t)}/\binom{m}{2} \ge 2X^{(t)}/m^2$ since the $g$-value can be decreased by altogether $g(x_t) - g(x_{opt})$ via a sequence of at most $\binom{m}{2}$ disjoint two-bit flips; see also the proof of Theorem 15 in [48] for the underlying combinatorial argument. Let $T$ denote the number of steps at
strength 2 until $g$ is minimized, assuming no larger strength to occur. Using the multiplicative drift theorem (Theorem 3), we have $E[T] \le (m^2/2)(1 + \ln(\sum_{i \in [m]} r_i)) \le (m^2/2)(1 + \ln(m^2))$ and by the tail bounds for multiplicative drift (e. g., [51]), it holds that $\Pr[T > (m^2/2)(\ln(m^2) + \ln(m^3))] \le e^{-\ln(m^3)} = 1/m^3$. We choose a phase length of $4(1 - \ell_1)^{-1}m^2 \ln m$, which includes at least $m^2 \ln m$ steps choosing rate 2 with probability $1 - e^{-\Omega(m^2 \ln m)}$ according to Chernoff bounds [57, Theorem 1.10.5]. Assuming this to happen, we have bounded the probability of not finding the optimum in Phase 2 of that length by $o(m^{-2})$. The total probability of any error as described above is still $o(m^{-2})$.

To bound the total expected optimization time, we note that we have already proved an upper bound $o(m^2 \log m)$ on the expected time to reach a spanning tree conditional on no error occurring. If an error occurs while not having constructed a spanning tree, we wait for an accepted one-bit flip, which happens after expected time $O(m \log m)$ and repeat the argumentation. The expected number of repetitions is $o(1)$.

We now bound the expected time for the final phase. Hence, we assume a spanning tree as current search point. If an error occurs, we have no real control over the archive $A^{(t)}$. However, after an expected number of at most $(1/\ell_2)m^2 = O(m^4 \ln m)$ steps, an accepted two-bit mutation adds rate 2 to the archive and progress can be made by flipping two bits as above, with the caveat that the stochastically equivalent behavior as on the function $g$ cannot be assumed any longer. Hence, we use a weaker bound on the expected optimization time. More precisely, we replace the fitness function $f$ by the fitness function $f'$ under which the $2^m$ search points have the same ranking as on $f$, but the maximum weight is $O(m^m)$ [54]. Since the flex-EA is ranking based, it has the same stochastic behavior on $f$ and $f'$. On the process $X_t' := f'(x_t)$, using the classical analysis by [53], there is a multiplicative drift with parameter $\delta = \Omega(q/m^2)$, where $q$ is a lower bound on the probability of a step flipping two bits, while steps flipping more bits do not harm the analysis. Clearly, $q = \Omega(1/m)$
since no more than $m$ rates can be in the archive. Hence, we obtain an expected runtime of $O(m \cdot m^2 \ln(m^m)) = O(m^4 \ln m)$ in the failure case. By the law of total probability, using the failure probability $o(m^{-2})$, the total expected runtime is still $((1 - \ell_1)^{-1} + o(1))(m^2/2)(1 + \ln(\sum_{i \in [m]} r_i))$. □

## 8 A Function Where the Archive Stores Several Rates Simultaneously

Most of the above results do not exploit the full power of the archive A. Most of the time, it was sufficient that the archive contained only one rate and larger archive sizes were even detrimental for the analysis. A major difference of the flex-EA to classical stagnation detection is that a successful rate is kept for the next iteration; however, to some extent this idea was already present in stagnation detection with radius memory [6], which we will compare against.

The purpose of this section is to present an example where flex-EA needs to focus on two rates simultaneously. This can be beneficial on a multimodal function where fitness gaps of different sizes occur frequently. Our example resembles a HURDLE function [58] and features two different gap sizes, so that the archive should include the two corresponding rates. It seems possible to extend the example to a larger number of gap sizes.

Assume the numbers $s := (7/8)n - \sqrt{n}$, $(7/8)n$, $g := (2/3) \log n$ and $\sqrt{n}/g$ are integers. We define the TWO RATES function (Figure 1b) as

$$ \text{TWO RATES}(x) := \begin{cases} \text{OM}(x) & \text{if } |x|_1 < s \text{ or } |x|_1 \ge (7/8)n \\ -1 & \text{or } |x|_1 = s + ig \text{ for } i \in \{0, 2, 3, 5, 6, \dots\}, \end{cases} \quad (5) $$

where the values of $i$ alternatingly increase by 2 and 1.
The hurdles of width $g$, which are located in the interval $[s..7n/8]$ for the number of one-bits, are overcome at the corresponding rate with probability at least

$$ \frac{\binom{n/8}{g}}{\binom{n}{g}} \ge \left( \frac{n/8 - g}{n} \right)^g = \left( 1 - \frac{O(\log n)}{n} \right)^{(2/3) \log n} 8^{-(2/3) \log n} = \frac{(1-o(1))}{n^2} $$

(using the inequalities $\frac{(n-k)!}{k!} \le \binom{n}{k} \le \frac{n^k}{k!}$) and at most

$$ \frac{\binom{n/8+\sqrt{n}}{g}}{\binom{n}{g}} \le \left( \frac{n/8+\sqrt{n}}{n-g} \right)^g = 2^{\log(1/8+O(1/\sqrt{n}))((2/3) \log n)} = \frac{(1+o(1))}{n^2} \quad (6) $$

and accordingly those of width $2g$ with the probability bounds $(1-o(1))/n^4$ and $(1+o(1))/n^4$, respectively.

We now prove that the flex-EA optimizes TWO RATES efficiently, while classical stagnation detection algorithms with and without radius memory need superpolynomial time. Moreover, the Fast $(1+1)$ EA from [3] is by at least a polylogarithmic factor of $\Omega((\log n)^{\beta-1/2}) = \omega(\sqrt{\log n})$ slower than our approach.

**Theorem 9.** The expected runtime of the flex-EA with the recommended parameter set on TWO RATES is bounded by $O(n^{4.5})$. For the stagnation detection algorithms of the type SD-RLS in [2, 6] with typical parameter choice $R = n^d$ for a constant $d > 0$, the expected runtime is $n^{\Omega(\log n)}$. Moreover, the expected runtime of the Fast $(1+1)$ EA is by a factor $\Omega((\log n)^{\beta-1/2})$ larger than that of the flex-EA.

In the proof, we shall need the following useful auxiliary result. It relates to the fact that flipping exactly $g$ zero-bits and no one-bits may not be optimal to cross a hurdle of size $g$, and it bounds the increase in probability when flipping both zero- and one-bits.

**Lemma 10.** Let $x \in \{0,1\}^n$ be a search point with $a \ge 0$ one-bits, and let $p(n, a, d, i)$, where $d, i \ge 0$, be the probability of mutating $x$ into a point containing exactly $a$ +
1519 d one-bits when flipping d + 2i bits uniformly at random. If d + 2i ≤ n¹/³, then
1520
1521 p(n, a, d, i)/p(n, a, d, 0) ≤ (1+o(1))((2+d/i)e·(1-a/n))i ≤ (1+o(1))e¹+²i(1-a/n)¹.
1522
1523 Proof. To reach a+d one-bits by flipping d+2i bits, exactly d+i zero-bits and i one-
1524
1525 bits must be flipped. Hence, we assume that d+i ≤ n-a and i ≤ a. By elementary
1526 combinatorics and expanding the binomial coefficients, we have
1527
1528
1529 p(n, a, d, i) / p(n, a, d, 0) = (n-a) (a) / (d+i) (d+2i) = (d+2i)! i!(d+i)! (n-a) / (n+d+2i) a
1530
1531 = (d+2i)! (n-a-d) / (i!(d+i)! (n-d)²i),
1532
1533
1534
1535 where b = Πj∈[c](b-j+1) is the falling factorial (sometimes called Pochhammer
1536
1537 symbol).
1538
1539 We estimate the two fractions in the last expression separately and start with the
1540 second one. By our assumption that d+2i ≤ n¹/³, we have (n-d)²i ≥ (n-d-2i)²i ≥
1541
1542 (n-n¹/³)²i = (1-o(1))n²i and therefore
1543
1544
1545 (n-a-d) / (n-d)²i ≤ (n-a)⁴n²i ≤ (1+o(1)) (n-a) / n.
1546
1547
1548
1549 For the first fraction, we have (noting that bound below holds trivially if i = 0)
1550
1551 (d+2i)! / i!(d+i)! = (d+2i)⁴ / i! ≤ (d+2i)⁴ / (i/e)⁴ = ((2+d/i) · e)⁴ ≤ (e¹+¹⁴/i)⁴ e⁴ = e¹+²⁴,
1552
1553
1554
1555 where the first inequality used the well-known estimate i! ≥ (i/e)⁴ following from
1556
1557 Stirling's formula and the second inequality used that 1 + x ≤ e⁴ for all x ∈ ℝ.
1558
1559 Multiplying the two estimates gives the claim of the lemma. □
1560
1561 The main idea for the upper bound for the flex-EA is as follows: the expected
1562 time to cross a hurdle is O(n⁴) and there are Θ(√n/ log n) hurdles. The probability of
1563
1564
choosing a beneficial rate of $g$ or $2g$ is $\Omega(1/\log n)$ since the cardinality of the archive 1565
is bounded by $O(\log n)$ with high probability. The lower bound for the Fast (1+1) EA 1566
stems from the fact that rates of $\Omega(\log n)$ must be chosen with high probability to cross 1567
a hurdle, which has probability $O((\log n)^{-\beta})$ in the heavy-tailed mutation. Another 1568
factor of $\Theta(\sqrt{\log n})$ is lost since the Fast (1+1) EA uses standard-bit mutation instead 1569
of flipping a deterministic number of bits. 1570
1571
1572
1573
1574

*Proof of Theorem 9.* We start with the upper bound for the flex-EA.

**Reaching the first hurdle.** By Chernoff bounds, the initial search point has at 1575
most $s = (7/8)n - \sqrt{n}$ one-bits with probability $1-2^{-\Omega(n)}$, which we assume to happen. 1576
Hence, by Theorem 5, the level of at least $s$ one-bits, i. e., the start of the hurdle section 1577
of TWO RATES, is reached within expected time $O(\ell_1^{-1} n \log n) = O(n \log n)$, and rate 1 1578
is in the archive with probability $1 - O(1/n^{-c})$ for any given constant $c > 0$ by 1579
choosing the constant in $C_1$ appropriately. Moreover, by applying Markov's inequality 1580
and repeating independent phases, the time to reach level at least $s$ is bounded by 1581
$O(n^4)$ with probability $1 - 2^{-\omega(n)}$. 1582
1583
1584
1585
1586
1587
1588
1589

We now consider the first time where the current search point has $s$ or more one-bits. Let $x^*$ denote this search point. Since we assumed an initial point of at most $s$ one-bits and thus a non-negative fitness, we have $|x^*|_1 = s+ig$ for $i \in \{0, 2, 3, 5, 6, \dots\}$, 1590
i. e., $x^*$ is a locally optimal hurdle point, or $|x^*|_1 \ge (7/8)n$. We pessimistically ignore 1591
the case that $|x^*| \ge (7/8)n$ since from there the optimum can be reached using one-bit flips in the same way as before reaching the first hurdle. Hence, we now assume $x^*$ 1592
is a local optimum in the hurdle section of TWO RATES. 1593
1594
1595
1596
1597
1598
1599
1600
1601

Since $x^*$ is a local optimum and we assume that rate 1 is in the archive while not 1602
in stagnation detection mode, the counter $c_1^{(t)}$ reaches its threshold in a deterministic 1603
number of $O(n \log n)$ iterations, and the archive is reset to contain rate 1 only. We 1604
assume this to happen before the hurdles are crossed, noting that the algorithm is now 1605
1606
1607
1608
1609
1610
1611 in stagnation detection mode but leaves this mode as soon as it improves its current
1612 solution.
1613

Bounding the archive size. When the current search point is a local optimum
1614
1615
1616 in the hurdle section, then successes are only possible at rates $g$ or larger. The aim is
1617
to bound the size of the archive while the hurdles of width $g$ and $2g$ are overcome. We
1618
1619 first rule out that extremely large rates yield a success and thereby enter the archive.
1620
1621 Applying a mutation flipping $d$ bits uniformly at random to a search point with $a \ge s$
1622
1623 one-bits, the number of flipping one-bits follows a hypergeometric distribution and
1624 the expected increase in one-bits equals $ad/n - (n-a)d/n < 0$. Applying a Chernoff
1625
1626 bound for the hypergeometric distribution (Theorem 1.10.25 in [57]), the probability
1627
1628 of increasing the number of one-bits by any positive amount when flipping a certain
1629 number $d \ge n^{1/3}$ of bits in one step is bounded from above by $2^{-\Omega(n^{1/3})}$. By a union
1630
1631 bound over all $d \ge n^{1/3}$, the probability of increasing the number of one-bits using
1632 any rate at least $n^{1/3}$ is still $2^{-\Omega(n^{1/3})}$. Hence, we work under the assumption that
1633
1634 rates larger than $n^{1/3}$ are never successful in polynomial time; the error probability is
1635
1636 still $2^{-\Omega(n^{1/3})}$ by a union bound.
1637
1638

Recall that the minimum successful rate is $g$ while crossing the hurdles in the
1639 interval $[s..(7/8)n]$ of one-bits. We now estimate the success probabilities of rates
1640
1641 in $[g..n^{1/3}]$. By flipping $2g + i$ zero-bits and $i$ one-bits at rate $2g + 2i$, also larger
1642
1643 rates than $2g$ can overcome hurdles of size $2g$. Using Lemma 10 choosing $d = 2g =$
1644 $(4/3) \log n$, $i = c' \log n$ for a sufficiently large constant $c'$, $a \ge s$, and by our assumption
1645
1646 of rates at most $n^{1/3}$ being active, we have that the probability of increasing the
1647
1648 number of one-bits by $d$ at rate $d + 2i$ is no larger than a factor of

$$ (1 + o(1))e^{\log n}e^{2i\left(\frac{1}{8} + \frac{1}{\sqrt{n}}\right)^i} \le (1 + o(1))e^{(4/3)\log n}0.93^i $$
the probability of doing this at rate $d$. Hence, for a sufficiently large constant $c' > 0$, 1657 rates larger than $2g + 2c' \log n$ only have a success probability of $O(n^{-c})$ for any given 1658 constant $c > 0$. By a union bound, the size of the archive is bounded by $O(\log n)$ within 1659 a period of $\Theta(n^{4.5})$ steps with probability $1 - O(n^{4.5-c})$, i. e., with high probability. 1660

**Crossing the hurdles and reaching the optimum.** In the following, under 1663 the above assumptions, we first show that a phase of $c''n^{4.5}$ steps for a sufficiently 1664 large constant $c'' > 0$ is sufficient to cross all hurdles by reaching at least $7n/8$ one- 1665 bits with high probability. Recall that by equation (6) and the discussion following it, 1666 the success probability of overcoming a gap of size $g$ and $2g$ is at least $(1 - o(1))n^{-2}$ 1667 and $(1 - o(1))n^{-4}$, respectively, but possibly larger since it may be beneficial to flip 1668 more bits than the gap size to overcome the gap. Hence, no matter whether there is a 1669 current hurdle of width $g$ or $2g$ one-bits to the next improvement, the rate having the 1670 highest success probability enters the archive after an expected number of $O(\ell_{2g}^{-1}n^4) = 1671$ 1671 $O(n^4 \log^2 n)$ steps since it is sufficient to select the best rate and have a success (using 1672 that $\ell_g^{-1} \le \ell_{2g}^{-1}$). In our estimate $\ell_{2g} = \Omega(\log^{-2} n)$, we used that the heavy-tailed 1673 parameter satisfies $\beta \le 2$. For a geometrically distributed random variable $G$ with 1674 success probability $p$ and any $k \ge 0$, we have the tail bound $\Pr[G \ge k/p] \le (1 - 1/p)^{k/p} \le e^{-k}$. Hence, the time for the rate to enter is $O(n^4 \log^4 n)$ with overwhelming 1675 probability. Once both the optimal rate for gap $g$ and the one for gap $2g$ are in the 1676 archive, the probability of choosing the rate fitting the next hurdle is $\Omega(1/\log n)$ by our 1677 assumption on the archive size. Hence, the probability of choosing the right rate and 1678 improving the solution by jumping the hurdle is $\Omega(1/(n^4 \log n))$ (using that gap $2g$ is 1679 the worst case). Since at most $\sqrt{n}/g = O(\sqrt{n}/\log n)$ improvements jumping hurdles 1680 are sufficient to reach level $7n/8$ or larger and the remaining part of the optimization 1681 is completed within expected time $O(\ell_1^{-1}n \log n) = O(n \log n)$ in the same way as 1682 described above, the optimization time is $O(n^{4.5})$ in expectation and also with high 1683
probability by Chernoff bounds for sums of geometrically distributed random variables (Theorem 1.10.32 in [57]).

**Handling possible error cases.** Above, we have bounded the probabilities of various errors by $O(n^{-c})$ for any given constant $c$ or by even smaller expressions. The first possible error is that the archive does not contain rate 1 when reaching the hurdle section. Then we do not know whether the archive will be reset to contain rate 1 only. The second possible error is that the initial search point has more than $s$ one-bits and rate 1 may be unsuccessful. Nevertheless, in both error cases, as soon as a rate of at most $g$ or at most $2g$ is chosen according to the probabilities in $\ell$, the algorithm will be able to improve. The waiting time for this to happen is $O(n^4 \log^4 n)$ as argued above. In this case, we do not assume a bound on the size of the archive either. In fact, an archive not bounded by $O(\log n)$ while crossing the hurdles was already identified as a third error case above.

In summary, regardless of the error type, in the case of an untypical archive, we argue with the maximum possible archive size $n$ and have a success probability of $\Omega(1/n^5)$ for each local optimum and even $\Omega(1/n^2)$ for the ONEMAX-parts of TWOATES. The expected time in the three error cases is therefore $O(n^{5.5}/\log n)$ and by the law of total probability the three error cases contribute $O(n^{4.5})$ to the expected runtime for choosing the constant $c > 0$ in the high-probability bounds large enough. Finally, as a fourth type of error, the probability of exceeding a counter while crossing the hurdles is superpolynomially small since $C_g \ge (\log n)^n$; if this happens neverthe- less, then we again wait for the optimum rates for gap sizes $g$ and $2g$ to enter the archive as above. By the law of total probability, this contributes a superpolynomially small extra term to the expected runtime. Altogether, the unconditional expected optimization time of flex-EA is $O(n^{4.5})$.

**Lower Bounds for stagnation detection and Fast (1+1) EA.** We are left with the bounds for the other algorithms. With overwhelming probability $1 - 2^{-\Omega(n)}$,
their first search point, which is drawn uniformly, is before the first hurdle, i. e., has 1749
at most $s$ one-bits. Hence, in the algorithms SD-RLS$^r$ and SD-RLS$^m$, the rate must 1750
increase from its initial value 1 to at least $g$ as least once. With the standard parameter 1751
choices, this takes $\Omega(\sum_{i=1}^{g-1} \binom{n}{i} \ln R) = n^{\Omega(\log n)}$ steps. 1752
1753

The Fast (1+1) EA, under the same assumption on the first point, must increase 1756
the number of one-bits by a total of at least $\sqrt{n}$ to cross all hurdles. We show that the 1757
algorithm does not cross more than $h^*$ hurdles at once in a period of $O(n^5)$ steps with 1758
high probability, where $h^*$ is a sufficiently large constant. To cross $h^*$ hurdles in one 1759
mutation, it is necessary that at least $cg$ zero-bits flip at once for some constant $c > 0$. 1760
By the results in [3], for any $k \in [n/2]$, the probability of flipping exactly $k$ bits is 1761
maximized at mutation probability $k/n$ (recall that the Fast (1+1) EA uses standard 1762
bit mutation). Hence, the probability of flipping $k \ge cg$ zero-bits and thereby crossing 1763
at least $h^*$ hurdles at once is at most 1764

$$ \binom{n-s}{k} \left(\frac{k}{n}\right)^k \le \left(\frac{(n-s)e}{k}\right)^k \left(\frac{k}{n}\right)^k \le \left(\frac{1}{8} + \frac{1}{\sqrt{n}}\right)^k e^k \le \left(\frac{e}{8} + \frac{e}{\sqrt{n}}\right)^{cg} = O(n^{-6}) $$

if $h^*$, and thereby $c$, are large enough. By a union bound over all $k \le n$, the probability 1775
of crossing at least $h^*$ hurdles at once is still $O(n^{-5})$. In the following, we assume that 1776
this does not happen in $O(n^{4.6})$ steps. 1777

Under our assumptions, to reach the optimum, at least $\sqrt{n}/(cg)$ increases of the 1780
number of one-bits by at least $cg$ in search points at level $s$ or larger are necessary, 1781
where $c$ may be a large constant. We pessimistically (for the perspective of a lower 1782
bound) assume that the heavy-tailed mutation operator always flips a number of bits 1783
$2g+2i$ that maximizes the probability of overcoming a hurdle of width $2g$ (and in the 1784
same way for the hurdles of width $g$). As mentioned above, the Fast (1+1) EA flips 1785
$2g+2i$ bits with the highest probability at mutation probability $(2g+2i)/n$. Hence, 1786
1787

1791
1792
1793
1794
1795 the probability of crossing a hurdle of width $2g$ is at most

1796

1797

1798

1799

1800

1801

1802

1803

1804 Inspecting the product following $p(n, s, 2g, i)$, which is the ratio of success probabilities

1805

1806 of the Fast (1+1) EA and of the flex-EA, we have

1807

1808

1809

1810

1811

1812

1813

1814

1815 where the $o(1)$ comes from the assumption of $2g+2i \le n^{1/3}$. Using Stirling's formula,

1816

1817

1818

1819

1820

1821

1822

1823

1824

1825 so the probability of the Fast (1+1) EA crossing a hurdle is by a factor of

1826

1827

1828

1829

1830 Finally, we analyze the probability of the Fast (1+1) EA choosing a successful rate

1831

1832

1833

1834

1835

1836

1837

1838

1839

1840

$$ \binom{n-s}{2g+i} \binom{s}{i} \left( \frac{2g+2i}{n} \right)^{2g+2i} \left( 1 - \frac{2g+2i}{n} \right)^{n-2g-2i} $$

$$ = p(n, s, 2g, i) \cdot \left( \frac{2g+2i}{n} \right)^{2g+2i} \left( 1 - \frac{2g+2i}{n} \right)^{n-2g-2i} \binom{n}{2g+2i}. $$

$$ \left( \frac{2g+2i}{n} \right)^{2g+2i} \left( 1 - \frac{2g+2i}{n} \right)^{n-2g-2i} \binom{n}{2g+2i} $$

$$ \leq \left( \frac{2g+2i}{n} \right)^{2g+2i} e^{-2g-2i+o(1)} \frac{n^{2g+2i}}{(2g+2i)!}, $$

1816 we have $(2g+2i)! \ge \sqrt{2\pi}\sqrt{2g+2i} \cdot e^{-2g-2i}(2g+2i)^{2g+2i}$. Plugging this into the previous formula, the bound on the ratio of success probabilities simplifies to

$$ (1 + o(1)) \frac{1}{\sqrt{2\pi}\sqrt{2g + 2i}}, $$

1827 $\Omega(\sqrt{2g+2i}) = \Omega(\sqrt{\log n})$ smaller than the respective probability for the flex-EA when using an optimal rate.

1831 in the heavy-tailed mutation operator. If its rate is at most $c' \log n$ for a constant $c' > 0$, 1832 the probability of crossing a hurdle of width $g$ is at most

$$ \left( \frac{n-s}{g} \right) \left( \frac{c' \log n}{n} \right)^g \le \left( \frac{c' \log n}{\log n} \right)^{\log n} = O\left( \frac{1}{n^5} \right) $$
choosing $c'$ small enough. Hence, by a union bound, no hurdle is crossed at rate less
than $c' \log n$ in a period of $\Omega(n^{4.5\sqrt{\log n}})$ steps, which we assume to happen. On the
other hand, the probability of the heavy-tailed mutation choosing rate at least $c' \log n$
is at most $O((1/\log n)^\beta)$. This probability is by a factor $O((1/\log n)^{\beta-1})$ smaller than
$1/\log n$, the asymptotic worst-case probability of the flex-EA choosing the best radius
from an archive of $O(\log n)$ bits. Since both algorithms have to overcome $\Theta(\sqrt{n}/\log n)$
hurdles with high probability and the success probability of the flex-EA for crossing a
hurdle is bigger by a factor of $\Omega(\sqrt{\log n})$, we obtained the claimed asymptotic speed-up
of $\Omega((\log n)^{\beta-1/2})$ for the flex-EA compared to the Fast (1+1) EA. □

We conjecture that the runtime of the SD-FEA from [5] on TWO_RATES is asymptotically at least as large as the one of the Fast (1+1) EA. Essentially, rates in the order $\Omega(\log n)$ must be used to obtain a sufficient probability of crossing a hurdle. Then in the same way as described above, the selection probability $O((\log n)^{-\beta})$ in the heavy-tailed component impacts the runtime bound.

# 9 Conclusion

We introduced the flex-EA – a flexible evolutionary algorithm that maintains an
archive of previously successful mutation rates. The algorithm is highly configurable
and thus allows to exploit problem-specific knowledge. However, we also recommended
a default configuration, based on heavy-tailed distributions and stagnation detection,
which eliminates the need of the user to make any parameter choices. Using this rec-
ommended configuration, we proved that the flex-EA achieves standard runtimes on
ONEMAX and on LEADINGONES, and that it achieves a near best-possible runtime
on JUMP for unbiased mutation-only algorithms. Furthermore, for a hurdle-like prob-
lem that features repetitive sub-structures, this configuration outperforms the Fast

1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887 (1+1) EA (which uses heavy-tailed mutations) and stagnation detection. When provided with some mild problem-specific knowledge, the flex-EA matches the best known runtime result for the minimum spanning tree problem.

1889 Although the performance of the flex-EA is very good on the problems we considered, the algorithm still has some shortcomings that can be improved. For one, on 1894 shifted jump benchmarks [59], we believe that the combination of heavy-tailed mutation and stagnation detection by Doerr and Rajabi [5] proves superior, as the flex-EA 1897 basically defaults to classic stagnation detection. However, this shortcoming can be 1899 overcome by adjusting the mutation of the flex-EA in a similar way as done by Doerr 1900 and Rajabi [5] for their algorithm. Another possible shortcoming is that mutation rates 1901 larger than $\frac{n}{2}$ are only activated via stagnation detection after a time super-polynomial 1903 in $n$ despite the number of improving solutions in this distance being potentially far 1905 smaller than that. One way to avoid this problem is to have usually two rates active 1906 while in stagnation detection mode, namely, for all $i \in [\lfloor \frac{n}{2} \rfloor]$, have $i$ and $n-i$ active 1909 at the same time (and try out a rate of $n$ once whenever entering stagnation detection). Since this halves the probability of an active frequency being chosen, runtimes 1910 that rely on stagnation detection (such as our result for jump functions (Theorem 6)) 1914 become worse by a factor of 2. In return, this allows to make very large jumps quickly, 1915 leading, for example, to the same asymptotic runtime on the classical TRAP function 1916 as on ONEMAX. 1919

1920 Overall, the flex-EA proposes a concept for evolutionary algorithms that performs 1921 very well compared to other well-studied algorithms on widely-studied benchmark 1923 functions, and it can be studied in multiple domains that exceed the content of this 1924 paper.

1927 Acknowledgments. This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions 1928 with data science.

1932
References

<table>
  <tbody>
    <tr>
      <td>[1] Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation – Recent Developments in Discrete Optimization. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4</td>
      <td>1933<br>1934<br>1935<br>1936<br>1937<br>1938<br>1939<br>1940</td>
    </tr>
    <tr>
      <td>[2] Rajabi, A., Witt, C.: Stagnation detection with randomized local search. Evolutionary Computation 31(1), 1–29 (2023) https://doi.org/10.1162/evco_a_00313</td>
      <td>1941<br>1942<br>1943<br>1944</td>
    </tr>
    <tr>
      <td>[3] Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Proc. of GECCO ’17, pp. 777–784 (2017). https://doi.org/10.1145/3071178.3071301</td>
      <td>1945<br>1946<br>1947<br>1948<br>1949<br>1950</td>
    </tr>
    <tr>
      <td>[4] Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623–642 (2012)</td>
      <td>1951<br>1952<br>1953<br>1954</td>
    </tr>
    <tr>
      <td>[5] Doerr, B., Rajabi, A.: Stagnation detection meets fast mutation. Theoretical Computer Science 946, 113670 (2023) https://doi.org/10.1016/j.tcs.2022.12.020</td>
      <td>1955<br>1956<br>1957<br>1958</td>
    </tr>
    <tr>
      <td>[6] Rajabi, A., Witt, C.: Stagnation detection in highly multimodal fitness landscapes. In: Proc. of GECCO ’21, pp. 1178–1186. ACM Press, New York, USA (2021). https://doi.org/10.1145/3449639.3459336</td>
      <td>1959<br>1960<br>1961<br>1962<br>1963<br>1964</td>
    </tr>
    <tr>
      <td>[7] Krejca, M.S., Witt, C.: A flexible evolutionary algorithm with dynamic mutation rate archive. In: Proc. of GECCO ’24. ACM, New York, USA (2024). https://doi.org/10.1145/3638529.3654076</td>
      <td>1965<br>1966<br>1967<br>1968<br>1969<br>1970</td>
    </tr>
    <tr>
      <td>[8] Krejca, M., Witt, C.: Theory of estimation-of-distribution algorithms. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation – Recent Developments in Discrete Optimization, pp. 405–442. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4</td>
      <td>1971<br>1972<br>1973<br>1974<br>1975<br>1976<br>1977<br>1978</td>
    </tr>
  </tbody>
</table>
1979 [9] Dang, D., Eremeev, A.V., Lehre, P.K.: Escaping local optima with non-elitist evolutionary algorithms. In: Proc. of AAAI '21, pp. 12275-12283. AAAI Press, Palo Alto, USA (2021). https://doi.org/10.1609/AAAI.V35I14.17457

1980
1981
1982
1983
1984
1985 [10] Doerr, B., Houssaini, T.E.G.E., Rajabi, A., Witt, C.: How well does the metropolis algorithm cope with local optima? In: Proc. of GECCO '23, pp. 1000-1008. ACM, New York, USA (2023). https://doi.org/10.1145/3583131.3590390

1986
1987
1988
1989
1990
1991 [11] Jansen, T., Wegener, I.: The analysis of evolutionary algorithms – A proof that crossover really can help. Algorithmica 34, 47-66 (2002) https://doi.org/10.1007/s00453-002-0940-2

1992
1993
1994
1995
1996
1997 [12] Corus, D., Oliveto, P.S., Yazdani, D.: Fast immune system-inspired hypermutation operators for combinatorial optimization. IEEE Transactions on Evolutionary Computation 25(5), 956-970 (2021) https://doi.org/10.1109/TEVC.2021.3068574

2000
2001
2002
2003
2004 [13] Zarges, C.: Theoretical foundations of immune-inspired randomized search heuristics for optimization. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation – Recent Developments in Discrete Optimization, pp. 443-474. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4

2010
2011
2012 [14] Friedrich, T., Quinzan, F., Wagner, M.: Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In: Proc. of GECCO '18, pp. 293-300. ACM, Cham, Switzerland (2018). https://doi.org/10.1145/3205455.3205515

2013
2014
2015
2016
2017 [15] Friedrich, T., Göbel, A., Quinzan, F., Wagner, M.: Heavy-tailed mutation operators in single-objective combinatorial optimization. In: Proc. of PPSN '18, pp. 134-145. Springer, Cham, Switzerland (2018). https://doi.org/10.1007/978-3-319-99253-2_11

2018
2019
2020
2021
2022
2023
2024
[16] Wu, M., Qian, C., Tang, K.: Dynamic mutation based Pareto optimization for subset selection. In: Proc. of ICIC '18, pp. 25–35. Springer, Cham, Switzerland (2018). https://doi.org/10.1007/978-3-319-95957-3_4

[17] Antipov, D., Doerr, B.: Runtime analysis of a heavy-tailed $(1 + (\lambda, \lambda))$ genetic algorithm on jump functions. In: Prof. of PPSN '20, pp. 545–559. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-58115-2_38

[18] Quinzan, F., Göbel, A., Wagner, M., Friedrich, T.: Evolutionary algorithms and submodular functions: Benefits of heavy-tailed mutations. Natural Computing 20(3), 561–575 (2021) https://doi.org/10.1007/s11047-021-09841-7

[19] Zheng, W., Doerr, B.: Theoretical analyses of multiobjective evolutionary algorithms on multimodal objectives. Evolutionary Computation 31(4), 337–373 (2023) https://doi.org/10.1162/EVCO_A_00328

[20] Antipov, D., Buzdalov, M., Doerr, B.: Fast mutation in crossover-based algorithms. Algorithmica 84, 1724–1761 (2022) https://doi.org/10.1007/s00453-022-00957-5

[21] Dang, D., Eremeev, A.V., Lehre, P.K., Qin, X.: Fast non-elitist evolutionary algorithms with power-law ranking selection. In: Proc. of GECCO '22, pp. 1372–1380. ACM, New York, USA (2022). https://doi.org/10.1145/3512290.3528873

[22] Doerr, B., Ghannane, Y., Ibn Brahim, M.: Runtime analysis for permutation-based evolutionary algorithms. Algorithmica 86(1), 90–129 (2024) https://doi.org/10.1007/S00453-023-01146-8

[23] Doerr, B., Qu, Z.: A first runtime analysis of the NSGA-II on a multimodal problem. IEEE Transactions on Evolutionary Computation 27(5), 1288–1297 (2023) https://doi.org/10.1109/TEVC.2023.3250552
2071 [24] López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, 2072 M.: The irace package: Iterated racing for automatic algorithm configuration. 2073 Operations Research Perspectives 3, 43–58 (2016) https://doi.org/10.1016/j.orp. 2074 2075 2076 2016.09.002 2077

2078 [25] Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization 2079 for general algorithm configuration. In: Proc. of LION-5, pp. 507–523. Springer, 2080 Berlin, Heidelberg, Germany (2011). https://doi.org/10.1007/978-3-642-25566-3- 2081 2082 40 2083 2084 2085

2086 [26] Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp, A., Deng, D., Ben- 2087 jamins, C., Ruhkopf, T., Sass, R., Hutter, F.: Smac3: A versatile bayesian 2088 optimization package for hyperparameter optimization. CoRR abs/2109.09831 2089 2090 (2021) 2091 2092

2093 [27] Hall, G.T., Oliveto, P.S., Sudholt, D.: On the impact of the cutoff time on the 2094 performance of algorithm configurators. In: Proc. of GECCO ’19, pp. 907–915. 2095 2096 ACM, New York, USA (2019). https://doi.org/10.1145/3321707.3321879 2097 2098

2099 [28] Hall, G.T., Oliveto, P.S., Sudholt, D.: Fast perturbative algorithm configurators. 2100 In: Proc. of PPSN ’20, vol. 12269, pp. 19–32. Springer, Cham, Switzerland (2020). 2101 2102 2103 https://doi.org/10.1007/978-3-030-58112-1_2 2104

2105 [29] Hall, G.T., Oliveto, P.S., Sudholt, D.: Analysis of the performance of algorithm 2106 configurators for search heuristics with global mutation operators. In: Proc. of 2107 GECCO ’20, pp. 823–831. ACM, New York, USA (2020). https://doi.org/10. 2108 2109 2110 2111

2112 [30] Hall, G.T., Oliveto, P.S., Sudholt, D.: On the impact of the performance metric 2113 on efficient algorithm configuration. Artificial Intelligence 303, 103629–110362927 2114 2115 2116
(2022) https://doi.org/10.1016/J.ARTINT.2021.103629

2117

2118

[31] Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: Provable performance gains through dynamic parameter choices. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation – Recent Developments in Discrete Optimization, pp. 271–321. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4

2119

2120

2121

2122

2123

2124

2125

2126

2127

[32] Schumer, M., Steiglitz, K.: Adaptive step size random search. IEEE Transactions on Automatic Control 13(3), 270–276 (1968) https://doi.org/10.1109/TAC.1968.1098903

2128

2129

2130

2131

2132

2133

[33] Rechenberg, I.: Evolutionstrategie: Optimierung Technischer Systeme Nach Prinzipien der Biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart, Germany (1973)

2134

2135

2136

2137

2138

2139

[34] Doerr, B., Doerr, C.: Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings. In: Proc. of GECCO '15, pp. 1335–1342. ACM Press, New York, USA (2015). https://doi.org/10.1145/2739480.2754684

2140

2141

2142

2143

2144

2145

[35] Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. Algorithmica 84(6), 1694–1723 (2022) https://doi.org/10.1007/s00453-022-00933-z

2146

2147

2148

2149

2150

2151

[36] Dang, D.-C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Proc. of PPSN '16, pp. 803–813. Springer, Cham, Switzerland (2016). https://doi.org/10.1007/978-3-319-45823-6_75

2152

2153

2154

2155

2156

2157

[37] Lehre, P.K., Qin, X.: Self-adaptation via multi-objectivisation: a theoretical study. In: Proc. of GECCO '22, pp. 1417–1425. ACM, New York, USA (2022). https://doi.org/10.1145/3512290.3528836

2158

2159

2160

2161

2162
2163 [38] Lehre, P.K., Qin, X.: Self-adaptation can improve the noise-tolerance of evolutionary algorithms. In: Proc. of FOGA '23, pp. 105–116. ACM, New York, USA (2023). https://doi.org/10.1145/3594805.3607128

2164
2165
2166
2167
2168

2169 [39] Lehre, P.K., Qin, X.: Self-adaptation can help evolutionary algorithms track dynamic optima. In: Proc. of GECCO '23, pp. 1619–1627. ACM, New York, USA (2023). https://doi.org/10.1145/3583131.3590494

2170
2171
2172
2173
2174

2175 [40] Case, B., Lehre, P.K.: Self-adaptation in nonelitist evolutionary algorithms on discrete problems with unknown structure. IEEE Transactions on Evolutionary Computation **24**(4), 650–663 (2020) https://doi.org/10.1109/TEVC.2020.2985450

2176
2177
2178
2179
2180
2181

2182 [41] Doerr, B., Witt, C., Yang, J.: Runtime analysis for self-adaptive mutation rates. Algorithmica **83**(4), 1012–1053 (2021) https://doi.org/10.1007/s00453-020-00726-2

2183
2184
2185
2186
2187

2188 [42] Doerr, B., Doerr, C., Yang, J.: *k*-bit mutation with self-adjusting *k* outperforms standard bit mutation. In: Proc. of PPSN '16, pp. 824–834. Springer, Cham, Switzerland (2016). https://doi.org/10.1007/978-3-319-45823-6_77

2189
2190
2191
2192
2193

2194 [43] Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: Simple hyper-heuristics control the neighbourhood size of randomised local search optimally for LeadingOnes. Evolutionary Computation **28**(3), 437–461 (2020) https://doi.org/10.1162/EVCO_A_00258

2195
2196
2197
2198
2199
2200

2201 [44] Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: When move acceptance selection hyper-heuristics outperform Metropolis and elitist evolutionary algorithms and when not. Artificial Intelligence **314**, 1038041–10380423 (2023) https://doi.org/10.1016/J.ARTINT.2022.103804

2202
2203
2204
2205
2206
2207
2208
[45] Wegener, I.: Theoretical aspects of evolutionary algorithms. In: Proc. of ICALP '01, pp. 64–78. Springer, Berlin, Heidelberg, Germany (2001). https://doi.org/10.1007/3-540-48224-5_6

[46] Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17(3), 418–435 (2013) https://doi.org/10.1109/TEVC.2012.2202241

[47] He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127(1), 51–81 (2001) https://doi.org/10.1016/S0004-3702(01)00058-3

[48] Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673–697 (2012) https://doi.org/10.1007/s00453-012-9622-x

[49] Kötzing, T., Krejca, M.S.: First-hitting times under drift. Theoretical Computer Science 796, 51–69 (2019) https://doi.org/10.1016/j.tcs.2019.08.021

[50] Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65(1), 224–250 (2013) https://doi.org/10.1007/S00453-011-9585-3

[51] Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation – Recent Developments in Discrete Optimization, pp. 89–131. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4

[52] Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovač, Hamburg, Germany (1997)

[53] Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science 378, 32–40 (2007) https://doi.org/10.1016/j.tcs.2006.11.002
2255 [54] Reichel, J., Skutella, M.: On the size of weights in randomized search heuristics. In: Proc. of FOGA 2009, pp. 21–28 (2009). https://doi.org/10.1145/1527125.1527130

2257

2258

2260 [55] Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Transaction on Evolutionary Computation 10(2), 145–156 (2006) https://doi.org/10.1109/TEVC.2006.871251

2265

2266

2267 [56] Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Information Processing Letters 114(1-2), 38–41 (2014) https://doi.org/10.1016/J.IPL.2013.09.013

2271

2272

2273 [57] Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation – Recent Developments in Discrete Optimization, pp. 1–87. Springer, Cham, Switzerland (2020). https://doi.org/10.1007/978-3-030-29414-4

2277

2278

2279

2280 [58] Nguyen, P.T.H., Sudholt, D.: Memetic algorithms outperform evolutionary algorithms in multimodal optimisation. Artificial Intelligence 287, 103345 (2020) https://doi.org/10.1016/j.artint.2020.103345

2281

2282

2283

2284

2285

2286 [59] Witt, C.: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoretical Computer Science 940, 18–42 (2023) https://doi.org/10.1016/J.TCS.2022.08.014

2287

2288

2289

2290

2291

2292

2293

2294

2295

2296

2297

2298

2299

2300