# Representation-agnostic distance-driven perturbation for optimizing ill-
conditioned problems

Kirill Antonov  LIACS, Leiden UniversityNiels Bohrweg 1Leiden2333The
Netherlands<EMAIL_ADDRESS>0000-0002-8757-8598 ,  Anna V.
Kononova  LIACS, Leiden UniversityNiels Bohrweg 1Leiden2333The Netherlands
<EMAIL_ADDRESS>0000-0002-4138-7024 ,  Thomas Bäck  LIACS,
Leiden UniversityNiels Bohrweg 1Leiden2333The Netherlands
<EMAIL_ADDRESS>0000-0001-6768-1478 and  Niki van Stein
LIACS, Leiden UniversityNiels Bohrweg 1Leiden2333The Netherlands
<EMAIL_ADDRESS>0000-0002-0013-7969

###### Abstract.

Locality is a crucial property for efficiently optimising black-box problems
with randomized search heuristics. However, in practical applications, it is
not likely to always find such a genotype encoding of candidate solutions that
this property is upheld with respect to the Hamming distance. At the same
time, it may be possible to use domain-specific knowledge to define a metric
with locality property. We propose two mutation operators to solve such
optimization problems more efficiently using the metric. The first operator
assumes prior knowledge about the distance, the second operator uses the
distance as a black box. Those operators apply an estimation of distribution
algorithm to find the best mutant according to the defined in the paper
function, which employs the given distance. For pseudo-boolean and integer
optimization problems, we experimentally show that both mutation operators
speed up the search on most of the functions when applied in considered
evolutionary algorithms and random local search. Moreover, those operators can
be applied in any randomized search heuristic which uses perturbations.
However, our mutation operators increase wall-clock time and so are helpful in
practice when distance is (much) cheaper to compute than the real objective
function.

##  1\. Introduction

Randomized search heuristics (RSH) are convenient off-the-shelf solvers of
difficult optimization problems (Auger and Doerr, 2011; Rozenberg et al.,
2012). While they do not necessarily guarantee to locate the exact solution to
any problem, they aim to approximate a solution of sufficient quality in a
feasible time frame. Applications of such algorithms require the user to
define a search space $X$, where possible solutions are located, and the
objective function $f$ with domain $X$. This function defines the considered
problem and usually is expensive to evaluate (in terms of computation cost,
licenses or resources). In the scope of the current work, we consider finite
set $X\subseteq\mathbb{Z}^{n}$, function $f$ with image $\mathbb{R}$ and
algorithms that aim to maximize function $f$, meaning finding such $x^{*}\in
X$ that

$\max\\{f(x)\mid x\in X\\}-f(x^{*})\approx 0$

Evolutionary algorithms (EAs) are RSH inspired by the process of natural
evolution. Such algorithms, supported by theory (Jansen, 2013a; Doerr and
Neumann, 2019; Lengler, 2020), show promising applications to pseudo-
boolean/integer problems (Li et al., 2013; Doerr et al., 2019; Dushatskiy et
al., 2021) including real-world scenarios (Bäck et al., 1995; Grossmann and
Sahinidis, 2002; Slowik and Kwasnicka, 2020). One of the main classical
assumptions and the most important requirement to the problem optimized with
EAs is strong causality (Rechenberg, 1989) also known as contiguity and
locality (Raidl and Gottlieb, 2005). It means that a small change in the
candidate solution leads to a solution with similar performance according to
the fitness function. The significance of the change is measured according to
the distance metric $d:X^{2}\to\mathbb{R}$ (Jansen, 2013b), for example,
Hamming distance in the case of pseudo boolean domains, or euclidean distance
in the case of $\mathbb{R}^{n}$ domains. We will say that metric $d$ is strong
causal (SC) for the set of problems $\mathcal{F}$ if all the problems in the
set have locality property with regard to metric $d$. It is known that the
existence of such SC metric for $\mathcal{F}$ guarantees that $\mathcal{F}$ is
not closed under permutations of the search space $X$ (Jansen, 2013c). In this
case, the NFL theorem (Schumacher et al., 2001) guarantees the existence of an
algorithm that outperforms other algorithms on average for functions in
$\mathcal{F}$. So the existence of SC metric for $\mathcal{F}$ is sufficient
to design a problem solver for $\mathcal{F}$ that performs above average.

The SC metric may exist for a set of functions that a practitioner solves, but
obtaining this metric usually requires a certain level of expertise in the
domain. It means that the SC metric gives away some information on the
structure of the considered problems. While EAs do not require any information
on the domain of the problem, it is well known that problem-specific knowledge
significantly increases the performance of EAs (Droste and Wiesmann, 2003). We
identify 4 main categories of approaches to take advantage of different kinds
of domain-specific information in EA:

1) Asymmetric mutation operator. Methods in this category use the information
about the problem to modify the mutation operator employed by an EA. Doerr et
al (Doerr et al., 2006, 2007) consider the Eulerian cycle problem and
rigorously show that asymmetry in mutation operator, for example avoiding
certain modifications, leads to a performance increase compared to EA with
classical mutations. Raidl et al (Raidl et al., 2006) show the benefits of EA
with a mutation operator that chooses rather edges with smaller weights to
solve the minimum spanning tree problem and the traveling salesmen problem.
Jansen and Sudholt analyzed the influence of a bias in the mutation operator
when it is applied to pseudo boolean functions (Jansen and Sudholt, 2010).
They considered a mutation operator that flips 1 with a higher probability
when a solution contains more ones and vice-versa. The work rigorously shows
that such bias speeds up $(1+1)$-EA equipped with such operator on three of
the functions they considered, and slows down the algorithm on another
function. Their work was extended by proposing an adaptation of the degree of
asymmetry during the optimization process (Rajabi and Witt, 2020).

2) Enhanced representation. Traditionally, there are no specific restrictions
on the used representation, but there is a number of recommendations (Rothlauf
and Rothlauf, 2006). In the EA community, the mainstream is to simply use the
most natural representation of the individual (Rudolph, 2012). However,
finding such a representation may already require expert-level knowledge in
the domain of the problem. Many works with a focus on practical applications
prove this, for example, Yu et al applied an EA to the object decomposition
for 3D printing (Yu et al., 2017), where they used a Binary Space Partitioning
tree encoded as an array of continuous numbers. The design of such
representation requires an understanding of the principles of object
decomposition. In the area of spatial design creation, the challenging problem
of defining a search space that does not significantly restrict the space of
all possible solutions was subjected to comprehensive research in
(Pereverdieva et al., 2023). Moreover, standard EA may work significantly
slower when the representation is not carefully chosen. Doerr et al developed
such a representation for the Eulerian cycle problem that allowed to develop
an EA with the arguably best reachable by RSH expected run-time (Doerr and
Johannsen, 2007).

3) Data-driven approaches. This category covers automated algorithm selection
(Kerschke et al., 2019; Kostovska et al., 2022; Ye et al., 2021; Long et al.,
2022; Guo et al., 2019) and dynamic algorithm configuration (Biedenkapp et
al., 2020; Adriaensen et al., 2022), where automatically extracted features of
the problem are used to suggest an optimization method or a configuration of
the algorithm.

4) Diverse set of candidate solutions. Diversity measure of the set of
candidate solutions can be evaluated using a domain-specific distance, as it
is suggested in (Solow and Polasky, 1994). It is known, that more diverse sets
of parents in EA facilitate global exploration properties of the algorithm,
reduce the risk to get stuck in local optima and allow obtaining multiple
dissimilar high-quality solutions (Sudholt, 2020). Niching methods were
developed to maintain diverse sets of individuals in EA, for a comprehensive
overview see (Das et al., 2011; Preuss, 2015; Preuss et al., 2021). Distance-
based niching methods have a great number of successful applications, which
shows the advantage of distance knowledge. For example, Dynamic Peak
Identification niching (Shir and Bäck, 2009) maintains high-performing
solutions with a pairwise distance larger than the given lower bound. This
method was successfully applied to find a number of high-performing designs of
lenses in a single run of an EA in (Kononova et al., 2021). In the domain of
airfoil optimization, a variation of niching was proposed, where the algorithm
alternates between pure quality and distance-based diversity optimizations
which allows to obtain better-performing solutions (Reehuis et al., 2013;
Reehuis, 2013).

