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

1 Introduction

The non-dominated sorting genetic algorithm II (NSGA-II) [Deb et al., 2002] is the most widely used multi-objective evolutionary algorithm (MOEA). The recent first mathematical runtime analysis of this algorithm [Zheng et al., 2022; Zheng and Doerr, 2023] has inspired many theoretical works on domination-based MOEAs such as the SPEA2 [Zitzler et al., 2001], the SMS-EMOA [Beume et al., 2007], and the NSGA-III [Deb and Jain, 2014]. Notable results include [Bian and Qian, 2022; Doerr and Qu, 2023a; Doerr and Qu, 2023b; Doerr and Qu, 2023c; Dang et al., 2023; Bian et al., 2023; Dinot et al., 2023; Wietheger and Doerr, 2023;

∗Corresponding author.

Zheng and Doerr, 2024b; Zheng and Doerr, 2024c; Zheng et al., 2024; Opris et al., 2024; Ren et al., 2024; Doerr et al., 2025; Alghouass et al., 2025; Doerr et al., 2025; Li et al., 2025; Opris, 2025a; Opris, 2025b]. Interestingly, these results suggest that the slightly less prominent algorithms SPEA2, SMS-EMOA, and NSGA-III are more powerful than the NSGA-II, at least when the number of objectives is three or more. This is the reason why in this work we concentrate on one of them, namely the NSGA-III.

The mathematical runtime analysis of evolutionary algorithms [Neumann and Witt, 2010; Auger and Doerr, 2011; Jansen, 2013; Zhou et al., 2019; Doerr and Neumann, 2020] so far has almost exclusively regarded the complexity of computing the full Pareto front. In practice, this is often not feasible, because the Pareto front is too large, and it may also not be desirable, since ultimately a human decision maker has to select one of the computed solutions as the solution to be adopted. For this reason, we shall discuss the approximation qualities of the NSGA-III in this work.

In the first and only mathematical work discussing the approximation abilities of one of the above-named algorithms, Zheng and Doerr [2022; 2024a] analyzed how well the NSGA-II approximates the Pareto front of ONEMINMAX when its population size N is less than the size of the Pareto front. They first observed that the classic NSGA-II, which first computes the crowding distance and then, based on these numbers, selects the next population, can compute very bad approximations, creating empty intervals on the Pareto front by arbitrary factors larger than what an optimal approximation displays. This can be overcome by using the sequential NSGA-II proposed in [Kukkonen and Deb, 2006], which removes individuals sequentially, always updating the crowding distance values after each removal, or the steady-state NSGA-II [Durillo et al., 2009], which generates only one offspring per iteration and hence also removes only one individual per iteration. For these two variants of the NSGA-II, it was proven that within an expected number of O(Nn log n) function evaluations, approximations with largest empty interval size MEI ≤ max{ 2n N-3 , 1} are computed. Since the optimal MEI value for ONEMINMAX and population size N is ⌈ n N-1 ⌉, this is essentially a 2-approximation. No such results exist for any other domination-based algorithms, in particular, not for the NSGA-III.

Our contributions: To fill this research gap, this work will conduct the first analysis of the approximation ability of the NSGA-III, and will detect some notable differences to the NSGA-II. Since ONEMINMAX is the only benchmark for which the approximation abilities of the NSGA-II-type algorithms were studied, in this first approximation work for the NSGA-III we shall also regard this bi-objective problem. We are aware of the fact that generally the NSGA-III is seen as an algorithm for many-objective optimization, but in this first work our focus is on a comparison with the NSGA-II via the results obtained in [Zheng and Doerr, 2024a], so for that reason we restrict ourselves to two objectives. From our proofs, we would conjecture that our findings can be generalized to more objectives.

The main approximation guarantee we prove is that with a population size N at least as the number Nr of reference points, the NSGA-III computes approximations to the Pareto front of ONEMINMAX with MEI ≤ ⌈ (5-2√2)n Nr-1 ⌉, and this within an expected number of O(Nnc logn) function evaluations, where c = ⌈ 2(2-√2) Nr-1 ⌉. Recalling that the optimal MEI is MEI = ⌈ n N-1 ⌉, we see that also the NSGA-III can compute constant factor approximations. Our result shows this factor to be at most 5 - 2√2 ≈ 2.17, slightly larger than the factor of 2 shown for the sequential and steady-state NSGA-II.

