Speeding Up the NSGA-II via Dynamic Population Sizes

1 Introduction

Real-world problems often require the optimization of conflicting objectives, resulting in several incomparable optimal trade-offs, known as Pareto optima. One solution concept for such multi-objective optimization problems is to compute several Pareto optima, ideally all of them (the Pareto front), and let a decision maker select the final solution. Multi-objective evolutionary algorithms (MOEAs) are a natural choice for this task as they usually work with sets of solutions (populations) and, in fact, MOEAs are among the most successful and widely applied approaches in multi-objective optimization [Coello et al., 2007; Zhou et al., 2011].

Recently, the empirical success of popular state-of-theart MOEAs, such as the NSGA-II [Deb et al., 2002], NSGA-III [Deb and Jain, 2014], SMS-EMOA [Beume et al., 2007], MOEA/D [Zhang and Li, 2007], or SPEA2 [Zitzler et al., 2001], has been supported by the first mathematical analyses of these algorithms [Zheng et al., 2022; Wietheger and Doerr, 2023; Bian et al., 2023; Li et al., 2016; Ren et al., 2024]. This not only gave rigorous performance guarantees for MOEAs but also led to deeper insights into their merits and shortcomings. As a result, theoretically motivated and provably improved MOEAs have been presented, e.g., in [Bian et al., 2023; Doerr et al., 2025a]. We aim at this as well, for the most prominent MOEA, the NSGA-II.

When analyzing the mathematical runtime analyses of the NSGA-II, we observe an ambivalent role of the population size N, the main parameter of this algorithm. On the one hand, the population size must be large enough to represent the Pareto front (and, in fact, a little larger, since the algorithm fails to perfectly efficiently cover the Pareto front) [Zheng and Doerr, 2023]. On the other hand, since the NSGA-II generates and evaluates N solutions per iteration, a large N slows down the algorithm. This effect was made precise in [Doerr and Qu, 2023b]. These two insights, together with the details of the proofs in these works, suggest to design an NSGA-II that gradually increases the population size.

Our contribution. We propose the dynamic NSGA-II (Algorithm 2), which is an NSGA-II that starts with a small population of size four and doubles it after a user-specified number τ of function evaluations, but not beyond a maximum population size Nmax. This second main parameter of the algorithm plays a similar role as the population size N of the classic NSGA-II, in particular, it has to be large enough for the algorithm to eventually cover the Pareto front. Since both empirical [Kukkonen and Deb, 2006] and mathematical [Zheng and Doerr, 2025] results have shown that it is preferable to select the next population of the NSGA-II sequentially, always based on the current crowding distance at that moment, we use this variant of the NSGA-II.

We analyze mathematically the performance of this dynamic NSGA-II on two standard benchmarks from the theory of MOEAs. For the OneMinMax benchmark (denoted here by OMM), we show that our algorithm with optimal parameters with high probability finds the Pareto front within O(n log2 n) function evaluations (Theorem 1). This is considerably faster than the O(n2 logn) best runtime guarantees known for the standard versions of the NSGA-II, NSGA-III, SMS-EMOA, SPEA2, and MOEA/D with optimal parameters [Zheng and Doerr, 2023; Dang et al., 2023; Zheng and Doerr, 2024; Ren et al., 2024; Li et al., 2016], proven to be asymptotically tight for the NSGA-II [Doerr and Qu, 2023b]. For the OneJumpZeroJump benchmark (OJZJk) with difficulty parameter k ∈ [2..⌊ n2 ⌋], we prove that the dynamic NSGA-II with optimal parameters satisfies a runtime guarantee of O(nk log2 n) function evaluations with high probability (Theorem 4). Except for very large values of k, this compares again favorably with the best known runtime guarantee of O((n-2k)nk ) for the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2 [Doerr and Qu, 2023a; Opris, 2025; Bian et al., 2023; Ren et al., 2024], which is again tight for the classic NSGA-II [Doerr and Qu, 2023b]; we are not aware of any runtime analysis of the MOEA/D on OJZJ. Both of our runtime guarantees are independent of the maximum population size Nmax as long as this is at least slightly larger than the size of the Pareto front.

