# Run Time Bounds for Integer-Valued OneMax Functions

Jonathan Gadea Harder<EMAIL_ADDRESS>Hasso Plattner Institute
University of PotsdamPotsdamGermany ,  Timo Kötzing<EMAIL_ADDRESS>Hasso Plattner Institute
University of PotsdamPotsdamGermany ,  Xiaoyue Li<EMAIL_ADDRESS>Hasso
Plattner Institute
University of PotsdamPotsdamGermany and  Aishwarya Radhakrishnan
<EMAIL_ADDRESS>Hasso Plattner Institute
University of PotsdamPotsdamGermany

(2023)

###### Abstract.

While most theoretical run time analyses of discrete randomized search
heuristics focused on finite search spaces, we consider the search space
$\mathbb{Z}^{n}$. This is a further generalization of the search space of
multi-valued decision variables $\\{0,\ldots,r-1\\}^{n}$.

We consider as fitness functions the distance to the (unique) non-zero optimum
$a$ (based on the $L_{1}$-metric) and the (1+1) EA which mutates by applying a
step-operator on each component that is determined to be varied. For changing
by $\pm 1$, we show that the expected optimization time is
$\Theta(n\cdot(|a|_{\infty}+\log(|a|_{H})))$. In particular, the time is
linear in the maximum value of the optimum $a$. Employing a different step
operator which chooses a step size from a distribution so heavy-tailed that
the expectation is infinite, we get an optimization time of
$O(n\cdot\log^{2}(|a|_{1})\cdot\left(\log(\log(|a|_{1}))\right)^{1+\epsilon})$.

Furthermore, we show that RLS with step size adaptation achieves an
optimization time of $\Theta(n\cdot\log(|a|_{1}))$.

We conclude with an empirical analysis, comparing the above algorithms also
with a variant of CMA-ES for discrete search spaces.

Evolutionary algorithms, integer optimization, run time analysis, theory.

††journalyear: 2023††copyright: acmlicensed††conference: Genetic and
Evolutionary Computation Conference; July 15–19, 2023; Lisbon,
Portugal††booktitle: Genetic and Evolutionary Computation Conference (GECCO
’23), July 15–19, 2023, Lisbon, Portugal††price: 15.00††doi: xxx††isbn: xxx

##  1\. Introduction

Optimization problems are formalized as finding the optimal element $x$ from a
fixed search space $\mathcal{X}$ given some quality measure
$f:\mathcal{X}\rightarrow\mathbb{R}$. In the theory of evolutionary search
heuristics, the most commonly studied discrete search space is
$\mathcal{X}=\\{0,1\\}^{n}$, the set of bit strings of fixed length. Other
search spaces have been considered, such as permutations (Do et al., 2021;
Doerr et al., 2022), or multi-valued decision variables (Rudolph, 1994; Doerr
et al., 2017a) ($\mathcal{X}=\\{0,\ldots,r-1\\}^{n}$). Note that all these
search spaces are finite.

In this work we are interested in the infinite (but still discrete) search
space $\mathbb{Z}^{n}$. This models a set of $n$ decision variables with an
infinite (totally and discretely ordered) domain. While many search problems
can be usefully addressed by translating them into optimization problems using
$\mathcal{X}=\\{0,1\\}^{n}$ or another of the before-mentioned search spaces,
this is impossible in principle for an infinite search space. Furthermore,
understanding them in their more natural formulation can lead to more
efficient optimization algorithms.

In order to analyze heuristic search in this domain, we generalize fitness
functions as well as heuristic search algorithms accordingly. Note that a
generalization of the $\\{0,1\\}^{n}$ search space to $\\{0,\ldots,r-1\\}^{n}$
was done in (Doerr et al., 2017a), and we follow a similar path in the
generalization, but now with the added difficulty of an infinite search space.

As a first analysis, we consider the simple setting where, for a given
$a\in\mathbb{Z}^{n}$, we have the fitness function

$f_{a}:\mathbb{Z}^{n}\rightarrow\mathbb{Z}_{\geq
0},x\mapsto\sum_{i=1}^{n}|x_{i}-a_{i}|.$

Minimizing this function generalizes the well-known OneMax function (class),
defined on the search space $\\{0,1\\}^{n}$, to the more general space of
$\mathbb{Z}^{n}$.

As algorithms, we consider the (1+1) EA and RLS (Random Local Search), both
suitably adjusted to deal with the search space $\mathbb{Z}^{n}$ as follows
(see Section 2 for a detailed description of both algorithms). First, for
finite search spaces, it is common to start the search with a uniformly random
search point. For the infinite search space $\mathbb{Z}^{n}$ we make the
decision to start deterministically with the all-$0$ string. Since for our
fitness functions only the position-wise differences of the starting point to
the optimum matter, this choice does not restrict the meaningfulness of our
results.

Second, as a variation operator, we consider to change either exactly one
position (RLS) or each position independently with probability $1/n$ ((1+1)
EA), just as in the common definitions of these algorithms. However, while
changing a _bit_ from $\\{0,1\\}$ leaves only one possible choice for the new
value, changing a variable from $\mathbb{Z}$ leaves infinitely many choices
for the new value. We consider two possible _step operators_ , defining how to
change a value from $\mathbb{Z}$. The first step operator is the _$\pm 1$
operator_; it either increases or decreases the value by $1$, decided
uniformly at random. The second step operator is the _heavy-tailed operator_ ;
it makes a uniform decision to either increase or decrease, but instead of
deterministically changing by 1, it changes by a random number. In particular,
we consider a distribution of the numbers that is unbounded and is so heavy-
tailed that it does not have finite expectation.

Note that (Doerr et al., 2017a) considered a _Harmonic operator_ as a step
operator for variables on $\\{0,\ldots,r-1\\}$, which gives a step of size $i$
a weight proportional to $1/i$. This cannot be directly extended to an
operator on $\mathbb{Z}$, since the sequence $(1/i)_{i}$ is not summable.
Instead, we take inspiration from (Doerr et al., 2015), where very slowly
decreasing yet summable sequences were considered, to define our heavy-tailed
operator. In effect, a step size of $i$ has a probability proportional to
$1/(i\log(i)^{i+\varepsilon})$. The goal of this very heavy tail of the
distribution is to have as high as possible a chance to gain a constant
fraction of the distance to the optimum, independent of the distance to the
optimum. See Section 2 for details on the distribution.

Recently, heavy tailed distributions where used to speed up optimization in
various settings. In (Doerr et al., 2017b), the authors proposed to apply a
heavy-tailed mutation operator for the first time. In particular, the number
of variables to change was chosen from a heavy-tailed distribution (which for
us still follows the traditional binomial distribution). In contrast to our
work, the heavy-tailed distributions in (Doerr et al., 2017b) have finite
expectation. This more explorative mutation operator was then shown to
optimize so-called jump-functions faster. Since this work, further analyses
have shown the use of such heavy-tailed distributions, for example for
crossover and the $(1+(\lambda,\lambda))$-GA on OneMax (Antipov et al., 2020)
and jump-functions (Antipov and Doerr, 2020).

In our work we consider the expected time of the given algorithms to find the
optimum of a fitness function $f_{a}$. This time naturally depends on $a$ (as
well as $n$), specifically on its total weight
$|a|_{1}=\sum_{i=1}^{n}|a_{i}|$, its maximal weight
$|a|_{\infty}=\max\left\\{|a_{i}|\ \left|\ \vphantom{|a_{i}|}i\leq
n\right.\right\\}$ or its Hamming distance to the all-$0$ string
$|a|_{H}=|\left\\{i\ \left|\ \vphantom{i}a_{i}\neq 0,i\leq
n\right.\right\\}|$. Through out our analyses we consider $a$ to be non-zero.

In Section 3 we formally analyze the (1+1) EA with the $\pm 1$ operator.
Theorems 6 and 7 show that the expected optimization time is
$\Theta(n\cdot(|a|_{\infty}+\log(|a|_{H})))$ on any given fitness function
$f_{a}$. While the linear dependence on the dimension $n$ constitutes a good
performance, the linear dependence on $|a|_{\infty}$ is rather slow. For
comparison, note that there are $\Theta(|a|_{\infty}^{n})$ many target bit
strings of roughly that size. Since the (1+1) EA gains about one bit of
information with a comparison of two fitness values, a direct information
theoretic lower bound for finding the optimum is at
$\Omega(n\cdot\log(|a|_{\infty}))$.

In Section 4 we turn to the (1+1) EA with the heavy-tailed operator. In
Theorem 8 we show that the expected optimization time is
$O(n\cdot\log^{2}(|a|_{1})\cdot\left(\log(\log(|a|_{1}))\right)^{1+\epsilon})$
for a given $f_{a}$. This is already much closer to the information-theoretic
lower bound mentioned above.

Finally, we consider a version of RLS which adapts the step size during the
search. This strategy was proven to be very efficient in (Doerr et al., 2017a)
for the search space $\\{0,\ldots,r-1\\}$ and we show that also here the
algorithm achieves an expected optimization time of
$\Theta(n\cdot\log(|a|_{1}))$. Note that, for all three operators, we derive
central parts of our proofs by carefully adjusting analogous proofs from
(Doerr et al., 2017a).

With our analyses of the search space $\mathbb{Z}^{n}$, we also aim at
bridging the gap towards analyses of heuristic search on $\mathbb{R}^{n}$
(continuous optimization): if one is interested in approximating the optimum
up to a distance of $\varepsilon$, one can discretize the search space
accordingly, arriving at the search space $\mathbb{Z}^{n}$. In optimization
problems on $\mathbb{R}^{n}$, one is frequently interested only in
approximating the optimum, since finding it is typically impossible in
principle. In Corollary 9 we show a result about the (1+1) EA with heavy-
tailed operator approximating the optimum, showing that finding an
approximation ratio of $\alpha$ scales with respect to $\alpha$ as
$O(\log(1/\alpha))$.

For $\mathbb{R}^{n}$, the covariance matrix adaptation evolution strategy
(CMA-ES) is a widely used optimization algorithm (Hansen et al., 2003). To
extend the use of CMA-ES to address also discrete variables, authors in
(Hamano et al., 2022) propose a variant of CMA-ES (called CMA-ES with margin,
CMA-ESwM). We are interested in the performance of this algorithm in
optimizing an integer-valued problem in comparison to other discrete
optimization algorithms. In Section 6 we experimentally compare our algorithms
with CMA-ESwM, finding that the CMA-ESwM fails to optimize with certain
probability even with a large time budget, while the (1+1) EA with the heavy-
tailed operator and RLS with the self-adjusting operator can handle the
instances efficiently.

