Speeding Up the NSGA-II via Dynamic Population Sizes

Benjamin Doerr, Martin S. Krejca, Simon Wietheger · 2025

Read Speeding Up the NSGA-II via Dynamic Population Sizes by Benjamin Doerr, Martin S. Krejca, Simon Wietheger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01739.txt.

Introduction

Benjamin Doerr, Martin S Krejca, and Simon Wietheger speed up a well known optimizer that juggles two goals at once. Such optimizers keep many candidate answers to hold all best trade-offs, called Pareto optima. Large fixed groups slow the search, and picking the group size is a key choice. Their variant starts small and doubles the group after a set number of tries.

Proofs show the growing group finds the full trade-off front much faster on a standard test problem. A second test with a gap also runs faster than the fixed version. A tweak that lingers longer at small sizes does slightly better still. Running copies side by side removes the need to set sizes by hand.

Catalog record

CREATORBenjamin Doerr, Martin S. Krejca, Simon Wietheger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01739

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Speeding Up the NSGA-II via Dynamic Population Sizes Benjamin Doerr, Martin S. Krejca, Simon Wietheger Abstract Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima ) at once, MOEAs are typically run with a large, static population of solution candidates, which can slow down the algorithm. We propose the dynamic NSGA-II ( dNSGA-II ), which is based on the popular NSGA-II and features a non-static population size. The dNSGA-II starts with a small initial population size of four and doubles it after a user-specified number τ \tau of function evaluations, up to a maximum size of μ \mu . Via a mathematical runtime analysis, we prove that the dNSGA-II with parameters μ ≥ 4 ​ ( n + 1 ) \mu\geq 4(n+1) and τ ≥ 256 50 ​ e ​ n \tau\geq\frac{256}{50}en computes the full Pareto front of the OneMinMax benchmark of size n n in O ⁡ ( log ⁡ ( μ ) ​ τ + μ ​ log ⁡ ( n ) ) O(\log(\mu)\tau+\mu\log(n)) function evaluations, both in expectation and with high probability. For an optimal choice of μ \mu and τ \tau , the resulting O ⁡ ( n ​ log ⁡ ( n ) ) O(n\log(n)) runtime improves the optimal expected runtime of the classic NSGA-II by a factor of Θ ⁡ ( n ) \Theta(n) . In addition, we show that the parameter τ \tau can be removed when utilizing concurrent runs of the dNSGA-II . This approach leads to a mild slow-down by a factor of O ⁡ ( log ⁡ ( n ) ) O(\log(n)) compared to an optimal choice of τ \tau for the dNSGA-II , which is still a speed-up of Θ ⁡ ( n / log ⁡ ( n ) ) \Theta(n/\log(n)) over the classic NSGA-II. Introduction Real-world problems often require the optimization of conflicting objectives, resulting in several incomparable optimal trade-offs, known as Pareto optima . Due to their incomparable nature, it is desirable to quickly find as many Pareto optima as possible—ideally all of them, called the Pareto front . Multi-objective evolutionary algorithms (MOEAs) lend themselves well to this task, as they maintain a population of multiple solution candidates at once. Hence, MOEAs are among the most widely and effectively applied approaches in multi-objective optimization ( Coello, Lamont, and van Veldhuizen 2007 ; Zhou et al. 2011 ) . Recently, the empirical success of popular state-of-the-art MOEAs, such as the NSGA-II ( Deb et al. 2002 ) , NSGA-III ( Deb and Jain 2014 ) , SMS-EMOA ( Beume, Naujoks, and Emmerich 2007 ) , MOEA/D ( Zhang and Li 2007 ) , or SPEA2 ( Zitzler, Laumanns, and Thiele 2001 ) , has been complemented by theoretical analyses, e.g., ( Zheng, Liu, and Doerr 2022 ; Wietheger and Doerr 2023 ; Zheng and Doerr 2024b ; Li et al. 2016 ; Ren et al. 2024 ) . Such analyses do not only provide us with rigorous performance guarantees for MOEAs but also with insights into their merits and shortcomings. As a result, theoretically motivated and provably improved MOEAs have been presented, e.g., by Bian et al. 2023 and Doerr, Ivan, and Krejca 2025 . Despite the large variety of MOEAs, the mathematical performance guarantees that we have for simple benchmark problems is often asymptotically the same. Wietheger and Doerr 2024 even state a meta theorem that applies to a plethora of MOEAs and results in the same, well-known performance guarantees. For the simple OneMinMax ( OMM ) benchmark ( Giel and Lehre 2010 ) of size n —the most popular MOEA theory benchmark, typically considered first when conducting a runtime analysis—the common runtime for an MOEA with a (static) population of size \mu is O(\mu n\log(n)) , with the restriction \mu\geq C(n+1) , for some constant C\geq 1 . This bound applies to the expected number of function evaluations until the population of the MOEA witnesses the entire Pareto front of OMM for the first time. The constraint \mu\geq C(n+1) is a consequence of requiring that the population can represent the entire Pareto front of OMM , which has size n+1 . Hence, an optimal choice of \mu results in a bound of O(n^{2}\log(n)) . For the NSGA-II, this bound is tight ( Doerr and Qu 2023 ) , and there is little room to believe that it is not close to optimal for the other commonly studied MOEAs as well. We note that the bound O(n^{2}\log(n)) for optimal \mu even holds for a recently improved NSGA-II version ( Doerr, Ivan, and Krejca 2025 ) . Since the Pareto front of OMM has a size linear in the problem size n , it may seem that a runtime performance of O(n^{2}\log(n)) is reasonable. However, the closely related single-objective OneMax problem can be solved by (single-objective) evolutionary algorithms (EAs) in an expected time of \Theta(n\log(n)) ( Droste, Jansen, and Wegener 2002 ) , where the trajectory of the algorithm is in some sense comparable to that of many MOEAs. In particular, reaching the extremal points of the Pareto front of OMM is closely related to finding the optimum of OneMax , the latter of which has a widely applicable lower bound of \Omega(n\log(n)) for a variety of EAs ( Lehre and Witt 2012 ) . The slow-down of MOEAs in comparison to single-objective EAs lies in the large population of the MOEAs, which needs to accommodate the entire Pareto front of the problem. Single-objective EAs with a \Theta(n\log(n)) performance on OneMax use only very few (often only a single) solutions, which are updated. In contrast, MOEAs have an at least linear population size on OMM . This in itself is not immediately detrimental, but this large population is likely to be clustered. Consequently, only few solutions exist that easily lead to new, improving solutions. This results in a lot of wasted function evaluations in each iteration. A natural way to circumvent the problem stemming from a large population size is to reduce the population size while still keeping track of all Pareto optima. One popular way of doing this is to maintain an archive , which is an external memory that contains all best-so-far solutions in a look-up table while not using them explicitly in the run of the algorithm. We elaborate on archives in the following section. Another, far less popular, strategy is to adjust the population size of an MOEA during the run. We note that for single-objective problems, it is known that dynamic updates to the population size can result in provable speed-ups over static choices ( Doerr and Doerr 2018 ) , whereas no such result is currently known for the multi-objective domain. Our contribution. We introduce the dynamic NSGA-II ( dNSGA-II , Algorithm 1 ), which is based on the NSGA-II and adjusts its population size over time. For the OMM benchmark, we prove that the dNSGA-II is faster up to a factor of \Theta(n) than the classic NSGA-II ( Theorem 2 ). The dNSGA-II runs a variant of the classic NSGA-II with an initial population of size four and then doubles its population periodically in phases

Read the complete text