We also prove that when N < Nr, the approximation can be worse than an optimal one by a factor of Ω(log n). These results suggest that the number of reference points is best set to be equal to the population size, that is, Nr = N. This is consistent with (and thus supports) the suggestion (without theoretical explanation) to take Nr ≈ N made in the original NSGA-III paper [Deb and Jain, 2014].

Experiments are conducted to see how the NSGA-III approximates the Pareto front for ONEMINMAX. The results show that with Nr = N, the NSGA-III performs better than the NSGA-II with sequential survival selection, and always reaches the optimal approximation. This observation suggests that proving a tighter approximation bound is an interesting target for future research. The experiments also consider the case where Nr > N, and show that the approximation ability of the NSGA-III becomes worse as Nr increases, and even the extremal points of the population can be lost (which cannot happen for the NSGA-II as these points have infinite crowding distance). To verify the generalizability of the above theoretical findings and experimental observations on ONEMINMAX, we also conduct experiments for the popular LOTZ benchmark. We again observe that the setting of Nr = N results in optimal approximations, and that large numbers of reference points, that is, Nr > N, lead to worse approximations.

In summary, our results show that also the NSGA-III can compute constant-factor approximations of the Pareto front. Different from the NSGA-II (with sequential survival selection or in the steady-state mode), the absolute population size is less important (in particular, increasing the population size

Algorithm 1: NSGA-III

• 1 Let the initial population P0 be composed of N individuals chosen independently and uniformly at random from {0, 1}n ;
• 2 for t = 0, 1, 2, . . . do
• 3 Generate the offspring population Qt with size N;
• 4 Use fast-non-dominated-sort() [Deb et al., 2002] to divide Rt = Pt ∪Qt into F1, F2, . . . ;
• 5 Find i∗ ≥ 1 such that ∑i∗-1 i=1 |Fi| < N and ∑i∗ i=1 |Fi| ≥ N; 6 Zt ← ⋃i∗-1 i=1 Fi;
• 7 Use Algorithm 3 to select ˜ Fi∗ ⊆ Fi∗ such that |Zt ∪ ˜ Fi∗ | = N; 8 Pt+1 ←Zt ∪ ˜ Fi∗ ;

does not give better approximations), but the relation to the number of reference points is important for the approximation ability of the NSGA-III. In particular, we observe that for approximating the Pareto front, it appears best that Nr and N are very close, in contrast to the existing result for computing the full Pareto front [Wietheger and Doerr, 2023; Opris et al., 2024], which all require N to be at least a constant factor larger than Nr.

2 Preliminaries

This section will give a brief introduction on the NSGA-III, the algorithm to analyze, ONEMINMAX, the benchmark to optimize, and the approximation metric that we will use.

2.1 NSGA-III

The overall framework of the NSGA-III is presented in Algorithm 1. The NSGA-III, a variant of the NSGA-II designed for many objectives, was proposed by Deb and Jain [2014], and its first runtime analysis was conducted by Wietheger and Doerr [2023]. Same as the NSGA-II, the NSGA-III maintains a population Pt of a fixed size N and generates an offspring population Qt of the same size in each iteration. Also the NSGA-III will remove N individuals from the combined population Rt = Pt ∪ Qt and first uses the non-dominated sorting [Deb et al., 2002] to divide Rt into F1, F2, . . . . The NSGA-III only differs in the secondary criterion used in the critical front Fi∗ for the survival selection. Instead of the crowding distance in the NSGA-II, the NSGA-III uses the following reference point mechanism.

Initially, the objective function values are normalized, and subsequently, the normalized individuals are associated with reference points for selection. We adopted the structured reference point placement method used in [Deb and Jain, 2014], which is based on the systematic approach by [Das and Dennis, 1998]. In this approach, these reference points are uniformly distributed on the normalized hyperplane, specifically on a (M - 1)-dimensional simplex, where each axis intercept is set to 1. The total number of reference points Nr for an M-objective problem with p divisions along each objective is given by Nr = (M+p-1 p ). Figure 1 shows an example with M = 3 and p = 4. For bi-objective problems, we have Nr = p + 1. Due to the evenly distributed nature of reference points, the ideal scenario is for different individuals in the offspring population Pt+1 to be associated with different reference points. The greater the number and the more uniform the distribution of reference points associated with individuals in Pt+1 , the higher its diversity. In the selection of the critical front Fi∗ of the NSGA-III, the number of individuals already selected to Pt+1 and associated with a reference point r is referred to as the niche count ρr of that reference point. The algorithm prioritizes selecting individuals associated with the reference point that has the smallest niche count ρ if such individuals exist. This strategy increases the number of reference points associated with individuals in Pt+1, thereby enhancing the diversity of the population. Algorithms 2 and 3 present the algorithmic frameworks for the normalization and selection processes, respectively. For further details, please refer to [Deb and Jain, 2014; Blank et al., 2019; Wietheger and Doerr, 2023].

