This paper introduces the bi-objective problem class CLIMB and analyzes the runtime of GSEMO and the widely used NSGA-II on this problem, and proves that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes, can find the Pareto front of CLIMB in expected fitness evaluations.
Abstract
This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class CLIMB and analyze the runtime of GSEMO and the widely used NSGA-II on this problem. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a speedup of order $\Omega(\sqrt{n}/\log n)$. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes we propose in this paper, can find the Pareto front of CLIMB in expected $O(n \log n)$ fitness evaluations, whereas NSGA-II with a fixed population size requires $\Omega(n^{1.5})$ fitness evaluations in expectation. To the best of our knowledge, this is the first rigorous runtime analysis in multi-objective optimization demonstrating a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, like the evolution of population diversity over time, and employs the well-known family-three method to prove the lower bound.
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
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
Evolutionary algorithms (EAs) have been widely and successfully applied to solve multi-objective optimization problems, due to their nature of population-based search. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. In this paper, we analytically present that stochastic population update can be beneficial for the search of MOEAs. Specifically, we prove that the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, for solving two bi-objective problems, OneJumpZeroJump and bi-objective RealRoyalRoad, can be exponentially decreased if replacing its deterministic population update mechanism by a stochastic one. Empirical studies also verify the effectiveness of the proposed population update method. This work is an attempt to show the benefit of introducing randomness into the population update of MOEAs. Its positive results, which might hold more generally, should encourage the exploration of developing new MOEAs in the area. This paper for the Hot-off-the-Press track at GECCO 2025 summarizes the work C. Bian, Y. Zhou, M. Li, and C. Qian. Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms. Artificial Intelligence, 2025, 341: 104308. [5]
Chao Bian, Yawen Zhou, Miqing Li et al.· Proceedings of the Genetic a...· 0 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
Evolutionary algorithms (EAs) are popular for multi-objective optimization due to their population-based nature. While population updates in multi-objective EAs (MOEAs) are typically greedy and deterministic. However, recent studies have questioned this practice and shown that stochastic population update (SPU), which allows inferior solutions have a chance to be preserved, can help MOEAs jump out of local optima more easily. Nevertheless, SPU risks losing high-quality solutions, potentially requiring a large population. Intuitively, a possible solution to this issue is to introduce an archive that stores the best solutions ever found. This paper theoretically demonstrates that incorporating an archive to store best-found solutions enables smaller populations and enhances SPU-based MOEA performance. Analyzing SMS-EMOA and NSGA-II on the bi-objective OneJumpZeroJump problem, we prove archives reduce expected running time upper bounds (even exponentially). The comparison between SMS-EMOA and NSGA-II also suggests that the (μ + μ) update mode may be more suitable for SPU than the (μ + 1) update mode. We also validate our findings empirically. This paper for the Hot-off-the-Press track at GECCO 2026 sum marizes the work S. Ren, Z. Liang, M. Li, and C. Qian. A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization. IJCAI, 2025, 8921: 8929. [17]
Shengjie Ren, Zimin Liang, Miqing Li et al.· Proceedings of the Genetic a...· 0 citations
This paper compares six different strategies identified in a recent survey, categorizing them as either global strategies (GS), which treat the decision vector as a unified type, or decomposition-based strategies (DS), which split the problem into continuous and discrete subproblems.
Thomas Lang, Denis Pallez· Proceedings of the Genetic a...· 0 citations
