# A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive

Martin S. Krejca  0000-0002-1765-1219 Laboratoire d’Informatique (LIX), CNRS,
École Polytechnique, Institut Polytechnique de ParisPalaiseauFrance
<EMAIL_ADDRESS>and  Carsten Witt  0000-0002-6105-7700
Technical University of DenmarkLyngbyDenmark<EMAIL_ADDRESS>
(2024)

###### 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.

Theory, runtime analysis, evolutionary algorithm, parameter adaptation,
archive

††journalyear: 2024††copyright: rightsretained††conference: Genetic and
Evolutionary Computation Conference; July 14–18, 2024; Melbourne, VIC,
Australia††booktitle: Genetic and Evolutionary Computation Conference (GECCO
’24), July 14–18, 2024, Melbourne, VIC, Australia††doi:
10.1145/3638529.3654076††isbn: 979-8-4007-0494-9/24/07††price: 15.00††ccs:
Theory of computation Theory of randomized search heuristics††ccs: Mathematics
of computing Evolutionary algorithms

##  1\. Introduction

The success of evolutionary algorithms (EAs) depends crucially on their
parametrization (Doerr and Neumann, 2020). 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 (Doerr and Neumann, 2020). 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 no rate is active, the flex-EA picks the
successor of the last-active rate, reminiscent of stagnation detection (Rajabi
and Witt, 2023). If the archive becomes too full without seeing any progress,
it is reset.

The flex-EA allows many of its parameters to be adjusted in order to
incorporate problem-specific knowledge. However, in the absence of such
knowledge, we recommend to choose the probabilities of inactive rates
according to a heavy-tailed distribution – a common, general-purpose choice,
first suggested by Doerr et al. (2017), also known as a _power-law_ – and to
choose the times for discarding active rates in the same manner as done in
stagnation detection (Rajabi and Witt, 2023). This results in an essentially
parameter-less algorithm.

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

For unimodal functions (Section 5), the progress of the flex-EA is mainly
determined by its probability to improve solutions locally (Theorem 5.1). For
OneMax and LeadingOnes of problem size $n$ and with the recommended
parametrization, this results in the common bounds of
$\mathrm{O}\mathopen{}\mathclose{{}\left(n\log(n)}\right)$ and
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{2}}\right)$, respectively.

For the Jump benchmark of problem size $n$ and gap size $k$ (Section 6), the
recommended parametrization results for
$k=\mathrm{o}\mathopen{}\mathclose{{}\left(n/\log n}\right)$ in a bound of
$\big{(}2+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)\big{)}\binom{n}{k}$
(Corollary 6.2), which is optimal for unbiased algorithms with unary mutation,
up to a factor of $2+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$ (Doerr
and Rajabi, 2023). 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
$\bigl{(}1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)\bigr{)}\bigl{(}m^{2}\log(m)\bigr{)}$
(Theorem 7.1), which matches the best known bound (Rajabi and Witt, 2021).

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 stagnation detection (Theorem 8.1).
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
recommended 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.

##  2\. Related Work

There exists a plethora of different operators for choosing good mutation
rates (Doerr and Neumann, 2020). 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.
By using populations and diversity-maintaining operators, one opens up for a
new level of complexity in the design and analysis of evolutionary algorithms.
In addition, this excludes estimation-of-distribution algorithms (EDAs)
(Krejca and Witt, 2020), 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 (Dang et al., 2021; Doerr et al., 2023). 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 (Jansen and Wegener, 1999).

Artificial immune systems (AISes) use operators that change solutions more
drastically (Corus et al., 2021). 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 (Zarges, 2020).

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. (2017)
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 (Friedrich et al.,
2018b; Friedrich et al., 2018a; Wu et al., 2018; Antipov and Doerr, 2020;
Quinzan et al., 2021; Zheng and Doerr, 2023; Corus et al., 2021; Antipov et
al., 2022; Dang et al., 2022; Doerr et al., 2022; Doerr and Rajabi, 2023;
Doerr and Qu, 2023). 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.

#### Dynamic rate distributions.

Some algorithms change the distribution for choosing the mutation rate during
the optimization process (Doerr and Doerr, 2020). 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., (Schumer and Steiglitz,
1968; Rechenberg, 1973; Doerr and Doerr, 2015)), 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
(Rajabi and Witt, 2022, 2023). 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 (Rajabi and Witt, 2021), 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 (Doerr and Rajabi, 2023) 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 (Doerr and Rajabi, 2023). 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.

#### Learning-based algorithms.

Doerr et al. (2016) 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.,
(Lissovoi et al., 2020, 2023), which are algorithms that aim at selecting in
each iteration an algorithm that is best suited for the current sate. 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 being
that it updates its distribution over the mutation rate in a simpler way. This
simplification especially allows a rigorous analysis of the flex-EA on a wide
variety of problems while still showcasing a strong performance.

##  3\. Preliminaries

The natural numbers $\mathds{N}$ include $0$. For $a,b\in\mathds{R}$, let
$[a..b]=[a,b]\cap\mathds{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\mathds{N}_{\geq 1}$, the optimization of functions
$f\colon\\{0,1\\}^{n}\to\mathds{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
$\bm{x}\in\\{0,1\\}^{n}$ an _individual_ , and
$f\mathopen{}\mathclose{{}\left(\bm{x}}\right)$ its _fitness_. For each
$i\in\mathds{N}$, let $\bm{x}_{i}$ denote the value of $\bm{x}$ at position
$i$. Last, let $|\bm{x}|_{1}$ be the number of $1$s of $\bm{x}$, and
$|\bm{x}|_{0}$ its number of $0$s.

For each $\bm{x},\bm{y}\in\\{0,1\\}^{n}$, let
$d_{\mathrm{H}}\mathopen{}\mathclose{{}\left(\bm{x},\bm{y}}\right)=|\mathopen{}\mathclose{{}\left\\{i\in\mathds{N}\mid\bm{x}_{i}\neq\bm{y}_{i}}\right\\}|$
denote the Hamming distance of $\bm{x}$ and $\bm{y}$. For each $r\in[n]$, we
define the _$r$ -bit flip neighborhood of $\bm{x}$_ to be the set
$\mathopen{}\mathclose{{}\left\\{\bm{y}\in\\{0,1\\}^{n}\mid
d_{\mathrm{H}}\mathopen{}\mathclose{{}\left(\bm{x},\bm{y}}\right)=r}\right\\}$.

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).

##  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 vector (the _frequency
vector_). The flex-EA updates its frequency vector in each iteration, aiming
to give promising rates a high probability. This 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. The result
is a basically parameter-less algorithm that can be thought of as a
superposition of heavy-tailed mutation (Doerr et al., 2017) and stagnation
detection (Rajabi and Witt, 2023).

#### Update of the frequency vector.

