Benjamin Doerr

AAAI Conference 2026 Conference Paper

Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer

• Benjamin Doerr
• Martin S. Krejca
• Milan Stanković

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.

AAAI Conference 2026 Conference Paper

Superior Runtime Guarantees for the MOEA/D Multi-Objective Optimizer via Weighted-Sum Decomposition

• Danyang Zhang
• Zerong Zhong
• Weijie Zheng
• Benjamin Doerr

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.

AAAI Conference 2025 Conference Paper

(1+1) Genetic Programming with Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error

• Benjamin Doerr
• Andrei Lissovoi
• Pietro S. Oliveto

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.

IJCAI Conference 2025 Conference Paper

Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It

• Denis Antipov
• Benjamin Doerr

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.

AAAI Conference 2025 Conference Paper

From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms (Journal Track)

• Weijie Zheng
• Benjamin Doerr

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.

IJCAI Conference 2025 Conference Paper

Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II

• Yasser Alghouass
• Benjamin Doerr
• Martin S. Krejca
• Mohammed Lagmah

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.

AAAI Conference 2025 Conference Paper

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces

• Benjamin Doerr
• Martin S. Krejca
• Günter Rudolph

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.

IJCAI Conference 2025 Conference Paper

Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy

• Mingfeng Li
• Weijie Zheng
• Benjamin Doerr

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.

IJCAI Conference 2025 Conference Paper

Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator

• Abderrahim Bendahi
• Benjamin Doerr
• Adrien Fradin
• Johannes F. Lutzeyer

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.

AAAI Conference 2025 Conference Paper

Speeding Up the NSGA-II with a Simple Tie-Breaking Rule

• Benjamin Doerr
• Tudor Ivan
• Martin S. Krejca

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.

IJCAI Conference 2025 Conference Paper

The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)

• Renzhong Deng
• Weijie Zheng
• Benjamin Doerr

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<Nr. These theoretical results suggest that the best setting to approximate the Pareto front is Nr=N. In our experiments, we observe that with this setting the NSGA-III computes optimal approximations, very different from the NSGA-II, for which optimal approximations have not been observed so far.

IJCAI Conference 2025 Conference Paper

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

• Benjamin Doerr
• Martin S. Krejca
• Andre Opris

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.

NeurIPS Conference 2025 Conference Paper

Why Popular MOEAs Are Popular: Proven Advantages in Approximating the Pareto Front

• Mingfeng Li
• Qiang Zhang
• Weijie Zheng
• Benjamin Doerr

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.

TCS Journal 2024 Journal Article

Estimation-of-distribution algorithms for multi-valued decision variables

• Firas Ben Jedidia
• Benjamin Doerr
• Martin S. Krejca

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 ( r ln ⁡ ( r ) 2 n 2 ln ⁡ ( n ) ) function evaluations. This bound is nearly tight as our lower bound Ω ( r ln ⁡ ( r ) n 2 ln ⁡ ( n ) ) shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.

AAAI Conference 2024 Conference Paper

How to Use the Metropolis Algorithm for Multi-Objective Optimization?

• Weijie Zheng
• Mingfeng Li
• Renzhong Deng
• Benjamin Doerr

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.

AAAI Conference 2024 Conference Paper

Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations

• Benjamin Doerr
• Aymen Echarghaoui
• Mohammed Jamal
• Martin S. Krejca

Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the (µ+1) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size µ. This drastically improves over the previously best known guarantee, which is only quadratic in µ. Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size n suffice to gain an Ω(n)-factor runtime improvement from crossover (previous works achieved comparable bounds only with µ = Θ(n) or a non-standard mutation rate).

AAAI Conference 2024 Conference Paper

Runtime Analysis of the SMS-EMOA for Many-Objective Optimization

• Weijie Zheng
• Benjamin Doerr

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.

AIJ Journal 2023 Journal Article

