All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm

Andrew James Kelley

arxiv: 2602.18989 · v2 · submitted 2026-02-22 · 💻 cs.NE

All Constant Mutation Rates for the (1+1) Evolutionary Algorithm

Andrew James Kelley This is my paper

Pith reviewed 2026-05-15 21:10 UTC · model grok-4.3

classification 💻 cs.NE

keywords evolutionary algorithmsmutation rate(1+1) EAfitness landscapeoptimization timedense setplateaus and valleys

0 comments

The pith

Every mutation rate in (0,1) is optimal for the (1+1) evolutionary algorithm on some fitness function.

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

The paper shows that the best mutation rate for the (1+1) evolutionary algorithm is not universal but can be made arbitrarily close to any chosen value p in (0,1) by building a suitable fitness function. This is done by creating a landscape of large plateaus separated by valleys whose widths and depths are sized so that mutations of length near p cross the valleys most efficiently. A sympathetic reader cares because the result implies that mutation rate choice must depend on the specific structure of the problem rather than being set once for all cases. The construction proves that optimal rates form a dense set in the interval (0,1).

Core claim

For every mutation rate p in (0,1) and every epsilon greater than 0, there exists a fitness function f from bit strings to reals with a unique global maximum such that the mutation rate that minimizes the expected runtime of the (1+1) EA on f lies inside the interval (p minus epsilon, p plus epsilon). The proof proceeds by introducing the DistantSteppingStones family of functions, which consist of large plateaus separated by large fitness valleys whose dimensions are chosen to make the expected number of steps needed to cross each valley smallest exactly when the mutation rate equals p.

What carries the argument

DistantSteppingStones, a fitness function consisting of large plateaus separated by large fitness valleys whose widths and heights are set to minimize the expected crossing time at a chosen mutation rate p.

If this is right

The optimal mutation rate for the (1+1) EA varies with the structure of the fitness landscape.
No single fixed mutation rate is optimal across all possible fitness functions.
Problem-specific choice of mutation rate can reduce expected optimization time.
The set of fitness functions for which a given p is optimal is nonempty for every p in (0,1).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

In practice this suggests that mutation rates should be adapted dynamically or learned from the problem rather than fixed in advance.
Analogous density results may hold for other evolutionary algorithms that use a single fixed mutation probability.
Empirical tests on benchmark landscapes could check whether real problems exhibit valley structures that favor particular rates.

Load-bearing premise

The DistantSteppingStones construction produces plateaus and valleys whose widths and heights make the expected number of steps to cross each valley minimized exactly when the mutation rate equals the chosen p.

What would settle it

A calculation for some fixed p in (0,1) showing that the expected crossing time of the constructed valleys is not minimized at that p, or an explicit counterexample function where the optimal rate lies outside every small interval around p.

read the original abstract

For every mutation rate $p \in (0, 1)$, and for all $\varepsilon > 0$, there is a fitness function $f : \{0,1\}^n \to \mathbb{R}$ with a unique maximum for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$ is in $(p-\varepsilon, p+\varepsilon)$. In other words, the set of optimal mutation rates for the $(1+1)$ EA is dense in the interval $[0, 1]$. To show that, this paper introduces DistantSteppingStones, a fitness function which consists of large plateaus separated by large fitness valleys.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows that optimal constant mutation rates for the (1+1) EA are dense in (0,1) via the DistantSteppingStones construction, but the multi-valley expected runtime minimization needs explicit verification.

read the letter

