Pith. sign in

REVIEW 3 major objections 4 minor 55 references

Speeding Up the NSGA-II With a Simple Tie-Breaking Rule

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A tie-break that prefers rarer objective values fixes both known failings of the NSGA-II: many-objective inefficiency and population-size sensitivity.

desk verdict A valuable but imperfect paper: the balanced NSGA-II result is real, yet Theorem 3's OJZJ bound is off by n^{k-1}, Theorem 5 lacks a proof, and Theorem 13 has a bad inequality—all fixable. read the letter →

arxiv 2412.11931 v2 pith:G6AZ4TAM submitted 2024-12-16 cs.NE

Benjamin Doerr , Tudor Ivan , Martin S. Krejca This is my paper · ORCID
classification cs.NE MSC 68Q2568W50
keywords NSGA-IItie-breakingmany-objectiveoptimizationruntimeanalysiscrowdingdistanceOneMinMaxJumpZeropopulationsize
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

This paper tries to establish that a single, simple change to the selection step of the NSGA-II removes the two proven weaknesses of the most widely used multi-objective optimizer: exponential-time behavior on problems with three or more objectives, and a runtime that grows linearly with the population size. The change is to break ties in the final selection stage by first taking an equal share of individuals from each distinct objective value, instead of choosing uniformly at random among the tied candidates. If the arguments are correct, practitioners can use the NSGA-II on many-objective problems without the exponential slowdown, and they no longer have to tune the population size precisely. The paper proves polynomial expected runtimes for a constant number of objectives on the three standard benchmark problems, and bi-objective runtime guarantees that stay flat while the population size varies over a wide range.

What carries the argument

The load-bearing object is the balanced tie-breaking rule itself. In the classic NSGA-II, when the population has been filtered by non-dominated rank and then by crowding distance, the remaining ties are broken uniformly at random; the balanced rule instead partitions the tied candidates by objective value, selects floor(s/a) individuals from each of the a distinct values, and only then fills the remaining slots randomly. The proof machinery is the survival property (Lemma 4): if the population size N is at least S + U, where S is the size of the largest set of pairwise incomparable solutions and U is the maximum number of individuals with positive crowding distance in such a set, then every objective value occupying the first non-dominated front survives into the next generation. Because U is at most 2m(n'+1) for the three benchmarks, a population size exceeding the Pareto front size by only O(mn) suffices, which is what converts the classic algorithm's exponential many-objective failure and its N-dependent runtime into polynomial, N-independent guarantees.

What would settle it

Run the balanced NSGA-II on a many-objective problem for which a set of pairwise incomparable solutions contains more than 2m(n'+1) individuals with positive crowding distance, using population size N = S + 2m(n'+1), and check whether a Pareto-optimal objective value disappears from the population; any loss would falsify the survival property. Separately, the 3-objective OneMinMax bound is stated without its full proof, so a direct simulation at n = 40 with N set to the stated threshold could either confirm the predicted fast coverage or expose a missing condition.

Watch

Extended reading notes

Core claim

The central claim is that replacing the uniform random tie-break in the NSGA-II's final selection step with a balanced one—first taking floor(s/a) individuals from each distinct objective value among the tied candidates, then filling the remaining slots randomly—makes the algorithm provably efficient where the classic version is provably bad. On the m-objective versions of OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump with even m ≥ 4 and constant gap parameter k, the balanced NSGA-II with population size N at least S + 2m(n'+1) finds the whole Pareto front in polynomial expected time (Theorem 3), whereas the classic algorithm needs exponential time on many-objective OneMinMax. The same mechanism yields a polynomial bound for 3-objective OneMinMax (Theorem 5). For the bi-objective versions, the guarantee on OneJumpZeroJump is O(max{$n^{{k+1}}$, N n}) function evaluations when N ≥ 4(n−2k+3), so for N between 4(n−2k+3) and O(n^k) the runtime is O($n^{{k+1}}$), an improvement over the classic algorithm's Θ(N n^k) runtime; similar flat-guarantee results hold for OneMinMax and LeadingOnesTrailingZeros. All of this hangs on the survival property (Lemma 4): once the population size exceeds the size of the largest pairwise-incomparable set plus the maximum number of positive-crowding-distance individuals in such a set, an objective value that appears in the first non-dominated front is never lost.

