Pith. sign in

REVIEW 1 minor 45 references

SEMO covers the Pareto front of the r-valued OneMinMax in expected O(n² r (r + log n)) evaluations.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-30 19:54 UTC pith:2BTAIRWY

load-bearing objection First runtime bounds for MOEAs on r-valued variables, nearly tight on one benchmark via standard methods.

arxiv 2605.14836 v1 pith:2BTAIRWY submitted 2026-05-14 cs.NE

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

Mingfeng Li , Zheng Cheng , Weijie Zheng , Benjamin Doerr This is my paper
classification cs.NE
keywords multi-objective evolutionary algorithmsruntime analysismulti-valued decision variablesOneMinMaxSEMOPareto frontevolutionary computation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper gives the first mathematical runtime analysis of any multi-objective evolutionary algorithm on decision variables taking more than two values. It examines the classic SEMO algorithm with unit-strength local mutation on an r-valued version of the OneMinMax benchmark. The authors establish an upper bound of O(n² r² log n) and a near-matching lower bound of Ω(n² r (r + log n)) on the expected evaluations needed to cover the Pareto front. Restricting acceptance to strictly improving solutions closes the gap, yielding matching Θ(n² r (r + log n)) bounds. The results indicate that moving from binary to multi-valued variables adds only polynomial factors in r rather than fundamentally harder behavior.

Core claim

For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of O(n² r² log n) and a near-tight lower bound of Ω(n² r (r + log n)). We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of O(n² r (r + log n)), matching our lower bound.

What carries the argument

The SEMO algorithm with unit-strength local mutation on the r-valued OneMinMax benchmark.

Load-bearing premise

The bounds are derived specifically for the r-valued OneMinMax problem under unit-strength local mutation inside SEMO.

What would settle it

Running the algorithm on the r-valued OneMinMax problem and measuring an expected runtime that grows asymptotically faster or slower than these bounds would falsify the claims.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 1 minor

Summary. The paper claims to deliver the first runtime analysis for MOEAs on multi-valued decision variables by studying the SEMO algorithm with unit-strength local mutation on the r-valued OneMinMax benchmark. It establishes an upper bound of O(n² r² log n) and a lower bound of Ω(n² r (r + log n)) for the expected number of function evaluations until the Pareto front is covered by the population, and shows that a variant accepting only strictly better solutions achieves a matching upper bound of O(n² r (r + log n)).

Significance. If the results hold, this work is significant as it fills a clear gap in the theory of MOEAs for the prevalent case of multi-valued decision variables. The explicit upper and lower bounds obtained via direct probabilistic analysis, together with the gap-closing variant, provide a solid and falsifiable contribution. The transparency that the results apply specifically to this benchmark and mutation operator is a strength.

minor comments (1)
  1. [Abstract] Abstract: the phrase 'a variant of the algorithm that accepts only strictly better solutions' appears without prior definition; a one-sentence clarification of how this differs from standard SEMO would improve readability for readers unfamiliar with the base algorithm.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript and the recommendation to accept. We are pleased that the contribution is viewed as filling an important gap in the theory of MOEAs for multi-valued decision variables.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives asymptotic runtime bounds for SEMO on the r-valued OneMinMax benchmark via direct probabilistic arguments (drift analysis, coupon-collector phases, and population coverage arguments) that start from the algorithm definition and the objective function and do not reduce to fitted parameters, self-referential equations, or load-bearing self-citations. The upper and lower bounds are obtained independently and then tightened by considering a strict-acceptance variant; no step equates a claimed prediction to its own input by construction. Standard citations to prior MOEA runtime work are present but not used to import uniqueness theorems or ansatzes that would close the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard probabilistic expected-runtime analysis applied to a specific benchmark; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • standard math Standard techniques of expected runtime analysis for randomized search heuristics apply directly to the described algorithm and benchmark.
    The bounds are stated as proven results using classic methods from the field.

pith-pipeline@v0.9.1-grok · 5783 in / 1294 out tokens · 30271 ms · 2026-06-30T19:54:18.091653+00:00 · methodology

