Search

Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.

The non-dominated sorting genetic algorithm~II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II., Comment: To appear at AAAI 2025

Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces., Comment: To appear at AAAI 2025

The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. IEEE Transactions on Evolutionary Computation (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result. In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NGSA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.

The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function $f$, but instead optimizes $N + 1$ single-objective subproblems of $f$ in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the $g$-optima), it may still miss Pareto optima of $f$. The algorithm is then tasked to find the remaining Pareto optima directly by mutating the $g$-optima. In this work, we analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the $g$-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of $O(n N \log n + n^{n/(2N)} N \log n)$ function evaluations. Especially for the second, more interesting phase when the algorithm start with all $g$-optima, we prove an $\Omega(n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})$ expected runtime. This runtime is super-polynomial if $N = o(n)$, since this leaves large gaps between the $g$-optima, which require costly mutations to cover. For power-law mutation with exponent $\beta \in (1, 2)$, we prove an expected runtime of $O\left(n N \log n + n^{\beta} \log n\right)$ function evaluations. The $O\left(n^{\beta} \log n\right)$ term stems from the second phase of starting with all $g$-optima, and it is independent of the number of subproblems $N$. This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for $N = O(n^{\beta - 1})$, resulting in an $O(n^\beta \log n)$ bound. In contrast to standard bit mutation, smaller values of $N$ are better for power-law mutation, as it is capable of easily creating missing solutions.

The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized search heuristics, namely a biased random-key genetic algorithm (BRKGA) obtained from extensive parameter tuning, a max-min ant system (MMAS), and a MMAS using Q-learning with a graph convolutional network. We show that the BRKGA with two simple modifications and without the costly parameter tuning obtains significantly better results. Our first modification is to simply choose all parameters of the BRKGA in each iteration randomly from a power-law distribution. The resulting parameterless BRKGA is already competitive with the tuned BRKGA, as our experiments on the previously used benchmarks show. We then add a natural greedy heuristic, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms. Besides providing a superior algorithm for the TSS problem, this work shows that randomized parameter choices and elementary greedy heuristics can give better results than complex algorithms and costly parameter tuning.

We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using $k$-bit flip mutations. The algorithm adds successful mutation rates to an archive of promising rates that are favored in subsequent steps. Rates expire when their number of unsuccessful trials has exceeded a threshold, while rates currently not present in the archive can enter it in two ways: (i) via user-defined minimum selection probabilities for rates combined with a successful step or (ii) via a stagnation detection mechanism increasing the value for a promising rate after the current bit-flip neighborhood has been explored with high probability. For the minimum selection probabilities, we suggest different options, including heavy-tailed distributions. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning trees, and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.

Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erd\H{o}s-R\'enyi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.

Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient $\lambda$. We give the first fully rigorous results for thresholds of $\lambda$ at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.

Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. Estimation-of-distribution algorithms (EDAs) are an alternative, maintaining a probabilistic model of the solution space instead of a population. Such a model is able to implicitly represent a solution set far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EqualBlocksOneMax (EBOM). It has an easy fitness landscape with exponentially many optima. We show that the bivariate EDA mutual-information-maximizing input clustering, without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for EBOM, which samples each of the exponentially many optima with the same maximal probability. We also prove via mathematical means that no univariate model can come close to having this property: If the probability to sample an optimum is at least inverse-polynomial, there is a Hamming ball of logarithmic radius such that, with high probability, each sample is in this ball.

The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take $r$ different values, the time for genetic drift to become significant is $r$ times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen $r$ times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the $r$-valued \leadingones problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in $O(r\ln(r)^2 n^2 \ln(n))$ function evaluations. This bound is nearly tight as our lower bound $\Omega(r\ln(r) n^2 \ln(n))$ shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.

Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven with mathematical means. The most convincing such result shows that the $(\mu+1)$ genetic algorithm (GA) with population size $\mu=O(n)$ optimizes jump functions with gap size $k \ge 3$ in time $O(n^k / \mu + n^{k-1}\log n)$, beating the $\Theta(n^k)$ runtime of many mutation-based EAs. This result builds on a proof that the GA occasionally and then for an expected number of $\Omega(\mu^2)$ iterations has a population that is not dominated by a single genotype. In this work, we show that this diversity persist with high probability for a time exponential in $\mu$ (instead of quadratic). From this better understanding of the population diversity, we obtain stronger runtime guarantees, among them the statement that for all $c\ln(n)\le\mu \le n/\log n$, with $c$ a suitable constant, the runtime of the $(\mu+1)$ GA on $\mathrm{Jump}_k$, with $k \ge 3$, is $O(n^{k-1})$. Consequently, already with logarithmic population sizes, the GA gains a speed-up of order $\Omega(n)$ from crossover.

