Pith. sign in

REVIEW 2 major objections 4 minor 69 references

The Runtime of the Compact Genetic Algorithm on Jump Functions

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For jump widths up to (1/20) ln n, the compact genetic algorithm optimizes in O(n log n), matching OneMax; larger jumps cost exponential time for every population-size setting.

desk verdict A genuine breakthrough for EDA runtime analysis, with a solid self-contained upper bound and exponential lower bound, but the matching Ω(n log n) lower bound is conditional on an unverified transfer from Sudholt–Witt. read the letter →

arxiv 1908.06527 v2 pith:674MYG5N submitted 2019-08-18 cs.NE cs.DS

Benjamin Doerr This is my paper · ORCID
classification cs.NEcs.DS MSC 68Q2568W20
keywords compactgeneticalgorithmestimation-of-distributionalgorithmsjumpfunctionsruntimeanalysisdriftmultimodaloptimizationpopulationsizelowerbounds
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 proves that the compact genetic algorithm (cGA) can cross moderate fitness valleys at no extra cost. On any $n$-dimensional jump function with gap width $k \le \frac{1}{20}\ln n - 1$, the cGA with hypothetical population size $\mu$ between $\Omega(\sqrt n \log n)$ and $\operatorname{poly}(n)$ finds the optimum with high probability in $O(\mu\sqrt n)$ iterations, which is $O(n\log n)$ for the smallest admissible $\mu$---the same order as its runtime on the unimodal OneMax function. For larger gaps, the paper shows an exponential lower bound $\exp(\Omega(k))$ that holds for every population size, so the earlier exponential guarantee of [HS18] cannot be improved by tuning $\mu$. A matching lower bound $\Omega(\mu\sqrt n + n\log n)$ for all jump functions, plus a parallel-run method that converts high-probability guarantees into expected runtimes without prescribing $\mu$, completes the picture.

What carries the argument

The load-bearing object is the cGA's frequency vector $f_t$ and its aggregate distance from the all-ones optimum, $D_t = n - \|f_t\|_1$. While $D_t$ is large, gap samples are so rare that the run can be coupled to a OneMax run (Lemma 16); the proof then uses a drift estimate (Lemma 17) that corrects a mean-field mistake in [HS18], and a reduction of each component frequency to a fair random walk on a reflecting grid (Lemma 19) that keeps all frequencies above $1/3$ for long enough. In this regime the drift of $D_t$ is $\Omega(1/\mu)$, which by the additive drift theorem yields $D_t \le O(k)$ within $O(\mu\sqrt n)$ iterations. From such small $D_t$, Lemma 11 shows the optimum is sampled with probability $1-n^{-\omega(1)}$ in $O(\mu \log^{-2} n)$ more iterations. The exponential lower bound uses a different object: the rescaled process $Y_t = \exp(c\min\{\frac12 k - D_t, \frac14 k\})$, whose one-step drift is at most a constant; a Markov bound then forces $D_t$ to remain above $k/4$ for $\exp(\Omega(k))$ steps.

What would settle it

Evaluate exactly, for the cGA on a jump function with k ≤ κn, the one-step probability that a frequency at the lower boundary 1/n enters the interior. The proof of the Ω(n log n) lower bound requires this probability to be O(1/n) and requires at least √n frequencies to remain at the boundary; a numerical Markov-chain calculation that finds a larger exit probability, or fewer pinned frequencies, would invalidate Theorem 26.

Watch

Extended reading notes

Core claim