The update of the vector $\bm{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. If a rate repeatedly fails to be successful,
the probability of choosing it (called its _frequency_) is reduced. To this
end, the flex-EA groups all rates into those that receive a high frequency
(called _active_) and those that receive a low frequency (called _inactive_).

The active frequencies follow a uniform distribution. Each active frequency
has a counter of how often it failed to succeed. If this counter exceeds a
user-defined limit, the respective frequency becomes inactive. If this results
in no frequencies being active and the frequency at index $r\in[n]$ was the
last active one, then the frequency at index $r+1$ is set to active
(identifying $n+1$ with $1$).

The update process is superimposed by user-defined lower bounds per frequency.
If a frequency would be set to a value less than its lower bound, it takes on
its lower bound instead.

In addition, the flex-EA keeps a global counter that counts how many times in
a row no success was achieved with any mutation rate. If this counter reaches
a specific limit, all frequencies become inactive, and the frequency at
position $1$ becomes active. This effectively resets the frequency vector.

#### The flex-EA in more detail.

Algorithm 1 shows the detailed flex-EA. The frequency vector is denoted by
$\bm{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_ $\bm{\ell}\in[0,1]^{n}$. We assume
that $\sum_{i\in[n]}\bm{\ell}_{i}\leq 1$.

1 $t\leftarrow 0$;

2 $g^{(t)}\leftarrow 0$;

3 $A^{(t)}\leftarrow\\{1\\}$;

4 for  _$i\in[n]$_ do $\bm{c}^{(t)}_{i}\leftarrow 0$;

5 $\bm{x}^{(t)}\leftarrow$ solution from $\\{0,1\\}^{n}$ chosen uniformly at
random;

6 while  __termination criterion not met__ do

7 $\bm{p}^{(t)}\leftarrow$ distribute probability mass over $A^{(t)}$,
respecting $\bm{\ell}$ (Algorithm 2);

8 $m\leftarrow\min A^{(t)}$;

9 $G^{(t)}\leftarrow\frac{\bm{C}_{m}}{\bm{p}^{(t)}_{m}}$;

10 choose $r\in[n]$ according to $\bm{p}^{(t)}$;

11 $\bm{y}^{(t)}\leftarrow$ copy $\bm{x}^{(t)}$ and flip $r$ bits uniformly at
random in this copy;

12 if  _$f\mathopen{\big{(}}\bm{y}^{(t)}\mathclose{\big{)}}
>f\mathopen{\big{(}}\bm{x}^{(t)}\mathclose{\big{)}}$_ then

13 $\bm{x}^{(t+1)}\leftarrow\bm{y}^{(t)}$;

14 $A^{(t+1)}\leftarrow A^{(t)}\cup\\{r\\}$;

15 $g^{(t+1)}\leftarrow 0$;

16 $\bm{c}^{(t+1)}_{r}\leftarrow 0$;

17

18 else

19 if
_$f\mathopen{\big{(}}\bm{y}^{(t)}\mathclose{\big{)}}=f\mathopen{\big{(}}\bm{x}^{(t)}\mathclose{\big{)}}$_
then $\bm{x}^{(t+1)}\leftarrow\bm{y}^{(t)}$;

20 $g^{(t+1)}\leftarrow g^{(t)}+1$;

21 $\bm{c}^{(t+1)}_{r}\leftarrow\bm{c}^{(t)}_{r}+1$;

22 if  _$g^{(t+1)}\geq G^{(t)}$_ then

23 $g^{(t+1)}\leftarrow 0$;

24 $A^{(t+1)}\leftarrow\\{1\\}$;

25 $\bm{c}^{(t+1)}_{1}\leftarrow 0$;

26

27 else if  _$\bm{c}^{(t+1)}_{r}\geq\bm{C}_{r}$_ then

28 $A^{(t+1)}\leftarrow A^{(t)}\smallsetminus\\{r\\}$;

29 if  _$A^{(t+1)}=\emptyset$_ then

30 $r^{\prime}\leftarrow$ if  _$r+1\leq n$_ then $r+1$ else $1$;

31 $A^{(t+1)}\leftarrow A^{(t+1)}\cup\\{r^{\prime}\\}$;

32 $\bm{c}^{(t+1)}_{r^{\prime}}\leftarrow 0$;

33

34

35

36 $t\leftarrow t+1$;

37

Algorithm 1 The flexible evolutionary algorithm (flex-EA) with given lower-
bound vector $\bm{\ell}$ and count bound vector $\bm{C}$, maximizing a pseudo-
Boolean function $f\colon\\{0,1\\}^{n}\to\mathds{R}$, stopping at a user-
defined termination criterion.

Furthermore, each rate $i\in[n]$ has a counter $\bm{c}_{i}\in\mathds{N}$ for
counting its number of failed attempts to improve the current solution. If
$\bm{c}_{i}$ reaches a user-defined limit $\bm{C}_{i}\in\mathds{R}_{\geq 0}$,
then frequency $i$ becomes inactive. These limits are provided by the user as
the _count bound vector_ $\bm{C}\in\mathds{R}_{\geq 0}^{n}$.

The global counter is denoted by $g\in\mathds{N}$. Its limit that, if reached,
resets the archive of the flex-EA is denoted by $G\in\mathds{R}_{\geq 0}$. The
value $G$ is chosen as the count bound of the smallest active rate $m\in[n]$
divided by its current frequency. This resembles the normal bound $\bm{C}_{m}$
but accounts for rate $m$ being only chosen once in $\bm{p}_{m}^{-1}$
iterations in expectation.

The update of the frequency vector is a bit involved, as frequencies may be
capped by their respective lower bound, thus disallowing to distribute the
probability mass uniformly among all active frequencies. Note that the flex-EA
aims to give each active frequency the same probability. The total probability
to distribute among these $|A|\eqqcolon\varphi$ frequencies is
$1-\sum_{i\in[n]\smallsetminus A}\bm{\ell}_{i}\eqqcolon M$, as all inactive
frequencies are at their respective lower bound. Hence, each active frequency
should get a probability of $\frac{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
$\frac{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.

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 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.

1 $M\leftarrow 1-\sum_{i\in[n]\smallsetminus A}\bm{\ell}_{i}$;

2 for  _$i\in[n]\smallsetminus A$_ do $\bm{p}_{i}\leftarrow\bm{\ell}_{i}$;

3 $\varphi\leftarrow|A|$;

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

5 for  _$i\in[\varphi]$_ do

6 if  _$\bm{\ell}_{S_{i}}\leq\frac{M}{\varphi-i+1}$_ then

7 for  _$j\in[i..\varphi]$_ do
$\bm{p}_{S_{j}}\leftarrow\frac{M}{\varphi-i+1}$;

8 return _$\bm{p}$_ ;

9

10 else

11 $\bm{p}_{S_{i}}\leftarrow\bm{\ell}_{S_{i}}$;

12 $M\leftarrow M-\bm{\ell}_{S_{i}}$;

13

14

15return _$\bm{p}$_ ;

Algorithm 2 The algorithm that, given an index set $A\subseteq[n]$ and a
lower-bound vector $\bm{\ell}$ of size $n$, returns a frequency vector
$\bm{p}$ of size $n$ where all possible probability mass is distributed as
evenly as possible over the frequencies with indices in $A$, respecting
$\bm{\ell}$.

###  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
$\bm{\ell}$, we recommend to choose a heavy-tailed distribution, inspired by
the fast-mutation operator (Doerr et al., 2017). For the count bound vector
$\bm{C}$, we recommend to choose the same values as for stagnation detection
(Rajabi and Witt, 2023). 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\colon(1,2)\to\mathds{R}_{\geq 1}$ denote a normalization with
$N\colon\alpha\mapsto\sum_{i\in[n]}i^{-\alpha}$. We recommend for all
$i\in[n]$ to choose

$\displaystyle\bm{\ell}_{i}=\frac{1}{2N\mathopen{}\mathclose{{}\left(\beta}\right)missing}i^{-\beta}.$

Note that $\sum_{i\in[n]}\bm{\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
(Doerr et al., 2017). 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. (2017) name the variant of the $(1+1)$
EA that uses fast mutation the Fast (1+1) EA.

Doerr et al. (2017) choose the heavy-tailed distribution because even large
rates have a reasonable probability of at least $\frac{1}{n^{2}}$ of being
chosen. 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 $\textsc{Jump}_{k}$ and 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\mathds{R}_{>1}$. We recommend

$\displaystyle\bm{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 (2023). In their paper, the authors introduce
the algorithm _SD-RLS ${}^{\text{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${}^{\text{r}}$ starts with rate $1$ and counts how many times it used this
rate. It then uses rate $1$ for at most $\bm{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${}^{\text{r}}$ chooses rate $2$ from now on, for a total of at most
$\bm{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${}^{\text{r}}$ only tries out rates up to $\frac{n}{2}$, but the
formula for the bounds generalizes to all values in $[n]$.

Rajabi and Witt (2023) 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${}^{\text{r}}$ find
this improvement with probability at least $1-R^{-1}$, as the probability of
not doing so is at most $\big{(}1-\binom{n}{r}^{-1}\big{)}^{\bm{C}_{r}}\leq
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${}^{\text{r}}$, 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\mathds{R}_{>1}$. However, the exact choice of these parameters is
typically not very relevant, as we show in this article. Doerr et al. (2017)
recommend to choose $\beta=\frac{3}{2}$. Since the flex-EA can act similarly
to the algorithm discussed by Doerr et al. (2017), we recommend this choice
too. For the parameter $R$, Rajabi and Witt (2023) show that a choice of
$R\geq 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. However,
one needs to keep in mind that the flex-EA allows to choose its parameters
$\bm{\ell}$ and $\bm{C}$ more flexibly, which can be a good choice if given
extra information (see also Section 7).

##  5\. Runtime on Unimodal Functions

We analyze the flex-EA on unimodal pseudo-Boolean functions, that is,
functions $f\colon\\{0,1\\}^{n}\to\mathds{R}$ with a unique global optimum
$\bm{z}^{*}\in\\{0,1\\}^{n}$ such that, for all
$\bm{x}\in\\{0,1\\}^{n}\smallsetminus\\{\bm{z}^{*}\\}$, there is a
$\bm{y}\in\\{0,1\\}^{n}$ with
$d_{\mathrm{H}}\mathopen{}\mathclose{{}\left(\bm{x},\bm{y}}\right)=1$ such
that
$f\mathopen{}\mathclose{{}\left(\bm{x}}\right)<f\mathopen{}\mathclose{{}\left(\bm{y}}\right)$.
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 5.1.

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 $\bm{z}$ in fitness level $j$, flipping a single bit in $\bm{z}$
creates an offspring with strictly better fitness. Furthermore, consider the
flex-EA with $\bm{\ell}_{1}>0$.

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

$\displaystyle 1+\bm{\ell}_{1}^{-1}\sum\nolimits_{j\in[L-1]}q_{j}^{-1}.$

Especially, it is at most $1+n(L-1)\bm{\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 A.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
$\bm{\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 $\bm{\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}\geq\frac{1}{n}$. Applying the first claim
concludes the proof. ∎

Theorem 5.1 leads to useful bounds on various functions. For example, the
coarser bound at the end results already in the common expected runtime of
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{2}}\right)$ for the LeadingOnes
benchmark (Rudolph, 1997) 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 $\mathrm{O}\mathopen{}\mathclose{{}\left(n\log
n}\right)$ for the OneMax benchmark, as we show below (Corollary 5.2). 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_ ($\mathrm{OM}_{k}$) be defined as

$\displaystyle\bm{x}\mapsto\begin{cases}k+\mathrm{OM}\mathopen{}\mathclose{{}\left(\bm{x}}\right)&\textrm{if
$|\bm{x}|_{1}\leq n-k$,}\\\
n-\mathrm{OM}\mathopen{}\mathclose{{}\left(\bm{x}}\right)&\textrm{else.}\end{cases}$

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

###### Corollary 5.2.

Let $k\in[0..n]$. Consider the flex-EA with $\bm{\ell}_{1}>0$ optimizing
$\mathrm{OM}_{k}$. Then the expected runtime is
$\mathrm{O}\mathopen{\big{(}}\bm{\ell}_{1}^{-1}n\log(n)\mathclose{\big{)}}$.

###### Proof.

We apply Theorem 5.1 and use its notation. For all $j\in[n+1]$, denote the
fitness level that represents an $\mathrm{OM}_{k}$-value of $j-1$. We say that
individuals with at most $n-k$ $1$s are on the _left branch_ of the function,
and the other ones on the _right branch_.

Let $j\in[n]$. We bound $q_{j}$ 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$ $1$s. If mutation flips any of the $n-j+1+k$ $0$s, then the result
strictly improves the fitness. Hence, $q_{j}=\frac{n-j+1+k}{n}$.

If the current individual is on the right branch, it has $n-j+1$ $1$s. If
mutation flips any of these $1$s, then the result strictly improves the
fitness. Hence, $q_{j}=\frac{n-j+1}{n}$.

Combining both cases, by Theorem 5.1 and disregarding the plus $1$, we obtain
an upper bound on the expected runtime of

$\displaystyle\bm{\ell}_{1}^{-1}\sum_{j\in[n]}\mathopen{}\mathclose{{}\left(\frac{n}{n-j+1+k}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{j\geq
k+1}\right\\}+\frac{n}{n-j+1}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{j<k+1}\right\\}}\right)$
$\displaystyle\leq\bm{\ell}_{1}^{-1}\cdot
2n\sum\nolimits_{j\in[n]}j^{-1}=\mathrm{O}\mathopen{\big{(}}\bm{\ell}_{1}^{-1}n\log(n)\mathclose{\big{)}}.\qed$

##  6\. Runtime on Jump Functions

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

$\displaystyle\bm{x}\mapsto\begin{cases}k+\mathrm{OM}\mathopen{}\mathclose{{}\left(\bm{x}}\right)&\textrm{if
$|\bm{x}|_{1}\in[n-k]\cup\\{n\\}$,}\\\
n-\mathrm{OM}\mathopen{}\mathclose{{}\left(\bm{x}}\right)&\textrm{else.}\end{cases}$

This function is identical to $\mathrm{OM}_{k}$ except that its unique global
optimum is at the all-$1$s bit string. Consequently, the individuals with
exactly $n-k$ $1$s 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$ $0$s 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 (Doerr and Rajabi, 2023).

With Corollary 6.2, 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.1.

Let $R\in\mathds{R}_{>1}$ and $k\in[2..n]$. Consider the flex-EA with the
standard-SD choice $\bm{C}$ with parameter $R$ and with lower bounds
$\bm{\ell}$ such that $\bm{\ell}_{1},\bm{\ell}_{k}>0$ and
$1-\sum_{i\in[n]\smallsetminus\\{k\\}}\bm{\ell}_{i}=\Theta\mathopen{}\mathclose{{}\left(1}\right)$.
Furthermore, consider that the flex-EA optimizes $\textsc{Jump}_{k}$. Let
$L=(1-\sum\nolimits_{i\in[n]\smallsetminus\\{k\\}}\bm{\ell}_{i})^{-1}$. Then
the expected runtime is

$\displaystyle\mathrm{O}\mathopen{}\mathclose{{}\left(n\bm{\ell}_{1}^{-1}\log(nR)}\right)+\min\Bigg{\\{}\binom{n}{k}\cdot\bm{\ell}_{k}^{-1},$
$\displaystyle\qquad\binom{n}{k}\cdot\mathopen{}\mathclose{{}\left(L+\mathrm{O}\mathopen{}\mathclose{{}\left(\frac{k}{n-2k+3}\log(R)}\right)+\bm{\ell}_{k}^{-1}R^{-1/L}}\right)$
$\displaystyle\qquad+2^{n}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{k\geq\frac{n}{2}}\right\\}\ln(R)\Bigg{\\}}.$

###### Proof.

Let $T$ denote the runtime of the algorithm on $\textsc{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
iteration that phase $1$ stops and 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
$\mathrm{E}\mathopen{}\mathclose{{}\left[T}\right]=\mathrm{E}\mathopen{}\mathclose{{}\left[T_{1}}\right]+\mathrm{E}\mathopen{}\mathclose{{}\left[T_{2}}\right]$.
We consider the expectations of both phases separately.

Phase $\bm{1}$. Note that the time until the algorithm finds an optimum of
$\mathrm{OM}_{k}$ is an upper bound for $T_{1}$. Hence, the same is true for
their expectations. By Corollary 5.2, we obtain
$\mathrm{E}\mathopen{}\mathclose{{}\left[T_{1}}\right]=\mathrm{O}\mathopen{\big{(}}\bm{\ell}_{1}^{-1}n\log(n)\mathclose{\big{)}}$.

Phase $\bm{2}$. Note that before the global optimum is found, no rate enters
the archive due to being successful, since the global optimum is the only
remaining strictly better solution. We bound the expected time of this phase
in two different ways. The first way relies exclusively on the lower bound
$\bm{\ell}_{k}$ for sampling the global optimum, and the second way considers
a course of events similar to stagnation detection. It assumes that rate $1$
is active in iteration $T_{1}$, that is, at the beginning of phase $2$.
Calling the respective bounds $B_{1}$ and $B_{2}$, we then conclude that
$\mathrm{E}\mathopen{}\mathclose{{}\left[T_{2}}\right]\leq\min\\{B_{1},B_{2}\\}$,
as either bound is valid.

1\. Relying only on the lower bound. In each iteration, the probability for
choosing rate $k$ is at least $\bm{\ell}_{k}$. Then, since the current
individual has exactly $k$ $0$s, the probability to mutate it into the global
optimum is $\binom{n}{k}^{-1}$. Hence, in each iteration, the probability to
create the global optimum is at least $\bm{\ell}_{k}\binom{n}{k}^{-1}\eqqcolon
q$. Since each iteration has an independent chance to create the global
optimum, $T_{2}$ follows a geometric distribution with a success probability
of at least $q$. Hence,
$\mathrm{E}\mathopen{}\mathclose{{}\left[T_{2}}\right]\leq
q^{-1}=\bm{\ell}_{k}^{-1}\binom{n}{k}$.

2\. Rate $\bm{1}$ is active at the start. Let $D$ denote the event that $1\in
A^{(T_{1})}$, and assume that $D$ occurs. Then
$G^{(T_{1})}=\bm{C}_{1}/\bm{p}^{(T_{1})}_{1}\leq\bm{C}_{1}/\bm{\ell}_{1}$.
Thus, if no strict improvement is found within at most
$\bm{C}_{1}/\bm{\ell}_{1}$ iterations, the algorithm reverts to classic
stagnation detection. Since the current individual is on the plateau, finding
a strict improvement means to find the global optimum (and thus ending the
phase).

Let $T_{2,1}$ denote the first time in phase $2$ such that
$g^{(T_{2,1}+T_{1})}\geq\bm{C}_{1}/\bm{\ell}_{1}$, and let
$T_{2,2}=T_{2}-T_{2,1}$. Since no mutation rate but $k$ can lead to creating
the global optimum, the global counter increases at most
$\bm{C}_{1}/\bm{\ell}_{1}$ times. Hence,
$T_{2,1}\leq\bm{C}_{1}/\bm{\ell}_{1}$, and thus
$\mathrm{E}[T_{2,1}\,|\,D]\leq\bm{C}_{1}/\bm{\ell}_{1}$.

After $T_{2,1}$, if the algorithm did not find the optimum yet, it performs
classic stagnation detection by maintaining a single active rate, based on
$\bm{C}$. Since all rates in $[k-1]$ cannot lead to an improvement, a total of
$\sum_{i\in[k-1]}\binom{n}{i}\ln(R)$ iterations is spent until rate $k$
becomes active. For $k\leq\frac{n}{2}$, we obtain by Lemma A.2

$\displaystyle\sum\nolimits_{i\in[k-1]}\binom{n}{i}\ln(R)$
$\displaystyle\leq\frac{n-(k-2)}{n-(2k-3)}\binom{n}{k-1}\ln(R)$
$\displaystyle=\frac{n-(k-2)}{n-(2k-3)}\frac{k}{n-k+1}\binom{n}{k}\ln(R)$
$\displaystyle=\mathrm{O}\mathopen{}\mathclose{{}\left(\frac{k}{n-2k+3}}\right)\binom{n}{k}\ln(R).$

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

Overall, for
$\gamma\coloneqq\mathrm{O}\mathopen{}\mathclose{{}\left(\frac{k}{n-2k+3}}\right)\binom{n}{k}+2^{n}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{k>\frac{n}{2}}\right\\}$,
it takes at most $\gamma\ln(R)$ iterations until rate $k$ is active or the
optimum is found.

Assume that the optimum is not found until rate $k$ is active. Let $S$ denote
the event that the algorithm samples the optimum within the next
$\bm{C}_{k}\ln(R)$ iterations. The probability (unconditional on $S$) to
create the optimum in a single iteration is
$(1-\sum_{i\in[n]\smallsetminus\\{k\\}}\bm{\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 (Rajabi and Witt, 2023) and is dominated by a geometric
distribution with success probability $L^{-1}\binom{n}{k}^{-1}$, since the
actual process stops after at most $\bm{C}_{k}\ln(R)$ attempts. Hence,
$\mathrm{E}[T_{2,2}\,|\,D,S]\leq\gamma\ln(R)+L\binom{n}{k}$.

In the case that $S$ does not hold, we use the same arguments as when relying
only on $\bm{\ell}_{k}$ and obtain
$\mathrm{E}[T_{2,2}\,|\,D,\overline{S}]\leq\gamma\ln(R)+\bm{\ell}_{k}^{-1}\binom{n}{k}$.

Next, we trivially bound
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[D,S}\right]\leq 1$ as well as
$\mathrm{Pr}[D,\overline{S}]\leq\mathrm{Pr}[\overline{S}\,|\,D]$. By the
definition of $S$, the estimates above of finding the global optimum in a
single iteration, as well as that $\binom{n}{k}=\bm{C}_{k}$ due to the
standard-SD choice,
$\mathrm{Pr}[\overline{S}\,|\,D]\leq\big{(}1-L^{-1}\bm{C}_{k}^{-1}\big{)}^{\bm{C}_{k}\ln(R)}\leq
R^{-1/L}$. Thus, we obtain

$\displaystyle\mathrm{E}\mathopen{}\mathclose{{}\left[T_{2}\,\middle|\,D}\right]$
$\displaystyle\leq\frac{\bm{C}_{1}}{\bm{\ell}_{1}}+\gamma\ln(R)+L\binom{n}{k}+\bm{\ell}_{k}^{-1}\binom{n}{k}R^{-1/L}.$

We conclude by trivially bounding
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[D}\right]\leq 1$ and by adding the
term $\bm{C}_{1}/\bm{\ell}_{1}=n\bm{\ell}_{1}^{-1}\ln(R)$ also to our first
bound for phase $2$. ∎

Theorem 6.1 shows the intricate interplay of the parameters of the flex-EA.
For $k\geq\frac{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 the order of at least the central binomial coefficient,
which is exponential in $n$.

In contrast, if $k<\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 for this case to occur.

The following corollary summarizes how the expected runtime improves with the
recommended parameter choices. Up to a factor of
$2+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$, 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 bounds, which take up a total
probability mass of $\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}$.

###### Corollary 6.2.

Let $\beta\in(1,2)$ and $\varepsilon\in\mathds{R}_{>0}$ be constants, let
$R=n^{2(\beta+\varepsilon)}$, and let $k\in[2..n]$. Consider the flex-EA with
the standard-SD choice $\bm{C}$ with parameter $R$ and with heavy-tailed lower
bounds $\bm{\ell}$. Furthermore, consider that the flex-EA optimizes
$\textsc{Jump}_{k}$. Then the expected runtime is

$\displaystyle\big{(}1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)\big{)}\min\Bigg{\\{}\binom{n}{k}\cdot
2N\mathopen{}\mathclose{{}\left(\beta}\right)k^{\beta},$ $\displaystyle\
\binom{n}{k}\cdot\mathopen{}\mathclose{{}\left(2+\mathrm{O}\mathopen{}\mathclose{{}\left(\frac{k}{n-2k+3}\log(n)+n^{-\varepsilon}}\right)}\right)+2^{n}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{k\geq\frac{n}{2}}\right\\}\ln(R)\Bigg{\\}}.$

Especially, for
$k=\mathrm{o}\mathopen{}\mathclose{{}\left(\frac{n}{\log(n)}}\right)$, this
simplifies to
$\big{(}2+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\binom{n}{k}$.

###### Proof.

The first bound follows from Theorem 6.1. Due to the assumptions on
$\bm{\ell}$, it holds that
$\bm{\ell}_{1}^{-1}=\Theta\mathopen{}\mathclose{{}\left(1}\right)$, that
$\bm{\ell}_{k}=\frac{1}{2N\mathopen{}\mathclose{{}\left(\beta}\right)missing}k^{-\beta}$,
and that $1-\sum_{i\in[n]\smallsetminus\\{k\\}}\bm{\ell}_{i}\geq\frac{1}{2}$.
Furthermore, due to the choice of $R$, it follows that
$\mathrm{O}\mathopen{}\mathclose{{}\left(n\bm{\ell}_{1}^{-1}\log(nR)}\right)=\mathrm{O}\mathopen{}\mathclose{{}\left(n\log(n)}\right)$.
Since $k\geq 2$, the other summand is
$\Omega\mathopen{}\mathclose{{}\left(n^{2}}\right)$, so the summand
$\mathrm{O}\mathopen{}\mathclose{{}\left(n\bm{\ell}_{1}^{-1}\log(nR)}\right)$
is of lower order. Last, since $L^{-1}\geq\frac{1}{2}$, it follows that
$R^{-1/L}\leq R^{-1/2}\leq n^{-(\beta+\varepsilon)}$. Substituting all of the
values yields the desired result.

For the case
$k=\mathrm{o}\mathopen{}\mathclose{{}\left(\frac{n}{\log(n)}}\right)$, note
that
$\frac{k}{n-2k+3}\log(n)=\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$.
Hence, the second term in the minimum is
$\big{(}2+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\binom{n}{k}$.
This term is smaller than the first term in the minimum, since
$N\mathopen{}\mathclose{{}\left(\beta}\right)\geq 1$ as well as $k^{\beta}\geq
2$, concluding the proof. ∎

##  7\. Benefits of the Rate Archive on Minimum Spanning Trees

The prior works on SD-RLS${}^{\text{r}}$ (i. e., RLS with a classical
stagnation detection mechanism) in (Rajabi and Witt, 2023) and on SD-
RLS${}^{\text{m}}$, a variant with a radius memory, in (Rajabi and Witt, 2021)
include analyses of the algorithms on the classical minimum spanning tree
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
$\mathrm{O}\mathopen{}\mathclose{{}\left(m^{2}(\log n+\log w_{\max})}\right)$,
where $n$ is the number of vertices, $m$ the number of edges and $w_{\max}$ is
the largest edge weight, from the seminal work (Neumann and Wegener, 2007)
analyzing the (1+1) EA on the MST problem. It is well known (Reichel and
Skutella, 2009) that the dependency of the bound on $w_{\max}$ can be removed
and that the runtime bound $\mathrm{O}\mathopen{}\mathclose{{}\left(m^{3}\ln
n}\right)$ 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=\lvert V\rvert$, $m=\lvert E\rvert$ and the weight of edge $e_{i}$, where
$i\in\\{1,\dots,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}$. The fitness function $f\colon\\{0,1\\}^{m}\to\mathds{R}$
considered in (Neumann and Wegener, 2007), to be minimized, is defined by

$f(x)\coloneqq
M^{2}(c(x)-1)+M\mathopen{}\mathclose{{}\left(\sum\nolimits_{i\in[m]}x_{i}-(n-1)}\right)+\sum\nolimits_{i\in[m]}w_{i}x_{i}$

for an integer $M\geq 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 (Rajabi and
Witt, 2023) showed that SD-RLS${}^{\text{r}}$ starting with an arbitrary
spanning tree finds an MST in $(1+o(1))\bigl{(}m^{2}\ln m+(4m\ln
m)\mathrm{E}\mathopen{}\mathclose{{}\left[S}\right]\bigr{)}$ fitness calls
where $\mathrm{E}\mathopen{}\mathclose{{}\left[S}\right]$ is the expected
number of strict improvements. The variant SD-RLS${}^{\text{m}}$ with radius
memory analyzed in (Rajabi and Witt, 2021) has an expected runtime of at most

$(1+o(1))\bigl{(}(m^{2}/2)(1+\ln({\textstyle\sum_{i\in[m]}}r_{i}))\bigr{)}\leq(1+o(1))\bigl{(}m^{2}\ln
m\bigr{)},$

where $r_{i}$ is the rank of the $i$th edge in the sequence sorted by
increasing edge weights. This holds since SD-RLS${}^{\text{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_{1},\dots,w_{m}$ is replaced by the rank number $r_{i}$ (Raidl et al.,
2006). Essentially, the bound for SD-RLS${}^{\text{m}}$ is better by a factor
of $2$ than for the classical RLS1,2 algorithm choosing uniformly at random a
rate $r\in\\{1,2\\}$ and flipping $r$ bits uniformly. In fact, RLS1,2 wastes
every second step since $1$-bit flips are never accepted on spanning trees.

We obtain Theorem 7.1 below. Choosing
$\bm{\ell}_{1}=\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$, it matches
the bound from (Rajabi and Witt, 2021). 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 (Rajabi and
Witt, 2021). Finally, it assumes a uniform starting point instead of an
initialization with a spanning tree as in(Rajabi and Witt, 2021).

We note that the parameter settings for the $\bm{C}_{i}$ and particularly the
$\bm{\ell}_{i}$ in Theorem 7.1 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$. If the expected value was to hold conditioned on
an event of probability $1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$
only, then the conditions on $\bm{\ell}_{i}$ for $i\geq 3$ could be relaxed.

###### Theorem 7.1.

Consider an instance to the MST problem, modeled with the classical fitness
function from (Neumann and Wegener, 2007). Let flex-EA with the following
parameter settings run on this function:

  * •

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

  * •

$\bm{\ell}_{1}=\upomega\mathopen{}\mathclose{{}\left(1/\ln m}\right)$ and
$\bm{\ell}_{1}\leq 1/2$

  * •

$\bm{\ell}_{2}=\Omega\mathopen{}\mathclose{{}\left(1/(m^{2}\ln m)}\right)$,
and
$\bm{\ell}_{i}=\mathrm{o}\mathopen{\big{(}}1/(m^{5}\ln^{2}m)\mathclose{\big{)}}$
for $i=3..n$.

Then with probability $1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$,
the runtime is at most

$\displaystyle((1-\bm{\ell}_{1})^{-1}+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\bigl{(}(m^{2}/2)(1+\ln({\textstyle\sum_{i\in[m]}}r_{i}))\bigr{)}$
$\displaystyle\quad\leq((1-\bm{\ell}_{1})^{-1}+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\bigl{(}m^{2}\ln
m\bigr{)},$

where $r_{i}$ is the rank of the $i$th edge in the sequence sorted by
increasing edge weights. The expected runtime is bounded in the same way.

The proof had to be omitted from this paper. Its main idea is to consider a
phase of length
$\Theta\mathopen{}\mathclose{{}\left((1-\bm{\ell}_{1})^{-1}m^{2}\ln m}\right)$
after finding the first spanning tree and to show that within the phase, the
archive only contains rates $1$ and $2$ w. h. p. Then the above-mentioned
stochastic equivalence to RLS with a 2-bit flip neighborhood is applied.

##  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 (Rajabi
and Witt, 2021), 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 (Nguyen and Sudholt, 2018) 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\coloneqq(3/4)n-\sqrt{n}$, $(3/4)n$, $g\coloneqq\log n$
and $\sqrt{n}/g$ are integers. We define

$\textsc{TwoRates}(x)\coloneqq\begin{cases}\mathrm{OM}(x)&\text{if $\lvert
x\rvert<s$ or $\lvert x\rvert\geq(3/4)n$}\\\ &\text{or $\lvert x\rvert=s+ig$
for $i\in\\{0,2,3,5,6,\dots\\}$},\\\ -1&\text{otherwise},\end{cases}$

where the values of $i$ alternatingly increase by $2$ and $1$.

The hurdles of width $g$, which are located in the interval $[s..3n/4]$ for
the number of one-bits, are overcome at the corresponding rate with
probability at least

$\displaystyle\frac{\binom{n/4}{g}}{\binom{n}{g}}\geq\mathopen{}\mathclose{{}\left(\frac{n/4-g}{n}}\right)^{g}=\mathopen{}\mathclose{{}\left(1-\frac{\mathrm{O}\mathopen{}\mathclose{{}\left(\log
n}\right)missing}{n}}\right)^{\log n}4^{-\log
n}=\frac{(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))}{n^{2}}$

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

(1) $\displaystyle\frac{\binom{n/4+\sqrt{n}}{g}}{\binom{n}{g}}$
$\displaystyle\leq\mathopen{}\mathclose{{}\left(\tfrac{n/4+\sqrt{n}}{n-g}}\right)^{g}=2^{\log(1/4+\mathrm{O}\mathopen{}\mathclose{{}\left(1/\sqrt{n}}\right))(\log
n)}\leq\tfrac{(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))}{n^{2}}$

and accordingly those of width $2g$ with the probability bounds
$(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))/n^{4}$ and
$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))/n^{4}$, respectively.

We now prove that the flex-EA optimizes TwoRates efficiently, while classical
stagnation detection algorithms with and without radius memory need
superpolynomial time. Moreover, the Fast (1+1) EA from (Doerr et al., 2017) is
by a at least a polylogarithmic factor of $\Omega\mathopen{\big{(}}(\log
n)^{\beta-1/2}\mathclose{\big{)}}=\upomega\mathopen{\big{(}}\sqrt{\log
n}\mathclose{\big{)}}$ slower than our approach.

###### Theorem 8.1.

The expected runtime of the flex-EA with the recommended parameter set on
TwoRates is bounded by
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4.5}}\right)$. For the stagnation
detection algorithms of the type SD-RLS in (Rajabi and Witt, 2021, 2023) with
typical parameter choice $R=n^{d}$ for a constant $d>0$, the expected runtime
is $n^{\Omega\mathopen{}\mathclose{{}\left(\log n}\right)}$. Moreover, the
expected runtime of the Fast (1+1) EA is by a factor
$\Omega\mathopen{\big{(}}(\log n)^{\beta-1/2}\mathclose{\big{)}}$ larger than
for the flex-EA.

In the proof, we shall need the following useful helper 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 8.2.

Let $x\in\\{0,1\\}^{n}$ be a search point with $a\geq 0$ one-bits and let
$p(n,a,d,i)$, where $d,i\geq 0$, be the probability of mutating $x$ into a
point containing exactly $a+d$ one-bits when flipping $d+2i$ bits uniformly at
random. If $d+2i\leq n^{1/3}$, then
$p(n,a,d,i)/p(n,a,d,0)\leq(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))(\mathrm{e}(2+d/i)(1-a/n))^{i}\leq(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\mathrm{e}^{d+2i}(1-a/n)^{i}$.

The main idea for the upper bound for the flex-EA is as follows: the expected
time to cross a hurdle is
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4}}\right)$ and there are
$\Theta\mathopen{}\mathclose{{}\left(\sqrt{n}/\log n}\right)$ hurdles. The
probability of choosing a beneficial rate of $g$ or $2g$ is
$\Omega\mathopen{}\mathclose{{}\left(1/\log n}\right)$ since the cardinality
of the archive is bounded by $\mathrm{O}\mathopen{}\mathclose{{}\left(\log
n}\right)$ with high probability. The lower bound for the Fast (1+1) EA stems
from the fact that rates of $\Omega\mathopen{}\mathclose{{}\left(\log
n}\right)$ must be chosen with high probability to cross a hurdle, which has
probability $\mathrm{O}((\log n)^{-\beta})$ in the heavy-tailed mutation.
Another factor of $\Theta(\sqrt{\log n})$ is lost since the Fast (1+1) EA uses
standard-bit mutation instead of a flipping a deterministic number of bits.