(1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error

• Benjamin Doerr
• Andrei Lissovoi
• Pietro S. Oliveto

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 ( ℓ n log 2 ⁡ 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 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 super-linear in the distance from the optimum.

IJCAI Conference 2023 Conference Paper

A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

• Simon Wietheger
• Benjamin Doerr

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.

TCS Journal 2023 Journal Article

Bivariate estimation-of-distribution algorithms can find an exponential number of optima

• Benjamin Doerr
• Martin S. Krejca

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

JMLR Journal 2023 Journal Article

From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms

• Weijie Zheng
• Benjamin Doerr

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. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

AAAI Conference 2023 Conference Paper

From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds

• Benjamin Doerr
• Zhongdi Qu

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.

AIJ Journal 2023 Journal Article

Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)

• Weijie Zheng
• Benjamin Doerr

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.

IJCAI Conference 2023 Conference Paper

Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise

• Matthieu Dinot
• Benjamin Doerr
• Ulysse Hennebelle
• Sebastian Will

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.

AAAI Conference 2023 Conference Paper

Runtime Analysis for the NSGA-II: Provable Speed-Ups from Crossover

• Benjamin Doerr
• Zhongdi Qu

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.

TCS Journal 2023 Journal Article

Stagnation detection meets fast mutation

• Benjamin Doerr
• Amirhossein Rajabi

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.

IJCAI Conference 2023 Conference Paper

The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem

• Sacha Cerf
• Benjamin Doerr
• Benjamin Hebras
• Yakob Kahane
• Simon Wietheger

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.

AAAI Conference 2022 Conference Paper

A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II)

• Weijie Zheng
• Yufei Liu
• Benjamin Doerr

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.

TCS Journal 2021 Journal Article

A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes

• Benjamin Doerr
• Martin S. Krejca

With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors.

IJCAI Conference 2021 Conference Paper

Choosing the Right Algorithm With Hints From Complexity Theory

• Shouda Wang
• Weijie Zheng
• Benjamin Doerr

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.

TCS Journal 2021 Journal Article

Exponential upper bounds for the runtime of randomized search heuristics

• Benjamin Doerr

We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in heuristic search and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension n. This drastically extends a previous such result, limited to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most 1/2, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the ( 1, λ ) evolutionary algorithm on the OneMax problem when the offspring population size λ is logarithmic, but below the efficiency threshold. To show that our approach can also deal with non-trivial parent population sizes, we prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark, matching a known exponential lower bound.

AAAI Conference 2021 Conference Paper

Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives

• Benjamin Doerr
• Weijie Zheng

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 ∈ [4. .n 2 − 1], the global SEMO (GSEMO) covers the Pareto front in Θ((n − 2k)nk ) 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 singleobjective 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 multiobjective optimization.

TCS Journal 2020 Journal Article

Optimal parameter choices via precise black-box analysis

• Benjamin Doerr
• Carola Doerr
• Jing Yang

It has been observed that some working principles of evolutionary algorithms, in particular, the influence of the parameters, cannot be understood from results on the asymptotic order of the runtime, but only from more precise results. In this work, we complement the emerging topic of precise runtime analysis with a first precise complexity theoretic result. Our vision is that the interplay between algorithm analysis and complexity theory becomes a fruitful tool also for analyses more precise than asymptotic orders of magnitude. As particular result, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is n ln ⁡ ( n ) − c n ± o ( n ) for a constant c which is between 0. 2539 and 0. 2665. This runtime can be achieved with a simple ( 1 + 1 ) -type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13% closer to the optimum than those of the best previously known algorithms. To prove our results, we formulate several new versions of the variable drift theorems, which also might be of independent interest.

AAAI Conference 2020 Conference Paper

Optimization of Chance-Constrained Submodular Functions

• Benjamin Doerr
• Carola Doerr
• Aneta Neumann
• Frank Neumann
• Andrew Sutton

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.

TCS Journal 2020 Journal Article

The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time

• Benjamin Doerr
• Timo Kötzing
• J.A. Gregor Lagodzinski
• Johannes Lengler

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, that is, the unnecessary growth of solution lengths, which may slow down the optimization process. So far, the mathematical runtime analysis could not deal well with bloat and required explicit assumptions limiting bloat. In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism. More specifically, we analyzed the performance of the ( 1 + 1 ) GP on the two benchmark functions Order and Majority. When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of O ( T init + n log ⁡ n ) iterations both for Order and Majority. For the case without bloat control, the bounds O ( T init log ⁡ T init + n ( log ⁡ n ) 3 ) and Ω ( T init + n log ⁡ n ) (and Ω ( T init log ⁡ T init ) for n = 1 ) hold for Majority. 1

TCS Journal 2020 Journal Article

Working principles of binary differential evolution

