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

For the (1+1) evolutionary algorithm with standard bit mutation, we study the sensitivity of the expected hitting time $H_p=\mathbb{E}_x T$ to the mutation rate. We first point out an easily overlooked formalization pitfall: the improvement event is not monotone in the mutation mask, so the unsigned (total-influence) form of the Margulis-Russo formula does not apply; the correct object is the signed endpoint difference. Second, we give an exact three-dimensional separation: two fitness functions share the entire one-step success-rate curve, yet their expected hitting times are two different exact rational numbers; hence one-step success-rate quantities do not determine the expected hitting time. Building on the runtime derivative $H'_p=(I-Q_p)^{-1}Q'_p H_p$, we construct computable double-residual sign certificates, prove a per-initial-state sign theorem on OneMax (for every non-optimal initial state, $\partial_c H<0$ on $0<c<1$, where $p=c/n$; at $c=1$ only the distance-one state is stationary), and extend the framework to non-lumpable positive linear families: an explicit non-lumpability witness, a block-interval double-residual certificate that covers all states without enumerating them, a uniform sign bound $\partial_c\mathbb{E}T\le -9n/16$ over the whole interval $c\in[1/4,1/2]$ for an explicit family at all even scales $n\ge 8$, and a heterogeneous instance certificate $H'_x\le -1/6$ on 57 of 63 states across $c=1$. All finite verifications use exact rational arithmetic. A bounded systematic literature search did not uncover this exact combination, although the underlying tools are well established; we therefore make no novelty claim beyond the stated combination.

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.

Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G-OneMax$\colon \{0,\dots,r-1\}^n \to \mathbf{N}$ defined by G-OneMax$(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i$ and truly depending on all $r$ categories. We improve their runtime result from $\textrm{O}\bigl(n r^3 \log^2( n)\log (r)\bigr)$ to $\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr)$, both for an optimal choice of the update strength $K$. Our result matches, up to polylogarithmic factors, the existing bound for the simpler $r$-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the $r$-valued frequency matrix.