Benjamin Doerr

Lower Bounds from Fitness Levels Made Easy

Benjamin Doerr, Timo KÃ¶tzing

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…

cs.NE2013

Evolutionary Algorithms and Dynamic Programming

Benjamin Doerr, Anton Eremeev, Frank Neumann +2

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…

cs.NE2012

Ranking-Based Black-Box Complexity

Benjamin Doerr, Carola Winzen

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing the…

cs.DS2010

Randomized Rounding for Routing and Covering Problems: Experiments and Improvements

Benjamin Doerr, Marvin KÃ¼nnemann, Magnus WahlstrÃ¶m

Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigat…

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 s…

Precise Runtime Analysis for Plateau Functions

Denis Antipov, Benjamin Doerr

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 natur…

The (1+ $I^»$ ) Evolutionary Algorithm with Self-Adjusting Mutation Rate

Benjamin Doerr, Christian GieÃen, Carsten Witt +1

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offs…

cs.DS2010

Quasirandom Rumor Spreading: An Experimental Analysis

Benjamin Doerr, Tobias Friedrich, Marvin KÃ¼nnemann +1

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…

Runtime Analysis for Permutation-based Evolutionary Algorithms

Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretic…

Fast Mutation in Crossover-based Algorithms

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

The heavy-tailed mutation operator proposed in Doerr, Le, Makhmara, and Nguyen (GECCO 2017), called \emph{fast mutation} to agree with the previously used language, so far was prov…

Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift

Benjamin Doerr

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) us…

cs.NE2019

An Exponential Lower Bound for the Runtime of the cGA on Jump Functions

Benjamin Doerr

In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multi-modal jump function class, HasenÃ¶hrl and Sutton (GECCO 2018) proved that the runtime of…

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 shortcom…

Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems

Benjamin Doerr, Pietro S. Oliveto, John Alasdair Warwicker

The Random Gradient hyper-heuristic was recently shown to be able to learn the optimal neighbourhood size when optimizing the LeadingOnes benchmark via the Randomised Local Search…

A Rigorous Runtime Analysis of the $(1 + (I^», I^»))$ GA on Jump Functions

Denis Antipov, Benjamin Doerr, Vitalii Karavaev

The $(1 + (I^», I^»))$ genetic algorithm is a younger evolutionary algorithm trying to profit also from inferior solutions. Rigorous runtime analyses on unimodal fitness functions sho…

Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives

Weijie Zheng, Benjamin Doerr

The theoretical understanding of MOEAs is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unim…

The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis

Benjamin Doerr, Martin S. Krejca

In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize…

Automated Algorithm Selection for Radar Network Configuration

Quentin Renau, Johann Dreo, Alain Peres +3

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…

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…

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

Abderrahim Bendahi, Benjamin Doerr, Adrien Fradin +1

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,…

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 populati…

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 on the search space from which good solutions can be sampled easily. A key parame…

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 sho…

cs.LG2019

Optimization of Chance-Constrained Submodular Functions

Benjamin Doerr, Carola Doerr, Aneta Neumann +2

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 th…

How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs

Benjamin Doerr, Arthur Dremaux, Johannes Lutzeyer +1

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…

cs.NE2010

Faster Black-Box Algorithms Through Higher Arity Operators

Benjamin Doerr, Daniel Johannsen, Timo KÃ¶tzing +3

We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary op…

math.NA2017

Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples

Benjamin Doerr, Carola Doerr, Michael Gnewuch

We provide probabilistic lower bounds for the star discrepancy of Latin hypercube samples. These bounds are sharp in the sense that they match the recent probabilistic upper bounds…

cs.DM2012

Strong Robustness of Randomized Rumor Spreading Protocols

Benjamin Doerr, Anna Huber, Ariel Levavi

Randomized rumor spreading is a classical protocol to disseminate information across a network. At SODA 2008, a quasirandom version of this protocol was proposed and competitive bo…

cs.CR2016

Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem

Benjamin Doerr, Marvin KÃ¼nnemann

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…

cs.NE2016

Optimal Parameter Settings for the $(1 + (I^», I^»))$ Genetic Algorithm

Benjamin Doerr

The $(1 + (I^», I^»))$ 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 u…

math.NA2013

A Lower Bound for the Discrepancy of a Random Point Set

Benjamin Doerr

We show that there is a constant $K > 0$ such that for all $N, s \in N$ , $s \leq N$ , the point set consisting of $N$ points chosen uniformly at random in the $s$ -dimensional unit c…

A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis

Benjamin Doerr, Joshua Knowles, Aneta Neumann +1

We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Bloc…

math.CO2004

Balanced Partitions of Vector Sequences

Imre BÃ¡rÃ¡ny, Benjamin Doerr

Let $d, r \in N$ , $∥ \cdot ∥$ any norm on $R^{d}$ and $B$ denote the unit ball with respect to this norm. We show that any sequence $v_{1}, v_{2}, ...$ of vectors in $B$ can be partition…