Load-bearing premise

The entire many-objective argument rests on the previously proven bound that any set of pairwise incomparable solutions contains at most 2m(n'+1) individuals with positive crowding distance; if some problem admitted more, the required population size would rise and the polynomial-time guarantee could fail.

Editorial extensions

If this is right

  • On any even constant number m ≥ 4 of objectives, the balanced NSGA-II with population size N ≥ S + 2m(n'+1) finds the full Pareto front of OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump in polynomial expected time, directly contradicting the exponential lower bound proven for the classic NSGA-II on many-objective OneMinMax.
  • For 3-objective OneMinMax, population size N ≥ (n/2+1)^2 + 4n + 6 suffices for an expected O(n^3) iteration bound, extending the fix to the smallest odd many-objective case.
  • On bi-objective OneJumpZeroJump, the expected runtime is O(max{n^{k+1}, N n}) function evaluations for all N ≥ 4(n−2k+3), so in the range N ∈ [4(n−2k+3), O(n^k)] the runtime does not depend on N at all, versus the classic algorithm's Θ(N n^k).
  • On bi-objective OneMinMax and LeadingOnesTrailingZeros the guarantees are O(N n + n^2 log n) and O(n^3 + N n log(N/(n+1))) function evaluations, meaning moderately larger population sizes cost asymptotically nothing, where classic NSGA-II lower bounds show a real linear penalty.
  • The empirical section shows the balanced NSGA-II's advantage is already statistically significant at population sizes 8M and 16M (M the Pareto front size), and that it covers the 4-objective OneMinMax Pareto front quickly where the classic algorithm stagnates below 60% coverage.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The survival property is proved for general m-objective problems, not just the three benchmarks, so the balanced rule should confer polynomial many-objective guarantees on any problem where the positive-crowding-distance count U stays within O(mn) and incomparable-set size S is polynomial; testing this on a different benchmark family would show whether the fix is general.
  • Because balanced selection acts only on objective-value multiplicities, the same idea transfers directly to other population-based multi-objective algorithms that break ties randomly, such as reference-point or hypervolume-based selectors, potentially removing their population-size sensitivity too.
  • The bi-objective results point to an open gap: the paper's bounds treat N = O(n^k) on OneJumpZeroJump as flat, but no matching lower bound is shown, so the true N-dependence in the intermediate regime is unknown; a targeted lower bound would tell practitioners exactly how large a safety margin they can afford.
  • A practical reading is that the tie-breaker is nearly free: the paper measures the balanced procedure as about 10x slower per tie-break operation and roughly 15% of the non-dominated sorting time, so any run that currently tunes N could instead adopt the balanced rule and skip the tuning effort.
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.

Referee Report

3 major / 4 minor

Summary. This paper proposes a simple modification to the NSGA-II: when the final tie-break among individuals with equal crowding distance in the critical rank is required, the algorithm selects individuals as evenly as possible among distinct objective values ('balanced tie-breaking') instead of uniformly at random. The authors prove runtime guarantees for the resulting 'balanced NSGA-II' on OneMinMax (OMM), LeadingOnesTrailingZeros (LOTZ), and OneJumpZeroJump (OJZJ). For even numbers of objectives m >= 4 and constant m and k, they show polynomial expected runtimes on the many-objective versions of these benchmarks (Theorem 3), in contrast to the exponential lower bound for the classic NSGA-II on OMM with m >= 3 (Zheng and Doerr 2024b). A separate theorem (Theorem 5) treats the 3-objective OMM case. For the bi-objective problems, they prove bounds that do not grow with N over a wide range: O(max{Nn, n^{k+1}}) function evaluations for OJZJ with N between 4(n-2k+3) and O(n^k) (Theorem 13), O(Nn + n^2 log n) for OMM (Corollary 9), and O(n^3 + Nn log n) for LOTZ (Theorem 15). The results are supported by experiments with publicly available code.

Significance. If correct, the results are significant: they show that a minimal, easily implementable change to the selection operator resolves two previously identified deficiencies of the most widely used multi-objective optimizer—its exponential-time difficulty for many-objective OMM and its linear dependence on population size in bi-objective settings. The paper gives concrete, falsifiable runtime bounds and validates them empirically with released code and statistical testing. In particular, the improvement for OJZJ from Theta(N n^k) to O(N n + n^{k+1}) function evaluations for a wide range of N is a noteworthy theoretical advance. The proofs are mostly detailed and build on established lemmas from prior work; the survival property (Lemma 4) is a clean, reusable statement. However, as detailed in the major comments, the many-objective OJZJ bound of Theorem 3 contains a probability miscalculation, Theorem 5 lacks its proof, and the large-N part of the Theorem 13 proof uses an invalid inequality. These are correctable and do not appear to threaten the qualitative polynomial-time conclusions for constant k and m.

major comments (3)
  1. [Theorem 3, OJZJ case (main text and Appendix 'Proof of Theorem 3')] In the proof of Theorem 3, the OJZJ paragraph asserts that, once the population has reached the Pareto front, generating a missing Pareto-optimal point y from an existing point x with Hamming distance at most k succeeds with probability at least 1/(2enk) per iteration, 'analogous to the computation further above'. The analogous computation for distance 1 gives 1/(en) for a single mutation; for a k-bit jump (e.g., from an inner-front string with |x|_1 = k in a block to 0^{n'}), the single-mutation probability is (1/n)^k(1-1/n)^{n-k} >= 1/(e n^k). The correct per-iteration lower bound is therefore about 1/(2e n^k), not 1/(2e n k). Consequently the stated bound 2enkM in Theorem 3 is too small by a factor of n^{k-1}, and should be replaced by O(n^k M) iterations. The polynomial-time conclusion for constant k remains valid, but the theorem as stated and its proof need correction.
  2. [Appendix, Proof of Theorem 13] In the proof of Theorem 13, for the case N > 4n, the argument uses (1-2^{-n})^N <= exp(-2^{-n}N) <= exp(-N^{1/2}). The second inequality requires 2^{-n}N >= N^{1/2}, i.e., N >= 4^n, which is not implied by N > 4n. For population sizes in (4n, 4^n), the claimed bound that the expected number of iterations is o(1) does not follow; indeed for N = n^2 the initial population misses a given search point with probability close to 1. The proof should be repaired, for example by treating N <= 4^n separately (where log(N/n) = O(n)) and using the exponential coverage argument only for N > 4^n.
  3. [Appendix, 'Discussion of Theorem 5'] Theorem 5, which establishes the polynomial-time result for the 3-objective OMM benchmark, is not proved; the appendix states only that the proof is 'completely analogous' to the even-objective case and is omitted. Since the m = 3 case is precisely the setting of the exponential lower bound for the classic NSGA-II (Zheng and Doerr 2024b) and is highlighted in the abstract and introduction, this is a central result. The full proof should be provided, in particular the computation of the waiting times given the different numbers of values taken by the three objectives (n+1 for f1 versus n/2+1 for f2 and f3) entering the bound U = 4n+6.
minor comments (4)
  1. [Appendix, Proof of Lemma 1] The phrase 'If li = 0 or li = 2N' should presumably be 'If li = 1 or li = 2N', since the sorted lists are indexed from 1 to 2N.
  2. [Lemmas 12 and 13] The notation O(log N/n) is ambiguous; it should be written as O(log(N/n)) if the ratio is meant, or as O((log N)/n) if the latter is intended.
  3. [Appendix, Proof of Lemma 7] The statement 'as we assume n big enough, hence n >= 2' is informal; the argument should explicitly note that (1-1/n)^n >= 1/(2e) for all n >= 2, or add the assumption.
  4. [Table 1 caption] The caption contains a grammar error: 'the balanced NSGA-II being lower that of the classic NSGA-II' should be 'lower than that of'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the balanced NSGA-II analysis is a new derivation built on independently published lemmas; cited prior results are external evidence, not the paper's conclusions.

full rationale

The paper's central object, the balanced tie-breaking rule, is explicitly defined in the paper rather than imported by citation: 'We replace line 11 in Algorithm 1 with the following procedure...' and the runtime theorems are derived from that definition. The most load-bearing external ingredient is the bound U = 2m(n'+1) on the number of individuals with positive crowding distance in a set of pairwise incomparable or equal-valued individuals, cited from Zheng and Doerr (2024b) and used in Lemma 4 and Theorem 3. That bound is a published, parameter-free combinatorial lemma about the classic crowding-distance definition; it does not assume the balanced NSGA-II's efficiency or any runtime conclusion of this paper, so relying on it is a normal mathematical dependency, not circularity. Similarly, the bi-objective proofs reuse lemmas from Zheng, Liu, and Doerr (2022), Zheng and Doerr (2023), Doerr and Qu (2023a), and the multiplicative up-drift theorem of Doerr and Kötzing (2021); these are stated with their own assumptions and do not contain the present paper's target results. No fitted parameter is renamed as a prediction: every quantity in the bounds is a problem parameter (n, k, m, N, M, S, U) or a directly estimated waiting time. Two non-circular concerns should be flagged separately: Theorem 5 is stated with only a 'completely analogous ... and thus omitted' proof, which is a completeness gap rather than circularity; and the many-objective OJZJ proof's claim that generating a missing Pareto-optimal point occurs with probability at least 1/(2enk) 'analogous to the computation further above' appears to undercount a k-bit jump by roughly n^{k-1}, a quantitative correctness risk that does not change the circularity verdict. On the circularity axis, the derivation chain is self-contained against external benchmarks and prior published lemmas, so the appropriate score is 0.

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

The paper introduces no new entities or fitted parameters. It relies on standard prior results from the runtime-analysis literature, mostly by the same research group, plus the standard bit-mutation model. The only implicit conditions are the population-size thresholds N >= 4(n+1) (or N >= S+U) that make the survival property hold; these are stated explicitly in the theorems.

assumptions (4)
  • standard math Multiplicative up-drift theorem (Doerr and Koetzing 2021, Theorem 3) bounds expected hitting times for processes satisfying a binomial drift condition.
    Used in Lemma 7, Lemma 14, and the LOTZ analysis to bound time until subpopulations reach desired sizes; external proven theorem, not a paper-specific assumption.
  • standard math Lemma 1 from Zheng, Liu, and Doerr (2022): a Pareto-optimal objective value present in the combined population is never lost under the selection procedure.
    Invoked in the bi-objective OMM analysis (Lemma 16) and LOTZ analysis (Lemma 20) as a prior proven result; the present paper notes it applies unchanged because it does not depend on the final tie-breaker.
  • standard math Upper bound U = 2m(n'+1) on the number of individuals with positive crowding distance in any set of pairwise incomparable solutions (from Zheng and Doerr 2024b).
    Used in Lemma 4 and Theorem 3 to ensure survival of all objective values; if this bound were wrong, the population size condition N >= S+U would fail.
  • domain assumption Standard bit mutation: each offspring is a copy of a uniformly random parent with each bit flipped independently with probability 1/n.
    All runtime proofs compute probabilities of specific mutations under this operator; it is the standard model in runtime analysis of evolutionary algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Speeding Up the NSGA-II With a Simple Tie-Breaking Rule." pith.science (2026). https://pith.science/paper/G6AZ4TAM

@misc{pith2026241211931,
  author       = {Pith},
  title        = {Pith review of: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G6AZ4TAM}},
  note         = {Machine review of arXiv:2412.11931}
}
abstract

The non-dominated sorting genetic algorithm~II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.

Figures

Figures reproduced from arXiv: 2412.11931 by the authors.

Figure 1
Figure 1. The average number of function evaluations of [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. The average number of function evaluations of [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. The average number of function evaluations of [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Average runtimes of the balanced NSGA-II with [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 40 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Auger, A.; and Doerr, B., eds. 2011. Theory of Randomized Search Heuristics. World Scientific Publishing

    work page 2011

  4. [4]

    Beume, N.; Naujoks, B.; and Emmerich, M. 2007. SMS-EMOA : Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181: 1653--1669

    2007

  5. [5]

    Bian, C.; and Qian, C. 2022. Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection. In Parallel Problem Solving From Nature, PPSN 2022, 428--441. Springer

    work page 2022

  6. [6]

    Bian, C.; Qian, C.; and Tang, K. 2018. A general approach to running time analysis of multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2018 , 1405--1411. ijcai.org

    work page 2018

  7. [7]

    Bian, C.; Ren, S.; Li, M.; and Qian, C. 2024. An archive can bring provable speed-ups in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2024 , 6905--6913. ijcai.org

    2024

  8. [8]

    Bian, C.; Zhou, Y.; Li, M.; and Qian, C. 2023. Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2023, 5513--5521. ijcai.org

    2023

Show all 55 references
  1. [9]

    Bossek, J.; and Sudholt, D. 2024. Runtime analysis of quality diversity algorithms. Algorithmica, 86: 3252--3283

    2024

  2. [10]

    Brockhoff, D.; Friedrich, T.; and Neumann, F. 2008. Analyzing hypervolume indicator based algorithms. In Parallel Problem Solving from Nature, PPSN 2008 , 651--660. Springer

    2008

  3. [11]

    Cerf, S.; Doerr, B.; Hebras, B.; Kahane, J.; and Wietheger, S. 2023. The first proven performance guarantees for the N on- D ominated S orting G enetic A lgorithm II ( NSGA-II ) on a combinatorial optimization problem. In International Joint Conference on Artificial Intelligen...

    2023

  4. [12]

    Coello, C. A. C.; Lamont, G. B.; and van Veldhuizen, D. A. 2007. Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, 2nd edition

    2007

  5. [13]

    Covantes Osuna, E.; Gao, W.; Neumann, F.; and Sudholt, D. 2020. Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation. Theoretical Computer Science, 832: 123--142

    2020

  6. [14]

    Dang, D.-C.; Opris, A.; Salehi, B.; and Sudholt, D. 2023 a . Analysing the robustness of NSGA-II under noise. In Genetic and Evolutionary Computation Conference, GECCO 2023, 642--651. ACM

    2023

  7. [15]

    Dang, D.-C.; Opris, A.; Salehi, B.; and Sudholt, D. 2023 b . A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. In Conference on Artificial Intelligence, AAAI 2023 , 12390--12398. AAAI Press

    2023

  8. [16]

    Deb, K.; and Jain, H. 2014. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18: 577--601

    2014

  9. [17]

    Deb, K.; Pratap, A.; Agarwal, S.; and Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II . IEEE Transactions on Evolutionary Computation, 6: 182--197

    2002

  10. [18]

    Deng, R.; Zheng, W.; Li, M.; Liu, J.; and Doerr, B. 2024. Runtime analysis for state-of-the-art multi-objective evolutionary algorithms on the subset selection problem. In Affenzeller, M.; Winkler, S. M.; Kononova, A. V.; Trautmann, H.; Tusar, T.; Machado, P.; and B \" a ck, T...

    2024

  11. [19]

    Doerr, B.; Ivan, T.; and Krejca, M. S. 2024. Speeding Up the NSGA-II With a Simple Tie-Breaking Rule (Code). Zenodo. https://doi.org/10.5281/zenodo.14501034

    2024 doi

  12. [20]

    Doerr, B.; Kodric, B.; and Voigt, M. 2013. Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In Congress on Evolutionary Computation, CEC 2013, 432--439. IEEE

    2013

  13. [21]

    Doerr, B.; Korkotashvili, D.; and Krejca, M. S. 2024. Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem. CoRR, abs/2411.10017

    2024 arXiv

  14. [22]

    Doerr, B.; and K \" o tzing, T. 2021. Multiplicative up-drift. Algorithmica, 83: 3017--3058

    2021

  15. [23]

    Doerr, B.; and K \" u nnemann, M. 2015. Optimizing linear functions with the (1+ ) evolutionary algorithm---different asymptotic runtimes for different instances. Theoretical Computer Science, 561: 3--23

    2015

  16. [24]

    Doerr, B.; and Neumann, F., eds. 2020. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization. Springer. Also available at http://www.lix.polytechnique.fr/Labo/Benjamin.Doerr/doerr_neumann_book.html

    2020

  17. [25]

    Doerr, B.; and Qu, Z. 2023 a . A first runtime analysis of the NSGA-II on a multimodal problem. IEEE Transactions on Evolutionary Computation, 27: 1288--1297

    2023

  18. [26]

    Doerr, B.; and Qu, Z. 2023 b . From understanding the population dynamics of the NSGA-II to the first proven lower bounds. In Conference on Artificial Intelligence, AAAI 2023 , 12408--12416. AAAI Press

    2023

  19. [27]

    Doerr, B.; and Qu, Z. 2023 c . Runtime analysis for the NSGA-II: Provable speed-ups from crossover. In Conference on Artificial Intelligence, AAAI 2023 , 12399--12407. AAAI Press

    2023

  20. [28]

    Doerr, B.; and Zheng, W. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021 , 12293--12301. AAAI Press

    2021

  21. [29]

    Droste, S.; Jansen, T.; and Wegener, I. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276: 51--81

    2002

  22. [30]

    Fortin, F.; and Parizeau, M. 2013. Revisiting the NSGA-II crowding-distance computation. In Genetic and Evolutionary Computation Conference, GECCO 2013 , 623--630. ACM

    2013

  23. [31]

    Giel, O. 2003. Expected runtimes of a simple multi-objective evolutionary algorithm. In Congress on Evolutionary Computation, CEC 2003 , 1918--1925. IEEE

    2003

  24. [32]

    Giel, O.; and Lehre, P. K. 2010. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation, 18: 335--356

    2010

  25. [33]

    Huang, Z.; Zhou, Y.; Luo, C.; and Lin, Q. 2021. A runtime analysis of typical decomposition approaches in MOEA/D framework for many-objective optimization problems. In International Joint Conference on Artificial Intelligence, IJCAI 2021 , 1682--1688

    2021

  26. [34]

    Jansen, T. 2013. Analyzing Evolutionary Algorithms -- The Computer Science Perspective. Springer

    2013

  27. [35]

    Jansen, T.; Jong, K. A. D.; and Wegener, I. 2005. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13: 413--440

    2005

  28. [36]

    Laumanns, M.; Thiele, L.; and Zitzler, E. 2004. Running time analysis of multiobjective evolutionary algorithms on pseudo- B oolean functions. IEEE Transactions on Evolutionary Computation, 8: 170--182

    2004

  29. [37]

    Laumanns, M.; Thiele, L.; Zitzler, E.; Welzl, E.; and Deb, K. 2002. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In Parallel Problem Solving from Nature, PPSN 2002 , 44--53. Springer

    2002

  30. [38]

    Li, Y.-L.; Zhou, Y.-R.; Zhan, Z.-H.; and Zhang, J. 2016. A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 20: 563--576

    2016

  31. [39]

    Neumann, F.; and Witt, C. 2010. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer

    2010

  32. [40]

    Q.; Sutton, A

    Nguyen, A. Q.; Sutton, A. M.; and Neumann, F. 2015. Population size matters: rigorous runtime results for maximizing the hypervolume indicator. Theoretical Computer Science, 561: 24--36

    2015

  33. [41]

    C.; Neumann, F.; and Sudholt, D

    Opris, A.; Dang, D. C.; Neumann, F.; and Sudholt, D. 2024. Runtime analyses of NSGA-III on many-objective problems. In Genetic and Evolutionary Computation Conference, GECCO 2024, 1596--1604. ACM

    2024

  34. [42]

    Ren, S.; Bian, C.; Li, M.; and Qian, C. 2024 a . A first running time analysis of the S trength P areto E volutionary A lgorithm 2 (SPEA2) . In Parallel Problem Solving from Nature, PPSN 2024, Part III , 295--312. Springer

    2024

  35. [43]

    Ren, S.; Qiu, Z.; Bian, C.; Li, M.; and Qian, C. 2024 b . Maintaining diversity provably helps in evolutionary multimodal optimization. In International Joint Conference on Artificial Intelligence, IJCAI 2024 , 7012--7020. ijcai.org

    2024

  36. [44]

    Rudolph, G. 1997. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kov a c

    1997

  37. [45]

    Thierens, D. 2003. Convergence time analysis for the multi-objective counting ones problem. In Evolutionary Multi-Criterion Optimization, EMO 2003 , 355--364. Springer

    2003

  38. [46]

    Wietheger, S.; and Doerr, B. 2023. A mathematical runtime analysis of the N on-dominated S orting G enetic A lgorithm III ( NSGA-III ). In International Joint Conference on Artificial Intelligence, IJCAI 2023 , 5657--5665. ijcai.org

    2023

  39. [47]

    Wietheger, S.; and Doerr, B. 2024. Near-tight runtime guarantees for many-objective evolutionary algorithms. In Parallel Problem Solving from Nature, PPSN 2024, Part IV , 153--168. Springer

    2024

  40. [48]

    Witt, C. 2006. Runtime analysis of the ( + 1) EA on simple pseudo- B oolean functions. Evolutionary Computation, 14: 65--86

    2006

  41. [49]

    Zheng, W.; and Doerr, B. 2023. Mathematical runtime analysis for the non-dominated sorting genetic algorithm II ( NSGA-II ). Artificial Intelligence, 325: 104016

    2023

  42. [50]

    Zheng, W.; and Doerr, B. 2024 a . Approximation guarantees for the N on- D ominated S orting G enetic A lgorithm II ( NSGA-II ). IEEE Transactions on Evolutionary Computation. In press, https://doi.org/10.1109/TEVC.2024.3402996

    2024

  43. [51]

    Zheng, W.; and Doerr, B. 2024 b . Runtime analysis for the NSGA-II : proving, quantifying, and explaining the inefficiency for many objectives. IEEE Transactions on Evolutionary Computation, 28: 1442--1454

    2024

  44. [52]

    Zheng, W.; and Doerr, B. 2024 c . Runtime analysis of the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024 , 20874--20882. AAAI Press

    2024

  45. [53]

    Zheng, W.; Liu, Y.; and Doerr, B. 2022. A first mathematical runtime analysis of the N on- D ominated S orting G enetic A lgorithm II ( NSGA-II ). In Conference on Artificial Intelligence, AAAI 2022 , 10408--10416. AAAI Press

    2022

  46. [54]

    N.; and Zhang, Q

    Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; and Zhang, Q. 2011. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 1: 32--49

    2011

  47. [55]

    Zhou, Z.-H.; Yu, Y.; and Qian, C. 2019. Evolutionary Learning: Advances in Theories and Algorithms. Springer

    2019

Pith tools

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