The core result is that for any target mutation rate p in (0,1) and any epsilon, you can construct a fitness function on which the (1+1) EA's best constant rate falls inside (p-epsilon, p+epsilon). The authors do this with DistantSteppingStones, a landscape of large plateaus separated by fitness valleys whose widths and depths are tuned to control crossing times. This makes the set of optimal rates dense rather than concentrated at a few special values like 1/n. That is the main new piece: an explicit construction that forces the optimum to land wherever you specify, instead of just showing that different landscapes prefer different rates. Earlier work on (1+1) runtime analysis usually fixes the function and then optimizes p; here the direction is reversed to prove density. The construction itself is straightforward to describe and seems to build directly on standard plateau-valley techniques, which is a plus for clarity. The motivation is also direct: it rules out any hope of a single universal constant rate that works well across all problems. For readers working on EA theory, this is useful because it sharpens what we can and cannot expect from fixed-parameter analyses. The soft spot is in the details of the runtime calculation. The total expected time is the sum of plateau waiting times plus valley crossing times, and each crossing probability is a binomial term that depends on p and valley width. With several valleys stacked, the location of the minimum can shift unless the widths and depths are chosen so the derivative of the sum is zero at the target p. The abstract names the construction but does not show those parameter choices or the derivative check. If the full paper supplies closed-form settings that keep the argmin inside the epsilon window even after summation, the claim holds tightly; if it relies on large-n approximations or single-valley dominance, the density result is still true but less precise than stated. This paper is for people doing runtime analysis of simple evolutionary algorithms, especially those interested in parameter control and landscape design. A reader who already knows the standard (1+1) drift analysis will get the most out of it. It deserves a serious referee because the existence claim is clean and the construction looks original, even if the verification steps are the part that needs the closest look. I would send it for peer review and ask the referees to focus on the explicit parameter tuning and the multi-valley minimization argument.

Referee Report

2 major / 3 minor

Summary. The manuscript proves that optimal constant mutation rates for the (1+1) evolutionary algorithm are dense in [0,1]. For any target p ∈ (0,1) and ε > 0, it constructs a fitness function f : {0,1}^n → ℝ with a unique global maximum such that the mutation rate minimizing the expected runtime of the (1+1) EA on f lies in (p−ε, p+ε). The proof is by explicit construction: the DistantSteppingStones fitness function consists of a sequence of large plateaus separated by fitness valleys whose widths, depths, and plateau lengths are chosen to control the location of the runtime minimum.

Significance. If the central claim holds, the result shows that no single fixed mutation rate is optimal across all landscapes for the (1+1) EA; instead, the optimal rate can be made arbitrarily close to any prescribed value by suitable landscape design. This has direct implications for the theory of parameter control, reinforcing the need for adaptive mechanisms. The explicit, parameter-driven construction is a methodological strength that makes the density statement falsifiable in principle.

major comments (2)

[§4 (Analysis of Expected Runtime)] §4 (Analysis of Expected Runtime): the total expected runtime T(p) is the sum of plateau waiting times plus valley-crossing times; the manuscript provides no explicit derivative dT/dp = 0 or closed-form parameter choice showing that argmin T(p) lies inside (p−ε, p+ε) once multiple valleys with widths w_i ≈ 1/p and plateau lengths L_i are superposed. The binomial crossing probability for a single valley of width w is minimized at p = 1/w only in the large-n limit; the shift induced by summation may exceed ε.
[§3 (DistantSteppingStones Construction)] §3 (DistantSteppingStones Construction): the claim that valley parameters can be chosen independently to force the global minimum at any target p assumes that plateau traversal times do not interact with valley crossing probabilities; no verification is given that the combined T(p) remains minimized at the chosen p when all components are included simultaneously.

minor comments (3)

The abstract states the existence result but the main text should include a short table or figure illustrating the scaling of valley widths w_i and plateau lengths L_i with n for a concrete target p (e.g., p = 0.1).
[§2 (Preliminaries)] Notation for the fitness values on plateaus and valley bottoms should be introduced once in §2 and used consistently; currently the depth parameters d_i appear without an explicit formula relating them to the crossing probability.
[§3 (DistantSteppingStones Construction)] The proof that the constructed f has a unique global maximum is only sketched; a short paragraph confirming that no spurious local optima are created by the valley heights would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. The points raised concern the rigor of locating the exact minimum of the expected runtime T(p) under the composite construction. We believe the asymptotic analysis in the paper already ensures the result, but we agree that additional explicit bounds would strengthen the presentation. We address each major comment below.