As we see from the examples of approaches in categories 1 and 2, the user
needs to have deep knowledge of both: the domain of the problem, and the
optimization method. Approaches in category 3 have the disadvantage that the
predicted algorithms/configurations do not always perform well, especially
when a new (unseen) problem is dissimilar from the problems that the
approaches are trained for. Approaches in category 4 leave the hard work to
pick a distance that represents the problem well to the expert in the domain
and allows using this distance as a black-box in the optimization algorithm.
However, this distance has influence only on the selection part of EA. Since
distance gives away information on the problem, it can also be leveraged in
other parts of an EA to speed up the optimization even more. At the moment,
there exist classical requirements to the design of crossover and mutation
operators for an EA in a metric space (Droste and Wiesmann, 2000, 2003;
Jansen, 2013b). A practitioner, who wants to use metrics, needs to redesign
the operators accordingly, which requires the application of methods from
categories 1 and 2.

Our contribution: We propose two versions of the mutation operator which
employs a given distance and allows switching it without the necessity to
amend the algorithm. The first developed mutation operator uses information
about possible values of the distance. The second operator does not require
any knowledge of the structure of the distance and uses it as a black-box. The
application of such mutation operators in an EA does not require any
additional effort from a practitioner to switch one metric to another and has
great benefits where a natural representation of the problem lacks strong
causality.

##  2\. Preliminaries

Evolutionary algorithms (EAs) are a class of search and optimization
algorithms inspired by the principles of natural selection and Darwinian
evolution. These algorithms are based on the idea that a population of
solutions to a problem can evolve and improve over time through the
application of selection, reproduction, and variation operators. For example,
the algorithm, (1+1)-ES, uses an iterative procedure that mutates the search
point of a single individual $x\in\mathbb{R}^{n}$ by a multivariate normal
distribution, $x^{\prime}=x+\sigma\cdot\mathcal{N}(\mathbf{0},\mathbf{I})$,
and assigns $x\leftarrow x^{\prime}$ iff $f(x^{\prime})\leq f(x)$.

During the optimization process an EA samples elements of the search space $X$
and evaluates the values of fitness function $f$ in the sampled points. While
doing it, EA ideally balances exploration/exploitation. It explores the search
space by sampling elements with significantly different structures, which can
be seen as gaining knowledge of the problem. Reversely, an EA exploits when
structures of consequently sampled elements are similar. The significance of
the structural difference between sampled solutions can be measured with
metric $d$, which is usually considered as the distance between elements is
$X$. Despite the fact that the optimization problem is completely specified
when $X$ and $f$ are given, it is convenient to talk about the landscape of
the problem when the exploration/exploitation capabilities of an EA are
analyzed. The landscape of the optimization problem is classically defined as
follows.

###### Definition 2.0 (Landscape (Reeves, 2000)).

For the problem $f$ defined on the metric space $X$ with metric $d$ the
landscape is a triple $(X,f,d)$.

The following algorithms are used in this work for the basis of our proposed
mutation operators:

_$(1+\lambda)~{}\text{EA}$_ is an elitist evolutionary algorithm without
crossover. Given the fitness function $f:X\to\mathbb{R}$, such algorithm
maintains the most fit solution and iteratively samples modifications of this
solution. Each modification is obtained using the given parameterized
distribution $\mathcal{D}$ over the number of modified components (Doerr et
al., 2016).

_$(1+(\lambda,\lambda))~{}\text{EA}$_ is an extension of
$(1+\lambda)~{}\text{EA}$ which uses crossover with bias $c$. At first, this
algorithm samples $\lambda$ solutions using mutation, then it picks the best
mutant and recombines it $\lambda$ times with the best-so-far solution. Each
recombination applies crossover in such a way that for every component the bit
is taken from the first parent with probability $(1-c)$, and from the second
parent with probability $c$. The best-so-far solution is updated with the
fittest individual after such recombinations. This algorithm has proven itself
well in theory (Antipov et al., 2019, 2020).

_Randomized Local Search_ (RLS) is a stochastic local search algorithm. RLS
iteratively explores the neighborhood of a current solution and selects a new
solution based on a randomized criterion that takes into account the quality
of the neighboring solutions. RLS is characterized by its simplicity,
efficiency, and ease of implementation. In this work we apply an extension of
this algorithm to integer search spaces, so-called RLS-ab (Doerr et al.,
2018). This extension controls the set of values of size $n$, which identifies
how quickly the corresponding component is updated. The control is done
independently for every value. When the new mutant is better than the best-so-
far solution, the value is increased, otherwise, it is decreased.

_$(1+\lambda)~{}\text{EA}_{\text{ab}}$_ This is our simple extension of RLS-
ab. The update adds a possibility to create $\lambda$ individuals on every
iteration and sample the number of modified components from the binomial
distribution with success probability $1/n$. The operator to make mutation for
every selected component stays the same, including the update rule of the
parameters.

_Univariate Marginal Distribution Algorithm_ (UMDA) (Larrañaga and Lozano,
2001) is another population-based stochastic optimization algorithm. UMDA
operates by sampling and updating the probability distribution of each
variable in the solution vector independently, and generating new candidate
solutions using a random sampling process based on the updated probability
distributions. Every iteration it samples $\lambda$ individuals and uses $\mu$
best of them to update the probability distribution. This algorithm does not
use the notions of the neighbourhood and so it has the potential to be
efficiently applied even when SC distance does not exist for the problem.
However, it is suggested to use a large enough size of $\lambda$ to solve
problems with difficult properties (Doerr and Krejca, 2020), so this algorithm
may not be applicable in practical applications right away. We apply this
algorithm to a relatively cheap function when we design our mutation operator.
In this work, UMDA is adapted to handle integer domains. To achieve this we
maintain the estimated probability of every integer in every component.

##  3\. High-level overview of the proposed approaches

Given the definition 2.1 of a landscape, we say that an algorithm becomes
landscape aware if it uses the specific distance $d$ for solving the
optimization problem apart from $X$ and $f$ that are always used by RSH. In
the scope of this work, we only propose ways to use this distance in the
mutation operator. We will call a mutation operator distance-driven if it uses
such distance to generate mutants. Accordingly, we will say that an algorithm
is distance-driven if it uses a distance-driven mutation operator.

Let us consider RSH $\mathcal{A}$ which applies a mutation operator when it
solves an optimization problem in the landscape $(X,f,d^{\prime})$. We make an
assumption that $d^{\prime}$ is not a SC distance for $f$. At the same time,
we assume that SC distance $d\neq d^{\prime}$ for $f$ is given to us by an
oracle. In this section we propose a way to change $\mathcal{A}$ to a
distance-driven algorithm dd-$\mathcal{A}$ which solves the optimization
problem (at least partially) in the landscape $(X,f,d)$. The optimization is
performed in the new landscape completely when $\mathcal{A}$ uses only
mutations to sample new solutions. However, we leave distance-driven crossover
operators for future work, so if $\mathcal{A}$ uses recombination in addition
to mutation, then dd-$\mathcal{A}$ partially works in the old landscape.

Both our distance-driven mutation operators rely on a parameterized family of
distributions over all possible step sizes. In Section 4 we explain what we
exactly mean by this. In Section 4 we assume that the distribution is defined
by hand, which is possible when the so-called structure of the distance is
known. Then in Section 5, we show how to create this distribution
automatically for any given distance. The distance-driven mutation operator
itself is given in Algorithm 1 and it is applied in both proposed methods, but
with different distributions. Consequently, given SC distance $d$ and
distribution $\mathcal{D}$ defined in Section 4 we transform $\mathcal{A}$ to
dd-$\mathcal{A}$ by substituting distance-driven mutation operator to
$\mathcal{A}$ instead of the usual mutation operator.

##  4\. Proposed method for the distance with known structure