The remainder of this paper is structured as follows. In Section 2 we
introduce algorithms and notation. In Sections 3 and 4 we give our theoretical
analyses of the (1+1) EA. Section 5 addresses the self-adjusting RLS. In
Section 6 we present our experiments.

##  2\. Preliminaries

In this section we define the (1+1) EA and random local search algorithms,
along with the different step operators. At the end of this section we also
state different drift theorems we use for our analysis.

For any $a\in\mathbb{Z}^{n}$, we let

$\displaystyle|a|_{1}$ $\displaystyle=\sum_{i=1}^{n}|a_{i}|;$
$\displaystyle|a|_{\infty}$ $\displaystyle=\max\left\\{|a_{i}|\ \left|\
\vphantom{|a_{i}|}i\leq n\right.\right\\};$ $\displaystyle|a|_{H}$
$\displaystyle=|\left\\{i\ \left|\ \vphantom{i}a_{i}\neq 0,i\leq
n\right.\right\\}|.$

Also for $a\in\mathbb{Z}^{n}\setminus\\{0^{n}\\}$, we define

$f_{a}:\mathbb{Z}^{n}\rightarrow\mathbb{R},x\mapsto|a-x|_{1}.$

Our class of target fitness functions is $\mathscr{F}=\\{f_{a}\mid
a\in\mathbb{Z}^{n}\setminus\\{0^{n}\\}\\}$ to be minimized by evaluating the
fitness function at any point as chosen by the algorithm.

We consider different _step operators_
$\mathrm{step}:\mathbb{Z}\mapsto\mathbb{Z}$. These step operators decide on
the update of a mutation in a given component. We consider the following step
operators.

###### Definition 1.

[$\pm 1$-operator] The _$\pm 1$ -operator_ takes an integer $x$ as input and
makes the following changes: With probability $1/2$ return $x+1$ and otherwise
return $x-1$.

For the next operator we need a definition. Given $\epsilon>0$, let
$c_{\epsilon}=\sum_{i=2}^{\infty}\frac{1}{i\cdot(\log i)^{1+\epsilon}}$ (note
that this sum is finite (Doerr et al., 2015)).

###### Definition 2.

[Heavy-tailed-operator] For a given $\varepsilon>0$, the _heavy-tailed
operator_ takes an integer $x$ as input and makes the following changes: First
sample a step size of $2^{I-2}$ using a random variable $I$ which can take a
value of any natural number $i\geq 2$ with $P(I=i)=\frac{1}{c_{\epsilon}\cdot
i\cdot(\log i)^{1+\epsilon}}$. With probability $\frac{1}{2}$ then return
$x+2^{I-2}$, otherwise return $x-2^{I-2}$.

We consider the algorithms RLS and the (1+1) EA as given by Algorithm 1 and
Algorithm 2. Both start from the initial search point being the all-$0$
string. They then proceed in rounds, each of which consists of a _mutation_
and a _selection_ step. Throughout the whole optimization process, the
algorithms maintain a single individual, which is always the most recently
sampled best-so-far solution. The two algorithms differ only in the _mutation
operator_. While $RLS$ makes a step in exactly one position (chosen uniformly
at random), the (1+1) EA makes, in each position, a step with probability
$1/n$. We specify the termination criterion as the point in time when the
search point has a fitness of $0$.

1Initialization: $x\leftarrow 0^{n}$;

2 Optimization: while  _$f(x)\neq 0$_ do

3 for  _i from 1 to n_ do

4 With probability $\frac{1}{n}$ set $y_{i}=\text{step}(x_{i})$ and set

5 $y_{i}=x_{i}$ otherwise;

6 if  _$f(y)\leq f(x)$_ then

7 $x\leftarrow y$;

8

Algorithm 1 The (1+1) EA minimizing a function
$f:\mathbb{Z}^{n}\mapsto\mathbb{R}$ with a given step operator
$\mathrm{step}:\mathbb{Z}\rightarrow\mathbb{Z}$

$RLS_{\alpha,\beta}$ maintains a search point $x\in\mathbb{Z}^{n}$ as well as
a real-valued _velocity vector_ $v\in[1,\infty]^{n}$; we use real values for
the velocity to circumvent rounding problems. The initial search point is the
all-$0$s string and the initial velocity is the all-$1$s string. In one
iteration of the algorithm a position $i\in[n]$ is chosen uniformly at random.
The entry $x_{i}$ is replaced by $x_{i}-\left\lfloor v_{i}\right\rfloor$ with
probability $1/2$ and by $x_{i}+\left\lfloor v_{i}\right\rfloor$ otherwise.
The entries in positions $j\neq i$ are not subject to mutation. The resulting
string $y$ replaces $x$ if its fitness is at least as good as the one of $x$,
i.e. if $f(y)\leq f(x)$ holds. If the offspring $y$ is strictly better than
its parent $x$, i.e. if $f(y)<f(x)$, we increase the velocity $v_{i}$ in the
$i$-th component by multiplying it with the constant $\alpha$; we decrease
$v_{i}$ to $\beta v_{i}$ otherwise. The algorithm proceeds this way until we
decide to stop it. To further lighten the notation, we say that the algorithm
“ _moves in the right direction_ ” or “ _towards the target value_ ” if the
distance to the target is actually decreased by $\left\lfloor
v_{i}\right\rfloor$. Analogously, we speak otherwise of a step “ _away from
the target_ ” or “ _in the wrong direction_ ”.

1Initialization: $x\leftarrow 0^{n}$, $v\leftarrow 1^{n}$;

2 Optimization: while  _$f(x)\neq 0$_ do

3 for  _i from 1 to n_ do

4 $y\leftarrow x$;

5 Choose $i\in[n]$ uniformly at random;

6 With probability $\frac{1}{2}$ set $y_{i}=x_{i}-\left\lfloor
v_{i}\right\rfloor$ and set $y_{i}=x_{i}+\left\lfloor v_{i}\right\rfloor$
otherwise;

7 if  _$f(y) <f(x)$_ then

8 $v_{i}\leftarrow\alpha v_{i}$;

9 else

10 $v_{i}\leftarrow\max\\{1,\beta v_{i}\\}$;

11 if  _$f(y)\leq f(x)$_ then

12 $x\leftarrow y$;

13

Algorithm 2 $RLS_{\alpha,\beta}$ with self-adjusting step sizes minimizing a
function $f:\mathbb{Z}^{n}\mapsto\mathbb{R}$

A central tool in many of our proofs is drift analysis, which comprises a
number of tools to derive bounds on hitting times from bounds on the expected
progress a process makes towards the target. Drift analysis is currently the
most powerful tool in run time analysis for evolutionary computation. We
briefly collect here the tools we use.

_Additive drift_ is the situation that the progress is bounded by any
(constant) value. This quite common situation in run time analysis was the
first framed into a drift theorem, namely the following one, in (He and Yao,
2004).

###### Theorem 3 (Additive Drift Theorem (He and Yao, 2004)).

Let $S\subseteq\mathbb{R}$ be a finite set of positive numbers and let
$({X^{t}})_{t\in\mathbb{N}}$ be a sequence of random variables over
$S\cup\\{0\\}$. Let $T$ be the random variable that denotes the first point in
time $t\in\mathbb{N}$ for which $X^{t}\leq 0$. Suppose that there exists a
constant $\delta_{1}>0$ such that

$E[X^{t}-X^{t+1}\mid T>t]\geq\delta_{1}$

holds. Then

$E[T\mid X^{0}]\leq\frac{X^{0}}{\delta_{1}}.$

If there exists a constant $\delta_{2}>0$ such that

$E[X^{t}-X^{t+1}\mid T>t]\leq\delta_{2}$

holds. Then

$E[T\mid X^{0}]\geq\frac{X^{0}}{\delta_{2}}.$

_Multiplicative drift_ (first) addresses the situation where progress is
proportional to the distance from the target. For this situation quite common
in run time analysis we can use the following drift theorem (Doerr et al.,
2012).

###### Theorem 4 (Multiplicative Drift Theorem (Kötzing and Krejca, 2019)).

Let $(X_{t})_{t\in\mathbb{N}}$ be random variables over $\mathbb{R}$,
$x_{\min}>0$, and let $T=\min\\{t\mid X_{t}<x_{\min}\\}$. Furthermore, suppose
that

(a) $X_{0}\geq x_{\min}$ and, for all $t\leq T$, it holds that $X_{t}\geq 0$,
and that

(b) there is some value $\delta>0$ such that, for all $t<T$, it holds that
$X_{t}-E[X_{t+1}\mid X_{0},\ldots,X_{t}]\geq\delta X_{t}$.

Then

$E[T\mid X_{0}]\leq\frac{1+\ln\left(\frac{X_{0}}{x_{\min}}\right)}{\delta}.$

##  3\. Unit Mutation Strength

In this section, we regard the mutation operator that applies only $\pm 1$
changes to each component. We give a tight bound on the expected run time of
the (1+1) EA with the $\pm$ operator. We start by stating the following lemma
which bounds the expected cost of a given random variable over $[n]$ for
$n\in\mathbb{N}$, which we later use in our analysis.

###### Lemma 5.

(Doerr et al., 2017a, Lemma 13) Let $n\in\mathbb{N}$ be fixed, let $q$ be a
cost function on elements of $[n]$ and let $c$ be a cost function on subsets
of $[n]$. Furthermore, let a random variable $S$ ranging over subsets of $[n]$
be given. Then we have

(1) $\displaystyle\forall T\subseteq[n]:c(T)\leq\sum_{i\in T}q(i)\implies
E[c(S)]\leq\sum_{i=1}^{n}q(i)P(i\in S)$

and

(2) $\displaystyle\forall T\subseteq[n]:c(T)\geq\sum_{i\in T}q(i)\implies
E[c(S)]\geq\sum_{i=1}^{n}q(i)P(i\in S)$

The following theorem gives an upper bound on the expected optimization time
of the $(1+1)EA$ optimizing any $f_{a}\in\mathscr{F}$ with the $\pm 1$
operator.

