Jul 2026· Proceedings of the Genetic and Evolutionary Computation Conference Companion· pp. 87-88· 0 citations· 19 references
TL;DR
This first complete mathematical runtime analysis for the MOEA/D using the original weighted-sum decomposition shows 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.
Abstract
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].
The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(nk+d/2 +μn ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size μ ∈ 2O(n) is at least (2n/d + 1)d/2. Notably, NSGA-III is faster than NSGA-II by a factor of μ/nd/2 for some μ ∈ ω(nd/2). We also show that a stochastic population update, proposed by Bian et al. [1], provably guarantees a speedup of order Θ((k/b)k-1) in the runtime where b > 0 is a constant. Besides [15], this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved. This Hot-off-the-Press paper summarises the work Andre Opris. 2025. A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, Article No.: 990, Pages 8903 - 8911, 2025 [9].
Andre Opris· Proceedings of the Genetic a...· 11 citations
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 μ ≥ n - 2k + 3 and offspring population size λ computes the Pareto front of the OneJumpZeroJump benchmark with gap size k in O((λ + μ;)n + nk+1) expected function evaluations. This shows that the best runtime guarantee of O(nk+1) is not only achieved for μ; = Θ(n) and λ = O(n) but for arbitrary μ;, λ = O(nk). Thus, choosing suitable parameters - a key challenge in using heuristic algorithms - is much easier for the SPEA2 than the NSGA-II. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Milan Stanković: Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer. Conference on Artificial Intelligence, AAAI 2026. AAAI Press. 36855–36863. [10].
Benjamin Doerr, Martin S. Krejca, Milan Stanković· Proceedings of the Genetic a...· 0 citations
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].
Benjamin Doerr, Martin S. Krejca, Andre Opris· Proceedings of the Genetic a...· 0 citations
Diversity optimization is the class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently-used approaches to solve such problems is evolutionary diversity optimization (EDO). In this paper, we analyze EDO on a three-objective function LOTZk, which is a modification of the two-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in O(kn3) expected iterations. We also analyze the runtime of the GSEMOD algorithm (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures: the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMOD optimizes it in O(kn2 log(n)) expected iterations (which is asymptotically faster than the upper bound on the runtime until it finds a Pareto-optimal population), and for the second measure we show an upper bound of O(k2n3 log(n)) expected iterations. The complementary empirical study shows a very similar behavior for both diversity measures. The results of experiments suggest that our bounds for the total imbalance measure are tight, while the bounds for the imbalances vector are too pessimistic. This paper summarizes the work Denis Antipov, Aneta Neumann, Frank Neumann and Andrew M. Sutton: Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem. Evolutionary Computation, 1–23, 2025. [2].
D. Antipov, Aneta Neumann, Frank Neumann et al.· Proceedings of the Genetic a...· 0 citations
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(n2 log n) fitness evaluations to compute an additive ε-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. This paper summarizes the work Mingfeng Li, Qiang Zhang, Weijie Zheng and Benjamin Doerr: Why Popular MOEAs Are Popular: Proven Advantages in Approximating the Pareto Front. Advances in Neural Information Processing Systems, NeurIPS 2025. [15].
Mingfeng Li, Qiang Zhang, Weijie Zheng et al.· Proceedings of the Genetic a...· 0 citations
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].
Yasser Alghouass, Benjamin Doerr, Martin S. Krejca et al.· Proceedings of the Genetic a...· 0 citations