Traditionally, mutation creates a structural change in the individual. The
change is usually defined by the probabilistic distribution over different
structural changes. The shape of the distribution reflects the intuition about
the search. For example, in local search methods, the distribution is defined
over only small mutations, that likely do not lead to quitting the basin of
attraction. In global search methods, such as Evolutionary Strategies (ES),
the distribution is defined over all the search space, but smaller changes
happen with higher probability. Even though the mutation itself is sampled
from this distribution, the significance of this change is defined w.r.t. the
distance metric. Classically, it is assumed that the distribution is equipped
with such a distance metric, that considers components independently and a
small change in the value of every component contributes a small addition to
the total value of distance. When the metric is different, but the same
algorithm is applied, the mutations sampled from the same distribution likely
do not give the properties that are expected from the perturbations.

Let us consider mutation $\mu:X\to X$ that happens at some point in the
optimization algorithm. Note that $\mu$ and $\mu^{\prime}$ as mutations at
different time points may be different due to the stochasticity of the
heuristic search. We will say that step size of mutation w.r.t. distance $d$
is the value $s\coloneqq d(x,\mu(x))$. The probabilistic distribution that is
used in the mutation operator defines the step size of the operator. This step
size may be sampled from the distribution explicitly, or implicitly, as
happens in ES when the mutation itself is sampled. In the mutation operator
that we design, we do not use anything from the distribution except the
information on the step size. Hence, we consider the distribution defined over
step sizes.

Let us define what we denote as the distribution over step sizes more
precisely. First of all, we denote the set of all pairwise distances between
points in the search space $S=\\{d(x,y)\mid x,y\in X\\}$ as structure of the
distance. In this section, we assume that $S$ is known to the designer of the
algorithm. In order to allow balancing exploration/exploitation in the
algorithm we add parametrization to the distribution, which significantly
improves the performance of EA (Eiben et al., 1999; Antonov et al., 2021). All
the parameters of the distribution are denoted with $\alpha$. This vector
controls the shape of the distribution and is updated outside of the mutation
operator according to the rules defined in the distance-driven algorithm.
Given parameters $\alpha$, individual $x\in X$ which is being perturbed and
metric $d$, the distribution over step sizes from $x$ is:

(1)
$\mathcal{D}_{x,\alpha}\coloneqq\\{\mathbb{P}_{\alpha}\left[d(x,\mu(x))=d(x,y)\right]\mid
y\in X\\}$

For the given $\alpha$, distance-driven algorithm possess the following set of
distributions in order to apply distance-driven mutation operator at any point
of $X$:

(2) $\mathcal{D}_{\alpha}\coloneqq\\{\mathcal{D}_{x,\alpha}\mid x\in X\\}$

Then the parametrized family of sets of distributions is given by:

(3) $\mathcal{D}\coloneqq\\{\mathcal{D_{\alpha}}\mid\alpha\\}$

We will say that $\mathcal{D}$ defined in Eq. 3 is distributions family. The
choice of this distribution family is left to the user. To choose
$\mathcal{D}$ it is sufficient to define $\mathcal{D_{\alpha}}$ in Eq. 2 and
so it is sufficient to define $\mathcal{D}_{x,\alpha}$ in Eq. 1. Therefore it
is sufficient to define the parametrized probability of mutation from any
element in $X$ to any element in $X$. In order to do this, it is necessary and
sufficient to know the set $S$.

Our distance-driven mutation operator generates another individual that steps
away from the initial one to the distance closest to the given step size. To
implement this generation we solve another optimization problem as written in
Algorithm 1.

Algorithm 1 Distance-driven mutation operator of individual $x\in X$ given
distance $d:X^{2}\to\mathbb{R}$, distributions family $\mathcal{D}$ and
distribution parameters $\alpha$

1:$\mathcal{D_{\alpha}}\in\mathcal{D}$ $\triangleright$ Choose parametrized
distribution from $\mathcal{D}$

2:$\mathcal{D}_{x,\alpha}\in\mathcal{D}_{\alpha}$ $\triangleright$ Choose
distribution for the given point $x$

3:$s\sim\mathcal{D}_{x,\alpha}$ $\triangleright$ Sample mutation strength

4:$y\leftarrow\operatorname*{arg\,min}_{y}\\{\left|d(x,y)-s\right|\\}$
$\triangleright$ Internal optimization

5:return $y$

In line 4 of Algorithm 1 the optimization problem is solved. The properties of
the function optimized in this line are mostly defined by the properties of
distance $d$. Note that Hamming distance (or Euclidean distance) $h$ is not SC
distance for this function, because otherwise $h(x,y)<\varepsilon\implies
d(x,y)<\varepsilon\implies\left|f(x)-f(y)\right|<\delta$ which contradicts our
assumption that $h$ is not SC distance for fitness function $f$. In order to
optimize this function, we apply UMDA with a large $\lambda$ and a big budget.

Application of this version of the mutation operator requires the user to know
the structure of distance and define the distributions family. Obtaining
knowledge of the distance structure may require expertise in the domain of the
problem. Moreover, the size of $S$ may be extremely big, so defining the
distributions family may not be feasible in some cases. To free the user from
the necessity to learn this structure, we propose the following extension of
the mutation operator, which automatically does both: explores the structure
of distance and creates distributions family.

##  5\. Proposed method for black-box distance

The main purpose of this section is to propose a method that is able to extend
the perturbation operator for the distance with an unknown structure. This
allows the decoupling of an expert in optimization and an expert in the field
of the domain. We expect that the distance created by an expert in the domain
is well-defined. It means that the distance is SC and on top of that we also
expect certain structural properties, which we summarize in the following
assumption.

###### Assumption 1.

For any points $x,y\in X$:

  1. (1)

Variability: $\left|\\{d(x,z)\mid z\in X\\}\right|\gg 1$;

  2. (2)

Consistency: $\min\\{d(x,z)\mid z\in
X\setminus\\{x\\}\\}\approx\min\\{d(y,z)\mid z\in X\setminus\\{y\\}\\}$;
moreover $\max\\{d(x,z)\mid z\in X\\}\gg\min\\{d(x,z)\mid z\in
X\setminus\\{x\\}\\}$;

  3. (3)

Cheapness: wall-clock time required for computation of $d(x,y)$ is
significantly smaller than the wall-clock time required for computation of the
objective function at any point.

The most important assumption for our methods is cheapness because the inner
optimization problem is solved for every application of the mutation operator,
which is normally called as often as the objective function. When the metric
does not satisfy this property our method becomes very time-consuming. If the
variability assumption is not upheld for many points, then the practitioner,
who knows this fact, has already enough knowledge to use the previous method
and create distributions family $\mathcal{D}$ based on their tastes. The
consistency assumption is needed to save computational resources when we
explore the space of possible values of the given metric. Our method is still
applicable if this condition is not upheld for a subset of the search space,
but for every point in this subset, we need to run a new exploration
procedure, which becomes time-consuming.

In the case of black-box distance, it is impossible to define a distributions
family $\mathcal{D}$ in advance. Here we propose a method to create such
distributions family that can be used in Algorithm 1. Designing this
distributions family for the general case of the metric is challenging because
of the two following problems. 1) Different scales: For different search
points $x$, $y$ and different metrics $d_{1}$, $d_{2}$ it may be the case that
$d_{1}(x,y)/d_{2}(x,y)\gg 1$. 2) Different gaps: For different search points
$x,y\in X$ and different metrics $d_{1},d_{2}$, the values
$v_{i}\coloneqq\left|\\{z\in
X\mid\max\\{d_{i}(x,z),d_{i}(y,z)\\}<d_{i}(x,y)\\}\right|$ may be
significantly different for $i\in\\{1,2\\}$.

At first, we propose a general transformation of the distance metric to solve
both those problems. Then we define the distributions family over the
transformed values of distance. This transformed distance and distributions
family are used in Algorithm 1 in the same way as in the previous subsection.

###  5.1. Transformation of the distance