Noting that the optimal choice of the doubling parameter τ is mostly determined by the part of the optimization process working with the initial population size, we also propose a variant of the dynamic NSGA-II that allows for a longer initial phase. For this dynamic NSGA-II with longer initial phase, we set the length of the initial phase in such a manner that it takes as long as all later phases combined until the maximum population size is reached. This significantly increases the time spent with a small population without increasing the asymptotic order of the runtime. In our runtime analysis, we show that this variant allows for a smaller doubling factor (for all but this initial phase), resulting in slightly superior runtimes (Theorems 5 and 6), e.g., an O(n log n) runtime on OMM, which is asymptotically optimal in a large class of unbiased black-box algorithms [Lehre and Witt, 2012].

Our results described so far stated the performance for an optimal choice of the doubling parameter τ. They display a linear dependence on τ when τ is at least of a certain size. Below this, the runtime essentially reverts to the one of the classic NSGA-II with population size Nmax. In that sense, a suboptimal choice of τ is not fatal, but the advantage of the dynamic choice of the population size could decrease or vanish. To relieve the user from manually optimizing τ, we propose a simple concurrent-run strategy (Algorithm 3) that removes the parameter τ from the algorithm at the price of a runtime that is by a logarithmic factor larger than the runtime obtainable with the optimal choice of τ (Theorem 7). This strategy works both for the dynamic NSGA-II and its variant with longer initial phase. Since the runtime of the former was independent of Nmax, we obtain here a version of the NSGA-II that has no parameters related to the population size.

Note. All proofs are available at [Doerr et al., 2025b].

2 RelatedWork

Doubling schemes have been considered for single-objective evolutionary optimization, e.g., [Harik and Lobo, 1999;

Doerr and Doerr, 2020]. To the best of our knowledge, this work is the first to study a MOEA with dynamic parameters via mathematical means, and our findings heavily rely on the multi-objective nature of the considered problems. In such, there is little directly related work to be discussed here.

What comes closest to our work are the recent works that study how to run a MOEA with a smaller population size with the help of an archive. An archive is a storage for good solution candidates that do not take part in the evolutionary process. This way, good solutions can be stored outside the main population of the MOEA, possibly allowing the MOEA to be run with a smaller population size. We refer to [Li et al., 2024] for a recent general survey on this technique and review the two independent theoretical works on this topic.

[Bian et al., 2024] consider the NSGA-II with an archive. They prove that this algorithm optimizes the OMM and LOTZ benchmark in O(n log n) and O(n2 ) function evaluations, respectively, when a constant population size is chosen. To achieve these runtimes, the analysis relies on an intensive use of one-point crossover. This is natural for a problem like LOTZ, but less natural for a problem like OMM, in which there is no particular order of the bits. We are very skeptical that the NSGA-II with archive and constant population size can optimize the OMM or OJZJk benchmarks without this type of crossover. All results proven in this work hold if each parent in each iteration has a constant chance to receive mutation only, allowing arbitrary use of crossover otherwise.

[Doerr et al., 2024a] consider the MOEA/D, which by definition uses an archive. Their main result is that the mutationonly MOEA/D with a population size smaller than the Pareto front size has enormous difficulties finding the Pareto front of OMM when bit-wise mutation is used. However, when a heavy-tailed mutation operator (having a higher sampling variance) is used, smaller population sizes are admissible and lead to considerably better runtimes. More precisely, for N = O(nβ-1 ) the runtime becomes O(nβ log n), where the constant β > 1 is the exponent of the power-law distribution used to define the mutation operator. By choosing β small, runtimes of O(n1+ε ) can be obtained. Building on this work, [Corus et al., 2025] showed that the MOEA/D with Fast Contiguous Somatic Hypermutation can optimize OMM in a runtime of order O(n log n). The MOEA/D with constant population size and one-point crossover was shown to optimize OMM in time O(n log n) in [Huang et al., 2021].

From these results and our understanding of the proofs, we tend to believe that working with a growing population size is slightly preferable to an archive. Since the solutions in the archive can never be used to generate new solutions, there is a considerable risk (as proven in the bit-wise mutation setting regarded in [Doerr et al., 2024b]) that the few solutions in the population are not sufficient to reach all solutions on the Pareto front. That said, a dynamic population size requires choosing the right growth schedule for the population.

3 Preliminaries

Let N denote the positive natural numbers, and N0 := {0}∪N. For i, j ∈ N0, let [i..j] := [i, j] ∩N0, [i] := [1..i], and [i]0 := [0..i]. We abbreviate log2(x) to log(x) and loge(x) to ln(x).

We consider pseudo-Boolean maximization, that is, for a given n ∈ N, we study functions f : {0, 1}n → R2 . We call each x ∈ {0, 1}n an individual and f(x) =: (f1(x), f2(x)) its objective value. Furthermore, for all x ∈ {0, 1}n , we denote the number of ones of x by |x|1.

