Anytime Analysis on BinVal: Adaptive Parameters Help

Timo Kötzing; Jurek Sander

cs.NEApr 8, 2026

Anytime Analysis on BinVal: Adaptive Parameters Help

Authors: Timo Kötzing, Jurek Sander

Organizations: Hasso Plattner Institute University of Potsdam Potsdam, Germany

Abstract

While most theoretical run time analyses of discrete randomized search heuristics provide bounds on the expected number of evaluations to find the global optimum, we consider the anytime performance of evolutionary and estimation-of-distribution algorithms. For this purpose, we analyze the fixed-target run time of various algorithms using BinVal as fitness function and bound the run time to optimize the most significant $k \in o(n)$ bits of a bit string with length $n$ . We analyze the run times such that they hold not only for a fixed $k$ , but simultaneously for all $k \in o(n)$ . For the standard (1+1) EA with fixed mutation rate $1/n$ , we show that the fixed-target run time for all $k \in o(n)$ is in $Θ(n \log k)$ . Using an EDA instead, we get an expected number of evaluations of $Θ(k \log n)$ for the sig-cGA. Replacing in the standard (1+1) EA the fixed mutation rate with a self-adjusting rate, we show that the fixed-target run time for $k \in o(n)$ and a constant $\varepsilon >0$ arbitrarily close to zero is in $\mathcal{O}\left(k^{1+\varepsilon}\right)$ for this algorithm. In particular, this run time is independent of $n$ , holds simultaneously for all $k \in o(n)$ , and is close to the run time of $Θ(k \log k)$ for the (1+1) EA with the best fixed mutation rate if $k$ is known.

Figures & tables

Randomized search heuristic	Lower Bound		Upper Bound
(1+1) EA with $\chi=1/n$	$\Omega\left(n\log k\right)$	( Witt, 2013 , Cor. 6.6)	$\mathcal{O}\left(n\log k\right)$	( Witt, 2013 , Cor. 4.2)
(1+1) EA with $\chi=c/n$ , $c>0$ , $k\leq n/c$	$\Omega\left(\frac{n\log k}{c}\right)$	( Witt, 2013 , Cor. 6.6)	$\mathcal{O}\left(\frac{n\log k}{c}\right)$	( Witt, 2013 , Cor. 4.2)
(1+1) EA with $0<\chi<1/2$ , $k\leq 1/\chi$	$\Omega\left(\frac{\log k}{\chi}\right)$	( Witt, 2013 , Cor. 6.6)	$\mathcal{O}\left(\frac{\log k}{\chi}\right)$	( Witt, 2013 , Cor. 4.2)
sig-cGA	$\Omega\left(k\log n\right)$	[Lem. 4.4 ]	$\mathcal{O}(k\log n)$	[Cor. 4.2 ]
sig-cGA with $s(\varepsilon,\mu)=\varepsilon\max\left\{\sqrt{\mu\ln\tilde{k}},\ln\tilde{k}\right\}$ , $k\leq\tilde{k}$	$\Omega\left(k\log\tilde{k}\right)$	[Cor. 4.5 ]	$\mathcal{O}\left(k\log\tilde{k}\right)$	[Cor. 4.3 ]
(1+1) EA with adjusting MR	$\Omega(k\log k)$	[Cor. 5.3 ]	$\mathcal{O}(k\log k)$	[Thm. 5.2 ]

Figure 1. Bounds of the fixed-target run time for the most significant

k\in o(n)

bits simultaneously for different randomized search heuristics on the BinVal function. All Landau notations depend only on the bit length

n\in\mathbb{N}

and the number

k

of the most significant bits that should be optimized.

\gamma

is a fixed constant and

\varepsilon>0

can be chosen arbitrarily close to zero. Overview of fixed-target run time results. Overview of the fixed-target run time results of all analyzed \EAvariants and the sig-cGA.