Given metric $d$, for every point $x\in X$ we map $A_{d,x}=\\{d(x,y)\mid y\in
X\\}$ to the spread subset of $(0,1)$ with a monotonic function

(4) $\tau_{\gamma}(x,y)=1-\exp{(-\gamma^{2}d^{2}(x,y))}$

The second term in the mapping is the well-known Gaussian function. Let us
define the set $\mathcal{I}_{\gamma}=\\{\tau_{\gamma}(x,y)\mid y\in
X\setminus\\{x\\}\\}$. Such mapping transforms $A_{d,x}$ to
$\mathcal{I}_{\gamma}\subset(0,1)$ for any metric $d$ and so allows to have
the same ranges of distances, which solves the first problem we mentioned. The
parameter $\gamma$ of Eq. 4 is chosen in such a way that
$\mathcal{I}_{\gamma}$ is as spread as possible. This requirement ensures that
all the values of $\mathcal{I}_{\gamma}$ do not collapse to a very dense
segment where different values of distance are not distinguishable given the
limitations of the representation of floating point numbers.

To satisfy this requirement we consider the following problem regarding
$\varepsilon_{1},\varepsilon_{2}$:

(5) $\displaystyle\min\quad$ $\displaystyle\varepsilon_{1}$ (6)
$\displaystyle\min\quad$ $\displaystyle\varepsilon_{2}$ (7) s.t.
$\displaystyle\min{\mathcal{I}_{\gamma}}\leq\varepsilon_{1}$ (8)
$\displaystyle\max{\mathcal{I}_{\gamma}}\geq 1-\varepsilon_{2}$

The constraint 7 defines the upper bound on the smallest mapped distance,
analogously constraint 8 defines the lower bound for the largest mapped
distance. For the purposes of our application, we simplify the problem. We aim
to find sufficiently small $\varepsilon_{1}$ and ensure that $\varepsilon_{2}$
is small as well. Specifically, we iterate over values of $\varepsilon_{1}$ in
the range $(10^{-4},10^{-2})$ with step $10^{-4}$ and stop when we find
smallest $\varepsilon_{1}\geq\varepsilon_{2}$ such that
$\varepsilon_{1},\varepsilon_{2}$ satisfy the constraints 7, 8.

To check if the given value of $\varepsilon_{1}$ satisfies the constraints we
simplify them as follows. Using monotonic property of Eq. 4 we have:

$\begin{cases}1-\exp{(-\gamma^{2}(\min{A_{d,x}})^{2})}\leq\varepsilon_{1}\\\
1-\exp{(-\gamma^{2}(\max{A_{d,x})^{2})}}\geq 1-\varepsilon_{2}\end{cases}$

which is transformed to:

$\dfrac{\sqrt{-\ln(\varepsilon_{2})}}{(\max{A_{d,x}})^{2}}\leq\gamma\leq\dfrac{\sqrt{-\ln(1-\varepsilon_{1})}}{(\min{A_{d,x}})^{2}}$

We combine this with the additional condition
$\varepsilon_{1}\geq\varepsilon_{2}$ and obtain the following:

$(1-\varepsilon_{1})^{\left(\dfrac{\max{A_{d,x}}}{\min{A_{d,x}}}\right)^{2}}\leq\varepsilon_{1}$

To estimate the values $\zeta_{\text{max}}\coloneqq\max{A_{d,x}}$ and
$\zeta_{\text{min}}\coloneqq\min{A_{d,x}}$ we consider fixed values
$t,T\in\mathbb{R}:0<t<1<T$ and such sequence $(z_{i})_{i=-k,\dots,k}$ that:

$\begin{cases}z_{i}\sim\text{u.a.r.}(X\setminus\\{x\\}),&\text{if }i=0\\\
d(x,z_{i})\geq Td(x,z_{i-1}),&i>0\\\ d(x,z_{i})\leq
td(x,z_{i+1}),&i<0\end{cases}$

As approximation of $\zeta_{\text{max}}$ and $\zeta_{\text{min}}$ we take
$\widehat{\zeta_{\text{max}}}\coloneqq d(x,z_{k})$,
$\widehat{\zeta_{\text{min}}}\coloneqq d(x,z_{-k})$ accordingly. Steps above
to compute $\varepsilon_{1},\varepsilon_{2},\gamma$ are summarised in
Algorithm 2.

Algorithm 2 Computation of the parameters
$\varepsilon_{1},\varepsilon_{2},\gamma$ for the given point $x\in X$

1:$z_{0}\leftarrow\text{u.a.r.}(X\setminus\\{x\\})$

2:for $i\leftarrow 1,\dots,k$ do

3: $z_{i}\leftarrow z\in\left\\{z\in X\mid d(x,z)\geq T\cdot
d(x,z_{i-1})\right\\}$ $\triangleright$ Optimize

4: $z_{-i}\leftarrow z\in\left\\{z\in X\setminus\\{x\\}\mid d(x,z)\leq t\cdot
d(x,z_{i+1})\right\\}$ $\triangleright$ Optim.

5:end for

6:$\widehat{\zeta_{\text{max}}}\leftarrow d(x,z_{k})$

7:$\widehat{\zeta_{\text{min}}}\leftarrow d(x,z_{-k})$

8:for $j\leftarrow 1,\dots,c$ do

9: $\varepsilon_{1}\leftarrow 10^{-4}j$

10:
$\varepsilon_{2}\leftarrow\exp{\left[\left(\dfrac{\widehat{\zeta_{\text{max}}}}{\widehat{\zeta_{\text{min}}}}\right)^{2}\ln{(1-\varepsilon_{1})}\right]}$

11: if $\varepsilon_{2}\leq\varepsilon_{1}$ then break end if

12:end for

13:$\gamma\leftarrow\dfrac{1}{2}\left(\dfrac{\sqrt{-\ln(\varepsilon_{2})}}{\widehat{\zeta_{\text{max}}}^{2}}+\dfrac{\sqrt{-\ln(1-\varepsilon_{1})}}{\widehat{\zeta_{\text{min}}}^{2}}\right)$

14:return {$\varepsilon_{1},\varepsilon_{2},\gamma$}

Algorithm 2 takes as input a point from $X$. When a certain point $p\in X$ is
passed as input to Algorithm 2 we say that the output values
$\varepsilon_{1},\varepsilon_{2},\gamma$ are computed for the point $p$.
Following our consistency assumption, the values of $\varepsilon_{1}$ and
$\varepsilon_{1}^{\prime}$ are similar when computed for different points
$x,x^{\prime}\in X$. Using the same assumption we have: $d(x,z_{k})\gg
d(x,z_{-k})$. When the optimization problems in lines 3, 4 of Algorithm 2 are
solved precisely we obtain:
$\widehat{\zeta_{\text{max}}}\gg\widehat{\zeta_{\text{min}}}$. So we neglect
the small change in
$\left(\frac{\widehat{\zeta_{\text{max}}}}{\widehat{\zeta_{\text{min}}}}\right)^{2}$
and argue that values $\varepsilon_{2}$ and $\varepsilon_{2}^{\prime}$ are
very close, when computed as in line 10 of Algorithm 2 for different points
$x,x^{\prime}\in X$. We take advantage of this and compute
$\varepsilon_{1},\varepsilon_{2},\gamma$ only once for a point $x\in X$ chosen
uniformly at random.

Following the variability assumption, $\left|A_{d,x}\right|\gg 1$ which makes
elements of $\mathcal{I}_{\gamma}=\\{\tau_{\gamma}(x,y)\mid y\in X\\}$ located
very close to each other in $\mathcal{I}_{\gamma}$. It means that there are no
significant gaps between values in $\mathcal{I}_{\gamma}$, which solves the
second problem.

In our implementation, we used the following constants:
$k=10,T=2,t=1.2,c=100$. To find an element from the set defined in line 3 we
apply UMDA to maximize the objective function $f_{1}(z)\coloneqq d(x,z)-T\cdot
d(x,z_{i-1})$ with stopping criteria that, apart from limiting the number of
function evaluations, has condition $f_{1}(z)\geq 0$. Similarly, to compute
$z_{-i}$ in line 4 we apply UMDA with the objective function
$f_{2}(z)\coloneqq t\cdot d(x,z_{i+1})-d(x,z)$ and stopping criteria that
includes conditions $f_{2}(z)\geq 0$ and $f_{2}(z)<t\cdot d(x,z_{i+1})$. The
second additional condition is needed to ensure that $z_{-i}\neq x$.