The central discovery is that the cGA's runtime on jump functions is controlled by the frequency distance $D_t = n - \|f_t\|_1$: as long as no sampled search point lies in the gap, the process behaves exactly as on OneMax, and once a gap sample occurs, the drift of $D_t$ can still be bounded from below. The paper proves (Theorem 13) that for jump size $k \le \frac{1}{20}\ln n - 1$, any hypothetical population size $\mu$ between $\Omega(\sqrt n \log n)$ and $\operatorname{poly}(n)$ yields $O(\mu\sqrt n)$ iterations with probability $1-O(n^{-0.4})$; with $\mu = \Theta(\sqrt n \log n)$ this is $O(n\log n)$. The proof is phase-based: first $D_t$ is driven to $O(\log n)$ without ever sampling the gap, then to $O(k)$ using the drift estimate of Lemma 17, while Lemma 19, a pessimistic fair-random-walk replacement for each frequency, rules out frequencies dropping below $1/3$; from a state with $D_t$ of order $k$, Lemma 11 shows the optimum is sampled quickly with overwhelming probability. Theorem 22 gives the complementary lower bound: for every $\mu$, an exponential rescaling $Y_t = \exp(c\min\{\frac12 k - D_t, \frac14 k\})$ has at most constant drift, so $D_t$ stays above $k/4$ for $\exp(\Omega(k))$ steps, and in each such step the optimum is sampled only with probability $\exp(-\Omega(k))$. Theorem 26 transfers the OneMax lower bound of [SW19] to jump functions, giving $\Omega(\mu\sqrt n + n\log n)$ and establishing that the upper bound is tight at the optimal $\mu$.

Load-bearing premise

The matching Ω(n log n) lower bound assumes that [SW19]'s OneMax lemmas remain valid for jump functions; footnote 4 in the proof of Theorem 26 concedes that one boundary-exit probability is wrong and replaces it with a weaker estimate confirmed only privately, with no self-contained proof in this paper.

Editorial extensions

If this is right

  • For $k \le \frac{1}{20}\ln n - 1$, the cGA with $\mu = \Theta(\sqrt n \log n)$ solves every subjump function in $O(n\log n)$ iterations with probability $1-O(n^{-0.4})$, the same asymptotic as its OneMax runtime.
  • The prior guarantee of $O(n^{5+\varepsilon})$ for small $k$ is replaced by $O(n\log n)$, and the usable population sizes are enlarged from $\Omega(n^{3.5+\varepsilon})$ down to $\Omega(\sqrt n \log n)$.
  • For any hypothetical population size, jump size $k = \omega(\log n)$ forces runtime $\exp(\Omega(k))$ with high probability, so no parameter tuning can beat the exponential guarantee of [HS18].
  • The lower bound $\Omega(\mu\sqrt n + n\log n)$ for $\mu = \Omega(\log n)$ on jump functions matches the upper bound, so the $O(n\log n)$ result is tight at the optimal $\mu$.
  • The parallel-run method converts an EDA with a high-probability runtime guarantee into a parameter-less version with expected runtime $O(T^*\log T^*)$, where $T^*$ is the best restart-based bound with the optimal population size.

Reading between the lines

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

  • The proof's diagnosis that the cGA samples candidates with high variance, hitting the optimum from distance $O(k)$ with probability $\exp(-O(k))$ rather than $n^{-k}$, suggests that other EDAs with similar sampling variance, such as the UMDA, may also cross logarithmic jumps at no extra cost; the paper does not prove this.
  • Because the paper shows the natural domination arguments that make OneMax the easiest function for many evolutionary algorithms fail for the cGA, a general $\Omega(n\log n)$ lower bound for all functions with a unique optimum would need a proof genuinely about the cGA's stochastic process, not a black-box reduction.
  • The $\Omega(n\log n)$ lower bound is proved for jump functions, not for superjump functions; the failure of the OneMax lower bound to transfer to all unique-optimum functions leaves open the possibility that superjump functions are strictly harder for the cGA.
  • A direct test of the sampling-variance mechanism would be to run a cGA variant with artificially reduced sampling variance on small-$k$ jumps; the theory predicts its runtime should degrade toward the exponential regime at smaller $k$ than the standard cGA.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 analyzes the runtime of the compact genetic algorithm (cGA) on jump functions. It proves an O(µ√n) upper bound (Theorem 13) for subjump functions with jump size k ≤ (1/20)ln n - 1 and µ ≥ K√n ln n polynomially bounded in n, an exponential lower bound exp(Ω(k)) for all hypothetical population sizes µ (Theorem 22), and a lower bound Ω(µ√n + n log n) (Theorem 26) intended to match the upper bound for small k. The paper also contains ancillary results: a parallel-run scheme that converts high-probability runtime guarantees into expected-runtime guarantees (Theorem 2), and negative results showing that standard domination arguments cannot transfer OneMax lower bounds to arbitrary functions with unique optimum (Lemmas 24 and 25).

