Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem

Benjamin Doerr; Dimitri Korkotashvili; Martin S. Krejca

Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem

T0 review · 0 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read NSGA-II provably fails to cover the Pareto front of many-objective LOTZ in sub-exponential time.

desk verdict Solid extension of the Zheng–Doerr lower bound from OneMinMax to LOTZ; worth refereeing, with minor proof-presentation gaps. read the letter →

arxiv 2411.10017 v1 pith:ZLAGA2UW submitted 2024-11-15 cs.NE

Benjamin Doerr , Dimitri Korkotashvili , Martin S. Krejca This is my paper · ORCID

classification cs.NE MSC 68Q2568W2090C29

keywords NSGA-IImany-objectiveoptimizationruntimeanalysisLeadingOnesTrailingZerosParetofrontcoveragecrowdingdistanceevolutionaryalgorithmtheorystandardbitmutation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that the NSGA-II, one of the most widely used multi-objective optimizers, provably struggles once the number of objectives reaches four. The benchmark is many-objective LeadingOnesTrailingZeros (mLOTZ), a problem in which most solutions are dominated, unlike the OneMinMax benchmark used in earlier negative results. With population size at most a constant factor larger than the Pareto front, the algorithm misses a constant fraction of the front for exponentially many evaluations, with overwhelming probability. The proof points to the crowding-distance tie-breaker as the bottleneck: it starts discarding Pareto-optimal solutions uniformly at random before the front is fully explored.

What carries the argument

The carrying mechanism is the comparison of two reproduction rates: with standard bit mutation, a Pareto-front parent creates an exact copy with constant probability, but creates a different Pareto optimum with probability at most m/n. Lemma 5 bounds the per-generation increase in distinct covered optima by 2amM/n; Lemma 4 shows that within O(n) generations the first non-dominated front reaches at least (1+α)N while the covered fraction stays below c2M; Lemma 3, the random selection lemma, then shows that once the first front overflows N, the crowding-distance tie-break loses a constant fraction of the covered Pareto front with high probability.

What would settle it

Compute the crowding distance of a pairwise non-dominated set for mLOTZ with, say, m=4 and n large and look for more than 4n+2m individuals with positive crowding distance; if one exists, Lemma 2, on which the whole selection-loss argument rests, is false. Alternatively, run NSGA-II with standard bit mutation, fair selection, and N=8M on 4-LOTZ with n=40 for 1000 iterations: covering all 441 Pareto optima at any iteration would directly contradict the claim that a constant fraction is always missed.

Watch

Extended reading notes

Core claim

For even m≥4 objectives, on m-objective LOTZ of size n with Pareto front of size M, the NSGA-II with N≤aM, standard bit mutation, and fair, random, or binary-tournament parent selection does not cover a constant fraction of the Pareto front for the first T iterations, with probability at least 1−T exp(−Ω(mM/n)). Consequently, the expected time to cover the full Pareto front is exponential in n. The mechanism is a race between two growth rates: while the population is still below size N on the non-dominated front, it expands mostly by exact copies of already known Pareto optima, whereas the number of distinct newly discovered optima grows only by O(mM/n) per generation. The first front therefore outgrows N before a constant fraction of the front is covered, triggering crowding-distance selection, and only O(n) individuals in any non-dominated set receive positive crowding distance, so the remaining Pareto-optimal values are discarded nearly at random.

Load-bearing premise

The proof requires standard bit mutation with bit-flip probability 1/n, which creates the needed gap between a constant-probability exact-copy rate and an at-most-m/n rate for producing a new Pareto optimum; with one-bit mutation that gap disappears and the argument, along with the empirical picture, changes.

Editorial extensions

If this is right