We conjecture that the runtime of the SD-FEA from (Doerr and Rajabi, 2023) on
TwoRates is asymptotically at least as large as the one of the Fast (1+1) EA.
Essentially, rates in the order $\Omega\mathopen{}\mathclose{{}\left(\log
n}\right)$ must be used to obtain a sufficient probability of crossing a
hurdle. Then in the same way as described above, the selection probability
$\mathrm{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 results in an essentially
parameter-less algorithm. Using this recommended 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 problem that features repetitive
sub-structures, this configuration outperforms the Fast (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.

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 shifted jump benchmarks (Witt, 2023), the combination of heavy-
tailed mutation and stagnation detection by Doerr and Rajabi (2023) should
prove superior, as the flex-EA basically defaults to classic stagnation
detection. However, this shortcoming can be overcome by adjusting the mutation
of the flex-EA in a similar way as done by Doerr and Rajabi (2023) for their
algorithm. Another potential shortcoming is that the archive of the flex-EA
can become very crowded when many different mutation rates prove useful. If
the mutation rates are removed in an incorrect order, this can result in long
waiting times. It is unclear under what circumstances this effect actually
occurs.

Overall, the flex-EA proposes an arguably new paradigm for evolutionary
algorithms that performs very well and can be studied in multiple domains that
exceed the content of this paper.

## References

  * (1)
  * Antipov et al. (2022) Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2022\.  Fast mutation in crossover-based algorithms.  _Algorithmica_ 84 (2022), 1724–1761.  https://doi.org/10.1007/s00453-022-00957-5
  * Antipov and Doerr (2020) Denis Antipov and Benjamin Doerr. 2020.  Runtime analysis of a heavy-tailed ${(1+(\lambda,\lambda))}$ genetic algorithm on jump functions. In _Prof. of PPSN ’20_. Springer, 545–559.  https://doi.org/10.1007/978-3-030-58115-2_38
  * Corus et al. (2021) Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. 2021\.  Fast immune system-inspired hypermutation operators for combinatorial optimization.  _IEEE Transactions on Evolutionary Computation_ 25, 5 (2021), 956–970.  https://doi.org/10.1109/TEVC.2021.3068574
  * Dang et al. (2021) Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2021\.  Escaping local optima with non-elitist evolutionary algorithms. In _Proc. of AAAI ’21_. AAAI Press, 12275–12283.  https://doi.org/10.1609/AAAI.V35I14.17457
  * Dang et al. (2022) Duc-Cuong Dang, Anton V. Eremeev, Per Kristian Lehre, and Xiaoyu Qin. 2022.  Fast non-elitist evolutionary algorithms with power-law ranking selection. In _Proc. of GECCO ’22_. ACM, 1372–1380.  https://doi.org/10.1145/3512290.3528873
  * Doerr (2020) Benjamin Doerr. 2020\.  Probabilistic tools for the analysis of randomized optimization heuristics.  In _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_ , Benjamin Doerr and Frank Neumann (Eds.). Springer, 1–87.  https://doi.org/10.1007/978-3-030-29414-4_1
  * Doerr and Doerr (2015) Benjamin Doerr and Carola Doerr. 2015.  Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings. In _Proc. of GECCO ’15_. ACM Press, 1335–1342.  https://doi.org/10.1145/2739480.2754684
  * Doerr and Doerr (2020) Benjamin Doerr and Carola Doerr. 2020.  Theory of parameter control for discrete black-box optimization: Provable performance gains through dynamic parameter choices.  In _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_ , Benjamin Doerr and Frank Neumann (Eds.). Springer, 271–321.  https://doi.org/10.1007/978-3-030-29414-4_1
  * Doerr et al. (2016) Benjamin Doerr, Carola Doerr, and Jing Yang. 2016.  $k$-bit mutation with self-adjusting $k$ outperforms standard bit mutation. In _Proc. of PPSN ’16_. Springer, 824–834.  https://doi.org/10.1007/978-3-319-45823-6_77
  * Doerr et al. (2022) Benjamin Doerr, Yassine Ghannane, and Marouane Ibn Brahim. 2022\.  Towards a stronger theory for permutation-based evolutionary algorithms. In _Proc. of GECCO ’22_. ACM, 1390–1398.  https://doi.org/10.1145/3512290.3528720
  * Doerr and Goldberg (2013) Benjamin Doerr and Leslie Ann Goldberg. 2013.  Adaptive Drift Analysis.  _Algorithmica_ 65, 1 (2013), 224–250.  https://doi.org/10.1007/S00453-011-9585-3
  * Doerr et al. (2023) Benjamin Doerr, Taha El Ghazi El Houssaini, Amirhossein Rajabi, and Carsten Witt. 2023.  How well does the metropolis algorithm cope with local optima?. In _Proc. of GECCO ’23_. ACM, 1000–1008.  https://doi.org/10.1145/3583131.3590390
  * Doerr et al. (2012) Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012\.  Multiplicative drift analysis.  _Algorithmica_ 64 (2012), 673–697.  https://doi.org/10.1007/s00453-012-9622-x
  * Doerr et al. (2017) Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017.  Fast genetic algorithms. In _Proc. of GECCO ’17_. 777–784.  https://doi.org/10.1145/3071178.3071301
  * Doerr and Neumann (2020) Benjamin Doerr and Frank Neumann (Eds.). 2020.  _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_.  Springer.  https://doi.org/10.1007/978-3-030-29414-4
  * Doerr and Qu (2023) Benjamin Doerr and Zhongdi Qu. 2023.  A first runtime analysis of the NSGA-II on a multimodal problem.  _IEEE Transactions on Evolutionary Computation_ 27, 5 (2023), 1288–1297.  https://doi.org/10.1109/TEVC.2023.3250552
  * Doerr and Rajabi (2023) Benjamin Doerr and Amirhossein Rajabi. 2023.  Stagnation detection meets fast mutation.  _Theoretical Computer Science_ 946 (2023), 113670.  https://doi.org/10.1016/j.tcs.2022.12.020
  * Friedrich et al. (2018a) Tobias Friedrich, Andreas Göbel, Francesco Quinzan, and Markus Wagner. 2018a.  Heavy-tailed mutation operators in single-objective combinatorial optimization. In _Proc. of PPSN ’18_. Springer, 134–145.  https://doi.org/10.1007/978-3-319-99253-2_11
  * Friedrich et al. (2018b) Tobias Friedrich, Francesco Quinzan, and Markus Wagner. 2018b.  Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In _Proc. of GECCO ’18_. ACM, 293–300.  https://doi.org/10.1145/3205455.3205515
  * He and Yao (2001) Jun He and Xin Yao. 2001\.  Drift analysis and average time complexity of evolutionary algorithms.  _Artificial Intelligence_ 127, 1 (2001), 51–81.  https://doi.org/10.1016/S0004-3702(01)00058-3
  * Jansen and Wegener (1999) Thomas Jansen and Ingo Wegener. 1999.  On the analysis of evolutionary algorithms – A proof that crossover really can help. In _Proc. of ESA ’99_. Springer, 184–193.  https://doi.org/10.1007/3-540-48481-7_17
  * Krejca and Witt (2020) Martin Krejca and Carsten Witt. 2020.  Theory of estimation-of-distribution algorithms.  In _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_ , Benjamin Doerr and Frank Neumann (Eds.). Springer, 405–442.  https://doi.org/10.1007/978-3-030-29414-4
  * Kötzing and Krejca (2019) Timo Kötzing and Martin S. Krejca. 2019.  First-hitting times under drift.  _Theoretical Computer Science_ 796 (2019), 51–69.  https://doi.org/10.1016/j.tcs.2019.08.021
  * Lengler (2020) Johannes Lengler. 2020\.  Drift Analysis.  In _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_ , Benjamin Doerr and Frank Neumann (Eds.). Springer, 89–131.  https://doi.org/10.1007/978-3-030-29414-4_1
  * Lissovoi et al. (2020) Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2020\.  Simple Hyper-Heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for LeadingOnes.  _Evolutionary Computation_ 28, 3 (2020), 437–461.  https://doi.org/10.1162/EVCO_A_00258
  * Lissovoi et al. (2023) Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2023\.  When move acceptance selection hyper-heuristics outperform Metropolis and elitist evolutionary algorithms and when not.  _Artificial Intelligence_ 314 (2023), 103804:1–103804:23.  https://doi.org/10.1016/J.ARTINT.2022.103804
  * Neumann and Wegener (2007) Frank Neumann and Ingo Wegener. 2007.  Randomized local search, evolutionary algorithms, and the minimum spanning tree problem.  _Theoretical Computer Science_ 378 (2007), 32–40.  https://doi.org/10.1016/j.tcs.2006.11.002
  * Nguyen and Sudholt (2018) Phan Trung Hai Nguyen and Dirk Sudholt. 2018.  Memetic algorithms beat evolutionary algorithms on the class of hurdle problems. In _Proc. of GECCO ’18_. ACM, 1071–1078.  https://doi.org/10.1145/3205455.3205456
  * Quinzan et al. (2021) Francesco Quinzan, Andreas Göbel, Markus Wagner, and Tobias Friedrich. 2021.  Evolutionary algorithms and submodular functions: Benefits of heavy-tailed mutations.  _Natural Computing_ 20, 3 (2021), 561–575.  https://doi.org/10.1007/s11047-021-09841-7
  * Raidl et al. (2006) Günther R. Raidl, Gabriele Koller, and Bryant A. Julstrom. 2006.  Biased mutation operators for subgraph-selection problems.  _IEEE Transaction on Evolutionary Computation_ 10, 2 (2006), 145–156.  https://doi.org/10.1109/TEVC.2006.871251
  * Rajabi and Witt (2021) Amirhossein Rajabi and Carsten Witt. 2021.  Stagnation detection in highly multimodal fitness landscapes. In _Proc. of GECCO ’21_. ACM Press, 1178–1186.  https://doi.org/10.1145/3449639.3459336
  * Rajabi and Witt (2022) Amirhossein Rajabi and Carsten Witt. 2022.  Self-adjusting evolutionary algorithms for multimodal optimization.  _Algorithmica_ 84, 6 (2022), 1694–1723.  https://doi.org/10.1007/s00453-022-00933-z
  * Rajabi and Witt (2023) Amirhossein Rajabi and Carsten Witt. 2023.  Stagnation detection with randomized local search.  _Evolutionary Computation_ 31, 1 (2023), 1–29.  https://doi.org/10.1162/evco_a_00313
  * Rechenberg (1973) I. Rechenberg. 1973\.  _Evolutionstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution_.  Frommann-Holzboog Verlag.
  * Reichel and Skutella (2009) Joachim Reichel and Martin Skutella. 2009.  On the size of weights in randomized search heuristics. In _Proc. of FOGA 2009_. 21–28.  https://doi.org/10.1145/1527125.1527130
  * Rudolph (1997) Günter Rudolph. 1997\.  _Convergence properties of evolutionary algorithms_.  Verlag Dr. Kovač.
  * Schumer and Steiglitz (1968) M. Schumer and Kenneth Steiglitz. 1968.  Adaptive step size random search.  _IEEE Transactions on Automatic Control_ 13, 3 (1968), 270–276.  https://doi.org/10.1109/TAC.1968.1098903
  * Sudholt (2013) Dirk Sudholt. 2013\.  A new method for lower bounds on the running time of evolutionary algorithms.  _IEEE Transactions on Evolutionary Computation_ 17, 3 (2013), 418–435.  https://doi.org/10.1109/TEVC.2012.2202241
  * Wegener (2001) Ingo Wegener. 2001\.  Theoretical aspects of evolutionary algorithms. In _Proc. of ICALP ’01_. Springer, 64–78.  https://doi.org/10.1007/3-540-48224-5_6
  * Witt (2014) Carsten Witt. 2014\.  Fitness levels with tail bounds for the analysis of randomized search heuristics.  _Information Processing Letters_ 114, 1-2 (2014), 38–41.  https://doi.org/10.1016/J.IPL.2013.09.013
  * Witt (2023) Carsten Witt. 2023\.  How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys.  _Theoretical Computer Science_ 940 (2023), 18–42.  https://doi.org/10.1016/J.TCS.2022.08.014
  * Wu et al. (2018) Mengxi Wu, Chao Qian, and Ke Tang. 2018.  Dynamic mutation based Pareto optimization for subset selection. In _Proc. of ICIC ’18_. Springer, 25–35.  https://doi.org/10.1007/978-3-319-95957-3_4
  * Zarges (2020) Christine Zarges. 2020\.  Theoretical foundations of immune-inspired randomized search heuristics for optimization.  In _Theory of Evolutionary Computation – Recent Developments in Discrete Optimization_ , Benjamin Doerr and Frank Neumann (Eds.). Springer, 443–474.  https://doi.org/10.1007/978-3-030-29414-4_1
  * Zheng and Doerr (2023) Weijie Zheng and Benjamin Doerr. 2023.  Theoretical analyses of multiobjective evolutionary algorithms on multimodal objectives.  _Evolutionary Computation_ 31, 4 (2023), 337–373.  https://doi.org/10.1162/EVCO_A_00328

##  Appendix A Appendix

This appendix contains material that does not fit the main paper, due to space
restrictions. It is meant to be read at the reviewer’s discretion only. It
contains mathematical tools that we use in some of our proofs and proofs that
had to be omitted from the main paper.

## Unimodal Functions

The fitness level method was introduced by Wegener (2001) for the analysis of
evolutionary 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\mathds{N}_{\geq 1}$) such that the fitness increases in each level.
That is, for all $i\in[m-1]$ and all $\bm{x}\in L_{i}$ and $\bm{y}\in
L_{i+1}$, it holds that
$f\mathopen{}\mathclose{{}\left(\bm{x}}\right)<f\mathopen{}\mathclose{{}\left(\bm{y}}\right)$.
We call such a partition a _fitness level partition_ and its elements _fitness
levels._

The following theorem by Sudholt (2013) is used in the proof of Theorem 5.1.

###### Theorem A.1 ((Sudholt, 2013, Theorem $2$)).

Let $f$ be a pseudo-Boolean function, let $m\in\mathds{N}_{\geq 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\nolimits_{i\in[m-1]}\frac{1}{s_{i}}$.

## Jump Functions

The following lemma by Rajabi and Witt (2021) is used in the proof of Theorem
6.1.

###### Lemma A.2 ((Rajabi and Witt, 2021, Lemma $1$ (a))).

Let $n,k\in\mathds{N}$ with $k\leq\frac{n}{2}$. Then
$\sum_{i\in[k]}\binom{n}{i}\leq\frac{n-(k-1)}{n-(2k-1)}\binom{n}{k}$.

## Benefits of the Rate Archive on Minimum Spanning Trees (Section 7)

Drift analysis is the most prominent mathematical tool for analyzing
evolutionary algorithms. It was introduced by He and Yao (2001). We use the
following theorem by Doerr et al. (2012) in the proof of Theorem 7.1,
presented in a version close to the one by Kötzing and Krejca (2019). The tail
bound can be found in (Doerr and Goldberg, 2013) and (Lengler, 2020).

###### Theorem A.3 ((Doerr et al., 2012, Theorem $3$)).

Let $(X_{t})_{t\in\mathds{N}}$ be a Markov chain over $\mathds{R}_{\geq 0}$,
and let $T=\inf\\{t\in\mathds{N}\mid X_{t}<1\\}$. Suppose that there is a
$\delta>0$ such that it holds that
$\mathrm{E}\mathopen{}\mathclose{{}\left[X_{t}-X_{t+1}\,\middle|\,X_{t}}\right]\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{t<T}\right\\}\geq\delta
X_{t}\cdot\mathds{1}\mathopen{}\mathclose{{}\left\\{t<T}\right\\}$. Then
$\mathrm{E}\mathopen{}\mathclose{{}\left[T}\right]\leq(1+\mathrm{E}\mathopen{}\mathclose{{}\left[\ln(X_{0})}\right])/\delta$.
Moreover,
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[T\geq(\mathrm{E}\mathopen{}\mathclose{{}\left[\ln(X_{0})}\right]+r)}\right]\leq\mathrm{e}^{-r}$.