• Benjamin Doerr
• Weijie Zheng

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 for a long time. 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 enables BDE to optimize the most important bits very fast. Overall, our results indicate that BDE is an interesting optimization paradigm having characteristics significantly different from classic evolutionary algorithms or estimation-of-distribution algorithms (EDAs). On the technical side, we observe that the strong stochastic dependencies in the random experiment describing a run of BDE prevent us from proving all desired results with the mathematical rigor that was successfully used in the analysis of other evolutionary algorithms. Inspired by mean-field approaches in statistical physics we propose a more independent variant of BDE, show experimentally its similarity to BDE, and prove some statements rigorously only for the independent variant. Such a semi-rigorous approach might be interesting for other problems in evolutionary computation where purely mathematical methods failed so far.

TCS Journal 2019 Journal Article

Analyzing randomized search heuristics via stochastic domination

• Benjamin Doerr

Apart from few exceptions, the mathematical runtime analysis of evolutionary algorithms is mostly concerned with expected runtimes, occasionally augmented by tail bounds. In this work, we argue that stochastic domination is a notion that should be used more frequently in this area. Stochastic domination allows to formulate much more informative performance guarantees, it allows to decouple the algorithm analysis into the true algorithmic part of detecting a domination statement and the probability-theoretical part of deriving the desired probabilistic guarantees from this statement, and it helps finding simpler and more natural proofs. As particular results, we prove a variant of the fitness level theorem which shows that the runtime of the search heuristic is dominated by a sum of independent geometric random variables, we prove the first tail bounds for several classic runtime problems, and we give a short and natural proof for Witt's result that the runtime of any ( μ, p ) mutation-based algorithm on any function with unique optimum is subdominated by the runtime of a variant of the ( 1 + 1 ) EA on the OneMax function. As side-products, we determine the fastest unbiased ( 1 + 1 ) algorithm for the LeadingOnes benchmark problem, both in the general case and when restricted to static mutation operators, and we prove a Chernoff-type tail bound for sums of independent coupon collector distributions.

TCS Journal 2015 Journal Article

From black-box complexity to designing new genetic algorithms

• Benjamin Doerr
• Carola Doerr
• Franziska Ebel

Black-box complexity theory recently produced several surprisingly fast black-box optimization algorithms. In this work, we exhibit one possible reason: These black-box algorithms often profit from solutions inferior to the previous-best. In contrast, evolutionary approaches guided by the “survival of the fittest” paradigm often ignore such solutions. We use this insight to design a new crossover-based genetic algorithm. It uses mutation with a higher-than-usual mutation probability to increase the exploration speed and crossover with the parent to repair losses incurred by the more aggressive mutation. A rigorous runtime analysis proves that our algorithm for many parameter settings is asymptotically faster on the OneMax test function class than all what is known for classic evolutionary algorithms. A fitness-dependent choice of the offspring population size provably reduces the expected runtime further to linear in the dimension. Our experimental analysis on several test function classes shows advantages already for small problem sizes and broad parameter ranges. Also, a simple self-adaptive choice of these parameters gives surprisingly good results.

TCS Journal 2015 Journal Article

Optimizing linear functions with the ( 1 + λ ) evolutionary algorithm—Different asymptotic runtimes for different instances

• Benjamin Doerr
• Marvin Künnemann

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 linear functions, e. g. , the binary value function. Since previous works shows an asymptotically smaller runtime for the special case of OneMax, it follows that 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 [13]. We also use our methods to analyze the runtime of the ( 1 + λ ) EA on the OneMax test function and obtain a new upper bound of O ( n log ⁡ log ⁡ λ / log ⁡ λ ) for the case that λ is larger than O ( log ⁡ n log ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ); this is the cut-off point where a linear speed-up ceases to exist. While our results are mostly spurred from a theory-driven interest, they also show that choosing the right size of the offspring population can be crucial. For both the binary value and the OneMax test function we observe that once a linear speed-up ceases to exist, in fact, the speed-up from a larger λ reduces to sub-logarithmic (still at the price of a linear increase of the cost of each generation).

TCS Journal 2014 Journal Article

Reducing the arity in unbiased black-box complexity

• Benjamin Doerr
• Carola Winzen

We show that for all 1 < k ≤ 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. [Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, Carola Winzen, Faster black-box algorithms through higher arity operators, in Proc. of the 11th ACM Workshop on Foundations of Genetic Algorithms, FOGA’11, ACM, 2011, pp. 163–172] suggests. The key to this result is an encoding strategy, which might be of independent interest. It shows that, using k-ary unbiased variation operators only, we may simulate an unrestricted memory of O ( 2 k ) bits.

