Pith. sign in

REVIEW 2 major objections 4 minor 60 references

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces

T0 review · 2 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 This paper proves that power-law mutation gives polynomial, parameter-free runtime bounds for multi-objective evolutionary algorithms on unbounded integer spaces.

desk verdict First sound runtime analysis of multi-objective EAs on unbounded integer spaces, with upper bounds proven for a finite-line benchmark; the broader practical recommendation to prefer power-law mutation goes beyond what the theorems or experiments support. read the letter →

arxiv 2412.11684 v2 pith:VSPOO6X5 submitted 2024-12-16 cs.NE

Benjamin Doerr , Martin S. Krejca , Günter Rudolph This is my paper · ORCID
classification cs.NE MSC 68W5090C29
keywords runtimeanalysismulti-objectiveevolutionaryalgorithmsunboundedintegersearchspacespower-lawmutationSEMOGSEMOdriftParetofront
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 opens the runtime analysis of multi-objective evolutionary algorithms on unbounded integer search spaces, a setting where almost no theory existed. On a natural bi-objective benchmark whose Pareto front is a finite line of 2a+1 points, the authors prove expected-runtime bounds for SEMO and GSEMO under three mutation strengths. The central result is that power-law mutation with constant exponent beta in (1,2) covers the full Pareto front in time polynomial in the width a and in the initial L1-distance, uniformly over all starting points. Unit-step mutation can be slow from far away, and exponential-tail mutation is only good with a carefully tuned step-size parameter. The paper recommends power-law mutation for unknown integer-space problems, backed by experiments.

What carries the argument

The analysis is driven by a potential function equal to the minimum L1-norm among all population members. Lemmas 1 through 6 show that this minimum never increases, that the population never exceeds 2a+1 individuals, and that all progress toward the zero vector is monotone in L1. The runtime proof splits into two phases: first hit the Pareto front by drifting the minimum L1-norm to zero, then cover the front by a doubling argument over intervals; drift theorems turn the per-step expected progress into hitting-time bounds, and the power-law's heavy tail supplies the uniform progress.

What would settle it

Pick beta=1.5, a large a, and a starting point with L1-norm comparable to a, run GSEMO with power-law mutation on f thousands of times, and check whether the mean runtime ever exceeds the right-hand side of Theorem 16 by a constant factor; a violation for a single parameter combination would refute the claimed uniform bound.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 16: for both SEMO and GSEMO using power-law mutation with any constant exponent $\beta$ in (1,2), the expected number of function evaluations to cover the entire Pareto front of the benchmark f is bounded by a product of (2a+1), n, and a polynomial whose leading terms are O(a^$\beta$) from covering the front and O(||x(0)||$_1^{{beta-1}}$) from the initial approach, with constants depending only on $\beta$. This holds uniformly for every initial search point x(0), with no tuning of the mutation operator.

Load-bearing premise

The proofs assume the objective has a finite line Pareto front with exactly 2a+1 points, so the uniform power-law recommendation is only directly established for problems with that structure.

Editorial extensions

If this is right

  • Unit-step mutation is at most linearly affected by initial distance but pays an extra linear factor per step, so from far starting points it is slowest.
  • Exponential-tail mutation can beat power-law in theory only when its scale q is chosen as a function of a and x(0); a wrong q can make the guarantee much worse.
  • Power-law mutation achieves a polynomial guarantee that does not depend on knowing a or x(0), making it the first parameter-free mutation operator with uniform worst-case bounds in this setting.
  • The two-phase drift framework applies to any finite-line Pareto front, so the same type of bound should transfer to problems whose Pareto set lies on a finite line of integer solutions.

Reading between the lines

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

  • The empirical observation of roughly linear runtime for power-law, far below the theorem's polynomial bound, suggests the true worst case is smaller and that the maximum-population assumption in the analysis is pessimistic.
  • If the uniform polynomial bound holds, it implies that the choice of mutation operator is more decisive than the choice between SEMO and GSEMO in unbounded integer spaces, since both receive essentially the same guarantee.
  • A natural extension would replace the finite line Pareto front by an infinite or higher-dimensional integer Pareto set; the present proof relies on |F*|=2a+1, so the recommendation to prefer power-law mutation should be re-examined there.
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

