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

• URL: http://arxiv.org/abs/2602.18989v1
• Date: Sun, 22 Feb 2026 00:30:45 GMT
• Title: All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm
• Authors: Andrew James Kelley,
• Abstract summary: For every mutation rate $p in (0, 1)$, there is a fitness function $f : 0,1n to mathbbR$ with a unique maximum for which the optimal mutation rate for the $(p-varepsilon, p+varepsilon)$ evolutionary algorithm on $f$ is in $(p-varepsilon, p+varepsilon)$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm [0.0]
  For every real number $c geq 1$ and for all $varepsilon > 0$, there is a fitness function $f : 0,1n to mathbbR$ for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$, denoted $p_n$, satisfies $p_n approx c/n$ in that $|np_n - c| varepsilon$.
  arXiv  Detail & Related papers  (2026-02-27T00:52:59Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity [1.8434042562191815]
  We show that population diversity in the $(mu+1)$-$lambda_c$-GA converges to an equilibrium of near-perfect diversity.<n>We also show that our analysis can be extended to other unitation functions such as JUMP$_k, delta$ and HURDLE.
  arXiv  Detail & Related papers  (2024-04-10T14:50:43Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
  We study the $(1,lambda)$-EA with mutation rate $c/n$ for $cle 1$, where the population size is adaptively controlled with the $(1:s+1)$-success rule. We show that this setup with $c=1$ is efficient on onemax for $s1$, but inefficient if $s ge 18$.
  arXiv  Detail & Related papers  (2022-04-01T15:46:12Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
  The (1+1)-evolution strategy (ES) with success-based step-size adaptation is analyzed on a general convex quadratic function. The convergence rate of the (1+1)-ES is derived explicitly and rigorously on a general convex quadratic function.
  arXiv  Detail & Related papers  (2021-03-02T09:03:44Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
  We extend the analysis of optimal mutation rates to two variants of the OneMax problem. We compute for all population sizes $lambda in 2i mid 0 le i le 18$ which mutation rates minimize the expected running time. Our results do not only provide a lower bound against which we can measure common evolutionary approaches.
  arXiv  Detail & Related papers  (2020-06-20T01:23:14Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.