###  5.2. Distribution over the transformed values

In this subsection, we derive distribution $\mathcal{D}_{x,\alpha}$ for
arbitrary element $x\in X$ and parameters $\alpha$. Since the values
$\varepsilon_{1},\varepsilon_{2},\gamma$ are the same for all the points, the
distributions $\mathcal{D}_{x,\alpha}$ are the same for all the points in $X$
when parameters $\alpha$ are fixed. To be more concise, in this section, we
will denote $\mathcal{D}_{x,\alpha}$ as $\mathcal{D}$.

The distribution over $\mathcal{I}_{\gamma}$ is chosen to be continuous to
avoid computation of the exact value $\left|\mathcal{I}_{\gamma}\right|$. The
fact that $\mathcal{I}_{\gamma}$ has finite size does not corrupt the
algorithm, because of the big density of points in $\mathcal{I}_{\gamma}$.
Moreover, the optimization problem in Algorithm 1 may not be solved precisely
even when the distribution is discrete. It means that for a random variable
$\xi\sim\mathcal{D}$ the value $\xi-\min\\{\left|d(x,y)-\xi\right|\\}$ may not
be zero in practice, but close to zero in the case of discrete and continuous
distributions. Then, the distribution is chosen as such $\mathcal{D}^{*}$ that
have maximal differential entropy over continuous distributions with fixed
mean $m\in\mathcal{I}_{\gamma}$:

(9)
$\mathcal{D}^{*}=\operatorname*{arg\,max}_{\mathcal{D}}\\{H(\mathcal{D})\mid\operatorname{E}(\xi\sim\mathcal{D})=m\\}$

The maximal entropy is enforced to obtain an unbiased mutation operator
(Rudolph, 2012). We fix the mean of this distribution to allow controlling the
step size during the optimization process. Distributions with fixed moments of
higher order and other properties are left for future works. This is done
because enforcing other properties will make it much more complex to solve the
optimization problem defined in Eq. 9. On the other hand, distribution with a
fixed mean and maximal entropy is already enough to efficiently solve problems
with different complex properties, when the algorithm adjusts the mean during
the optimization process. For example, one of $(1+\lambda)$ EA with mutation
rate control optimizes a number of difficult pseudo-boolean functions faster
than competitors (Doerr et al., 2019). The step size of mutation in
$(1+\lambda)$ EA is sampled from the Binomial distribution. Mutation rate
control is equivalent to controlling only the mean of this distribution. At
the same time, Binomail distribution is the maximal entropy distribution among
discrete distributions with the fixed mean and fixed support (Harremoës,
2001). This motivates the hope, that our mutation operator with distribution
from Eq. 9 has the potential to assist optimization better than mutation
operators with other distributions, given that a smart enough method to
control the mean is used.

In order to find the probability density function (pdf) $\mathcal{P}$ of
distribution defined in Eq. 9 we consider the following optimization problem:

(10) $\displaystyle\operatorname*{arg\,max}\limits_{\mathcal{P}}\quad$
$\displaystyle{-\int\limits_{\varepsilon_{1}}^{1-\varepsilon_{2}}{\mathcal{P}(x)\ln\mathcal{P}(x)dx}}$
(11) s.t.
$\displaystyle\int\limits_{\varepsilon_{1}}^{1-\varepsilon_{2}}{\mathcal{P}(x)dx}=1$
(12)
$\displaystyle\int\limits_{\varepsilon_{1}}^{1-\varepsilon_{2}}{\mathcal{P}(x)xdx}=m$

The following solution of Eq. 10 is unique for such
$\lambda_{0},\lambda_{1}\in\mathbb{R}$ that satisfy the constraints Eq. 11,
Eq. 12 (Jaynes, 1957a, b; Cover, 1999):

(13) $\mathcal{P}(x)=\exp{(\lambda_{0}+\lambda_{1}x)}$

Substitution of Eq. 13 to Eq. 11, Eq. 12 and integration, gives us the
following system:

$\begin{cases}\dfrac{\exp{(\lambda_{0})}}{\lambda_{1}}\left(e^{\lambda_{1}(1-\varepsilon_{2})}-e^{\lambda_{1}\varepsilon_{1}}\right)=1\\\
\dfrac{\exp{(\lambda_{0})}}{\lambda_{1}^{2}}\left(e^{\lambda_{1}(1-\varepsilon_{2})}(\lambda_{1}(1-\varepsilon_{2})-1)-e^{\lambda_{1}\varepsilon_{1}}(\lambda_{1}\varepsilon_{1}-1)\right)=m\end{cases}$

Combining those two equations into one with condition that $\lambda_{1}\neq 0$
gives us the following:

(14)
$e^{\lambda_{1}(1-\varepsilon_{2})}(\lambda_{1}(1-\varepsilon_{2})-1)-e^{\lambda_{1}\varepsilon_{1}}(\lambda_{1}\varepsilon_{1}-1)=\\\
\lambda_{1}m\left(e^{\lambda_{1}(1-\varepsilon_{2})}-e^{\lambda_{1}\varepsilon_{1}}\right)$

If the solution of Eq. 14 exists regarding $\lambda_{1}$ then it is unique
because the solution of Eq. 10 is unique. The left part of Eq. 14 converges to
0 for $\lambda_{1}\to-\infty$ and converges to 0 for $\lambda_{1}\to 0$. The
right part of Eq. 14 is infinitely big for $\lambda_{1}\to-\infty$ and
converges to 0 for $\lambda_{1}\to 0$. Moreover for $\lambda_{1}\to-0$ the
left part is greater than the right part. Since the functions of
$\lambda_{1}<0$ in both parts are continuous there exists a solution of Eq. 14
for $\lambda_{1}<0$. To find the solution we apply binary search with bounds
$(-K,0)$, where $K$ is sufficiently big.

Figure 1. Average parallel optimization time and standard deviation of the
considered algorithms (x-axis: best-so-far value of fitness function; y-axis:
average number of iterations) on the Ruggedness with $v\in[1,5]$.
Dimensionality $n=100$, $11$ runs for every algorithm. UMDA is used as an
internal optimizer of distance-driven algorithms with parameters
$\mu=50,\lambda=100$, budget = $1000$. The limit on the number of iterations
is $5\cdot 10^{6}$.
Figure 2. Convergence of the considered algorithms (x-axis: number of fitness
evaluations; y-axis: best-so-far value of regret and its standard error) on
the transformed COCO/BBOB-MIXINT suite. Dimensionality $n=40$, cardinality of
every component is $100$, $100$ runs for RLS-ab and $(1+1)$ EA-ab, $10$ run
for dd$(1+1)$ EA-ab. UMDA is used as an internal optimizer of the distance-
driven algorithm with parameters $\mu=10^{2},\lambda=10^{3}$, budget = $4\cdot
10^{4}$. The limit on the number of fitness function evaluations is $5000$.

##  6\. Experiments

In this section we outline the different experimental setups used to validate
the proposed contributions. This is done using two experiments: binary OneMax-
based problems to show the effectiveness of using distance-driven permutation
in an easy-to-analyze use-case, and a discretized version of the BBOB
benchmark suite to show the generalizability of the proposed approach.

###  6.1. Experimental Setup

#### Binary problems.