###### Theorem 6.

Let $f_{a}\in\mathscr{F}$. Then the expected optimization time of the (1+1) EA
with $\pm 1$ operator starting with all $0$ integer string on $f_{a}$ is
$O(n\cdot(|a|_{\infty}+\log(|a|_{H})))$.

###### Proof.

Our proof idea is similar to the proof idea in (Doerr et al., 2017a, Theorem
12). We will use the multiplicative drift analysis (see 4) to prove this
theorem. For our analysis, we make use of two edge cases that both have a
fitness of $n$; which would be only one entry being incorrect but $n$ away
from its target and the case that every entry in the target is $1$. The former
is hard to optimize since it takes long for the algorithm to successively
change the incorrect position, while the latter can be solved very fast since
there are multiple ways of progressing in each step. We exploit this by giving
each position a weight exponential in the amount that is incorrect, and then
sum over those weights. With any search point $x\in\Omega$ we associate a
vector $d\in\mathrm{R}^{n}$ such that, for all $i\leq n,d_{i}=|a_{i}-x_{i}|$.
Given some $\omega>1$ we consider the potential

(3) $\displaystyle g(x)\coloneqq\sum_{i=1}^{n}(\omega^{d_{i}}-1)$

Let $x_{t}$ be the integer string at iteration $t$ when the (1+1) EA with $\pm
1$ operator is optimizing $f_{a}$. Let $X_{t}=g(x_{t})$ and let
$T=\min\\{t\geq 0\mid X_{t}=0\\}$. Further let $E_{1}$ be the event that
$X_{t+1}$ is obtained by mutating exactly one position and let $E_{2}$ be the
event that $X_{t+1}$ is obtained by mutating at least two positions. Then
$X_{0}\leq|a|_{H}\cdot\omega^{|a|_{\infty}}$, since we start with all $0$
integer string. We denote $O$ as the set of already optimized positions and
$A(S)$ as the set of accepted offspring by only manipulating $S\subseteq[n]$
positions. Now we bound the expected drift. Since $t<T$, at least one of the
position is at least $1$ distant far from the optimum and the probability to
mutate this position in the right direction is $\frac{1}{2n}$ and the
probability to not mutate any other positions is
$\left(1-\frac{1}{n}\right)^{n-1}$. Therefore,

$\displaystyle E[X_{t}-X_{t+1}$ $\displaystyle\mid t<T,E_{1}]\cdot P(E_{1})$
$\displaystyle\geq\sum_{i\in[n]\setminus
O}\frac{1}{2n}\left(1-\frac{1}{n}\right)^{n-1}(\omega^{d_{i}}-1)-(\omega^{d_{i}-1}-1)$
$\displaystyle\geq\frac{1}{2ne}\sum_{i\in[n]\setminus
O}(\omega^{d_{i}}-1)-(\omega^{d_{i}-1}-1)$
$\displaystyle=\frac{1}{2ne}\sum_{i\in[n]\setminus
O}^{n}\left(1-\frac{1}{\omega}\right)\cdot\omega^{d_{i}}$
$\displaystyle\geq\frac{1}{2ne}\sum_{i=1}^{n}\left(1-\frac{1}{\omega}\right)\cdot\left(\omega^{d_{i}}-1\right)$
$\displaystyle=\frac{\omega-1}{2\omega ne}\sum_{i=1}^{n}(\omega^{d_{i}}-1)$

Let $U$ be the set of all tuples $(y,i),y\in A(S)$ where the $i$-th positions
worsens. As we only consider accepted mutations, we have that, for all $y\in
A(S),\sum_{i\in S}d(y_{i},z_{i})-d_{i}\leq 0$.This implies that there are at
least as many improving-pairs as there are worsening-pairs in
$A(S)\crossproduct S$. For every $(y,i)$ with $d_{i}=0$ where bit position $i$
changes in the wrong direction, there is a $(y^{\prime},i)\in U$ with bit
position $i$ changing in the right direction and the remaining positions
behaving the same. The change in potential for both pairs added is

$\omega^{d_{i}+1}-\omega^{d_{i}}+\omega^{d_{i}-1}-\omega^{d_{i}}=\omega^{d_{i}}\frac{(\omega-1)^{2}}{\omega}$

Since there are in total at least as many improving-pairs as worsening-pairs,
we can further map injectively each $y\in A(S)$ with a correct position
($d_{i}=0$) that changes in the wrong direction to another $y^{\prime}\in
A(S)$ with some improving position. The change in potential for both positions
added is

$\omega-1+\omega^{d_{i^{\prime}}-1}-\omega^{d_{i^{\prime}}}=(1-\omega^{d_{i}^{\prime}-1})\cdot(\omega-1)<\omega^{d_{i}}\frac{(\omega-1)^{2}}{\omega}$

Let $Y$ be the random variable describing the search point after one cycle of
mutation and selection. The random variable Y is completely determined by
choosing a set $S\subseteq[n]$ of bit positions to change in $x$ and then, for
each such position $i\in S$, choosing whether to change towards or away from
the target. For each possible $S\subseteq[n]$, let $Y(S)$ be the random
variable $Y$ conditional on making changes exactly at the bit positions of S.
Note that since we increase/decrease each index by $1$ with the same
probability, $Y(S)$ is the uniform distribution on $A(S)$. Further let

$\displaystyle c(S)$ $\displaystyle\coloneq E[g(Y(S))-g(x)]$
$\displaystyle=\frac{1}{|A(S)|}\sum_{y\in A(S)}g(y)-g(x)$
$\displaystyle=\frac{1}{|A(S)|}\sum_{y\in
A(S)}\sum_{i=1}^{n}\left(\omega^{|y_{i}-a_{i}|}-\omega^{d_{i}}\right)$
$\displaystyle=\frac{1}{|A(S)|}\sum_{(y,i)\in
U}\left(\omega^{|y_{i}-a_{i}|}-\omega^{d_{i}}+\omega^{|y_{i^{\prime}}-a_{i^{\prime}}|}-\omega^{d_{i^{\prime}}}\right)$
$\displaystyle\leq\frac{1}{2}\sum_{i\in
S}\omega^{d_{i}}\frac{(\omega-1)^{2}}{\omega}.$

Using Lemma 5, we get that

$E[g(Y)-g(x)|E_{2}]\leq\sum_{i=1}^{n}\frac{1}{n}\omega^{d_{i}}\frac{(\omega-1)^{2}}{2\omega}=\frac{(\omega-1)^{2}}{2\omega
n}\sum_{i=1}^{n}\omega^{d_{i}}$

We can use any $\omega>1$ such that $\omega-1-e(\omega-1)^{2}>0$ and set
$c=(\omega-1-e(\omega-1)^{2})/e$. One can verify that for $\omega=1.2$ we
obtain $0.0912687>0$, so such $\omega$ exist. In total we get

$\displaystyle E[g(x)-g(Y)]\geq\frac{\omega-1}{2\omega
ne}\sum_{i=1}^{n}\omega^{d_{i}}-\frac{(\omega-1)^{2}}{2\omega
n}\sum_{i=1}^{n}\omega^{d_{i}}$
$\displaystyle=\frac{\omega-1-e(\omega-1)^{2}}{2\omega
ne}\sum_{i=1}^{n}\omega^{d_{i}}=\frac{c}{2\omega
n}\sum_{i=1}^{n}\omega^{d_{i}}\geq\frac{c}{2\omega n}g(x).$

Therefore by the multiplicative drift theorem (4), we have

$E[T]=O((|a|_{\infty}+\log(|a|_{H}))\cdot n)=O(|a|_{\infty}\cdot
n+n\cdot\log(|a|_{H})).$

∎

We show in the following theorem that this upper bound on the (1+1) EA is
sharp by proving the same asymptotic lower bound.

###### Theorem 7.

Let $f_{a}\in\mathscr{F}$. Then the expected optimization time of the (1+1) EA
with $\pm 1$ operator starting with all $0$ integer string on $f_{a}$ is
$\Omega(|a|_{\infty}\cdot n+n\cdot\log(|a|_{H}))$.

###### Proof.

The lower bound $|a|_{\infty}\cdot n$ follows from looking at the position
with a distance of $|a|_{\infty}$ to the target. The drift in the right
direction is at most $\frac{1}{n}$, which is the probability of mutating the
position. Therefore by the additive drift theorem (3), we have a run time of
$\Omega(n\cdot|a|_{\infty})$. For the second part we prove that
$P(T\geq(n-1)\log(|a|_{H}))$ is at least $\frac{1}{2}$. The probability that a
particular index does not get modified in any of the $t$ iterations is
$\left(1-\frac{1}{n}\right)^{t}$. The previous statement implies that the
probability that it does get modified at least once is
$1-\left(1-\frac{1}{n}\right)^{t}$. Therefore the probability that $|a|_{H}$
indices gets modified at least once in $t$ iterations is
$\left(1-\left(1-\frac{1}{n}\right)^{t}\right)^{|a|_{H}}$. This in turn
implies that the probability that at least one of the $|a|_{H}$ indices does
not get modified in $t$ iterations is
$1-\left(1-\left(1-\frac{1}{n}\right)^{t}\right)^{|a|_{H}}$. If
$t=(n-1)\ln(|a|_{H})$, then

$\displaystyle 1-\left(1-\left(1-\frac{1}{n}\right)^{t}\right)^{|a|_{H}}$
$\displaystyle=1-\left(1-\left(1-\frac{1}{n}\right)^{(n-1)\ln|a|_{H}}\right)^{|a|_{H}}$
$\displaystyle\geq
1-\left(1-\left(\frac{1}{e}\right)^{\ln|a|_{H}}\right)^{|a|_{H}}$
$\displaystyle=1-\left(1-\frac{1}{|a|_{H}}\right)^{|a|_{H}}\geq
1-e^{-1}\geq\frac{1}{2}.\ $

Now we have expected time

$\displaystyle E[T]$ $\displaystyle=\sum_{t=1}^{\infty}t\cdot P(T=t)$
$\displaystyle=\sum_{t=1}^{\infty}P(T\geq t)$
$\displaystyle\geq(n-1)\ln|a|_{H}\cdot P(T\geq(n-1)\ln|a|_{H})$
$\displaystyle\geq(n-1)\ln|a|_{H}\cdot\frac{1}{2}=\Omega(n\ln|a|_{H}).$