We compare objective values u, v ∈ R2 via the domination partial order ⪰. We say u weakly dominates v (u ⪰ v) if u1 ≥ v1 and u2 ≥ v2; and u and v are incomparable if neither u ⪰ v nor v ⪰ u. If and only if u ⪰ v and u ̸= v, we say u strictly dominates v (u ≻ v). We use domination also for individuals, referring to domination of their objective values.

For a function f, we call each x ∈ {0, 1}n Pareto-optimal if and only if no y ∈ {0, 1}n satisfies f(y) ≻ f(x). For each Pareto-optimal x ∈ {0, 1}n , we call f(x) a Pareto optimum. The Pareto front is the set of all Pareto optima.

The ONEMINMAX Benchmark

We consider the ONEMINMAX (OMM) benchmark function [Giel and Lehre, 2010], which is the most commonly studied benchmark in the theory of MOEAs. OMM features two conflicting objectives: the first returns the number of zeros in a given individual, the second its number of ones. Formally, we have OMM: {0, 1}n → [n]20 with x ↦→ (n - |x|1, |x|1).

Due to the conflicting objectives, all individuals are Paretooptimal, and the Pareto front is {(i, n- i) | i ∈ [n]0}.

The ONEJUMPZEROJUMP Benchmark

As a second benchmark function, we consider ONEJUMPZEROJUMP (OJZJk) [Doerr and Zheng, 2021], which is based on the commonly studied single-objective benchmark JUMP [Droste et al., 2002] benchmark. Similar to OMM, OJZJk features two conflicting objectives that try to maximize the number of ones and zeros, respectively. However, given a hardness parameter k ∈ [⌊ n2 ⌋], both objectives have low values for numbers of ones (zeros) which are at a distance of 1 to k to the maximum number n, requiring the population to jump across this valley of small objective values. Formally, we have OJZJk : {0, 1}n → [n + k]20 with x ↦→ (JUMPk(x), ZEROJUMPk(x)), where

and ZEROJUMPk is like JUMPk, swapping ones and zeros.

Individuals in the valley of low objective values are not Pareto-optimal, and the Pareto front is {(n + k, 0), (0, n +

k)} ∪ {(i + k, n - i + k) | i ∈ N, k ≤ i ≤ n - k}. We call the objective values (n+k, 0) and (0, n+k) the outer Pareto front, and the remaining Pareto front the inner Pareto front.

Throughout this work, when we mention OMM or OJZJk, we assume that the problem size n ∈ N is given. Our mathematical statements aim at asymptotics in terms of this n, implying that we may assume n to be sufficiently large.

Runtime

During the run of an MOEA, we assume that the objective value of an individual is evaluated exactly once-at the point of its creation. Hence, each potential copy of an individual is also evaluated exactly once. The runtime of an MOEA is the (random) number of function evaluations until the current multi-set of individuals that the MOEAmaintains (its population) covers the Pareto front for the first time, that is, until the objective values of the population contain the Pareto front.

Empty Intervals

Given a population P of individuals not covering the Pareto front of the chosen benchmark, we are interested in the consecutive objective values of the Pareto front that are not in P . We call these intervals empty, defining them formally below. The classic NSGA-II that uses the current crowding distance (details in Section 4) has the useful property that empty intervals (for OMM) do not increase over time and even reduce quickly in time, if the population size is large enough and if the algorithm's parent population contains the all-zeros bit string (0n ) as well as the all-ones bit string (1n ). Note that the objective values of 0n and 1n are the two extreme points of the Pareto front of both OMM and OJZJk. Considering such populations is vital for our runtime analysis.

In the interest of clarity, we here only define empty intervals for OMM and defer the definition for OJZJk to the respective section. In order to allow the comparison of empty intervals among different populations, we follow the definition of Zheng and Doerr [2025] and define a fixed number of n empty intervals for any population, based on the points {i - 0.5 | i ∈ [n]} in the space [0, n] of the first objective of OMM. Formally, let P be a population of individuals containing at least 0n and 1n . For all i ∈ [n], the i-th empty interval Ii (of P for OMM) is defined as

Algorithm 1: The classic (static) NSGA-II [Deb et al., 2002] with population size N ∈ N and selection based on current crowding distance [Zheng and Doerr, 2025], maximizing a given pseudo-Boolean function

