Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator

Abderrahim Bendahi; Adrien Fradin; Benjamin Doerr; Johannes F. Lutzeyer

REVIEW 3 major objections 5 minor 21 references

Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A Markov chain that alternates between accepting only improvements and only worsenings lets a simple hyper-heuristic find global optima of Jump and Cliff functions in $O(n^3 \log n)$ expected time, independent of the gap size.

desk verdict A promising hyper-heuristic paper with a real result and a real gap: the OI+AM bound is solid, but the main OW/SEQOPT theorem rests on an unproved one-phase approximation. read the letter →

arxiv 2506.01107 v2 pith:76N3MIVN submitted 2025-06-01 cs.NE cs.AIcs.DS

Abderrahim Bendahi , Benjamin Doerr , Adrien Fradin , Johannes F. Lutzeyer This is my paper

classification cs.NEcs.AIcs.DS

keywords hyper-heuristicsruntimeanalysisMarkovchainoperatorselectiononly-worseningacceptancelocaloptimaJumpbenchmarkCliffSEQOPT

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proposes two changes to a move-acceptance hyper-heuristic and proves that together they remove the main cause of slow escape from local optima. First, the random per-iteration choice between acceptance operators is replaced by a two-state Markov chain, which creates long runs of the same operator. Second, the all-moves operator is replaced by an only-worsening operator that accepts a new solution only when it is strictly worse, a deliberate inversion of elitist search. On the new benchmark class $\mathrm{SEQOPT}_k$, the resulting algorithm reaches the global optimum of any function with $k$ successive local optima in expected time $O(n^{k+1} \log n \,/\, (d_1 \cdots d_k))$, and in particular solves $\mathrm{Jump}_m$ and $\mathrm{Cliff}_d$ in $O(n^3 \log n)$ independent of $m$ or $d$. The paper's central message is that leaving a local optimum is best done by explicitly searching downward, and that operator selection should be persistent rather than independent.

What carries the argument

The load-bearing objects are the two-state Markov chain governing operator selection and the only-worsening acceptance operator OW. In each phase the current operator is kept with probability $1-p$ (for OI) or $1-q$ (for OW), so phases have geometric lengths and, with $p, q = \Theta(1/(n \log n))$, long stretches of one operator are common. The phase-level probability lemma gives an exact formula for the chance that one OI phase starting in layer $k$ reaches layer $h$ on $\mathrm{ONEMAX}$, and an OW counterpart for descending; these feed the one-phase approximation, the assertion that a neighboring local optimum is reached in $O(1)$ phases on average, which is the step that carries the induction in the main theorem.

What would settle it

Take a fixed $\mathrm{Cliff}_d$ function with $d = n/2$ and run the MMAHH with $p = q = 1/(c n \log n)$, starting in the local maximum at layer $L_{n-d}$; record the number of operator phases until the algorithm first reaches layer $L_{n-d-1}$. If this expected number grows with $n$ rather than staying $O(1)$, the one-phase approximation fails and the $O(n^3 \log n)$ bound on $\mathrm{Cliff}_d$ would not follow from the given proof.

Watch

Extended reading notes

Core claim

The central claim is that a move-acceptance hyper-heuristic whose operator choice follows a two-state Markov chain, using only-improving (OI) and only-worsening (OW) acceptance, optimizes every function in a broad class $\mathrm{SEQOPT}_k$ in expected time $O(n^{k+1} \log n)$ when $k$ is constant. This class contains functions with $k$ successive local optima arranged in monotone layer intervals, including $\mathrm{ONEMAX}$, $\mathrm{TRAP}$, $\mathrm{Jump}_m$, and $\mathrm{Cliff}_d$. For $k = 2$ the bound becomes $O(n^3 \log n)$, independent of the difficulty parameters $m$ and $d$; for $\mathrm{Jump}_m$ the paper proves that the Markov-chain selection alone, with OI and all-moves, already improves the previous lower bound from $\Omega(n^{2m-1})$ to $O(n^{m+1})$. The proof proceeds by induction on the sequence of local optima, using phase-level estimates of how often an OI phase climbs to a prescribed layer and how often an OW phase descends, and bounding the number of failed excursions before the next local optimum is reached.

