# Difficulties of the NSGA-II With the Many-Objective LeadingOnes Problem

Benjamin Doerr, Dimitri Korkotashvili, Martin S Krejca

<figure><img src="image_1.png" /></figure>

## To cite this version:

Benjamin Doerr, Dimitri Korkotashvili, Martin S Krejca. Difficulties of the NSGA-II With the Many-Objective LeadingOnes Problem. IEEE Transactions on Evolutionary Computation, 2025, 26, pp.228. 10.1109/TEVC.2025.3573784. hal-05533938

HAL Id: hal-05533938

https://hal.science/hal-05533938v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem

Benjamin Doerr, Dimitri Korkotashvili, and Martin S. Krejca

***Abstract***—The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. *IEEE Transactions on Evolutionary Computation* (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result.

In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NSGA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.

***Index Terms***—NSGA-II, many-objective optimization, runtime analysis, LeadingOnes.

## I. INTRODUCTION

MANY real-world optimization problems feature several conflicting objectives. This results in incomparable optimal solutions—the *Pareto optima*—, where each optimum that is better than another one in at least one objective is necessarily worse in another objective. Solvers are therefore expected to return a rich and diverse set of Pareto optima, for discrete problems also all of them, collectively known as the *Pareto front*. Due to the hardness of many multi-objective problems, *heuristic* algorithms are oftentimes employed and constitute an essential class of solvers in this field [1]. The most prominent multi-objective heuristic is the *non-dominated sorting genetic algorithm II* [2] (NSGA-II), counting over 50 000 citations on Google Scholar.

The NSGA-II belongs to the successful line of *multi-objective evolutionary algorithms* [1] (MOEAs). As such, it maintains a multi-set (the *population*) of *N* solutions and refines it iteratively, creating new solutions based on random

mutations of existing ones and then selecting the best solutions found so far. This results in complex dynamics, for which the first mathematical runtime guarantees were proven only recently [3]: The NSGA-II optimizes the bi-objective ONEMIN-MAX [4] (OMM) and LEADINGONESTRAILINGZEROS [5] (LOTZ) benchmarks of size *n* in, respectively, $O(Nn \log n)$ and $O(Nn^2)$ function evaluations (in expectation), when the population size *N* is at least a constant factor larger than the size of the Pareto front. These runtimes agree with the asymptotic runtimes of other MOEAs (with suitable parameter ranges), such as the (global) simple evolutionary multi-objective optimizer [6], [7], [8] ((G)SEMO), the ($\mu + 1$) SIBEA [9], [10], the decomposition-based multi-objective evolutionary algorithm [11] (MOEA/D; only for a OMM variant), the NSGA-III [12], [13], the SMS-EMOA [14], and the Strength Pareto Evolutionary Algorithm 2 [15] (SPEA2).

Runtime analyses confirming the strength of the NSGA-II have also been conducted in other directions, such as for combinatorial optimization [16], for noisy optimization [17], with crossover [18], [19], and in approximative settings [20].

All these positive result, however, regard bi-objective problems, and this is no coincidence. In a very recent result [21], it was shown that the NSGA-II fails to optimize the OMM benchmark efficiently once the number of objectives is 3 or more. More precisely, it was proven that the NSGA-II with any population size that is linear in the size of the Pareto front for an exponential number of iterations cannot reach a population that witnesses the Pareto front. The reason for this drastic decline in performance was attributed to the secondary criterion in the selection of the next population, the *crowding distance*. We note that a declining performance of NSGA-II for a higher number of objectives has also been observed empirically [22], but this work does not exhibit such a drastic difference between two and three objective, and it also does not blame the crowding distance for the difficulties. That indeed the crowding distance is the likely culprit can now also be seen from the fact that the NSGA-III [12], [13] and the SMS-EMOA [23], [14] provably easily optimize many classic benchmarks in three or more objectives; here we note that these two algorithms, as the NSGA-II, use non-dominated sorting as first selection criterion, but use a different secondary selection criterion, namely closeness to reference points for the NSGA-III and the hypervolume for the SMS-EMOA.

In this light, the negative result of [21] appears to be a crucial step towards understanding the strengths and weaknesses of the different MOEAs massively used in practice. A clear limitation of this result, however, is the fact that it applies only to the OMM benchmark. This benchmark is extremely simple

All authors are with Laboratoire d'Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris.

This research benefited from the support of the FMJH Program PGMO. This work has profited from many deep discussions at the Dagstuhl Seminars 23361 *Multiobjective Optimization on a Budget* and 24271 *Theory of Randomized Optimization Heuristics*.
and in particular has the uncommon property that all solutions are Pareto-optimal, a fact heavily exploited in the proof of the result. While one could argue that proven difficulties on a simple benchmark should indicate even greater problems on more complex benchmarks, in view of the importance of this questions, it appears desirable to back up this intuition with more rigorous research. This is what we aim at in this work.

**Our contribution:** We show that the poor performance of the NSGA-II for more than 2 objectives is not restricted to OMM but extends to the LOTZ benchmark. This benchmark does not have the particularity that all solutions are Pareto-optimal, rather the vast majority of the solutions are dominated by others. In that sense, this benchmark is closer to a real-world multi-objective optimization problem (while, of course, still being a synthetic benchmark simple enough to admit mathematical runtime analyses).

More precisely, let the number of objectives $m$ be an even integer (the LOTZ benchmark is only defined for even numbers of objectives). Assume that $m \ge 4$. Denote by $M = (\frac{2n}{m} + 1)^{m/2}$ the size of the Pareto front of the $m$-objective LOTZ benchmark of problem size $n$. Consider optimizing this benchmark via the NSGA-II with population size at most $aM$, where $a > 1$ is an arbitrary constant. Then for all $T \in \mathbb{N}$, with probability at least $1 - T \exp(-\Omega(n))$ the NSGA-II misses a constant fraction of the Pareto front for the first $T$ iterations (see Theorems 1 and 6 and note that the precise failure probability of the result can be even smaller than the simplified $T \exp(-\Omega(n))$ expression stated here). This result implies that the expected runtime (time to have the full Pareto front witnessed by the population) of the NSGA-II on LOTZ is at least exponential in expectation and with high probability when the number of objective is at least 4.

Although our main result is comparable to the one for the $m$-objective OMM benchmark by Zheng and Doerr [21], due to the more complex fitness landscape of the LOTZ problem, our analysis requires significant additional effort. In the OMM problem, all solutions are Pareto-optimal, and consequently, they are all contained in the first (and only) front of the non-dominated sorting of the combined parent and offspring population. Hence in this first front, a non-trivial selection decision is made via the crowding distance, and the deficiencies of the crowding distance detected in [21] lead to the undesired loss of Pareto-optimal solution values.

The LOTZ benchmark, in contrast, has (strictly) dominating solution values. Consequently, it can happen that the first front of the non-dominated sorting contains at most $N$ solutions, and in this case, these (including all Pareto optima in the population) all survive into the next generation. Hence our main technical contribution is a careful analysis of the population dynamics, which shows that the size of the first front of the non-dominated sorting grows to above $N$ faster than that all Pareto optima are found; then, as in the case of OMM, a non-trivial selection decision is made in the first front and the shortcomings of the crowding distance come into play.

We note that our lower bound applies to population sizes linear in the size of the Pareto front, whereas all upper bounds proven in the past require a population size that is at least linear in the size of the largest incomparable set

of objective values. For the OMM problem, these quantities agree, but for the LOTZ they do not [13]. This raises the question whether one should ask for the NSGA-II to be able optimize LOTZ with a population size linear in the Pareto front size. To answer this question, we ran experiments for the balanced NSGA-II [24], a version of the NSGA-II that aims at overcoming the weaknesses of the crowding distance with a second tie-breaker (applied after the crowding distance). We observe that this version of the NSGA-II is able to optimize the 4-objective LOTZ benchmark with a population size linear in the Pareto front size (Figure 3). Together with this finding, our main result shows that the weakness of the crowding distance is present also for the LOTZ benchmark.

We complement our theoretical results with an empirical analysis. Here we observe that the NSGA-II is indeed capable of quickly finding a constant fraction of the Pareto front but struggles to get past a constant fraction. Larger populations manage to cover larger fractions of the Pareto front. In addition, we study random and binary-tournament parent selection mechanisms as well as uniform crossover and see that the performance is essentially the same. Last, and perhaps most interestingly, we consider the NSGA-II with one-bit mutation and see that while it still does not cover the entire Pareto front, it covers a much larger fraction than the algorithms with bit-wise mutation. We have no explanation for this.

## II. PRELIMINARIES

### A. Notation and Terminology

Let $\mathbb{N}$ denote the set of non-negative integers, hence including 0, and let $\mathbb{R}$ denote the set of real numbers. For all $k, \ell \in \mathbb{N}$, let $[k..\ell] := [k, \ell] \cap \mathbb{N}$ and $[k] := [1..k]$. Moreover, for all $k \in \mathbb{N}_{\ge 1}$, $x \in \mathbb{R}^k$, and $i \in [n]$, we denote the value of $x$ at position $i$ by $x_i$.

In the following, let $n \in \mathbb{N}_{\ge 1}$ and $m \in \mathbb{N}_{\ge 3}$. We consider pseudo-Boolean many-objective maximization, that is, the maximization of functions $f: \{0,1\}^n \to \mathbb{R}^m$. We call each $x \in \{0,1\}^n$ an individual, we call $f(x) \in \mathbb{R}^m$ the objective-value of $x$, and for all $i \in [m]$, we denote the value of objective $i$ of $x$ by $f_i(x) := f(x)_i$.

We compare all objective-values $u, v \in \mathbb{R}^m$ via domination, which is a partial order. We say that $u$ weakly dominates $v$ (written $u \succeq v$) if and only if for all $i \in [m]$ we have that $u_i \ge v_i$, and we say that $u$ strictly dominates $v$ (written $u \succ v$) if and only if at least one of these inequalities is strict. If and only if neither $u$ weakly dominates $v$ nor the other way around, we say that $u$ and $v$ are incomparable. Moreover, we extend the notion of domination to individuals by implicitly referring to the domination of their objective-values.

For a given many-objective pseudo-Boolean function $f$, we say that an individual $x \in \{0,1\}^n$ is Pareto-optimal if and only if for all $y \in \{0,1\}^n$, we have that $f(y) \not\asymp f(x)$; we call $f(x)$ a Pareto optimum in this case. We call the set of all Pareto-optimal individuals the Pareto set (of $f$), denoted by $S^*$, and we call the set of all Pareto optima the Pareto front (of $f$), denoted by $F^*$.

When we use big-Oh notation, we always refer to the asymptotics in the length $n$ of the bit-string representation, a number often called the problem size.
## B. The Many-Objective LOTZ Benchmark

Let $m \in \mathbb{N}_{\ge 4}$ be even, and let $n \in \mathbb{N}_{\ge m}$ s.t. $m/2$ divides $n$.

**Definition.** The $m$-objective LEADINGONESTRAILINGZEROS [5] ($m$-LOTZ) benchmark bases its definition of the objectives on the bi-objective LOTZ benchmark. The latter maps an individual, as the name suggests, to the longest number of consecutive 1s from the first position and to the longest number of consecutive 0s from the last position.

In $m$-LOTZ, the $m$ objectives are defined over $\frac{m}{2}$ independent parts of the bit-string, where each part defines two LOTZ objectives for a different consecutive number of $n' := \frac{2n}{m}$ bits of the input. Formally, for all $k \in [m]$ and all $x \in \{0, 1\}^n$, abbreviating $f_k := mLOTZ_k$, we have

$$f_k(x) = \begin{cases} \sum_{i \in [n']} \prod_{j \in [i]} x_{j+(k-1)n'/2} & \text{if } k \text{ is odd,} \\ \sum_{i \in [n']} \prod_{j \in [i..n']} (1 - x_{j+(k-2)n'/2}) & \text{else.} \end{cases} \quad (1)$$

That is, $f_k(x)$ for odd $k$ describes the number of leading 1s of the $(k+1)/2$-th block of the argument, whereas for even $k$ it refers to the number of trailing 0s in the $k/2$-th substring.

**Pareto set and front.** For all $i, j \in [n]$ with $i \le j$, let $x_{[i..j]}$ denote the individual $(x_a)_{a \in [i..j]}$, that is, the substring from position $i$ to $j$. An individual $x \in \{0, 1\}^n$ is Pareto-optimal for $m$-LOTZ if and only if for all $k \in [\frac{m}{2}]$ there is an $i \in [0..n']$ such that $x_{[(k-1)n'+1..kn']} = 1^i 0^{n'-i}$. Consequently, for a Pareto-optimal individual $x$, we have for all $k \in [\frac{m}{2}]$ that $f_{2k-1}(x) + f_{2k}(x) = n'$. Thus, the size of the Pareto set and the Pareto front are both $(n' + 1)^{m/2} =: M$.

We say that two Pareto optima $u, v \in [0..n']^{m/2}$ are neighbors ($u \sim v$) if and only if there is an $i \in [\frac{m}{2}]$ such that $|u_{2i} - v_{2i}| = 1$ (equivalent to $|u_{2i-1} - v_{2i-1}| = 1$) and for all $j \in [\frac{m}{2}] \setminus \{i\}$, we have $u_{2j} = v_{2j}$ (equivalent to $u_{2j-1} = v_{2j-1}$). In other words, there is a unique block in which two corresponding objectives differ by exactly one.

## C. The NSGA-II

The non-dominated sorting genetic algorithm II [2] (NSGA-II, Algorithm 1) maximizes a given many-objective pseudo-Boolean function by iteratively refining a multi-set of $N \in \mathbb{N}_{\ge 1}$ individuals—the so-called population. It operates as follows, where we note that we define important operators below later. The population is initialized with individuals drawn independently and uniformly at random. The main loop of the algorithm consists of generating $N$ new individuals (offspring) from suitably selected members of the population (parents) and selecting the next population of $N$ individuals from the $N$ old and $N$ new individuals.

For the parent selection, we consider fair selection (each individual gives rise to one offspring), random selection (each parent is chosen uniformly at random from the population), and binary tournament selection (the better of two independently chosen individuals is taken as parent; here better refers to non-dominated sorting and crowding distance as tie-breaker, see below for details on these two criteria). As in most other theoretical works on the NSGA-II, also in our theoretical analysis we do not consider the use of crossover

for the generation of the offspring, but only mutation, namely standard bit mutation.

Out of the combined parent and offspring population, the NSGA-II selects $N$ individuals as next population via a three-stage process. First, the combined population is sorted via non-dominated sorting, and at least $N$ individuals are selected with respect to increasing fronts. If more than $N$ individuals are selected, ties among those in the highest front are broken with respect to the crowding distance of the individuals, preferring individuals with a higher crowding distance. If this still results, they ties are broken uniformly at random.

**Algorithm 1** The non-dominated sorting genetic algorithm II [2] (NSGA-II) for maximizing a given $m$-objective pseudo-Boolean function $f: \{0, 1\}^n \to \mathbb{R}^m$.

**Input:** Population size $N \in \mathbb{N}_{\ge 1}$, objective function $f$

**Output:** Population $P_t$ upon termination

1: Independently and uniformly at random (u.a.r.), generate the initial population $P_0 = \{x_i\}_{i \in [N]}$

2: while termination criterion not met do

3: Generate the offspring population $Q_t$ of size $N$

4: Combine populations $R_t = P_t \cup Q_t$

5: Compute non-dominated fronts $F_1, F_2, \dots$ from $R_t$

6: Find the critical front $i^*$

7: Use Algorithm 2 to calculate the crowding distance of each individual in $F_{i^*}$

8: Let $F'_{i^*}$ be the $N - |\bigcup_{i \in [i^*-1]} F_i|$ individuals in $F_{i^*}$ with the largest crowding distance, breaking ties u.a.r.

9: $P_{t+1} = (\bigcup_{i \in [i^*-1]} F_i) \cup F'_{i^*}$

10: Increment $t$ by 1

**Standard bit mutation.** Given a parent individual $x \in \{0, 1\}^n$, standard bit mutation creates a new offspring individual $y \in \{0, 1\}^n$ by first copying $x$ and then flipping each bit independently with probability $\frac{1}{n}$. Formally, for all $i \in [n]$ independently, we have with probability $1 - \frac{1}{n}$ that $y_i = x_i$ and with probability $\frac{1}{n}$ that $y_i = 1 - x_i$.

**Non-dominated sorting.** Given a population $R$, non-dominated sorting divides the individuals recursively into $I \in \mathbb{N}_{\ge 1}$ (population) fronts ($F_i)_{i \in [I]$), depending on how many fronts dominate an individual. For each $i \in I$, the individuals in $F_i$ are those in $R$ that are not strictly dominated when disregarding all smaller fronts. Formally, $F_i := \{x \in R \mid \bigcup_{j \in [i]} F_j \mid \forall y \in R \setminus \bigcup_{j \in [i]} F_j : f(y) \neq f(x)\}$.

The NSGA-II always selects full fronts increasingly until the number of individuals it selected is at least $N$. The smallest index that satisfies this property is called the critical front $i^* \in [I]$. That is, $i^* := \min\{i \in I \mid |\bigcup_{j \in [i]} F_j| \ge N\}$. If and only if $|\bigcup_{j \in [i^*]} F_j| > N$, then non-dominated sorting has selected too many individuals, and the NSGA-II continues with removing individuals from $F_{i^*}$ according to their crowding distance.

**Crowding distance.** The crowding distance (Algorithm 2) of a population $S$ assigns a non-negative number or infinity to each individual in $S$. This value is the sum of the crowding distances per objective. For each objective $i \in [m]$, let $S_{i,1}, \dots, S_{i,|S|}$ be a sorting of $S$ in order of descending value of the $i$-th objective. Then the $i$-th crowding distance
contribution of $S_{i,1}$ and $S_{i,|S|}$ is infinite, whereas for all $j \in [2..|S|-1]$, it is $\frac{f_i(S_{i,j-1})-f_i(S_{i,j+1})}{f_i(S_{i,1})-f_i(S_{i,|S|})}$.

The NSGA-II selects among the individuals in $F_i^*$ those $N - |\bigcup_{i \in [i^*-1]} F_i|$ with the largest crowding distance. Ties are broken uniformly at random.

**Algorithm 2** Computation of the crowding distance cDis(S).

**Input:** $S = \{S_i\}_{i \in [|S|]}$, a multi-set of individuals

**Output:** $cDis(S) = (cDis(S_i))_{i \in [|S|]}$, where $cDis(S_i)$ is the crowding distance for $S_i$

1: $cDis(S) = (0)_{i \in [|S|]}$

2: **for** each objective $f_i$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;Sort $S$ in order of descending $f_i$ value: $S_{i,1}$ to $S_{i,|S|}$

4: &nbsp;&nbsp;&nbsp;&nbsp;$cDis(S_{i,1}) = +\infty$, $cDis(S_{i,|S|}) = +\infty$

5: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 2$ to $|S|-1$ **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$cDis(S_{i,j}) = cDis(S_{i,j}) + \frac{f_i(S_{i,j-1})-f_i(S_{i,j+1})}{f_i(S_{i,1})-f_i(S_{i,|S|})}$

**Algorithm-specific terminology.** We say that a population $P$ covers a Pareto optimum $v \in \mathbb{R}^m$ (of $f$) if and only if there is an individual $x \in P$ such that $f(x) = v$. We extend this notion to sets $F$ of Pareto optima, saying that $P$ covers $F$ if and only if each $v \in F$ is covered by $P$.

The runtime $T$ of the NSGA-II (on an $m$-objective function) is the (random) number of evaluations of $f$ until the population of the NSGA-II covers the Pareto front $F^*$ of $f$ for the first time. Formally, since the NSGA-II performs $N$ evaluations of $f$ in each iteration (and $N$ once initially), it holds that $T = \min\{N(t+1) \in \mathbb{N} \mid P_t$ covers $F^*\}$.

### III. THEORETICAL RUNTIME ANALYSIS

Our main result is Theorem 1 (for fair parent selection) and its extension to random and binary tournament selection (Theorem 6), which prove that the NSGA-II (Algorithm 1) struggles to optimize $m$-LOTZ (eq. (1)) for $m \in \mathbb{N}_{\ge 4}$ objectives within sub-exponential time if its population size $N$ is linear in the Pareto front size $M$ (recall from Section II-B that $M = (\frac{2n}{m}+1)^{m/2}$). We show that the NSGA-II is missing a constant fraction of the Pareto front with overwhelming probability. That is, the failure probability is at least exponentially small in $\frac{m}{n}M$ in each iteration. Thus, for any number of iterations sub-exponential in $\frac{m}{n}M$, the NSGA-II is missing a constant fraction of the Pareto front with probability $1-o(1)$.

**Theorem 1.** Let $m \in \mathbb{Z}_{\ge 4}$ and $a > 1$ be constants, with $m$ even. Consider using the NSGA-II with population size $N \le aM = a(2n/m+1)^{m/2}$, fair selection (every parent creates one offspring), and bitwise mutation to optimize $m$-LOTZ with problem size $n$. Then for any $T$ and all $1 \le t \le T$, with a probability of at least $1-T \exp(-\Omega(\frac{m}{n}M))$ the combined parent and offspring population $R_t = P_t \cup Q_t$ does not cover a constant fraction of the Pareto front.

In all of the remainder, we assume that the assumptions of the theorem above are fulfilled.

From [21], we obtain the following result, which captures the key shortcoming of the crowding distance. This result was proven as Lemma 1 in [21] only for the optimization of the

OMM benchmark, but a closer inspection of the proof reveals that it is valid for any many-objective problem in which each of the objectives takes at most $n+1$ different values.

**Lemma 2.** Let $S$ be a set of pair-wise non-dominated individuals in $\{0,1\}^n$. Assume that we compute the crowding distance $cDis(S)$ concerning the objective function $m$LOTZ via Algorithm 2. Then at most $4n+2m$ individuals in $S$ have a positive crowding distance.

The next lemma quantifies how the random selection among individuals with crowding distance zero leads to the loss of Pareto-optimal solution values. The proof of this result is very similar to the main arguments in the proof Theorem 4 in [21]. In fact, our lemma generalizes the central argument in that theorem. In the case of the OneMinMax problem, all solutions belong to the Pareto front, hence the combined parent and offspring population consists of a single front $F_1$ with size $|F_1| = 2N$. To prove our main result, we need to understand the general situation where $F_1$ has cardinality at least $(1+\alpha)$ with $\alpha$ being any positive constant.

**Lemma 3 (Random selection lemma).** Let $N \le aM$ with $a \ge 1$ being a constant. Suppose that at some iteration $t$ in the combined population $R_t = P_t \cup Q_t$, we have $|F_1| > (1+\alpha)N$ for some $\alpha > 0$. Then, in the population $P_{t+1}$ with an $1-\exp(-\Omega(M))$ probability we will be missing at least $a$ $d(\alpha) = \frac{1}{6}(\frac{\alpha}{2e} + \frac{1-8a}{2eN})^{8a}$ fraction of the Pareto front.

*Proof.* Since we are aiming at an asymptotic statement, we assume that $n$, and hence $M$, are sufficiently large. We also assume that $N \ge \frac{1}{2}M$ as otherwise the claim is trivially satisfied. Let $U^* = F^* \cap f(R_t) = \{u \in F^* \mid \exists x \in R_t, f(x) = u\}$ and let $U'$ be the set of points in the Pareto front that have more than $\Delta := 8a$ individuals in $R_t$ corresponding to it, i.e., $U' = \{u \in U^* \mid |\{x \in R_t \mid f(x) = u\}| \ge \Delta\}$. Notice that if $|U^*| < 3M/4$, then we are missing at least $M/4 > d(\alpha)M$ points from the Pareto front. Hence we may assume that $|U^*| \ge 3M/4$. We see that $\Delta|U'| \le |R_t| \le 2N < 2aM$, thus $|U'| \le \frac{2aM}{\Delta} \le \frac{M}{4}$, and we have $|U^* \cup U'| \ge |U^*| - \frac{M}{4} \ge \frac{M}{2}$.

Let $U = \{u \in U^* \setminus U' \mid \forall x: f(x) = u \Rightarrow cDis(x) = 0\}$. Let us further denote by $A$ the number of individuals in $F_1$ that have crowding distance greater than zero. By Theorem 2 we have $A \le 4n+2m$ and, taking $n$ large enough, we obtain $|U| \ge |U^* \cup U'| - A \ge \frac{M}{2} - 4n - 2m \ge \frac{M}{3}$.

Our goal is to compute the probability that a value $u \in U$ is not covered by $P_{t+1}$. For $u$, all the individuals corresponding to it have the crowding distance equal to 0, and every such individual is in the $F_1$. This means, to form $P_{t+1}$ we first have to select $A$ individuals that have positive crowding distance and then select $N-A$ individuals from the remaining $|F_1|-A$ uniformly randomly. Notice that this is the same as randomly picking $N' := |F_1|-N$ individuals with zero crowding distance from $|F_1|$ and removing them. Let $X$ be the random variable modeling the number of uncovered points in $P_{t+1}$. Our goal is to prove that $X = \Omega(M)$ with high probability. To ease the argument, we instead consider a process where $N'$ times independently and uniformly at random we mark an individual from $F_1$ with zero crowding distance. We then remove from $F_1$ all individuals marked at least once. Let
us denote by $Y$ the random variable modeling the number of uncovered points in this process. Then $X$ stochastically dominates $Y$, simply because in the original process we remove at least as many individuals as in the new process, and in either process, the set of individuals removed is uniformly distributed among all sets of the respective cardinality. We hence regard the process leading to $Y$ in the following.

Let $u \in U$ and assume that there are exactly $b$ corresponding individuals in $R_t$ denoted by $u_1, \dots, u_b$. Observe that for the point $u$ to become uncovered, it suffices that $u_1, \dots, u_b$ appear exactly once among the $N'$ picks. We regard this event. For each $1 \le i \le b$, denote by $a_i$ the pick in which $u_i$ appears. For any fixed $a_1, \dots, a_b$, the probability that for each $i \in [1..b]$ the element $u_i$ is picked exactly in round $a_i$ is

$$ \frac{1}{(|F_1| - A)^b} \left(1 - \frac{b}{|F_1| - A}\right)^{N'-b}, $$

since each $u_i$ is chosen with probability $1/(|F_1| - A)$ and the remaining $N' - b$ picks must avoid the $b$ copies. There are exactly $b! \binom{N'}{b}$ ways to select the positions $a_1, \dots, a_b$. Hence, we obtain the probability that each $u_i$ appears exactly once is

$$ \begin{aligned} & \binom{N'}{b} \frac{b!}{(|F_1| - A)^b} \left(1 - \frac{b}{|F_1| - A}\right)^{N'-b} \\ &= \frac{N'!}{(N' - b)!(|F_1| - A)^b} \\ & \quad \cdot \left(1 - \frac{b}{|F_1| - A}\right)^{\binom{|F_1| - A}{b} - 1} \left(\frac{(N' - b)b}{|F_1| - A - b}\right)^{\binom{N' - b}{b}} \\ & \ge \frac{N'!}{(N' - b)!(|F_1| - A)^b} \exp\left(-\frac{(N' - b)b}{|F_1| - A - b}\right) \\ & \ge \frac{N'!}{(N' - b)!e^b(|F_1| - A)^b} = \frac{N' \cdots (N' - b + 1)}{e^b(|F_1| - A)^b} \\ & \ge \left(\frac{N' - b + 1}{e^b(|F_1| - A)}\right)^b \ge \left(\frac{\alpha N - \Delta + 1}{e^b(|F_1| - A)}\right)^{\Delta}, \end{aligned} $$

where in the first inequality we used that for $n$ big enough $b \le \Delta \le |F_1| - A$ and $(1 - 1/r)^{r-1} \ge \exp(-1)$ for all $r > 1$. The second inequality follows from $|F_1| - A \ge N' = |F_1| - N$, which is true, as for $n$ big enough $N \ge \frac{1}{2}M > A$. The final inequality is due to $b \le \Delta$. Using $|F_1| \le |R_t| = 2N$ and $\Delta := 8a$, we conclude that

$$ \Pr[u \text{ not covered}] \ge \left( \frac{\alpha N - \Delta + 1}{e^b(|F_1| - A)} \right)^{\Delta} \ge \left( \frac{\alpha N - \Delta + 1}{2e^N} \right)^{\Delta} \\ \ge \left( \frac{\alpha}{2e} + \frac{1 - 8a}{2e^N} \right)^{8a} := p. $$

Since each point in $U$, with a probability of at least $p$, it is not covered by $P_{t+1}$, we have $E[Y] \ge p|U| \ge p \frac{M}{3}$. As $Y$ can be written as a function of $N' \ge \alpha N$ independent picks, by applying McDiarmid's method of bounded differences [25] (also found as Theorem 1.10.27 in [26]), we obtain

$$ \Pr\left[Y \le \frac{1}{6}pM\right] \le \Pr\left[Y \le \frac{1}{2}E[Y]\right] \\ \le \exp(-\Omega(E[Y])) = \exp(-\Omega(M)). $$

As $X$ stochastically dominates $Y$, we have $\Pr[X \le \frac{1}{6}pM] \le \Pr[Y \le \frac{1}{6}pM] \le \exp(-\Omega(M))$. This means with the probability of $1 - \exp(-\Omega(M))$ we are missing at least $\frac{1}{6}pM = d(\alpha)M$ points from the Pareto front. $\square$

We define some additional notation needed for the proof. We first specify that we always treat sets of solutions as multi-sets, that is, we allow them to contain the same individual multiple times. In contrast, sets of objective values are always seen as proper sets, that is, they contain each objective vector at most once. Let $P_t^*$ be the (multi-)set of points defined by $P_t^* = \{x \in P_t | f(x) \in F^*\}$. Define $N_t^* := |P_t^*|$, the number of Pareto optima in $P_t$, and $M_t' := |f(P_t) \cap F^*|$, the number of different objective values of solutions on the Pareto front.

As outlined in Section I, the main additional challenges over the analysis of the OMM case in [21] is that we need to understand how the population is distributed over the the non-dominated fronts. More specifically, the shortcoming of the crowding distance can only come into play when the crowding distance plays a role in the selection of solutions on the Pareto front. For this to happen, we need to have more than $N$ solutions in the first front of the non-dominated sorting.

Theorem 4 below shows that we arrive at such a situation, and this before having found the full Pareto front. The proof of this result is a careful analysis of the population dynamics, where we simultaneously have a multiplicative increase of the number of solutions on the Pareto front (which necessarily end up in the first front) but only a very slow growth of the number of different solutions on the Pareto front. This leads to a situation with the first front having at least $(1+\alpha)N$ elements without ever having witnessed more than $(1-\beta)N$ different solutions on the Pareto front, where $\alpha, \beta$ are suitable positive constants. In this situation, we apply the random selection lemma (Theorem 3) and show that we lose sufficiently many solutions on the Pareto front to iterate this argument.

**Lemma 4.** Let $\alpha = \frac{1}{12ae}$. Let $c_1 := 1 - d(\alpha)$ and $c_2 := (1 + c_1)/2$. Assume that $M/2 \le M'_t \le c_1 M$ for some $t$. Then there exists a $T = O(n)$ such that, with probability $1 - (T + 1)\exp(-\Omega(mM/n))$, for all $0 \le i \le T$, we have $M'_{t+i} \le c_2 M$ and $M'_{t+T+1} \le c_1 M$.

To prove this lemma, we first show that $M'_t$, the number of different Pareto optima in the population, cannot increase by a lot in a single iteration. We shall need this argument again in the final proof of our main result.

**Lemma 5.** Let $t$ be some iteration. Then

$$ \Pr[f(Q_t \cup P_t) \cap F^* \ge M'_t + \frac{2amM}{n}] \le \exp(-\frac{maM}{3n}). $$

In particular, $\Pr[M'_{t+1} \ge M'_t + \frac{2amM}{n}] \le \exp(-\frac{maM}{3n})$.

*Proof.* The second statement is an immediate consequence of the first one since any new Pareto optimum in $P_{t+1}$ must be contained in $Q_t$. We thus prove the first statement.

Let $x \in P_t$, and let us denote by $x' \in Q_t$ its offspring (recall that we assume fair selection, that is, each parent creates one offspring). The probability that $f(x')$ is in $F^*$ but not in $f(P_t)$ is at most the probability that $x'$ is a Pareto set point different from $x$. We first show that this probability it at most $\frac{m}{n}$. We
know that there are $m$ objectives and $m' = m/2$ blocks of leading ones and trailing zeroes. Let $\ell_i = \min\{k \in \mathbb{N} | x_k = 0$ and $(\frac{i-1}{m})n \le k \le \frac{in}{m'}\}$ and $r_i = \max\{k \in \mathbb{N} | x_k = 1$ and $(\frac{i-1}{m'})n \le k \le \frac{in}{m'}\}$, the positions of the first 0 from the left and the first 1 from the right in the $i$-th block. For $x'$ to be a Pareto set point different from $x$, at least one of the bits $\{x_{\ell_1}, x_{r_1}, \dots, x_{\ell_{m'}}, x_{r_{m'}}\}$ has to be flipped. The probability for any bit in $x$ to be flipped is $\frac{1}{n}$. Thus using the union bound, we easily conclude that the probability of $x'$ being a different Pareto set point is at most $\frac{2m'}{n} = \frac{m}{n}$.

Let $X$ denote the random variable that counts the number of offspring that are in the Pareto set and are different from their parent. Then $X = \sum_{u \in P_t} X_u$, where $X_u$ is a binary random variable that, for each $u \in P_t$, models whether the offspring is a Pareto set point different from the parent. As we just computed that $E[X_u] \le \frac{m}{n}$, from $N \le aM$ we obtain $E[X] \le \frac{maM}{n}$. Since the $X_u \in [0, 1]$ are independent, using a multiplicative Chernoff bound working with estimates for the expectation (e.g., Theorem 1.10.21 from [26]) we have $\Pr[X \ge \frac{2amM}{n}] \le \exp(-\frac{maM}{3n})$. Since $f(Q_t \cup P_t) \cap F^* \le M'_t + X$, we have shown our claim. $\square$

We are now prove Theorem 4, the heart of our analysis.

**Proof of Theorem 4.** The proof of this lemma is divided into three parts. The first part, exploiting Theorem 5, shows that, starting with the condition of the lemma, covering more than $c_2M$ different points in the Pareto front requires more than $(\frac{c_2-c_1}{n})\frac{n}{2am}$ steps. In the second part we prove that in $(\frac{c_2-c_1}{n})\frac{n}{2am}$ steps, there will be a point when $|F_1| \ge (1+\alpha)N$, where $\alpha := \frac{1}{12ae}$. The last part uses the Theorem 3 to conclude that as result of the next iteration, we will indeed be missing at least $c_1M$ points of the Pareto front.

**Part 1:** By Theorem 5, with probability at least $1 - \exp(-\Omega(\frac{m}{n}M))$, we cover at most $\frac{2amM}{n}$ new points in the Pareto set in one iteration. To cover more than $c_2M$ points in the Pareto front, we need to obtain more than $(c_2-c_1)M$ new points, therefore the algorithm will require more than $(\frac{c_2-c_1}{n})\frac{n}{2am}$ iterations, with probability at least $1 - \frac{(c_2-c_1)n}{2am}\exp(-\Omega(\frac{m}{n}M)) = 1 - \exp(-\Omega(\frac{m}{n}M))$.

**Part 2:** Let us denote by $F_1^k$ the non-dominated points in $R_k$ and for simplicity let $\delta := \lfloor \frac{c_2-c_1}{2am} \rfloor$. Aiming at a contradiction, assume that for all $k \le t + \delta n$ and for $\alpha := \frac{1}{12ae}$, we have $|F_1^k| < (1+\alpha)N$.

We note that for all $x \in P_t^*$, the probability that we do not flip any bit of $x$ is $(1 - \frac{1}{n})^n$, as each bit stays the same with probability $1 - \frac{1}{n}$. Hence for $n \ge 3$, the generated offspring $x'$ equals the parent with probability at least $(1 - \frac{1}{n})(1 - \frac{1}{n})^{n-1} > \frac{n-1}{ne} \ge \frac{2}{3e}$.

Let $O' := f(P_t) \cap F^*$ be the set of Pareto front points that are already covered by $P_t$ at the start of the process. For $k$ such that $t \le k \le t+\delta n$, let $O_k = \{x \in P_k | f(x) \in O'\}$. Our goal is to show that for all $k$, we have $|O_k| \ge |O_t|(1+\frac{1}{6e})^{k-t}$, apart from a failure probability of at most $\exp(-\Omega(M))$ for each $k$. Before conducting this proof, we mention that from the assumptions of the lemma, we have $|O_t| \ge M'_t \ge M/2$.

We show our claim by induction on $k$. The base case is trivial, so we proceed to the induction step. Assume that for

some $k$ we have $|O_k| \ge |O_t|(1+\frac{1}{6e})^{k-t}$. Let $X$ be the random variable that counts the number of created copies of the elements of $O_k$, i.e., the offspring of the elements of $O_k$ that are the same as their parents. It is crucial to point out that $X$ just models the number of created copies, not the copies that are selected in the next generation. Each point $x \in O_k$ creates a copy with a probability of at least $\frac{2}{3e}$, hence $E[X] \ge \frac{2}{3e}|O_k|$. Again, we can write $X = X_1 + \dots + X_{|O_k|}$, where $X_i$ is a binary random variable modeling the creation of a copy of the $i$-th point in the set $O_k$. Since the $X_i$ are bounded and independent, using a Chernoff bound we deduce that

$$ \Pr[X \le \frac{e}{3}] \le \Pr[X \le \frac{E[X]}{2}] \\ \le \exp(-\Omega(E[X])) = \exp(-\Omega(M)). $$

As $|F_1^k| \le (1+\alpha)N$, and as for $P_{k+1}$ we select $\min\{N, |F_1^k|\}$ points from $F_1^k$, with a probability of at least $1 - \exp(-\Omega(M))$, we have $|\{x \in R_k | f(x) \in O'\}| \ge (1+\frac{1}{3e})|O_k|$. Using $\{x \in R_k | f(x) \in O'\} \subseteq F_1^k$, we obtain

$$ |O_{k+1}| \ge |\{x \in R_k | f(x) \in O'\}| - \alpha N \\ \ge |O_k|(1 + \frac{1}{3e}) - \alpha N \ge |O_k|(1 + \frac{1}{3e}) - \frac{1}{6e}\frac{M}{2} \\ \ge |O_k|(1 + \frac{1}{6e}), $$

where the second inequality used $N \le aM$ and $\alpha = \frac{1}{12ae}$, and the last inequality follows from $M/2 \le |O_1| \le |O_k|$. Thus, by the induction hypothesis, we can deduce that $|O_{k+1}| \ge |O_t|(1 + \frac{1}{6e})^{k+1-t} \ge (1 + \frac{1}{6e})^{k+1-t}$. To conclude the argument, notice that for $n$ big enough, more precisely, $n > \frac{\ln(2(1+\alpha)a)}{\delta\ln(1+1/6e)}$, we have $|F_1^{t+\delta n}| \ge |O_{t+\delta n}| \ge \frac{M}{2}(1 + \frac{1}{6e})^{\delta n} > (1+\alpha)aM \ge (1+\alpha)N$, and we obtain a contradiction.

**Part 3:** In the first two parts of this proof, we have seen that there is a $T \le \delta n$ such that in the time interval $[t..t+T]$, we have never covered more than $c_2M$ points of the Pareto front, and such that in $R_{t+T} = P_{t+T} \cup Q_{t+T}$, we have $|F_1| \ge (1+\alpha)N$. This statement holds apart from a failure probability of at most $T \exp(-\Omega(\frac{m}{n}M))$. From Theorem 3, we now conclude that $P_{t+T+1}$ is missing at least a $d(\alpha) \ge (1-c_1)$ fraction of the Pareto front, with a probability of at least $1 - \exp(-\Omega(M))$. $\square$

The proof of our main result now is, mostly, a repeated application of the lemma just shown.

**Proof of Theorem 1.** Consider a run of the NSGA-II on the $m$-LOTZ benchmark. We first show that with high probability, the random initial population satisfies one of the conditions of Theorem 4, namely that it covers at most $c_1M$ points of the Pareto front, that is, we have $M'_0 \le c_1M$. To this aim, we note that a random individual is in the Pareto set with probability $|F^*|/2^n = M/2^n$, where we recall that there is a one-to-one correspondence between the Pareto front and the Pareto set in the $m$-LOTZ benchmark. Consequently, the expected number of Pareto set points in $P_0$ is $\frac{NM}{2^n} \le M/4$ when assuming $n$ to be sufficiently large. Using a Chernoff bounds that works relative to an estimate for the expectation, e.g., Theorem 1.10.21
from [26], we conclude that $\Pr[M'_0 < c_1 M] \ge \Pr[M'_0 < M/2] \ge 1 - \Pr[M'_0 \ge 2(M/4)] \ge 1 - \exp(-M/12)$.

We next show that if at some time $t$ we have $M'_t \le c_1 M$, then there is a time $s > t$, $s = t + O(n)$ such that, with probability at least $1 - (s-t)\exp(-\Omega(\frac{mM}{n}))$, we have $M'_r \le c_2 M$ for all $r \in [t..s-1]$ and furthermore $M_s \le c_1 M$. We argue differently depending on $M'_t$.

If $M'_t \le M/2$, then Theorem 5 immediately implies that $s = t + 1$ fulfills our claim.

Hence assume that $M/2 \le M'_t \le c_1 M$. By Theorem 4 we know that there exists $T = O(n)$ such that with probability at least $1 - (T+1)\exp(-\Omega(\frac{mM}{n}))$ we have $M'_{t+T+1} \le c_1 M$ and for all $k \in [t..T]$ we cover at most $M'_k \le c_2 M$ points from the Pareto front. Hence $s = t+T+1$ fulfills our claim.

Via induction, using a union bound to add up the failure probabilities, we obtain the statement that for all $t \ge 1$ there is an $s = t + O(n)$ such that with probability $1-s\exp(-\Omega(\frac{mM}{n}))$, the parent population of the NSGA-II optimizing m-LOTZ has, in the first $t$ iterations, never covered more than $(1-c_2)M$ points of the Pareto front. We note that $\frac{mM}{n} = \Omega(n)$. Hence we have $s\exp(-\Omega(\frac{mM}{n})) = t\exp(-\Omega(\frac{mM}{n}))$. Consequently, we can rewrite our result in the way that for all $t \ge 1$, with probability $1-t\exp(-\Omega(\frac{mM}{n}))$, we have, in the first $t$ iterations, never covered more than $(1-c_2)M$ points of the Pareto front.

So far we have proven that $P_t$ misses a constant fraction of the Pareto front for a long time. By the first statement of Theorem 5, the number $f(P_t \cup Q_t) \cap F^*$ of Pareto front points covered by the combined parent and offspring population is at most by a lower-order term larger than $f(P_t) \cap F^*$. Hence our result immediately extends to the combined parent and offspring population, and this proves our theorem. $\square$

We now extend our main result to two other variants of the NSGA-II, namely the ones obtained by replacing fair selection by random selection or (independent) binary tournament selection. Both are common variants of the NSGA-II. To profit from similarities of the two methods, we prove a result for a broader class of selection operators that includes these two.

**Theorem 6.** Theorem 1 remains valid if the NSGA-II selects the individuals to be mutated in any way that ensures that (i) each parent individual is chosen independently, and (ii) in a way that there is a constant $\gamma > 0$ such that for any set $O$ of individuals on the Pareto front with $|O| \ge M/2$, the parent individual is from this set with probability at least $\gamma$. This includes in particular the cases that each parent is chosen uniformly at random from the population (random selection) and that each parent is chosen by selecting two random individuals from $P_t$ and then taking as parent the one that appears earlier in the non-dominated sorting, using the crowding distance as tie-breaker (binary tournament selection).

*Proof.* We note that Theorems 2 and 3 only regard the selection of the next population, so they are independent of the way the offspring are generated.

The two main arguments in the proof of Theorem 5 are that an offspring with probability at most $2m'/n$ leads to a new Pareto-optimal solution value, and that this can be used,

by a Chernoff bound, to prove a probabilistic upper bound on the expansion of the population on the Pareto front. For the first argument, no assumption was made on the parent, hence it immediately extends to other selection operators. For the Chernoff bound, we proceed a little differently (since now not each individual in $P_t$ creates an offspring), but the remaining calculations remain unchanged. Assume that the $N$ offspring are generated sequentially. For $i \in [1..N]$, let $X_i$ be the indicator variable of the event that the $i$-th offspring lies on the Pareto front and is different from its parent. These random variables are independent and, by the first argument, satisfy $\Pr[X_i = 1] \le 2m'/n = m/n$. Hence the sum $X = \sum_{i=1}^N X_i$ (an upper bound on the number of newly generated Pareto-optimal solution values) admits the same Chernoff bounds as the corresponding sum $X$ in the proof of Theorem 5.

For the proof of Theorem 4, we first note that the first part only builds on Theorem 5 without exploiting directly properties of the algorithm. In the second part of the proof, we argue that we generate quickly new solutions (with existing solution values) on the Pareto front. Again, since we select parents independently, we reorganize the central Chernoff bound, but more importantly, we ensure that the right parent individuals are selected sufficiently often. Recall that in the second part of the proof of Theorem 4 we assume that the number $|O'|$ of points of the Pareto front covered at the start of this phase is at least $M/2$. Hence, the set $O_k$ defined in this proof always has a cardinality at least $M/2$. By our assumptions, this implies that each parent chosen in iteration $k \in [t..t+\delta n]$ is in $O_k$ with probability at least some positive constant $\gamma$. Hence the probability that the $i$-th offspring generated in this iteration is equal to its parent, which is in $O_k$, is at least $\gamma(1 - \frac{1}{n})^n \ge \frac{2\gamma}{3^\gamma}$. Denoting by $X_i$ the indicator variable for this event, we note that $X = \sum_{i=1}^N X_i$ counts the number of offspring equal to their parent in $O_k$. By the same Chernoff bound as in Theorem 4 and replacing the constant $\alpha$ by $\gamma\alpha$, we obtain that with probability at least $1 - \exp(-\Omega(M))$, we have $|O_{k+1}| \ge |O_k|(1 + \frac{\gamma}{6\gamma})$. By adjusting also the other constants in Theorem 4, that is, using $c_1 = 1 - d(\gamma\alpha) = 1 - d(\frac{\gamma}{12\gamma\alpha})$ instead of $c_1 = 1 - d(\alpha) = 1 - d(\frac{1}{12\gamma\alpha})$ and defining $c_2 = (1 + c_1)/2$ relative to the new $c_1$, we obtain an identical version of Theorem 4 except for the values of $c_1$ and $c_2$.

Last, the main proof of Theorem 1 only uses the previously shown lemmas (and does not rely on specific values of $c_1$ and $c_2$), showing our claim, which differs from the claim of Theorem 1 only in the constants hidden in the asymptotics.

We finally argue that random selection and binary tournament selection are covered by this theorem. Let $O$ be any set of individuals such that $|O| \ge M/2$. Recall that $N \le aM$ for some constant. For random selection, the probability to pick an individual from $O$ is apparently $|O|/N \ge \frac{M/2}{aM} = \frac{1}{2a} =: \gamma$. For binary tournament selection, the probability to select an individual from $O$ is at least the probability that both individuals participating in the tournament are in $O$, which is $(\frac{|O|}{N})^2 \ge (\frac{M/2}{aM})^2 = \frac{1}{4a^2} =: \gamma$. $\square$

We note that our proof method does not cover all variants of the NSGA-II regarded so far. In particular, surprisingly, our proof does not extend to one-bit mutation, as the argument that
<figure><img src="image_3.png" /><figcaption>Fig. 1: The number of distinct objective values on the Pareto front of the NSGA-II (Algorithm 1) with standard bit mutation and fair selection for the combined parent and offspring population ($R_t$) and the selected population ($P_{t+1}$) over 1000 iterations. The algorithm is run on 4-LOTZ of size $n = 40$, with the dashed line showing the total size of the Pareto front ($M = 441$) for reference. From top to bottom, each pair of curves refers, respectively, to the population size $N = 8M$, $N = 4M$, and $N = 2M$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2: The number of individuals in the non-dominated subpopulation $F_1$ (of $R_t$) as well as the number of Pareto-optimal individuals in the combined parent and offspring population ($R_t$) and the selected population ($P_{t+1}$) of the NSGA-II (Algorithm 1) with standard bit mutation and fair selection over 1000 iterations. The algorithm is run on 4-LOTZ of size $n = 40$, resulting in a total size of the Pareto front of $M = 441$, with $N = 4M$. The dashed lines show the total population size of $R_t$ (namely $2N$) and of $P_{t+1}$ (namely $N$) for reference. This is the same run as in Figure 1 for $N = 4M$.</figcaption></figure>

the number of individuals in the Pareto front grows quickly in the second part of the proof of Theorem 4 breaks down, since with one-bit mutation, we never create a copy of a parent. In Section IV, we investigate the impact of one-bit mutation empirically, and Figure 4 suggests that while the algorithm still does not manage to cover the entire Pareto front in reasonable time, it covers a larger fraction than with standard bit mutation.

Our proof also does not immediately extend to crossover, as it is challenging to show that the probability of generating a new Pareto-optimal solution value is small, which is the main argument in the proof of Theorem 5. We note that there are very few proofs of lower bounds for crossover-based algorithms, again for the reason that the population dynamics are harder to analyze. We briefly study this setting empirically though in Section IV. Figure 3 shows that adding crossover has no real impact on the suboptimal coverage of the algorithm.

## IV. EXPERIMENTS

We study empirically how well the NSGA-II approximates the Pareto front of 4-LOTZ in three different settings, two of which study different algorithm variants that are not covered by our theoretical analysis. Since it is costly to run the NSGA-II, we limit our tests to the problem size $n = 40$, which results in a Pareto front of size $M = 441$. For many settings, we started 10 independent runs. Since all the results are qualitatively the same, we only present a single run in each instance in order to increase the interpretability of our results.

We study the following algorithm variant settings:

(i) The **NSGA-II with fair selection and standard bit mutation** as analyzed in Theorem 1. We aim to observe what fraction of the Pareto front the algorithm is still missing. This setting acts as a baseline for the other ones.

(ii) The **NSGA-II with different parent selection mechanisms and crossover**. In addition to fair selection, we consider: (a) *random selection*, where each offspring is generated

by choosing a parent uniformly at random (u.a.r.) from the current parent population; (b) *binary tournament selection*, where each offspring is generated by choosing the fittest of two parents, each chosen u.a.r. (breaking ties via non-dominated sorting, crowding distance, and then u.a.r.) with replacement from the current parent population; and (c) *crossover*. The algorithm with crossover decides u.a.r. and independently for each offspring, before the parent selection, whether it uses crossover followed by mutation or whether it only uses mutation (with *random selection*). If it uses crossover, the algorithm first picks two parents u.a.r., with replacement, and then performs a crossover operation among these two parents before applying mutation to the crossover result. We consider two common mutation operators. *Uniform crossover* chooses for each position $i \in [n]$ of the offspring one bit of the parents at position $i$ u.a.r. *One-point crossover* chooses a single position $i \in [n]$ u.a.r. and copies all bits from positions 1 to $i$ from the first parent, and the remaining bits from the other parent. All these variants still use standard bit mutation.

We also study the *balanced NSGA-II* [24], which is a variant of the classic NSGA-II [2] that improves the crowding distance. Instead of making a selection u.a.r. among individuals with equal crowding distance, the balanced NSGA-II selects individuals (among individuals with equal crowding distance) such that the multiplicity of their objective values is as close to uniform as possible (and only thereafter, it chooses u.a.r. among ties). We study the balanced NSGA-II only with standard bit mutation and without crossover.

(iii) The **NSGA-II with one-bit mutation**, where an offspring is generated by flipping exactly one bit in the parent, with the bit position chosen uniformly at random. This variant still uses fair parent selection.

**Classic NSGA-II.** Figure 1 shows how well the NSGA-II covers the Pareto front over a span of 1000 iterations, for three different population sizes. We see that it is missing for
<figure><img src="image_5.png" /><figcaption>Fig. 3: The number of distinct objective values on the Pareto front of the NSGA-II (Algorithm 1) with standard bit mutation and different selection and crossover methods for the combined parent and offspring population ($R_t$) over 1000 iterations. The algorithm is run on 4-LOTZ of size $n = 40$, with the dashed line showing the total size of the Pareto front ($M = 441$) for reference. The population size of the algorithm is $N = 4M$. The data for the run of the *Standard* algorithm is the same as in Figure 1 with $N = 4M$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4: The number of distinct objective values on the Pareto front of the NSGA-II (Algorithm 1) with one-bit mutation and fair selection for the combined population ($R_t$) and the selected population ($P_{t+1}$) over 1000 iterations. The algorithm is run on 4-LOTZ of size $n = 40$, with the dashed line showing the total size of the Pareto front ($M = 441$) for reference. From top to bottom, each pair of curves refers, respectively, to the population size $N = 8M$, $N = 4M$, and $N = 2M$.</figcaption></figure>

each configuration still a constant fraction of the Pareto front, but this missing fraction is smaller the larger the population size is. Furthermore, we see that while the combined population $R_t$ covers more of the Pareto front than the selected population $P_{t+1}$, the difference is not very large. This suggests that the offspring population does not add many new objective values such that the selection process for the new parent population is able to remove sufficiently many objective values for the process to converge prematurely. This happens very consistently, as the trends of both curves are very similar.

Figure 2 shows how many individuals are Pareto-optimal over 1000 iterations, for three different populations. In all cases, the selected population $P_{t+1}$ for the next iteration consists almost exclusively of Pareto-optimal individuals. The same is not true for the combined population, as it is easy to create non-optimal individuals. Nonetheless, almost all of the non-dominated individuals are also Pareto-optimal. Still,

non-Pareto-optimal non-dominated individuals regularly result in $P_{t+1}$ containing a small number of non-optimal individuals.

**Different parent selection mechanisms.** Figure 3 shows the Pareto front coverage of the combined population of the NSGA-II with different selection mechanisms, all with population size $N = 4M$, over 1000 iterations. As we prove with Theorem 6 for all mechanisms but crossover, the algorithm struggles. The behavior seems to be very similar in all configurations, suggesting that the exact type of selection mechanism is not very relevant (recall that Theorem 6 covers a more general class). Notably, uniform crossover has a very similar performance, further suggesting that various mechanisms fail to make the NSGA-II cover the entire Pareto front efficiently. One-point crossover also does not help cover the entire Pareto front, but the coverage is considerably higher, likely because one-point crossover is more suited to problems where the order of bits matters, as it copies this order. This order-preserving mechanism seems to pay off but does not fully overcome the problem introduced by the crowding distance.

We see a strong contrast in the performance of the balanced NSGA-II, which is able to quickly cover the entire Pareto front of 4-LOTZ. Since the balanced NSGA-II values less frequent objective values over more frequent ones, it never loses a Pareto-optimal solution if the population size is capable to fit the entire Pareto front, which is the case in our setting. The most interesting insight for the balanced NSGA-II is that it succeeds with a population size that is not in the order of the size of the largest incomparable set of objective values, which is larger than the size of the Pareto front [13]. In theory, such a large incomparable set could make the algorithm get stuck on non-optimal solutions, as it cannot discern which of the incomparable solutions are on the Pareto front and which are not. However, this problem does not seem to occur, and the algorithm quickly covers the entire Pareto front once it reaches it. Due to this observation, we conjecture that other MOEAs, such as the NSGA-III, SMS-EMOA, and SPEA2, do also not run into a problem with a large incomparable set. Under this assumption, the classic NSGA-II is the only MOEA from this selection that fails to optimize *m*-LOTZ efficiently.

**One-bit mutation.** Figure 4 shows how well the NSGA-II with one-bit mutation covers the Pareto front over a time span of 1000 iterations, for three different population sizes. We see that, similar to Figure 1 with standard bit mutation, the algorithm typically does not cover the entire Pareto front during this time, and it covers a larger fraction when using a larger population size. However, the fraction covered is larger as for the results seen in Figure 1. For a population size of $N = 8M$, the algorithm even occasionally covers the entire Pareto front, but it is missing, on average, five objective values on the Pareto front starting from around iteration 800, showing that it does not *converge* to the entire Pareto front. We have no explanation for the better approximation ability of the NSGA-II with one-bit mutation. We observe that one-bit mutation compared to bit-wise mutation has a much smaller probability to create from a parent on the Pareto front another solution on the Pareto front, so we speculate that this difference is the main reason for the different performance. It is the reason why our analysis for bit-wise mutation cannot
easily be extended to one-bit mutation, but this is, apparently, not a strong argument for the better performance. We have to leave this question open for future research.

## V. CONCLUSION

We extended the result of [21], showing that the NSGA-II has enormous difficulties solving the many-objective OMM problem, to the LOTZ benchmark. This result is technically non-trivial and shows that the difficulties observed in [21] persist also in situations where non-dominated sorting is relevant for the selection, and thus could potentially overcome the weaknesses of the crowding distance pointed out in [21]. Together with the recent results showing that the NSGA-III, SMS-EMOA, and SPEA2 do not have such weaknesses for many objectives [12], [13], [14], [27], [15], our result suggests that the crowding distance as secondary selection criterion is less suitable compared to several alternatives.

For future work, it would be interesting to study other variants of the NSGA-II rigorously, for example, when using one-bit mutation or crossover.

## REFERENCES

[1] A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P. N. Sughanthan, and Q. Zhang, "Multiobjective evolutionary algorithms: A survey of the state of the art," *Swarm and Evolutionary Computation*, vol. 1, pp. 32–49, 2011.

[2] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," *IEEE Transactions on Evolutionary Computation*, vol. 6, pp. 182–197, 2002.

[3] W. Zheng, Y. Liu, and B. Doerr, "A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II)," in *Conference on Artificial Intelligence, AAAI 2022*. AAAI Press, 2022, pp. 10408–10416.

[4] O. Giel and P. K. Lehre, "On the effect of populations in evolutionary multi-objective optimisation," *Evolutionary Computation*, vol. 18, pp. 335–356, 2010.

[5] M. Laumanns, L. Thiele, and E. Zitzler, "Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions," *IEEE Transactions on Evolutionary Computation*, vol. 8, pp. 170–182, 2004.

[6] M. Laumanns, L. Thiele, E. Zitzler, E. Welzl, and K. Deb, "Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem," in *Parallel Problem Solving from Nature, PPSN 2002*. Springer, 2002, pp. 44–53.

[7] D. Thierens, "Convergence time analysis for the multi-objective counting ones problem," in *Evolutionary Multi-Criterion Optimization, EMO 2003*. Springer, 2003, pp. 355–364.

[8] O. Giel, "Expected runtimes of a simple multi-objective evolutionary algorithm," in *Congress on Evolutionary Computation, CEC 2003*. IEEE, 2003, pp. 1918–1925.

[9] D. Brockhoff, T. Friedrich, and F. Neumann, "Analyzing hypervolume indicator based algorithms," in *Parallel Problem Solving from Nature, PPSN 2008*. Springer, 2008, pp. 651–660.

[10] A. Q. Nguyen, A. M. Sutton, and F. Neumann, "Population size matters: rigorous runtime results for maximizing the hypervolume indicator," *Theoretical Computer Science*, vol. 561, pp. 24–36, 2015.

[11] Y.-L. Li, Y.-R. Zhou, Z.-H. Zhan, and J. Zhang, "A primary theoretical study on decomposition-based multiobjective evolutionary algorithms," *IEEE Transactions on Evolutionary Computation*, vol. 20, pp. 563–576, 2016.

[12] S. Wietheger and B. Doerr, "A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III)," in *International Joint Conference on Artificial Intelligence, IJCAI 2023*. ijcai.org, 2023, pp. 5657–5665.

[13] A. Opris, D. C. Dang, F. Neumann, and D. Sudholt, "Runtime analyses of NSGA-III on many-objective problems," in *Genetic and Evolutionary Computation Conference, GECCO 2024*. ACM, 2024, pp. 1596–1604.

[14] W. Zheng and B. Doerr, "Runtime analysis of the SMS-EMOA for many-objective optimization," in *Conference on Artificial Intelligence, AAAI 2024*. AAAI Press, 2024, pp. 20874–20882.

[15] S. Ren, C. Bian, M. Li, and C. Qian, "A first running time analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)," in *Parallel Problem Solving from Nature, PPSN 2024, Part III*. Springer, 2024, pp. 295–312.

[16] S. Cerf, B. Doerr, B. Hebras, J. Kahane, and S. Wietheger, "The first proven performance guarantees for the non-dominated sorting genetic algorithm II (NSGA-II) on a combinatorial optimization problem," in *International Joint Conference on Artificial Intelligence, IJCAI 2023*. ijcai.org, 2023, pp. 5522–5530.

[17] D.-C. Dang, A. Opris, B. Salehi, and D. Sudholt, "Analysing the robustness of NSGA-II under noise," in *Genetic and Evolutionary Computation Conference, GECCO 2023*. ACM, 2023, pp. 642–651.

[18] ——, "A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation," in *Conference on Artificial Intelligence, AAAI 2023*. AAAI Press, 2023, pp. 12390–12398.

[19] B. Doerr and Z. Qu, "Runtime analysis for the NSGA-II: provable speed-ups from crossover," in *Conference on Artificial Intelligence, AAAI 2023*. AAAI Press, 2023, pp. 12399–12407.

[20] W. Zheng and B. Doerr, "Approximation guarantees for the non-dominated sorting genetic algorithm II (NSGA-II)," *IEEE Transactions on Evolutionary Computation*, 2024, in press.

[21] ——, "Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives," *IEEE Transactions on Evolutionary Computation*, vol. 28, pp. 1442–1454, 2024.

[22] V. Khare, X. Yao, and K. Deb, "Performance scaling of multi-objective evolutionary algorithms," in *International Conference on Evolutionary Multi-criterion Optimization, EMO 2003*. Springer, 2003, pp. 376–390.

[23] C. Bian, Y. Zhou, M. Li, and C. Qian, "Stochastic population update can provably be helpful in multi-objective evolutionary algorithms," in *International Joint Conference on Artificial Intelligence, IJCAI 2023*. ijcai.org, 2023, pp. 5513–5521.

[24] B. Doerr, T. Ivan, and M. S. Krejca, "Speeding up the NSGA-II with a simple tie-breaking rule," in *Conference on Artificial Intelligence, AAAI 2025*. AAAI Press, 2025, pp. 26964–26972.

[25] C. McDiarmid, "Concentration," in *Probabilistic Methods for Algorithmic Discrete Mathematics*. Berlin: Springer, 1998, vol. 16, pp. 195–248.

[26] B. Doerr, "Probabilistic tools for the analysis of randomized optimization heuristics," in *Theory of Evolutionary Computation: Recent Developments in Discrete Optimization*, B. Doerr and F. Neumann, Eds. Springer, 2020, pp. 1–87.

[27] S. Wietheger and B. Doerr, "Near-tight runtime guarantees for many-objective evolutionary algorithms," in *Parallel Problem Solving from Nature, PPSN 2024, Part IV*. Springer, 2024, pp. 153–168.

**Benjamin Doerr** received the Diploma, Ph.D., and Habilitation degrees in mathematics from the Christian-Albrechts-Universität zu Kiel, Kiel, Germany, in 1998, 2000, and 2005, respectively. He is a Full Professor with the École Polytechnique, Palaiseau, France. From 2005 to 2013, he was a Senior Researcher (tenured) with the Max Planck Institute for Informatics, Saarbrücken, Germany, and an Adjunct Professor with Saarland University, Saarbrücken. His research interests include mathematical analyses of problem-specific algorithms and randomized search heuristics as well as the development of new algorithms based on such analyses.

Prof. Doerr is an Editor of several scientific journals, among them, Artificial Intelligence, Journal of Complexity, and Natural Computing.

**Dimitri Korkotashvili** received the B.Sc. in mathematics and computer science at École Polytechnique, Palaiseau, France, in 2023. He is currently pursuing a Master's degree in Theoretical Computer Science at Institut Polytechnique de Paris (IP Paris), Palaiseau, France.

**Martin S. Krejca** received the B.Sc. and M.Sc. degree from the University of Jena, Jena, Germany, in 2012 and 2014, respectively, and the Ph.D. degree from the Hasso Plattner Institute, University of Potsdam, Potsdam, Germany, in 2019, all in computer science. He has been an Assistant Professor with École Polytechnique, Palaiseau, France, since 2022. His research interests include in particular the theoretical analysis of randomized search heuristics.