2 major / 4 minor

Summary. This paper initiates the runtime analysis of multi-objective evolutionary algorithms on unbounded integer search spaces by analyzing SEMO and GSEMO (Algorithm 1) on the bi-objective benchmark f(x) = (|x1 - a| + sum_{i>=2}|xi|, |x1 + a| + sum_{i>=2}|xi|), whose Pareto front is the finite line {(k,0,...,0) : k in [-a,a]} of size 2a+1. Three mutation strengths are compared: unit-step (plus/minus 1), a bilateral geometric law with parameter q (exponential tails), and a symmetric power-law with exponent beta in (1,2). Each runtime is split into a first phase (hitting the all-zeros vector) and a second phase (covering the front). The main results are Theorem 9 (unit-step: O(n(2a+1)(||x(0)||1 + 2a))), Theorem 12 (exponential-tail: a bound dominated by an(n/q + ||x(0)||1 q + max{ln(a+1)/(aq), aq + ln(a+1)}) with an unspecified constant), and Theorem 16 (power-law: O(n(2a+1)||x(0)||1^(beta-1) + n(2a+1)^beta + n(2a+1)ln a), uniform over a and x(0)). Experiments for n in {2,4,10}, a up to 200, and 50 runs per setting indicate that power-law mutation is empirically fastest, including against a near-optimally tuned exponential-tail operator, and the authors recommend power-law mutation for unknown unbounded-integer problems.

Significance. If the theorems are correct, this is a genuine first step into a previously unstudied area: multi-objective runtime analysis in unbounded integer spaces. I spot-checked the drift arguments, case analyses, and constants in the appendix and found them consistent; for example, the constants in Theorem 16 majorize those derived in the proofs of Lemmas 18 and 19, and the integral estimates via Theorem 17 are valid. The most valuable result is Theorem 16, giving a parameter-free mutation operator with a polynomial bound uniform in a, n, and the starting point. The paper is also honest: it states that its bounds are not tight, that no lower bounds are proven, and that the experiments contradict the asymptotic ordering suggested by the upper bounds; the code is publicly available. The main shortcomings are the gap between the benchmark-specific structural lemmas and the general operator recommendation, and an internal inconsistency in the empirical section's theoretical comparison (see major comments). Once these are fixed, this will be a solid and useful contribution to the theory of evolutionary multi-objective optimization.

major comments (2)
  1. [Abstract, Conclusion, Lemmas 1-6] The headline recommendation - to favor power-law mutation 'for unknown problems in integer spaces' (Abstract, Conclusion) - extends beyond the class of problems for which any theorem or experiment is provided. Every positive result is proven for the single benchmark f, whose Pareto front is the finite line {(k,0,...,0) | k in [-a,a]}, and every drift argument in Lemmas 10, 14, 18, and 19 uses the population bound |P(t)| <= 2a+1 (Lemma 4) and the non-increasing minimum L1 distance (Lemma 6). These are benchmark-specific: Lemma 1 and Lemma 3 rely on total comparability of solutions with equal or out-of-range first coordinate, Lemma 5 couples dominance to L1 order, and Lemma 6 follows from Lemma 5; these facts supply the 1/(2a+1) selection probability used throughout. For a problem with an unbounded Pareto front, or with two incomparable nondominated solutions sharing a first coordinate, the population bound fails and the L1 potential can increase, so none of the uniform guarantees transfers. The experiments cover only this one benchmark, starting points with a single non-zero component equal to 100a, and a up to 200. This is a scoping gap rather than an error in Theorem 16 as stated, but it is load-bearing for the concluding recommendation. The authors should either scope the title, abstract, and conclusion to the benchmark class with an explicit limitation statement, or prove that a broader class of unbounded-integer objectives satisfies analogues of Lemmas 1-6.
  2. [Empirical Analysis, 'Theoretical considerations'] The comparison of the exponential-tail operator with the paper's own Theorem 12 is misstated. The paragraph claims the runtime 'is in the order of a^2 q + a max{ ln(a+1)/(aq), aq + ln(a+1)}' and that 'choosing q = 1/a minimizes the maximum expression ... resulting in a runtime bound in the order of a ln(a)'. This omits the first-phase term (2a+1)en/K * n*pi^2/(6q) from Lemma 14, which is the Theta(an^2/q) term in Theorem 12. At q = 1/a this term equals Theta(a^2 n^2), which dominates the claimed a ln(a) for every constant n >= 2; hence the asserted optimality of q = 1/a and the 'quasi-linear' comparison with power-law mutation do not follow from the bounds actually proven. Including the omitted term shifts the predicted optimal q and weakens the abstract's statement that exponential-tail 'yields the best runtime guarantees in our results'. Please reconcile the empirical theoretical comparison with Lemma 14 and Theorem 12, or state explicitly which regime of the bound is being ignored and why.