2.2 ONEMINMAX and ApproximationMetric

As mentioned before, the bi-objective ONEMINMAX [Giel and Lehre, 2010] is the only benchmark used in the theoretical community to analyze the approximation ability of the NSGA-II-type algorithms [Zheng and Doerr, 2022; Zheng and Doerr, 2024a]. For a meaningful comparison, this work also chooses this bi-objective benchmark (and also the approximation metric used in these works) to analyze the approximation ability of the NSGA-III. We believe the techniques and the insights obtained in this work will be useful for analyzing problems with many objectives.

The ONEMINMAX function is defined as follows, and we consider its maximization.

Definition 1 ([Giel and Lehre, 2010]). For all search points x the objective function f : {0, 1}n → N × N is defined by

In the language of multi-objective optimization, we say that x weakly dominates y, denoted as x ⪰ y, if f1(x) ≥ f1(y) and f2(x) ≥ f2(y). If at least one of the two inequalities is strict, we say that x dominates y, denoted as

Algorithm 2: Normalization

Input: F1, . . . , Fi∗ : non-dominated fronts; f = (f1, . . . , fM): objective function; z∗ ∈ RM : observed min in each objective; zw ∈ RM : observed max in each objective; E ⊆ RM : extreme points from previous iteration (initially {∞}M ); 1 for j = 1 toM do 2 ˆ z∗ j =min{z∗ j , minz∈Z fj (z)}; 3 Determine an extreme point e(j) in the jth objective from Z ∪ E using an achievement scalarization function; 4 valid ←False; 5 if e(1) , . . . , e(M) are linearly independent then 6 valid ← True; 7 Let H be the hyperplane spanned by e(1) , . . . , e(M) ; 8 for j = 1 to M do 9 Ij ← the intercept of H with the jth objective axis; 10 if Ij ≥ ϵnad and Ij ≤ zw j then 11 ˆ znad j ← Ij; 12 else 13 valid ← False; 14 break; 15 if valid =False then 16 for j = 1 to M do 17 ˆ znad j =maxx∈F1 fj(x); 18 for j = 1 toM do 19 if ˆ znad j < ˆ z∗ j + ϵnad then 20 ˆ znad j =maxx∈F1∪···∪Fi∗ fj(x); 21 Define f n j (x) = (fj(x) - ˆ z∗ j )/(ˆ znad j - ˆ z∗ j ), j ∈ [1..M];

x ≻ y. If x is not dominated by any individual in {0, 1}n , it is called Pareto optimal, and the set of function values corresponding to all Pareto optimal solutions forms the Pareto front. It is easy to see that the Pareto front of ONEMINMAX is {(0, n), (1, n - 1), . . . , (n, 0)}, with a size of n + 1.

As in the NSGA-II's approximation theory [Zheng and Doerr, 2022; Zheng and Doerr, 2024a], we will use the maximum empty interval (MEI) metric (see Definition 2) to evaluate how the algorithm approximates the Pareto front w.r.t. ONEMINMAX. Note that the MEI can be easily transferred to other commonly used approximation metrics such as ϵdominance [Laumanns et al., 2002] or Hypervolume [Zitzler and Thiele, 1998], see [Zheng and Doerr, 2024a].

Definition 2 ([Zheng and Doerr, 2022; Zheng and Doerr, 2024a]). Let S = {(s1, n-s1), . . . , (sm, n-sm)} be a subset of Pareto front M of ONEMINMAX. Let j1, j2, . . . , jm be the sorted list of s1, . . . , sm in the increasing order (ties broken uniformly at random). We define the maximum empty Input: Zt: the multi-set of already selected individuals; Fi∗: the multi-set of individuals to

Algorithm 3: Selection based on a set U of reference points when maximizing the function f