Figure 2. Comparison of the standard (1+1) EA, the (1+1) EA with adjusting mutation rate and the (1+1) EA with self-adjusting mutation rate. The number of iterations to optimize the first $k$ leading bits. (1+1) EA with adjusting and self-adjusting mutation rate outperforms (1+1) EA for $k\in o(n)$ . Smaller number of iterations to optimize the first $k\ino(n)$ for the \EAwith adjusting and self-adjusting mutation rate in comparison to the standard \EA.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3. The number of leading bits in relation to $n$ until the (1+1) EA with self-adjusting mutation rate requires fewer iterations to optimize them than the standard (1+1) EA. Note that the $x$ -axis is logarithmically scaled. Constant relative turning point of (1+1) EA and (1+1) EA with self-adjusting mutation rate. For an increasing number of $n$, the relative number of leading bits that the \EAwith self-adjusting mutation rate optimizes faster than the \EAstays constant. — Figure 3. The number of leading bits in relation to $n$ until the (1+1) EA with self-adjusting mutation rate requires fewer iterations to optimize them than the standard (1+1) EA. Note that the $x$ -axis is logarithmically scaled. Constant relative turning point of (1+1) EA and (1+1) EA with self-adjusting mutation rate. For an increasing number of $n$ , the relative number of leading bits that the \EAwith self-adjusting mutation rate optimizes faster than the \EAstays constant.

Figure 4. Comparison of the standard (1+1) EA (dashed lines) and the (1+1) EA with self-adjusting mutation rate (solid lines). For different $k$ , we record the number of iterations until the first $k$ bits are optimized for different $n$ . Each line represents a combination of a $k$ and an algorithm. Note that both axes are logarithmically scaled. (1+1) EA with self-adjusting mutation rate optimizes first $k\in o(n)$ independent of $n$ . Comparison for fixed values of $k \ino(n)$. \EAwith self-adjusting mutation rate optimizes them independently of $n$, for \EAit clearly depends on $n$. — Figure 4. Comparison of the standard (1+1) EA (dashed lines) and the (1+1) EA with self-adjusting mutation rate (solid lines). For different $k$ , we record the number of iterations until the first $k$ bits are optimized for different $n$ . Each line represents a combination of a $k$ and an algorithm. Note that both axes are logarithmically scaled. (1+1) EA with self-adjusting mutation rate optimizes first $k\in o(n)$ independent of $n$ . Comparison for fixed values of $k \ino(n)$ . \EAwith self-adjusting mutation rate optimizes them independently of $n$ , for \EAit clearly depends on $n$ .

Runtime Analysis of Evolutionary Algorithms

Runtime analysis of evolutionary algorithms studies how long population-based randomized search methods take to optimize specified fitness functions.

See all 33 papers

Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
Jun 11, 2026Joris Belder, Johannes Lengler, Raghu Raman RaviEvolutionary Optimization Black-Box Optimization
ETH Zürich, Switzerland
The $(1 + 1)$ -EA in Dynamic Environments
Jun 11, 2026Georg Hasebe, Johannes Lengler, Raghu Raman RaviEvolutionary Optimization Black-Box Optimization
Eidgenössische Technische Hochschule Zürich, Switzerland
Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions
Jul 15, 2026Anton V. Eremeev, Valentin A. TopchiiRuntime Analysis of Evolutionary Algorithms Genetic Algorithms

Jun 11, 2026J/K move · Enter open · S save

Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal

Joris Belder, Johannes Lengler, Raghu Raman Ravi

ETH Zürich, Switzerland

Evolutionary Optimization Black-Box Optimization Runtime Analysis of Evolutionary Algorithms

Open paper AskPDF arXiv

We study the

(μ+1)

EA on the Binary Value function BinVal. We show that it needs at most

O(μ\log μ\cdot n \log n)

function evaluations to find the optimum when

μ= o(n/\log n)

. This substantially improves upon the recent upper bound of

O(μ^5 n \log(n/μ^4))

by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the

(μ+1)

EA is at most a factor

O(\log μ\cdot \log n)

slower on BinVal than on OneMax.

Abstract

Runtime Analysis of Evolutionary Algorithms

Explore similar work

Improved Runtime Bound for the (μ+1)(μ+ 1)(μ+1) EA on BinVal

The (1+1)(1 + 1)(1+1)-EA in Dynamic Environments

Asymptotical Analysis of the (1+(λ,λ))(1+(λ,λ))(1+(λ,λ)) GA Escape Time from Local Optima on Jump Functions

Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal

The $(1 + 1)$ -EA in Dynamic Environments

Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions