Benjamin Doerr

research

∙ 05/22/2023

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

The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the m...

0 Sacha Cerf, et al. ∙

research

∙ 05/17/2023

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

In single-objective optimization, it is well known that evolutionary alg...

0 Matthieu Dinot, et al. ∙

research

∙ 05/08/2023

Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise

Evolutionary algorithms are known to be robust to noise in the evaluatio...

0 Alexandra Ivanova, et al. ∙

research

∙ 04/21/2023

How Well Does the Metropolis Algorithm Cope With Local Optima?

The Metropolis algorithm (MA) is a classic stochastic local search heuri...

0 Benjamin Doerr, et al. ∙

research

∙ 04/20/2023

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

In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligenc...

0 Benjamin Doerr, et al. ∙

research

∙ 03/20/2023

Randomized Rumor Spreading Revisited (Long Version)

We develop a simple and generic method to analyze randomized rumor sprea...

0 Benjamin Doerr, et al. ∙

research

∙ 03/13/2023

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

Recently it has been proven that simple GP systems can efficiently evolv...

0 Benjamin Doerr, et al. ∙

research

∙ 02/28/2023

Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables

With apparently all research on estimation-of-distribution algorithms (E...

0 Firas Ben Jedidia, et al. ∙

research

∙ 02/24/2023

Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm

Most evolutionary algorithms (EAs) used in practice employ crossover. In...

0 Benjamin Doerr, et al. ∙

research

∙ 02/16/2023

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus

We propose a new method based on discrete Fourier analysis to analyze th...

0 Benjamin Doerr, et al. ∙

research

∙ 11/23/2022

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

The NSGA-II is one of the most prominent algorithms to solve multi-objec...

0 Weijie Zheng, et al. ∙

research

∙ 11/15/2022

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

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most pro...

0 Simon Wietheger, et al. ∙

research

∙ 10/07/2022

The (1+(λ,λ)) Global SEMO Algorithm

The (1+(λ,λ)) genetic algorithm is a recently proposed single-objective ...

0 Benjamin Doerr, et al. ∙

research

∙ 09/28/2022

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

Due to the more complicated population dynamics of the NSGA-II, none of ...

0 Benjamin Doerr, et al. ∙

research

∙ 08/18/2022

The First Mathematical Proof That Crossover Gives Super-Constant Performance Gains For the NSGA-II

Very recently, the first mathematical runtime analyses for the NSGA-II, ...

0 Benjamin Doerr, et al. ∙

research

∙ 07/05/2022

Runtime Analysis for Permutation-based Evolutionary Algorithms

While the theoretical analysis of evolutionary algorithms (EAs) has made...

0 Benjamin Doerr, et al. ∙

research

∙ 06/22/2022

General Univariate Estimation-of-Distribution Algorithms

We propose a general formulation of a univariate estimation-of-distribut...

0 Benjamin Doerr, et al. ∙

research

∙ 06/18/2022

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

Estimation-of-distribution algorithms (EDAs) are optimization algorithms...

0 Weijie Zheng, et al. ∙

research

∙ 05/07/2022

Automated Algorithm Selection for Radar Network Configuration

The configuration of radar networks is a complex problem that is often p...

0 Quentin Renau, et al. ∙

research

∙ 04/28/2022

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

Very recently, the first mathematical runtime analyses of the multi-obje...

0 Zhongdi Qu, et al. ∙

research

∙ 04/15/2022

Towards a Stronger Theory for Permutation-based Evolutionary Algorithms

While the theoretical analysis of evolutionary algorithms (EAs) has made...

0 Benjamin Doerr, et al. ∙

research

∙ 04/05/2022

Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem

We prove that Simulated Annealing with an appropriate cooling schedule c...

0 Benjamin Doerr, et al. ∙

research

∙ 03/05/2022

Better Approximation Guarantees for the NSGA-II by Using the Current Crowding Distance

A recent runtime analysis (Zheng, Liu, Doerr (2022)) has shown that a va...

0 Weijie Zheng, et al. ∙

research

∙ 01/28/2022

Stagnation Detection meets Fast Mutation

Two mechanisms have recently been proposed that can significantly speed ...

0 Benjamin Doerr, et al. ∙

research

∙ 12/16/2021

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

The non-dominated sorting genetic algorithm II (NSGA-II) is the most int...

0 Weijie Zheng, et al. ∙

research

∙ 09/14/2021

Choosing the Right Algorithm With Hints From Complexity Theory

Choosing a suitable algorithm from the myriads of different search heuri...

0 Shouda Wang, et al. ∙

research

∙ 05/07/2021

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

Jump functions are the most studied non-unimodal benchmark in the theory...

0 Henry Bambury, et al. ∙

research

∙ 04/21/2021

On Negative Dependence Properties of Latin Hypercube Samples and Scrambled Nets

We study the notion of γ-negative dependence of random variables. This n...

0 Benjamin Doerr, et al. ∙

research

∙ 04/14/2021

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

Most evolutionary algorithms have multiple parameters and their values d...

0 Denis Antipov, et al. ∙

research

∙ 04/07/2021

Lower Bounds from Fitness Levels Made Easy

One of the first and easy to use techniques for proving run time bounds ...

0 Benjamin Doerr, et al. ∙

research

∙ 03/29/2021

A Sharp Discrepancy Bound for Jittered Sampling

For m, d ∈ℕ, a jittered sampling point set P having N = m^d points in [0...

0 Benjamin Doerr, et al. ∙

research

∙ 02/01/2021

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

Facilitated by the recent advances of Machine Learning (ML), the automat...

0 Quentin Renau, et al. ∙

research

∙ 12/14/2020

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

Previous theory work on multi-objective evolutionary algorithms consider...

0 Benjamin Doerr, et al. ∙

research

∙ 07/16/2020

The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis

In their recent work, Lehre and Nguyen (FOGA 2019) show that the univari...

0 Benjamin Doerr, et al. ∙

research

∙ 06/30/2020

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

The theory of evolutionary computation for discrete search spaces has ma...

21 Benjamin Doerr, et al. ∙

research

∙ 06/22/2020

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

The mathematical runtime analysis of evolutionary algorithms traditional...

0 Denis Antipov, et al. ∙

research

∙ 06/19/2020

Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy

Exploratory landscape analysis (ELA) supports supervised learning approa...

0 Quentin Renau, et al. ∙

research

∙ 06/08/2020

Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

We use an elementary argument building on group actions to prove that th...

0 Benjamin Doerr, et al. ∙

research

∙ 06/05/2020

Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions

It was recently observed that the (1+(λ,λ)) genetic algorithm can compar...

0 Denis Antipov, et al. ∙

research

∙ 05/02/2020

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

A decent number of lower bounds for non-elitist population-based evoluti...

0 Benjamin Doerr, et al. ∙

research

∙ 04/20/2020

Fixed-Target Runtime Analysis

Runtime analysis aims at contributing to our understanding of evolutiona...

0 Maxim Buzdalov, et al. ∙

research

∙ 04/15/2020

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

One of the key difficulties in using estimation-of-distribution algorith...

0 Benjamin Doerr, et al. ∙

research

∙ 04/14/2020

The (1 + (λ, λ)) GA Is Even Faster on Multimodal Problems

The (1 + (λ,λ)) genetic algorithm is a recent invention of the theory co...

0 Denis Antipov, et al. ∙

research

∙ 04/14/2020

Fast Mutation in Crossover-based Algorithms

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017)...

0 Denis Antipov, et al. ∙

research

∙ 04/13/2020

Exponential Upper Bounds for the Runtime of Randomized Search Heuristics

We argue that proven exponential upper bounds on runtimes, an establishe...

0 Benjamin Doerr, et al. ∙

research

∙ 04/10/2020

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

With elementary means, we prove a stronger run time guarantee for the un...

0 Benjamin Doerr, et al. ∙

research

∙ 04/02/2020

Does Comma Selection Help To Cope With Local Optima

One hope of using non-elitism in evolutionary computation is that it aid...

0 Benjamin Doerr, et al. ∙

research

∙ 11/26/2019

Optimization of Chance-Constrained Submodular Functions

Submodular optimization plays a key role in many real-world problems. In...

0 Benjamin Doerr, et al. ∙

research

∙ 10/31/2019

Sharp Bounds for Genetic Drift in EDAs

Estimation of Distribution Algorithms (EDAs) are one branch of Evolution...

0 Benjamin Doerr, et al. ∙

research

∙ 08/18/2019

The Runtime of the Compact Genetic Algorithm on Jump Functions

In the first and so far only mathematical runtime analysis of an estimat...

0 Benjamin Doerr, et al. ∙

Benjamin Doerr

Featured Co-authors