• choose from; 1 fn ←Normalize(f,Z = Zt ∪Fi∗) using Algorithm 2; 2 Associate each individual x ∈ Zt ∪ Fi∗ to the reference point rp(x); 3 For each reference point r ∈ U, let ρr denote the number of (already selected) individuals in Zt associated with r; 4 U ′ ←U, ˜ Fi∗ ← ∅; 5 while True do 6 Let rmin ∈ U ′ be such that ρrmin is minimal (break ties randomly); 7 Let xrmin ∈ Fi∗ \ ˜ Fi∗ be the individual associated with rmin that minimizes the distance between f n (xrmin ) and rmin (break ties randomly); 8 if xrmin exists then 9 ˜ Fi∗ ← ˜ Fi∗ ∪ {xrmin }; 10 ρrmin ← ρrmin + 1; 11 if |Zt| + | ˜ Fi∗ | = N then 12 break all and return ˜ Fi∗ ; 13 else 14 U ′ ←U ′ \ {rmin};

interval size of S, denoted by MEI(S), as

For n ∈ N≥2 := {i ≥ 2 | i ∈ N}, we further define MEIopt(N) := min{MEI(S) | S ⊆ M, |S| ≤ N, (0, n) ∈ S, (n, 0) ∈ S}.

Obviously, this is the smallest MEI that an MOEA with a fixed population size N can obtain when the extremal points (0, n) and (n, 0) are covered.

The optimal MEI value is shown in the following. Our work will obtain the upper bound of the MEI that the NSGA-III will achieve w.r.t. ONEMINMAX.

Lemma 3 ([Zheng and Doerr, 2022; Zheng and Doerr, 2024a]). For all N ∈ N≥2, we have MEIopt(N) = ⌈ n N-1 ⌉.

3 Approximation Guarantee when Nr ≤ N

In this section, we will theoretically prove that when the number of reference points Nr ≤ N, the NSGA-III can effectively approximate the Pareto front of ONEMINMAX.

3.1 Reach Extremal Points

To ease the discussion, here we call any optimal solution of one objective in a multi-objective problem an extremal point. Note that it is not the same as the extreme point/vector used to determine the hyperplane, see Algorithm 2. For ONEMINMAX, 0n and 1n are the only extremal points. We will consider whether the two extremal points 0n and 1n can be reached.

To achieve this, the following lemma will first show that for Nr ≤ N, the maximal and minimal objective values in the combined population survives. The key point is that after the normalization, such values will be mapped to (1, 0) or (0, 1). Note that (1, 0) and (0, 1) are reference points. Hence, the above values is closest to such reference points. Since Nr ≤ N and all solutions are in F1, we know that to select N individuals in the survival selection in Algorithm 3, the final ρrmin must be greater than or equal to 1. Thus, before ρrmin > 1, at least one individual with the maximal or minimal objective value (normalized to (1, 0) or (0, 1)) will be selected into the next generation. Due to the page limit, all proofs are included in the full version [Deng et al., 2025].

Lemma 4. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1 and Nr ≤ N. Let zmin 1 := min{f1(x) | x ∈ Rt} and zmax 1 := max{f1(x) | x ∈ Rt}, where Rt = Pt ∪ Qt is the combined parent and offspring population. Then Pt+1 will contain two individuals x, y such that f1(x) = zmin 1 and f1(y) = zmax 1 .

Note that the offspring generation operator (see Step 3 in Algorithm 1) will not increase zmin 1 or decrease zmax 1 . Then Lemma 4 shows that the minimal value of any objective will not increase and the maximal value of any objective will not decrease for all generations. Hence, the extremal points 0n and 1n will not be removed once they are reached. Thus, we focus on the time to decrease the minimal value of f1 to 0 to reach 0n , and the time to increase the maximal value of f1 to n to reach 1n . Lemma 5 provides an upper bound on the runtime for the population to cover these two extremal points.

Lemma 5. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1 and Nr ≤ N. Then within an expected number of O(n logn) iterations, that is, an expected number of O(Nn logn) fitness evaluations, the two extremal points 0n and 1n will be reached for the first time, and both points will be kept in all future populations.

3.2 Good Approximation Guarantee

Lemma 5 shows that the population will always contain 0n and 1n once they are reached for the first time. From basic calculations based on Algorithm 2, we obtain the following clear form for the normalized function value when the population contains both 0n and 1n .

Lemma 6. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1 and Nr ≤ N. Assume that the two extremal points 0n and 1n are included in the population. Then for any individual x in the population, its function value f(x) is normalized to f n (x) = 1n f(x).

