Pith. sign in

REVIEW 4 major objections 5 minor 61 references

Running-time Analysis of ($\mu+\lambda$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read One drift bound tames (µ+λ) EA on knapsack, SAT, TSP

desk verdict A well-structured but ultimately under-supported paper: the multiple-gain model is drift analysis in disguise, and the central knapsack bound (Theorem 3) rests on an invalid drift inequality that the stress-test counterexample correctly exposes. read the letter →

arxiv 2507.02381 v1 pith:SGSHJ5SI submitted 2025-07-03 cs.NE

Min Huang , Pengxiang Chen , Han Huang , Tongli He , Yushan Zhang , Zhifeng Hao This is my paper · ORCID
classification cs.NE MSC 68Q2568W2090C27
keywords (µ+λ)evolutionaryalgorithmmultiple-gainmodelexpectedfirsthittingtimerunning-timeanalysisknapsackproblemk-MAX-SATtravelingsalespersonaveragegaindrift
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 sets out to extend running-time analysis from simple (1+1) heuristics to population-based $(\mu+\lambda)$ evolutionary algorithms on combinatorial optimization problems. It replaces the single-generation average gain with an expected multiple-gain $G(t,k)$, the expected fitness drop of the best individual over $k$ generations, and proves two drift theorems that turn a lower bound on that gain into an upper bound on the expected first hitting time. The theorems are applied to three problems: knapsack with favorably correlated weights, general $k$-MAX-SAT, and the traveling salesperson problem on points in convex position. The paper claims average-case and worst-case upper bounds for all three, including a closed-form $k$-MAX-SAT expression and improvements over previously known knapsack and TSP bounds. A sympathetic reader would care because population-based EAs are widely used but have far fewer provable time bounds than the $(1+1)$ EA.

What carries the argument

The load-bearing object is the expected multiple-gain $G(t,k)$, a fitness-difference drift measured over $k$ generations instead of one; the average gain is the special case $k=1$. Theorems 1 and 2 are the levers: they construct a potential $g(f(x_t))=\sum_{i=1}^{p}(r_i-r_{i-1})/h(r_i)$ whose expected decrease is at least one per $k$-step block, and then use the supermartingale optional-stopping lemma to convert that into a bound on $T_0=\min\{t:Y_t=0\}$. The worst-case version also introduces $k_{\mathrm{low}}$, the smallest $k$ for which the $k$-step gain covers the adjacent fitness gap, and the paper estimates it both from the drift formulas and, experimentally, as the average longest zero-gain stretch over repeated runs.

What would settle it

Enumerate every feasible solution of a small knapsack instance with favorably correlated weights, compute the exact transition probabilities of Algorithm 1 from each state, and verify whether $G(t,1)\ge(1-e^{-\lambda(p_1+n(1-p_1))/(\mu n^2 e)})(p_1d_{\min}+p_2v_{\min})$ holds for every state with $Y_t>0$; a single state that violates it, with $p_1,p_2$ computed as in Theorem 3, refutes the claimed bound. For a concrete test, take $n$ small (say 5), choose values so that $d_{\min}>v_{\min}$ (e.g., values $50,30,1,1,1$), and check the states whose last $n-q$ bits are all zero, where Case 2 dominates.

Watch

Extended reading notes

Core claim

The central claim is that the expected multiple-gain $G(t,k)=E(f(x_t)-f(x_{t+k})\mid H_t)$ is sufficient to control the whole run. Theorem 2 shows that if $G(t,k)\ge h(f(x_t))$ for a monotonically nondecreasing $h$, then the average-case expected first hitting time satisfies $E(T_0\mid f(x_0)=r_L)\le k\sum_{i=1}^{L}(r_i-r_{i-1})/h(r_i)$; Theorem 1 and Corollary 1 give the worst-case form $E(T_0\mid f(x_0))\le k_{\mathrm{low}}f(x_0)/\alpha$ when the gain over $k$ generations covers the smallest adjacent fitness gap $\alpha$. Using $k=1$ for simplicity, the paper derives the knapsack bound $E(T_0\mid Y_0)\le (Y_0-r_0)/((1-e^{-\lambda(p_1+n(1-p_1))/(\mu n^2 e)})(p_1d_{\min}+p_2v_{\min}))$, the $k$-MAX-SAT bound $E(T_0\mid Y_0)\le (\sum_{x=1}^{s}1/x)/(1-e^{-\lambda N_{\mathrm{opt}}/2^n})$, and the convex-TSP bound $E(T_0\mid f(x_0)=L)\le \frac{2}{1+g}(L+\mu e^{\lambda_p}C_n^2/(\lambda\lambda_p)\sum_{x=1}^{L}1/x)$, which is $O((\mu/\lambda)n^2\ln n+n)$. It further claims these improve the existing knapsack and TSP upper bounds in the stated parameter regimes.

Load-bearing premise

The knapsack bound rests on treating $p_1$ and $p_2$ as fixed combinatorial fractions of all feasible solutions and on the unproven inequality $G(t,1)\ge(1-e^{-\lambda(p_1+n(1-p_1))/(\mu n^2 e)})(p_1d_{\min}+p_2v_{\min})$ holding for every population state; if that state-independent mixture is not a valid lower bound on the conditional drift, Theorem 3 collapses.

Editorial extensions

If this is right

  • For the knapsack instance, Corollary 2 gives $O(\mu n^2(r_L-r_0)/(\lambda d_{\min}))$ when $p_1=1$ and $O(\mu n(r_L-r_0)/(\lambda v_{\min}))$ when $p_1=0$; at $\mu=\lambda=1$ these improve the earlier $O(n^2(\ln n+p_{\max}))$ bound by factors of $\ln n$ and $n\ln n$.
  • For every $k$-MAX-SAT instance, Corollary 3 gives $O(2^n(\ln s+1)/(\lambda N_{\mathrm{opt}}))$, where $N_{\mathrm{opt}}$ is the number of global optima, extending results that previously covered only specific random or small-$k$ instances.
  • For convex-position TSP, Corollary 4 gives $O((\mu/\lambda)n^2\ln n+n)$, improving the earlier $O(n\max\{(\mu/\lambda)n^2,1\})$ bound by $n/\ln n$ when $(\mu/\lambda)n^2>1$.
  • The worst-case counterparts (Theorems 4, 6, 8) use the same drift machinery with $k_{\mathrm{low}}$; the paper estimates $k_{\mathrm{low}}$ from runs and reports correlation coefficients above 0.99 between the theoretical bounds and observed first hitting times on the three test instances.
  • The knapsack theorem contains the earlier $(1+1)$ EA bound as the special case $\mu=1,\lambda=1$, so the population-level result is a strict generalization rather than a separate analysis.

Reading between the lines

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

  • Because the knapsack proof uses $p_1$ and $p_2$ as fixed fractions of the feasible-solution set and multiplies them directly by $d_{\min}$ and $v_{\min}$, the bound's validity depends on whether that state-independent mixture is truly a lower bound on $G(t,1)$ for every population state; a natural check is to enumerate all states for small $n$ and compare the exact conditional drift with the formu
  • A corrected version of the knapsack argument would likely condition on the actual improvement probabilities, which weight Case 2 improvements by roughly $n$ relative to Case 1; that would change the claimed rate in regimes where $d_{\min}$ and $v_{\min}$ differ substantially.
  • The same $G(t,k)$ machinery should transfer to other population EAs and other combinatorial objectives whenever the best individual's fitness admits a per-generation expected-improvement lower bound, suggesting that the three case studies are templates rather than isolated results.
  • A fully theoretical worst-case analysis would replace the experimentally estimated $k_{\mathrm{low}}$ with a rigorous upper bound on the longest zero-gain stretch; doing so would make the worst-case theorems independent of measurement.
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

4 major / 5 minor

Summary. The paper proposes a 'multiple-gain' model, a k-step generalization of the average-gain drift technique, and uses it to derive upper bounds on the expected first hitting time of (μ+λ) EAs for the knapsack problem with favorably correlated weights, general k-MAX-SAT, and the TSP on point sets in convex position. It also reports experiments with 1000 runs per instance and correlation coefficients between the derived bounds and empirical hitting times. The paper claims improvements over the known knapsack bound of Neumann and Sutton and the TSP bound of Sutton et al.

Significance. The paper addresses a real gap in the runtime analysis of population-based EAs on combinatorial problems, and the multi-step gain framework is a reasonable idea that could be useful if made rigorous. Theorem 5 is a valid, though weak, closed-form bound: it relies on mutation probability 1/2 and gives O(2^n ln s/(λ Nopt)). The main claimed contributions for knapsack and TSP, however, are not established because the drift lower bound in Theorem 3 is false for a concrete state and the probability computation in Theorem 7 uses the wrong distribution for the number of 2-opt inversions. The experimental work is transparent about its protocol, but the worst-case validation is circular because klow is estimated from the same runs used to evaluate the bound. Overall the central claims are not yet reliable.

major comments (4)
  1. [IV-B, Theorem 3, Eq. (7)] The drift lower bound in the proof of Theorem 3 is not valid, because p1 and p2 are global fractions of feasible solutions rather than probabilities over the current parent state, and the proof multiplies the probability of an improving offspring by the unweighted mixture p1 dmin + p2 vmin. For a fixed xt, the case is determined by whether xt has a 1-bit in positions q+1..n, so a convex combination of the Case 1 and Case 2 gains cannot be a lower bound for every state. Concretely, take n=100, q=2, μ=1, λ=10, capacity 3, values (2,2,1,...,1), weights (1,1,2,...,2), and xt=(1,0,0,1,0,...,0); here the only improving single mutation is the swap of a zero in the first two positions with the 1-bit at position 4, whose probability is at least 1/(n^2 e) per offspring, giving a true one-step drift of approximately 1-(1-1/(n^2 e))^{10} ≈ 0.00037, while the claimed bound in Eq. (7) is about 0.00073. Hence Eq. (7) can exceed the true drift on a single state, and the knapsack upper bound and its claimed improvements over [4] are not established.
  2. [III-B, Theorems 1-2, Eqs. (2) and (4)] The proofs of Theorems 1 and 2 have an optional-stopping gap. Theorem 1 applies Lemma 1 to the k-skeleton process {f(x_{kt})} with the original stopping time T0, but T0 is not adapted to the skeleton filtration because the event {T0 ≤ n} depends on f(x_t) for t that are not multiples of k; the integrability and finiteness conditions of the optional stopping theorem are also not verified. Theorem 2 invokes Theorem 1 directly ('According to Theorem 1'), so the gap propagates into the average-case bounds Eqs. (4), (7), (13), and (19). The issue may be repairable with a standard drift argument on the skeleton plus an overshoot term, but the manuscript does not provide such an argument.
  3. [IV-D, Theorem 7, Eq. (19)] In the proof of Theorem 7, E1 is defined as the event that mutation performs only one random 2-opt inversion, which has probability P(s=0)=e^{-λp} under the Poisson(λp) mutation, but the proof states the probability is λp/e^{λp}, which is instead P(s=1), i.e., two inversions. This wrong factor is used in the lower bound on the success probability p and therefore in Eq. (19), so the stated TSP bound is not established for general λp (the error is masked for λp=1 because both expressions equal 1/e). The conditional probabilities 1/(n−2) and 1/(n−3) used in the computation of g are also asserted without a distributional justification, and Theorem 8 inherits these issues.
  4. [V-B, Eqs. (5), (10), (11)] The worst-case experimental validation is circular. In Section V-B the theoretical klow from Eq. (10) is replaced by the empirical average bk of the longest zero-gain intervals from 1000 runs (Eq. (5)), and this bk is then plugged into Eq. (11) to produce the 'theoretical worst-case upper bound' that is compared with Tmax from those same 1000 runs. This comparison does not test the predictive content of Theorems 4, 6, and 8; it only checks that an empirical plug-in quantity exceeds the empirical maximum. The paper's claim that the experiments verify the worst-case bounds is therefore not supported.
minor comments (5)
  1. [Global] 'attend' is used where 'attain' is meant in several places, e.g., the Abstract and Definition 3; the wording should be corrected throughout.
  2. [V-C, Table II] Table II is titled 'RESULTS OF CORRELATION COEFFICIENT OF ALGORITHM 1 FOR THE k-MAX-SAT PROBLEM', but the experiment reported there concerns Algorithm 2.
  3. [V-A] The experimental setting states that Algorithms 1 and 2 were implemented in Matlab, but Algorithm 3 (TSP) is also benchmarked; the sentence should include it.
  4. [IV-D] The proof of Theorem 7 uses S = {0,1,...,n}, whereas the text before Algorithm 3 states that f(x) ∈ {0,2,3,...,n} for n>5; these two descriptions of the fitness range should be reconciled.
  5. [IV-D, Eq. (19)] The intermediate expression for g in the proof of Theorem 7 and the closed form in Eq. (19) are not shown to be equal; adding the algebraic step would help the reader verify the calculation.

Circularity Check

1 steps flagged · score 6.0 of 10

Worst-case experimental bounds reduce by construction because klow is estimated from the same runs used for comparison; the analytical drift bounds are independent, so circularity is partial.

  1. fitted input called prediction [Section V-A/V-B, Eq. (5) and Formulas (10)-(11); repeated in V-C and V-D]
    "Let ki denote the most prolonged time interval during which the gain remains zero in the i-th run. bk = Σ_{i=1}^{1000} k_i/1000 was considered to be the estimation of klow. ... Here, we replace Formula (10) with bk = Σ_{i=1}^{1000} k_i/1000 when calculating Formula (11)."

    Formula (11) is the claimed worst-case bound E(T0|Y0) ≤ klow(Y0 - r0)/α. Instead of using the theoretical klow from Formula (10), the paper substitutes bk, the average longest zero-gain interval observed in the same 1000 runs from which Tmax is taken. The bound being verified is therefore constructed from the very data it is compared against: the empirical statement EFHTworst > Tmax is only a check that a data-fitted constant is large enough, not an independent prediction of the model. The same replacement is applied in the k-MAX-SAT and TSP experiments, so all worst-case validations share this circularity.

full rationale

The theoretical average-case bounds (Theorems 3, 5, 7) are derived by drift arguments from explicit problem parameters (p1, p2, dmin, vmin, Nopt, etc.) and are not fitted to runtime data, so the central claims retain independent content. The worst-case empirical verification is circular as described: klow is estimated from the same runs and then inserted into Formula (11) to produce the bound compared against those runs. The self-citation of Lemma 1 from the authors' previous paper [28] is load-bearing but not circular: it is an elementary supermartingale stopping-time inequality that does not assume any of the paper's target results. The reviewer-identified gap in Theorem 3's drift lower bound — the state-independent mixture p1dmin + p2vmin and the dropped 1/(n^2 e) factor — is a substantive correctness concern, but it is a mathematical-error issue rather than a circularity, so it is not scored as a circular step here. Overall, one class of reported verifications reduces by construction to its own inputs, giving partial circularity while the analytical derivation itself is not circular.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central claims rely on standard martingale tools, on instance-structure assumptions for knapsack and TSP, and on two ad hoc assumptions: state-independent case probabilities in the knapsack proof and uniform conditioning in the TSP inversion analysis. The empirical worst-case validation additionally imports a fitted parameter, klow, into a formula that is then tested on the same data.

free parameters (3)
  • k (multiple-gain horizon) = k=1 in all three case studies; klow estimated empirically in experiments
    The claimed generalization to k>1 is never used in the theoretical bounds; the new results all set k=1, reducing to the average gain model.
  • klow (empirical worst-case step) = bk = (1/1000) sum ki from 1000 runs (Eq. 5)
    Worst-case upper bounds in Section V are evaluated by substituting the empirically estimated bk for the theoretical klow, then checked against the same runs.
  • p1, p2 (knapsack case probabilities) = p2 = (sum_{i=0}^{q-1} C(q,i)) / N, p1 = 1 - p2
    Treated as constants independent of the state; in reality they depend on the current best solution, and the drift lower bound needs a uniform bound over states.
assumptions (6)
  • standard math Optional stopping theorem for supermartingales (Lemma 1 from [28])
    Invoked in the proofs of Theorems 1 and 2; requires additional integrability or boundedness conditions that are not stated.
  • standard math Law of large numbers used to estimate klow from sample means
    Used in Section V.A Eq (5) to justify replacing the theoretical klow by an empirical average.
  • domain assumption Optimum of the favorably correlated knapsack instance has prefix form xopt=(1^q,0^(n-q))
    Stated at the start of Theorem 3 without proof; follows from the dominance ordering only if ties and capacity are handled carefully.
  • ad hoc to paper p1 and p2 are state-independent constants for the knapsack drift analysis
    This is the load-bearing modeling assumption in Theorem 3; no uniform bound over population states is given.
  • ad hoc to paper TSP: one improving 2-opt inversion exists per bad point, and its expected gain is 1+g with g computed from uniform randomness
    Used in Theorem 7; the conditioning on an improving inversion changes the distribution of endpoints, so the stated probabilities require proof.
  • domain assumption Fitness process {f(xt)} is a Markov chain
    Stated in Section IV.A before the case studies; for population-based (mu+lambda) EA, the distribution of the next best fitness depends on more than the scalar f(xt).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Running-time Analysis of ($\mu+\lambda$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation." pith.science (2026). https://pith.science/paper/SGSHJ5SI

@misc{pith2026250702381,
  author       = {Pith},
  title        = {Pith review of: Running-time Analysis of ($\mu+\lambda$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SGSHJ5SI}},
  note         = {Machine review of arXiv:2507.02381}
}
abstract

The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. However, theoretical results regarding the $(\mu+\lambda)$ evolutionary algorithm (EA) for combinatorial optimization problems remain relatively scarce compared to those for simple pseudo-Boolean problems. This paper proposes a multiple-gain model to analyze the running time of EAs for combinatorial optimization problems. The proposed model is an improved version of the average gain model, which is a fitness-difference drift approach under the sigma-algebra condition to estimate the running time of evolutionary numerical optimization. The improvement yields a framework for estimating the expected first hitting time of a stochastic process in both average-case and worst-case scenarios. It also introduces novel running-time results of evolutionary combinatorial optimization, including two tighter time complexity upper bounds than the known results in the case of ($\mu+\lambda$) EA for the knapsack problem with favorably correlated weights, a closed-form expression of time complexity upper bound in the case of ($\mu+\lambda$) EA for general $k$-MAX-SAT problems and a tighter time complexity upper bounds than the known results in the case of ($\mu+\lambda$) EA for the traveling salesperson problem. Experimental results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is an effective tool for running-time analysis of ($\mu+\lambda$) EA for combinatorial optimization problems.

Figures

Figures reproduced from arXiv: 2507.02381 by the authors.

Figure 1
Figure 1. The EFHT analysis process using the multiple-gain model [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Results of Algorithm 1 for the knapsack problem with favorably correlated weights. (a) Theoretical average-case upper bounds of EFHT given by c [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Results of Algorithm 2 for the k-MAX-SAT problem. (a) Theoretical average-case upper bounds of EFHT given by Formula (13) and estimation of actual EFHT Tc0 = P1000 i=1 Ti/1000. (b) Theoretical worst-case upper bounds of EFHT given by Formula (17) and actual largest FHT Tmax = max {Ti|1 ≤ i ≤ 1000}. (c) Estimation of klow given by bk = P1000 i=1 ki/1000 and theoretical value of klow given by Formula (16). (a) (b) (c)… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Results of Algorithm 3 for the TSP problem. (a) Theoretical average-case upper bounds of EFHT given by Formula (19) and estimation of actual EFHT c [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages

  1. [4]

    Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights,

    F. Neumann and A. M. Sutton, “Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights,” in Lect. Notes Comput. Sci , 2018, pp. 141–152

    work page 2018

  2. [1]

    A survey on recent progress in the theory of evolutionary algorithms for discrete optimization,

    B. Doerr and F. Neumann, “A survey on recent progress in the theory of evolutionary algorithms for discrete optimization,” ACM Trans. Evol. Learn. Optim., vol. 1, no. 4, pp. 1–43, 2021

    work page 2021

  3. [2]

    Average drift analysis and population scalability,

    J. He and X. Yao, “Average drift analysis and population scalability,” IEEE Trans. Evol. Comput. , vol. 21, no. 3, pp. 426–439, 2016

    work page 2016

  4. [3]

    A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems,

    T. Chen, J. He, G. Sun, G. Chen, and X. Yao, “A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 39, no. 5, pp. 1092–1106, 2009

    work page 2009

  5. [5]

    Runtime analysis of the (1+ 1) evolutionary algorithm for the chance-constrained knapsack problem,

    F. Neumann and A. M. Sutton, “Runtime analysis of the (1+ 1) evolutionary algorithm for the chance-constrained knapsack problem,” in Proc. ACM/SIGEVO Conf. Found. Genet. Algorithms. (FOGA), 2019, pp. 147–153

    work page 2019

  6. [6]

    Runtime analysis of RLS and the (1+ 1) EA for the chance-constrained knapsack problem with correlated uniform weights,

    Y . Xie, A. Neumann, F. Neumann, and A. M. Sutton, “Runtime analysis of RLS and the (1+ 1) EA for the chance-constrained knapsack problem with correlated uniform weights,” in Proc. Genet. Evol. Comput. Conf. (GECCO), 2021, pp. 1187–1194

    work page 2021

  7. [7]

    Performance analysis of evolutionary algorithms for the minimum label spanning tree problem,

    X. Lai, Y . Zhou, J. He, and J. Zhang, “Performance analysis of evolutionary algorithms for the minimum label spanning tree problem,” IEEE Trans. Evol. Comput. , vol. 18, no. 6, pp. 860–872, 2013

    work page 2013

  8. [8]

    Approximation and parameterized runtime analysis of evolutionary algorithms for the maximum cut problem,

    Y . Zhou, X. Lai, and K. Li, “Approximation and parameterized runtime analysis of evolutionary algorithms for the maximum cut problem,”IEEE Trans. Cybern., vol. 45, no. 8, pp. 1491–1498, 2014

    work page 2014

Show all 61 references
  1. [9]

    Y . Zhou, J. Zhang, and Y . Wang, “Performance analysis of the (1+

  2. [10]

    evolutionary algorithm for the multiprocessor scheduling problem,” Algorithmica, vol. 73, pp. 21–41, 2015

    2015

  3. [11]

    Improved runtime bounds for the (1+ 1) EA on random 3-CNF formulas based on fitness-distance correlation,

    B. Doerr, F. Neumann, and A. M. Sutton, “Improved runtime bounds for the (1+ 1) EA on random 3-CNF formulas based on fitness-distance correlation,” in Proc. Genet. Evol. Comput. Conf. (GECCO) , 2015, pp. 1415–1422

    2015

  4. [12]

    Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem,

    F. Shi, F. Neumann, and J. Wang, “Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem,” Algorithmica, vol. 83, no. 4, pp. 906–939, 2021

    2021

  5. [13]

    A first runtime analysis of the NSGA-II on a multimodal problem,

    B. Doerr and Z. Qu, “A first runtime analysis of the NSGA-II on a multimodal problem,” IEEE Trans. Evol. Comput. , vol. 27, no. 5, pp. 1288 – 1297, 2023. 15

    2023

  6. [14]

    Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives,

    W. Zheng and B. Doerr, “Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives,” IEEE Trans. Evol. Comput. , vol. 28, no. 5, pp. 1442–1454, 2024

    2024

  7. [15]

    Towards running time analysis of interactive multi-objective evolutionary algorithms,

    T. Lu, C. Bian, and C. Qian, “Towards running time analysis of interactive multi-objective evolutionary algorithms,” inProc. AAAI Conf. Artif. Intell., vol. 38, no. 18, 2024, pp. 20 777–20 785

    2024

  8. [16]

    An archive can bring provable speed-ups in multi-objective evolutionary algorithms,

    C. Bian, S. Ren, M. Li, and C. Qian, “An archive can bring provable speed-ups in multi-objective evolutionary algorithms,” inIJCAI Int. Joint Conf. Artif. Intell. , 2024, pp. 6905–6913

    2024

  9. [17]

    Stochastic population update can provably be helpful in multi-objective evolutionary algorithms,

    C. Bian, Y . Zhou, M. Li, and C. Qian, “Stochastic population update can provably be helpful in multi-objective evolutionary algorithms,” in IJCAI Int. Joint Conf. Artif. Intell. , 2023, pp. 5513–5521

    2023

  10. [18]

    Quality-diversity algorithms can provably be helpful for optimization,

    C. Qian, K. Xue, and R.-J. Wang, “Quality-diversity algorithms can provably be helpful for optimization,” in IJCAI Int. Joint Conf. Artif. Intell., 2024, pp. 6994–7002

    2024

  11. [19]

    Analysing the robustness of NSGA-II under noise,

    D.-C. Dang, A. Opris, B. Salehi, and D. Sudholt, “Analysing the robustness of NSGA-II under noise,” in Proc. Genet. Evol. Comput. Conf. (GECCO), 2023, pp. 642–651

    2023

  12. [20]

    The first proven performance guarantees for the non-dominated sorting genetic algorithm ii (nsga-ii) on a combinatorial optimization problem,

    S. Cerf, B. Doerr, B. Hebras, Y . Kahane, and S. Wietheger, “The first proven performance guarantees for the non-dominated sorting genetic algorithm ii (nsga-ii) on a combinatorial optimization problem,” IJCAI Int. Joint Conf. Artif. Intell. , 2023

    2023

  13. [21]

    Runtime analyses of nsga-iii on many-objective problems,

    A. Opris, D.-C. Dang, F. Neumann, and D. Sudholt, “Runtime analyses of nsga-iii on many-objective problems,” in Proc. Genet. Evol. Comput. Conf. (GECCO), 2024, pp. 1596–1604

    2024

  14. [22]

    Drift analysis and average time complexity of evolutionary algorithms,

    J. He and X. Yao, “Drift analysis and average time complexity of evolutionary algorithms,” Artif. Intell., vol. 127, no. 1, pp. 57–85, 2001

    2001

  15. [23]

    Simplified drift analysis for proving lower bounds in evolutionary computation,

    P. S. Oliveto and C. Witt, “Simplified drift analysis for proving lower bounds in evolutionary computation,” Algorithmica, vol. 59, no. 3, pp. 369–386, 2011

    2011

  16. [24]

    Combining Markov-Chain analysis and drift analysis: The (1+1) evolutionary algorithm on linear functions reloaded

    J. Jägersküpper, “Combining Markov-Chain analysis and drift analysis: The (1+1) evolutionary algorithm on linear functions reloaded.” Algo- rithmica, vol. 59, no. 3, pp. 409–424, 2011

    2011

  17. [25]

    Runtime analysis of a co-evolutionary algorithm: Overcoming negative drift in maximin- optimisation,

    M. A. H. Fajardo, P. K. Lehre, and S. Lin, “Runtime analysis of a co-evolutionary algorithm: Overcoming negative drift in maximin- optimisation,” in Proc. ACM/SIGEVO Conf. Found. Genet. Algorithms. (FOGA), 2023, pp. 73–83

    2023

  18. [26]

    Switch analysis for running time anal- ysis of evolutionary algorithms,

    Y . Yu, C. Qian, and Z.-H. Zhou, “Switch analysis for running time anal- ysis of evolutionary algorithms,” IEEE Trans. Evol. Comput. , vol. 19, no. 6, pp. 777–792, 2015

    2015

  19. [27]

    Running time analysis: Convergence-based analysis reduces to switch analysis,

    Y . Yu and C. Qian, “Running time analysis: Convergence-based analysis reduces to switch analysis,” in IEEE Congr. Evol. Comput. (CEC) . IEEE, 2015, pp. 2603–2610

    2015

  20. [28]

    Runtime analysis for continuous (1+1) evolutionary algorithm based on average gain model (in Chinese),

    H. Huang, W. Xu, Y . Zhang, Z. Lin, and Z. Hao, “Runtime analysis for continuous (1+1) evolutionary algorithm based on average gain model (in Chinese),” Scientia Sinica Informationis, vol. 44, no. 6, pp. 811–824, 2014

    2014

  21. [29]

    First hitting time analysis of continuous evolutionary algorithms based on average gain,

    Y . Zhang, H. Huang, Z. Hao, and G. Hu, “First hitting time analysis of continuous evolutionary algorithms based on average gain,” Cluster Comput., vol. 19, no. 3, pp. 1323–1332, 2016

    2016

  22. [30]

    An experimental method to estimate running time of evolutionary algorithms for continuous optimization,

    H. Huang, J. Su, Y . Zhang, and Z. Hao, “An experimental method to estimate running time of evolutionary algorithms for continuous optimization,” IEEE Trans. Evol. Comput. , vol. 24, no. 2, pp. 275–289, 2020

    2020

  23. [31]

    Runtime analysis of the (1+( λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas,

    M. Buzdalov and B. Doerr, “Runtime analysis of the (1+( λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas,” in Proc. Genet. Evol. Comput. Conf. (GECCO) , 2017, pp. 1343–1350

    2017

  24. [32]

    A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT,

    A. M. Sutton, J. Day, and F. Neumann, “A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT,” inProc. Int. Conf. Genet. Evol. Comput. (GECCO) , 2012, pp. 433–440

    2012

  25. [33]

    Parameterized runtime analyses of evolutionary algorithms for the planar euclidean traveling salesperson problem,

    A. M. Sutton, F. Neumann, and S. Nallaperuma, “Parameterized runtime analyses of evolutionary algorithms for the planar euclidean traveling salesperson problem,” Evol. Comput., vol. 22, no. 4, pp. 595–628, 2014

    2014

  26. [34]

    A rigorous complexity analysis of the (1+ 1) evolutionary algorithm for separable functions with boolean inputs,

    S. Droste, T. Jansen, and I. Wegener, “A rigorous complexity analysis of the (1+ 1) evolutionary algorithm for separable functions with boolean inputs,” Evol. Comput., vol. 6, no. 2, pp. 185–196, 1998

    1998

  27. [35]

    On the analysis of the (1+ 1) evolutionary algorithm,

    S. Droste, T. Jansen, and I. Wegener, “On the analysis of the (1+ 1) evolutionary algorithm,” Theor. Comput. Sci., vol. 276, no. 1-2, pp. 51– 81, 2002

    2002

  28. [36]

    Tight bounds on the optimization time of a randomized search heuristic on linear functions,

    C. Witt, “Tight bounds on the optimization time of a randomized search heuristic on linear functions,” Combinatorics, Probability and Computing, vol. 22, no. 2, pp. 294–318, 2013

    2013

  29. [37]

    Analysis of the (1 + 1)-ea for finding approximate solutions to vertex cover problems,

    P. S. Oliveto, J. He, and X. Yao, “Analysis of the (1 + 1)-ea for finding approximate solutions to vertex cover problems,” IEEE Trans. Evol. Comput., vol. 13, no. 5, pp. 1006–1029, 2009

    2009

  30. [38]

    On the choice of the offspring population size in evolutionary algorithms,

    T. Jansen, K. A. D. Jong, and I. Wegener, “On the choice of the offspring population size in evolutionary algorithms,” Evolutionary Computation, vol. 13, no. 4, pp. 413–440, 2005

    2005

  31. [39]

    The interplay of population size and mutation probability in the (1+ λ) ea on onemax,

    C. Gießen and C. Witt, “The interplay of population size and mutation probability in the (1+ λ) ea on onemax,” Algorithmica, vol. 78, no. 2, pp. 587–609, 2017

    2017

  32. [40]

    Royal road functions and the (1+ λ) evolutionary algorithm: Almost no speed-up from larger offspring populations,

    B. Doerr and M. Künnemann, “Royal road functions and the (1+ λ) evolutionary algorithm: Almost no speed-up from larger offspring populations,” in IEEE Congr. Evol. Comput. IEEE, 2013, pp. 424– 431

    2013

  33. [41]

    Analysis of population-based evolu- tionary algorithms for the vertex cover problem,

    P. S. Oliveto, J. He, and X. Yao, “Analysis of population-based evolu- tionary algorithms for the vertex cover problem,” in IEEE Cong. Evol. Comput., CEC. IEEE, 2008, pp. 1563–1570

    2008

  34. [42]

    Runtime analysis of the ( µ+ 1) ea on simple pseudo-boolean functions,

    C. Witt, “Runtime analysis of the ( µ+ 1) ea on simple pseudo-boolean functions,” Evol. Comput., vol. 14, no. 1, pp. 65–86, 2006

    2006

  35. [43]

    Analysis of evolutionary algorithms on fitness function with time-linkage property,

    W. Zheng, H. Chen, and X. Yao, “Analysis of evolutionary algorithms on fitness function with time-linkage property,” IEEE Trans. Evol. Comput., vol. 25, no. 4, pp. 696–709, 2021

    2021

  36. [44]

    Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,

    M. Theile, “Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm,” in Lect. Notes Comput. Sci. Springer, 2009, pp. 145–155

    2009

  37. [45]

    Fixed-parameter evolutionary algorithms for the euclidean traveling salesperson problem,

    S. Nallaperuma, A. M. Sutton, and F. Neumann, “Fixed-parameter evolutionary algorithms for the euclidean traveling salesperson problem,” in IEEE Congr. Evol. Comput., CEC . IEEE, 2013, pp. 2037–2044

    2013

  38. [46]

    Crossover can simulate bounded tree search on a fixed- parameter tractable optimization problem,

    A. M. Sutton, “Crossover can simulate bounded tree search on a fixed- parameter tractable optimization problem,” in Proc. Gen. Evol. Comput. Conf., 2018, pp. 1531–1538

    2018

  39. [47]

    A lower bound analysis of population- based evolutionary algorithms for pseudo-boolean functions,

    C. Qian, Y . Yu, and Z.-H. Zhou, “A lower bound analysis of population- based evolutionary algorithms for pseudo-boolean functions,” in Lect. Notes Comput. Sci. Springer, 2016, pp. 457–467

    2016

  40. [48]

    Does comma selection help to cope with local optima?

    B. Doerr, “Does comma selection help to cope with local optima?” in Proc. Gen. Evol. Comput. Conf. , 2020, pp. 1304–1313

    2020

  41. [49]

    On the limitations of the univariate marginal distribution algorithm to deception and where bivariate edas might help,

    P. K. Lehre and P. T. H. Nguyen, “On the limitations of the univariate marginal distribution algorithm to deception and where bivariate edas might help,” in Proc. ACM/SIGEVO Conf. Found. Genet. Algorithms. (FOGA), 2019, pp. 154–168

    2019

  42. [50]

    The analysis of evolutionary optimisation on the tsp(1,2) problem,

    X. Xia, X. Lai, and C. Yi, “The analysis of evolutionary optimisation on the tsp(1,2) problem,” Int. J. Comput. Sci. Eng. , vol. 18, no. 3, pp. 261–268, 2019

    2019

  43. [51]

    Evolutionary computation: Comments on the history and current state,

    T. Back, U. Hammel, and H.-P. Schwefel, “Evolutionary computation: Comments on the history and current state,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 3–17, 1997

    1997

  44. [52]

    Durrett, Probability: Theory and Examples

    R. Durrett, Probability: Theory and Examples . Cambridge university press, 2019, vol. 49

    2019

  45. [53]

    A new approach to estimating the expected first hitting time of evolutionary algorithms,

    Y . Yu and Z.-H. Zhou, “A new approach to estimating the expected first hitting time of evolutionary algorithms,” Artif. Intell., vol. 172, no. 15, pp. 1809–1832, 2008

    2008

  46. [54]

    Quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions,

    Y . Akimoto, A. Auger, and N. Hansen, “Quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions,” in Theor. Comput. Sci., vol. 832, 2020, pp. 42–67

    2020

  47. [55]

    Analysis of the (1+ 1) EA on subclasses of linear functions under uniform and linear constraints,

    T. Friedrich, T. Kötzing, G. Lagodzinski, F. Neumann, and M. Schirneck, “Analysis of the (1+ 1) EA on subclasses of linear functions under uniform and linear constraints,” in Proc. ACM/SIGEVO Conf. Found. Genet. Algorithms. (FOGA) , 2017, pp. 45–54

    2017

  48. [56]

    Runtime analysis of an ant colony optimization algorithm for tsp instances,

    Y . Zhou, “Runtime analysis of an ant colony optimization algorithm for tsp instances,” IEEE Trans. Evol. Comput. , vol. 13, no. 5, pp. 1083– 1092, 2009

    2009

  49. [57]

    Theoretical analysis of two aco approaches for the traveling salesman problem,

    T. Kötzing, F. Neumann, H. Röglin, and C. Witt, “Theoretical analysis of two aco approaches for the traveling salesman problem,” Swarm Intell., vol. 6, pp. 1–21, 2012

    2012

  50. [58]

    Approximation performance of ant colony optimization for the tsp (1, 2) problem,

    X. Peng, Y . Zhou, and G. Xu, “Approximation performance of ant colony optimization for the tsp (1, 2) problem,” Int. J. Comput. Math. , vol. 93, no. 10, pp. 1683–1694, 2016

    2016

  51. [59]

    The traveling salesman problem with few inner points,

    V . G. Deı, M. Hoffmann, Y . Okamoto, G. J. Woeginger et al. , “The traveling salesman problem with few inner points,” Oper. Res. Lett. , vol. 34, no. 1, pp. 106–110, 2006

    2006

  52. [60]

    Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection,

    C. Bian and C. Qian, “Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection,” in Lect. Notes Comput. Sci , 2022, pp. 428–441

    2022

  53. [61]

    G. R. Iversen and M. Gergen, Statistics: The Conceptual Approach . Springer, 1997

    1997

Pith tools

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