We study the SIRS process, a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate $\lambda$, and each recovered vertex becomes susceptible at a rate $\varrho$, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, rigorous theoretical results exist only for the related SIS model so far. We address this imbalance by conducting theoretical analyses of the SIRS process via their expansion properties. We prove that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of $\lambda$. This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs $G$ with $n$ vertices, degree close to $d$, and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in $n$ when $\lambda \geq c/d$ for a constant $c > 1$. Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if $G$ is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-R\'enyi graphs and a regime of exponential survival time for hyperbolic random graphs. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and applying a negative-drift theorem to show that the expected survival time is exponential.

Run time analysis of evolutionary algorithms recently makes significant progress in linking algorithm performance to algorithm parameters. However, settings that study the impact of problem parameters are rare. The recently proposed W-model provides a good framework for such analyses, generating pseudo-Boolean optimization problems with tunable properties. We initiate theoretical research of the W-model by studying how one of its properties -- neutrality -- influences the run time of random local search. Neutrality creates plateaus in the search space by first performing a majority vote for subsets of the solution candidate and then evaluating the smaller-dimensional string via a low-level fitness function. We prove upper bounds for the expected run time of random local search on this MAJORITY problem for its entire parameter spectrum. To this end, we provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY, where a sufficient majority is needed to optimize the subset. We also introduce a generalized version of classic drift theorems as well as a generalized version of Wald's equation, both of which we believe to be of independent interest.

It has long been observed that the performance of evolutionary algorithms and other randomized search heuristics can benefit from a non-static choice of the parameters that steer their optimization behavior. Mechanisms that identify suitable configurations on the fly ("parameter control") or via a dedicated training process ("dynamic algorithm configuration") are therefore an important component of modern evolutionary computation frameworks. Several approaches to address the dynamic parameter setting problem exist, but we barely understand which ones to prefer for which applications. As in classical benchmarking, problem collections with a known ground truth can offer very meaningful insights in this context. Unfortunately, settings with well-understood control policies are very rare. One of the few exceptions for which we know which parameter settings minimize the expected runtime is the LeadingOnes problem. We extend this benchmark by analyzing optimal control policies that can select the parameters only from a given portfolio of possible values. This also allows us to compute optimal parameter portfolios of a given size. We demonstrate the usefulness of our benchmarks by analyzing the behavior of the DDQN reinforcement learning approach for dynamic algorithm configuration.

We study algorithmic applications of a natural discretization for the hard-sphere model and the Widom-Rowlinson model in a region $\mathbb{V}\subset\mathbb{R}^d$. These models are used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles follow a Poisson point process with a type specific activity parameter (fugacity). The Gibbs distribution is characterized by the mixture of these point processes conditioned that no two particles are closer than a type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. We give sufficient conditions that the partition function of a discrete hard-core model on a geometric graph based on a point set $X \subset \mathbb{V}$ closely approximates those of such continuous models. Previously, this was only shown for the hard-sphere model on cubic regions $\mathbb{V}=[0, \ell)^d$ when $X$ is exponential in the volume of the region $\nu(\mathbb{V})$, limiting algorithmic applications. In the same setting, our refined analysis only requires a quadratic number of points, which we argue to be tight. We use our improved discretization results to approximate the partition functions of the hard-sphere model and the Widom-Rowlinson efficiently in $\nu(\mathbb{V})$. For the hard-sphere model, we obtain the first quasi-polynomial deterministic approximation algorithm for the entire fugacity regime for which, so far, only randomized approximations are known. Furthermore, we simplify a recently introduced fully polynomial randomized approximation algorithm. Similarly, we obtain the best known deterministic and randomized approximation bounds for the Widom-Rowlinson model. Moreover, we obtain approximate sampling algorithms for the respective spin systems within the same fugacity regimes.

Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We consider an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to changes their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge $\{u,v\}$ is monochrome, i.e., that both vertices $u$ and $v$ have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge $\{u,v\}$ makes a highly decisive common neighborhood for $u$ and $v$ more likely. Based on this, we prove the existence of a constant $c > 0$ such that the expected fraction of monochrome edges after the FSP is at least $1/2 + c$. (2) For Erd\"os-R\'enyi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most $1/2 + o(1)$. Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.