We now give the full proof of Theorem 7.1 that was omitted from the main
paper.

###### Proof of Theorem 7.1.

Similarly to the classical analysis of the (1+1) EA on the problem (Neumann
and Wegener, 2007), we divide the run into three phases. The first two phases
are considered jointly. They can find improvements in the $1$-bit flip
neighborhood by including edges (i. e., flipping zero-bits) and reducing the
number of connected components or by reducing the number of edges from a fully
connected subgraph by flipping one-bits. The expected number of $1$-bit flips
until the first phase is finished is bounded by
$\mathrm{O}\mathopen{}\mathclose{{}\left(m\log m}\right)$ in expectation, as
shown in (Neumann and Wegener, 2007) using fitness-level arguments. Using tail
bounds for fitness levels (Witt, 2014), the number is $c^{\prime}m\ln m$ for
some constant $c^{\prime}>0$ with probability
$1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$. As long as fitness
improvements by 1-bit flips are still available, the expected time until
choosing rate $1$ is at most
$1/\bm{\ell}_{1}=\mathrm{o}\mathopen{}\mathclose{{}\left(\log m}\right)$, so
both in expectation and with high probability after $\mathrm{o}(m\log^{2}m)$
steps a local optimum with respect to the $1$-bit neighborhood has been
reached and the current search point constitutes a (not necessarily minimum)
spanning tree. If the constant $c$ from $\bm{C}_{1}$ is chosen sufficiently
large, then the failure counter $c_{1}$ does not exceed the threshold
$\bm{C}_{1}$ during the considered number of steps at rate $1$ with
probability at least
$1-\mathrm{o}\mathopen{}\mathclose{{}\left(1/m^{2}}\right)$. Moreover, by a
union bound, the probability that mutation rates higher than $2$ are ever
chosen in the considered period is

