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

2026-03-02 · Source: cs.NE updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, long

Summary

A new study introduces the HillPathJump fitness function to demonstrate that the optimal mutation rate for the $(1+1)$ Evolutionary Algorithm (EA) can be approximated by $c/n$ for any real number $c \geq 1$. Specifically, for every $c \geq 1$ and $\varepsilon>0$, a fitness function exists where the optimal mutation rate $p_n$ satisfies $|np_n-c|<\varepsilon$. This implies that the set of all $c \geq 1$ for which $c/n$ is an optimal mutation rate for the $(1+1)$ EA is dense in the interval $[1,\infty)$. The HillPathJump function is defined with a ZeroMax-like hill, a path constructed using an expanded Gray code, and a final jump of $k$ bits to the optimum $x^*$. The proof relies on analyzing the expected time to find the optimum and the probability of hitting $x^*$ before the second-highest fitness individual.

Key takeaway

For AI Researchers and AI Scientists designing or analyzing evolutionary algorithms, this work indicates that optimal static mutation rates for the $(1+1)$ EA are not confined to small integer multiples of $1/n$. You should consider a broader range of $c/n$ values, especially $c \geq 1$, when tuning mutation rates for complex, multi-modal fitness landscapes, as optimal performance may lie outside traditionally assumed ranges.

Key insights

Optimal mutation rates for the $(1+1)$ EA are dense in $[1,\infty)$ when scaled by $1/n$.

Principles

• Optimal mutation rates can exceed $1/n$ for functions with local optima.
• The HillPathJump function allows for tunable optimal mutation rates.

Method

The HillPathJump fitness function is constructed by combining ZeroMax, an expanded Gray code path, and a $k$-bit jump to the optimum, allowing for the demonstration of diverse optimal mutation rates.

In practice

• Consider mutation rates $c/n$ where $c>1$ for complex optimization landscapes.
• Explore fitness functions with "jumps" to test EA robustness.

Topics

• Evolutionary Algorithms
• Mutation Rates
• HillPathJump
• Algorithm Optimization
• Fitness Functions

Best for: AI Researcher, AI Scientist, Research Scientist

Related on AIssential

• Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions — Non-strict selection and incomplete training sets can significantly optimize Cartesian Genetic Programming's efficiency for Boolean function evolution.
• From Cooperation to Hierarchy: A Study of Dynamics of Hierarchy Emergence in a Multi-Agent System — Hierarchy emerges in multi-agent systems primarily driven by sufficient mutation amplitude, not initial heterogeneity.
• Controlled Self-Evolution for Algorithmic Code Optimization — Controlled Self-Evolution significantly boosts code optimization efficiency by guiding LLM-based iterative refinement.
• Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples — A new TD(0) convergence rate with LFA is fast, robust to ill-conditioning, and independent of the covariance matrix's smallest eigenvalue.
• Evolutionary Two-Stage Hyperparameter Optimization Strategies for Physics-Informed Neural Networks — Evolutionary two-stage hyperparameter optimization significantly enhances PINN accuracy and robustness under fixed computational budgets.
• Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity — Tight lower bounds for Byzantine-robust distributed stochastic optimization are established and matched by new methods.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.NE updates on arXiv.org.