The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in $d$ dimensions. Up to a fugacity of $\lambda < \text{e}/2^d$, the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition---the clique dynamics condition---, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least $2^{1/\alpha}$ for the hard-core model on bipartite $\alpha$-expanders.

In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most $\lambda(\frac{n}{2} + 2 e \ln n)$ fitness evaluations. Since an offspring population size $\lambda$ of order $n \log n$ can prevent genetic drift, the UMDA can solve the DLB problem with $O(n^2 \log n)$ fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than $O(n^3)$ is known (which we prove to be tight for the ${(1+1)}$ EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than evolutionary algorithms; such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.

Estimation-of-distribution algorithms (EDAs) are general metaheuristics used in optimization that represent a more recent alternative to classical approaches like evolutionary algorithms. In a nutshell, EDAs typically do not directly evolve populations of search points but build probabilistic models of promising solutions by repeatedly sampling and selecting points from the underlying search space. Recently, there has been made significant progress in the theoretical understanding of EDAs. This article provides an up-to-date overview of the most commonly analyzed EDAs and the most recent theoretical results in this area. In particular, emphasis is put on the runtime analysis of simple univariate EDAs, including a description of typical benchmark functions and tools for the analysis. Along the way, open problems and directions for future research are described., Comment: This is a preliminary version of a chapter in the upcoming book "Theory of Randomized Search Heuristics in Discrete Search Spaces", edited by Benjamin Doerr and Frank Neumann, to be published by Springer

For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process -- the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift.

Drift theory is an intuitive tool for reasoning about random processes: It allows turning expected stepwise changes into expected first-hitting times. While drift theory is used extensively by the community studying randomized search heuristics, it has seen hardly any applications outside of this field, in spite of many research questions that can be formulated as first-hitting times. We state the most useful drift theorems and demonstrate their use for various randomized processes, including the coupon collector process, winning streaks, approximating vertex cover, and a random sorting algorithm. We also consider processes without expected stepwise change and give theorems based on drift theory applicable in such scenarios. We use these theorems for the analysis of the gambler's ruin process, for a coloring algorithm, for an algorithm for 2-SAT, and for a version of the Moran process without bias. A final tool we present is a tight theorem for processes on finite state spaces, which we apply to the Moran process. We aim to enable the reader to apply drift theory in their own research to derive accessible proofs and to teach it as a simple tool for the analysis of random processes.

Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the ($\mu$+1) GA and the $\text{Jump}_k$ test function. We show that the interplay of crossover and mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order $\Omega(n/\log n)$ compared to mutation-only algorithms like (1+1) EA. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to speedups of order $\Omega(n)$. We also compare seven commonly used diversity mechanisms and evaluate their impact on runtime bounds for the ($\mu$+1) GA. All previous results in this context only hold for unrealistically low crossover probability $p_c=O(k/n)$, while we give analyses for the setting of constant $p_c < 1$ in all but one case. For the typical case of constant $k > 2$ and constant $p_c$, we can compare the resulting expected runtimes for different diversity mechanisms assuming an optimal choice of $\mu$: $O(n^{k-1})$ for duplicate elimination/minim., $O(n^2\log n)$ for maximising the convex hull, $O(n\log n)$ for deterministic crowding (assuming $p_c = k/n$), $O(n\log n)$ for maximising Hamming distance, $O(n\log n)$ for fitness sharing, $O(n\log n)$ for single-receiver island model. This proves a sizeable advantage of all variants of the ($\mu$+1) GA compared to (1+1) EA, which requires time $\Theta(n^k)$. Experiments complement our theoretical findings and further highlight the benefits of crossover and diversity on $\text{Jump}_k$.