Load-bearing premise

The main theorem assumes that from any local optimum the algorithm reaches a neighboring local optimum after a constant expected number of operator phases, a step the paper states as Lemma 6 without a proof.

Editorial extensions

If this is right

On $\mathrm{Jump}_m$ and $\mathrm{Cliff}_d$ with constant $m$ or $d$, the expected runtime is $O(n^3 \log n)$, so the gap size stops appearing in the exponent and the earlier exponential-in-$m$ gap penalty disappears.
The same theorem covers the $\mathrm{CliffJump}_{d,r,s}$ benchmark with $O(n^3 \log n \,/\, (d(d-r)))$ expected runtime, a class not previously analyzed in this unified way.
For functions in $\mathrm{SEQOPT}_k$ with constant $k$, the runtime scales as $O(n^{k+1} \log n \,/\, (d_1 \cdots d_k))$, meaning the difficulty is governed by the product of the distances between successive local optima.
The Markov-chain selection alone, before OW is introduced, already reduces the $\mathrm{Jump}_m$ runtime from $\Omega(n^{2m-1})$ to $O(n^{m+1})$, showing that operator persistence, not just operator choice, is what drives the speedup.

Reading between the lines

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

If the one-phase approximation can be proved rigorously, the same phase-level argument should extend to acceptance operators that accept equal-fitness moves, removing the plateau restriction the paper notes as a limitation.
The OW operator suggests a general design heuristic for local-optimum escape: instead of random neutral or accepting-all moves, spend a phase deterministically decreasing fitness, and let the Markov chain control the phase length.
The exact phase-probability formula for $\mathrm{ONEMAX}$ may be reusable for other operator pairs with geometric phase lengths, since it depends only on the switching probabilities and the layer structure.
A testable prediction is that on functions with a wider local-optimum basin, the optimal switching probability should scale with the basin width; the paper's choice $p, q = \Theta(1/(n \log n))$ is tuned to the shallowest single-layer case.

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.

Desk Editor's Note

read the letter

The paper is a genuine step forward for move-acceptance hyper-heuristics. It introduces Markov-chain selection of acceptance operators, the only-worsening operator, and a clean unifying benchmark class, SEQOPT_k. The OI+AM result on Jump functions — O(n^{m+1}) instead of Omega(n^{2m-1}) — is new, and the proof structure there looks sound. The OI+OW runtime bounds on Jump, Cliff, and SEQOPT_k are the kind of result people in this subfield will want to know, assuming they hold up.

The main soft spot is exactly what the stress-test flags: Theorem 15 leans on Lemma 6, the one-phase approximation, which is stated without proof. The paragraph before it gives intuition from ONEMAX but does not justify the extension to arbitrary monotone segments of SEQOPT functions. That is load-bearing, so the central O(n^{k+1} log n) claim is not fully established as written. I would not call the paper wrong; I would call it incomplete. The gap looks fillable — the ingredients in Lemmas 3 and 4 are probably enough — but the authors need to supply the derivation.

The Lemma 8 arithmetic concern is less serious. The extraction makes it ambiguous, but the algebra in the appendix gives the correct drift (2i-n)/(2+q(n-2)), and the later proof of Lemma 13 uses that correct form. If the typesetting in the published version is genuinely missing the fraction bar, that is a minor typo, not a conceptual error.

The citation pattern is honest; the paper builds on Lissovoi et al. and the authors' own earlier MAHH analysis without hiding the negative result that motivated the fix. No circularity.