In order to benchmark Algorithm 1 as it is, we consider a binary OneMax-based
problem in $n$ dimensions (i.e. with search space $X=\\{0,1\\}^{n}$). We adopt
Ruggedness problem based on OneMax and implement it as in W-Model suite (Weise
and Wu, 2018). In our experiments, we define OneMax as
$l_{1}(x)\coloneqq\left|x\right|$ ($L_{1}$-norm of binary string $x$).
Ruggedness uses a given permutation $\pi$ and applies it to the objective
values of the underlying function, which is OneMax in our case. We define such
Ruggedness as: $r_{\pi}(x)\coloneqq\pi^{-1}(l_{1}(x))$. We define distance for
this problem as $d(x,y)\coloneqq\left|r_{\pi}(x)-r_{\pi}(y)\right|$. Note that
such distance satisfies all the requirements of the distance metric because it
is based on the absolute value. Moreover, this is SC distance. The permutation
is stored implicitly, such that for every integer $0<v<n$:

$\begin{cases}r(x)=l_{1}(x)+v-2(l_{1}(x)\bmod v)-1,&\text{if }\lfloor
l_{1}/v\rfloor\neq\lfloor n/v\rfloor\\\ r(x)=l_{1}(x)+v_{1}-2k-1,&\text{if
}\lfloor l_{1}/v\rfloor=\lfloor n/v\rfloor\end{cases}$

Here $v_{1}=(n\bmod v)$ and $k=(l_{1}(x)\bmod v_{1})-((\lfloor n/v\rfloor
v)\bmod v)$. In our implementation, we considered $v\in[1,5]$. Note that with
$v=1$ Ruggedness is OneMax. Greater values of $v$ create dissipative intervals
of size $v$, for example, for $v=5$ the objective value 99 of OneMax is
permuted to 95, 99 to 96, …, 95 to 99.

We extended both $(1+\lambda)$ EA and $(1+(\lambda,\lambda))$ EA with our
distance driven mutation operator. The modified algorithms are called
dd-$(1+\lambda)$ EA and dd-$(1+(\lambda,\lambda))$ EA accordingly. Both
algorithms are considered without any parameter control. In the implementation
of Algorithm 1 we implemented Binomial distribution with $n$ Bernoulli
experiments with success probability $1/n$. Note that the value sampled from
this distribution may be larger than the maximal distance reachable from point
$x$ (for example when it is of the form $11..100..0$). In this case, the
optimization in line 4 of Algorithm 1 is terminated when it runs out of
budget. The parameters of UMDA taken in the experiments on binary problems are
the following: $\mu=50,\lambda=100$, budget = $1000$.

#### Integer problems.

We consider integer problems to demonstrate the advantages of the distance-
driven mutation operator when the distance satisfies the assumptions. The
domain of those problems is $X=\Pi_{i=1}^{n}\\{0,c_{i}-1\\}$, where
$(c_{i})_{i=1\dots n}$ are cardinalities. The problems are taken from
COCO/BBOB-MIXINT suit (Tušar et al., 2019). We extended the problems to get
rid of continuous variables and support the arbitrary cardinality of every
component, the rest details on these problems were left unchanged. To show the
advantages of our mutation operator, we transform those problems in our
experiments. For the given permutation $\pi$ and function $f$ from BBOB-MIXINT
we define the transformed function $Tf(x)\coloneqq
f\left[(\pi^{-1}(x_{i}))_{i=1,\dots,n}\right]$. Here $x_{i}$ stands for the
$i$-th component of $x$. Note that here permutation is the same for all the
dimensions. We implemented this transformation because in our experiments the
cardinalities of all the dimensions are equal. When permutation is applied to
the search space the neighbourhood structures are destroyed in every
component, so Euclidean distance becomes ill-conditioned. We define distance
for the transformed problem as $d(x,y)\coloneqq
l_{2}(\left[(\pi^{-1}(x_{i}))_{i=1,\dots,n}\right]-\left[(\pi^{-1}(y_{i}))_{i=1,\dots,n}\right])$.
This distance takes inverse permutations of every component and computes
$L_{2}$-norm of the difference of obtained vectors. In all of the experiments,
the same permutation was used for search space transformation.

In the experiments we consider $n=40$ dimensions, each one with cardinality
$c=100$ for every problem in the suit COCO/BBOB-MIXINT. We extended UMDA to
the domains where the cardinality of every component is greater than 2. The
parameters of this extended UMDA taken in the experiments on those problems
are the following: $\mu=10^{2},\lambda=10^{3}$, budget = $4\cdot 10^{4}$.

In our experiments we maximized negative regret, meaning the value
$f(x^{*})-f(x)$, where $f$ is a problem, $x^{*}$ is the global optimum of $f$,
$x$ is a candidate solution. At the same time, we plot positive regret in
Figure 2 to avoid confusion.

We extended RLS algorithm with our mutation operator. Note that the new
algorithm does not do local search anymore because the distribution is defined
over all found values of distances. We control the mean of the distribution in
the following way. Assume that the mutation operator produced individual $y$,
and the best-so-far solution is $x$. Then if $f(y)>f(x)$ we increase the mean
(which increases the expected step size) $m=a\cdot m$. If $f(y)<f(x)$ then we
reduce the mean $m=b\cdot m$. The rest of the steps (except mutation and
parameter update) are the same as in RLS algorithm. We call this modified
algorithm dd-$(1+1)~{}\text{EA}_{\text{ab}}$. In the implementation, we take
values $a=1.001,b=0.999$. To simplify the numerical solution of Eq. 14 we took
$\varepsilon_{1}=0,\varepsilon_{2}=1$ at that equation (and only there). In
this case the solution regarding $\lambda_{1}$ always belongs to $[-1/m,0)$.

The implementation of all considered algorithms, problems and experiments can
be accessed at Zenodo (Antonov et al., 2023).

###  6.2. Results

#### Binary problems.

In Figure 1 we compare the performance of the described algorithms on
Ruggedness problem with different values of $v$. Algorithms with modified
mutation operators performed much better than their analogues in all of the
considered cases of $v>1$. For $v=1$ the performance of the algorithm is
almost the same, indeed distance-driven mutation operator uses the same step
sizes because the distribution is the same for all the algorithms. However,
$\text{dd}-(1+(4,4))~{}\text{EA}$ slightly outperforms dd-$(1+4)$ EA on most
of the points, except the final points for $v=4$ and $v=5$. When an individual
is in the local optima, the mutation-only algorithm waits in this optima until
a sufficiently big step size is sampled from the distribution. At the same
time, crossover adds additional variability which helps to escape the local
optima. This is the reason for the slight advantage of
$\text{dd}-(1+(4,4))~{}\text{EA}$ on the most of optimization trajectory. At
the same time, the performance of both algorithms is significantly better than
their analogues and the gap between them grows with the growth of $v$.

#### Integer problems.

In Figure 2 we compare the performance of dd-$(1+1)~{}\text{EA}_{\text{ab}}$
against two algorithms that are not aware of SC distance for the problems. As
expected, for the majority of functions, specifically for F1, F2, F6-F14, F16,
and F20-F22 the increase in performance of dd-$(1+1)~{}\text{EA}_{\text{ab}}$
is significant compared to the other algorithms. It shows that our algorithm
manages to explore the search space well enough to find the values of
parameters that allow the mutation operator to generate small distances as
well as big ones. However, we observe that performance is much worse on
functions F3 and F4. For function F4, this may happen because both competitor
algorithms got lucky with a permutation of the search space, which allowed
them to jump to the local optima of better quality at the beginning, where
they converged to the basin of attraction and got stuck. For function F3, the
distance-aware algorithm may lose because it treats all the directions evenly.
When it finds the ridge of F3, it continues to sample solutions outstanding to
the sampled step size $s$. Vectors of all possible perturbations make a hyper
ball of radius $s$ which intersects many other points apart from the points on
the ridge. So the probability to improve the value of the objective function
becomes very small. This is the reason why we observe a very slow convergence
of distance-driven algorithms on this function. For function F24 distance-
driven algorithm also loses to the competitor that is able to make jumps to
bigger step sizes in the search space. The reason for this might be the fact
that basins of attraction on F24 are small, so the algorithm needs to make
small steps to not jump from one valley to another. This is the weak spot of
the distance-driven algorithm because in order to find smaller values of
distance it needs to spend much more time on internal optimization, which
makes the algorithm significantly slower. On top of that, the algorithm stops
making jumps to other basins of attraction, because, after the initial
convergence, the mean of the distribution becomes too small. It happens
because the parameter control method that we pick for
dd-$(1+1)~{}\text{EA}_{\text{ab}}$ is rather simple. On the rest of the
functions, the distance-driven algorithm slightly wins or shows approximately
the same performance as competitors.

