Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size mu >= n - 2k + 3 and offspring population size lambda computes the Pareto front of the OneJumpZeroJump benchmark with gap size k in an expected number of O((lambda+mu)n + n^(k+1)) function evaluations. This shows that the best runtime guarantee of O(n^(k+1)) is not only achieved for mu = Theta(n) and lambda = O(n) but for arbitrary mu, lambda = O(n^k). Thus, choosing suitable parameters - a key challenge in using heuristic algorithms - is much easier for the SPEA2 than the NSGA-II.

The MOEA/D is the most popular decomposition-based evolutionary algorithm to solve multi-objective optimization problems. However, among the two common decomposition approaches, weighted-sum and Tchebycheff, the existing theoretical research almost exclusively focus on the latter one. In this first complete mathematical runtime analysis for the MOEA/D using the original weighted-sum decomposition, we show that this variant of the algorithm solves the classic ONEMINMAX benchmark considerably faster than both the MOEA/D with Tchebycheff decomposition and many other classic algorithms such as the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2. More precisely, we show that already a logarithmic number of subproblems suffices for the algorithm to be efficient, and then typically O(n log^2 n) function evaluations suffice to compute the full Pareto front. This beats the other algorithms by a factor of Θ(n / log n). For a second benchmark, the ONEJUMPZEROJUMP problem, we show a speed-up by a factor of Θ(n). Overall, this work shows that a further development of the weighted-sum approach might be fruitful.

The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA)– another simple EDA–, the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LEADINGONES benchmark–one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LEADINGONES. For the cGA’s single parameter–called the hypothetical population size–at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LEADINGONES with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LEADINGONES. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.

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.

Estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the process. Building on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.

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), N n}) 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 = Θ(n), this result improves considerably over the Θ(N n^k) runtime of the classic NSGA-II.

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.

Recently it has been proven that simple GP systems can efficiently evolve a conjunction of n variables if they are equipped with the minimal required components. In this paper, we make a considerable step forward by analysing the behaviour and performance of a GP system for evolving a Boolean conjunction or disjunction of n variables using a complete function set that allows the expression of any Boolean function of up to n variables. First we rigorously prove that a GP system using the complete truth table to evaluate the program quality, and equipped with both the AND and OR operators and positive literals, evolves the exact target function in O(\ell n log^2 n) iterations in expectation, where\ell ≥ n is a limit on the size of any accepted tree. Additionally, we show that when a polynomial sample of possible inputs is used to evaluate the solution quality, conjunctions or disjunctions with any polynomially small generalisation error can be evolved with probability 1 − O(log^2(n)/n). The latter result also holds if GP uses AND, OR and positive and negated literals, thus has the power to express any Boolean function of n distinct variables. To prove our results we introduce a super-multiplicative drift theorem that gives significantly stronger runtime bounds when the expected progress is only slightly superlinear in the distance from the optimum.

Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of σ-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.

Randomized search heuristics (RSHs) are known to have a certain robustness to noise. Mathematical analyses trying to quantify rigorously how robust RSHs are to a noisy access to the objective function typically assume that each solution is re-evaluated whenever it is compared to others. This aims at preventing that a single noisy evaluation has a lasting negative effect, but is computationally expensive and requires the user to foresee that noise is present (as in a noise-free setting, one would never re-evaluate solutions). In this work, we conduct the first mathematical runtime analysis of an evolutionary algorithm solving a single-objective noisy problem without re-evaluations. We prove that the (1+1) evolutionary algorithm without re-evaluations can optimize the classic LeadingOnes benchmark with up to constant noise rates, in sharp contrast to the version with re-evaluations, where only noise with rates O(n⁻²log n) can be tolerated. This result suggests that re-evaluations are much less needed than what was previously thought, and that they actually can be highly detrimental. The insights from our mathematical proofs indicate that this similar results are plausible for other classic benchmarks.

The move-acceptance hyper-heuristic was recently shown to be able to leave local optima with astonishing efficiency (Lissovoi et al., Artificial Intelligence (2023)). In this work, we propose two modifications to this algorithm that demonstrate impressive performances on a large class of benchmarks including the classic CLIFF_d and JUMP_m function classes. (i) Instead of randomly choosing between the only-improving and any-move acceptance operator, we take this choice via a simple two-state Markov chain. This modification alone reduces the runtime on JUMP_m functions with gap parameter m from ?(n²ᵐ⁻¹) to O(nᵐ⁺¹). (ii) We then replace the all-moves acceptance operators with the operator that only accepts worsenings. Such a, counter-intuitive, operator has not been used before in the literature. However, our proofs show that our only-worsening operator can greatly help in leaving local optima, reducing, e.g., the runtime on Jump functions to O(n³ log n) independent of the gap size. In general, we prove a remarkably good runtime of O(nᵏ⁺¹ log n) for our Markov move-acceptance hyper-heuristic on all members of a new benchmark class SEQOPT_k, which contains a large number of functions having k successive local optima, and which contains the commonly studied JUMP_m and CLIFF_d functions for k=2.

This work conducts a first theoretical analysis studying how well the NSGA-III approximates the Pareto front when the population size N is less than the Pareto front size. We show that when N is at least the number Nr of reference points, then the approximation quality, measured by the maximum empty interval (MEI) indicator, on the OneMinMax benchmark is such that there is no empty interval longer than ⌈(5-2√2)n/(Nr-1)⌉. This bound is independent of N, which suggests that further increasing the population size does not increase the quality of approximation when Nr is fixed. This is a notable difference to the NSGA-II with sequential survival selection, where increasing the population size improves the quality of the approximations. We also prove two results indicating approximation difficulties when N