Who is it for: anyone working on runtime analysis of hyper-heuristics or black-box optimization on multimodal benchmarks. The OI+AM section alone justifies a serious referee. With Lemma 6 supplied, the paper would be a solid contribution. I would send it to review and ask for a proof of Lemma 6 (or a rewrite that avoids it) before accepting.

Referee Report

3 major / 5 minor

Summary. The paper studies a Markov-chain variant of the move-acceptance hyper-heuristic (MMAHH) in which the choice between two acceptance operators is made by a two-state Markov chain, and it introduces a new 'only-worsening' (OW) acceptance operator. It claims that, for switching probabilities p,q = Θ(1/(n log n)), the MMAHH using OI and OW reaches the global optimum of every function in the newly defined class SEQOPT_k with k = O(1) in expected time O(n^{k+1} log n / (d_1 ... d_k)); in particular it obtains O(n^3 log n) on Jump_m and Cliff_d, independent of the gap parameter. The paper also gives an analysis of the OI+AM variant on Jump_m, proving an O(n^{m+1}) bound. The proofs rely on a phase decomposition with geometric phase lengths, on closed-form success probabilities for a single OI phase (Lemmas 3 and 4), and on a 'one-phase approximation' (Lemma 6) that is stated without proof and is used to control progress between successive local optima in Theorem 15.

Significance. If established, the main result would be significant: it would show that a simple operator-selection mechanism removes the exponential dependence on the jump-gap parameter, and the SEQOPT_k framework usefully unifies several classic benchmarks. The paper contains substantial genuine technical content: Lemma 3 gives an explicit formula for one-phase success probabilities, Lemma 4 identifies the constant e^{-1/c}, Lemma 5 is a clean minimality statement, and Theorem 7 for the OI+AM variant is a complete standalone contribution. The OW operator is a novel and falsifiable design idea. However, the significance of the OI+OW result is conditional: Theorem 15 and Corollary 16 rest on Lemma 6 and on several excursion arguments that are not rigorously derived, so the central claim is not fully established as written.

major comments (3)

[Section 2.4, Lemma 6 and Section 4, Theorem 15] The 'one-phase approximation' is the linchpin of the main result but is asserted without proof. The motivating paragraph only analyzes full ONEMAX and then postulates the extension to arbitrary monotone segments of SEQOPT. In the base case of the proof of Theorem 15, the bound E[k*_1] ≤ 1/p0_n = O(1) is not a consequence of the formal statement of Lemma 6 (which concerns reaching a neighboring local optimum from a local optimum layer, not reaching the first local optimum from the boundary layer L_n), and the induction step uses the lemma to conclude that O(1) right-excursions reach L_{d_{ℓ+1}} and have total length O(n log n). Since Corollary 16 depends on Theorem 15, the central runtime claim is not formally established as written. This gap is fixable: a proof should show, via Lemma 5 and the geometric phase-length distribution, that on a monotone segment the appropriate operator reaches the opposite end with probability at least p0_n = Ω(1) per phase.
[Section 4, induction step of Theorem 15] The statement 'the length of any left-excursion can be upper-bounded by E[T_ℓ]' is asserted without argument. A left-excursion starts from a particular layer with a particular operator after leaving L_{d_ℓ}; it is not a copy of the original first-hitting problem from a random initial solution, so the claimed stochastic domination is not immediate. This needs a proof or a different bound, because the sum of left-excursion lengths contributes directly to the runtime bound E[T_{ℓ+1}].
[Section 4, induction step and Theorem 17] The proof moves from 'O(1) phases suffice to cross a right slope' to 'the total length of all right-excursions is O(n log n)' and then multiplies by E[k*] = O(n/d_ℓ), but the dependence between the random number of excursions and their lengths is not made precise. The simplified Wald equation is cited, yet the condition E[X_i | T ≥ i] ≤ C is not verified for the excursion lengths λ(e_i) plus waiting times. This is a rigor gap that should be closed; it is likely fixable with the phase-length lemmas.