$\mathrm{O}\mathopen{}\mathclose{{}\left(m\log^{2}m}\right)\sum_{\ell=3}^{m}\bm{\ell}_{i}=\mathrm{o}\mathopen{}\mathclose{{}\left(1/m^{3}}\right),$

which we assume not to happen. Then no rates larger than $2$ are in the
archive $A^{(t)}$ at the end of the period. If rate $2$ is not yet present at
that time, then the global counter $G^{(t)}$ exceeds its threshold after
$\mathrm{O}(m\ln^{2}m)$ steps – and rate $2$ enters the archive after another
$\mathrm{O}\mathopen{}\mathclose{{}\left(\bm{C}_{1}/\bm{\ell}_{1}}\right)=\mathrm{O}(m\ln^{2}m)$
expected number of steps at rate $1$, all of which are unsuccessful. Again,
the probability of rates larger than $2$ entering the archive during that time
is $\mathrm{o}\mathopen{}\mathclose{{}\left(1/m^{3}}\right)$ by the same
arguments as above.

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 using $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 (Raidl et al., 2006, 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^{\prime}>0$ and to conduct the drift analysis conditioned on that only
rates $1$ and $2$ are chosen in a phase of predefined length
$c^{\prime}(1-\bm{\ell}_{1})^{-1}m^{2}\ln m=\mathrm{O}(m^{2}\ln^{2}m)$, using
$\bm{\ell}_{1}\leq 1/2$. Note that in the phase, the steps of rate $1$ cannot
be successful. The probability of only choosing rates at most $2$ throughout
the phase is at least

$1-\mathrm{O}\mathopen{}\mathclose{{}\left(m^{2}\ln^{2}m}\right)\sum_{\ell=3}^{m}\bm{\ell}_{i}=1-\mathrm{O}\mathopen{}\mathclose{{}\left(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 $\bm{c}^{(\cdot)}_{2}$
exceeds its threshold $\bm{C}_{2}$ by
$\mathrm{O}\mathopen{}\mathclose{{}\left(m^{-2}}\right)$ and analyze the error
case at the end of the proof.

Let $X^{(t)}\coloneqq g(x_{t})-g(x_{\mathrm{opt}})$ for the current search
point $x_{t}$ and an optimal search point $x_{\mathrm{opt}}$. Since d-SD RLS
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$,
we obtain that $\mathrm{E}[X^{(t)}-X^{(t+1)}\,|\,X^{(t)}]\geq
X^{(t)}/\binom{m}{2}\geq 2X^{(t)}/m^{2}$ since the $g$-value can be decreased
by altogether $g(x_{t})-g(x_{\mathrm{opt}})$ via a sequence of at most
$\binom{m}{2}$ disjoint two-bit flips; see also the proof of Theorem 15 in
(Doerr et al., 2012) 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 A.3) we
have
$\mathrm{E}\mathopen{}\mathclose{{}\left[T}\right]\leq(m^{2}/2)(1+\ln(r_{1}+\dots+r_{m}))\leq(m^{2}/2)(1+\ln(m^{2}))$
and by the tail bounds for multiplicative drift (e. g., (Lengler, 2020)) it
holds that
$\mathrm{Pr}\mathopen{}\mathclose{{}\left[T>(m^{2}/2)(\ln(m^{2})+\ln(m^{3}))}\right]\leq\mathrm{e}^{-\ln(m^{3})}=1/m^{3}$.
We choose a phase length of $4(1-\bm{\ell}_{1})^{-1}m^{2}\ln m$, which
includes at least $m^{2}\ln m$ steps choosing rate $2$ with probability
$1-\mathrm{e}^{-\Omega\mathopen{}\mathclose{{}\left(m^{2}\ln m}\right)}$
according to Chernoff bounds (Doerr, 2020, Theorem 1.10.5). Assuming this to
happen, we have bounded the probability of not finding the optimum in Phase
$2$ of that length is
$\mathrm{o}\mathopen{}\mathclose{{}\left(m^{-2}}\right)$. The total
probability of any error as described above is still
$\mathrm{o}\mathopen{}\mathclose{{}\left(m^{-2}}\right)$.

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

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/\bm{\ell}_{2})m^{2}=\mathrm{O}\mathopen{}\mathclose{{}\left(m^{4}\ln
m}\right)$ 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^{\prime}$ under which the $2^{m}$ search points have the same
ranking as on $f$, but the maximum weight is
$\mathrm{O}\mathopen{}\mathclose{{}\left(m^{m}}\right)$ (Reichel and Skutella,
2009). Since the flex-EA is ranking based, it has the same stochastic behavior
on $f$ and $f^{\prime}$. On the process $X_{t}^{\prime}\coloneqq
f^{\prime}(x_{t})$, using the classical analysis by (Neumann and Wegener,
2007), there is a multiplicative drift with parameter
$\delta=\Omega\mathopen{}\mathclose{{}\left(q/m^{2}}\right)$, where $q$ is a
lower bound on a step flipping two bits, while steps flipping more bits do not
harm the analysis. Clearly,
$q=\Omega\mathopen{}\mathclose{{}\left(1/m}\right)$ since no more than $m$
rates can be in the archive. Hence, we obtain an expected runtime of
$\mathrm{O}\mathopen{}\mathclose{{}\left(m\cdot
m^{2}\ln(m^{m})}\right)=\mathrm{O}\mathopen{}\mathclose{{}\left(m^{4}\ln
m}\right)$ in the failure case. By the law of total probability, using the
failure probability $\mathrm{o}\mathopen{}\mathclose{{}\left(m^{-2}}\right)$,
the total expected runtime is still
$(1-\bm{\ell}_{1})^{-1}+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))(m^{2}/2)(1+\ln(r_{1}+\dots+r_{m}))$.
∎