##  7\. Conclusion

In this work, we propose two extensions of the perturbation operator. Both
operators are applicable to a broader class of algorithms than just EAs. They
can extend other RSHs that use the notion of distance to make changes in the
solution, for example, Simulated-Annealing. The first extension relies on the
structure of the distance. The user of this approach is expected to design the
distribution over step sizes that they target to see in the perturbation
operator. When the step size is sampled from the distribution, it is used to
solve the inner optimization problem, where the mutant is generated. The goal
of the inner optimization is to generate such an individual that is a number
of steps away from the given individual to a distance close to the sampled
step size.

The second mutation operator uses distance as a black-box. It explores the
search space prior to defining the distribution. The information about the
problem that was obtained during the exploration is then used to define the
distribution over the step size with maximal entropy and fixed value of the
mean. To estimate the parameters of this distribution we solve the numerical
optimization problem and repeat this optimization every time the mean changes.
This allows us to control the strength of changes that are made in the
mutation operator.

We observed the performance of the first operator on pseudo-boolean problems
and the performance of the second operator on integer problems to empirically
evaluate the proposed operators. From the results, distance-driven operators
were found to do better on most functions. It shows the advantage of being
aware of the distance during the optimization. However, the performance on
some functions is worse, because of imperfections of parameter control,
specificities of the considered problem, and due to the fact that our operator
treats all the directions evenly.

In future work, we plan to identify directions in the metric space to assist
the mutations to proceed in the most promising direction with higher
probability. This should improve the performance of the functions F3.
Moreover, it will allow us to apply the most advanced methods of parameter
control that exist in Evolutionary Strategies in our mutation operators.

###### Acknowledgements.

We would like to thank our collaborators at SRON for the real-world motivation
that inspired this work.