minor comments (5)

[Section 2.4, Lemma 8] The display should be typeset as (2i-n)/(2+q(n-2)); as extracted it reads as (2i-n)/2 + q(n-2). The proof actually derives the fraction, so this is a notation/clarity issue rather than an algebra error.
[Corollary 16 (iii)] The corollary refers to CLIFFJUMP_{d,r,s} without defining it in the manuscript; please define the function or provide an explicit definition/reference in Section 2.1.
[Proof of Lemma 11] The straight path from L_m to x* requires m accepted steps, so the phase-survival factor is (1-q)^{m-1}, not (1-q)^{m-2}. The displayed bound is stronger by a factor (1-q); this does not change the asymptotic conclusions for the parameter regimes considered, but the computation should be corrected.
[Definition 2] Chains such as L_{d_ℓ} ≺ ... ≺ L_{d_{ℓ+1}} over decreasing indices are confusing; please state explicitly that the relation is applied to consecutive layers L_{h+1} ≺ L_h, so that the ONEMAX example is not read as contradictory.
[Throughout] The notation p,q = Θ(1/n log(n)) should be written with parentheses as Θ(1/(n log n)) to avoid ambiguity about the mode of convergence.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: runtime bounds are derived from the algorithm's definition and external drift/Wald tools; the unproved Lemma 6 is a completeness gap, not a circular step.

full rationale

I walked the derivation chain of Theorems 7 and 15. The positive results are obtained from the definition of the MMAHH, geometric phase-length computations (Lemmas 3 and 4), drift arguments (Lemmas 8-14), and external drift/Wald theorems (Theorems 17-19). The parameters p and q are algorithm settings chosen with the scaling Theta(1/(n log n)); their values are not fitted to data or to the claimed bound, so the runtime guarantees are derived, not predicted from fitted inputs. SEQOPT_k is defined as a benchmark class and then analyzed; this is not a renamed known result. Self-citations, in particular [Doerr et al., 2023a], are used only for motivation and for comparative statements about the earlier MAHH lower bound; the new proofs do not import any conclusion from that prior paper. The only load-bearing weakness is Lemma 6 (the one-phase approximation): it is stated without a rigorous proof, and Theorem 15 invokes it in both the base case and the induction step. That makes the main O(n^{k+1}/(d1...dk) log n) bound conditional on an unproved lemma, which is a correctness/completeness risk, not circularity. Lemma 6 is not the theorem's conclusion, is not a fitted quantity, and is not justified by citing the authors' own work as if it were an external result. I also note a separate consistency issue: the abstract says O(n^3 log n) independent of gap size, while Corollary 16 gives O(n^3/m log n) for Jump_m and O(n^3/d^2 log n) for Cliff_d; this is an exposition matter, not a circular-forcing step. Under the hard rules, no equation-level reduction or fitted-input-renamed-as-prediction is present, so the appropriate finding is no significant circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 3 invented entities

The central theorem relies on the unproved one-phase approximation and on the structural definition of SEQOPT_k. The algorithm parameters p and q are not fitted to data but are hand-chosen for the analysis. The OW operator and the new benchmark class are constructed within the paper, so they carry no external evidence.

free parameters (2)

p = Theta(1/(n log n))
Switching probability from OI to OW (or AM) in the Markov chain. Chosen by hand to balance phase length and success probability; not fitted to data.
q = Theta(1/(n log n))
Switching probability from OW (or AM) to OI. Chosen by hand to match the desired asymptotic regime.

assumptions (3)