cs.NE2015

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

Benjamin Doerr, Carola Doerr, Timo KÃ¶tzing

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…

math.CO2006

Deterministic Random Walks on the Integers

Joshua Cooper, Benjamin Doerr, Joel Spencer +1

Jim Propp's P-machine, also known as the "rotor router model" is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly c…

cs.NE2015

A Tight Runtime Analysis of the $(1 + (I^», I^»))$ Genetic Algorithm on OneMax

Benjamin Doerr, Carola Doerr

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 mig…

From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm

Benjamin Doerr, Weijie Zheng

One of the key difficulties in using estimation-of-distribution algorithms is choosing the population size(s) appropriately: Too small values lead to genetic drift, which can cause…

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 acad…

Significance-based Estimation-of-Distribution Algorithms

Benjamin Doerr, Martin Krejca

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 qu…

math.PR2021

On Negative Dependence Properties of Latin Hypercube Samples and Scrambled Nets

Benjamin Doerr, Michael Gnewuch

We study the notion of $I^^{3}$ -negative dependence of random variables. This notion is a relaxation of the notion of negative orthant dependence (which corresponds to $1$ -negative dep…

General Univariate Estimation-of-Distribution Algorithms

Benjamin Doerr, Marc Dufay

We propose a general formulation of a univariate estimation-of-distribution algorithm (EDA). It naturally incorporates the three classic univariate EDAs \emph{compact genetic algor…

cs.NE2019

Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming

Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto

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,…

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 proble…

cs.DS2011

Playing Mastermind With Constant-Size Memory

Benjamin Doerr, Carola Winzen

We analyze the classic board game of Mastermind with $n$ holes and a constant number of colors. A result of ChvÃ¡tal (Combinatorica 3 (1983), 325-329) states that the codebreaker c…

Runtime Analysis for Self-adaptive Mutation Rates

Benjamin Doerr, Carsten Witt, Jing Yang

We propose and analyze a self-adaptive version of the $(1, I^»)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation…

cs.DS2006

Unbiased Matrix Rounding

Benjamin Doerr, Tobias Friedrich, Christian Klein +1

We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classic…

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 b…

stat.ML2026

Position: Don't be Afraid of Over-Smoothing And Over-Squashing

Niklas Kormann, Benjamin Doerr, Johannes F. Lutzeyer

Over-smoothing and over-squashing have been extensively studied in the literature on Graph Neural Networks (GNNs) over the past years. We challenge this prevailing focus in GNN res…

How Well Does the Metropolis Algorithm Cope With Local Optima?

Benjamin Doerr, Taha El Ghazi El Houssaini, Amirhossein Rajabi +1

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…

Towards Explainable Exploratory Landscape Analysis: Extreme Feature Selection for Classifying BBOB Functions

Quentin Renau, Johann Dreo, Carola Doerr +1

Facilitated by the recent advances of Machine Learning (ML), the automated design of optimization heuristics is currently shaking up evolutionary computation (EC). Where the design…

The Runtime of the Compact Genetic Algorithm on Jump Functions

Benjamin Doerr

In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, HasenÃ¶hrl and Sutton (GECCO 2018) showed for a…

A Fresh Look at Lamarckian Evolution and the Baldwin Effect

InÃ¨s Benito, Johannes F. Lutzeyer, Benjamin Doerr

Baldwinian and Lamarckian evolution have existed for a long time in evolutionary algorithms (EAs) without ever dominating the academic literature or practical applications. In this…

Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these v…

Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices

Benjamin Doerr, Carola Doerr

Parameter control aims at realizing performance gains through a dynamic choice of the parameters which determine the behavior of the underlying optimization algorithm. In the conte…

cs.NE2017

Fast Genetic Algorithms

Benjamin Doerr, Huu Phuoc Le, RÃ©gis Makhmara +1

For genetic algorithms 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 reall…

Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

Weijie Zheng, Benjamin Doerr

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 NS…

First Steps Towards a Runtime Analysis When Starting With a Good Solution

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

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 rando…

math.NA2019

The recovery of ridge functions on the hypercube suffers from the curse of dimensionality

Benjamin Doerr, Sebastian Mayer

A multivariate ridge function is a function of the form $f (x) = g (a^{T} x)$ , where $g$ is univariate and $a \in R^{d}$ . We show that the recovery of an un…

cs.DS2018

The Query Complexity of a Permutation-Based Variant of Mastermind

Peyman Afshani, Manindra Agrawal, Benjamin Doerr +3

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair $(z, I ¨ )$ which consists of a binary string $z \i…

cs.LG2025

HIEGNet: A Heterogenous Graph Neural Network Including the Immune Environment in Glomeruli Classification

Niklas Kormann, Masoud Ramuz, Zeeshan Nisar +6

Graph Neural Networks (GNNs) have recently been found to excel in histopathology. However, an important histopathological task, where GNNs have not been extensively explored, is th…

Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics

Benjamin Doerr, Martin S. Krejca, Nguyen Vu

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 t…

The $(1 + (I^», I^»))$ Global SEMO Algorithm

Benjamin Doerr, Omar El Hadri, Adrien Pinard

The $(1 + (I^», I^»))$ genetic algorithm is a recently proposed single-objective evolutionary algorithm with several interesting properties. We show that its main working principle, mut…

Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

Benjamin Doerr

We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected n…

Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

Marcel ChwiaÅkowski, Benjamin Doerr, Martin S. Krejca

The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another si…

Towards a Stronger Theory for Permutation-based Evolutionary Algorithms

Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretic…

cs.NE2010

Optimizing Monotone Functions Can Be Difficult

Benjamin Doerr, Thomas Jansen, Dirk Sudholt +2

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 m…

cs.NE2014

Unbiased Black-Box Complexities of Jump Functions

Benjamin Doerr, Carola Doerr, Timo KÃ¶tzing

We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we…

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

Mingfeng Li, Zheng Cheng, Weijie Zheng +1

Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime anal…

A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization

Benjamin Doerr, Frank Neumann

The theory of evolutionary computation for discrete search spaces has made significant progress in the last ten years. This survey summarizes some of the most important recent resu…

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 or…

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…

Speeding Up the NSGA-II via Dynamic Population Sizes

Benjamin Doerr, Martin S. Krejca, Simon Wietheger

Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-off…

Fixed-Target Runtime Analysis

Maxim Buzdalov, Benjamin Doerr, Carola Doerr +1

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization probl…

The Runtime of Random Local Search on the Generalized Needle Problem

Benjamin Doerr, Andrew James Kelley

In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on g…

Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions

The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function $f$ , but instead optimizes $N + 1$ single-object…

Bounding Bloat in Genetic Programming

Benjamin Doerr, Timo KÃ¶tzing, J. A. Gregor Lagodzinski +1

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 vari…

Hyper-Heuristics Can Profit From Global Variation Operators

Benjamin Doerr, Johannes F. Lutzeyer

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…

cs.DS2015

Simple and Optimal Randomized Fault-Tolerant Rumor Spreading

Benjamin Doerr, Carola Doerr, Shay Moran +1

We revisit the classic problem of spreading a piece of information in a group of $n$ fully connected processors. By suitably adding a small dose of randomness to the protocol of Ga…

(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, w…

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

Yasser Alghouass, Benjamin Doerr, Martin S. Krejca +1

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 (M…

cs.DS2011

Adaptive Drift Analysis

Benjamin Doerr, Leslie Ann Goldberg

We show that, for any c>0, the (1+1) evolutionary algorithm using an arbitrary mutation rate p_n = c/n finds the optimum of a linear objective function over bit strings of length n…

An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics

Henry Bambury, Antoine Bultel, Benjamin Doerr

Jump functions are the {most-studied} non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly im…

A First Runtime Analysis of the NSGA-II on a Multimodal Problem

Benjamin Doerr, Zhongdi Qu

Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted. We continue this line of research with a first run…

Lasting Diversity and Superior Runtime Guarantees for the $(I^¼ + 1)$ Genetic Algorithm

Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal +1

Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven wi…

math.NA2021

A Sharp Discrepancy Bound for Jittered Sampling

Benjamin Doerr

For $m, d \in N$ , a jittered sampling point set $P$ having $N = m^{d}$ points in $[0, 1)^{d}$ is constructed by partitioning the unit cube $[0, 1)^{d}$ into $m^{d}$ axis-aligned cu…

cs.NE2011

Multiplicative Drift Analysis

Benjamin Doerr, Daniel Johannsen, Carola Winzen

In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multipl…

cs.NE2017

Runtime Analysis of the $(1 + (I^», I^»))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas

Maxim Buzdalov, Benjamin Doerr

The $(1 + (I^», I^»))$ genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on so me optimization problems. The theoretical analysis so far was restri…

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 direct…

Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms

Benjamin Doerr, Weijie Zheng

Estimation of Distribution Algorithms (EDAs) are one branch of Evolutionary Algorithms (EAs) in the broad sense that they evolve a probabilistic model instead of a population. Many…

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

Weijie Zheng, Benjamin Doerr

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 of the bi-object…

A Tight Runtime Analysis for the $(I^¼ + I^»)$ EA

Denis Antipov, Benjamin Doerr

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challengin…

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…

cs.DS2012

Black-Box Complexity: Breaking the $O (n lo g n)$ Barrier of LeadingOnes

Benjamin Doerr, Carola Winzen

We show that the unrestricted black-box complexity of the $n$ -dimensional XOR- and permutation-invariant LeadingOnes function class is $O (n lo g (n) / lo g lo g n)$ . This shows tha…

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

Matthieu Dinot, Benjamin Doerr, Ulysse Hennebelle +1

In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can tolerate a certain amount of noise in the evaluation of the obj…

A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes

Benjamin Doerr, Martin 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 desirab…