∎

##  4\. Heavy-Tailed Mutation Strength

In this section we discuss the behavior of the (1+1) EA with the heavy-tailed
mutation operator on optimizing any $f_{a}\in\mathscr{F}$. First, in the
following theorem, we give an _upper_ bound on the expected optimization time.

###### Theorem 8.

Let $f_{a}\in\mathscr{F}$. Then the expected optimization time of the (1+1)
EA, starting with the all-$0$s integer string, with the _heavy-tailed
operator_ (see Definition 2) with parameter $\epsilon>0$ on $f_{a}$ is
$O(n\cdot\log^{2}|a|_{1}\cdot\left(\log(\log|a|_{1})\right)^{1+\epsilon})$.

###### Proof.

Our proof idea is similar to the proof idea in (Doerr et al., 2017a, Theorem
15). We use multiplicative drift analysis in this proof.

Let $x$ and $x^{\prime}$ be the integer string at iteration $t$ and $t+1$ when
the (1+1) EA with heavy-tailed operator is optimizing $f_{a}$. Let the
potential value $X$ at time $t$ be $f_{a}(x)$. Then the initial potential
value is $|a|_{1}$, since we start with all $0$ integer string. Let
$T=\min\\{t\geq 0\mid X=0\\}$. For any $t\geq 0$ and $i\in\\{1,\cdots,n\\}$,
let $d_{i}=|a_{i}-x_{i}|$.

For any $i\in\\{1,\cdots,n\\}$ and $j\in\\{0,1,\cdots,\left\lfloor\log
d_{i}\right\rfloor\\}$, let $A_{i,j}$ be the event that the mutation operator
only modifies the index $i$ such that
$|a_{i}-x_{i}|-|a_{i}-x_{i}^{\prime}|=2^{j}$ and do not make any other
changes. If $j^{*}=j+2$, then
$P(A_{i,j})\geq\frac{1}{2ec_{\epsilon}nj^{*}(\log j^{*}))^{1+\epsilon}}$. We
get the previous bound on the probability because the probability to make
$2^{j}$ changes to a particular index in the right direction is
$\frac{1}{2c_{\epsilon}nj^{*}(\log j^{*}))^{1+\epsilon}}$ and the probability
to make exactly this change and no other changes to any other indices is at
least $1/e$. Also note that while calculating the probability $P(A_{i,j})$, we
did not consider the case that the mutation operator can overshoot, since this
will only increase the probability.

$\displaystyle E[X-X^{\prime}$ $\displaystyle\mid
X]\geq\sum_{i=1}^{n}\sum_{j=0}^{\left\lfloor\log
d_{i}\right\rfloor}E[X-X^{\prime}\mid A_{i,j},X]\cdot P(A_{i,j})$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=0}^{\left\lfloor\log
d_{i}\right\rfloor}2^{j}\cdot P(A_{i,j})$
$\displaystyle\geq\sum_{i=1}^{n}\sum_{j=0}^{\left\lfloor\log
d_{i}\right\rfloor}\frac{2^{j}}{2ec_{\epsilon}nj^{*}(\log
j^{*}))^{1+\epsilon}}$
$\displaystyle\geq\frac{1}{2ec_{\epsilon}n}\sum_{i=1}^{n}\frac{d_{i}}{(\left\lfloor\log
d_{i}\right\rfloor+2)\left(\log(\left\lfloor\log
d_{i}\right\rfloor+2)\right)^{1+\epsilon}}$
$\displaystyle\geq\frac{\sum_{i=1}^{n}d_{i}}{2ec_{\epsilon}n\cdot(\log|a|_{1}+2)\cdot\left(\log(\log|a|_{1}+2)\right)^{1+\epsilon}}$
$\displaystyle=\frac{X}{2ec_{\epsilon}n\cdot(\log|a|_{1}+2)\cdot\left(\log(\log|a|_{1}+2)\right)^{1+\epsilon}}.$

Since we have an initial potential value $|a|_{1}$ and a multiplicative drift
value of
$\frac{1}{2ec_{\epsilon}n\cdot(\log|a|_{1}+2)\cdot\left(\log(\log|a|_{1}+2)\right)^{1+\epsilon}}$,
by multiplicative drift theorem (4),

$\displaystyle E[T]$ $\displaystyle\leq
2ec_{\epsilon}n\cdot(\log|a|_{1}+2)\cdot\left(\log(\log|a|_{1}+2)\right)^{1+\epsilon}\cdot(1+\log|a|_{1})$
$\displaystyle=O(n\cdot\log^{2}|a|_{1}\cdot\left(\log(\log|a|_{1})\right)^{1+\epsilon}).$

Thus we get the upper bound as claimed. ∎

As a corollary to the proof, we give an upper bound on the expected time taken
by the (1+1) EA with the heavy-tailed mutation operator to find an integer
string which is at a distance at most $|a|_{1}\cdot\alpha$ from the optimum.
Thus, we can inform about the time it takes to approximate the optimum.

###### Corollary 9.

Let $f_{a}\in\mathscr{F}$ and $\alpha\in(0,1)$. Then the expected optimization
time of the (1+1) EA, starting with all $0$ integer string, with _heavy-tailed
operator_ with parameter $\epsilon>0$ on $f_{a}$, to find an integer string
with weight $|a|_{1}\cdot\alpha$ is
$O(n\cdot\log|a|_{1}\cdot\log\left(\frac{1}{\alpha}\right)\cdot\left(\log(\log|a|_{1})\right)^{1+\epsilon})$.

###### Proof.

The proof is similar to the proof of the Theorem 8. If we consider the same
potential as in Theorem 8, $X=f_{a}(x)$, then we have the same value
$\frac{1}{2ec_{\epsilon}n\cdot(\log|a|_{1}+2)\cdot\left(\log(\log|a|_{1}+2)\right)^{1+\epsilon}}$
as the multiplicative drift. Let $T=\\{t\geq 0\mid
X_{t}\leq|a|_{1}\cdot\alpha\\}$. The initial potential value is at most
$|a|_{1}$ and the minimum value the potential can take is
$|a|_{1}\cdot\alpha$.

Therefore, by multiplicative drift theorem (4),

$\displaystyle E[T]$ $\displaystyle\leq
4ec_{\epsilon}n\cdot(\log|a|_{1})\cdot\left(\log(\log|a|_{1})\right)^{1+\epsilon}\cdot\left(1+\log\left(\frac{|a|_{1}}{|a|_{1}\cdot\alpha}\right)\right)$
$\displaystyle=O(n\cdot\log|a|_{1}\cdot\log\left(\frac{1}{\alpha}\right)\cdot\left(\log(\log|a|_{1})\right)^{1+\epsilon}).$

∎

##  5\. Self-Adjusting Mutation Rates

In this section, we analyze self-adjusting mutation rates for the $RLS$
algorithm and show how these can outperform the (1+1) EA with the static
operators analyzed in the previous sections. The mutation strength for
$RLS_{\alpha,\beta}$ is adjusted using the constants $1<\alpha\leq 2$ and
$1/2<\beta<1$ (see Algorithm 2 for further details on the algorithm). In
Theorem 12, we give a tight bound on the expected run time of
$RLS_{\alpha,\beta}$ for suitable $\alpha$ and $\beta$. We start by giving a
lower bound on the expected run time in Lemma 10.

###### Lemma 10 (RLS lower bound).

Let $f_{a}\in\mathscr{F}$. For constants $\alpha,\beta$ the expected
optimization time of $RLS_{\alpha,\beta}$ starting with all $0$ integer string
on $f_{a}$ is $\Theta(n\cdot\log(|a|_{1}))$.

###### Proof.

A bound of $\Omega(n\log|a|_{H})$ easily follows from a coupon collector
argument: Since we need to change $|a|_{H}$ many entries and each one has a
probability of $\frac{1}{n}$ of being changed in each iteration.

A bound of $\Omega(n\log|a|_{\infty})$ follows from analyzing the entry $j$
with the highest distance to the target. First observe that since the velocity
doubles at most each time that an entry is selected and we start at $0$, we
need at least $\log(a_{\infty})-1$ changes for this entry. Let $X_{t}$ be the
random variable counting the number of changes on $j$. Let $Y_{t}$ be another
random variable with $Y_{t}\coloneqq\log(a_{\infty})-1-X_{t}$. Since
$Y_{0}=\log(|a|_{\infty})-1$ and we have an additive drift of at most
$\frac{1}{n}$, the expected run time is of order
$\Omega(n\cdot\log(|a|_{\infty}))$. We obtain this drift because the
probability of changing the entry $j$ is $\frac{1}{n}$ and we can only change
it or not change it.

The lower bound of $\Omega(n\log|a|_{1})$ is obtained by adding both run times
(this is asymptotically the same as taking the max) to get

$n\log|a|_{\infty}+n\log|a|_{H}=n\log(|a|_{\infty}|a|_{H})\geq
n\log(|a|_{1}).$

∎

The proof of the upper bound in the following lemma is essentially the same as
in (Doerr et al., 2017a, Theorem 17), only omitting parts that are not
necessary for our setting. For the sake of self-containment, we present the
modified proof here.

###### Lemma 11 (RLS upper bound).

Let $f_{a}\in\mathscr{F}$. For constants $\alpha,\beta$ satisfying
$1<\alpha\leq 2,1/2<\beta\leq 0.9,2\alpha\beta-\beta-\alpha>0,\alpha+\beta>2$
and $\alpha^{2}\beta>1$ the expected optimization time of $RLS_{\alpha,\beta}$
starting with all $0$ integer string on $f_{a}$ is $O(n\cdot\log(|a|_{1}))$.

###### Proof.

To simplify the notation for a given search point $x$ and the target integer
string $z$ and the chosen metric $d$, we let $d_{i}=d(x_{i},z_{i})$ for all
$(i\leq n)$ be the distance vector of $x$ to $z$. Thus, the goal is to reach a
state in which the distance vector is $(0,...,0)$. We now want to define a
potential function in dependence on $(d,v)$ (where of course $d$ is dependent
on $x$) such that it is $0$ when $d$ is $(0,...,0)$ and strictly positive for
any $x\neq(0,...,0)$.