ad hoc to paper Lemma 6 (one-phase approximation): reaching a neighboring local optimum from a local optimum takes O(1) phases on average
This is the backbone of the induction in Theorem 15, but it is stated without proof. The paper only provides a heuristic paragraph, making it an unproved assumption of the main result.
standard math Standard drift theorems (additive with overshooting, multiplicative) and Wald's equation
These are standard tools invoked in Sections 3-4 and in the appendices. They are not proved in the paper but are well-established.
domain assumption The benchmark functions are unitation-based and have monotone slopes between successive local optima (the defining property of SEQOPT_k)
The runtime analysis is restricted to the class SEQOPT_k, which generalizes Jump, Cliff, Trap, and OneMax. This structural assumption is used throughout the proofs.

invented entities (3)

Only-worsening (OW) acceptance operator
purpose: Accepts a new solution only if it is strictly worse, letting the search leave local optima quickly.
New operator introduced in this paper. Its utility is supported only by the runtime proofs here, with no external measurements or prior use.
SEQOPT_k benchmark class
purpose: A new family of pseudo-Boolean functions with k successive local optima, intended to unify Jump, Cliff, Trap, and OneMax.
Defined in the paper for the purpose of stating the general runtime theorem. No external validation exists.
Markov move-acceptance hyper-heuristic (MMAHH)
purpose: A variant of the move-acceptance hyper-heuristic that selects acceptance operators via a two-state Markov chain.
New algorithm variant introduced and analyzed in this paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator." pith.science (2026). https://pith.science/paper/76N3MIVN

@misc{pith2026250601107,
  author       = {Pith},
  title        = {Pith review of: Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/76N3MIVN}},
  note         = {Machine review of arXiv:2506.01107}
}

abstract

The move-acceptance hyper-heuristic was recently shown to be able to leave local optima with astonishing efficiency (Lissovoi et al., Artificial Intelligence (2023)). In this work, we propose two modifications to this algorithm that demonstrate impressive performances on a large class of benchmarks including the classic Cliff$_d$ and Jump$_m$ function classes. (i) Instead of randomly choosing between the only-improving and any-move acceptance operator, we take this choice via a simple two-state Markov chain. This modification alone reduces the runtime on Jump$_m$ functions with gap parameter $m$ from $\Omega(n^{2m-1})$ to $O(n^{m+1})$. (ii) We then replace the all-moves acceptance operator with the operator that only accepts worsenings. Such a, counter-intuitive, operator has not been used before in the literature. However, our proofs show that our only-worsening operator can greatly help in leaving local optima, reducing, e.g., the runtime on Jump functions to $O(n^3 \log n)$ independent of the gap size. In general, we prove a remarkably good runtime of $O(n^{k+1} \log n)$ for our Markov move-acceptance hyper-heuristic on all members of a new benchmark class SEQOPT$_k$, which contains a large number of functions having $k$ successive local optima, and which contains the commonly studied Jump$_m$ and Cliff$_d$ functions for $k=2$.

Figures

Figures reproduced from arXiv: 2506.01107 by the authors.

**Figure 1.** Transition probabilities between the two operators of the MMAHH, here OI and OW. 2.2 The Markov Move-Acceptance Hyper-Heuristic We now introduce a novel algorithm called the Markov MoveAcceptance Hyper-Heuristic algorithm (MMAHH). We recall that the Move-Acceptance Hyper-Heuristic algorithm (MAHH) first proposed in [Lehre and Ozcan, 2013 ¨ ] and then intensively studied in [Lissovoi et al., 2023] is a simple rand… view at source ↗