## A Function Where the Archive Stores Several Rates Simultaneously (Section
8)

We now give the full proofs of Lemma 8.2 and Theorem 8.1 that were omitted
from the main paper.

###### Proof of Lemma 8.2.

To reach $a+d$ one-bits by flipping $d+2i$ bits, exactly $d+i$ zero-bits and
$i$ one-bits must be flipped. Hence, we assume that $d+i\leq n-a$ and $i\leq
a$. By elementary combinatorics and expanding the binomial coefficients, we
have

$\frac{p(n,a,d,i)}{p(n,a,d,0)}=\frac{\frac{\binom{n-a}{d+i}\binom{a}{i}}{\binom{n}{d+2i}}}{\frac{\binom{n-a}{d}}{\binom{n}{d}}}=\frac{(d+2i)!}{i!(d+i)!}\cdot\frac{(n-a)^{\underline{d+i}}\cdot
a^{\underline{i}}}{n^{\underline{d+2i}}}\cdot\frac{n^{\underline{d}}}{(n-a)^{\underline{d}}}=\frac{(d+2i)!}{i!(d+i)!}\cdot\frac{(n-a-d)^{\underline{i}}\cdot
a^{\underline{i}}}{(n-d)^{\underline{2i}}},$

where $b^{\underline{c}}=b(b-1)\cdot\dots\cdot(b-c+1)$ is the falling
factorial (sometimes called _Pochhammer_ symbol).