minor comments (4)
  1. [Appendix, Proof of Theorem 9] In the first sentence, 'letting S from Lemma 11 be T2' should read 'be T1'; as written, the definition of T2 is circular.
  2. [Empirical Analysis, first paragraph] The first paragraph contains two issues: 'GESMO' should be 'GSEMO', and the claim that the GSEMO's runtime 'should be worse by a factor of at most e' is a statement about the proven upper bounds (factors 2n vs. 2en in Theorems 9, 12, and 16), not about the true runtimes; please rephrase accordingly.
  3. [Theorem 12] The bound is written as an equality, E[T | x(0)] = C(...), with C an unspecified 'sufficiently large' constant; since the proof supplies an upper bound, it would be clearer to write '<=' and to state that C depends on the constant c and on K from Lemma 13, as the current phrasing invites misreading as a two-sided estimate.
  4. [Lemma 19, last stage] The claim that each uncovered Pareto-optimal point 'has at least one neighbor in the population in distance 1' is not true for an arbitrary cover of half a path (e.g., a = 3 with covered set {0,1,-2,-3} leaves point 3 with only uncovered neighbors). The claim holds here only because the preceding doubling steps end with every interval of the fine partition (size between 1 and 2) hit; please insert that justification, since the sentence as written hides a use of that structure.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 16 and the other runtime bounds are proven upper bounds derived from the explicitly stated benchmark, self-contained structural lemmas, and external drift theorems; the self-citations to Rudolph (2023) and Doerr et al. (2017) supply the benchmark and operator definitions, not the conclusions.

full rationale

The derivation chain is self-contained. The benchmark f is defined explicitly in the paper (Section 'Benchmark Problem'), and every structural fact used by the runtime proofs — the population bound |P(t)| ≤ 2a+1 (Lemma 4), the L1-dominance alignment (Lemma 5), and the non-increasing minimum-L1 potential (Lemma 6) — is stated and fully proven in the appendix. The Pareto-front characterization X* = {(k,0,...,0) | k ∈ [-a..a]} with |F*| = 2a+1 is cited to Rudolph (2023), a co-author's prior work, but it is a parameter-free fact about the explicitly defined f that the paper's own Lemmas 1-3 independently re-derive (comparability and one-solution-per-x1-value), so the citation is corroborated rather than load-bearing. The drift tools (Theorems 7 and 8) come from external sources (Doerr et al. 2020; Kötzing and Krejca 2019). Theorems 9, 12, and 16 are proven upper bounds with no fitted parameters: the three mutation distributions (unit, bilateral geometric with parameter q, power-law with exponent β) are fixed throughout, and no quantity measured in the experiments feeds back into the proofs. The empirical section reports results that openly contradict the theoretical suggestion that tuned exponential-tail mutation should beat power-law ('While we expected the choice 1/q = a = 200 to be best, it is actually 1/q = 50'; power-law 'is better than the mean of the exponential-tail distribution for any of our choices of 1/q'), and the paper explicitly flags its bounds as not tight — evidence that the empirical conclusions are not coerced by the theory. No fitted parameter is renamed as a prediction, and no equation reduces to its own input. The only legitimate concern is a generality gap, not circularity: every theorem is proven on the single finite-line benchmark f, whose population bound (Lemma 4) and L1 potential (Lemmas 5-6) are benchmark-specific, so the final recommendation to prefer power-law 'for unknown problems in integer spaces' extrapolates beyond the class for which theorems or experiments are provided. That is a scope limitation, honestly stated, not a reduction of the results to their inputs.

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

