BDBenjamin Doerr

Benjamin Doerr

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Benjamin Doerr has a total of 108 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • A Fresh Look at Lamarckian Evolution and the Baldwin Effect

    by Inès Benito, Johannes F. Lutzeyer, Benjamin Doerr

  • Open Access

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

    by Benjamin Doerr, Martin 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 only sporadic tight runtime analyses existing. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark. From this, we prove a lower bound of order Ω(n2 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(n2), improving over the previous estimate of O(n2 log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(nk+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. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Andre Opris: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm. International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8876–8884. [6].

  • Open Access

    Hot off the Press: Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy

    by 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,2k/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 ≥ 4 log2(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. This paper summarizes the work Mingfeng Li, Weijie Zheng and Benjamin Doerr: Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025. 8885–8893 [13].

  • Open Access

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

    by 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 [EQUATION]. 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. This and further results suggest that the best setting 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. This paper summarizes the work Renzhong Deng, Weijie Zheng, and Benjamin Doerr: The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8867–8875. [5].

  • Open Access

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

    by 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 focuses 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 log2 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. This paper summarizes the work Danyang Zhang, Zerong Zhong, Weijie Zheng, and Benjamin Doerr. 2026. Superior Runtime Guarantees for the MOEA/D Multi-Objective Optimizer via Weighted-Sum Decomposition. In AAAI Conference on Artificial Intelligence, AAAI 2026. AAAI Press, 37187–37194 [14].

  • Open Access

    Hot off the Press: Proven Approximation Superiority of SPEA2 over NSGA-II

    by Yasser Alghouass, Benjamin Doerr, Martin Krejca, Mohammad Lagmah

    The SPEA2 and the NSGA-II are two of the most widely used dominance-based multi-objective evolutionary algorithms (MOEAs). While prior theoretical work established similar runtime guarantees for both, the differences in their selection mechanisms were not well understood from an approximation perspective. We provide the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability. Specifically, the steady-state SPEA2 computes an optimal spread of the OneMinMax Pareto front in O(μ2n log(μ;) log(n)) expected function evaluations. In contrast, the steady-state NSGA-II, when started near an optimal spread with just two sub-optimal gaps, fails to achieve optimality within polynomial time with overwhelming probability. This is the first result showing a provable qualitative gap between the approximation abilities of these two algorithms. This paper summarizes the work Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. International Joint Conference on Artificial Intelligence, IJCAI 2025. [1].