For any fixed even m≥4, every population size N≤aM yields the same stagnation: a constant fraction of the Pareto front remains unwitnessed for exponentially many evaluations.
The slow-growth bound applies to the combined parent-and-offspring population, not just the selected parent population, so larger offspring batches cannot circumvent the failure.
The negative result holds for fair, random, and binary-tournament parent selection, so the difficulty is not an artifact of a single selection rule.
The failure occurs while the front is still mostly unexplored: the first non-dominated front exceeds N before even a constant fraction of the Pareto optima are covered.
The proof implies a quantitative path to the failure: a missing fraction at least d(α)M appears once the first front reaches (1+α)N, with α=1/(12ae).
An extension the proof leaves open is the superlinear-population regime: taking N to grow faster than M would delay the first-front overflow and might escape the barrier, since the argument relies on N being within a constant factor of M.
Because the proved mechanism is the crowding-distance tie-break, replacing that tie-break with a reference-point or hypervolume-based secondary selection is the natural test of the causal story, and the paper's cited results on NSGA-III and SMS-EMOA already point in that direction.
One-bit mutation is the live escape hatch: since it never creates an exact copy, it breaks the multiplicative growth of known optima in Lemma 4, which likely explains the larger coverage seen in the paper's experiments; testing one-bit mutation on larger instances would settle whether it fully escapes the lower bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this is a solid, non-routine extension of the Zheng–Doerr negative result, and it deserves a serious referee. The real news is that the NSGA-II's crowding-distance failure is not an artifact of OneMinMax's all-optimal landscape. The authors prove for mLOTZ—where most solutions are dominated—that with population size at most a constant factor above the Pareto front, the combined parent-offspring population misses a constant fraction of the front for exponential time, for m >= 4 objectives. The proof genuinely needs new population dynamics: Lemma 5's union bound on new Pareto optima via critical bits is clean, and Lemma 4's copy-growth phase is the right way to show the first front outgrows N before the front is covered. Extending to random and binary tournament selection via a general parent-choice condition is a nice touch. The experiments are honest, including the one-bit mutation variant that visibly covers more of the front, and the paper flags that this variant is not covered by the proof—that is a disclosed limitation, not a counterexample.

Soft spots are minor. The expected-exponential-runtime corollary is stated as 'consequently' without a formal derivation; it follows from the high-probability statement by standard arguments, but a few lines would remove the gap. Lemma 3's random-selection proof is compressed, and the definition of d(alpha) is hard to parse; the positive-fraction conclusion is plausible but deserves a clearer derivation. There are small typos (e.g., the 'X <= e/3' bound in Lemma 4), and the experiments use n=40 and single runs, so they are illustrative rather than statistically strong. The paper's own end-of-Section-3 note about one-bit mutation is an important boundary: the negative result does not apply to all NSGA-II variants, and the empirically better coverage of one-bit mutation is left unexplained. That is fine for this paper, but it should be kept visible in any summary.

On overlap with [ZD24b]: importing Lemmas 2 and the random-selection argument from there is legitimate; those results are proven elsewhere and do not assume the current theorem. The authorship overlap is a dependency, not circularity. The citation pattern is appropriate.

Who is this for: runtime-analysis researchers and anyone who uses NSGA-II in many-objective settings and wants evidence about when crowding distance is the bottleneck. I would take it to a reading group and would cite it. Recommendation: send to peer review. The main theorem is the kind of precisely scoped negative result that the community needs, and the remaining issues are presentation-level.

Referee Report

0 major / 5 minor

Summary. The paper proves a lower bound for the NSGA-II on the many-objective LeadingOnesTrailingZeros (mLOTZ) benchmark. For an even number of objectives m >= 4, population size N <= aM (where M is the size of the Pareto front and a > 1 is a constant), fair parent selection, and standard bit mutation, the authors show that with probability at least 1 - T exp(-Omega(mM/n)) the combined parent and offspring population misses a constant fraction of the Pareto front for all t <= T. This implies an exponential expected runtime for covering the full Pareto front. The proof analyzes the dynamics of the first non-dominated front, showing that the front grows above N by duplicating existing Pareto-optimal values before a constant fraction of the Pareto front is discovered; once the crowding distance becomes decisive, the random-selection lemma (Lemma 3) shows that many Pareto-optimal values are lost. The result is extended to random and binary-tournament parent selection in Theorem 6. Experiments on 4-LOTZ support the theoretical findings and additionally explore one-bit mutation and crossover, which are not covered by the proof.

Significance. If the result holds, it substantially extends the known limitations of the NSGA-II from the OneMinMax benchmark (where every solution is Pareto-optimal) to a benchmark with a realistic dominated-solution structure, strengthening the evidence that the crowding-distance mechanism is the cause of the algorithm's poor many-objective performance. The main technical contribution is a careful population-dynamics analysis of the first front, including a quantitative bound on the growth of Pareto-optimal value diversity (Lemma 5) and a copy-growth argument (Lemma 4) that is the heart of the proof. The paper is honest about its scope: it explicitly states that the proof does not cover one-bit mutation or crossover, and it provides experiments that are consistent with the theory. The generalization to random and tournament selection in Theorem 6 is valuable, and the negative result is stated with a precise failure probability rather than as a vague impossibility claim. The proof chain is detailed and checkable, and I did not find a load-bearing error.