0 comments
read the original abstract

Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number $r > 2$ of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an $r$-valued counterpart of the classic \oneminmax benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of $O(n^2 r^2 \log n)$ and a near-tight lower bound of $\Omega(n^2 r (r + \log n))$. We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of $O(n^2 r (r + \log n))$, matching our lower bound (which also holds for this variant). Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.

Figures

Figures reproduced from arXiv: 2605.14836 by Benjamin Doerr, Mingfeng Li, Weijie Zheng, Zheng Cheng.

Figure 4
Figure 4. Figure 4: The mean (with standard deviations) number of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 2
Figure 2. Figure 2: The mean (with standard deviations) number of [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The mean (with standard deviations) number of [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references

  1. [1]

    Adak and C

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

    2024

  2. [2]

    , 2025 ] Y

    [Alghouass et al. , 2025 ] Y. Alghouass, B. Doerr, M. S. Krejca, and M. Lagmah. Proven approximation guar- antees in multi-objective optimization: SPEA2 beats NSGA-II. In International Joint Conference on Ar- tificial Intelligence, IJCAI 2025 , pages 8833–8841. ijcai.org,

    2025

  3. [3]

    [B¨ ack, 1993] T. B¨ ack. Optimal mutation rates in genetic search. In International Conference on Genetic Algo- rithms, ICGA 1993 , pages 2–8. Morgan Kaufmann,

    1993

  4. [4]

    , 2024 ] F

    [Ben Jedidia et al. , 2024 ] F. Ben Jedidia, B. Doerr, and M. S. Krejca. Estimation-of-distribution algorithms for multi-valued decision variables. Theoretical Com- puter Science, 1003:114622,

    2024

  5. [5]

    , 2025 ] A

    [Bendahi et al. , 2025 ] A. Bendahi, B. Doerr, A. Fradin, and J. F. Lutzeyer. Speeding up hyper-heuristics with Markov-chain operator selection and the only- worsening acceptance operator. In International Joint Conference on Artificial Intelligence, IJCAI 2025 , pages 8850–8857. ijcai.org,

    2025

  6. [6]

    , 2024 ] C

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

    2024

  7. [7]

    , 2025 ] C

    [Bian et al. , 2025 ] C. Bian, Y. Zhou, M. Li, and C. Qian. Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. Artificial Intelligence, 341:104308,

    2025

  8. [8]

    Bossek and D

    [Bossek and Sudholt, 2024 ] J. Bossek and D. Sudholt. Runtime analysis of quality diversity algorithms. Al- gorithmica, 86:3252–3283,

    2024

  9. [9]

    [Chernoff, 1952 ] H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics , 23:493–507,

    1952

  10. [10]

    , 2020 ] E

    [Covantes Osuna et al. , 2020 ] E. Covantes Osuna, W. Gao, F. Neumann, and D. Sudholt. Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimi- sation. Theoretical Computer Science , 832:123–142,

    2020

  11. [11]

    , 2024 ] D

    [Dang et al. , 2024 ] D. Dang, A. Opris, and D. Sudholt. Crossover can guarantee exponential speed-ups in evo- lutionary multi-objective optimisation. Artificial In- telligence, 330:104098,

    2024

  12. [12]

    , 2025 ] R

    [Deng et al. , 2025 ] R. Deng, W. Zheng, and B. Doerr. The first theoretical approximation guarantees for the non-dominated sorting genetic algorithm III (NSGA- III). In International Joint Conference on Artificial Intelligence, IJCAI 2025 , pages 8867–8875. ijcai.org,

    2025

  13. [13]

    Doerr and F

    [Doerr and Neumann, 2020 ] B. Doerr and F. Neumann, editors. Theory of Evolutionary Computation—Recent Developments in Discrete Optimization . Springer,

    2020

  14. [14]

    Doerr and S

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

    2012

  15. [15]

    Doerr and Z

    [Doerr and Qu, 2023a ] B. Doerr and Z. Qu. From un- derstanding the population dynamics of the NSGA-II to the first proven lower bounds. In Conference on Ar- tificial Intelligence, AAAI 2023 , pages 12408–12416. AAAI Press,

    2023

  16. [16]

    Doerr and Z

    [Doerr and Qu, 2023b ] B. Doerr and Z. 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

  17. [17]

    Doerr and W

    [Doerr and Zheng, 2021 ] B. Doerr and W. Zheng. The- oretical analyses of multi-objective evolutionary al- gorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021 , pages 12293– 12301. AAAI Press,

    2021

  18. [18]

    , 2011 ] B

    [Doerr et al. , 2011 ] B. Doerr, D. Johannsen, and M. Schmidt. Runtime analysis of the (1+1) evolu- tionary algorithm on strings over finite alphabets. In Foundations of Genetic Algorithms, FOGA 2011 , pages 119–126. ACM,

    2011

  19. [19]

    , 2012 ] B

    [Doerr et al. , 2012 ] B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorith- mica, 64:673–697,

    2012

  20. [20]

    , 2018 ] B

    [Doerr et al. , 2018 ] B. Doerr, C. Doerr, and T. K¨ otzing. Static and self-adjusting mutation strengths for multi- valued decision variables. Algorithmica, 80:1732–1768,

    2018

  21. [21]

    , 2025a ] B

    [Doerr et al. , 2025a ] B. Doerr, M. S. Krejca, and A. Opris. Tight runtime guarantees from understand- ing the population dynamics of the GSEMO multi- objective evolutionary algorithm. In International Joint Conference on Artificial Intelligence, IJCAI 2025, pages 8876–8884. ijcai.org,

    2025

  22. [22]

    , 2025b ] B

    [Doerr et al. , 2025b ] B. Doerr, M. S. Krejca, and G. Rudolph. Runtime analysis for multi-objective evolutionary algorithms in unbounded integer spaces. In Conference on Artificial Intelligence, AAAI 2025 , pages 26955–26963. AAAI Press,

    2025

  23. [23]

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

    2003

  24. [24]

    , 2024 ] J

    [Harder et al. , 2024 ] J. G. Harder, T. K¨ otzing, X. Li, A. Radhakrishnan, and J. Ruff. Run time bounds for integer-valued OneMax functions. In Genetic and Evolutionary Computation Conference, GECCO 2024, pages 1569–1577. ACM,

    2024

  25. [25]

    He and X

    [He and Yao, 2001 ] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence , 127:51–81,

    2001

  26. [26]

    Horoba and F

    [Horoba and Neumann, 2008 ] C. Horoba and F. Neu- mann. Benefits and drawbacks for the use of epsilon- dominance in evolutionary multi-objective optimiza- tion. In Genetic and Evolutionary Computation Con- ference, GECCO 2008 , pages 641–648. ACM,

    2008

  27. [27]

    , 2015 ] T

    [K¨ otzinget al. , 2015 ] T. K¨ otzing, A. Lissovoi, and C. Witt. (1+1) EA on generalized dynamic OneMax. In Foundations of Genetic Algorithms, FOGA 2015 , pages 40–51. ACM,

    2015

  28. [28]

    , 2002 ] M

    [Laumanns et al. , 2002 ] M. Laumanns, L. Thiele, E. Zit- zler, E. Welzl, and K. Deb. Running time analysis of multi-objective evolutionary algorithms on a sim- ple discrete optimization problem. In Parallel Prob- lem Solving from Nature, PPSN 2002 , pages 44–53. Springer,

    2002

  29. [29]

    , 2016 ] Y.-L

    [Li et al. , 2016 ] Y.-L. Li, Y.-R. Zhou, Z.-H. Zhan, and J. Zhang. A primary theoretical study on decomposition-based multiobjective evolutionary al- gorithms. IEEE Transactions on Evolutionary Com- putation, 20:563–576,

    2016

  30. [30]

    , 2025a ] M

    [Li et al. , 2025a ] M. Li, Q. Zhang, W. Zheng, and B. Doerr. Why popular MOEAs are popular: Proven advantages in approximating the Pareto front. In Advances in Neural Information Processing Systems, NeurIPS 2025 ,

    2025

  31. [31]

    [Li et al

    To appear. [Li et al. , 2025b ] M. Li, W. Zheng, and B. Doerr. Scal- able speed-ups for the SMS-EMOA from a simple ag- ing strategy. In International Joint Conference on Artificial Intelligence, IJCAI 2025 , pages 8885–8893. ijcai.org,

    2025

  32. [32]

    M¨ uhlenbein

    [M¨ uhlenbein, 1992] H. M¨ uhlenbein. How genetic algo- rithms really work: mutation and hillclimbing. In Par- allel Problem Solving from Nature, PPSN 1992 , pages 15–26. Elsevier,

    1992

  33. [33]

    [Opris, 2026b ] A. Opris. Towards a rigorous understand- ing of the population dynamics of the NSGA-III: Tight runtime bounds. In Conference on Artificial Intelli- gence, AAAI 2026 , pages 37125–37133. AAAI Press,

    2026

  34. [34]

    , 2018b ] C

    [Qian et al. , 2018b ] C. Qian, Y. Zhang, K. Tang, and X. Yao. On multiset selection with size constraints. In Conference on Artificial Intelligence, AAAI 2018 , pages 1395–1402. AAAI Press,

    2018

  35. [35]

    , 2024 ] S

    [Ren et al. , 2024 ] S. Ren, C. Bian, M. Li, and C. Qian. A first running time analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2). In Parallel Prob- lem Solving from Nature, PPSN 2024, Part III , pages 295–312. Springer,

    2024

  36. [36]

    , 2025 ] S

    [Ren et al. , 2025 ] S. Ren, Z. Liang, M. Li, and C. Qian. Stochastic population update provably needs an archive in evolutionary multi-objective optimization. In International Joint Conference on Artificial Intel- ligence, IJCAI 2025 , pages 8921–8929. ijcai.org,

    2025

  37. [37]

    [Rudolph, 2023 ] G. Rudolph. 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 , pages 1380–

    2023

  38. [38]

    Wietheger and B

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

    2023

  39. [39]

    [Witt, 2014 ] C. Witt. Fitness levels with tail bounds for the analysis of randomized search heuristics. Informa- tion Processing Letters , 114:38–41,

    2014

  40. [40]

    Zheng and B

    [Zheng and Doerr, 2023 ] W. Zheng and B. Doerr. Math- ematical runtime analysis for the non-dominated sort- ing genetic algorithm II (NSGA-II). Artificial Intelli- gence, 325:104016,

    2023

  41. [41]

    Zheng and B

    [Zheng and Doerr, 2024 ] W. Zheng and B. Doerr. Run- time analysis of the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024 , pages 20874–20882. AAAI Press,

    2024

  42. [42]

    Zheng and B

    [Zheng and Doerr, 2025 ] W. Zheng and B. Doerr. Ap- proximation guarantees for the non-dominated sorting genetic algorithm II (NSGA-II). IEEE Transactions on Evolutionary Computation , 29:891–905,

    2025

  43. [43]

    , 2024 ] W

    [Zheng et al. , 2024 ] W. Zheng, M. Li, R. Deng, and B. Doerr. How to use the Metropolis algorithm for multi-objective optimization? In Conference on Ar- tificial Intelligence, AAAI 2024 , pages 20883–20891. AAAI Press,

    2024

  44. [44]

    , 2019 ] Z.-H

    [Zhou et al. , 2019 ] Z.-H. Zhou, Y. Yu, and C. Qian. Evo- lutionary Learning: Advances in Theories and Algo- rithms. Springer,

    2019

  45. [45]

    For the unit-strength local mu tation, the maximum value of f1 in the population (and analogously of f2) can increase by at most one per iteration

    We first prove the upper bound. For the unit-strength local mu tation, the maximum value of f1 in the population (and analogously of f2) can increase by at most one per iteration. Since already rea ched Pareto front points will be maintained in all future generations, w e know that the maximum f1-value and the maximum f2-value reached by Pt will not decrea...

    2018