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

Jun 11, 2026

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

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.

Joris Belder, Johannes Lengler, Raghu Raman Ravi

ETH Zürich, Switzerland

Evolutionary Optimization Black-Box Optimization Runtime Analysis of Evolutionary Algorithms

Ask PDF

Jun 11, 2026

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

We study the

(1 + 1)

-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of

1,2,4,\dots,2^{n-1}

, and a Uniform weight variant, where the weights are drawn independently from

\mathrm{Unif}(0,1)

. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter

χ

for mutation rate

χ/n

. Below the threshold, the expected optimisation time is

\mathcal{O}(n\log n)

, whereas above it the runtime becomes

2^{Ω(n)}

. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.

Georg Hasebe, Johannes Lengler, Raghu Raman Ravi

Eidgenössische Technische Hochschule Zürich, Switzerland

Evolutionary Optimization Black-Box Optimization Runtime Analysis of Evolutionary Algorithms

Ask PDF

Jul 15, 2026

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

The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory. We consider the family of Jump

_k

benchmark functions, defined on the search space of binary strings of length

n

, parametrized by the integer

k

, which have a plateau of multiple local optima at the Hamming distance

k

from a unique global optimum. In this work, we consider the genetic algorithm

(1+(λ,λ)) GA

from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate

p

, crossover bias

c

, and two intermediate population sizes

λ_M

and

λ_C

. We study the time it escapes from the plateau of local optima and reaches the global optimum in the case of Jump

_k

fitness function and tighten the upper bounds on the expected escape time, known from the work of Antipov, Doerr and Karavaev (2022). The obtained bounds also apply to a wider range of algorithmic parameters. The main result of this work applies to the case when

k\to \infty

n \to \infty.

The case of finite

k

is investigated quite simply and considered tangentially.

Anton V. Eremeev, Valentin A. Topchii

Runtime Analysis of Evolutionary Algorithms Genetic Algorithms

Ask PDF

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