## References

  * (1)
  * Adriaensen et al. (2022) Steven Adriaensen, André Biedenkapp, Gresa Shala, Noor Awad, Theresa Eimer, Marius Lindauer, and Frank Hutter. 2022\.  Automated dynamic algorithm configuration.  _Journal of Artificial Intelligence Research_ 75 (2022), 1633–1699.
  * Antipov et al. (2019) Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2019\.  A tight runtime analysis for the (1+($\lambda$, $\lambda$)) GA on LeadingOnes. In _Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms_. 169–182.
  * Antipov et al. (2020) Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2020\.  The (1+($\lambda$, $\lambda$)) GA is even faster on multimodal problems. In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_. 1259–1267.
  * Antonov et al. (2021) Kirill Antonov, Maxim Buzdalov, Arina Buzdalova, and Carola Doerr. 2021.  Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms. In _2021 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 878–885.
  * Antonov et al. (2023) Kirill Antonov, Anna V. Kononova, Thomas Bäck, and Niki van Stein. 2023.  _distance-aware-ea: FOGA release_.  https://doi.org/10.5281/zenodo.7897290
  * Auger and Doerr (2011) Anne Auger and Benjamin Doerr. 2011.  Theory of randomized search heuristics: Foundations and recent developments.  (2011).
  * Bäck et al. (1995) Thomas Bäck, Martin Schütz, et al. 1995\.  Evolution Strategies for Mixed-Integer Optimization of Optical Multilayer Systems.. In _Evolutionary Programming_. 33–51.
  * Biedenkapp et al. (2020) André Biedenkapp, H Furkan Bozkurt, Theresa Eimer, Frank Hutter, and Marius Lindauer. 2020\.  Dynamic algorithm configuration: Foundation of a new meta-algorithmic framework.  In _ECAI 2020_. IOS Press, 427–434.
  * Cover (1999) Thomas M Cover. 1999\.  _Elements of information theory_.  John Wiley & Sons.
  * Das et al. (2011) Swagatam Das, Sayan Maity, Bo-Yang Qu, and Ponnuthurai Nagaratnam Suganthan. 2011\.  Real-parameter evolutionary multimodal optimization—A survey of the state-of-the-art.  _Swarm and Evolutionary Computation_ 1, 2 (2011), 71–88.
  * Doerr et al. (2018) Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2018\.  Static and self-adjusting mutation strengths for multi-valued decision variables.  _Algorithmica_ 80 (2018), 1732–1768.
  * Doerr et al. (2016) Benjamin Doerr, Carola Doerr, and Jing Yang. 2016.  Optimal parameter choices via precise black-box analysis. In _Proceedings of the Genetic and Evolutionary Computation Conference 2016_. 1123–1130.
  * Doerr et al. (2006) Benjamin Doerr, Nils Hebbinghaus, and Frank Neumann. 2006\.  Speeding up evolutionary algorithms through restricted mutation operators. In _Parallel Problem Solving from Nature-PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings_. Springer, 978–987.
  * Doerr et al. (2007) Benjamin Doerr, Nils Hebbinghaus, and Frank Neumann. 2007\.  Speeding up evolutionary algorithms through asymmetric mutation operators.  _Evolutionary Computation_ 15, 4 (2007), 401–410.
  * Doerr and Johannsen (2007) Benjamin Doerr and Daniel Johannsen. 2007.  Adjacency list matchings: an ideal genotype for cycle covers. In _Proceedings of the 9th annual conference on Genetic and evolutionary computation_. 1203–1210.
  * Doerr and Krejca (2020) Benjamin Doerr and Martin S Krejca. 2020.  The univariate marginal distribution algorithm copes well with deception and epistasis. In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion_. 17–18.
  * Doerr and Neumann (2019) Benjamin Doerr and Frank Neumann. 2019.  Theory of evolutionary computation: Recent developments in discrete optimization.  (2019).
  * Doerr et al. (2019) Carola Doerr, Furong Ye, Naama Horesh, Hao Wang, Ofer M Shir, and Thomas Bäck. 2019\.  Benchmarking discrete optimization heuristics with IOHprofiler. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. 1798–1806.
  * Droste and Wiesmann (2000) Stefan Droste and Dirk Wiesmann. 2000.  Metric based evolutionary algorithms. In _Genetic Programming: European Conference, EuroGP 2000, Edinburgh, Scotland, UK, April 15-16, 2000. Proceedings 3_. Springer, 29–43.
  * Droste and Wiesmann (2003) Stefan Droste and Dirk Wiesmann. 2003.  On the design of problem-specific evolutionary algorithms.  _Advances in evolutionary computing: theory and applications_ (2003), 153–173.
  * Dushatskiy et al. (2021) Arkadiy Dushatskiy, Marco Virgolin, Anton Bouter, Dirk Thierens, and Peter AN Bosman. 2021.  Parameterless Gene-pool Optimal Mixing Evolutionary Algorithms.  _arXiv preprint arXiv:2109.05259_ (2021).
  * Eiben et al. (1999) Ágoston E Eiben, Robert Hinterding, and Zbigniew Michalewicz. 1999.  Parameter control in evolutionary algorithms.  _IEEE Transactions on evolutionary computation_ 3, 2 (1999), 124–141.
  * Grossmann and Sahinidis (2002) IE Grossmann and Nikolaos V Sahinidis. 2002.  Special issue on mixed integer programming and its application to engineering, part I.  _Optim. Eng_ 3, 4 (2002), 52–76.
  * Guo et al. (2019) Xin Guo, Bas van Stein, and Thomas Bäck. 2019.  A new approach towards the combined algorithm selection and hyper-parameter optimization problem. In _2019 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2042–2049.
  * Harremoës (2001) Peter Harremoës. 2001\.  Binomial and Poisson distributions as maximum entropy distributions.  _IEEE Transactions on Information Theory_ 47, 5 (2001), 2039–2041.
  * Jansen (2013a) Thomas Jansen. 2013a.  _Analyzing evolutionary algorithms: The computer science perspective_.  Springer.
  * Jansen (2013b) Thomas Jansen. 2013b.  Evolutionary Algorithms and Other Randomized Search Heuristics.  _Analyzing Evolutionary Algorithms: The Computer Science Perspective_ (2013), 7–29.
  * Jansen (2013c) Thomas Jansen. 2013c.  General limits in black-box optimization.  _Analyzing Evolutionary Algorithms: The Computer Science Perspective_ (2013), 45–84.
  * Jansen and Sudholt (2010) Thomas Jansen and Dirk Sudholt. 2010.  Analysis of an asymmetric mutation operator.  _Evolutionary Computation_ 18, 1 (2010), 1–26.
  * Jaynes (1957a) Edwin T Jaynes. 1957a.  Information theory and statistical mechanics.  _Physical review_ 106, 4 (1957), 620.
  * Jaynes (1957b) Edwin T Jaynes. 1957b.  Information theory and statistical mechanics. II.  _Physical review_ 108, 2 (1957), 171.
  * Kerschke et al. (2019) Pascal Kerschke, Holger H Hoos, Frank Neumann, and Heike Trautmann. 2019.  Automated algorithm selection: Survey and perspectives.  _Evolutionary computation_ 27, 1 (2019), 3–45.
  * Kononova et al. (2021) Anna V Kononova, Ofer M Shir, Teus Tukker, Pierluigi Frisco, Shutong Zeng, and Thomas Bäck. 2021\.  Addressing the multiplicity of solutions in optical lens design as a niching evolutionary algorithms computational challenge. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. 1596–1604.
  * Kostovska et al. (2022) Ana Kostovska, Anja Jankovic, Diederick Vermetten, Jacob de Nobel, Hao Wang, Tome Eftimov, and Carola Doerr. 2022.  Per-run algorithm selection with warm-starting using trajectory-based features. In _Parallel Problem Solving from Nature–PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part I_. Springer, 46–60.
  * Larrañaga and Lozano (2001) Pedro Larrañaga and Jose A Lozano. 2001.  _Estimation of distribution algorithms: A new tool for evolutionary computation_. Vol. 2.  Springer Science & Business Media.
  * Lengler (2020) Johannes Lengler. 2020\.  Drift analysis.  _Theory of evolutionary computation: Recent developments in discrete optimization_ (2020), 89–131.
  * Li et al. (2013) Rui Li, Michael TM Emmerich, Jeroen Eggermont, Thomas Bäck, Martin Schütz, Jouke Dijkstra, and Johan HC Reiber. 2013\.  Mixed integer evolution strategies for parameter optimization.  _Evolutionary computation_ 21, 1 (2013), 29–64.
  * Long et al. (2022) Fu Xing Long, Bas van Stein, Moritz Frenzel, Peter Krause, Markus Gitterle, and Thomas Bäck. 2022\.  Learning the characteristics of engineering optimization problems with applications in automotive crash. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 1227–1236.
  * Pereverdieva et al. (2023) Ksenia Pereverdieva, Michael Emmerich, André Deutz, Tessa Ezendam, Thomas Bäck, and Hèrm Hofmeyer. 2023.  The Prism-Net Search Space Representation for Multi-objective Building Spatial Design. In _Evolutionary Multi-Criterion Optimization: 12th International Conference, EMO 2023, Leiden, The Netherlands, March 20–24, 2023, Proceedings_. Springer, 476–489.
  * Preuss (2015) Mike Preuss. 2015\.  Groundwork for Niching.  In _Multimodal Optimization by Means of Evolutionary Algorithms_. Springer, 55–73.
  * Preuss et al. (2021) Mike Preuss, Michael Epitropakis, Xiaodong Li, and Jonathan E Fieldsend. 2021.  Multimodal Optimization: Formulation, Heuristics, and a Decade of Advances.  In _Metaheuristics for Finding Multiple Solutions_. Springer, 1–26.
  * Raidl and Gottlieb (2005) Günther R Raidl and Jens Gottlieb. 2005.  Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem.  _Evolutionary computation_ 13, 4 (2005), 441–475.
  * Raidl et al. (2006) Günther R Raidl, Gabriele Koller, and Bryant A Julstrom. 2006.  Biased mutation operators for subgraph-selection problems.  _IEEE Transactions on Evolutionary Computation_ 10, 2 (2006), 145–156.
  * Rajabi and Witt (2020) Amirhossein Rajabi and Carsten Witt. 2020.  Evolutionary algorithms with self-adjusting asymmetric mutation. In _Parallel Problem Solving from Nature–PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part I_. Springer, 664–677.
  * Rechenberg (1989) Ingo Rechenberg. 1989\.  Evolution strategy: Nature’s way of optimization. In _Optimization: Methods and Applications, Possibilities and Limitations: Proceedings of an International Seminar Organized by Deutsche Forschungsanstalt für Luft-und Raumfahrt (DLR), Bonn, June 1989_. Springer, 106–126.
  * Reehuis et al. (2013) Edgar Reehuis, Markus Olhofer, Bernhard Sendhoff, and Thomas Bäck. 2013.  Novelty-guided Restarts for Diverse Solutions in Optimization of Airfoils.  _A Bridge between Probability, Set-Oriented Numerics, and Evolutionary Computation, EVOLVE_ 2013 (2013).
  * Reehuis (2013) Edgar Julius Jeronimus Reehuis. 2013\.  _Guiding evolutionary search towards innovative solutions_.  Ph. D. Dissertation. Leiden University.
  * Reeves (2000) Colin R Reeves. 2000\.  Fitness landscapes and evolutionary algorithms. In _Artificial Evolution: 4th European Conference, AE’99, Dunkerque, France, November 3-5, 1999. Selected Papers 4_. Springer, 3–20.
  * Rothlauf and Rothlauf (2006) Franz Rothlauf and Franz Rothlauf. 2006.  _Representations for genetic and evolutionary algorithms_.  Springer.
  * Rozenberg et al. (2012) Grzegorz Rozenberg, Thomas Bäck, and Joost N Kok. 2012\.  _Handbook of natural computing_.  Springer.
  * Rudolph (2012) Günter Rudolph. 2012\.  _Evolutionary Strategies_.  Springer Berlin Heidelberg, Berlin, Heidelberg, 673–698.
  * Schumacher et al. (2001) Chris Schumacher, Michael D Vose, L Darrell Whitley, et al. 2001\.  The no free lunch and problem description length. In _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)_. 565–570.
  * Shir and Bäck (2009) Ofer M Shir and Thomas Bäck. 2009.  Niching with derandomized evolution strategies in artificial and real-world landscapes.  _Natural Computing_ 8 (2009), 171–196.
  * Slowik and Kwasnicka (2020) Adam Slowik and Halina Kwasnicka. 2020.  Evolutionary algorithms and their applications to engineering problems.  _Neural Computing and Applications_ 32 (2020), 12363–12379.
  * Solow and Polasky (1994) Andrew R Solow and Stephen Polasky. 1994.  Measuring biological diversity.  _Environmental and Ecological Statistics_ 1 (1994), 95–103.
  * Sudholt (2020) Dirk Sudholt. 2020\.  The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses.  _Theory of evolutionary computation: Recent developments in discrete optimization_ (2020), 359–404.
  * Tušar et al. (2019) Tea Tušar, Dimo Brockhoff, and Nikolaus Hansen. 2019\.  Mixed-integer benchmark problems for single-and bi-objective optimization. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 718–726.
  * Weise and Wu (2018) Thomas Weise and Zijun Wu. 2018.  Difficult features of combinatorial optimization problems and the tunable w-model benchmark problem for simulating them. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. 1769–1776.
  * Ye et al. (2021) Furong Ye, Carola Doerr, and Thomas Bäck. 2021.  Leveraging benchmarking data for informed one-shot dynamic algorithm selection. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. 245–246.
  * Yu et al. (2017) Eric A Yu, Jin Yeom, Cem C Tutum, Etienne Vouga, and Risto Miikkulainen. 2017.  Evolutionary decomposition for 3D printing. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 1272–1279.