1 t := 0; 2 P0 := drawN individuals uniformly at random; 3 while termination criterion not met do 4 Qt := generate offspring population with size N; 5 Pt+1 := select N individuals from Pt ∪Qt by non-dominated sorting followed by the current crowding distance (with uniform tie-breaker); 6 t := t +1;

By definition, the objective values not in P are given by the interior points of the empty intervals. For example, the empty interval [0..2] implies that the objective value (1, n-1) is not in the population. Different empty intervals can coincide.

Furthermore, given a population P of individuals containing at least 0n and 1n , we define the maximum empty interval (MEI) as the maximum length of its empty intervals, that is,

where |[a..b]| = b - a denotes the length of an interval [a..b]. Note that if P covers the Pareto front, then MEI(P) = 1.

4 The Classic NSGA-II as a Baseline

The non-dominated sorting genetic algorithm II [Deb et al., 2002] (NSGA-II, Algorithm 1) is the most popular and widely applied MOEA. As such, we use it as a baseline for our dynamic versions. However, we note that we use a slight improvement proposed by [Zheng and Doerr, 2025], which applies the current crowding distance, which handles ties in a manner that results in a more equidistant spread of solutions.

The NSGA-II maintains a multi-set of promising individuals (the parent population) of a given size N. The initial population is generated uniformly at random and updated iteratively. In each iteration, the NSGA-II creates an offspring population of size N by user-defined means and then selects from the combined parent and offspring population the N most promising individuals for the next iteration. This selection mechanism ranks individuals hierarchically: first, individuals are selected by their rank assigned via non-dominated sorting. Ties are handled via the (current) crowding distance, and any remaining ties are handled uniformly at random.

Computing the offspring population. The NSGA-II creates in total N offspring by repeatedly picking a certain number of individuals from the parent population and then creating modifications of them. If it picks a single parent, the process of creating an offspring is called mutation.

We allow for a variety of ways to select parents and to create offspring. The only restriction we make is that there is a constant q ∈ (0, 1] such that for each possible parent population P and each parent x ∈ P, the probability to select x at least once during the computation of the offspring population and to apply bit-wise mutation to x is at least q.

Given a parent x ∈ {0, 1}n , bit-wise mutation creates an offspring y ∈ {0, 1}n by first copying x and then flipping each bit of y independently with probability 1n .

Non-dominated sorting. Non-dominated sorting assigns each individual x in a given (combined) population R a rank that determines by how many individuals x is strictly dominated. Individuals with the same rank are grouped into the same non-dominated front, resulting in a partition (Fi)i∈[0..k-1] of R (of some size k)

The NSGA-II always attempts to add entire fronts in increasing order to its next parent population, as the individuals per front are incomparable. Once at least N individuals are chosen, the algorithm does not add any further fronts. Formally, i∗ = min{i ∈ [0..k - 1] | ∑j∈[0..i] Fi ≥ N} is the critical rank. The fronts up to i∗ - 1 are always part of the next parent population. If adding Fi∗ results exactly in a population size of N, the selection process for the next parent population terminates. Otherwise, the NSGA-II selects the best N - | ⋃j∈[0..i∗-1] Fi| individuals from Fi∗ based on their crowding distance, where higher values are preferable.

Crowding distance. The crowding distance of each individual x ∈ Fi∗ is the sum of the crowding distance of x per objective. For each objective j ∈ {1, 2}, let (yk)k∈[|Fi∗|] denote the individuals of Fi∗ sorted in increasing order with respect to objective j. If x is in the first or last position, its crowding distance for objective j is positive infinity. Otherwise, its crowding distance for objective j is the normalized distance in objective value to its direct neighbors, that is, it is

The current crowding distance [Zheng and Doerr, 2025] is a modification of the classic crowding distance that aims at decreasing the maximum distances of the resulting population. The current crowding distance achieves this by iteratively removing an individual x with the smallest (classic) crowding distance and then recomputing all (classic) crowding distances 1 , until the desired population size is achieved.

5 The Dynamic NSGA-II

Based on the classic, static NSGA-II (Algorithm 1), we propose the dynamic NSGA-II (Algorithm 2), which starts with an initial population of size 4 and attempts to double it periodically after a user-defined number τ ∈ N of function evaluations. An attempt is successful if and only if the current population size is less than the user-defined maximum population size Nmax ∈ N. We call the consecutive function evaluations between attempts phases, noting that phase 0 starts at the beginning of the algorithm run and ends at the end of the iteration in which the population size is attempted to be doubled for the first time. Moreover, note that the number of phases is unbounded although the number of doublings is not.