We estimate the two fractions in the last expression separately and start with
the second one. By our assumption that $d+2i\leq n^{1/3}$, we have
$(n-d)^{\underline{2i}}\geq(n-d-2i)^{2i}\geq(n-n^{1/3})^{2i}=(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{2i}$
and therefore

$\frac{(n-a-d)^{\underline{i}}\cdot
a^{\underline{i}}}{(n-d)^{\underline{2i}}}\leq\frac{(n-a)^{i}n^{i}}{(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{2i}}\leq(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\mathopen{}\mathclose{{}\left(\frac{n-a}{n}}\right)^{i}.$

For the first fraction, we have

$\frac{(d+2i)!}{i!(d+i)!}=\frac{(d+2i)^{\underline{i}}}{i!}\leq\frac{(d+2i)^{i}}{(i/\mathrm{e})^{i}}=\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(2+\frac{d}{i}}\right)\cdot\mathrm{e}}\right)^{i}\leq\mathopen{}\mathclose{{}\left(\mathrm{e}^{1+d/i}}\right)^{i}\mathrm{e}^{i}=\mathrm{e}^{d+2i},$

where the first inequality used the well-known estimate
$i!\geq(i/\mathrm{e})^{i}$ following from Stirling’s formula and the second
inequality used that $1+x\leq\mathrm{e}^{x}$ for all $x\in\mathds{R}$.

Multiplying the two estimates gives the claim of the lemma. ∎

###### Proof of Theorem 8.1.

We start with the upper bound for the flex-EA.

#### Reaching the first hurdle

If the initial search point has less than $s\coloneqq(7/8)n-\sqrt{n}$ one-
bits, then by Corollary 5.2, the level of at least $s$ one-bits is reached
within expected time $\mathrm{O}\mathopen{}\mathclose{{}\left(n\log
n/\bm{\ell}_{1}}\right)=\mathrm{O}\mathopen{}\mathclose{{}\left(n\log
n}\right)$ and rate $1$ is in the archive with probability
$1-\mathrm{O}\mathopen{}\mathclose{{}\left(1/n^{2}}\right)$ by choosing the
constant in $\bm{C}_{1}$ appropriately. Moreover, by applying Markov’s
inequality and repeating independent phases, the time to reach level at least
$s$ is bounded by $\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4}}\right)$ with
probability $1-2^{-\upomega\mathopen{}\mathclose{{}\left(n}\right)}$.

We now consider the first time where the current search point has $s$ or more
one-bits and assume pessimistically exactly $s$ one-bits. The smallest
feasible rate at this point is $g$ and the probability of a success, i. e.,
increasing the number of one-bits by $g$, at this rate is
$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-2}$ according to
(1). Using Lemma 8.2, the probability of a success at rate $g+2i$, where
$i>0$, is bounded from above by