Significance. If the main results hold, this is a significant advance in the theory of estimation-of-distribution algorithms: it is the first analysis showing that the cGA can cross moderate fitness valleys at no extra cost compared with optimizing OneMax, and it provides the first exponential lower bound for an EDA that holds for arbitrary parameter settings. Theorems 13 and 22 are supported by detailed, self-contained proofs with explicit universal constants, and the paper correctly identifies and avoids a mean-field dependency issue in the earlier analysis of Hasenöhrl and Sutton. The parallel-run meta-algorithm of Theorem 2 is a useful side contribution. However, the lower bound in Theorem 26 is not self-contained and currently rests on a privately communicated correction, so the paper's 'complete the picture' claim is conditional.

major comments (2)
  1. [Section 6.2, Theorem 26 and footnote 4] The claimed Ω(µ√n + n log n) lower bound is not proven in the manuscript. The proof states that a self-contained version cannot be given and instead transfers Lemmas 10–15 of [SW19] to jump functions, including a boundary correction from O(n^{-3/2}) to O(1/n) that is said to have been confirmed privately by the authors of [SW19]. Because the corrected estimate is not proved and its propagation through Lemma 15 of [SW19] and the final paragraphs of that proof is not quantified, the theorem as stated is conditional. This is load-bearing for the abstract's claim that the picture is completed; either include the full transfer argument or state Theorem 26 as a conditional result and adjust the abstract and conclusion accordingly.
  2. [Section 6.2, footnote 4] The assertion that with the correct boundary estimate 'at least √n frequencies remain at the lower boundary at the end of the first T iterations' needs a supporting calculation. Lemma 15 of [SW19] has failure probability poly(n)2^{-Ω(min{µ,n})}, and it is not immediate that a per-iteration exit probability of O(1/n) preserves the conclusion under the constants needed in that proof. Without a self-contained analysis of this point, the Ω(n log n) part of Theorem 26 is unsupported.
minor comments (4)
  1. [Abstract and Section 1.1] The notation μ = Ω(√n log n) ∩ poly(n) is nonstandard as written; the theorem statements later give the intended meaning (μ ≥ c_μ√n ln n and μ ≤ n^{C_μ}), so the abstract formulation should be aligned with the precise statements.
  2. [Section 4.4] There is a typo: 'mution' should be 'mutation' in the sentence beginning 'the number of bits that are flipped in a mution follows a binomial distribution'.
  3. [Lemma 12] In the proof of Lemma 12 the dimension parameter m is set, but the proof then uses n in expressions such as x1[ℓ+1..n]; this should be reconciled by consistently using m or by writing n for the dimension throughout the proof.
  4. [Section 2.2] The phrase 'with high probability needs at least Ω(µ√n + n log n) iterations' could be made more precise by noting that this is a lower bound on the optimization time, not on the first hitting time of a particular frequency state; the formal statements in Section 6 are clearer.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core upper and exponential lower bounds are self-contained derivations against external benchmarks, and the conditional Ω(n log n) lower bound rests on an external proof rather than on a self-citation or a fitted parameter.

full rationale