minor comments (5)

[Section 3, Lemma 4, proof of Part 2] The line "Pr[X <= e/3] <= Pr[X <= E[X]/2]" appears to contain a typo: the event "X <= e/3" is not the one needed for the subsequent Chernoff bound. It should presumably read "Pr[X <= E[X]/2] <= exp(-Omega(E[X]))" or use a threshold of the form E[X]/2; please correct the displayed inequality.
[Section 3, proof of Theorem 1] The sentence claiming that the parent population "never covered more than (1 - c2)M points of the Pareto front" is inconsistent with Lemma 4, which provides an upper bound of c2M (so the missing fraction is at least (1 - c2)M). The phrase "(1 - c2)M" should be "c2M" or the sentence should be reworded to say the population always misses at least (1 - c2)M points.
[Abstract and Introduction] The claim that the high-probability bound of Theorem 1 implies an exponential expected runtime is stated but not derived. A short argument—choosing T = exp(epsilon n) with epsilon smaller than the implicit constant in Omega(mM/n), applying the union bound, and noting mM/n = Omega(n) for constant m >= 4—would make the paper self-contained.
[Section 3, Lemma 5, proof] The definitions of l_i and r_i (first 0 from the left and first 1 from the right in a block) do not cover blocks that are all 0s or all 1s. The argument still works because such blocks have only one critical bit (or none if the parent is already Pareto-optimal), but a clarifying sentence would remove ambiguity.
[Throughout] Several minor typos and stylistic issues: "NGSA-II" in the abstract should be "NSGA-II"; "all positive result" in the Introduction should be "all positive results"; "the short-comings" should be "the shortcomings"; the sentence "This benchmark does not have the particularity that all solutions are Pareto-optimal, rather the vast majority..." is a comma splice; and "m in Z>=4" is unconventional, as Z>=4 is not standard notation—"even integer m >= 4" would be clearer.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is derived from population dynamics, and imported lemmas are independent prior results with disclosed scope.

full rationale

The paper's central claim is not circular. Theorem 1 is derived from a chain of lemmas: Lemma 5 bounds the rate at which new Pareto optima are created using standard bit mutation; Lemma 4 converts a multiplicative growth of duplicate Pareto-optimal individuals into the condition |F1| > (1+alpha)N before c2M distinct optima are covered; Lemma 3 then shows that random removal of zero-crowding-distance individuals loses a constant fraction. Each step is either proved in the paper or imported from [ZD24b] as a standalone lemma (Lemma 2) with stated assumptions that do not include the target result. The overlap in authorship with [ZD24b] is not a circular dependency: the cited lemma is a general combinatorial fact about crowding distance, not a restatement of the LOTZ inefficiency result. The choice of constants c1, c2, alpha is a closing argument, not a fitted input; d(alpha) is used to define c1 = 1 - d(alpha), so the conclusion M' <= c1M is the mechanism of Lemma 3, not an assumption. No parameter is fitted to data, no prediction is defined in terms of the result, and no uniqueness claim is imported from the authors' prior work. The one-bit-mutation and crossover gaps are explicitly disclosed limitations at the end of Section 3, and the experiments present them as outside the theorem's scope rather than as evidence for the theorem. Hence the derivation is self-contained with respect to the stated theorem, and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data. The theorem is asymptotic in n for any constant a>1; the internal constants alpha=1/(12ae), c1, c2 are fixed choices in the proof, not empirical fits. The mathematical axioms are standard concentration inequalities and the definitions of the benchmark and algorithm. Lemma 2 is imported from the authors' earlier published work [ZD24b], which the present paper generalizes. No new entities are postulated.

assumptions (4)