The mathematical theorems use no fitted constants; the only hand-chosen numbers are experimental settings for algorithm parameters q and beta. The proofs rely on standard drift theory plus the special finite-line structure of Rudolph's benchmark. No new particles, forces, or other entities are postulated.

free parameters (2)
  • q (exponential-tail mutation parameter) = empirically tuned to 1/q = 50 for a = 200; scenario 2 uses 1/q = a/4
    Parameter of the exponential-tail mutation law. The proofs do not fit q, but the empirical comparison tunes it by grid search, and the theoretical bound is highly sensitive to it. This is the parameter-dependence that the power-law operator avoids.
  • beta (power-law exponent) = beta = 3/2 in all experiments
    Power-law exponent chosen by hand within (1,2), following earlier recommendations. The paper calls the operator 'essentially parameter-less' because a fixed beta is used, but beta is still a tunable constant.
assumptions (4)
  • standard math The drift theorems, Theorem 7 and Theorem 8, correctly bound expected hitting times for the potential processes.
    Used throughout Lemmas 10, 14, and 18 to convert per-iteration drift into runtime upper bounds; cited from Doerr et al. 2020 and Kotzing and Krejca 2019.
  • domain assumption The benchmark f satisfies Lemmas 1 to 6: dominance implies L1 order, at most 2a+1 incomparable individuals exist, and the minimum L1-norm never increases.
    These structural facts, proved in 'Useful Properties of the Benchmark Problem', justify the 1/(2a+1) parent-selection factor and the two-phase decomposition used in every theorem.
  • standard math The power-law distribution normalizes via the Riemann zeta function for beta in (1,2), and the integral estimate in Theorem 17 applies.
    Used in Lemmas 18 and 19 to bound expected improvements and to turn power-law sums into integrals.
  • ad hoc to paper The experimental settings, n up to 10, a up to 200, x(0) with one component equal to 100a, and beta = 3/2, are representative enough to support a general recommendation for power-law mutation.
    This is the premise behind the conclusion's recommendation. The paper presents it as a suggestion rather than a theorem, and it is the weakest link for the broad claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces." pith.science (2026). https://pith.science/paper/VSPOO6X5

@misc{pith2026241211684,
  author       = {Pith},
  title        = {Pith review of: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VSPOO6X5}},
  note         = {Machine review of arXiv:2412.11684}
}
read the original abstract

Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.

Figures

Figures reproduced from arXiv: 2412.11684 by the authors.

Figure 1
Figure 1. The results of scenario 2. Average evaluations of f for varying a for the GSEMO optimizing f with the muta￾tion operators: unit-step (diamonds), exponential-tail (cross diamonds) with 1 q = a 4 , and power-law (triangles) with β = 3 2 . Each point is based on 50 independent runs, with x (0) = (0, 100a). The dotted lines depict the std. deviations. periments, due to the search space being unbounded in any case. Then … view at source ↗
Figure 2
Figure 2. The results from scenario 2 for n = 4 (left) and n = 10 (right). Average function evaluations for varying a for the GSEMO optimizing f with three different mutation operators: unit-step (brown diamonds), exponential-tail (blue diamonds) with 1 q = a 4 , and power-law (red triangles) with β = 3 2 . For each point, 50 independent runs were conducted, choosing x (0) 2 = 100a and all other components of x (0) as 0. The … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 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]

    Adak, S.; and Witt, C. 2024. Runtime analysis of a multi-valued compact genetic algorithm on generalized OneMax . In Parallel Problem Solving from Nature, PPSN 2024, Proceedings, Part III , 53--69

    work page 2024

  4. [4]

    Antipov, D.; Buzdalov, M.; and Doerr, B. 2022. Fast mutation in crossover-based algorithms. Algorithmica, 84: 1724--1761

    work page 2022

  5. [5]

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

    2011

  6. [6]

    P.; and Neumann, F

    Baswana, S.; Biswas, S.; Doerr, B.; Friedrich, T.; Kurur, P. P.; and Neumann, F. 2009. Computing single source shortest paths using single-objective fitness. In Foundations of Genetic Algorithms, FOGA 2009, 59--66. ACM

    work page 2009

  7. [7]

    Ben Jedidia , F.; Doerr, B.; and Krejca, M. S. 2024. Estimation-of-distribution algorithms for multi-valued decision variables. Theoretical Computer Science, 1003: 114622

    work page 2024

  8. [8]

    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

Show all 60 references
  1. [9]

    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

    2018

  2. [10]

    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

  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]

    H.; Leiserson, C

    Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; and Stein, C. 2001. Introduction to Algorithms. The MIT Press, 2 edition

    2001

  5. [13]

    S.; and Yazdani, D

    Corus, D.; Oliveto, P. S.; and Yazdani, D. 2021. Fast immune system-inspired hypermutation operators for combinatorial optimization. IEEE Transactions on Evolutionary Computation, 25: 956--970

    2021

  6. [14]

    V.; Lehre, P

    Dang, D.; Eremeev, A. V.; Lehre, P. K.; and Qin, X. 2022. Fast non-elitist evolutionary algorithms with power-law ranking selection. In Genetic and Evolutionary Computation Conference, GECCO 2022, 1372--1380. ACM

    2022

  7. [15]

    Dang, D.-C.; Opris, A.; Salehi, B.; and Sudholt, D. 2023. 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]

    Dinot, M.; Doerr, B.; Hennebelle, U.; and Will, S. 2023. Runtime analyses of multi-objective evolutionary algorithms in the presence of noise. In International Joint Conference on Artificial Intelligence, IJCAI 2023 , 5549--5557. ijcai.org

    2023

  11. [19]

    V.; Neumann, A.; Neumann, F.; and Sutton, A

    Do, A. V.; Neumann, A.; Neumann, F.; and Sutton, A. M. 2023. Rigorous runtime analysis of MOEA/D for solving multi-objective minimum weight base problems. In Advances in Neural Information Processing Systems, NeurIPS 2023

    2023

  12. [20]

    Doerr, B. 2019. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science, 773: 115--137

    2019

  13. [21]

    Doerr, B. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Doerr, B.; and Neumann, F., eds., Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, 1--87. Springer. Also available at https://arxiv.org/abs/1801.06733

    2020 arXiv

  14. [22]

    Doerr, B.; and Doerr, C. 2018. Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm. Algorithmica, 80: 1658--1709

    2018

  15. [23]

    Doerr, B.; Doerr, C.; and K \" o tzing, T. 2018. Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica, 80: 1732--1768

    2018

  16. [24]

    Doerr, B.; Doerr, C.; and K \" o tzing, T. 2019. Solving problems with unknown solution length at almost no extra cost. Algorithmica, 81: 703--748

    2019

  17. [25]

    Doerr, B.; Doerr, C.; and Yang, J. 2020. Optimal parameter choices via precise black-box analysis. Theoretical Computer Science, 801: 1--34

    2020

  18. [26]

    Doerr, B.; Happ, E.; and Klein, C. 2012. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science, 425: 17--33

    2012

  19. [27]

    Doerr, B.; Johannsen, D.; and Schmidt, M. 2011. Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets. In Foundations of Genetic Algorithms, FOGA 2011, 119--126. ACM

    2011

  20. [28]

    S.; and Rudolph, G

    Doerr, B.; Krejca, M. S.; and Rudolph, G. 2024. Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (Code). Zenodo. https://zenodo.org/records/14506854

    2024

  21. [29]

    S.; and Vu, N

    Doerr, B.; Krejca, M. S.; and Vu, N. 2024. Superior genetic algorithms for the target set selection problem based on power-law parameter choices and simple greedy heuristics. In Genetic and Evolutionary Computation Conference, GECCO 2024. ACM

    2024

  22. [30]

    P.; Makhmara, R.; and Nguyen, T

    Doerr, B.; Le, H. P.; Makhmara, R.; and Nguyen, T. D. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017, 777--784. ACM

    2017

  23. [31]

    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

  24. [32]

    Doerr, B.; and Pohl, S. 2012. Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet. In Genetic and Evolutionary Computation Conference, GECCO 2012, 1317--1324. ACM

    2012

  25. [33]

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

    2023

  26. [34]

    Doerr, B.; and Rajabi, A. 2023. Stagnation detection meets fast mutation. Theoretical Computer Science, 946: 113670

    2023

  27. [35]

    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

  28. [36]

    Friedrich, T.; Quinzan, F.; and Wagner, M. 2018. Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In Genetic and Evolutionary Computation Conference, GECCO 2018 , 293--300. ACM

    2018

  29. [37]

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

    2003

  30. [38]

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

    2010

  31. [39]

    G.; K \" o tzing, T.; Li, X.; Radhakrishnan, A.; and Ruff, J

    Harder, J. G.; K \" o tzing, T.; Li, X.; Radhakrishnan, A.; and Ruff, J. 2024. Run Time Bounds for Integer-Valued OneMax Functions. In Genetic and Evolutionary Computation Conference, GECCO 2024, 1569--1577. ACM

    2024

  32. [40]

    He, J.; and Yao, X. 2004. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3: 21--35

    2004

  33. [41]

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

    2013

  34. [42]

    Johannsen, D. 2010. Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. thesis, Universit\"at des Saarlandes

    2010

  35. [43]

    K \" o tzing, T.; and Krejca, M. S. 2019. First-hitting times under drift. Theoretical Computer Science, 796: 51--69

    2019

  36. [44]

    K \" o tzing, T.; Lissovoi, A.; and Witt, C. 2015. (1+1) EA on Generalized Dynamic OneMax . In Foundations of Genetic Algorithms, FOGA 2015, 40--51. ACM

    2015

  37. [45]

    S.; and Witt, C

    Krejca, M. S.; and Witt, C. 2024. A flexible evolutionary algorithm with dynamic mutation rate archive. In Genetic and Evolutionary Computation Conference, GECCO 2024, 1578--1586. ACM

    2024

  38. [46]

    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

  39. [47]

    E.; and Cannings, C

    Mitavskiy, B.; Rowe, J. E.; and Cannings, C. 2009. Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. International Journal on Intelligent Computing and Cybernetics, 2: 243--284

    2009

  40. [48]

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

    2010

  41. [49]

    Qian, C.; Shi, J.; Tang, K.; and Zhou, Z. 2018 a . Constrained monotone k -submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Transactions on Evolutionary Computation , 22: 595--608

    2018

  42. [50]

    Qian, C.; Zhang, Y.; Tang, K.; and Yao, X. 2018 b . On multiset selection with size constraints. In Conference on Artificial Intelligence, AAAI 2018 , 1395--1402. AAAI Press

    2018

  43. [51]

    Ren, S.; Bian, C.; Li, M.; and Qian, C. 2024. 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

  44. [52]

    Rudolph, G. 1994. An evolutionary algorithm for integer programming. In Parallel Problem Solving from Nature, PPSN 1994 , 139--148

    1994

  45. [53]

    Rudolph, G. 2023. Runtime analysis of (1+1)-EA on a biobjective test function in unbounded integer search space. In IEEE Symposium Series on Computational Intelligence, SSCI 2023 , 1380--1385. IEEE

    2023

  46. [54]

    Scharnow, J.; Tinnefeld, K.; and Wegener, I. 2004. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3: 349--366

    2004

  47. [55]

    Sudholt, D.; and Thyssen, C. 2012. A simple ant colony optimizer for stochastic shortest path problems. Algorithmica, 64: 643--672

    2012

  48. [56]

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

    2024

  49. [57]

    Zheng, W.; Li, M.; Deng, R.; and Doerr, B. 2024. How to use the M etropolis algorithm for multi-objective optimization? In Conference on Artificial Intelligence, AAAI 2024 , 20883--20891. AAAI Press

    2024

  50. [58]

    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

  51. [59]

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

    2019

  52. [60]

    Zitzler, E.; Laumanns, M.; and Thiele, L. 2001. SPEA2 : Improving the strength P areto evolutionary algorithm. TIK report, 103

    2001

Pith tools

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