I walked the derivation chain for each main claim. Theorem 13, the O(µ√n) upper bound for subjump functions, is proved from scratch inside the paper: constants are universal (e.g., cµ, Cµ, D′, D′′ are chosen by asymptotic arguments, not fitted to data), and μ and k are quantified variables. Its external dependencies, Droste's Lemma 5/14 and Sudholt–Witt's Lemma 20, are published independent results whose assumptions do not include the target conclusion. Theorem 22, the exponential lower bound for superjump functions, is self-contained: it introduces the rescaled process Y_t, derives the drift bound E[Y_{t+1}-Y_t | Y_t=y] ≤ 2 through its own Cases 1 and 2, and then applies Markov's inequality with a universal constant c. No step in that proof reduces to the claimed runtime by construction. The only load-bearing weakness is Theorem 26, the Ω(µ√n + n log n) lower bound. Section 6.2 explicitly says 'we cannot give a self-contained version of the proof' and instead transfers Lemmas 10–15 of [SW19] to jump functions; footnote 4 concedes that one transferred estimate (the O(n^{-3/2}) boundary-leaving probability) is wrong and must be replaced by O(1/n), with the correction confirmed only privately by the authors of [SW19]. This is a genuine completeness and verification concern: the matching lower bound is conditional on an unverified transfer and a private communication. However, it is not circularity under the stated definitions. The cited work is external, the paper does not fit a parameter and then rename it as a prediction, and the paper does not rely on its own prior work [Doe19b, Doe19c] as the source of the target conclusion; those self-citations are preliminary versions of the same results, not load-bearing external justification. There is also no uniqueness theorem imported from the author's own prior work and no ansatz smuggled in via self-citation. Because no equation in the paper is equivalent to its own input by construction, the appropriate finding is no significant circularity, score 0.

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

No parameters are fitted: all constants are universal, chosen by asymptotic arguments, and µ and k are quantified variables of the theorems. The central claims rest on standard probabilistic tools, the well-behaved frequency assumption, and several published external lemmas; the most fragile is the transfer of SW19's proof in Section 6.2.

assumptions (6)
  • standard math Multiplicative and additive Chernoff/Hoeffding bounds for sums of independent [0,1] variables (Theorems 4 and 6)
    Section 3.1: used throughout for concentration of sample counts and for partial-sum bounds in Lemma 19 and Lemma 21.
  • standard math Additive drift theorem of He-Yao (Theorem 7)
    Section 3.1: used to convert expected progress into hitting-time bounds in Lemma 18.
  • domain assumption Well-behaved frequency assumption: µ is such that (1 - 2/n)µ is an even integer, so all frequencies lie on the lattice F_µ = {1/n + i/µ}
    Section 2.1: standard in cGA analyses; needed in Lemmas 8, 12, 17, 19, and 21 for exact step-size bookkeeping. It restricts the parameter settings but is satisfied by even µ with nµ even.
  • standard math Lemma 14 from Droste [Dro06]: a constant C exists such that two independent samples from f ∈ [1/3,1]^n with OneMax distance D have 1-norm difference at least (1/5)√D with probability at least C
    Section 4.2: unproved in this paper; load-bearing in Lemmas 15 and 17 for the drift of D_t.
  • standard math Lemma 20 from Sudholt-Witt [SW19]: for the OneMax process, the expected increase of a non-boundary frequency is at least (2/11)f_i(1-f_i)(Σ_{j≠i} f_j(1-f_j))^{-1/2}
    Section 4.2: unproved in this paper; used in Lemma 21 to guarantee frequencies remain above 1/3.
  • standard math Correctness and transferability of the internal lemmas (Lemmas 10-15) of the proof of Theorem 8 in [SW19] to jump functions
    Section 6.2: Theorem 26 is obtained by re-using the SW19 proof structure; the paper does not give a self-contained proof and relies on a private correction to a boundary-leaving probability (footnote 4).

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Runtime of the Compact Genetic Algorithm on Jump Functions." pith.science (2026). https://pith.science/paper/674MYG5N

@misc{pith2026190806527,
  author       = {Pith},
  title        = {Pith review of: The Runtime of the Compact Genetic Algorithm on Jump Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/674MYG5N}},
  note         = {Machine review of arXiv:1908.06527}
}
abstract