AIJ Journal 2014 Journal Article

The unbiased black-box complexity of partition is polynomial

• Benjamin Doerr
• Carola Doerr
• Timo Kötzing

Unbiased black-box complexity was introduced as a refined complexity model for random-ized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10]. We show that for some problems the unbiased black-box complexity remains artificially small. More precisely, for two different formulations of an NP -hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O ( n log ⁡ n ). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.

TCS Journal 2013 Journal Article

Black-box complexities of combinatorial problems

• Benjamin Doerr
• Timo Kötzing
• Johannes Lengler
• Carola Winzen

Black-box complexity, counting the number of queries needed to find the optimum of a problem without having access to an explicit problem description, was introduced by Droste, Jansen, and Wegener [S. Droste, T. Jansen, I. Wegener, Upper and lower bounds for randomized search heuristics in black-box optimization, Theory of Computing Systems 39 (2006) 525–544] to measure the difficulty of solving an optimization problem via generic search heuristics such as evolutionary algorithms, simulated annealing or ant colony optimization. Since then, a number of similar complexity notions were introduced. However, so far these new notions were only analyzed for artificial test problems. In this paper, we move a step forward and analyze the different black-box complexity notions for two classic combinatorial problems, namely the minimum spanning tree and the single-source shortest path problem. Besides proving bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem has a significant influence on its black-box complexity. In addition, when regarding the unbiased (symmetry-invariant) black-box complexity of combinatorial problems, it is important to choose a meaningful definition of unbiasedness.

TCS Journal 2013 Journal Article

More effective crossover operators for the all-pairs shortest path problem

• Benjamin Doerr
• Daniel Johannsen
• Timo Kötzing
• Frank Neumann
• Madeleine Theile

The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w. r. t. the number of fitness evaluations) of Θ ( n 3. 25 ( log n ) 0. 25 ). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O ( n 3. 2 ( log n ) 0. 2 ). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an optimization time of O ( n 3 log n ). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.

SODA Conference 2013 Conference Paper

Playing Mastermind with Many Colors

• Benjamin Doerr
• Reto Spöhel
• Henning Thomas
• Carola Winzen

TCS Journal 2012 Journal Article

Crossover can provably be useful in evolutionary computation

• Benjamin Doerr
• Edda Happ
• Christian Klein

We show that a 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.

TCS Journal 2012 Journal Article

Non-existence of linear universal drift functions

• Benjamin Doerr
• Daniel Johannsen
• Carola Winzen

Drift analysis is a powerful tool to prove upper and lower bounds on the runtime of randomized search heuristics. Its most famous application is a simple proof for the classical problem how the (1+1) Evolutionary Algorithm (EA) optimizes linear pseudo-Boolean functions. A relatively simple potential function allows to track the progress of the EA optimizing any linear function. In this work, we show that such beautiful proofs cease to exist if the mutation probability is slightly larger than the standard value of 1 / n.

TCS Journal 2011 Journal Article

Evolutionary algorithms and dynamic programming

• Benjamin Doerr
• Anton Eremeev
• Frank Neumann
• Madeleine Theile
• Christian Thyssen

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. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.

TCS Journal 2011 Journal Article

Runtime analysis of the 1-ANT ant colony optimizer

• Benjamin Doerr
• Frank Neumann
• Dirk Sudholt
• Carsten Witt

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies simple ACO algorithms such as the 1-ANT are investigated. 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 work puts forward the rigorous runtime analysis of the 1-ANT on the example functions LeadingOnes and BinVal. With respect to Evolutionary Algorithms (EAs), such analyses were 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 has a crucial impact on the runtime. Moreover, the analyses provide insight into the working principles of ACO algorithms. Our theoretical results are accompanied by experimental results that give us a more detailed impression of the 1-ANT’s performance. Furthermore, the experiments also deal with the question whether using many ant solutions in one iteration can decrease the total runtime.

STOC Conference 2011 Conference Paper

Social networks spread rumors in sublogarithmic time

• Benjamin Doerr
• Mahmoud Fouz
• Tobias Friedrich 0001

SODA Conference 2008 Conference Paper

Deterministic random walks on regular trees

• Joshua N. Cooper
• Benjamin Doerr
• Tobias Friedrich 0001
• Joel Spencer

SODA Conference 2008 Conference Paper

Quasirandom rumor spreading