It is important that we attempt doublings after τ function evaluations and not iterations. If we double the population size after a fixed number of iterations, then, since the work done per iteration is proportional to the population size, relatively little work is done with small population sizes. This Algorithm2: The dynamic NSGA-II withmaximum population size Nmax ∈ N and doubling parameter τ ∈ N, maximizing a given pseudo-Boolean function f : {0, 1}n → R2 . Our only assumption on the offspring generation is that each parent has a probability of at least a constant q ∈ (0, 1] to be selected for generating an offspring via bit-wise mutation.

1 Note that x has at most four neighbors in its objectives.

1 t := 0, N := 4, w := 0; 2 P0 := drawN individuals uniformly at random; 3 while termination criterion not met do 4 Qt := generate offspring population with size N; 5 w := w+N; 6 if w ≥ τ then w := 0, N := max{2N, Nmax} ; 7 Pt+1 := select N individuals from Pt ∪Qt by non-dominated sorting followed by the current crowding distance (with uniform tie-breaker); 8 t := t +1;

risks losing any advantage from a dynamic value for the population size. By counting function evaluations, we ensure that each phase receives roughly the same computational budget.

Performance Guarantees for OMM We start by proving the following bound for the OMM benchmark. For the optimal value of τ , our runtime guarantee is O(n log2 n), which is considerably faster than the Θ(n2 logn) known for the classic NSGA-II with optimal parameters [Zheng and Doerr, 2023; Doerr and Qu, 2023b]. We note that all slower doubling schedules with τ = o(n2 ) still lead to an asymptotic improvement over the static NSGA-II. Likewise, a too small value of τ is not detrimental, but reverts to the O(Nmaxn logn) performance of the classic NSGA-II.

Theorem 1. Consider the dynamic NSGA-II (Algorithm 2) optimizing OMM with Nmax ≥ n+4. Let T denote the number of iterations until the population covers the Pareto front, and let F denote the number of function evaluations in the first T iterations. If τ ≥ 64en ln(n)/q, then with probability at least 1-O(1/n), we have T = O(τ ) and F = O(τ log n).

For smaller values of τ, we have F = O(Nmaxn logn) both in expectation and with probability 1-O(1/n), the same for the static NSGA-II with population size Nmax.

We note that we did not optimize the constants in Theorem 1. Remarkably, for sufficiently large τ, both the bounds on T and F do not depend on Nmax, as the dynamic NSGA-II covers the entire Pareto front with high probability once its population size is in the order of the size of the Pareto front, that is, order n. This makes the dynamic NSGA-II very robust in terms of choosing Nmax, in particular, since a population size of n + 1 is required in order to cover the entire Pareto front, and our lower bound of n + 4 almost matches this required minimum. Moreover, since we cover all possible cases for τ , we see that the dynamic NSGA-II is also very robust in terms of choosing the doubling parameter, being better or as good as the static NSGA-II for any τ = O(n2 ).

Moreover, we note that the arguments for small τ in Theorem 1 also apply to the failure case with probability O(1/n). Hence if the dynamic NSGA-II fails to display the desired behavior (which happens with probability O(1/n)), then the runtime reverts to the classic O(Nmaxn logn) number of function evaluations, both in expectation and with probability 1 -O(1/n). We note further that by raising the constant in the requirement on τ, all failure probabilities can be reduced to n-c for any desired constant c. We omit the details.

We prove Theorem 1 in two parts. First, we show that, with high probability, the dynamic NSGA-II finds the extreme solutions 0n and 1n during phase 0. Afterward, we show that the MEI roughly halves, with high probability, in each phase.

For the first part, we apply a result by [Zheng and Doerr, 2025], which holds in expectation, whereas we require one that holds with high probability. We obtain such a result by following essentially the analysis in [Zheng and Doerr, 2025] but adding a tail bound for harmonic sums of geometric random variables from [Doerr, 2020, Theorem 1.10.35]. Since the proof holds also for the NSGA-II with classic crowding distance and for arbitrary population sizes (of at least four), we formulate the result in this general way.

Lemma 2. Consider the NSGA-II (Algorithm 1) with arbitrary initialization, with survival based on the classic or current crowding distance, and with arbitrary population size N ≥ 4. Assume that in each iteration, each parent with probability at least q ∈ (0, 1] is chosen to generate an offspring via bit-wise mutation. Let T denote the number of iterations until in this algorithm, when optimizing OMM, the population contains 1n and 0n . Then T ≤ 2en ln(n)/q with probability at least 1- 2n .