In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, Hasen\"ohrl and Sutton (GECCO 2018) showed for any $k = o(n)$ that the compact genetic algorithm (cGA) with any hypothetical population size $\mu = \Omega(ne^{4k} + n^{3.5+\varepsilon})$ with high probability finds the optimum of the $n$-dimensional jump function with jump size $k$ in time $O(\mu n^{1.5} \log n)$. We significantly improve this result for small jump sizes $k \le \frac 1 {20} \ln n -1$. In this case, already for $\mu = \Omega(\sqrt n \log n) \cap \text{poly}(n)$ the runtime of the cGA with high probability is only $O(\mu \sqrt n)$. For the smallest admissible values of $\mu$, our result gives a runtime of $O(n \log n)$, whereas the previous one only shows $O(n^{5+\varepsilon})$. Since it is known that the cGA with high probability needs at least $\Omega(\mu \sqrt n)$ iterations to optimize the unimodal OneMx function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. For large $k$, we show that the exponential (in $k$) runtime guarantee of Hasen\"ohrl and Sutton is tight and cannot be improved, also not by using a smaller hypothetical population size. We prove that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size $k$. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 65 canonical work pages

  1. [1]

    The query complexity of a permutation-based variant of M astermind

    Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, and Kurt Mehlhorn. The query complexity of a permutation-based variant of M astermind. Discrete Applied Mathematics , 260:28--50, 2019

    work page 2019

  2. [2]

    Theory of Randomized Search Heuristics

    Anne Auger and Benjamin Doerr, editors. Theory of Randomized Search Heuristics . World Scientific Publishing, 2011

    work page 2011

  3. [3]

    Precise runtime analysis for plateaus

    Denis Antipov and Benjamin Doerr. Precise runtime analysis for plateaus. In Parallel Problem Solving From Nature, PPSN 2018, Part II , pages 117--128. Springer, 2018

    work page 2018

  4. [4]

    Runtime analysis of a heavy-tailed (1+( , )) genetic algorithm on jump functions

    Denis Antipov and Benjamin Doerr. Runtime analysis of a heavy-tailed (1+( , )) genetic algorithm on jump functions. In Parallel Problem Solving From Nature, PPSN 2020 . Springer, 2020. To appear

    work page 2020

  5. [5]

    The (1 + ( , )) GA is even faster on multimodal problems

    Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. The (1 + ( , )) GA is even faster on multimodal problems. In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 1259--1267. ACM , 2020

    work page 2020

  6. [6]

    The efficiency threshold for the offspring population size of the ( , ) EA

    Denis Antipov, Benjamin Doerr, and Quentin Yang. The efficiency threshold for the offspring population size of the ( , ) EA . In Genetic and Evolutionary Computation Conference, GECCO 2019 , pages 1461--1469. ACM , 2019

    work page 2019

  7. [7]

    Paul Wiegand

    Gautham Anil and R. Paul Wiegand. Black-box search by elimination of fitness functions. In Foundations of Genetic Algorithms, FOGA 2009 , pages 67--78. ACM, 2009

    work page 2009

  8. [8]

    The unrestricted black-box complexity of jump functions

    Maxim Buzdalov, Benjamin Doerr, and Mikhail Kever. The unrestricted black-box complexity of jump functions. Evolutionary Computation , 24:719--744, 2016

    work page 2016