• Benjamin Doerr
• Tobias Friedrich 0001
• Thomas Sauerwald

TCS Journal 2006 Journal Article

Improved bounds and schemes for the declustering problem

• Benjamin Doerr
• Nils Hebbinghaus
• Sören Werth

The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning range queries to higher-dimensional data. We give a declustering scheme with an additive error of O d ( log d - 1 M ) independent of the data size, where d is the dimension, M the number of storage devices and d - 1 does not exceed the smallest prime power in the canonical decomposition of M into prime powers. In particular, our schemes work for arbitrary M in dimensions two and three. For general d, they work for all M ⩾ d - 1 that are powers of two. Concerning lower bounds, we show that a recent proof of a Ω d ( log ( d - 1 ) / 2 M ) bound contains an error. We close the gap in the proof and thus establish the bound.

SODA Conference 2005 Conference Paper

Matrix rounding with low error in small submatrices

• Benjamin Doerr

TCS Journal 2004 Journal Article

European tenure games

• Benjamin Doerr

We study a variant of the tenure game introduced by Spencer (Theoret. Comput. Sci. 131 (1994) 415). In this version, faculty is not fired, but downgraded to the lowest rung instead. For the upper bound we give a potential function argument showing that the value v d of the game starting with d faculty on the first rung satisfies vd⩽⌊log 2 d+log 2 log 2 d+1. 98⌋. We prove a nearly matching lower bound of ⌊log 2 d+log 2 log 2 d⌋ using a strategy that can be interpreted as an antirandomization of Spencer's original game. For d tending to infinity, these bounds improve to ⌊log 2 d+log 2 log 2 d+1+o(1)⌋⩽vd⩽⌊log 2 d+log 2 log 2 d+1. 73+o(1)⌋. In particular, the set of all d∈N such that the value of the game is precisely ⌊log 2 d+log 2 log 2 d+1⌋ has lower density greater than 1 5.

MFCS Conference 2004 Conference Paper

Improved Bounds and Schemes for the Declustering Problem

• Benjamin Doerr
• Nils Hebbinghaus
• Sören Werth

Abstract The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed among the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning rectangular queries of higher-dimensional data. For this problem, we give a declustering scheme with an additive error of O d (log d − 1 M ) independent of the data size, where d is the dimension, M the number of storage devices and d -1 not larger than the smallest prime power in the canonical decomposition of M. Thus, in particular, our schemes work for arbitrary M in two and three dimensions, and arbitrary M ≥ d -1 that is a power of two. These cases seem to be the most relevant in applications. For a lower bound, we show that a recent proof of a \(\Omega_d(\log^{\frac{d-1}{2}} M)\) bound contains a critical error. Using an alternative approach, we establish this bound.

SODA Conference 2004 Conference Paper

Matrix rounding and approximation

• Benjamin Doerr

TCS Journal 2004 Journal Article

Typical rounding problems

• Benjamin Doerr

The linear discrepancy problem is to round a given [0, 1]-vector x to a binary vector y such that the rounding error with respect to a linear form is small, i. e. , such that ||A(x−y)||∞ is small for some given matrix A. The combinatorial discrepancy problem is the special case of x=( 1 2, …, 1 2 )t. A famous result of Beck and Spencer [Math. Programming 30 (1984) 88] as well as Lovász et al. [European J. Combin. 7 (1986) 151] shows that the linear discrepancy problem is not much harder than this special case: Any linear discrepancy problem can be solved with at most twice the maximum rounding error among the discrepancy problems of the submatrices of A. In this paper, we strengthen this result for the common situation that the discrepancy of submatrices having n 0 columns is bounded by Cn 0 α for some C>0, α∈]0, 1]. In this case, we improve the constant by which the general problem is harder than the discrepancy one from 2 down to 2( 2 3 )α. We also find that a random vector has expected linear discrepancy 2( 1 2 )αCnα only. Hence in the typical situation that the discrepancy is decreasing for smaller matrices, the linear discrepancy problem is even less difficult compared to the discrepancy one than assured by previous results. We also obtain the bound lindisc(A, x)⩽2(2 α /(21−α −1))C||x||1 α. Our proofs use a reduction to Pusher–Chooser games.

SODA Conference 2003 Conference Paper

Non-independent randomized rounding

• Benjamin Doerr

SODA Conference 2001 Conference Paper

Lattice approximation and linear discrepency of totally unimodular matrices

• Benjamin Doerr