For the second part, we rely on the following lemma showing that the MEI quickly reduces once 0n and 1n are found. This result and its proof are similar to [Zheng and Doerr, 2025, Lemmas 11 and 12], except that we need a more detailed result and a more precise tail bound, since we apply this statement for each phase separately (and thus also for phases of few iterations, where the strong concentration behavior is weaker).

Lemma 3. Consider a run of the NSGA-II (Algorithm 1), generating the next population in any way that has the property that any parent has a probability of at least q ∈ (0, 1] to be selected a parent of a bit-wise mutation, and using the current crowding distance for the selection of the next population. Consider some iteration t ∈ N0 of this algorithm optimizing OMM. Let Pt be arbitrary except that {0n , 1n } ⊆ Pt. Let m,m′ ∈ N such that max{ 2n N-3 , 1} ≤ m′ and MEI(Pt) ≤ m. Let δ ∈ N such that δ ≥ 4e(m-m′ )/q. Then Pr[MEI(Pt+δ) ≤ m′ ] ≥ 1 - n exp(- δq 16e ).

Performance Guarantees for OJZJk

Theorem 4. Consider the dynamic NSGA-II (Algorithm 2) optimizing OJZJk with k ∈ [2..⌊ n2 ⌋] and Nmax ≥ n + 4. Let T denote the number of iterations until the population covers the Pareto front, and let F denote the number of function evaluations in the first T iterations. If τ ≥ 4e(nk + 8n2 ) ln(n)/q, then with probability at least 1 -O(1/n), we have T = O(τ ) and F = O(τ log n).

For smaller values of τ, we have F = O(Nmaxnk logn) with probability 1 - O(1/n) and E[F ] = O(Nmaxnk ), both the same as for the static NSGA-II with population size Nmax.

For an optimal choice of τ, the resulting runtime guarantee of O(nk log2 n) is considerably faster than the Θ(nk+1 ) bound for the static NSGA-II [Doerr and Qu, 2023a; Doerr and Qu, 2023b], and it remains faster for any such choice with τ = o(nk+1 / logn). Moreover, a too small choice of τ just results in the same bound as for the static NSGA-II.

We note that, in comparison to our result for OMM (Theorem 1), our speed-up is slower by a factor of O(log n), which is a consequence of our results holding with high probability. The final steps in the analysis of OJZJk usually wait for a mutation to occur that flips exactly k bits. In expectation, this takes O(nk ) iterations (with each iteration requiring Nmax function evaluations). However, since this event follows a geometric distribution, it is not strongly concentrated around its expectation and requires and additional factor of O(log n) in order to hold with high probability.

The details of our proof for Theorem 4 are in the supplementary material. However, the outline of our proof strategy is very similar to that for OMM. The main difference is that we first wait until we find the optima of the outer Pareto front, which requires in either direction a mutation that flips exactly k bits at once. This happens with high probability for the stated choice of τ . During the next phase, we wait to reach the outermost optima of the inner Pareto front. This requires for either direction a mutation that flips at least k arbitrary bits, which is easier than the first phase. From then on, the problem essentially boils down to OMM.

6 Using a Longer Initial Phase

As the proofs of the results in the previous section show, the initial phase of the dynamic NSGA-II is crucial as here the extreme points of the Pareto front are found. To accommodate for this, we propose a dynamic NSGA-II with longer initial phase. For all but the initial phase, it works as the dynamic NSGA-II (Algorithm 2), doubling its population size after a fixed budget of τ ∈ N fitness evaluations. For the initial phase, we use a budget that is roughly equal to the budget of all following phases (until the maximum population size Nmax is reached), namely ⌈log(Nmax/4)⌉τ function evaluations. By this, the dynamic NSGA-II with longer initial phase spends more time in the very efficient phase with population size four, but this without increasing the asymptotic runtime. As we shall see, this allows to use smaller values for τ, leading to better runtimes.

We prove runtime guarantees for the dynamic NSGA-II with longer initial phase on the OMM and OJZJk benchmarks in Theorems 5 and 6, respectively. For optimal parameter values, these runtime guarantees are better by a factor of O(n) compared to the best known bounds for static NSGA-II, in particular, they are better by a factor of O(logn) than the guarantees for optimal parameters for the dynamic NSGA-II. However, the runtime now always depends on Nmax, due to the choice of the budget for phase 0.

