[Paper] All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm

Source: arXiv - 2602.23573v1

Overview

This paper shows that for the classic (1+1) Evolutionary Algorithm (EA), the “optimal” mutation probability can be tuned to any value of the form (c/n) with (c \ge 1). In other words, by crafting a suitable fitness landscape (the authors call it HillPathJump), you can make the EA perform best when you set the mutation rate to essentially any constant (c) divided by the problem size (n). The result settles a long‑standing question about how flexible the optimal mutation rate really is.

Key Contributions

• Density result: Proves that the set of constants (c) for which the mutation rate (c/n) is optimal is dense in ([1,\infty)).
• Constructive example: Introduces the HillPathJump fitness function, a deliberately engineered landscape that forces the EA to prefer a specific mutation rate.
• Rigorous analysis: Provides a mathematical proof (using drift analysis and tail bounds) that the EA’s expected runtime is minimized exactly at the prescribed (c).
• General insight: Shows that the “one‑size‑fits‑all” belief (e.g., (1/n) is universally good) is false; optimal rates can be arbitrarily large depending on the problem structure.

Methodology

1. Design of HillPathJump:

   • The search space ({0,1}^n) is partitioned into a hill (a long monotone path of improving fitness) and a jump region (a set of high‑fitness points that can only be reached by flipping many bits at once).
   • The hill’s length and the jump’s distance are parameterized by the target constant (c).

2. Runtime analysis of the (1+1) EA:

   • The algorithm starts with a random bitstring and repeatedly creates an offspring by flipping each bit independently with probability (p).
   • Using drift analysis, the authors compute the expected time to climb the hill and to make the crucial jump.
   • They derive a closed‑form expression for the expected runtime as a function of (p) and show it is minimized when (p \approx c/n).

3. Density argument:

   • By varying the hill length and jump distance continuously, they can make the optimal constant (c) approach any desired value (\ge 1).
   • An (\varepsilon)-approximation argument guarantees that for any target (c) and tolerance (\varepsilon), a suitable HillPathJump instance exists.

Results & Findings

• Optimal mutation rate is not unique: For each constructed fitness function, the runtime curve (T(p)) has a single sharp minimum at (p_n = c/n).
• Dense set of optimal constants: The authors prove that for any (c \ge 1) and any tiny (\varepsilon > 0), there is a problem instance where the EA’s best mutation rate satisfies (|np_n - c| < \varepsilon).
• Implication for theory: This demonstrates that the classic “(1/n) is optimal for OneMax” result does not generalize to arbitrary problems; the optimal constant can be arbitrarily large.

Practical Implications

• Algorithm tuning: Practitioners should treat the mutation rate as a hyperparameter that may need to be significantly larger than (1/n) for certain rugged or deceptive problems.
• Automated parameter control: The result motivates adaptive schemes (e.g., self‑adjusting mutation rates, reinforcement‑learning‑based controllers) that can discover problem‑specific (c) values on the fly.
• Benchmark design: When evaluating EAs, including synthetic functions like HillPathJump can expose weaknesses in static mutation settings and help stress‑test adaptive mechanisms.
• Real‑world analogues: Problems with large plateaus or rare high‑payoff configurations (e.g., combinatorial optimization, neural architecture search) may benefit from higher mutation probabilities to “jump” out of local basins.

Limitations & Future Work

• Constructed rather than natural: HillPathJump is a deliberately engineered worst‑case landscape; the paper does not claim that many real‑world problems naturally exhibit the same behavior.
• Focus on (1+1) EA: Results are specific to the simple (1+1) scheme; extending the analysis to populations, crossover, or other selection mechanisms remains open.
• Scalability of analysis: The proof relies on precise control of hill length and jump distance, which may be hard to translate into practical guidelines for large‑scale problems.
• Future directions: Investigating whether similar density results hold for other mutation operators (e.g., heavy‑tailed distributions) or for dynamic environments, and developing practical adaptive controllers that can approximate the optimal (c) on the fly.

Authors

• Andrew James Kelley

Paper Information

• arXiv ID: 2602.23573v1
• Categories: cs.NE
• Published: February 27, 2026
• PDF: Download PDF