The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order Ω(n² log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n²), improving over the previous estimate of O(n² log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(n^(k+1)) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2,3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs.

Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, a stochastic selection mechanism was recently proposed for the SMS-EMOA and was proven to speed up computing the Pareto front of the bi-objective jump benchmark with problem size n and gap parameter k by a factor of max{1,2^(k/4)/n}. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for k ≥ 4log(n), where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of max{1,Θ(k)^(k-1)}, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant k, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.

Recent breakthroughs in the analysis of multi-objective evolutionary algorithms (MOEAs) are mathematical runtime analyses of those algorithms which are intensively used in practice. So far, most of these results show the same performance as previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how existing popular MOEAs approximate the Pareto front of the established LargeFront benchmark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of $O(n^2 \log n)$ fitness evaluations to compute an additive $\varepsilon$-approximation of the Pareto front of the LargeFront benchmark. This contrasts with the already proven exponential runtime (with high probability) of the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front.

In their recent work, Doerr and Krejca (IEEE Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search (RLS) heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius k on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter k on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.

Recent theoretical works have shown that the NSGA-II efficiently computes the full Pareto front when the population size is large enough. In this work, we study how well it approximates the Pareto front when the population size is smaller. For the ONEMINMAX benchmark, we point out situations in which the parents and offspring cover well the Pareto front, but the next population has large gaps on the Pareto front. Our mathematical proofs suggest as reason for this undesirable behavior that the NSGA-II in the selection stage computes the crowding distance once and then removes individuals with smallest crowding distance without considering that a removal increases the crowding distance of some individuals. We then analyze two variants not prone to this problem. For the NSGA-II that updates the crowding distance after each removal (Kukkonen and Deb (2006)) and the steady-state NSGAII (Nebro and Durillo (2009)), we prove that the gaps in the Pareto front are never more than a small constant factor larger than the theoretical minimum. This is the first mathematical work on the approximation ability of the NSGA-II and the first runtime analysis for the steady-state NSGA-II. Experiments also show the superior approximation ability of the two NSGA-II variants.

The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of an algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the \((1+1)\) evolutionary algorithm and the static, self-adjusting, and heavy-tailed \((1+(\lambda,\lambda))\) genetic algorithms on the OneMax benchmark. We are optimistic that the question of how to profit from good initial solutions is interesting beyond these first examples.

The widely used multiobjective optimizer NSGA-II was recently proven to have considerable difficulties in many-objective optimization. In contrast, experimental results in the literature show a good performance of the SMS-EMOA, which can be seen as a steady-state NSGA-II that uses the hypervolume contribution instead of the crowding distance as the second selection criterion. This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart, the m-objective mOJZJ problem, of the bi-objective OJZJ benchmark, which is the first many-objective multimodal benchmark used in a mathematical runtime analysis. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of O(M^2 n^k) iterations, where n denotes the problem size (length of the bit-string representation), k the gap size (a difficulty parameter of the problem), and M=(2n/m-2k+3)^(m/2) the size of the Pareto front. This result together with the existing negative result on the original NSGA-II shows that in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies. We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective OJZJ benchmark, the stochastic population update often does not help for mOJZJ. It results in a 1/Θ(min(Mk^(1/2)/2^(k/2),1)) speed-up, which is Θ(1) for large m such as m>k. On the positive side, we prove that heavy-tailed mutation still results in a speed-up of order k^(0.5+k-β). Finally, we conduct the first runtime analyses of the SMS-EMOA on the bi-objective OneMinMax and LOTZ benchmarks and show that it has a performance comparable to the GSEMO and the NSGA-II.

The Metropolis algorithm can cope with local optima by accepting inferior solutions with suitably small probability. That this can work well was not only observed in empirical research, but also via mathematical runtime analyses on single-objective benchmarks. This paper takes several steps towards understanding, again via theoretical means, whether such advantages can also be obtained in multi-objective optimization. The original Metropolis algorithm has two components, one-bit mutation and the acceptance strategy, which allows accepting inferior solutions. When adjusting the acceptance strategy to multi-objective optimization in the way that an inferior solution that is accepted replaces its parent, then the Metropolis algorithm is not very efficient on our multi-objective version of the multimodal DLB benchmark called DLTB. With one-bit mutation, this multi-objective Metropolis algorithm cannot optimize the DLTB problem, with standard bit-wise mutation it needs at least Ω(n^5) time to cover the full Pareto front. In contrast, we show that many other multi-objective optimizers, namely the GSEMO, SMS-EMOA, and NSGA-II, only need time O(n^4). When keeping the parent when an inferior point is accepted, the multi-objective Metropolis algorithm both with one-bit or standard bit-wise mutation solves the DLTB problem efficiently, with one-bit mutation experimentally leading to better results than several other algorithms. Overall, our work suggests that the general mechanism of the Metropolis algorithm can be interesting in multi-objective optimization, but that the implementation details can have a huge impact on the performance.

International audience

Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the (1 + λ) and (1, λ) evolutionary algorithms in the presence of prior bit-wise noise, we show that both algorithms can tolerate constant noise probabilities without increasing the asymptotic runtime on the OneMax benchmark. For this, a population size λ suffices that is at least logarithmic in the problem size n. The only previous result in this direction regarded the less realistic one-bit noise model, required a population size super-linear in the problem size, and proved a runtime guarantee roughly cubic in the noiseless runtime for the OneMax benchmark. Our significantly stronger results are based on the novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring. We are optimistic that the technical lemmas resulting from this insight will find applications also in future mathematical runtime analyses of evolutionary algorithms.

We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.

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.

Abstract Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem (parameter tuning) is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice (parameter control) is necessary. In this work, we propose a lazy but effective solution, namely choosing all parameter values (where this makes sense) in each iteration randomly from a suitably scaled power-law distribution. To demonstrate the effectiveness of this approach, we perform runtime analyses of the $$(1+(\lambda ,\lambda ))$$ ( 1 + ( λ , λ ) ) genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the $$(1+1)$$ ( 1 + 1 ) EA, giving the same asymptotic runtime on problems like OneMax, LeadingOnes, or Minimum Spanning Tree. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to the best performance known for static parameters. For the most interesting case that the jump size k is constant, we prove that our performance is asymptotically better than what can be obtained with any static parameter choice. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest.

International audience

One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters $\gamma_{i,j}$, $0 \le i < j \le n$. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on \textsc{LeadingOnes}. (ii) A lower bound for the run time of the (1+1) EA on \textsc{OneMax}, tight apart from an $O(n)$ term. (iii) A lower bound for the run time of the (1+1) EA on long $k$-paths. We also prove a tighter lower bound for the run time of the (1+1) EA on jump functions by showing that, regardless of the jump size, only with probability $O(2^{-n})$ the algorithm can avoid to jump over the valley of low fitness.

Abstract We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by $$n, m, w_{\max }$$ n , m , w max , and $$w_{\min }$$ w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature $$T_0 \ge w_{\max }$$ T 0 ≥ w max and multiplicative cooling schedule with factor $$1-1/\ell $$ 1 - 1 / ℓ , where $$\ell = \omega (mn\ln (m))$$ ℓ = ω ( m n ln ( m ) ) , with probability at least $$1-1/m$$ 1 - 1 / m computes in time $$O(\ell (\ln \ln (\ell ) + \ln (T_0/w_{\min }) ))$$ O ( ℓ ( ln ln ( ℓ ) + ln ( T 0 / w min ) ) ) a spanning tree with weight at most $$1+\kappa $$ 1 + κ times the optimum weight, where $$1+\kappa = \frac{(1+o(1))\ln (\ell m)}{\ln (\ell ) -\ln (mn\ln (m))}$$ 1 + κ = ( 1 + o ( 1 ) ) ln ( ℓ m ) ln ( ℓ ) - ln ( m n ln ( m ) ) . Consequently, for any $$\epsilon >0$$ ϵ > 0 , we can choose $$\ell $$ ℓ in such a way that a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation is found in time $$O((mn\ln (n))^{1+1/\epsilon +o(1)}(\ln \ln n + \ln (T_0/w_{\min })))$$ O ( ( m n ln ( n ) ) 1 + 1 / ϵ + o (

Choosing a suitable algorithm from the myriads of different search heuristics is difficult when faced with a novel optimization problem. In this work, we argue that the purely academic question of what could be the best possible algorithm in a certain broad class of black-box optimizers can give fruitful indications in which direction to search for good established optimization heuristics. We demonstrate this approach on the recently proposed DLB benchmark, for which the only known results are O(n3) runtimes for several classic evolutionary algorithms and an O(n2log⁡n) runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only O(n2) suggests the Metropolis algorithm as an interesting candidate and we prove that it solves the DLB problem in quadratic time. Since we also prove that better runtimes cannot be obtained in the class of unary unbiased algorithms, we shift our attention to algorithms that use the information of more parents to generate new solutions. An artificial algorithm of this type having an O(nlog⁡n) runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time O(nlog⁡n) with high probability. Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes.

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 naïve 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, categorical 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(rln⁡(r)2n2ln⁡(n)) function evaluations. This bound is nearly tight as our lower bound Ω(rln⁡(r)n2ln⁡(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.

The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple m-objective generalization of the discrete OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in sub-exponential time when the number of objectives is at least three. The reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pair-wise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).

Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the (mu+1) genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee.

Due to the more complicated population dynamics of the NSGA-II, none of the existing runtime guarantees for this algorithm is accompanied by a non-trivial lower bound. Via a first mathematical understanding of the population dynamics of the NSGA-II, that is, by estimating the expected number of individuals having a certain objective value, we prove that the NSGA-II with suitable population size needs Omega(Nn log n) function evaluations to find the Pareto front of the OneMinMax problem and Omega(Nn^k) evaluations on the OneJumpZeroJump problem with jump size k. These bounds are asymptotically tight (that is, they match previously shown upper bounds) and show that the NSGA-II here does not even in terms of the parallel runtime (number of iterations) profit from larger population sizes. For the OneJumpZeroJump problem and when the same sorting is used for the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.

In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local optimum of the multimodal cliff benchmark with remarkable efficiency. With its O (n3) runtime, for almost all cliff widths d, the MAHH massively outperforms the Θ(nd) runtime of simple elitist evolutionary algorithms (EAs). For the most prominent multimodal benchmark, the jump functions, the given runtime estimates of O(n2mm-Θ(m)) and Ω(2Ω(m)), for gap size m ≥ 2, are far apart and the real performance of MAHH is still an open question.

The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this ability, we conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart from one local optimum, cliff functions are monotonically increasing towards the global optimum. Consequently, to optimize a cliff function, the MA only once needs to accept an inferior solution. Despite seemingly being an ideal benchmark for the MA to profit from its main working principle, our mathematical runtime analysis shows that this hope does not come true. Even with the optimal temperature (the only parameter of the MA), the MA optimizes most cliff functions less efficiently than simple elitist evolutionary algorithms (EAs), which can only leave the local optimum by generating a superior solution possibly far away. This result suggests that our understanding of why the MA is often very successful in practice is not yet complete. Our work also suggests to equip the MA with global mutation operators, an idea supported by our preliminary experiments.

We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the (1 + 1) evolutionary algorithm on the Needle problem due to Garnier, Kallel, and Schoenauer (1999).

Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. In particular, larger offspring population sizes often lead to strong robustness. We analyze to what extent the (1 + (Λ, Λ)) genetic algorithm is robust to noise. This algorithm also works with larger offspring population sizes, but an intermediate selection step and a non-standard use of crossover as repair mechanism could render this algorithm less robust than, e.g., the simple (1 + Λ) evolutionary algorithm. Our experimental analysis on several classic benchmark problems shows that this difficulty does not arise. Surprisingly, in many situations this algorithm is even more robust to noise than the (1 + Λ) EA.

With apparently all research on estimation-of-distribution algorithms (EDAs) concentrated on pseudo-Boolean optimization and permutation problems, we undertake the first steps towards using EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems. To this aim, we propose a natural way to extend the known univariate EDAs to such variables. Different from a naïve reduction to the binary case, it avoids additional constraints.

The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. Recently, the first mathematical runtime guarantees have been obtained for this algorithm, however only for synthetic benchmark problems. In this work, we give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem. More specifically, we show that the NSGA-II with population size N >= 4((n-1) wmax + 1) computes all extremal points of the Pareto front in an expected number of O(m^2 n wmax log(n wmax)) iterations, where n is the number of vertices, m the number of edges, and wmax is the maximum edge weight in the problem instance. This result confirms, via mathematical means, the good performance of the NSGA-II observed empirically. It also shows that mathematical analyses of this algorithm are not only possible for synthetic benchmark problems, but also for more complex combinatorial optimization problems. As a side result, we also obtain a new analysis of the performance of the global SEMO algorithm on the bi-objective minimum spanning tree problem, which improves the previous best result by a factor of |F|, the number of extremal points of the Pareto front, a set that can be as large as n wmax. The main reason for this improvement is our observation that both multi-objective evolutionary algorithms find the different extremal points in parallel rather than sequentially, as assumed in the previous proofs.

In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can stand a certain amount of noise in the evaluation of the objective function. In contrast, this question is not at all understood for multi-objective optimization. In this work, we conduct the first mathematical runtime analysis of a simple multi-objective evolutionary algorithm (MOEA) on a classic benchmark in the presence of noise in the objective function. We prove that when bit-wise prior noise with rate p <= alpha/n, alpha a suitable constant, is present, the simple evolutionary multi-objective optimizer (SEMO) without any adjustments to cope with noise finds the Pareto front of the OneMinMax benchmark in time O(n^2 log n), just as in the case without noise. Given that the problem here is to arrive at a population consisting of n+1 individuals witnessing the Pareto front, this is a surprisingly strong robustness to noise (comparably simple evolutionary algorithms cannot optimize the single-objective OneMax problem in polynomial time when p = omega(log(n)/n)). Our proofs suggest that the strong robustness of the MOEA stems from its implicit diversity mechanism designed to enable it to compute a population covering the whole Pareto front. Interestingly this result only holds when the objective value of a solution is determined only once and the algorithm from that point on works with this, possibly noisy, objective value. We prove that when all solutions are reevaluated in each iteration, then any noise rate p = omega(log(n)/n^2) leads to a super-polynomial runtime. This is very different from single-objective optimization, where it is generally preferred to reevaluate solutions whenever their fitness is important and where examples are known such that not reevaluating solutions can lead to catastrophic performance losses.

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that it is less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving the NGSA-II for an exponential number of iterations misses a constant factor of the Pareto front of the simple 3-objective OneMinMax problem. In this work, we provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives. We prove that the NSGA-III with sufficiently many reference points - a small constant factor more than the size of the Pareto front, as suggested for this algorithm - computes the complete Pareto front of the 3-objective OneMinMax benchmark in an expected number of O(n log n) iterations. This result holds for all population sizes (that are at least the size of the Pareto front). It shows a drastic advantage of the NSGA-III over the NSGA-II on this benchmark. The mathematical arguments used here and in the previous work on the NSGA-II suggest that similar findings are likely for other benchmarks with three or more objectives.

The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size four times larger than the size of the Pareto front, the NSGA-II with two classic mutation operators and four different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LeadingOnesTrailingZeroes benchmarks. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front: for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front. Our experiments confirm the above findings.

Multiobjective evolutionary algorithms are successfully applied in many real-world multiobjective optimization problems. As for many other AI methods, the theoretical understanding of these algorithms is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal objectives. As a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OneJumpZeroJump problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that the simple evolutionary multiobjective optimizer (SEMO) with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes n and all jump sizes k∈[4..n2-1], the global SEMO (GSEMO) covers the Pareto front in an expected number of Θ((n-2k)nk) iterations. For k=o(n), we also show the tighter bound 32enk+1±o(nk+1), which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least kΩ(k). When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least kΩ(k) and surpasses the heavy-tailed GSEMO by a small polynomial factor in k. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-5 speed-up from heavy-tailed mutation and a factor-10 speed-up from stagnation detection can be observed already for jump size 4 and problem sizes between 10 and 50. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorithms to cope with local optima can be effectively employed also in multiobjective optimization.

Estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the process. Building on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.

Two mechanisms have recently been proposed that can significantly speed up finding distant improving solutions via mutation, namely using a random mutation rate drawn from a heavy-tailed distribution (“fast mutation”, Doerr et al. (2017) [2]) and increasing the mutation strength based on a stagnation detection mechanism (Rajabi and Witt (2020) [3]). Whereas the latter can obtain the asymptotically best probability of finding a single desired solution in a given distance, the former is more robust and performs much better when many improving solutions in some distance exist. In this work, we propose a mutation strategy that combines ideas of both mechanisms. We show that it can also obtain the best possible probability of finding a single distant solution. However, when several improving solutions exist, it can outperform both the stagnation-detection approach and fast mutation. The new operator is more than an interleaving of the two previous mechanisms and it outperforms any such interleaving.

Very recently, the first mathematical runtime analyses of the multiobjective evolutionary optimizer nondominated sorting genetic algorithm II (NSGA-II) have been conducted. We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of multimodal objectives. We prove that if the population size$N$is at least four times the size of the Pareto front, then the NSGA-II with four standard ways to select parents, bitwise mutation, and crossover with rate less than one, optimizes the OneJumpZeroJump benchmark with jump size$2 \le k \le n/4$in time$O(N n^{k})$. When using fast mutation instead of bitwise mutation this guarantee improves by a factor of$k^{\Omega (k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.

The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size larger than the Pareto front size by a constant factor, the NSGA-II with two classic mutation operators and three different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LOTZ benchmark functions. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front (for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front). Our experiments confirm the above findings.

A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a variant of the NSGA-II algorithm can efficiently compute the full Pareto front of the OneMinMax problem when the population size is by a constant factor larger than the Pareto front, but that this is not possible when the population size is only equal to the Pareto front size. In this work, we analyze how well the NSGA-II with small population size approximates the Pareto front of One-MinMax. We observe experimentally and by mathematical means that already when the population size is half the Pareto front size, relatively large gaps in the Pareto front remain. The reason for this phenomenon is that the NSGA-II in the selection stage computes the crowding distance once and then repeatedly removes individuals with smallest crowding distance without updating the crowding distance after each removal. We propose an eficient way to implement the NSGA-II using the current crowding distance. In our experiments, this algorithm approximates the Pareto front much better than the previous version. We also prove that the gaps in the Pareto front are at most a constant factor larger than the theoretical minimum.

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems.

The (1 + (λ, λ)) genetic algorithm is a recently proposed single-objective evolutionary algorithm with several interesting properties. We show that its main working principle, mutation with a high rate and crossover as repair mechanism, can be transported also to multi-objective evolutionary computation. We define the (1 + (λ, λ)) global SEMO algorithm, a variant of the classic global SEMO algorithm, and prove that it optimizes the OneMinMax benchmark asymptotically faster than the global SEMO. Following the single-objective example, we design a one-fifth rule inspired dynamic parameter setting (to the best of our knowledge for the first time in discrete multi-objective optimization) and prove that it further improves the runtime to O(n2), whereas the best runtime guarantee for the global SEMO is only O(n2 log n).

The configuration of radar networks is a complex problem that is often performed manually by experts with the help of a simulator. Different numbers and types of radars as well as different locations that the radars shall cover give rise to different instances of the radar configuration problem. The exact modeling of these instances is complex, as the quality of the configurations depends on a large number of parameters, on internal radar processing, and on the terrains on which the radars need to be placed. Classic optimization algorithms can therefore not be applied to this problem, and we rely on "trial-and-error" black-box approaches.

Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal multi-objective problems. We propose the OneJumpZeroJump problem, a bi-objective problem whose single objectives are isomorphic to the classic jump functions benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. In contrast, for all problem sizes n and all jump sizes k in [4..n/2-1], the global SEMO (GSEMO) covers the Pareto front in Θ((n-2k)n^k) iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Runtime improvements of asymptotic order at least k^Ω(k) are shown for both strategies. Our experiments verify the substantial runtime gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization.

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice is necessary.

Jump functions are the most studied non-unimodal benchmark in the theory of evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs escape from local optima. However, their particular structure - to leave the local optimum the EA can only jump directly to the global optimum - raises the question of how representative the recent findings are.

Ant colony optimizers have been successfully used as general-purpose optimization heuristics. Due to the complicated nature of the random processes that describe the runs of ACO algorithms, the mathematical understanding of these algorithms is much less developed than that of other nature-inspired heuristics. In this first runtime analysis of a basic ACO algorithm on a classic multimodal benchmark, we analyze the runtime of the 2-MMASib on jump functions. For moderate jump sizes k ≤ α0 ln n, α0 > 0 a constant, we prove a runtime of order O(√n/ρ), when the evaporation factor ρ satisfies ρ ≤ Cn-1/2 ln(n)-1 for a sufficiently small constant C. For ρ = Θ(n-1/2 ln(n)-1), we thus obtain a runtime of O(n ln(n)). This result shows that simple ACO algorithms can cope much better with local optima than many evolutionary algorithms, which need Ω(nk) time.

One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters γi,j, 0 ≤ i ≤ j ≤ n.

Choosing a suitable algorithm from the myriads of different search heuristics is difficult when faced with a novel optimization problem. In this work, we argue that the purely academic question of what could be the best possible algorithm in a certain broad class of black-box optimizers can give fruitful indications in which direction to search for good established optimization heuristics. We demonstrate this approach on the recently proposed DLB benchmark, for which the only known results are O(n^3) runtimes for several classic evolutionary algorithms and an O(n^2 log n) runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only O(n^2) suggests the Metropolis algorithm as an interesting candidate and we prove that it solves the DLB problem in quadratic time. Since we also prove that better runtimes cannot be obtained in the class of unary unbiased algorithms, we shift our attention to algorithms that use the information of more parents to generate new solutions. An artificial algorithm of this type having an O(n log n) runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time O(n log n). Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes.

The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength F and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on Leading Ones depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths $$F=1+o(1)$$ and success rate 1/e. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.

Abstract Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a $$(1+\delta )$$ ( 1 + δ ) -multiplicative growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a simple and insightful proof of the level-based theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the best-possible near-linear dependence on $$1/\delta$$ 1 / δ (the previous results had an at least near-quadratic dependence), and it only requires a population size near-linear in $$\delta$$ δ (this was super-quadratic in previous results). These improvements immediately lead to stronger run time guarantees for a number of applications. We also discuss the case of large $$\delta$$ δ and show stronger results for this setting.

A decent number of lower bounds for non-elitist population-based evolutionary algorithms has been shown by now. Most of them are technically demanding due to the (hard to avoid) use of negative drift theorems-general results which translate an expected movement away from the target into a high hitting time. We propose a simple negative drift theorem for multiplicative drift scenarios and show that it can simplify existing analyses. We discuss in more detail Lehre's (2010) negative drift in populations method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms for discrete search spaces. Together with other arguments, we obtain an alternative and simpler proof of this result, which also strengthens and simplifies this method. In particular, now only three of the five technical conditions of the previous result have to be verified. The lower bounds we obtain are explicit instead of only asymptotic. This allows us to compute concrete lower bounds for concrete algorithms, but also enables us to show that super-polynomial runtimes appear already when the reproduction rate is only a (1-ω(n-1/2)) factor below the threshold. For the special case of algorithms using standard bit mutation with a random mutation rate (called uniform mixing in the language of hyper-heuristics), we prove the result stated by Dang and Lehre (2016b) and extend it to mutation rates other than Θ(1/n), which includes the heavy-tailed mutation operator proposed by Doerr et al. (2017). We finally use our method and a novel domination argument to show an exponential lower bound for the runtime of the mutation-only simple genetic algorithm on OneMax for arbitrary population size.

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n -dimensional Plateau k function as natural benchmark and analyze how different variants of the (1 + 1) EA optimize it. The Plateau k function has a plateau of second-best fitness in a ball of radius k around the optimum. As evolutionary algorithm, we regard the (1 + 1) EA using an arbitrary unbiased mutation operator. Denoting by α the random number of bits flipped in an application of this operator and assuming that Pr [α = 1] has at least some small sub-constant value, we show the surprising result that for all constant k ≥ 2, the runtime T follows a distribution close to the geometric one with success probability equal to the probability to flip between 1 and k bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between 1 and k bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately k/(en) . Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.

The theory of evolutionary computation for discrete search spaces has made significant progress since the early 2010s. This survey summarizes some of the most important recent results in this research area. It discusses fine-grained models of runtime analysis of evolutionary algorithms, highlights recent theoretical insights on parameter tuning and parameter control, and summarizes the latest advances for stochastic and dynamic problems. We regard how evolutionary algorithms optimize submodular functions, and we give an overview over the large body of recent results on estimation of distribution algorithms. Finally, we present the state of the art of drift analysis, one of the most powerful analysis technique developed in this field.

Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

In their recent work, Lehre and Nguyen (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 the 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 λ(n2+2elnn) fitness evaluations. Since an offspring population size λ of order nlogn can prevent genetic drift, the UMDA can solve the DLB problem with O(n2logn) fitness evaluations. In contrast, for classic evolutionary algorithms no better runtime guarantee than O(n3) 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 many classic 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.

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives.

For the (1 + (λ, λ)) genetic algorithm rigorous runtime analyses on unimodal fitness functions have shown that it can be faster than classical evolutionary algorithms, though on these simple problems the gains are only moderate.

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and a theoretical viewpoint, more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis.

One hope of using non-elitism in evolutionary computation is that it aids leaving local optima. We perform a rigorous runtime analysis of a basic non-elitist evolutionary algorithm (EA), the (μ, λ) EA, on the most basic benchmark function with a local optimum, the jump function. We prove that for all reasonable values of the parameters and the problem, the expected runtime of the (μ, λ) EA is, apart from lower order terms, at least as large as the expected runtime of its elitist counterpart, the (μ + λ) EA (for which we conduct the first runtime analysis to allow this comparison). Consequently, the ability of the (μ, λ) EA to leave local optima to inferior solutions does not lead to a runtime advantage.

Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms (EAs) 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.

One of the key difficulties in using estimation-of-distribution algorithms is choosing the population sizes appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime with no genetic drift, however, often the runtime is roughly proportional to the population size, which renders large population sizes inefficient.

Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based cGA (sig-cGA) optimizes the commonly regarded benchmark functions OneMax (OM), LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed stable compact genetic algorithm - an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model - we prove that it optimizes OM only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OM in polynomial time.

Estimation of distribution algorithms (EDAs) are a successful branch of evolutionary algorithms (EAs) that evolve a probabilistic model instead of a population. Analogous to genetic drift in EAs, EDAs also encounter the phenomenon that the random sampling in the model update can move the sampling frequencies to boundary values not justified by the fitness. This can result in a considerable performance loss. This article gives the first tight quantification of this effect for three EDAs and one ant colony optimizer, namely, for the univariate marginal distribution algorithm, the compact genetic algorithm, population-based incremental learning, and the max-min ant system with iteration-best update. Our results allow to choose the parameters of these algorithms in such a way that within a desired runtime, no sampling frequency approaches the boundary values without a clear indication from the objective function.

The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group 1) without revealing who was the origin of this information and 2) without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al. gave a 2-round protocol enabling the two players to succeed with probability 1/3 and showed the hardness result that no protocol can give a success probability of more than 3/8. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability of better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to 0.3384, that is, give a protocol leading to this success probability. Unfortunately, already our smallest protocol beating the previous 1/3 success probability takes up 16 rounds of communication. The protocol leading to the bound of 0.3384 even in a compact representation consists of 18248 game states. These numbers suggest that the task of finding good protocols for the cryptogenography problem as well as understanding their structure is harder than what the simple problem formulation suggests.

We conduct a rigorous runtime analysis of the (1 + (λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n2/λ) iterations and Θ(n2) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n2) fitness evaluations still holds.

In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multimodal jump function class, Hasenöhrl and Sutton (GECCO 2018) proved that the runtime of the compact genetic algorithm with suitable parameter choice on jump functions with high probability is at most polynomial (in the dimension) if the jump size is at most logarithmic (in the dimension), and is at most exponential in the jump size if the jump size is super-logarithmic. The exponential runtime guarantee was achieved with a hypothetical population size that is also exponential in the jump size. Consequently, this setting cannot lead to a better runtime.

Understanding when evolutionary algorithms are efficient or not, and how they efficiently solve problems, is one of the central research tasks in evolutionary computation. In this work, we make progress in understanding the interplay between parent and offspring population size of the (µ, λ) EA. Previous works, roughly speaking, indicate that for λ ≥ (1 + ε)eµ, this EA easily optimizes the OneMax function, whereas an offspring population size λ ≤ (1 - ε)eµ leads to an exponential runtime.

We prove that the compact genetic algorithm (cGA) with hypothetical population size $\mu = \Omega(\sqrt n \log n) \cap \text{poly}(n)$ with high probability finds the optimum of any $n$-dimensional jump function with jump size $k < \frac 1 {20} \ln n$ in $O(\mu \sqrt n)$ iterations. Since it is known that the cGA with high probability needs at least $\Omega(\mu \sqrt n + n \log n)$ iterations to optimize the unimodal OneMax function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. Our runtime guarantee improves over the recent upper bound $O(\mu n^{1.5} \log n)$ valid for $\mu = \Omega(n^{3.5+\varepsilon})$ of Hasen\"ohrl and Sutton (GECCO 2018). For the best choice of the hypothetical population size, this result gives a runtime guarantee of $O(n^{5+\varepsilon})$, whereas ours gives $O(n \log n)$. We also provide a simple general method based on parallel runs that, under mild conditions, (i)~overcomes the need to specify a suitable population size, but gives a performance close to the one stemming from the best-possible population size, and (ii)~transforms EDAs with high-probability performance guarantees into EDAs with similar bounds on the expected runtime.

When a problem instance is perturbed by a small modification, one would hope to find a good solution for the new instance by building on a known good solution for the previous one. Via a rigorous mathematical analysis, we show that evolutionary algorithms, despite usually being robust problem solvers, can have unexpected difficulties to solve such re-optimization problems. When started with a random Hamming neighbor of the optimum, the (1+1) evolutionary algorithm takes Ω(n2) time to optimize the LeadingOnes benchmark function, which is the same asymptotic optimization time when started in a randomly chosen solution. There is hence no significant advantage from re-optimizing a structurally good solution.

Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target.

Recently it has been proved that simple GP systems can efficiently evolve the conjunction of n variables if they are equipped with the minimal required components. In this paper, we make a considerable step forward by analysing the behaviour and performance of a GP system for evolving a Boolean function with unknown components, i.e. the target function may consist of both conjunctions and disjunctions. We rigorously prove that if the target function is the conjunction of n variables, then a GP system using the complete truth table to evaluate program quality evolves the exact target function in O(ℓ n log2 n) iterations in expectation, where ℓ ≥ n is a limit on the size of any accepted tree. Additionally, we show that when a polynomial sample of possible inputs is used to evaluate solution quality, conjunctions with any polynomially small generalisation error can be evolved with probability 1 - O(log2(n)/n). To produce our results we introduce a super-multiplicative drift theorem that gives significantly stronger runtime bounds when the expected progress is only slightly super-linear in the distance from the optimum.

Due to their randomized nature, many nature-inspired heuristics are robust to some level of noise in the fitness evaluations. A common strategy to increase the tolerance to noise is to re-evaluate the fitness of a solution candidate several times and to then work with the average of the sampled fitness values. In this work, we propose to use the median instead of the mean. Besides being invariant to rescalings of the fitness, the median in many situations turns out to be much more robust than the mean. We show that when the noisy fitness is ϵ-concentrated, then a logarithmic number of samples suffice to discover the undisturbed fitness (via the median of the samples) with high probability. This gives a simple metaheuristic approach to transform a randomized optimization heuristics into one that is robust to this type of noise and that has a runtime higher than the original one only by a logarithmic factor. We show further that ϵ-concentrated noise occurs frequently in standard situations. We also provide lower bounds showing that in two such situations, even with larger numbers of samples, the average-resample strategy cannot efficiently optimize the problem in polynomial time.

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of true population-based evolutionary algorithms remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (μ + λ) evolutionary algorithm on the simple OneMax benchmark function, only the special cases μ = 1 and λ = 1 have been solved.

Evolutionary algorithms, being problem-independent and randomized heuristics, are generally believed to be robust to dynamic changes and noisy access to the problem instance. We propose a new method to obtain rigorous runtime results for such settings. In contrast to many previous works, our new approach mostly relies on general parameters of the dynamics or the noise models, such as the expected change of the dynamic optimum or the probability to have a dynamic change in one iteration. Consequently, we obtain bounds which are valid for large varieties of such models. Despite this generality, for almost all particular models regarded in the past our bounds are stronger than those given in previous works. As one particular result, we prove that the (1 + λ) EA can optimize the OneMax benchmark function efficiently despite a constant rate of 1-bit flip noise. For this, a logarithmic size offspring population suffices (the previous-best result required a super-linear value of λ). Our results suggest that the typical way to find the optimum in such adverse settings is not via a steady approach of the optimum, but rather via an exceptionally fast approach after waiting for a rare phase of low dynamic changes or noise.

Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses.

Selection hyper-heuristics are randomised optimisation techniques that select from a set of low-level heuristics which one should be applied in the next step of the optimisation process. Recently it has been proven that a Random Gradient hyper-heuristic optimises the LeadingOnes benchmark function in the best runtime achievable with any combination of its low-level heuristics, up to lower order terms. To achieve this runtime, the learning period τ, used to evaluate the performance of the currently chosen heuristic, should be set appropriately, i.e., super-linear in the problem size but not excessively larger. In this paper we automate the hyper-heuristic further by allowing it to self-adjust the learning period τ during the run. To achieve this we equip the algorithm with a simple self-adjusting mechanism, called 1 - o(1) rule, inspired by the 1/5 rule traditionally used in continuous optimisation. We rigorously prove that the resulting hyper-heuristic solves LeadingOnes in optimal runtime by automatically adapting τ and achieving a 1 - o(1) ratio of the desired behaviour. Complementary experiments for realistic problem sizes show the value of τ adapting as desired and that the hyper-heuristic with adaptive learning period outperforms the hyper-heuristic with fixed learning periods.

We propose and analyze a self-adaptive version of the (1, λ) evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O(nλ/log λ + n log n). This time is asymptotically smaller than the optimization time of the classic (1, λ) EA and (1 + λ) EA for all static mutation rates and best possible among all λ-parallel mutation-based unbiased black-box algorithms.

We conduct a first fundamental analysis of the working principles of binary differential evolution (BDE), an optimization heuristic for binary decision variables that was derived by Gong and Tuson (2007) from the very successful classic differential evolution (DE) for continuous optimization. We show that unlike most other optimization paradigms, it is stable in the sense that neutral bit values are sampled with probability close to 1/2. This is generally a desirable property, however, it makes it harder to find the optima for decision variables with small influence on the objective function. This can result in an optimization time exponential in the dimension when optimizing simple symmetric functions like OneMax. On the positive side, BDE quickly detects and optimizes the most important decision variables. For example, dominant bits converge to the optimal value in time logarithmic in the population size. This leads to a very good performance in the situation where the decision variables have a differently strong influence on the result, in particular, when the target is not to find the optimal solution, but only a good one. Overall, our results indicate that BDE is an interesting optimization paradigm having characteristics significantly different from the classic evolutionary algorithms or EDAs.

The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on some optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation.

We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length N, but only n ≪ N of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the (1 + 1) evolutionary algorithm (EA) have been developed that solve, for arbitrary s ∈ ℕ, such OneMax and LeadingOnes instances, simultaneously for all n ∈ ℕ, in expected time O(n(log(n))2 log log(n) ... log(s−1)(n)(log(s)(n))1+ε) and O(n2 log(n) log log(n) ... log(s−1)(n)(log(s)(n))1+ε), respectively; that is, in almost the same time as if n and the relevant bit positions were known.

Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort.

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring.

While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat.

For genetic algorithms (GAs) using a bit-string representation of length n, the general recommendation is to take 1/n as mutation rate. In this work, we discuss whether this is justified for multi-modal functions. Taking jump functions and the (1+1) evolutionary algorithm (EA) as the simplest example, we observe that larger mutation rates give significantly better runtimes. For the Jumpm, n function, any mutation rate between 2/n and m/n leads to a speedup at least exponential in m compared to the standard choice.

We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a G(n,p) random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(-Omega(r)). We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Theta(n*log(log(n))) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Theta(n*log(n)). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the $\Theta(n*log(log(n))) message complexity.

The (1+(λ,λ)) genetic algorithm is one of the few algorithms for which a super-constant speed-up through the use of crossover could be proven. So far, this algorithm has been used with parameters based also on intuitive considerations. In this work, we rigorously regard the whole parameter space and show that the asymptotic time complexity on the OneMax test function class proven by Doerr and Doerr (GECCO 2015) for the intuitive choice is best possible among all settings for population size, mutation probability, and crossover bias. Our proofs also give some advice on how to choose the parameters for other optimization problems.

The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over Ω = {0, 1, ..., r-1}n. More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector z ∈ Ω. For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of Θ(nr log n). If we change each selected position by either +1 or -1 (random choice), the optimization time reduces to Θ(nr + n log n). If we use a random mutation strength i ∈ {0,1,...,r-1}n with probability inversely proportional to i and change the selected position by either +i or -i (random choice), then the optimization time becomes Θ(n log(r)(log(n)+log(r))), bringing down the dependence on $r$ from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.

In classical runtime analysis it has been observed that certain working principles of an evolutionary algorithm cannot be understood by only looking at the asymptotic order of the runtime, but that more precise estimates are needed. In this work we demonstrate that the same observation applies to black-box complexity analysis. We prove that the unary unbiased black-box complexity of the classic OneMax function class is n ln(n) -- cn ± o(n) for a constant c between 0.2539 and 0.2665. Our analysis yields a simple (1+1)-type algorithm achieving this runtime bound via a fitness-dependent mutation strength. When translated into a fixed-budget perspective, our algorithm with the same budget computes a solution that asymptotically is 13% closer to the optimum (given that the budget is at least 0.2675n).

Diversity mechanisms are key to the working behaviour of evolutionary multi-objective algorithms. With this paper, we contribute to the theoretical understanding of such mechanisms by means of rigorous runtime analysis. We consider the OneMinMax problem for which it has been shown in [11] that a standard benchmark algorithm called SIBEA is not able to obtain a population with optimal hypervolume distribution in expected polynomial time if the population size is relatively small. We investigate the same setting as in [11] and show that SIBEA is able to achieve a good approximation of the optimal hypervolume distribution very efficiently. Furthermore, we study OneMinMax in the context of search-based diversity optimization and examine the time until SIBEA with a search-based diversity mechanism has obtained a population of maximal diversity covering the whole Pareto front.

We analyze the unrestricted black-box complexity of the Jump function classes for different jump sizes. For upper bounds, we present three algorithms for small, medium, and extreme jump sizes. We prove a matrix lower bound theorem which is capable of giving better lower bounds than the classic information theory approach. Using this theorem, we prove lower bounds that almost match the upper bounds. For the case of extreme jump functions, which apart from the optimum reveal only the middle fitness value(s), we use an additional lower bound argument to show that any black-box algorithm does not gain significant insight about the problem instance from the first [Formula: see text] fitness evaluations. This, together with our upper bound, shows that the black-box complexity of extreme jump functions is [Formula: see text].

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n 1 − ε , ε > 0 a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n , our results imply that Codebreaker can find the secret code with O ( n log log n ) guesses. This bound is valid also when only black answer pegs are used. It improves the O ( n log n ) bound first proven by Chvátal. We also show that if both black and white answer pegs are used, then the O ( n log log n ) bound holds for up to n 2 log log n colors. These bounds are almost tight, as the known lower bound of Ω( n ) shows. Unlike for k ≤ n 1 − ε , simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal nonadaptive strategy (deterministic or randomized) needs Θ( n log n ) guesses.

While evolutionary algorithms are known to be very successful for a broad range of applications, the algorithm designer is often left with many algorithmic choices, for example, the size of the population, the mutation rates, and the crossover rates of the algorithm. These parameters are known to have a crucial influence on the optimization time, and thus need to be chosen carefully, a task that often requires substantial efforts. Moreover, the optimal parameters can change during the optimization process. It is therefore of great interest to design mechanisms that dynamically choose best-possible parameters. An example for such an update mechanism is the one-fifth success rule for step-size adaption in evolutionary strategies. While in continuous domains this principle is well understood also from a mathematical point of view, no comparable theory is available for problems in discrete domains. In this work we show that the one-fifth success rule can be effective also in discrete settings. We regard the (1+(λ,λ)) GA proposed in [Doerr/Doerr/Ebel: From black-box complexity to designing new genetic algorithms, TCS 2015]. We prove that if its population size is chosen according to the one-fifth success rule then the expected optimization time on OneMax is linear. This is better than what any static population size λ can achieve and is asymptotically optimal also among all adaptive parameter choices.

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably is useful, the (1+(λ, λ)) Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel. Lessons From the Black-Box: Fast Crossover-Based Genetic Algorithms. TCS 2015]. Using the fitness level method, the expected optimization time on general OneMax functions was analyzed and a O(max{n log(n) / λ, λ n}) bound was proven for any offspring population size λ ∈ [1..n]. We improve this work in several ways, leading to sharper bounds and a better understanding of how the use of crossover speeds up the runtime in this algorithm. We first improve the upper bound on the runtime to O(max{n log(n) / λ, n λ log log(λ)/log(λ)}). This improvement is made possible from observing that in the parallel generation of λ offspring via crossover (but not mutation), the best of these often is better than the expected value, and hence several fitness levels can be gained in one iteration.

Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length.

With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942--951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time $O(n \log n)$ with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

That the initialization can have a significant impact on the performance of evolutionary algorithms (EAs) is a well known fact in the empirical evolutionary computation literature. Surprisingly, it has nevertheless received only little attention from the theoretical community.

We analyze the unbiased black-box complexities of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is (1/2 - ε), that is, when only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values n/2 and n are blanked out, polynomial time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a Θ(n(-1/2)) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not only by comparing the fitnesses of the competing search points but also by taking into account the (empirical) expected fitnesses of their offspring.

In the online checkpointing problem, the task is to continuously maintain a set of k checkpoints that allow rewinding an ongoing computation faster than by a full restart. The only operation allowed is to replace an old checkpoint by the current state. Our aim is checkpoint placement strategies that minimize rewinding cost, i.e., such that at all times T when requested to rewind to some time t ≤ T the number of computation steps that need to be redone to get to t from a checkpoint before t is as few as possible. In particular, we want the closest checkpoint earlier than t to be no farther away from t than qk times the ideal distance T/(k + 1), where qk is a small constant. Improving earlier work showing 1 + 1/k ≤ qk ≤ 2, we show that qk can be chosen asymptotically less than 2. We present algorithms with asymptotic discrepancy qk ≤ 1.59 + o(1) valid for all k and qk ≤ ln(4) + o(1) ≤ 1.39 + o(1) valid for k being a power of two. Experiments indicate the uniform bound pk ≤ 1.7 for all k. For small k, we show how to use a linear programming approach to compute good checkpointing algorithms. This gives discrepancies of less than 1.55 for all k < 60. We prove the first lower bound that is asymptotically more than 1, namely qk ≥ 1.30 − o(1). We also show that optimal algorithms (yielding the infimum discrepancy) exist for all k.

To understand how evolutionary algorithms optimize the simple class of monotonic functions, Jansen (FOGA 2007) introduced the partially-ordered evolutionary algorithm (PO-EA) model and analyzed its runtime. The PO-EA is a pessimistic model of the true optimization process, hence performance guarantees for it immediately take over to the true optimization process. Based on the observation that Jansen's model leads to a process more pessimistic than what any monotonic function would, we extend his model by parametrizing the degree of pessimism. For all degrees of pessimism, and all mutation rates c/n, we give a precise runtime analysis of this process. For all degrees of pessimism lower than that of Jansen, we observe a Θ(n log n) runtime for the standard mutation probability of 1/n. However, we also observe a strange double-jump behavior in terms of the mutation probability. For all non-zero degrees of pessimism, there is a threshold c ∈ R such that (i) for mutation rates c'/n with c' c we have an exponential runtime.

It has often been observed that the expected runtime of an evolutionary algorithm with random initialization does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori would greatly simplify the runtime analysis for the algorithm using random initialization. We prove such a result for the optimization of the OneMax test function via the two randomized search heuristics Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm. For both algorithms, we show that the expected runtime from a random initial solution deviates at most by a constant number of iterations from the expected runtime when starting with a solution having exactly n/2 ones.

We analyze the unbiased black-box complexity of jump functions with large jump sizes. Among other results, we show that when the jump size is (1/2 - epsilon)n, that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values n/2 and n are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a Theta(n-1/2) fraction) is a plateau of constant fitness.

We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks (“randomized rumor spreading”). In the classical model, in each round, each informed vertex chooses a neighbor at random and informs it, if it was not informed before. It is known that this simple protocol succeeds in spreading a rumor from one vertex to all others within O (log n ) rounds on complete graphs, hypercubes, random regular graphs, Erdős-Rényi random graphs, and Ramanujan graphs with probability 1 − o (1). In the quasirandom model, we assume that each vertex has a (cyclic) list of its neighbors. Once informed, it starts at a random position on the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above-mentioned bounds still hold. In some cases, even better bounds than for the classical model can be shown.

Evolutionary computation methods, such as evolutionary algorithms or swarm intelligence algorithms, have been successfully applied to a wide range of difficult problems. These include classical NP-hard combinatorial optimization problems and a variety of hard real-world optimization problems. Real-world problems, in particular, are difficult to solve using traditional search methods because often they are nonlinear, highly constrained, multiobjective, and can include a number of uncertainties.

We analyze the runtime of the (1 + λ) evolutionary algorithm (EA) on the classic royal road test function class. For a royal road function defined on bit-strings of length n having block sized ≥ log n + (c + 1 + ε) log d, we prove that the (1 + λ) EA with λ = Θ(nc) finds the optimum in an expected number of O(2d/dc· n/d log n/d) generations. Together with our lower bound of Ω(2d/dc), this shows that for royal road functions even very large offspring populations do not reduce the runtime significantly.

While for single-objective evolutionary algorithms many sharp run-time analyses exist, there are only few for multiobjective evolutionary algorithms (MOEAs), and even fewer for global MOEAs, that is, MOEAs using standard bit mutation (instead of 1-bit mutation, which is easier to analyze, but less common in practice). For example, there is not a single lower bound result for the runtime of the classic “global simple evolutionary multiobjective optimizer” (GSEMO) on the biobjective test function LeadingOnesTrailingZeros (LOTZ). An upper bound of O(n2/p), where p ≤ 1/n is the mutation probability, for this runtime was proven ten years ago by Giel (CEC 2003). In this work, we show that this bound is sharp for small values of p, namely p-7/4.

Separable functions are composed of subfunctions that depend on mutually disjoint sets of bits. These subfunctions can be optimized independently, however in black-box optimization this direct approach is infeasible as the composition of subfunctions may be unknown. Common belief is that evolutionary algorithms make progress on all subfunctions in parallel, so that optimizing a separable function does not take not much longer than optimizing the hardest subfunction---subfunctions are optimized "in parallel."

The recently active research area of black-box complexity revealed that for many optimization problems the best possible black-box optimization algorithm is significantly faster than all known evolutionary approaches. While it is not to be expected that a general-purpose heuristic competes with a problem-tailored algorithm, it still makes sense to look for the reasons for this discrepancy.

At last year's GECCO a novel perspective for theoretical performance analysis of evolutionary algorithms and other randomised search heuristics was introduced that concentrates on the expected function value after a pre-defined number of steps, called budget. This is significantly different from the common perspective where the expected optimisation time is analysed. While there is a huge body of work and a large collection of tools for the analysis of the expected optimisation time the new fixed budget perspective introduces new analytical challenges. Here it is shown how results on the expected optimisation time that are strengthened by deviation bounds can be systematically turned into fixed budget results. We demonstrate our approach by considering the (1+1) EA on LeadingOnes and significantly improving previous results. We prove that deviating from the expected time by an additive term of ω(n3/2 happens only with probability o(1). This is turned into tight bounds on the function value using the inverse function. We use three, increasingly strong or general approaches to proving the deviation bounds, namely via Chebyshev's inequality, via Chernoff bounds for geometric random variables, and via variable drift analysis.

We analyze how the (1+λ) evolutionary algorithm (EA) optimizes linear pseudo-Boolean functions. We prove that it finds the optimum of any linear function within an expected number of O(1/λn log n+n) iterations. We also show that this bound is sharp for some functions, e.g., the binary value function. Hence unlike for the(1+1) EA, for the (1+λ) EA different linear functions may have run-times of different asymptotic order. The proof of our upper bound heavily relies on a number of classic and recent drift analysis methods. In particular, we show how to analyze a process displaying different types of drifts in different phases. Our work corrects a wrongfully claimed better asymptotic runtime in an earlier work~\cite{He10}.

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n1−ε, ε > 0 constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(n log log n) guesses. This bound is valid also when only black answer-pegs are used. It improves the O(n log n) bound first proven by Chvátal (Combinatorica 3 (1983), 325–329). We also show that if both black and white answer-pegs are used, then the O(n log log n) bound holds for up to n2 log log n colors. These bounds are almost tight as the known lower bound of Ω(n) shows. Unlike for k ≤ n1−ε, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that any non-adaptive strategy needs an expected number of Ω(n log n) guesses.

Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotonic. These functions have the property that whenever only 0-bits are changed to 1, then the objective value strictly increases. Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant c in the mutation probability p(n) = c/n can make a decisive difference. We show that if c < 1, then the (1+1) EA finds the optimum of every such function in Θ(n log n) iterations. For c = 1, we can still prove an upper bound of O(n(3/2)). However, for c ≥ 16, we present a strictly monotonic function such that the (1+1) EA with overwhelming probability needs 2(Ω(n)) iterations to find the optimum. This is the first time that we observe that a constant factor change of the mutation probability changes the runtime by more than a constant factor.

The first rigorous theoretical analysis (Horoba, Sudholt (GECCO 2010)) of an ant colony optimizer for the stochastic shortest path problem suggests that ant system experience significant difficulties when the input data is prone to noise. In this work, we propose a slightly different ant optimizer to deal with noise.

We analyze the run-time of the (1 + 1) Evolutionary Algorithm optimizing an arbitrary linear function f : {0,1,...,r}n -> R. If the mutation probability of the algorithm is p = c/n, then (1 + o(1))(ec/c))rn log n + O(r3n log log n) is an upper bound for the expected time needed to find the optimum. We also give a lower bound of (1 + o(1))(1/c)rn log n. Hence for constant c and all r slightly smaller than (log n)1/3, our bounds deviate by only a constant factor, which is e(1 + o(1)) for the standard mutation probability of 1/n. The proof of the upper bound uses multiplicative adaptive drift analysis as developed in a series of recent papers. We cannot close the gap for larger values of r, but find indications that multiplicative drift is not the optimal analysis tool for this case.

We show that for all 1 < k d log n the k-ary unbiased black-box complexity of the n-dimensional OneMax function class is O(n/k). This indicates that the power of higher arity operators is much stronger than what the previous O(n/log k) bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests.

We analyze the classic board game of Mastermind with n holes and a constant number of colors. The classic result of Chvatal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with Theta(n / log n) questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006), 525-544) on the memory-restricted black-box complexity of the OneMax function class.

We analyze the two existing algorithms to generate dependent randomized roundings for the bipartite edge weight rounding problem together with several newly proposed variants of these algorithms. For both the edge-based approach of Gandhi, Khuller, Parthasarathy, Srinivasan (FOCS 2002) and the bit-wise approach of Doerr (STACS 2006) we give a simple derandomization (guaranteeing the same rounding errors as the randomized versions achieve with positive probability). An experimental investigation on different types of random instances show that, contrary to the randomized rounding problem with disjoint cardinality constraints, the bit-wise approach is faster than the edge-based one, while the latter still achieves the best rounding errors. We propose a hybrid approach that, in terms of running time, combines advantages of the two previous approaches; in terms of rounding errors it seems a fair compromise. In all cases, the derandomized versions yield much better rounding errors than the randomized ones. We also test how the algorithms compare when used to solve different broadcast scheduling problems (as suggested by Gandhi et al.). Since this needs more random decisions than just in the rounding process, we need to partially re-prove previous results and simplify the corresponding algorithms to finally derive a derandomized version. Again, the derandomized versions give significantly better approximations than the randomized versions. We tested the algorithms on data taken from the Wikipedia access log. For the maximum throughput version of the problem, the derandomized algorithms compute solutions that are very close to the optimum of the linear relaxation. For the minimum average delay version, Gandhi et al. gave a (2, 1)-bicriteria algorithm, i.e., an algorithm which produces a 2-speed schedule with an average delay which on expectation is no worse than that of the 1-speed optimum. For this problem variant, while the performance guarantee of the algorithms certainly holds, we find that a simple greedy heuristic generally produces superior solutions.

We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al. (GECCO~2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the OneMax function is improved from 1.28n ln n to 0.982n ln n, which breaks the barrier of n ln n posed by coupon-collector processes. Compared to the classical 1+1-EA, whose runtime will for the first time be analyzed with respect to terms of lower order, this represents a speedup by more than a factor of e=2.71...

Unbiased black-box complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste, Jansen, and Wegener (Theor. Comput. Sci. 2006). In this work, we show that for two natural problems the unbiased black-box complexity remains artificially small. For the classical JumpK test function class and for a subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O(n log n). Since the first problem usually needs Theta(nk) function evaluations to be optimized by standard heuristics and the second is even NP-complete, these black-box complexities seem not to indicate the true difficulty of the two problems for randomized search heuristics.

Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.

In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem [2]. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(log n) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median of n numbers in time O(log m log log n + log n) under adversarial presence.

With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The well-known random phone call model of Karp et al. (FOCS 2000) is a push-pull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. - The push-pull strategy delivers a message to all nodes within Θ(log n) rounds with high probability. The best known bound so far was O(log2 n). - If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Θ(log n / log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding double-contacts reduces the run-time to a smaller order of magnitude.

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{ℓ, log(n)}), where ℓ is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ℓ edges. This bound is tight. For all values of n and ℓ we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{ℓ, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.

We regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. We show that any such function is optimized in time (1 + o(1)) 1.39en ln (n), where n is the length of the bit string. We also prove a lower bound of (1 -o(1))en ln(n), which in fact holds for all functions with a unique global optimum. This shows that for linear functions, even though the optimization behavior might differ, the resulting runtimes are very similar. Our experimental results suggest that the true optimization times are even closer than what the theoretical guarantees promise.

Motivated by recent successful applications of the concept of quasirandomness, we investigate to what extent such ideas can be used in evolutionary computation. To this aim, we propose different variations of the classical (1+1) evolutionary algorithm, all imitating the property that the (1+1) EA over intervals of time touches all bits roughly the same number of times. We prove bounds on the optimization time of these algorithms for the simple OneMax function. Surprisingly, none of the algorithms achieves the seemingly obvious reduction of the runtime from Θ( n log n ) to O(n) . On the contrary, one may even need Ω( n 2 ) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50% speed-up.

In this paper, we present a new representation for individuals in the single-source shortest path problem. Contrary to previous approaches, it has the natural property that different vertex degrees do not induce unfairness in the mutation step. In particular, at any time each edge has roughly the same probability of being added to or removed from the current individual.

Drift analysis is one of the strongest tools in the analysis of evolutionary algorithms. Its main weakness is that it is often very hard to find a good drift function.

With deep sadness, we had to realize that our co-editor and co-founder of the theory track, Ingo Wegener, has died on the 26th of November 2008 after a long fight with cancer.His death is a tragic loss for all who knew him, friends, colleagues and students.Ingo Wegener was born on the 4th of December 1950 in Bremen, Germany.He was a full professor at the Technische Universität Dortmund, leading a strong and influential group on efficient algorithms and complexity theory.He and his group contributed to many research areas.Their fundamental results on the complexity of Boolean functions and on the theory of evolutionary computation had an enormous impact.Ingo Wegener received numerous honors.Being appointed to the German Council of Science and Humanities as well as receiving the most important and prestigious German award for computer scientists, the Konrad-Zuse-Medaille, are just two examples.In the field of evolutionary computation, Ingo Wegener established a completely new research direction.He started analyzing evolutionary algorithms by purely theoretical means.To substantiate a claim, we would look for a mathematical proof, valid for all inputs, rather than experimentally analyzing a limited number of examples.Unlike in the classical theory of algorithms community, this approach was uncommon of in the field of evolutionary computation.With persistence and with convincing results he succeeded in getting his mathematical approach become a recognized direction in the field.Less than ten years

We bound the hereditary discrepancy of a hypergraph $\mathcal{H}$ in two colors in terms of its hereditary discrepancy in c colors. We show that $\mathrm{herdisc}(\mathcal{H},2)\leq Kc$ $\mathrm{herdisc}(\mathcal{H},c)$, where K is some absolute constant. This bound is sharp apart from the absolute constant.

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. At SODA 2008, three of the authors proposed a quasirandom variant. Here, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster (which was expected, though maybe not to this extent), but also that the runtime is more concentrated around the mean value (which is surprising given that much fewer random bits are used in the quasirandom process). These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that the particular structure of the lists has little influence on the efficiency. In particular, there is no problem if all nodes use an identical order to inform their neighbors.

We regard the problem of generating randomized roundings with a single cardinality constraint. This is motivated by recent results of Srinivasan (FOCS 2001), Gandhi et al. (FOCS 2002, J. ACM 2006) and the first author (STACS 2005, STACS 2006). Our work results in (a) an improved version of the bitwise derandomization given by the first author, (b) the first derandomization of Srinivasan's tree-based randomized approach, together with a proof of its correctness, and (c) an experimental comparison of the resulting algorithms. Our experiments show that adding a single cardinality constraint typically reduces the rounding errors and not seriously increases the running times. In general, our derandomization of the tree-based approach is superior to the derandomized bitwise one, while the two randomized versions produce very similar rounding errors. When implementing the derandomized tree-based approach, however, the choice of the tree is important.

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation, which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps.

We deepen the theoretical analysis of the genetic algorithm for the all-pairs shortest path problem proposed by Doerr, Happ and Klein (GECCO 2008). We show that the growth of the paths through crossover operations can be analyzed without the previously used approach of waiting until all paths of a certain length are present in the population. This allows to prove an improved guarantee for the optimization time of O(n3.25 log1/4(n). We also show that this bound is asymptotically tight. Besides the mere run-time result, our analysis is a step towards understanding how crossover works and how it can be analyzed with rigorous methods.

We present a simple framework for dealing with search spaces consisting of permutations. To demonstrate its usefulness, we build upon it a simple (1+1)-evolutionary algorithm for one of the most fundamental problems in computer science, namely the problem of sorting n pairwise comparable items. We give a rigorous proof that the optimization time is at most O(n2) with high probability. Our experimental evaluation shows that it is much better, namely around O(n log n). This compares favorably with the currently best (1 + 1)-EAs for sorting, for which an optimization time of O(n2log n) was proven (Scharnow, Tinnefeld and Wegener (2004)) and one of similar order is observed experimentally in this work. Our approach has the particular advantage that it does distinguish between wrong and unexplored information. This allows to retrieve partial, correct information even before the optimal solution has been found.

We show that the natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.

Evolutionary algorithms operating on bit strings usually employ a global mutation where each bit is flipped independently with some mutation probability. Most often the mutation probability is set fixed in a way that on average exactly one bit is flipped in a mutation. A seemingly very similar concept is a local one realized by an operator that flips exactly one bit chosen uniformly at random.

Motivated by neutrality observed in natural evolution often redundant encodings are used in evolutionary algorithms. Many experimental studies have been carried out on this topic. In this paper we present a first rigorous runtime analysis on the effect of using neutrality. We consider a simple model where a layer of constant fitness is distributed in the search space and point out situations where the use of neutrality significantly influence the runtime of an evolutionary algorithm.

We conduct a rigorous analysis of the (1 + 1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld and Wegener (Journal of Mathematical Modelling and Algorithms, 2004). We prove a tight bound of Theta(n2max{log(n),lscr}) on the optimization time, where lscr is the maximum number of edges of a shortest path with minimum number of edges from the source to another vertex. Using various tools from probability theory we show that these bounds not only hold in expectation, but also with high probability. We are optimistic that these tools can also be used to analyze the run-time of evolutionary algorithms for other problems.

Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm 1-Ant on pseudo-Boolean optimization problems. For the problem OneMax they showed how the runtime depends on the evaporation factor. In particular, they proved a phase transition from exponential to polynomial runtime. In this work, we simplify the view on this problem by an appropriate translation of the pheromone model. This results in a profound simplification of the pheromone update rule and, by that, a refinement of the results of Neumann and Witt. In particular, we show how the exponential runtime bound gradually changes to a polynomial bound inside the phase of transition.

We propose and analyze a novel genotype to represent walk and cycle covers in graphs, namely matchings in the adjacency lists. This representation admits the natural mutation operator of adding a random match and possibly also matching the former partners.

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w.r.t a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, the influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t the runtime behavior have been determined for the example function OneMax.This paper puts forward the rigorous runtime analysis of the 1-ANT on example functions, namely on the functions LeadingOnes and BinVal. With respect to EAs, such analyses have been essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics.

Successful applications of evolutionary algorithms show that certain variation operators can lead to good solutions much faster than other ones. We examine this behavior observed in practice from a theoretical point of view and investigate the effect of an asymmetric mutation operator in evolutionary algorithms with respect to the runtime behavior. Considering the Eulerian cycle problem we present runtime bounds for evolutionary algorithms using an asymmetric operator which are much smaller than the best upper bounds for a more general one. In our analysis it turns out that a plateau which both algorithms have to cope with changes its structure in a way that allows the algorithm to obtain an improvement much faster. In addition, we present a lower bound for the general case which shows that the asymmetric operator speeds up computation by at least a linear factor.

Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.

We investigate the problem of rounding a given [0,1]-valued matrix to a 0,1 matrix such that the rounding error with respect to $2 \times 2$ boxes is small. Such roundings yield good solutions for the digital halftoning problem, as shown by Asano et al. [Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2002, SIAM, Philadelphia, 2002, pp. 896--904]. We present a randomized algorithm computing roundings with expected error at most 0.5463 per box, improving the 0.75 nonconstructive bound of Asano et al. Our algorithm is the first to solve this problem fast enough for practical application, namely, in linear time. Of broader interest might be our rounding scheme, which is a modification of randomized rounding. Instead of independently rounding the variables, we impose a number of suitable dependencies. Thus, by equipping the rounding process with some of the problem information, we reduce the rounding error significantly compared to independent randomized rounding, which leads to an expected error of 0.82944 per box. Finally, we give a characterization of realizable dependencies.