With the clear form of the normalized function value obtained in Lemma 6, we easily map the function values to the normalized space so that we obtain the upper bound of the distance between the normalized function value and the associated reference point in Lemma 7 below.

Lemma 7. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1, Nr ≤ N, and let individual x be associated with reference point r = (r1, r2). Assume that the two extremal points 0n and 1n are included in the population. Normalize f(x) to f n (x) = (f n 1 (x), f n 2 (x)). Then f n (x) is located in the non-negative region of the reference point plane and |f n 1 (x) - r1| ≤ 2-√2 Nr-1 .

Since 0n and 1n are included in the population, Lemma 7 indicates a good mapping between the evenly distributed reference points Nr and the desired good approximation of the evenly distributed function values. It will be our key proof idea for our approximation guarantee in Theorem 11.

For better description, we call a reference point active or activated if it has at least one associated individual in the combined parent and offspring population before the survival selection. Now we first show in Lemma 8 that once a reference point is active, it will remain active forever. The key to the proof is that in Algorithm 3, each reference point will be selected at least once. Hence, at least one individual associated with the active reference point is retained.

Lemma 8. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1 and Nr ≤ N. Assume that the two extremal points 0n and 1n are included in the population. Then, if a reference point r has individuals associated with it, there will always be at least one individual associated with it in future generations.

As active reference points will remain active, we now calculate the time to activate all reference points, that is, to reach a status when all reference points have their associated individuals. From Lemma 7 we have the estimate between the active reference point and its associated individual's normalized function value. Then we use the waiting time argument to estimate the time from an active reference point to generate a neighbor non-activated reference point. Hence, the overall time for activating all reference points is obtained in Lemma 9.

Lemma 9. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1 and Nr ≤ N. Let c := ⌈ 2(2-√2)n Nr-1 ⌉. Assume that the two extremal points 0n and 1n are included in the population. Then after an expected number of O(nc logn) iterations, that is, an expected number of O(Nnc logn) fitness evaluations, each reference point r has at least one individual x associated with it and this property will be kept for all future time.

Although Lemma 9 estimates the runtime for activating all reference points, the individuals associated with the same reference point do not necessarily share the same normalized function value. Hence, we now use Lemma 7 to estimate the distance between individuals associated to neighboring reference points, and then obtain an upper bound on MEI (see the following lemma).

Lemma 10. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n + 1, Nr ≤ N, and let t0 be the first generation such that the two extremal points 0n and 1n are included in the population. Assume that each reference point r has at least one individual x associated with it. Then for any t ≥ t0, we have MEI ≤ ⌈ (5-2√2)n Nr-1 ⌉.

Hence, from Lemmas 5, 9 and 10, we obtain the following theorem regarding the approximation ability of NSGA-III.

Theorem 11. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N < n+1 and Nr ≤ N. Let c := ⌈ 2(2-√2)n Nr-1 ⌉. Then after an expected number of O(Nnc logn) fitness evaluations, a population containing the two extremal points 0n and 1n and with MEI ≤ ⌈ (5-2√2)n Nr-1 ⌉ is reached and both properties will be kept for all future time.

From Theorem 11, we see both the upper bound of the MEI value and the runtime to reach such upper bound heavily depend on Nr, the number of reference points. It is quite different from the NSGA-II (with sequential survival selection) whose upper bound MEI ≤ max{ 2n N-3 , 1} [Zheng and Doerr, 2024a] merely relies on N, the population size. Note that the optimal MEI = ⌈ n N-1 ⌉ merely depends on N, the number of points, as well. Besides, Theorem 11 shows that the minimal MEI upper bound of ⌈ (5-2√2)n N-1 ⌉ that the NSGA-III can reach happens when Nr = N. Although this upper bound is slightly worse than the one for the NSGA-II with sequential survival selection discussed before, our experiments in Section 5 shows the NSGA-III always reaches the optimal MEI, and performs better than the NSGA-II.

4 Possible Difficulty for Large Nr > N

In contrast to the approximation guarantee in the previous section, this section will show that NSGA-III may lose extremal points and yield poor approximation quality when Nr is sufficiently large. It is quite different from the existing theoretical results [Wietheger and Doerr, 2023; Opris et al., 2024] that require the large enough Nr for their analyses.

4.1 NSGA-III Can Lose Extremal Points