Performance Guarantees for OMM For optimal parameters, we show a runtime of O(n log n) function evaluations, which is considerably faster than the Θ(n2 logn) runtime guarantee for the static NSGA-II. We note that no unbiased mutation-only black-box algorithm can find the all-ones string faster than in Θ(n logn) time [Lehre and Witt, 2012], so it is hard to imagine that a general-purpose heuristic can solve the OMM problem asymptotically faster than this.

Theorem 5. Consider the dynamic NSGA-II with longer initial phase optimizing OMM with Nmax ≥ n + 4. Let T denote the number of iterations until the population covers the Pareto front, and let F denote the number of function evaluations in the first T iterations. If τ ≥ 16en/q, then with probability at least 1 -O(1/n), we have

For smaller values of τ , we have F = O(Nmaxn log n) both in expectation and with probability 1-O(1/n), the same for the static NSGA-II (Algorithm 1) with population size Nmax.

The proof of Theorem 5 is similar to the one of Theorem 1, noting that the budget for phase 0 is of the same order. Afterward, the budget for the dynamic NSGA-II with longer initial phase is slightly smaller, which is why we apply Lemma 3 only until the MEI is O(logn). We then wait until the algorithm attains a population size linear in n and show via Lemma 3 that the algorithm finds all remaining Pareto optima within the next O(log n) phases.

Performance Guarantees for OJZJk For optimal parameters, we show a runtime of O(nk logn). For small values of k, this is close to the general Ω(nk ) lower bound when relying solely on bit-wise mutation to flip exactly k bits.

Theorem 6. Consider the dynamic NSGA-II with longer initial phase optimizing OJZJk with k ∈ [2..⌊ n2 ⌋] and Nmax ≥ n + 4. Let T denote the number of iterations until the population covers the Pareto front, and let F denote the number of function evaluations in the first T iterations. If τ ≥ 4e(2nk +8n2 )/q, then with probability at least 1-O(1/n), we have

For smaller values of τ , we have F = O(Nmaxnk log n) with probability 1 - O(1/n) and E[F] = O(Nmaxnk ), both the same as for the static NSGA-II (Algorithm 1) with population size Nmax.

The proof strategy for Theorem 5 is similar to the one for Theorem 4. As the first phase is now longer by a factor of Θ(logNmax) ≥ Θ(log n), a value of τ = Θ(nk ) is sufficient to find with high probability the outer Pareto front. Afterward, finding the outermost Pareto optima on the inner front may have a smaller budget than in the case with the dynamic NSGA-II, but since it is easier to go from the outer front to the inner front than vice versa, the slightly reduced budget does not affect the time to find the outermost solutions on the inner front. Last, we deal essentially with an OMM instance.

7 Choosing the Phase Length Automatically

To relieve users from manually select a suiting value for the phase length τ of the dynamic NSGA-II and the dynamic NSGA-II with longer initial phase, we propose a framework (Algorithm 3) that concurrently runs multiple instances of the dynamic variant with distinct values for τ , namely all powers of Algorithm 3: Concurrent optimization for the dynamic NSGA-II and the dynamic NSGA-II with longer initial phase, called A⋆ , given parameter Nmax ∈ N>4. Read Algorithm 3 as an initialization for whenever these values are used for the first time, not as infinite loop. Recalling Eqs. (1) and (2), Algorithm 3 searches with increasing j ∈ N and stops once 2j is larger than all preceding values.

1 for i ∈ N≥2 do ri := 0; ϕi := 0; 2 while no instance meets termination criterion do 3 i := argminj∈N{rj + Phase(Nmax, j, ϕj)}; 4 if ϕi = 0 then initialize an A⋆ instance Ai with Nmax as in the input and with τ = 2i ; 5 Run the next phase of Ai; 6 ϕi := ϕi +1; 7 ri := ri +Phase(Nmax, i, ϕi);

two. For each such τ = 2i , we consider an instance Ai of the dynamic variant. The framework repeatedly picks an instance Ai and runs its next phase. If an instance was picked before, we continue with the process as we last left it. Each time, we pick an instance Ai such that the total number of function evaluations spend on Ai after the potential next phase is minimal among all instances, breaking ties arbitrarily.