We use as potential function the following map
$g:\mathbb{Z}^{n}\mapsto\mathbb{R},(x,v)\mapsto\sum_{i=1}^{n}g_{i}(d_{i},v_{i})$
where $g_{i}(d_{i},v_{i})\coloneqq 0$ for $d_{i}=0$ and for $d_{i}\geq 1$

$\displaystyle g_{i}(d_{i},v_{i})\coloneqq
d_{i}+\begin{cases}cd_{i}\max\\{2v_{i}/d_{i},d_{i}/(2v_{i})\\},&\text{ if
$v_{i}\leq 2\beta d_{i}$};\\\
cd_{i}\max\\{2v_{i}/d_{i},d_{i}/(2v_{i})\\}+pd_{i},&\text{otherwise.}\end{cases}$

and $c,p$ are (small) constants specified below. For further motivation on the
potential see (Doerr et al., 2017a, Theorem 17).

Summarizing all the conditions needed below, we require that the constants
$\alpha,\beta,c,p$ satisfy $1<\alpha\leq 2,1/2<\beta\leq
0.9,2\alpha\beta-\beta-\alpha>0,\alpha+\beta>2,\alpha^{2}\beta>1,8\alpha\beta
c+2p+4c/\beta\leq 1/16,p>8c\left(\frac{\alpha+\beta}{2}-1\right),$ and
$p>4(\alpha-1)c>0$.

We can thus choose, for example, $\alpha=1.7,\beta=0.9,p=0.01,$ and $c=0.001$.

Let $d\neq(0,...,0)$ and $v\in\mathbb{N}^{n}$. Let $(d^{\prime},v^{\prime})$
be the state of Algorithm 2 started in $(d,v)$ after one iteration (i.e.,
after a possible update of $x$ and $v$). First we show that the expected
difference in potential satisfies

$\displaystyle
E[g(d,v)-g(d^{\prime},v^{\prime})|d,v]\geq\frac{\delta}{n}g(d,v)$

for some positive constant $\delta$. Any fixed index $i$ is chosen by
Algorithm 2 for mutation with probability $1/n;$ for all $i$, let $A_{i}$ be
the event that index $i$ was chosen. We show that there is a constant $\delta$
such that, for all indices $i$ with $d_{i}\neq 0$

$\displaystyle E[g(d_{i},v_{i})-g(d_{i}^{\prime},v_{i}^{\prime})\mid
d,v]\geq\delta g_{i}(d_{i},v_{i})$

thus proving the claim using $P(A_{i})=1/n$.

We regard several cases, depending on how $d_{i}$ and $v_{i}$ relate.

Case $1$: $v_{i}\leq d_{i}/8$.
First we observe that $\max\\{2v_{i}/d_{i},d_{i}/(2v_{i})\\}=d_{i}/(2v_{i})$.
The contribution of the $i$-th position to the current potential is thus

$\displaystyle g_{i}(d_{i},v_{i})=d_{i}+cd_{i}^{2}/(2v_{i}).$

With probability $1/2$ the algorithm decides to move in the right direction.
In this case we make progress with respect to the fitness function and the
velocity. That is, after the iteration we have
$d_{i}^{\prime}=d_{i}-\left\lfloor v_{i}\right\rfloor<d_{i}$ and
$v_{i}^{\prime}=\alpha v_{i}>v_{i}$.

To bound the progress in the second component of $g_{i},$ we observe that

$\displaystyle cd_{i}^{\prime}\max\\{2\alpha
v_{i}/d_{i}^{\prime},d_{i}^{\prime}/(2\alpha v_{i})\\}$
$\displaystyle=\max\\{2c\alpha v_{i},cd_{i}^{\prime 2}/(2\alpha v_{i})\\}$
$\displaystyle=cd_{i}^{\prime 2}/(2\alpha v_{i}),$

where the second equality follows from $2\alpha v_{i}\leq
d_{i}/2<d_{i}^{\prime}$. We thus obtain that for this case the difference in
potential is at least

(4) $\displaystyle g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})$
$\displaystyle=d_{i}+cd_{i}^{2}/(2vi)-d_{i}^{\prime}-cd_{i}^{\prime
2}/(2\alpha v_{i})$ (5)
$\displaystyle\geq\frac{cd_{i}^{2}}{2v_{i}}-\frac{cd_{i}^{2}}{2\alpha v_{i}}.$

With probability $1/2$ the algorithm decides to go in the wrong direction,
then $d_{i}^{\prime}>d_{i}$ holds and the new individual is discarded while
the velocity $v_{i}$ at position $i$ is further decreased to $\max\\{\beta
v_{i},1\\}\geq\beta v_{i}$. Hence the difference in potential for this case is
at least

(6) $\displaystyle g_{i}(d_{i},v_{i})-g_{i}(d_{i},\beta
v_{i})=\frac{cd_{i}^{2}}{2v_{i}}-\frac{cd_{i}^{2}}{2\beta v_{i}}.$

Combining (4) and (6), we thus obtain that the expected difference in
potential is at least

$\displaystyle\frac{1}{2}\left(\frac{cd_{i}^{2}}{2v_{i}}-\frac{cd_{i}^{2}}{2\alpha
v_{i}}+\frac{cd_{i}^{2}}{2v_{i}}-\frac{cd_{i}^{2}}{2\beta
v_{i}}\right)=\frac{cd_{i}^{2}}{2v_{i}}\left(\frac{2\alpha\beta-\beta-\alpha}{2\alpha\beta}\right)$
$\displaystyle=\left(\frac{2\alpha\beta-\beta-\alpha}{4\alpha\beta}\right)\left(\frac{cd_{i}^{2}}{2v_{i}}+\frac{cd_{i}^{2}}{2v_{i}}\right)\geq\left(\frac{2\alpha\beta-\beta-\alpha}{4\alpha\beta}\right)\left(4cd_{i}+\frac{cd_{i}^{2}}{2v_{i}}\right)$
$\displaystyle\geq\left(\frac{2\alpha\beta-\beta-\alpha}{4\alpha\beta}\right)\min\\{4c,1\\}\left(d_{i}+\frac{cd_{i}^{2}}{2v_{i}}\right)$
$\displaystyle=\left(\frac{2\alpha\beta-\beta-\alpha}{4\alpha\beta}\right)\min\\{4c,1\\}g_{i}(d_{i},v_{i})$

where in the third step we have used the requirement that $v_{i}\leq d_{i}/8$.
Case $2$: $d_{i}/8<v_{i}\leq 2\beta d_{i}$.
Now we are in a range of velocity which is well-suited to make progress. In
fact, every step towards the optimum decreases the distance to the optimum by
at least the minimum of $\left\lfloor d_{i}\right\rfloor/{8}$ (if $v_{i}$ is
close to $d_{i}/8$ and we hence do not overshoot the target) and
$\left\lfloor(2-2\beta)d_{i}\right\rfloor$ (if $v_{i}=2\beta d_{i}\geq d_{i}$
in which case we overshoot the target and the distance to it from $d_{i}$ to
at most $\left\lfloor 2\beta d_{i}\right\rfloor-d_{i})$. In case of moving
towards the target value, the change in the first term of $g_{i}$ is thus at
least

$\min\\{\left\lfloor
d_{i}/8\right\rfloor,\left\lfloor(2-2\beta)d_{i}\right\rfloor\\}=\left\lfloor
d_{i}/8\right\rfloor,$

using $\beta\leq 0.9$. However, note that the decrease is at least $1$ (since
$v_{i}$ is at least $1$). Furthermore, we have, for all $z\geq
8,z/16\leq\left\lfloor z/8\right\rfloor.$ Thus, we always have a decrease of
at least $d_{i}/16$.

We now compute the change in the second term of $g_{i}$. Regard first the case
that
$\max\\{2v_{i}^{\prime}/d_{i}^{\prime},d_{i}^{\prime}/(2v_{i}^{\prime})\\}=2v_{i}^{\prime}/d_{i}^{\prime}$.
In this case, we pessimistically assume that the previous contribution of the
second term in $g_{i}(d_{i},v_{i})$ was zero. This contribution increases to
at most

(7) $\displaystyle 2cv_{i}^{\prime}+pd_{i}^{\prime}\leq 2\alpha
cv_{i}+pd_{i}^{\prime}\leq 2\alpha cv_{i}+pd_{i}\leq(4\alpha\beta c+p)d_{i}.$

On the other hand,
$\max\\{2v_{i}^{\prime}/d_{i}^{\prime},d_{i}^{\prime}/(2v_{i}^{\prime})\\}=d_{i}^{\prime}/(2v_{i}^{\prime})$
and the previous contribution of the second term in $g_{i}(d_{i},v_{i})$ was
$cd_{i}^{2}/(2v_{i})$, then the contribution of this second term has been
decreased to $c(d_{i}^{\prime})^{2}/(2\alpha v_{i})\leq cd_{i}^{2}/(2v_{i})$.
The change in contribution is thus positive in this case, and therefore in
particular strictly larger than $-(4\alpha\beta c+p)d_{i}$. We finally need to
regard the case that

$\max\\{2v_{i}^{\prime}/d_{i}^{\prime},d_{i}^{\prime}/(2v_{i}^{\prime})\\}=d_{i}^{\prime}/(2v_{i}^{\prime})$

and

$\max\\{2v_{i}/d_{i},d_{i}/(2v_{i})\\}=2v_{i}/d_{i}.$

In this case the contribution in the second term of $g_{i}$ increases by at
most

$\displaystyle\frac{cd_{i}^{\prime 2}}{2\alpha
v_{i}}\leq\frac{cd_{i}^{2}}{2\alpha(d_{i}/8)}\leq\frac{4cd_{i}}{\alpha}\leq
4\alpha\beta cd_{i},$

where the last step follows from $\alpha^{2}\beta\geq 1$.

Summarizing this discussion, we see that in case of stepping towards the
target the change in progress satisfies

(8) $\displaystyle g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})\geq
d_{i}(1/16-(4\alpha\beta c+p)),$

which is positive by our conditions on $c$ and $p$.

Let us now regard the case of stepping away from the optimum, which happens
with probability $1/2$ and the velocity is decreased to $\max\\{\beta
v_{i},1\\}$. Assume first that $\max\\{\beta v_{i},1\\}=\beta v_{i}$. Then,