standard math Chernoff bound and McDiarmid's inequality for bounded-difference random variables
Used in the proofs of Lemmas 3, 4, and 5 to obtain exponential tail bounds; cited from [Doe20].
domain assumption Definition of m-objective LOTZ and its Pareto front size M=(2n/m+1)^{m/2}
The benchmark and its Pareto structure are taken as given in Section 2.2.
domain assumption Lemma 2 from [ZD24b]: at most 4n+2m individuals in a pairwise non-dominated set have positive crowding distance for objectives with at most n+1 values
Imported without proof and used to seed the random-selection lemma (Lemma 3); the authors note the proof transfers from OneMinMax.
domain assumption The NSGA-II is executed with a multi-set population, standard bit mutation with per-bit probability 1/n, and no crossover
The theorem's scope is fixed by these choices in Sections 2.3 and 3; the authors explicitly state the proof does not extend to one-bit mutation or crossover.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem." pith.science (2026). https://pith.science/paper/ZLAGA2UW

@misc{pith2026241110017,
  author       = {Pith},
  title        = {Pith review of: Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZLAGA2UW}},
  note         = {Machine review of arXiv:2411.10017}
}

read the original 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 NGSA-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.

Figures

Figures reproduced from arXiv: 2411.10017 by the authors.

**Figure 2.** The number of individuals in the non-dominated subpopulation [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

**Figure 3.** The number of distinct objective values on the Pareto front of the [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The number of distinct objective values on the Pareto front of [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
cs.NE 2024-12 conditional novelty 7.0 of 10

A simple tie-break favoring rarer objective values in NSGA-II provably removes two known efficiency problems: poor handling of three or more objectives and linear runtime growth with population size.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

Analyz- ing hypervolume indicator based algorithms

[BFN08] Dimo Brockhoff, Tobias Friedrich, and Frank Neumann. Analyz- ing hypervolume indicator based algorithms. In Parallel Problem Solving from Nature, PPSN 2008, pages 651–660. Springer,

work page 2008
[5]

A proof that using crossover can guarantee exponential speed- ups in evolutionary multi-objective optimisation

[DOSS23b] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. A proof that using crossover can guarantee exponential speed- ups in evolutionary multi-objective optimisation. In Conference on Artificial Intelligence, AAAI 2023 , pages 12390–12398. AAAI Press,

work page 2023
[7]

Expected runtimes of a simple multi-objective evo- lutionary algorithm

[Gie03] Oliver Giel. Expected runtimes of a simple multi-objective evo- lutionary algorithm. In Congress on Evolutionary Computation, CEC 2003 , pages 1918–1925. IEEE,

work page 2003
[12]

Convergence time analysis for the multi-objective counting ones problem

[Thi03] Dirk Thierens. Convergence time analysis for the multi-objective counting ones problem. In Evolutionary Multi-Criterion Opti- mization, EMO 2003 , pages 355–364. Springer,

work page 2003
[13]

A mathematical run- time analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

[WD23] Simon Wietheger and Benjamin Doerr. A mathematical run- time analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2023 , pages 5657–5665. ijcai.org,

work page 2023
[14]

Near-tight runtime guar- antees for many-objective evolutionary algorithms

[WD24] Simon Wietheger and Benjamin Doerr. Near-tight runtime guar- antees for many-objective evolutionary algorithms. In Parallel Problem Solving from Nature, PPSN 2024, Part IV , pages 153–

work page 2024
[15]

[ZD24b] Weijie Zheng and Benjamin Doerr

In press, https://doi.org/10.1109/TEVC.2024.3402996. [ZD24b] Weijie Zheng and Benjamin Doerr. Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Transactions on Evolutionary Com- putation, 28:1442–1454,

arXiv 2024
[16]

Runtime analysis of the SMS- EMOA for many-objective optimization

[ZD24c] Weijie Zheng and Benjamin Doerr. Runtime analysis of the SMS- EMOA for many-objective optimization. In Conference on Arti- ficial Intelligence, AAAI 2024 , pages 20874–20882. AAAI Press,

work page 2024

Show all 17 references

[17]

A first mathe- matical runtime analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)

25 [ZLD22] Weijie Zheng, Yufei Liu, and Benjamin Doerr. A first mathe- matical runtime analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). In Conference on Artificial Intelligence, AAAI 2022 , pages 10408–10416. AAAI Press,

2022
[2002]

Runtime analysis for the NSGA-II: provable speed-ups from crossover

[DQ23] Benjamin Doerr and Zhongdi Qu. Runtime analysis for the NSGA-II: provable speed-ups from crossover. In Conference on Artificial Intelligence, AAAI 2023 , pages 12399–12407. AAAI Press,

2023
[2003]

Running time analysis of multi-objective evolu- tionary algorithms on a simple discrete optimization problem

[LTZ+02] Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. Running time analysis of multi-objective evolu- tionary algorithms on a simple discrete optimization problem. In Parallel Problem Solving from Nature, PPSN 2002 , pages 44–53. Springer,

2002
[2008]

Stochas- tic population update can provably be helpful in multi-objective evolutionary algorithms

[BZLQ23] Chao Bian, Yawen Zhou, Miqing Li, and Chao Qian. Stochas- tic population update can provably be helpful in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2023 , pages 5513–5521. ijcai.org,

2023
[2010]

Khare, X

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

2003
[2015]

Runtime analyses of NSGA-III on many-objective prob- lems

[ODNS24] Andre Opris, Duc Cuong Dang, Frank Neumann, and Dirk Sud- holt. Runtime analyses of NSGA-III on many-objective prob- lems. In Genetic and Evolutionary Computation Conference, GECCO 2024 , pages 1596–1604. ACM,

2024
[2020]

[DOSS23a] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt

Also available at https://arxiv.org/abs/1801.06733. [DOSS23a] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. Analysing the robustness of NSGA-II under noise. In Genetic and Evolutionary Computation Conference, GECCO 2023, pages 642–651. ACM,

2023 arXiv
[2023]

The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA- II) on a combinatorial optimization problem