Formally, let Phase(Nmax, i, ϕ) denote the number of function evaluations in phase ϕ of the dynamic NSGA-II variant with parameters Nmax and τ = 2i . Then, at the beginning of each iteration of the while-loop, ri equals the number of function evaluations that instance Ai received. Formally, for the dynamic NSGA-II and Nϕ = min{4·2ϕ , Nmax}, we have

since we perform exactly Nϕ function evaluations per iteration of Ai and we only stop once we reach or surpass the total budget of τ = 2i function evaluations. For the dynamic NSGA-II with longer initial phase, Phase is the same, except

Our main runtime result for Algorithm 3 is Theorem 7, which shows essentially that on both OMM and OJZJk, both dynamic NSGA-II variants are slower by only a factor of O(logn) and O(k logn), respectively, when compared to an optimal value of τ in Theorems 1 and 4 to 6. This small slow-down still results in runtimes that are far faster than the typical O(n2 log n) and O(nk+1 ) runtimes of many MOEAs on OMM and OJZJk, respectively, as discussed before.

Theorem 7. Consider Algorithm 3 optimizing OMM or OJZJk with k ∈ [2..⌊ n2 ⌋] and Nmax ≥ n + 4. Let FOMM and FOJZJk denote the total number of function evaluations until one of the instances covers the Pareto front, respectively.

If the instances run the dynamic NSGA-II (Algorithm 2),

If they run the dynamic NSGA-II with longer initial phase,

These four bounds also hold with probability 1 - O(1/n).

In contrast to our results in the previous sections, the bounds in Theorem 7 hold additionally in expectation, as multiple runs start with a small population size and thus result in independent trials of covering the Pareto front once the population is sufficiently large. Moreover, as in the case for the dynamic NSGA-II, Algorithm 3 with the dynamic NSGA-II also effectively eliminates Nmax as a parameter, as its runtime is independent of Nmax, once sufficiently large. Hence, choosing arbitrarily large values for Nmax results in an essentially parameterless algorithm, which is a remarkable result, in particular since this parameterless version still exhibits a very fast runtime on OMM and OJZJk.

Theoretical analysis. The balancing of the function evaluations across the instances in Algorithm 3 allows us to bound the total number of function evaluations from above by a function of the number of evaluations performed within any given instance Ai, as captured in the following lemma.

Lemma 8. Let i ∈ N≥2 and r ∈ N. Consider some point in the execution of Algorithm 3 on any objective function with Nmax ∈ N>4 such that at least phase 0 of Ai has been conducted and Ai received at most r function evaluations. Then the total number of function evaluations in Algorithm 3 so far is at most 2r log(2r).

The proof of Lemma 8 uses that in order to start a new instance i ∈ N≥2, its run time budget is larger than the cost of running any of the roughly log i smaller instances.

The proof of Theorem 7 uses bounds from Theorems 1 and 4 to 6 for optimal choices of τ. Then, Lemma 8 bounds the number of function evaluations in all other instances. The expected runtimes in Theorem 7 follow since the runtimes in Theorem 1 hold with high probability for sufficiently large τ .

8 Conclusion

We introduced the dynamic NSGA-II (Algorithm 2), which runs the classic NSGA-II with a periodically increasing population size, based on a periodicity τ determined by the user. We proved that the dynamic NSGA-II has a superior runtime performance in comparison to typical MOEAs for the OMM (Theorem 1) and OJZJk (Theorem 4) benchmark for a large range of τ. For optimal parameter choices, the dynamic NSGA-II even obtains speed-ups of ˜O(n).

Moreover, we showed that if the initial phase of the dynamic NSGA-II is slightly longer than the other phases, the optimal performance improves by a factor of O(logn), both on OMM (Theorem 5) and OJZJk (Theorem 6).

Last, in order to remove the need to choose the doubling parameter τ adequately, we introduced a scheme that runs the dynamic NSGA-II variants concurrently (Algorithm 3). We showed that this scheme increases the total runtime performance by only a logarithmic factor of the original runtime (Theorem 7), while eliminating the parameter τ .

For future research, it is interesting to see whether the dynamic NSGA-II maintains its advantage in other popular scenarios, such as LOTZ [Laumanns et al., 2004].

Acknowledgments

Simon Wietheger acknowledges support by the Austrian Science Fund (FWF) [10.55776/Y1329]. Martin S. Krejca is supported by the French National Agency for Research (ANR) via the JCJC grant titled MultiEDA (ANR-25-CE232418-01). The research of Benjamin Doerr and Martin S. Krejca benefited from the support of the FMJH Program PGMO.