Recall the definition of the extremal pointed in the above section. For ONEMINMAX, 0n and 1n are the only extremal points. Being the optima of single objectives, extremal points are particularly important and should therefore not be removed from the population. In the NSGA-II, for the multiset of any extremal point, at least one of the repetitions will have infinite crowding distance and will survive to the next generation if the population size is large enough, say at least 3 for ONEMINMAX. However, the NSGA-III has no such a special treatment to ensure the extremal points survive to the next generation. Instead, the removal is determined by the numbers of already chosen individuals associated to the reference points, and the extremal points have the chance to be removed. The following lemma gives an example where the extremal point can be removed.

Lemma 12. Consider using the NSGA-III with population size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let N ≤ (n + 1)/2 and Nr ≥ 2N. Assume that before the survival selection, in the combined parent and offspring population Rt that contains 0n and 1n , each reference point has at most one associated individual. Then after the survival selection, the probabilities to remove one specific extremal point, to remove at least one specific extremal point, and to remove both extremal points are 12 , 34 + 1 4(2N-1) , and 14 - 1 4(2N-1) respectively.

The above lemma shows that with a good probability, the survival selection will lose extremal points for this example.

4.2 Possible Bad Approximation Quality

In addition to the above example that the extremal points can be removed, here we discuss an example where the survival selection of the NSGA-III can lead to a quite bad approximation from a very promising situation. This situation is essentially similar to the one used to show the possible difficulty of the traditional NSGA-II in [Zheng and Doerr, 2024a].

Lemma 13. Consider using the NSGA-III with problem size N to optimize ONEMINMAX with problem size n and suppose that ϵnad ≥ n. Let n be odd and N = (n + 1)/2 and Nr = 2N. Assume that the combined parent and offspring population Rt covers the full Pareto front. Then the next population has the expected MEI value of Ω(log n).

The optimal MEI value of N = (n+ 1)/2 is ⌈ n N-1 ⌉ ≤ 4. The above lemma shows that even from the above optimallooking combined population Rt, the MEI value becomes Ω(logn) in expectation. Due to the complicated process of the NSGA-III, we currently do not know how often the above situation happens. However, our experiments in Section 5 show that the difficulties of the NSGA-III with large number of reference points exist indeed.

As mentioned before, this work focuses on the approximation ability of the original NSGA-III. Hence, here we will not discuss the strategies to overcome the above difficulty stemming from losing extremal points, but leave it as interesting future research.

5 Experiments

Previous sections gave theoretical approximation results for the NSGA-III on ONEMINMAX. This section conducts extensive experiments to address the following three research questions.

(1) The impact of the number of reference points Nr. Our theorem shows that the best approximation ability of the NSGA-III on ONEMINMAX happens when Nr = N. We will see whether it is experimentally true for ONEMINMAX. Besides, Section 4 proved the difficulties of the NSGA-III with Nr > N on special cases. It remains unknown whether it actually happens.

(2) The actual approximation ability. The upper bound of the MEI approximation metric obtained in Theorem 11 for ONEMINMAX is a factor of 5 - 2√2 larger than the optimal value, and is slightly worse than the theoretical bound for the NSGA-II (with sequential survival selection). We will see how well the NSGA-III experimentally approximates, together with its comparison with the NSGA-II.

(3) The verification of the above findings beyond ONEMINMAX. The above two concerns are for the verification on ONEMINMAX as in our theoretical results. A natural question is about the behaviors of the NSGA-III on other problems.

5.1 Experimental Settings