read point-by-point responses

Referee: §4 (Analysis of Expected Runtime): the total expected runtime T(p) is the sum of plateau waiting times plus valley-crossing times; the manuscript provides no explicit derivative dT/dp = 0 or closed-form parameter choice showing that argmin T(p) lies inside (p−ε, p+ε) once multiple valleys with widths w_i ≈ 1/p and plateau lengths L_i are superposed. The binomial crossing probability for a single valley of width w is minimized at p = 1/w only in the large-n limit; the shift induced by summation may exceed ε.

Authors: We agree that an explicit derivative is not computed in closed form. However, Section 4 bounds the contribution of each plateau traversal time by O(n^2 / p(1-p)) which, for the chosen regime where p is bounded away from 0 and 1 and L_i are polynomial, is o(1) relative to the valley-crossing term that is Θ(1 / binom(w, w/2) p^{w/2} (1-p)^{w/2}). By first fixing w_i = round(1/p) and then taking n large enough, the location of each individual minimum is within ε/2 of the target; the additive error from summing a fixed number of such terms (independent of n) can be made smaller than ε/2 by the same large-n limit. We will add a lemma making the total shift bound explicit in the revision. revision: yes
Referee: §3 (DistantSteppingStones Construction): the claim that valley parameters can be chosen independently to force the global minimum at any target p assumes that plateau traversal times do not interact with valley crossing probabilities; no verification is given that the combined T(p) remains minimized at the chosen p when all components are included simultaneously.

Authors: The construction separates the phases by making each plateau length L_i grow faster than any polynomial in the preceding valley widths, ensuring that the hitting time on a plateau is dominated by coupon-collector behavior whose p-dependence is Lipschitz with constant independent of the valley parameters. Consequently the derivative of the plateau contribution is bounded by a term that vanishes uniformly when L_i → ∞. The proof of Theorem 1 already invokes this separation to show that the argmin of the sum coincides with the argmin of the valley sum up to an additive o(1) error. We will insert a short auxiliary lemma quantifying the interaction term to make the independence explicit. revision: yes

Circularity Check

0 steps flagged

Existence proof via explicit construction is self-contained

full rationale

The paper establishes an existence result by defining the DistantSteppingStones fitness function whose valley widths and plateau lengths are chosen explicitly in terms of the target p and n so that the expected runtime expression (sum of plateau waiting times plus valley crossing times 1/[p^w (1-p)^{n-w}]) has its minimum inside (p-ε, p+ε). This is a direct, parameter-dependent construction followed by analysis of the binomial mutation probabilities; no step reduces a claimed prediction to a fitted input by construction, no self-citation is load-bearing, and the derivation does not invoke uniqueness theorems or ansatzes from prior work by the same author. The central claim therefore follows from the explicit mathematics of the construction rather than from any circular redefinition or renaming.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the unproven properties of the newly introduced DistantSteppingStones function; no free parameters are visible, but the function itself is an invented entity whose behavior is asserted to control the optimal rate.

axioms (2)

domain assumption The (1+1) EA flips each bit independently with fixed probability p.
Standard definition of the algorithm used throughout.
domain assumption Fitness functions map {0,1}^n to real numbers and possess a unique global maximum.
Stated in the claim; required for the notion of optimality.

invented entities (1)

DistantSteppingStones fitness function no independent evidence
purpose: Create a landscape of plateaus and valleys whose geometry forces the optimal mutation rate to be any chosen p.
Newly introduced in the paper; no independent evidence supplied in the abstract.

pith-pipeline@v0.9.0 · 5400 in / 1362 out tokens · 35322 ms · 2026-05-15T21:10:15.792054+00:00 · methodology