$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-2}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(2+\frac{g}{i}}\right)\cdot\mathrm{e}\cdot\mathopen{}\mathclose{{}\left(\frac{1}{8}+\frac{1}{\sqrt{n}}}\right)}\right)^{i}\leq(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-2}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(2+\frac{g}{i}}\right)\cdot\mathrm{e}\cdot\frac{1}{7.9}}\right)^{i}$

using $a\geq s=7n/8-\sqrt{n}$ and assuming $n$ large enough. The bracket
attains its maximum at $i\approx 0.2868g$ (which can be verified by a standard
computer algebra system) and is bounded from above by $1.89^{0.2868g}\leq
2^{g/3}=n^{1/6}$ then. Altogether, the success probability for a hurdle of
size $g$ even at optimal rate is no more than
$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-11/6}$.

Therefore with probability
$1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$ by a union bound over
$G=\mathrm{O}\mathopen{}\mathclose{{}\left(n\log n/\bm{\ell}_{1}}\right)$
steps, the global counter $g$ (not to be confused with the gap size) will
reach its threshold before a hurdle is jumped over and the archive will be
reset to contain rate $1$ only. We assume all this to happen.

#### Bounding the archive size.

When the current search point has $s$ one-bits, then successes are only
possible at rates $2g$ or larger. The aim is to bound the size of the archive
while the hurdles of width $g$ and $2g$ are overcome. We first rule out that
extremely large rates yield a success and thereby enter the archive. Applying
a mutation flipping $d$ bits uniformly at random to a search point with $a\geq
s$ one-bits, the number of flipping one-bits follows a hypergeometric
distribution and the expected increase in one-bits equals $ad/n-(n-a)d/n<0$.
Applying a Chernoff bound for the hypergeometric distribution (Theorem 1.10.25
in (Doerr, 2020)), the probability of increasing the number of one-bits by any
positive amount when flipping a certain number $d\geq n^{1/3}$ of bits in one
step is bounded from above by $2^{-\Omega(n^{1/3})}$. By a union bound over
all $d\geq n^{1/3}$, the probability of increasing the number of one-bits
using any rate at least $n^{1/3}$ is still $2^{-\Omega(n^{1/3})}$. Hence, we
work under the assumption that rates larger than $n^{1/3}$ are never
successful in polynomial time; the error probability is still
$2^{-\Omega(n^{1/3})}$ by a union bound.

Clearly, the minimum successful rate is $g$ while crossing the hurdles in the
interval $[s..(7/8)n]$ of one-bits. We now estimate the success probabilities
of rates in $[g..n^{1/3}]$. By flipping $2g+i$ zero-bits and $i$ one-bits at
rate $2g+2i$, also larger rates than $2g$ can overcome hurdles of size $2g$.
Using Lemma 8.2 using $d=2g$, $i=c^{\prime}\log n$ for a sufficiently large
constant $c^{\prime}$, $a\geq s$ and our assumption of rates at most
$n^{1/3}$, we have that the probability of increasing the number of one-bits
by $d$ at rate $d+2i$ is no larger than a factor of

$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\mathrm{e}^{\log
n}\mathrm{e}^{2i}\mathopen{}\mathclose{{}\left(\frac{1}{8}+\frac{1}{\sqrt{n}}}\right)^{i}\leq(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\mathrm{e}^{\log
n}0.93^{i}$

larger than the probability of doing this at rate $d$. Hence, for a
sufficiently large constant $c^{\prime}>0$, rates larger than
$2g+2c^{\prime}\log n$ only have a success probability of
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{-5}}\right)$. By a union bound,
the size of the archive is bounded by
$\mathrm{O}\mathopen{}\mathclose{{}\left(\log n}\right)$ within a period of
$\Theta\mathopen{}\mathclose{{}\left(n^{4.5}}\right)$ steps with probability
$1-\mathrm{O}(n^{-1/2})$. We assume that the error case of a larger archive
does not happen either.

#### Crossing the hurdles and reaching the optimum.

In the following, under the above assumptions, we first show that a phase of
$c^{\prime\prime}n^{4.5}$ steps is sufficient to cross all hurdles by reaching
at least $7n/8$ one-bits with high probability. No matter whether there is a
current hurdle of width $g$ or $2g$ one-bits to the next improvement, the rate
having the highest success probability (which is at least
$(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-2}$ and
$(1-\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))n^{-4}$, respectively,
but possibly larger since it may be beneficial to flip more bits than the gap
size to overcome the gap), enters the archive after
$\mathrm{O}\mathopen{}\mathclose{{}\left(\bm{\ell}_{2g}n^{4}}\right)$ steps
since it is sufficient to select the best rate and have a success (using that
$\bm{\ell}_{g}\leq\bm{\ell}_{2g}$). By Chernoff bounds for geometrically
distributed random variables (Doerr, 2020, 1.10.32), the time is
$\mathrm{O}\mathopen{}\mathclose{{}\left(\bm{\ell}_{2g}n^{4}}\right)$ with
overwhelming probability. Once both the optimal rate for gap $g$ and for gap
$2g$ are in the archive, the probability of choosing the rate fitting the next
hurdle is $\Omega\mathopen{}\mathclose{{}\left(1/\log n}\right)$ by our
assumption on the archive size and the time for an improvement is
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4}\log n}\right)$ with
overwhelming probability and in expectation (using that gap $2g$ is the worst
case). Since at most
$\sqrt{n}/g=\mathrm{O}\mathopen{}\mathclose{{}\left(\sqrt{n}/\log n}\right)$
improvements jumping hurdles are sufficient to reach level $7n/8$ or larger
and the remaining part of the optimization is completed within expected time
$\mathrm{O}\mathopen{}\mathclose{{}\left((n\log n)/\bm{\ell}_{1}}\right)$ in
the same way as described above, the optimization time is
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4.5}}\right)$ in expectation and
also with high probability by Chernoff bounds for geometrically distributed
random variables. In the error case of a larger archive, we argue with the
maximum archive size $n$ and have a success probability of
$\Omega\mathopen{}\mathclose{{}\left(1/n^{5}}\right)$. The expected time in
the error case is therefore
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{5.5}/\log n}\right)$. Finally, the
probability of exceeding a counter is superpolynomially small since
$\bm{C}_{g}\geq\binom{n}{\log n}$; if this happens nevertheless, then we 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
$\mathrm{O}\mathopen{}\mathclose{{}\left(n^{4.5}}\right)$.

#### 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\mathopen{}\mathclose{{}\left(n}\right)}$, their
first search point, which is drawn uniformly, is before the first hurdle, i.
e., has at most $s$ one-bits. Hence, in the algorithms SD-RLS${}^{\text{r}}$
and SD-RLS${}^{\text{m}}$, the rate must increase from its initial value $1$
to at least $g$ as least once. With the standard parameter choices, this takes
$\Omega\mathopen{\big{(}}\sum_{i=1}^{g-1}\binom{n}{i}\ln
R\mathclose{\big{)}}=n^{\Omega\mathopen{}\mathclose{{}\left(\log n}\right)}$
steps.

The Fast (1+1) EA, under the assumption on the first point, must increase the
number of one-bits by a total of at least $\sqrt{n}$ to cross all hurdles. We
show that the algorithm does not cross more than $h^{*}$ hurdles at once in a
period of $\mathrm{O}\mathopen{}\mathclose{{}\left(n^{5}}\right)$ steps with
high probability, where $h^{*}$ is a sufficiently large constant. To cross
$h^{*}$ hurdles in one mutation, it is necessary that at least $cn$ zero-bits
flip at once for some constant $c>0$. By the results in (Doerr et al., 2017),
for any $k\in[n/2]$, the probability of flipping exactly $k$ bits is maximized
at mutation probability $k/n$ (recall that the Fast (1+1) EA uses standard bit
mutation). Hence, the probability of flipping $k\geq cn$ zero-bits and thereby
crossing at least $h^{*}$ hurdles at once is at most

$\binom{n-s}{k}\mathopen{}\mathclose{{}\left(\frac{k}{n}}\right)^{k}\leq\mathopen{}\mathclose{{}\left(\frac{(n-s)e}{k}}\right)^{k}\mathopen{}\mathclose{{}\left(\frac{k}{n}}\right)^{k}\leq\mathopen{}\mathclose{{}\left(\frac{1}{8}+\frac{1}{\sqrt{n}}}\right)^{k}\mathrm{e}^{k}\leq\mathopen{}\mathclose{{}\left(\frac{\mathrm{e}missing}{8}+\frac{\mathrm{e}missing}{\sqrt{n}}}\right)^{cg}=\mathrm{O}\mathopen{\big{(}}n^{-6}\mathclose{\big{)}}$

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

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

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

Inspecting the product following $p(n,s,2g,i)$, which is the ratio of success
probabilities of the Fast (1+1) EA and of the flex-EA, we have

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

where the $\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right)$ comes from the
assumption of $2g+2i\leq n^{1/3}$. Using Stirling’s formula, we have
$(2g+2i)!\geq\frac{1}{\sqrt{2\pi}}\sqrt{2g+2i}\cdot\mathrm{e}^{-2g-2i}(2g+2i)^{2g+2i}$.
Plugging this into the previous formula, the bound on the ratio of success
probabilities simplifies to

$(1+\mathrm{o}\mathopen{}\mathclose{{}\left(1}\right))\sqrt{2\pi}\frac{1}{\sqrt{2g+2i}},$

so the probability of the Fast (1+1) EA crossing a hurdle is by a factor of
$\Omega\mathopen{}\mathclose{{}\left(\sqrt{2g+2i}}\right)=\Omega\mathopen{}\mathclose{{}\left(\sqrt{\log
n}}\right)$ smaller than when the flex-EA has chosen the optimum radius.

Finally, we analyze the probability of the Fast (1+1) EA choosing a successful
rate in the heavy-tailed mutation operator. If its rate is at most
$c^{\prime}\log n$ for a constant $c^{\prime}>0$, the probability of crossing
a hurdle of width $g$ is at most

$\binom{n-s}{g}\mathopen{}\mathclose{{}\left(\frac{c\ln
n}{n}}\right)^{g}\leq\mathopen{}\mathclose{{}\left(\frac{c^{\prime}\ln n}{\ln
n}}\right)^{\ln n}=\mathrm{O}\mathopen{}\mathclose{{}\left(1/n^{5}}\right)$

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