To address the first two concerns w.r.t. ONEMINMAX, we adopt the same settings in the only theoretical approximation works of the NSGA-II [Zheng and Doerr, 2022; Zheng and Doerr, 2024a]. That is, we consider the problem size n = 601 and population sizes N = 301, 151, 76 (N = ⌈(n + 1)/2⌉, ⌈(n + 1)/4⌉, ⌈(n + 1)/8⌉) in these works for the easy comparison to the NSGA-II (with sequential survival selection, denoted as NSGA-II' in the following). We set the number of reference points Nr = ⌈N/4⌉, ⌈N/2⌉, N, 2N, 4N, 8N, with the first three for Nr ≤ N discussed in Section 3 and the last three for Nr > N discussed in Section 4.

To tackle the last concern, we experimentally consider another popular benchmark, LOTZ, and the optimal MEI = ⌈ n N-1 ⌉. We set the problem size n = 120, the setting used in [Zheng and Doerr, 2023], and the population size N = ⌈(n+1)/2⌉, ⌈(n+1)/4⌉, ⌈(n+1)/8⌉ and the number of reference points Nr = ⌈N/4⌉, ⌈N/2⌉, N, 2N, 4N, 8N, same settings as for ONEMINMAX.

20 independent runs are conducted. We regard these numbers are enough as the collected data are quite concentrated.

5.2 Experimental Results

Due to the limited space, here we only report the results for N = ⌈(n + 1)/8⌉ (that is, N = 76 for ONEMINMAX and N = 16 for the LOTZ), while the results for other population sizes are included in the full version [Deng et al., 2025]. Note that experimental findings obtained for this setting of N also similarly hold for other N.

The Impact of Nr

From the stable MEI values reported in Table 1 for 20 runs and Figure 2 for one exemplary run, we see that Nr = N achieves the best MEI value, compared with other settings of Nr. We also see that small values of Nr < N leads to significantly better approximation quality against large values of Nr > N. Furthermore, in the experiments, we observed that the algorithm terminates only when Tmax is reached, which shows that the difficulty to have both 0n and 1n exists and verifies the possible difficulty of the NSGA-III with large enough number of reference points discussed in Section 4.

The Actual Approximation Ability

Note that for n = 601 and N = 76 reported in Table 1, the optimal MEI = ⌈ n N-1 ⌉ = 9. Hence, for the best setting of Nr = N, we see all three quartiles reach this optimal value. Together with one exemplary one plotted in Figure 2 and all data in generations [3001..3100]), we know that the NSGA-III will reach the optimal MEI for ONEMINMAX, while the NSGA-II' (the sequential version of the NSGA-II analyzed in [Zheng and Doerr, 2024a]) cannot. This result shows that the upper bound ⌈ (5-2√2)n N-1 ⌉ (with Nr = N) obtained in Theorem 11 is not tight, and this is left as an interesting question for future research.

The Approximation Ability of the NSGA-III on LOTZ

Analogous to Table 1 and Figure 2 for ONEMINMAX, Table 2 (20 runs) and Figure 3 (one exemplary run) are for the LOTZ problem. We see that Nr = N is the best setting for the approximation ability of the NSGA-III on LOTZ, and this best setting results in the optimal MEI value of 8 (note that the Pareto front for LOTZ is {(0, n), (1, n - 1), . . . , (n, 0)}, which is the same for ONEMINMAX. Hence, the optimal MEI value is MEI = ⌈ n N-1 ⌉ = 8 for n = 120 and N = 16).

6 Conclusion

This paper conducted the first theoretical analysis for the approximation performance of the NSGA-III. We showed that the number of reference points plays an essential role for the approximation quality of the NSGA-III, considering the ONEMINMAX benchmark.

In detail, we proved that when the population size N is smaller than the size of the Pareto front, the NSGA-III can achieve an MEI approximation value of ⌈ (5-2√2)n Nr-1 ⌉ on ONEMINMAX within an expected O(Nnc log n) function evaluations, where Nr ≤ N is the number of reference points and c = ⌈ 2(2-√2)n Nr-1 ⌉. Then the best upper bound of the approximation quality (only a constant factor of 5 - 2√2 larger than the optimal MEI) is witnessed for Nr = N. However, when Nr > N, we proved the possible approximation difficulties of the NSGA-III for some examples.

Our experiments verified the above findings, say the good approximation ability of the NSGA-III with Nr ≤ N and its bad approximation ability for Nr > N. Our experiments also showed that the NSGA-III with Nr = N can reach the optimal MEI for approximation, which will guide us to derive a tighter approximation bound as our future interesting research topic.

We note the differences compared to the existing theoretical works. For the approximation ability of the NSGA-II [Zheng and Doerr, 2024a], the population size influences the upper bound of the MEI value. However, there the number of reference points has the essential influence. Besides, different from the existing theory works [Wietheger and Doerr, 2023; Opris et al., 2024], a large enough number of the reference points are required to establish the runtime theory for the full coverage of the Pareto front. This work shows that a large number of reference points can be harmful for the approximation.

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant No. 62306086, 62350710797), Science, Technology and Innovation Commission of Shenzhen Municipality (Grant No. GXWD20220818191018001), and Guangdong Basic and Applied Basic Research Foundation (Grant No. 2025A1515011936). This research benefited from the support of the FMJH Program PGMO. This work has profited considerably from discussions at the Dagstuhl Seminars 23361 Multiobjective Optimization on a Budget and 24271 Theory of Randomized Optimization Heuristics.