**Figure 2.** A generic setting, depicting the phases (red or blue), their length (Zk)k∈N, the switching times (T (k) s )k∈N and the stopping time T occurring during the phase k ∗ . We call T := inf{t ≥ 0 | xt = x ∗} the runtime, that is, the first time we reach the global maximum. Let T (k) s denotes the k-th switching time between the operators. Hence T (0) s = 0 and for any k ≥ 0, we have T (k+1) s = inf{t ≥ T (k) s | st ̸= s … view at source ↗

**Figure 3.** Illustration of a function f : {0, 1} n → R with a set of local maxima in layer Ldℓ where three kinds of excursions can occur: a failing left excursion in red, the right excursion that fails to reach Ldℓ+1 also in red and the successful one in green. confined in the slope [dℓ+1, dℓ] where f is decreasing across the layers Ldℓ , . . ., Ldℓ+1 , our one-phase approximation in Lemma 6 applies once more and gives, here … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Theory of Randomized Search Heuristics

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

work page 2011
[10]

Recent advances in selec- tion hyper-heuristics

[Drake et al., 2020] John Drake, Ahmed Kheiri, Ender ¨Ozcan, and Edmund Burke. Recent advances in selec- tion hyper-heuristics. European Journal of Operational Research, 285:405–428, 09

work page 2020
[11]

On the analysis of the (1+1) evolution- ary algorithm

[Droste et al., 2002] Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolution- ary algorithm. Theoretical Computer Science, 276:51–81,

work page 2002
[13]

[K¨otzing and Krejca, 2019] Timo K ¨otzing and Martin S. Krejca. First-hitting times under drift. Theoretical Com- puter Science, 796:51–69,

work page 2019
[15]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2019] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. On the time complexity of algorithm selection hyper-heuristics for multimodal opti- misation. In Conference on Artificial Intelligence, AAAI 2019, pages 2322–2329. AAAI Press,

work page 2019
[16]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2020] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. How the duration of the learning period affects the performance of random gradi- ent selection hyper-heuristics. In Conference on Artificial Intelligence, AAAI 2020 , pages 2376–2383. AAAI Press,

work page 2020
[17]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2023] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. When move acceptance se- lection hyper-heuristics outperform Metropolis and elitist evolutionary algorithms and when not. Artificial Intelli- gence, 314:103804,

work page 2023
[18]

Bioinspired Computation in Combinatorial Opti- mization – Algorithms and Their Computational Complex- ity

[Neumann and Witt, 2010] Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Opti- mization – Algorithms and Their Computational Complex- ity. Springer,

work page 2010

Show all 21 references

[21]

Theorem 17 (Simplified version of Wald’s equation – [Wald, 1944]; [Doerr and K ¨unnemann, 2015 ])