(9) $\displaystyle
g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})=\max\\{2cv_{i},\frac{cd_{i}^{2}}{2v_{i}}\\}-\max\\{2c\beta
v_{i},\frac{cd_{i}^{2}}{2\beta v_{i}}\\}.$

If $\max\\{2c\beta v_{i},cd_{i}^{2}/(2\beta v_{i})\\}=cd_{i}^{2}/(2\beta
v_{i}),$ then the term in (9) is at least $-cd_{i}^{2}/(2\beta
v_{i})\geq-4cd_{i}/\beta$ by our condition $d_{i}/8\leq v_{i}$. Furthermore,
if $\max\\{2c\beta v_{i},cd_{i}^{2}/(2\beta v_{i})\\}=2c\beta v_{i},$ then (9)
is strictly positive as can be seen by the following observation

(10) $\displaystyle\max\\{2cv_{i},\frac{cd_{i}^{2}}{2v_{i}}\\}-2c\beta
v_{i}\geq 2cv_{i}-2c\beta v_{i}>0.$

Putting everything together we thus obtain that for $d_{i}/8\leq v_{i}\leq
2\beta d_{i}$

(11) $\displaystyle
E[g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})]\leq\frac{d_{i}}{2}(1/16-2(4\alpha\beta
c+p)-4c/\beta)$

which is positive if $8\alpha\beta c+2p+4c/\beta\leq 1/16$. Since
$v_{i}=\Theta(d_{i})$ this also shows that there is a positive constant
$\delta$ such that
$E[g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})]\geq\delta
g_{i}(d_{i},v_{i})$.

We finally need to regard the case that $\max\\{\beta v_{i},1\\}=1$.
Intuitively, the cap can only make our situation better. This is formalized by
the following computations. We need to bound

(12) $\displaystyle
g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})=\max\\{2cv_{i},\frac{cd_{i}^{2}}{2v_{i}}\\}-\max\\{2c,\frac{cd_{i}^{2}}{2}\\}.$

As above we obtain positive drift for the case $\max\\{2c,cd_{i}^{2}\\}=2c$ by
observing that $\max\\{2cv_{i},\frac{cd_{i}^{2}}{2v_{i}}\\}-2c\geq
2cv_{i}-2c\geq 0$ (using that $v_{i}\geq 1$). For the case
$\max\\{2c,cd_{i}^{2}\\}=cd_{i}^{2}$ the term in (12) is at least
$-cd_{i}^{2}\geq-cd_{i}^{2}/(2\beta v_{i})\geq-4cd_{i}/\beta$ as above. The
same computation as above thus shows a positive multiplicative gain in
$g_{i}$.

Case $3$: $2\beta d_{i}<v_{i}<2d_{i}$.
Under these conditions $g_{i}(d_{i},v_{i})=d_{i}+2cv_{i}+pd_{i}$ holds.

As before, we first regard the case that the algorithm moves towards the
target value. Since $\beta\geq 1/2$ it holds that $d_{i}\leq 2\beta
d_{i}<v_{i}$ and the target value is thus overstepped. However, due to the
requirement $v_{i}<2d_{i},$ the distance of the offspring is strictly smaller
than the previous distance. The velocity is hence increased to $\alpha v_{i}$.

With probability $1/2$ the algorithm does a step away from the goal and thus
the velocity is reduced to $v_{i}^{\prime}=\max\\{\beta v_{i},1\\}$. Regard
first the case that $v_{i}^{\prime}=\beta v_{i}$. Then, due to $\beta
v_{i}<2\beta d_{i}$, the penalty term $pd_{i}$ is no longer applied and the
resulting potential at component $i$ is thus
$g_{i}(d_{i}^{\prime},v_{i}^{\prime})=d_{i}+2c\beta v_{i}$.

Ignoring any possible gains in $d_{i}$, we therefore obtain that the expected
difference in the potential is at least

$2cv_{i}\left(1-\frac{\alpha+\beta}{2}\right)+\frac{p}{2}d_{i}$

Note that $1-(\alpha+\beta)/2$ is negative, since we require $\alpha+\beta>2.$
Using $v_{i}\leq 2d_{i}$ we see that the drift is at least

$4cd_{i}\left(1-\frac{\alpha+\beta}{2}\right)+\frac{p}{2}d_{i}=d_{i}\left(\frac{p}{2}-4c\left(\frac{\alpha+\beta}{2}-1\right)\right).$

Since $p>8c(\frac{\alpha+\beta}{2}-1)$ this expression is positive.
Furthermore, we have $g_{i}(d_{i},v_{i})=\Theta(d_{i}),$ yielding the desired
multiplicative drift.

For $v_{i}^{\prime}=1$ we first observe that $v_{i}^{\prime}=1\leq d_{i}\leq
2\beta d_{i}$ and the penalty term $pd_{i}$ is thus not in force. Furthermore,
we have $\beta d_{i}<\beta v_{i}\leq 1$ and thus $d_{i}\leq 1/\beta\leq 2,$
showing that $\max\\{2/d_{i},d_{i}/2\\}\leq\max\\{2,1\\}=2.$ We obtain

$E[g_{i}(d_{i},v_{i})-g(d_{i}^{\prime},v_{i}^{\prime})\geq\frac{p}{2}d_{i}-cv_{i}(\alpha-1)\geq\frac{p}{2}d_{i}-2(\alpha-1)cd_{i},$

which is positive for $p/2-2(\alpha-1)c>0$.

Case $4$: $v_{i}=2d_{i}.$
Steps away from the target are not accepted, thus regardless of whether or not
we move towards or away from the target, the fitness does not decrease;
therefore, the velocity is decreased to $\beta v_{i}$ (note that $v_{i}\geq 2$
and hence $\beta v_{i}\geq 1)$. The previous contribution of the $i$-th
component to $g(x)$ being $d_{i}+2cv_{i}+pd_{i}=d_{i}(1+4c+p),$ and the new
potential at the $i$-th component being $d_{i}(1+4\beta c)$, we obtain

$E[g_{i}(d_{i},v_{i})-g_{i}(d_{i}^{\prime},v_{i}^{\prime})]=d_{i}(4c+p-4\beta
c),$

which is strictly positive and linear in $g_{i}(d_{i},v_{i})$.

Case $5$: $2d_{i}<v_{i}$.
Steps towards the optimum are now also not accepted, since they overstep the
optimum by too much. Therefore, we always decrease the velocity to
$\max\\{\beta v_{i},1\\}=\beta v_{i}$ (note that $v_{i}>2$ and thus $\beta
v_{i}>1$) and the gain in potential is

$2cv_{i}+pd_{i}-(2c\beta v_{i}+pd_{i})=2cv_{i}(1-\beta)>4(1-\beta)cd_{i}$

showing that we have the multiplicative drift as desired.

Together with the observation that the initial potential is of order at most

$\sum_{i=1}^{n}d_{i}^{2}\leq\left(\sum_{i=1}^{n}d_{i}\right)^{2}=|a|_{1}^{2}$

plugged into the multiplicative drift theorem (4) proves the desired overall
expected run time of $O(n\log(|a|_{1}))$. ∎

Combining both results we get a sharp run time result in the following
theorem.

###### Theorem 12.

Let $f_{a}\in\mathscr{F}$. For constants $\alpha,\beta$ satisfying
$1<\alpha\leq 2,1/2<\beta\leq 0.9,2\alpha\beta-\beta-\alpha>0,\alpha+\beta>2$
and $\alpha^{2}\beta>1$ the expected optimization time of $RLS_{\alpha,\beta}$
starting with all $0$ integer string on $f_{a}$ is
$\Theta(n\cdot\log(|a|_{1}))$.

###### Proof.

The result follows by the matching lower bound in 10 with the upper bound in
11, ∎

##  6\. Comparison with CMA-ESwM

In this section we provide the following empirical analyses. First, we show
that the CMA-ESwM is not efficient for the integer-valued optimization problem
we consider. Then we compare the performances of (1+1) EA with the $\pm 1$
operator, (1+1) EA with the heavy-tailed operator and the RLS with the self-
adjusting operator.

Note that although the CMA-ESwM is designed to optimize mixed integer valued
problems, we restrict ourselves to all-integer inputs. This allows us to make
comparisons with the (1+1) EA and RLS with different mutation operators. We
use the code from GitHub111https://github.com/EvoConJP/CMA-ES_with_Margin
provided by the authors of the paper where the CMA-ESwM is proposed (Hamano et
al., 2022).

All our theoretical analyses are concerned with the unbounded integer search
space, whereas, for practical reasons, we have to restrict our search space to
be bounded. We bound the maximum value of the considered integer strings by a
value $r$.

We set the optimum as the all-$r$ integer string and let the algorithm run
until it finds the optimum and record the run time (number of function
evaluations). For (1+1) EA with different mutation operators and
$RLS_{\alpha,\beta}$, we start with the all-$0$ integer string. As for CMA-
ESwM, we consider the same set up proposed in (Hamano et al., 2022).

We choose the step size of $r$ as follows:

  1. (1)

(1+1) EA with $\pm 1$ operator: $r$ from 10 till 150 with a step size of 10.
Then we consider $r\in\\{10^{3},10^{4},10^{5}\\}$ to analyze the run time of
the algorithm for exponentially increasing values of $r$.

  2. (2)

$RLS_{\alpha,\beta}$ with the self-adjusting operator and (1+1) EA with the
heavy-tailed operator: we consider $r=10^{k}$, for $k\in\\{1,\ldots,12\\}$.
For RLS with the self-adjusting operator we set the parameter $\alpha=2.0$ and
$\beta=0.5$ and for the (1+1) EA with the heavy-tailed operator we set
$\epsilon=0.001$.

  3. (3)

CMA-ESwM: we consider the same values of $r$ as for the RLS since there are no
specific restrictions mentioned in (Hamano et al., 2022).

###  6.1. Success rate

During initial exploration we noticed that the CMA-ESwM does not always find
the optimum before it reaches the termination condition (minimum eigenvalue of
the covariance matrix in the update step of the CMA-ESwM algorithm is less
than $10^{-30}$). To further analyze this, we consider the following different
values of $r$, $\\{10,100,1000\\}$ and different $n$ (length of the integer
string) from $10$ to $100$ in steps of $10$. In Figure 1 we see the proportion
of failed runs over total of $100$ runs named failure rate. Note that for
$n<40$ the failure rate is zero so in Figure 1, $n\geq 40$.

Figure 1. Failure rate of the CMA-ESwM.

We can see from Figure 1 that the failure rate increases as $n$ increases.
Also, the failure rate is significant despite $r$ being quite small. This
shows the limitations of CMA-ESwM in optimizing a complete integer-valued
problem.

###  6.2. Comparison between different algorithms

We present experimental results of the (1+1) EA with the $\pm 1$ operator and
the heavy-tailed operator in Figure 2. All results are averaged over $20$
independent runs. We attach the results of the statistical test for $n=100$ in
the appendix.

Figure 2. Run time comparison of the (1+1) EA with two different mutation
operators and the RLS with the self-adjusting operator. Different colors stand
for different mutation operators and different line styles stand for different
values of $n$. Note that both axes are logarithmically scaled.

In Figure 2 we can see that the scaling behavior with respect to $r$ is
independent of the value of $n$.

Asymptotically, the results are as suggested by the theoretical results given
in the prior sections. However, for small values of $r$, the scaling behavior
is not yet the deciding factor. In particular, the $\pm 1$ operator is
competitive as long as the optimum is not much more than $r=10^{2}=100$ away
in each component. For higher values of $r$, the constantly small step size is
very much detrimental to efficient search.

An interesting finding is that the heavy-tailed operator can outperform the
self-adjusting RLS, in spite of what the asymptotic bounds given in this paper
suggest. For small values of $r$, a lot of time is wasted on attempting larger
jumps, but for middle-ranged $r$ these jumps start to pay off. In contrast,
the self-adaptive RLS needs a warm-up phase adjusting its velocity value,
meanwhile the heavy-tailed operator can make progress starting in the first
iteration.

## References

  * (1)
  * Antipov et al. (2020) Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020\.  Fast Mutation in Crossover-Based Algorithms. In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ (Cancún, Mexico) _(GECCO ’20)_. Association for Computing Machinery, New York, NY, USA, 1268–1276.  https://doi.org/10.1145/3377930.3390172
  * Antipov and Doerr (2020) Denis Antipov and Benjamin Doerr. 2020.  Runtime Analysis of a Heavy-Tailed Genetic Algorithm on Jump Functions. In _Parallel Problem Solving from Nature – PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part II_ (Leiden, The Netherlands). Springer-Verlag, Berlin, Heidelberg, 545–559.  https://doi.org/10.1007/978-3-030-58115-2_38
  * Do et al. (2021) Anh Viet Do, Mingyu Guo, Aneta Neumann, and Frank Neumann. 2021\.  Analysis of Evolutionary Diversity Optimisation for Permutation Problems. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Lille, France) _(GECCO ’21)_. Association for Computing Machinery, New York, NY, USA, 574–582.  https://doi.org/10.1145/3449639.3459313
  * Doerr et al. (2015) Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2015\.  Solving Problems with Unknown Solution Length at (Almost) No Extra Cost. In _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_ (Madrid, Spain) _(GECCO ’15)_. Association for Computing Machinery, New York, NY, USA, 831–838.  https://doi.org/10.1145/2739480.2754681
  * Doerr et al. (2017a) Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2017a.  Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables.  _Algorithmica_ 80 (07 2017).  https://doi.org/10.1007/s00453-017-0341-1
  * Doerr et al. (2022) Benjamin Doerr, Yassine Ghannane, and Marouane Ibn Brahim. 2022\.  Towards a Stronger Theory for Permutation-Based Evolutionary Algorithms. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Boston, Massachusetts) _(GECCO ’22)_. Association for Computing Machinery, New York, NY, USA, 1390–1398.  https://doi.org/10.1145/3512290.3528720
  * Doerr et al. (2012) Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012\.  Multiplicative Drift Analysis.  _Algorithmica_ 64, 4 (feb 2012), 673–697.  https://doi.org/10.1007/s00453-012-9622-x
  * Doerr et al. (2017b) Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017b.  Fast Genetic Algorithms. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Berlin, Germany) _(GECCO ’17)_. Association for Computing Machinery, New York, NY, USA, 777–784.  https://doi.org/10.1145/3071178.3071301
  * Hamano et al. (2022) Ryoki Hamano, Shota Saito, Masahiro Nomura, and Shinichi Shirakawa. 2022.  CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Boston, Massachusetts) _(GECCO ’22)_. Association for Computing Machinery, New York, NY, USA, 639–647.  https://doi.org/10.1145/3512290.3528827
  * Hansen et al. (2003) Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003.  Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES).  _Evolutionary Computation_ 11, 1 (03 2003), 1–18.  https://doi.org/10.1162/106365603321828970
  * He and Yao (2004) Jun He and Xin Yao. 2004\.  A study of drift analysis for estimating computation time of evolutionary algorithms.  _Natural Computing_ 3 (03 2004), 21–35.  https://doi.org/10.1023/B:NACO.0000023417.31393.c7
  * 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.
  * Rudolph (1994) Günter Rudolph. 1994\.  An evolutionary algorithm for integer programming. In _Parallel Problem Solving from Nature — PPSN III_ , Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 139–148.  https://doi.org/10.1007/3-540-58484-6_258