[CDH+23] Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Jakob Kahane, and Simon 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 Artifici...

2023
[2024]

A first running time analysis of the Strength Pareto Evolutionary Al- gorithm 2 (SPEA2)

[RBLQ24] Shengjie Ren, Chao Bian, Miqing Li, and Chao Qian. A first running time analysis of the Strength Pareto Evolutionary Al- gorithm 2 (SPEA2). In Parallel Problem Solving from Nature, PPSN 2024, Part III , pages 295–312. Springer,

2024

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Analyz- ing hypervolume indicator based algorithms

[BFN08] Dimo Brockhoff, Tobias Friedrich, and Frank Neumann. Analyz- ing hypervolume indicator based algorithms. In Parallel Problem Solving from Nature, PPSN 2008, pages 651–660. Springer,

work page 2008

[2] [5]

A proof that using crossover can guarantee exponential speed- ups in evolutionary multi-objective optimisation

[DOSS23b] Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. A proof that using crossover can guarantee exponential speed- ups in evolutionary multi-objective optimisation. In Conference on Artificial Intelligence, AAAI 2023 , pages 12390–12398. AAAI Press,

work page 2023

[3] [7]

Expected runtimes of a simple multi-objective evo- lutionary algorithm

[Gie03] Oliver Giel. Expected runtimes of a simple multi-objective evo- lutionary algorithm. In Congress on Evolutionary Computation, CEC 2003 , pages 1918–1925. IEEE,

work page 2003

[4] [12]

Convergence time analysis for the multi-objective counting ones problem

[Thi03] Dirk Thierens. Convergence time analysis for the multi-objective counting ones problem. In Evolutionary Multi-Criterion Opti- mization, EMO 2003 , pages 355–364. Springer,

work page 2003

[5] [13]

A mathematical run- time analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)

[WD23] Simon Wietheger and Benjamin Doerr. A mathematical run- time analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2023 , pages 5657–5665. ijcai.org,

work page 2023

[6] [14]

Near-tight runtime guar- antees for many-objective evolutionary algorithms

[WD24] Simon Wietheger and Benjamin Doerr. Near-tight runtime guar- antees for many-objective evolutionary algorithms. In Parallel Problem Solving from Nature, PPSN 2024, Part IV , pages 153–

work page 2024

[7] [15]

[ZD24b] Weijie Zheng and Benjamin Doerr

In press, https://doi.org/10.1109/TEVC.2024.3402996. [ZD24b] Weijie Zheng and Benjamin Doerr. Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Transactions on Evolutionary Com- putation, 28:1442–1454,

arXiv 2024

[8] [16]

Runtime analysis of the SMS- EMOA for many-objective optimization

[ZD24c] Weijie Zheng and Benjamin Doerr. Runtime analysis of the SMS- EMOA for many-objective optimization. In Conference on Arti- ficial Intelligence, AAAI 2024 , pages 20874–20882. AAAI Press,

work page 2024