Show all 69 references
  1. [9]

    Oliveto, and Donya Yazdani

    Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. On the runtime analysis of the O pt- IA artificial immune system. In Genetic and Evolutionary Computation Conference, GECCO 2017 , pages 83--90. ACM , 2017

    2017

  2. [10]

    Oliveto, and Donya Yazdani

    Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. Fast artificial immune systems. In Parallel Problem Solving from Nature, PPSN 2018, Part II , pages 67--78. Springer, 2018

    2018

  3. [11]

    From black-box complexity to designing new genetic algorithms

    Benjamin Doerr, Carola Doerr, and Franziska Ebel. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science , 567:87--104, 2015

    2015

  4. [12]

    Krejca, Per Kristian Lehre, Pietro S

    Duc - Cuong Dang, Tobias Friedrich, Timo K \" o tzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. Escaping local optima with diversity mechanisms and crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016 , p...

    2016

  5. [13]

    Krejca, Per Kristian Lehre, Pietro S

    Duc - Cuong Dang, Tobias Friedrich, Timo K \" o tzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation , 22:484--497, 2018

    2018

  6. [14]

    Tight analysis of the (1+1)- EA for the single source shortest path problem

    Benjamin Doerr, Edda Happ, and Christian Klein. Tight analysis of the (1+1)- EA for the single source shortest path problem. Evolutionary Computation , 19:673--691, 2011

    2011

  7. [15]

    Edge-based representation beats vertex-based representation in shortest path problems

    Benjamin Doerr and Daniel Johannsen. Edge-based representation beats vertex-based representation in shortest path problems. In Genetic and Evolutionary Computation Conference, GECCO 2010 , pages 759--766. ACM, 2010

    2010

  8. [16]

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

    Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science , 276:51--81, 2002

    2002

  9. [17]

    Upper and lower bounds for randomized search heuristics in black-box optimization

    Stefan Droste, Thomas Jansen, and Ingo Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems , 39:525--544, 2006

    2006

  10. [18]

    Multiplicative drift analysis

    Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica , 64:673--697, 2012

    2012

  11. [19]

    Benjamin Doerr and Martin S. Krejca. Significance-based estimation-of-distribution algorithms. IEEE Transactions on Evolutionary Computation , 2020. To appear

    2020

  12. [20]

    Benjamin Doerr and Martin S. Krejca. The univariate marginal distribution algorithm copes well with deception and epistasis. In Evolutionary Computation in Combinatorial Optimization, EvoCOP 2020 , pages 51--66. Springer, 2020

    2020

  13. [21]

    Fast genetic algorithms

    Benjamin Doerr, Huu Phuoc Le, R\'egis Makhmara, and Ta Duy Nguyen. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017 , pages 777--784. ACM , 2017

    2017

  14. [22]

    Theory of Evolutionary Computation---Recent Developments in Discrete Optimization

    Benjamin Doerr and Frank Neumann, editors. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization . Springer, 2020. Also available at https://cs.adelaide.edu.au/ frank/papers/TheoryBook2019-selfarchived.pdf

    2020

  15. [23]

    Analyzing randomized search heuristics via stochastic domination

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

    2019

  16. [24]

    An exponential lower bound for the runtime of the compact genetic algorithm on jump functions

    Benjamin Doerr. An exponential lower bound for the runtime of the compact genetic algorithm on jump functions. In Foundations of Genetic Algorithms, FOGA 2019 , pages 25--33. ACM , 2019

    2019

  17. [25]

    A tight runtime analysis for the cGA on jump functions: EDA s can cross fitness valleys at no extra cost

    Benjamin Doerr. A tight runtime analysis for the cGA on jump functions: EDA s can cross fitness valleys at no extra cost. In Genetic and Evolutionary Computation Conference, GECCO 2019 , pages 1488--1496. ACM , 2019

    2019

  18. [26]

    Does comma selection help to cope with local optima? In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 1304--1313

    Benjamin Doerr. Does comma selection help to cope with local optima? In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 1304--1313. ACM , 2020

    2020

  19. [27]

    Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift

    Benjamin Doerr. Lower bounds for non-elitist evolutionary algorithms via negative multiplicative drift. In Parallel Problem Solving From Nature, PPSN 2020 . Springer, 2020. To appear

    2020

  20. [28]

    Probabilistic tools for the analysis of randomized optimization heuristics

    Benjamin Doerr. Probabilistic tools for the analysis of randomized optimization heuristics. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization , pages 1--87. Springer, 2020. Also available at https://a...

    2020 arXiv

  21. [29]

    A rigorous analysis of the compact genetic algorithm for linear functions

    Stefan Droste. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing , 5:257--283, 2006

    2006

  22. [30]

    Ranking-based black-box complexity

    Benjamin Doerr and Carola Winzen. Ranking-based black-box complexity. Algorithmica , 68:571--609, 2014

    2014

  23. [31]

    A parameter-less compact genetic algorithm

    Benjamin Doerr and Weijie Zheng. A parameter-less compact genetic algorithm. In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 805--813. ACM , 2020

    2020

  24. [32]

    Sharp bounds for genetic drift in estimation-of-distribution algorithms

    Benjamin Doerr and Weijie Zheng. Sharp bounds for genetic drift in estimation-of-distribution algorithms. IEEE Transactions on Evolutionary Computation , 2020. To appear

    2020

  25. [33]

    Working principles of binary differential evolution

    Benjamin Doerr and Weijie Zheng. Working principles of binary differential evolution. Theoretical Computer Science , 801:110--142, 2020

    2020

  26. [34]

    Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck

    Tobias Friedrich, Timo K \" o tzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck. Fast building block assembly by majority vote crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016 , pages 661--668. ACM , 2016

    2016

  27. [35]

    Krejca, and Andrew M

    Tobias Friedrich, Timo K \" o tzing, Martin S. Krejca, and Andrew M. Sutton. The compact genetic algorithm is efficient under extreme G aussian noise. IEEE Transactions on Evolutionary Computation , 21:477--490, 2017

    2017

  28. [36]

    Escaping large deceptive basins of attraction with heavy-tailed mutation operators

    Tobias Friedrich, Francesco Quinzan, and Markus Wagner. Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In Genetic and Evolutionary Computation Conference, GECCO 2018 , pages 293--300. ACM , 2018

    2018

  29. [37]

    On the choice of the parameter control mechanism in the (1+( , )) genetic algorithm

    Mario Alejandro Hevia Fajardo and Dirk Sudholt. On the choice of the parameter control mechanism in the (1+( , )) genetic algorithm. In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 832--840. ACM, 2020

    2020

  30. [38]

    Evolutionary algorithms and the maximum matching problem

    Oliver Giel and Ingo Wegener. Evolutionary algorithms and the maximum matching problem. In Symposium on Theoretical Aspects of Computer Science, STACS 2003 , pages 415--426. Springer, 2003

    2003

  31. [39]

    Searching randomly for maximum matchings

    Oliver Giel and Ingo Wegener. Searching randomly for maximum matchings. Electronic Colloquium on Computational Complexity (ECCC) , (076), 2004

    2004

  32. [40]

    The interplay of population size and mutation probability in the (1 + ) EA on OneMax

    Christian Gie en and Carsten Witt. The interplay of population size and mutation probability in the (1 + ) EA on OneMax . Algorithmica , 78:587--609, 2017

    2017

  33. [41]

    Harik, Fernando G

    Georges R. Harik, Fernando G. Lobo, and David E. Goldberg. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation , 3:287--297, 1999

    1999

  34. [42]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58:13--30, 1963

    1963

  35. [43]

    V \' a clav Hasen \" o hrl and Andrew M. Sutton. On the runtime dynamics of the compact genetic algorithm on jump functions. In Genetic and Evolutionary Computation Conference, GECCO 2018 , pages 967--974. ACM , 2018

    2018

  36. [44]

    Drift analysis and average time complexity of evolutionary algorithms

    Jun He and Xin Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence , 127:51--81, 2001

    2001

  37. [45]

    Analyzing Evolutionary Algorithms -- The Computer Science Perspective

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

    2013

  38. [46]

    De Jong, and Ingo Wegener

    Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation , 13:413--440, 2005

    2005

  39. [47]

    Oliveto, and Christine Zarges

    Thomas Jansen, Pietro S. Oliveto, and Christine Zarges. Approximating vertex cover using edge-based representations. In Foundations of Genetic Algorithms, FOGA 2013 , pages 87--96. ACM , 2013

    2013

  40. [48]

    The analysis of evolutionary algorithms -- a proof that crossover really can help

    Thomas Jansen and Ingo Wegener. The analysis of evolutionary algorithms -- a proof that crossover really can help. Algorithmica , 34:47--66, 2002

    2002

  41. [49]

    Theory of estimation-of-distribution algorithms

    Martin Krejca and Carsten Witt. Theory of estimation-of-distribution algorithms. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization , pages 405--442. Springer, 2020. Also available at https://arxiv.org...

    2020 arXiv

  42. [50]

    Krejca and Carsten Witt

    Martin S. Krejca and Carsten Witt. Lower bounds on the run time of the U nivariate M arginal D istribution A lgorithm on OneMax . Theoretical Computer Science , 832:143--165, 2020

    2020

  43. [51]

    Drift analysis

    Johannes Lengler. Drift analysis. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization , pages 89--131. Springer, 2020. Also available at https://arxiv.org/abs/1712.00964

    2020 arXiv

  44. [52]

    Estimation of Distribution Algorithms

    Pedro Larra \ n aga and Jos \' e Antonio Lozano, editors. Estimation of Distribution Algorithms . Genetic Algorithms and Evolutionary Computation. Springer, 2002

    2002

  45. [53]

    Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration

    Per Kristian Lehre and Phan Trung Hai Nguyen. Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration. In Genetic and Evolutionary Computation Conference, GECCO 2017 , pages 1383--1390. ACM , 2017

    2017

  46. [54]

    On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDA s might help

    Per Kristian Lehre and Phan Trung Hai Nguyen. On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDA s might help. In Foundations of Genetic Algorithms, FOGA 2019 , pages 154--168. ACM, 2019

    2019

  47. [55]

    Medium step sizes are harmful for the compact genetic algorithm

    Johannes Lengler, Dirk Sudholt, and Carsten Witt. Medium step sizes are harmful for the compact genetic algorithm. In Genetic and Evolutionary Computation Conference, GECCO 2018 , pages 1499--1506. ACM , 2018

    2018

  48. [56]

    Black-box search by unbiased variation

    Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica , 64:623--642, 2012

    2012

  49. [57]

    Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity

    Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity . Springer, 2010

    2010

  50. [58]

    Oliveto, Jun He, and Xin Yao

    Pietro S. Oliveto, Jun He, and Xin Yao. Analysis of the (1+1) - EA for finding approximate solutions to vertex cover problems. IEEE Transactions on Evolutionary Computation , 13:1006--1029, 2009

    2009

  51. [59]

    Oliveto and Carsten Witt

    Pietro S. Oliveto and Carsten Witt. Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. CoRR , abs/1211.7184, 2012

    2012 arXiv

  52. [60]

    Martin Pelikan, Mark Hauschild, and Fernando G. Lobo. Estimation of distribution algorithms. In Janusz Kacprzyk and Witold Pedrycz, editors, Springer Handbook of Computational Intelligence , pages 899--928. Springer, 2015

    2015

  53. [61]

    Rowe and Aishwaryaprajna

    Jonathan E. Rowe and Aishwaryaprajna. The benefits and limitations of voting mechanisms in evolutionary optimisation. In Foundations of Genetic Algorithms, FOGA 2019 , pages 34--42. ACM , 2019

    2019

  54. [62]

    Self-adjusting evolutionary algorithms for multimodal optimization

    Amirhossein Rajabi and Carsten Witt. Self-adjusting evolutionary algorithms for multimodal optimization. In Genetic and Evolutionary Computation Conference, GECCO 2020 , pages 1314--1322. ACM , 2020

    2020

  55. [63]

    A new method for lower bounds on the running time of evolutionary algorithms

    Dirk Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation , 17:418--435, 2013

    2013

  56. [64]

    On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization

    Dirk Sudholt and Carsten Witt. On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. Algorithmica , 81:1450--1489, 2019

    2019

  57. [65]

    Simulated annealing beats M etropolis in combinatorial optimization

    Ingo Wegener. Simulated annealing beats M etropolis in combinatorial optimization. In Automata, Languages and Programming, ICALP 2005 , pages 589--601. Springer, 2005

    2005

  58. [66]

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

    Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing , 22:294--318, 2013

    2013

  59. [67]

    Domino convergence: why one should hill-climb on linear functions

    Carsten Witt. Domino convergence: why one should hill-climb on linear functions. In Genetic and Evolutionary Computation Conference, GECCO 2018 , pages 1539--1546. ACM , 2018

    2018

  60. [68]

    Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax

    Carsten Witt. Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax . Algorithmica , 81:632--667, 2019

    2019

  61. [69]

    Exploration and exploitation without mutation: solving the jump function in (n) time

    Darrell Whitley, Swetha Varadarajan, Rachel Hirsch, and Anirban Mukhopadhyay. Exploration and exploitation without mutation: solving the jump function in (n) time. In Parallel Problem Solving from Nature, PPSN 2018, Part II , pages 55--66. Springer, 2018

    2018

Pith tools

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