A Mathematical Tools The following theorem is used multiple times through the runtime analysis of the MMAHH to upper bound the expectation of a sum of random variables whose range also depends on a random variable. Theorem 17 (Simplified version of Wald’s equation – [Wald, 194...

1944
[1944]

Evolutionary Learning: Advances in Theories and Algo- rithms

[Zhou et al., 2019] Zhi-Hua Zhou, Yang Yu, and Chao Qian. Evolutionary Learning: Advances in Theories and Algo- rithms. Springer,

2019
[2000]

https://dlmf.nist.gov/, Release 1.2.3 of 2024-12-15

[DLMF, ] NIST Digital Library of Mathematical Func- tions. https://dlmf.nist.gov/, Release 1.2.3 of 2024-12-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V . Saunders, H. S. Cohl, and M. A. McClain, eds. [...

2024
[2002]

Analyzing Evolutionary Al- gorithms – The Computer Science Perspective

[Jansen, 2013] Thomas Jansen. Analyzing Evolutionary Al- gorithms – The Computer Science Perspective . Springer,

2013
[2010]

On cumulative sums of ran- dom variables

[Wald, 1944] Abraham Wald. On cumulative sums of ran- dom variables. Annals of Mathematical Statistics, 15:283– 296,

1944
[2011]

Burke, Michel Gendreau, Matthew R

[Burke et al., 2013] Edmund K. Burke, Michel Gendreau, Matthew R. Hyde, Graham Kendall, Gabriela Ochoa, En- der ¨Ozcan, and Rong Qu. Hyper-heuristics: a survey of the state of the art. Journal of the Operational Research Society, 64:1695–1724,

2013
[2012]

Oliveto, and John Alasdair Warwicker

[Doerr et al., 2018] Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In Genetic and Evolution- ary Computation Conference, GECCO 2018 , pages 1015–1022. ACM,

2018
[2013]

Cowling, Graham Kendall, and Eric Soubeiga

[Cowling et al., 2000] Peter I. Cowling, Graham Kendall, and Eric Soubeiga. A hyperheuristic approach to schedul- ing a sales summit. In Practice and Theory of Automated Timetabling, PATAT 2000, pages 176–190. Springer,

2000
[2015]

Theory of Evolutionary Computation— Recent Developments in Discrete Optimization

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

2020
[2018]

Lutzeyer, and Aur´elien Stumpf

[Doerr et al., 2023a] Benjamin Doerr, Arthur Dremaux, Jo- hannes F. Lutzeyer, and Aur´elien Stumpf. How the move acceptance hyper-heuristic copes with local optima: dras- tic differences between jumps and cliffs. In Genetic and Evolutionary Computation Conference, GECCO 2023 ,...

2023
[2019]

A runtime analysis of simple hyper-heuristics: to mix or not to mix operators

[Lehre and ¨Ozcan, 2013] Per Kristian Lehre and Ender ¨Ozcan. A runtime analysis of simple hyper-heuristics: to mix or not to mix operators. In Foundations of Genetic Algorithms, FOGA 2013, pages 97–104. ACM,

2013
[2020]

[Doerr et al., 2012] Benjamin Doerr, Daniel Johannsen, and Carola Winzen

Also available at http://www.lix.polytechnique.fr/ Labo/Benjamin.Doerr/doerr neumann book.html. [Doerr et al., 2012] Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorith- mica, 64:673–697,

2012
[2023]

How well does the Metropolis algorithm cope with local op- tima? In Genetic and Evolutionary Computation Con- ference, GECCO 2023, pages 1000–1008

[Doerr et al., 2023b] Benjamin Doerr, Taha El Ghazi El Houssaini, Amirhossein Rajabi, and Carsten Witt. How well does the Metropolis algorithm cope with local op- tima? In Genetic and Evolutionary Computation Con- ference, GECCO 2023, pages 1000–1008. ACM,

2023

Pith tools

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

[1] [1]

Theory of Randomized Search Heuristics

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

work page 2011

[2] [10]

Recent advances in selec- tion hyper-heuristics

[Drake et al., 2020] John Drake, Ahmed Kheiri, Ender ¨Ozcan, and Edmund Burke. Recent advances in selec- tion hyper-heuristics. European Journal of Operational Research, 285:405–428, 09

work page 2020

[3] [11]

On the analysis of the (1+1) evolution- ary algorithm

[Droste et al., 2002] Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolution- ary algorithm. Theoretical Computer Science, 276:51–81,

work page 2002

[4] [13]

[K¨otzing and Krejca, 2019] Timo K ¨otzing and Martin S. Krejca. First-hitting times under drift. Theoretical Com- puter Science, 796:51–69,

work page 2019

[5] [15]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2019] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. On the time complexity of algorithm selection hyper-heuristics for multimodal opti- misation. In Conference on Artificial Intelligence, AAAI 2019, pages 2322–2329. AAAI Press,

work page 2019

[6] [16]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2020] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. How the duration of the learning period affects the performance of random gradi- ent selection hyper-heuristics. In Conference on Artificial Intelligence, AAAI 2020 , pages 2376–2383. AAAI Press,

work page 2020

[7] [17]

Oliveto, and John Alasdair Warwicker

[Lissovoi et al., 2023] Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. When move acceptance se- lection hyper-heuristics outperform Metropolis and elitist evolutionary algorithms and when not. Artificial Intelli- gence, 314:103804,

work page 2023

[8] [18]

Bioinspired Computation in Combinatorial Opti- mization – Algorithms and Their Computational Complex- ity

[Neumann and Witt, 2010] Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Opti- mization – Algorithms and Their Computational Complex- ity. Springer,

work page 2010