###### Acknowledgements.

This work is supported by grant FR 2988/17-1 by the German Research Foundation
(DFG).

##  Appendix A Statistical test for run time comparison

In this section we present the results of the statistical test. For each
algorithm, we use one box plot to show the distribution of independent runs
for $n=100$. Each box is the first quartile ($Q1$) to the third quartile
($Q3$) of the group. The whiskers extend the box by $1.5$ times the
interquartile range ($IQR$). Dots are outliers which pass whiskers.

For the other set up $n=20$, we get a similar box plot.

Figure 3. (1+1) EA with $\pm 1$ operator Figure 4. (1+1) EA with _heavy-tailed
operator_. Figure 5. RLS with the self-adjusting operator.


Explanation: The article proposes that the observed co-existence of multiple vortices at the same latitude can be explained by the formation of Kármán vortex streets. These structures consist of staggered rows of cyclones and anti-cyclones, where the cyclones act as `blocking vortices', preventing the anti-cyclones from merging due to their mutually repulsive interactions. This arrangement is consistent with observations, such as the chain of vortices at 41$^\circ$S, where cyclones and anti-cyclones are observed in close proximity without merging.

§.§ Astrophysics of Galaxies

This category deals with the structure, formation, and evolution of galaxies, including our Milky Way.

Paper ID: 1980ARA&A..18..165M

Question: What is the most likely explanation for the observed alignment between the radio axis of double radio sources and the minor axis of their host elliptical galaxies?

(A) The alignment is purely coincidental and has no physical basis.

(B) The radio jets preferentially expand along the path of least resistance, which coincides with the minor axis of the galaxy due to its flattened shape.

(C) The radio axis is aligned with the angular momentum axis of the galaxy, suggesting a connection between the central engine and the galaxy's rotation.

(D) The alignment is caused by the interaction of the radio jets with the surrounding intergalactic medium, which shapes the radio source along the minor axis of the galaxy.

Correct Answer: C

Explanation: The article, particularly in section 5.3, discusses the observed alignment between radio and galaxy axes and argues that it suggests a link between the radio-source production axis and the angular momentum axis of the galaxy. This implies a connection between the central engine (likely a black hole) and the galaxy's rotation. Options B and D, while potentially contributing factors, do not address the fundamental relationship between the radio source and the galaxy's intrinsic properties.

Paper ID: 1963ARA&A...1..149R

Question: How can the study of integrated spectra of galaxies provide information about their stellar content?

(A) The overall spectral type of a galaxy, determined from its integrated spectrum, directly corresponds to the most common type of star in the galaxy.

(B) The presence and strength of specific absorption lines in the integrated spectrum can reveal the types of stars contributing most to the galaxy's light at different wavelengths.

(C) The redshift of the integrated spectrum indicates the galaxy's age, which in turn provides information about the types of stars present.

(D) The shape of the continuum in the integrated spectrum reflects the distribution of dust in the galaxy, which can be used to infer the types of stars that are obscured.

Correct Answer: B

Explanation: The article explains that the presence and strength of specific absorption lines in the integrated spectrum of a galaxy can be used to identify the types of stars that contribute most to the galaxy's light at different wavelengths. For example: Cyanogen bands indicate the presence of late G and early K giant stars, weak TiO bands suggest a lack of late-type giants or supergiants, and the strength of Mg b blend, Na D lines, and CaI line points to a significant population of late-type dwarf stars. By analyzing these features across a wide wavelength range, astronomers can construct a qualitative picture of the galaxy's Hertzsprung-Russell diagram and its spectrum-luminosity function.

§.§ Cosmology and Nongalactic Astrophysics

This category covers the study of the universe as a whole, its origin, evolution, and large-scale structures, as well as active galactic nuclei (AGN) and other extragalactic phenomena.
Paper ID: 1998ARA&A..36..267R

Question: How does the column density distribution function (CDDF) provide information about the Lyman alpha forest?

(A) The CDDF describes the number of absorbers per unit column density interval. Its power-law shape over a wide range of column densities suggests a common origin for most Lyman alpha absorbers and provides insights into the underlying physical processes.

(B) The CDDF measures the clustering of Lyman alpha absorbers along the line of sight, indicating the presence of large-scale structures in the intergalactic medium.

(C) The CDDF describes the redshift evolution of the Lyman alpha forest, showing how the number of absorbers changes with cosmic time.

(D) The CDDF measures the temperature of the intergalactic medium based on the Doppler broadening of absorption lines.

Correct Answer: A

Explanation: The CDDF describes the number of absorbers per unit column density interval. Its power-law shape over a wide range of column densities suggests a common origin for most Lyman alpha absorbers and provides information about the underlying physical processes. The article explains this in detail in section 3.4.

Paper ID: 2003ARA&A..41..645R

Question: What is the primary advantage of using weak gravitational lensing to map dark matter compared to methods that rely on the distribution of light?

(A) Weak lensing is less affected by dust obscuration, providing a clearer view of dark matter.

(B) Weak lensing directly measures the mass distribution, including dark matter, rather than just the distribution of luminous matter.

(C) Weak lensing is sensitive to the motion of dark matter, revealing its dynamic behavior.

(D) Weak lensing can probe dark matter at higher redshifts than traditional methods.

Correct Answer: B

Explanation: Unlike methods that rely on the distribution of light, which only traces luminous matter, weak lensing directly measures the total mass distribution, including dark matter. This is because the bending of light by gravitational lensing is caused by the total mass, regardless of its luminosity. This direct measurement allows for a more accurate and reliable mapping of dark matter compared to methods that require assumptions about the relationship between light and mass.

§.§ High Energy Astrophysics

This category involves the study of high-energy phenomena in the universe, including black holes, neutron stars, and cosmic rays.

Paper ID: 2009ARA&A..47..107H

Question: How do the spins of black holes in a binary system affect the gravitational waves they emit?

(A) The spins of black holes have a negligible impact on the emitted gravitational waves, as the dominant contribution comes from the mass quadrupole moment.

(B) Spin-orbit and spin-spin interactions introduce additional parameters into the waveform, encoding information about the binary's masses and spins, but these parameters may be highly correlated.

(C) Spin precession, caused by the motion of the black holes in the binary's curved spacetime, leads to phase and amplitude modulation of the gravitational waves, breaking parameter degeneracies and enhancing our ability to characterize the system.

(D) The presence of spin significantly reduces the recoil or `kick' experienced by the black hole due to the emission of gravitational waves.

Correct Answer: C

Explanation: The spins of black holes in a binary system have a profound effect on the emitted gravitational waves. Spin-orbit and spin-spin interactions introduce additional parameters into the waveform, but the most significant impact comes from spin precession. As the black holes' spins precess due to their motion in the binary's curved spacetime, the gravitational waves exhibit phase and amplitude modulation. This modulation breaks parameter degeneracies, allowing for more precise measurements of the binary's properties, such as the individual masses and spins of the black holes.

Paper ID: 1993ARA&A..31..175M

Question: What was the primary energy source for the luminosity of SN 1987A after the initial 3 months?

(A) Nuclear fusion in the core

(B) Gravitational contraction

(C) Radioactive decay of elements like Cobalt-56

(D) Accretion onto a central compact object

Correct Answer: C

Explanation: The article clearly states that after the initial 3 months, during which the trapped radiation diffused out, the light curve of SN 1987A closely followed the decay rate of Cobalt-56, indicating radioactive decay as the primary energy source. This is further supported by the discussion on the role of other radioactive isotopes like Cobalt-57 and Titanium-44 in powering the later stages of the light curve.

§.§ Instrumentation and Methods for Astrophysics

This category focuses on the development and application of tools and techniques used in astronomical observations and data analysis.

Paper ID: 1999ARA&A..37...65R

Question: What was the main point of contention between radio astronomers and the operators of the GLONASS satellite navigation system?

(A) The GLONASS satellites were transmitting signals within a radio astronomy band allocated for observations of the hydroxyl (OH) molecule, causing significant interference.

(B) The GLONASS satellites were physically obstructing the view of radio telescopes, hindering astronomical observations.

(C) The GLONASS system was consuming an excessive amount of radio frequency spectrum, leaving insufficient bandwidth for radio astronomy research.

(D) The GLONASS satellites were generating harmful radiation that posed a health risk to astronomers working at radio observatories.

Correct Answer: A

Explanation: The article details the conflict between radio astronomers and the operators of the GLONASS system, which arose due to the GLONASS satellites transmitting signals within the 1610.6-1613.8 MHz band allocated for radio astronomy observations of the hydroxyl (OH) molecule. This interference significantly impacted radio astronomy research, leading to extensive negotiations and efforts to resolve the issue.

Paper ID: 1982ARA&A..20..367W

Question: What is the main advantage of using `speckle interferometry'?

(A) It allows for observations at longer wavelengths, such as the infrared.

(B) It is a simple and inexpensive technique compared to other methods.

(C) It can achieve higher angular resolution than traditional imaging techniques.

(D) It is less affected by atmospheric seeing compared to direct imaging.

Correct Answer: C

Explanation: Speckle interferometry is a technique that analyzes the short-exposure speckle patterns in a star image to extract high-resolution information about the object. The article explains that this method can overcome the limitations imposed by atmospheric seeing and achieve diffraction-limited resolution, making it particularly valuable for studying close binary stars and resolving the structures of distant galaxies.

§ CLASSIFICATION OF ASTROPHYSICS QUESTIONS BY ABILITY

In addition to categorizing questions by topic, we also classified them based on the cognitive abilities and skills they require. This classification allows for a more nuanced analysis of model performance across different aspects of astrophysical knowledge. The categories are as follows:

§.§ Understanding Fundamental Concepts

This category tests the grasp of basic principles and foundational knowledge in astrophysics.

Paper ID: 1966ARA&A...4..145M

Question: What is the significance of the polarization of radio emission from radio galaxies?

(A) It indicates the presence of a strong, ordered magnetic field throughout the source

(B) It provides information about the distribution and orientation of the magnetic field in the source

(C) It is a direct measure of the energy of the relativistic electrons

(D) It is primarily caused by scattering of radio waves by dust grains

Correct Answer: B

Explanation: The article discusses how the polarization of radio emission, particularly the direction of polarization in different parts of the source, can be used to infer the structure of the magnetic field. The generally low degree of polarization observed suggests that the magnetic field is not uniform in direction. By studying the polarization, astronomers can gain insights into the magnetic field configuration within radio galaxies.

§.§ Technical and Observational Techniques

This category focuses on specific methods, tools, and techniques used in astrophysical research and observations.

Paper ID: 1970ARA&A...8..265H

Question: What is the primary factor that limits the sensitivity of radio telescopes when searching for pulsars at low frequencies?

(A) The intrinsic faintness of pulsars at low frequencies.

(B) Radio interference from terrestrial sources.

(C) The dispersion of pulsar signals by the interstellar medium, requiring smaller bandwidths and leading to a loss of sensitivity.

(D) The limited collecting area of existing radio telescopes.

Correct Answer: C

Explanation: As detailed in the `Search techniques and limitations' section, the dispersion of pulsar signals by the interstellar medium causes a frequency sweep. To observe this at low frequencies requires very small receiver bandwidths to avoid smearing out the signal, which in turn reduces sensitivity. This effect becomes more pronounced with increasing dispersion measure and hence distance.

§.§ Analytical and Reasoning Skills

This category includes questions that require critical thinking, problem-solving, and the application of knowledge to analyze and interpret data or phenomena.

Paper ID: 1990ARA&A..28..437H

Question: How do quasar-galaxy correlations inform us about the environments of quasars?

(A) Studies of quasar-galaxy correlations suggest that low-redshift quasars are more likely to have companion galaxies than typical galaxies, but they do not usually reside in rich clusters. The environments of high-redshift quasars are less clear, with some studies suggesting positive correlations and others indicating anticorrelations or no association.

(B) Quasar-galaxy correlations provide evidence for the non-cosmological nature of quasar redshifts, as quasars appear to be associated with galaxies at much lower redshifts.

(C) Quasar-galaxy correlations are used to study the phenomenon of gravitational lensing, where the light from a distant quasar is bent by the gravity of a foreground galaxy.

(D) Quasar-galaxy correlations are not a reliable tool for studying quasar environments due to the low space density of quasars and the challenges of identifying true associations.

Correct Answer: A

Explanation: Section 4.2 discusses quasar-galaxy correlations and their implications for quasar environments. The article highlights the findings from various studies, indicating that low-redshift quasars tend to have more companion galaxies than average but are not typically found in rich clusters. The situation at high redshifts is more complex and requires further investigation.

§.§ Historical and Theoretical Knowledge

This category tests the understanding of historical developments, theoretical models, and key discoveries in the field of astrophysics.

Paper ID: 1994ARA&A..32..319W

Question: What was the primary motivation for considering non-baryonic dark matter in the context of CMB anisotropies?

(A) The need to explain the observed large-scale structure in the universe.

(B) The inability of baryonic matter models to account for the observed CMB anisotropies.

(C) Claims of a significant mass for the electron neutrino, suggesting a potential dark matter candidate.

(D) The need to reconcile the age of the universe with the observed expansion rate.

Correct Answer: C

Explanation: In the early 1980s, claims of a substantial mass for the electron neutrino spurred interest in non-baryonic dark matter models. This was because such a massive neutrino could potentially account for the missing mass needed to explain the observed gravitational effects in the universe. As a result, researchers started exploring the implications of such models for CMB anisotropies.

§.§ Current Research and Advanced Topics

This category focuses on recent research, advanced topics, and cutting-edge developments in astrophysics.

Paper ID: 2019ARA&A..57..335F

Question: What is the role of gravitational screening mechanisms in modified gravity theories?

(A) Screening mechanisms suppress the effects of modified gravity on small scales, such as within galaxies and clusters, while allowing them to manifest on cosmological scales.

(B) Screening mechanisms enhance the strength of gravity in regions of high density, leading to the formation of black holes and other compact objects.

(C) Screening mechanisms explain the observed acceleration of the universe's expansion without the need for dark energy.

(D) Screening mechanisms account for the observed discrepancies between the predicted and measured values of the Hubble constant.

Correct Answer: A

Explanation: The article discusses how gravitational screening mechanisms can suppress the effects of modified gravity in regions of high density or curvature, such as within galaxies and clusters, while allowing them to manifest on larger, cosmological scales. This is achieved by suppressing the fifth force charge or coupling in these high-density environments.

These examples demonstrate the diverse range of abilities and skills required in astrophysics, from understanding fundamental concepts to analyzing complex phenomena and engaging with cutting-edge research. By categorizing questions in this manner, we can assess how well different models perform across various aspects of astrophysical knowledge and reasoning.

It's important to note that unlike the topic-based categorization, the classification by ability is arguably more subjective and potentially ambiguous. Many questions may test multiple abilities simultaneously, making a clear-cut categorization challenging. For this study, we assigned each question to a single ability category that we deemed most prominent, acknowledging that this approach is undoubtedly a simplification of the complex nature of these questions. This crude categorization allows us to discern broad trends in model performance across different cognitive skills. However, we recognize the limitations of this approach and aim to explore more nuanced categorization methods in future work. Our upcoming paper will investigate into this issue, presenting a more detailed human curation and analysis of these questions to provide a more comprehensive understanding of how different abilities are represented and tested in astrophysical knowledge assessment.