Paper deep dive
When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
Denis Antipov, Carola Doerr
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/10/2026, 4:04:09 AM
Summary
This paper provides the first theoretical proof that Online Algorithm Selection (OAS) can yield asymptotic speedups in evolutionary computation. By switching between the (1+λ) EA and the (1+(λ,λ)) GA, the authors demonstrate an O(n log log n) runtime on the OneMax problem, which is faster than either algorithm used in isolation. The study includes both an idealized switching rule based on distance to the optimum and a realistic, budget-based switching mechanism.
Entities (6)
Relation Signals (2)
Online Algorithm Selection → optimizes → OneMax
confidence 95% · OAS approach allows to find the optimum of OneMax in O(n log log n) fitness evaluations.
(1+λ) EA → switchesto → (1+(λ,λ)) GA
confidence 95% · switching between two algorithms -- the (1+λ) EA and the (1+(λ,λ)) GA -- solves the OneMax problem asymptotically faster
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from some artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing. In this paper, we present the first theoretical example in which switching between two algorithms -- the $(1+\lambda)$ EA and the $(1+(\lambda,\lambda))$ GA -- solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in $O(n\log\log n)$ expected time, faster than the $\Theta(n\sqrt{\frac{\log n \log\log\log n}{\log\log n}})$ runtime of the best of these two algorithms with optimally tuned parameters. We first establish this bound under an idealized switching rule that changes from the $(1+\lambda)$ to the $(1+(\lambda,\lambda))$ GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS.
Tags
Links
- Source: https://arxiv.org/abs/2604.07473v1
- Canonical: https://arxiv.org/abs/2604.07473v1
Trouble viewing inline? Open PDF directly →
Full Text
66,546 characters extracted from source content.
Expand or collapse full text
by When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection Denis Antipov 0000-0001-7906-096X Sorbonne Université, CNRS, LIP6ParisFrance denis.antipov@lip6.fr and Carola Doerr 0000-0002-4981-3227 Sorbonne Université, CNRS, LIP6ParisFrance carola.doerr@lip6.fr (2026) Abstract. Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from some artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing. In this paper, we present the first theoretical example in which switching between two algorithms—the (1+λ)(1+λ) EA and the (1+(λ,λ))(1+(λ,λ)) GA—solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in O(nloglogn)O(n n) expected time, faster than the Θ(nlognlogloglognloglogn) (n n n n) runtime of the best of these two algorithms with optimally tuned parameters. We first establish this bound under an idealized switching rule that changes from the (1+λ)(1+λ) to the (1+(λ,λ))(1+(λ,λ)) GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS. Evolutionary algorithms, Online algorithm selection, Theory, Runtime analysis †journalyear: 2026†copyright: c†conference: Genetic and Evolutionary Computation Conference; July 13–17, 2026; San Jose, Costa Rica†booktitle: Genetic and Evolutionary Computation Conference (GECCO ’26), July 13–17, 2026, San Jose, Costa Rica†doi: 10.1145/3795095.3805156†isbn: 979-8-4007-2487-9/2026/07†ccs: Theory of computation Theory of randomized search heuristics†ccs: Theory of computation Random search heuristics†ccs: Theory of computation Evolutionary algorithms†ccs: Computing methodologies Genetic algorithms 1. Introduction Online algorithm selection (OAS for brevity) is an approach to optimization based on switching between several optimization algorithms from a pre-defined portfolio in order to maximize the performance.111OAS is sometimes referred to as dynamic algorithm selection (dynAS), but we prefer to use different notation to avoid confusion with dynamic algorithm configuration (DAC) that involves some learning prior to running an algorithm. This approach is especially helpful for iterative random search heuristics such as evolutionary algorithms (EAs), since it is easy to switch from one algorithm to another between iterations (Vermetten et al., 2020; Kostovska et al., 2022; Vermetten et al., 2023). The ultimate goal of OAS is to always use the algorithm that yields the fastest progress at each stage of optimization, since it must outperform all algorithms from the portfolio. The main challenge of OAS lies in designing effective switching strategies. This includes detecting when the currently employed algorithm ceases to be effective and determining which algorithm from the portfolio is best suited to continue the search. In practice, these challenges are typically addressed using learning-based techniques. However, any theory-based guidelines on the how to switch between algorithms in OAS settings are still largely missing. The closest area to OAS that theory of evolutionary computation has studied before is the hyper-heuristics (HHs). HHs are usually embedded into EAs to select one or more of its components in each iteration. This includes HHs that select the operator to create offspring (Alanazi and Lehre, 2014; Lissovoi et al., 2017; Doerr et al., 2018; Lissovoi et al., 2020), parent selection strategy (Corus et al., 2025) or offspring selection strategy (Lissovoi et al., 2023; Bendahi et al., 2025). Most HHs use a simple strategy to switch between low-level heuristics, such as iteration through their portfolio in randomly shuffled order, using each heuristic from portfolio as long as it is successful, etc. Some of them involve more complex mechanisms, for example, they use a heuristic for some time τ to learn its usefulness (Doerr et al., 2018) or use a Markov chain to transition between different heuristics (Bendahi et al., 2025). The latter two HHs are very close to OAS, where the goal is to learn the usefulness of each algorithm from the portfolio and to switch between them at the best moments. Our results. In this paper, we address the lack of theoretical foundations for OAS by performing runtime analysis of an OAS algorithm that can switch between the (1+λ)(1+λ) EA and the (1+(λ,λ))(1+(λ,λ)) GA. The idea of such portfolio is inspired by the recent result of Antipov et al. (2025) who showed that the (1+(λ,λ))(1+(λ,λ)) GA is much more efficient in the late stages of optimization on OneMax than any mutation-only EA and that unlike them it does not encounter the coupon collector effect to the same extent. At the same time, in early stages of optimization the (1+(λ,λ))(1+(λ,λ)) GA wastes too many fitness evaluations on just a small progress that can be achieved with mutation. This implies that it makes sense to use the (1+λ)(1+λ) EA (or even the (1+1)(1+1) EA) in early stages of optimization, and switch to the (1+(λ,λ))(1+(λ,λ)) GA later. We show that this OAS approach allows to find the optimum of OneMax in O(nloglogn)O(n n) fitness evaluations. This is asymptotically faster than the Ω(nlogn) (n n) bound of all mutation-only EAs (Lehre and Witt, 2012) and Θ(nlognlogloglognloglogn) (n n n n) runtime of the (1+(λ,λ))(1+(λ,λ)) GA with the best static parameters (Doerr and Doerr, 2018). This is the first proven example of OAS, where we observe that switching between two different algorithms brings performance that is asymptotically better than the performance of the best of these two algorithms. We first prove this runtime bound for the algorithm that knows its distance from the optimum and can decide to switch based on this information. Interestingly, the range of distances at which it can switch to achieve the optimal runtime is quite large, namely it spreads over Θ(n(loglogn)2logn) ( n( n)^2 n) different distances, which gives the OAS algorithm a lot of freedom to decide when to do it. To prove this result, we use the fixed-start analysis results for the (1+(λ,λ))(1+(λ,λ)) GA from (Antipov et al., 2025), and also provide the fixed-target bounds for the (1+λ)(1+λ) EA. Since in practice it is not realistic to have access to the current distance to the optimum, we provide a mechanism that detects the optimal time to switch from the (1+1)(1+1) EA to the (1+(λ,λ))(1+(λ,λ)) GA. This mechanism is based on the budget requirements of these algorithms, and it decides to switch when the (1+1)(1+1) EA needs more fitness evaluations to get progress than it takes to run one iteration of the (1+(λ,λ))(1+(λ,λ)) GA. We show that the OAS algorithm that embeds this mechanism is also capable of solving OneMax in O(nloglogn)O(n n) time. To address the vague borderline between OAS and HHs, we also propose an H that in each iteration decides whether it should perform an iteration of the (1+1)(1+1) EA or of the (1+(λ,λ))(1+(λ,λ)) GA. This can be considered as a choice between two operators that create offspring, but more complicated than in previous studies of HHs. We propose a strategy of how the H can make this choice that is based on balancing the computation budget between the (1+1)(1+1) EA and the (1+(λ,λ))(1+(λ,λ)) GA, and we show that this H can also achieve O(nloglogn)O(n n) runtime. Apart from the result for the artificial GapPath function from (Lehre and Özcan, 2013; Lissovoi et al., 2017), this is the first example when an H that chooses operators to create an offspring has an asymptotical speed-up compared to the low-level heuristics it uses. Synopsis. The rest of the paper is organized as follows. In Section 2, we formally define the problem and the algorithms we analyze. In Section 3, we provide fixed-target results for the (1+λ)(1+λ) EA that help us in our analysis. Then we perform runtime analysis of an OAS that has access to the distance to the optimum in Section 4, and propose a switching mechanism that is independent of this distance in Section 5, where we also show that this mechanism has asymptotically the same performance. We translate our results into hyper-heuristics domain in Section 6. We conclude the paper with a short discussion. 2. Preliminaries 2.1. Online Algorithm Selection Formally, online algorithm selection can be defined as a technique of running several algorithms sequentially, where each algorithm is chosen based on the information obtained by the previous algorithms, and this information is also passed to the algorithm. In the context of evolutionary optimization, this information is usually passed through the population of solutions, so that each next algorithm is initialized with the final population of the previous one. In this paper, we consider EAs with a trivial population, that is, population that consists of a single individual. In this setting, a switch to another algorithm can be done after any iteration, and the algorithm selector can be described by the pseudocode in Algorithm 1. 1x′←x ← random solution from the search space; 2 while not terminated do 3 Select algorithm A from portfolio A; 4 Initialize A with x′x ; 5 Run A optimizing function f until some stopping criterion; 6 x′←x ← best solution found by A; 7 8 end while Algorithm 1 An OAS algorithm optimizing function f. We note that in this pseudocode we do not specify multiple details. First, we do not specify the stopping criterion for the algorithm selector, which is typical for most runtime analysis results, but we assume that this stopping criterion is not satisfied before the algorithm finds the optimum. Second, we do not specify neither how we select algorithms, nor how we stop them, which will be discussed in the later sections. 2.2. Available Algorithms In this subsection, we describe the algorithms which we are allowed to choose from in the algorithm selector. All these algorithms are designed for pseudo-Boolean optimization, that is, the search space is 0,1n\0,1\^n—the set of bit strings of length n (n is the problem size). The first algorithm is the (1+λ)(1+λ) EA, where λ is an integer parameter. The algorithm stores one individual x (which is initialized with x′x in the algorithm selector, see line 1 in Algorithm 1). In each iteration it independently generates λ individuals (where λ is a fixed parameter of the algorithm), each by creating a copy of x and independently flipping each bit in it with probability 1/n1/n (this variation operator is called standard bit mutation). The (1+λ)(1+λ) EA then selects an offspring y with the best fitness (the value of the optimized function) among the λ offspring, breaking ties in an arbitrary way (for example, uniformly at random). If the selected offspring y is not worse than its parent x, it replaces the parent. One iteration of this algorithm costs λ fitness evaluations. A pseudocode of this algorithm for maximization is shown in Algorithm 2. 1input: individual x; 2 while not terminated do 3 for i∈[1..λ]i∈[1..λ] do 4 yi←y_i← copy of x; 5 Independently flip each bit in yiy_i with prob. 1/n1/n; 6 7 end for 8 y←argmaxz∈y1,…,yλf(z)y← *arg\,max_z∈\y_1,…,y_λ\f(z); 9 if f(y)≥f(x)f(y)≥ f(x) then 10 x←yx← y; 11 12 end if 13 14 end while 15return x; Algorithm 2 The (1+λ)(1+λ) EA maximizing a pseudo-Boolean function f. The second algorithm is the (1+(λ,λ))(1+(λ,λ)) GA with a fixed parameter λ proposed in (Doerr et al., 2015). It also stores only one individual x that is initialized with x′x in line 1 of Algorithm 1. Its iterations are performed in two steps. In the first step, the (1+(λ,λ))(1+(λ,λ)) GA chooses a number ℓ following the binomial distribution Bin(n,λ/n)Bin(n,λ/n). It then independently creates λ offspring of x, each by flipping exactly ℓ bits that are chosen uniformly at random (note that this means that all offspring have the same distance ℓ from their parent x). The best of these λ offspring is chosen as the mutation winner x′x (ties are broken uniformly at random). In the second step, the (1+(λ,λ))(1+(λ,λ)) GA independently creates another λ offspring, each by applying a biased crossover to x and x′x . This biased crossover takes each bit value from x′x with probability 1/λ1/λ and from x with probability 1−1/λ1-1/λ (independently for each of n positions). The best of these λ offspring is considered to be the winner y, and if y is not worse than x, the algorithm replaces x with y. The pseudocode of the (1+(λ,λ))(1+(λ,λ)) GA is shown in Algorithm 3. The cost of one iteration is 2λ2λ fitness evaluations. Note that parameter λ can only take values from [1..n][1..n]. For λ=1λ=1 the iteration is identical to an iteration of the (1+1)(1+1) EA, but it is twice as costly. 1input: individual x; 2 while not terminated do // Mutation phase 3 Choose ℓ∼Bin(n,λn) (n, λn). for i∈[1..λ]i∈[1..λ] do 4 xi←x_i← copy of x; 5 Flip ℓ bits in xix_i, choosing positions u.a.r.; 6 7 end for 8 x′←argmaxz∈x1,…,xλf(z)x ← *arg\,max_z∈\x_1,…,x_λ\f(z); // crossover phase 9 for i∈[1..λ]i∈[1..λ] do 10 yi←y_i← copy of x; 11 For each bit in yiy_i replace it with a corresponding bit from x′x with probability 1λ 1λ; 12 13 end for 14 y←argmaxz∈y1,…,yλf(z)y← *arg\,max_z∈\y_1,…,y_λ\f(z); 15 if f(y)≥f(x)f(y)≥ f(x) then 16 x←yx← y; 17 18 end if 19 20 end while 21return x; Algorithm 3 The (1+(λ,λ))(1+(λ,λ)) GA maximizing a pseudo-Boolean function f (Doerr et al., 2015). Although it is well known that the (1+(λ,λ))(1+(λ,λ)) GA with a dynamic choice of λ (via the one-fifth success rule (Doerr and Doerr, 2018) or via a heavy-tailed distribution (Antipov et al., 2022)) can have linear runtime on OneMax, we avoid using this algorithm in the portfolio. We aim to theoretically analyze a situation that can be met in practice, namely when the algorithm user has a limited portfolio of algorithms for their problem. Using algorithms with self-adaptive or random parameters essentially emulates having a large portfolio consisting of n different algorithms. From the perspective of OAS, this would be a very large portfolio, and learning the efficiency of each algorithm might take a lot of time and be inefficient compared to even sub-optimal algorithms from the portfolio. For this reason, we restrict OAS to portfolios with the (1+(λ,λ))(1+(λ,λ)) GA with static parameters. 2.3. Target Function In this paper, we consider the optimization of the classic theoretical benchmark called OneMax. This function is defined on bit strings of length n and it returns the number of one-bits in its argument. More formally, OneMax(x)=∑i=1nxi. OneMax(x)= _i=1^nx_i. There also exists a so-called generalized OneMax, which has some hidden bit string z as a parameter and OneMax(x) OneMax(x) returns the number of bits which coincide in x and z. In this paper, we consider only algorithms using unbiased variation operators (the operators that decide whether to flip a bit independently of the bit’s position and value, see (Lehre and Witt, 2012)), which run identically on generalized OneMax with any hidden bit string z. For this reason, to simplify the proofs, we consider the classic OneMax, where the hidden bit string is the all-ones bit string. 2.4. Selection Mechanism In this paper, we consider a selection mechanism which starts with running the (1+λ)(1+λ) EA and then can decide to switch to the (1+(λ,λ))(1+(λ,λ)) GA. To simplify the analysis, we assume that it cannot switch back (similar to the study in (Kostovska et al., 2022)). This choice of the order of algorithms is natural, since it is known that mutation-based algorithms can be effective at hill-climbing, but closer to the optimum they slow down significantly due to the coupon-collector effect: it takes Θ(nlogn) (n n) evaluations to find the optimum when starting in distance nεn from it, where ε>0 >0 is any small constant. At the same time, in (Antipov et al., 2025) it was shown the (1+(λ,λ))(1+(λ,λ)) GA is much more effective in the late stages of optimization, when the algorithm is converging to the global optimum. In particular, they proved the following theorem. Theorem 2.1 (Theorem 3.1 in (Antipov et al., 2025)). The expected runtime of the (1+(λ,λ))(1+(λ,λ)) GA with static parameter λ (and mutation rate p=λ/np=λ/n and crossover bias c=1/λc=1/λ as recommended in (Doerr et al., 2015)) on OneMax with initialization at distance D>0D>0 from the optimum is E[TF]=O(nλlogD+Dλ)E[T_F]=O( nλ D+Dλ) fitness evaluations. This is minimized by λ=nlnDλ= n DD, which gives a runtime guarantee of E[TF]=O(nDlnD)E[T_F]=O ( nD D ). The main goal of our analysis is to find the optimal time (or, more precisely, optimal distance from the optimum) to switch from the (1+λ)(1+λ) EA to the (1+(λ,λ))(1+(λ,λ)) GA and to estimate the runtime of the algorithm when it makes a switch in that distance. We do that in Section 4. We also aim at finding a switching mechanism which would be able to detect that the algorithm is close to that optimal distance. We propose such a mechanism and show that it yields an asymptotically optimal runtime on OneMax in Section 5. 3. Fixed-target Results In this section, we show fixed-target results for the (1+λ)(1+λ) EA on OneMax. Fixed-target analysis (see (Buzdalov et al., 2022)) aims at estimating the time that it takes an algorithm to find a solution of at least some fixed quality. This kind of analysis usually gives more details about the optimization process than the standard runtime analysis, since it reflects how hard different stages of optimization can be. However, as it was shown in (Buzdalov et al., 2022) and (Vinokurov and Buzdalov, 2022), it is not trivial to find tight bounds for fixed-target runtime even for the simple (1+1)(1+1) EA, mostly because of the algorithm being able to overshoot the target fitness value. The problem of overshooting is even sharper in the population-based EAs such as the (1+λ)(1+λ) EA, for this reason we are not aware of any existing results for them. For our purposes, however, it is enough to get asymptotical upper bounds on the fixed-target runtime of the (1+λ)(1+λ) EA, and for this reason we state and prove the following theorem. We note that proving a similar result with a precise leading constant (which implies a matching lower bound) might be a valuable result itself, but it requires much more work to achieve it. Thus, we leave it for future research. Theorem 3.1. The expected number of fitness evaluations that it takes the (1+λ)(1+λ) EA optimizing OneMax to find a solution in distance at most D from the optimum is at most E[TF]=O(nλlog+log+λlog+λ), if D≥nλ,O(nλlog+log+λlog+λ+nlog(nλ(D+1))+), if D<nλ, E[T_F]= casesO ( nλ ^+ ^+λ ^+λ ),& if D≥ nλ,\\ O ( nλ ^+ ^+λ ^+λ+n ( nλ(D+1) )^+ ),& if D< nλ,\\ cases where (⋅)+(·)^+ denotes max⋅,1. \·,1\. Proof. We note that for λ≤eλ≤ e^e these bounds are simplified to O(n(1+lognD+))O(n(1+ nD^+)), and they trivially follow from the bounds for the (1+1)(1+1) EA from (Buzdalov et al., 2022, Theorem 9) by noting that the progress in one iteration of the (1+λ)(1+λ) EA dominates the progress of the (1+1)(1+1) EA, while each iteration of the (1+λ)(1+λ) EA with these values of λ costs Θ(1) (1) fitness evaluations. Hence, in the rest of the proof we assume that λ>eλ>e^e. We use the classic fitness levels technique to prove this result (Wegener, ; Wegener, 2002). We partition the set [0..n][0..n] of all fitness values into subsets (levels)222In the classic fitness levels technique, it is the search space that is partitioned, not the fitness space. However, to ease the reading we simplify the notation and assume that any level in the classic notation corresponds to all search points that have fitness values in the fitness level in our notation., and for each level i we estimate pip_i—the probability that the (1+λ)(1+λ) EA leaves level i to go to a level with strictly better fitness in one iteration. Then the expected number of iterations the (1+λ)(1+λ) EA spends in level i is at most 1pi 1p_i, and the total runtime is at most the sum of these expected runtimes over all levels. The level partitions that we use below are inspired by the previous analyses of the (1+λ)(1+λ) EA (Doerr and Künnemann, 2015; Gießen and Witt, 2017), which distinguished similar phases depending on the current distance to the optimum. We only adapt their arguments to the fixed-target setting. We consider 3 cases based on the distance D. Large target distance: D≥nlnλD≥ n λ. We define levels as follows. A0A_0 denotes the optimal level (that is, we aim at estimating the runtime until this level is reached), hence A0=[n−D..n]A_0=[n-D..n]. Then we define δ≔⌈lnλ2lnlnλ⌉δ λ2 λ (note that δ≥2δ≥ 2, since λ≥eλ≥ e^e), and with this δ we define levels AiA_i for i∈[1..⌈n−Dδ⌉]i∈[1.. n-Dδ ] as Ai=[max0,n−D−iδ..n−D−(i−1)δ−1]. A_i=[ \0,n-D-iδ\..n-D-(i-1)δ-1]. We say that the (1+λ)(1+λ) EA is in level i, if the current individual x has fitness f(x)∈Aif(x)∈ A_i. Note that the fitness level can only decrease with time due to elitism of the (1+λ)(1+λ) EA. We now estimate the probability pip_i that the algorithm leaves level AiA_i in one iteration for an arbitrary i. We note that for this it is sufficient to have at least one of λ offspring to be better than x by at least δ. Let qiq_i be the probability that this happens in one particular offspring. Then qiq_i is at least the probability that mutation flips exactly δ zero-bits and no one-bits. Denoting by d the number of zero-bits in x (the distance from it to the optimum), we have qi≥(dδ)(1n)δ(1−1n)n−δ≥1e(dδ)(1n)δ. q_i≥ dδ ( 1n )^δ (1- 1n )^n-δ≥ 1e dδ ( 1n )^δ. By the estimates of the binomial coefficients from (Doerr, 2020), namely Eq. (1.4.15), and since d≥D≥nlnλd≥ D≥ n λ, this is ≥1e(dδn)δ≥1e(1δlnλ)δ=exp(δln(1δlnλ)−1) ≥ 1e ( dδ n )^δ≥ 1e ( 1δ λ )^δ= (δ ( 1δ λ )-1 ) ≥exp(−lnλ2lnlnλln(ln2λ2lnlnλ)−1)≥exp(−lnλ−1)=1λe. ≥ (- λ2 λ ( ^2λ2 λ )-1 )≥ (- λ-1 )= 1λ e. The probability that it happens in at least one of the individuals is therefore (1) pi=1−(1−qi)λ≥1−(1−1eλ)λ≥1−e−1e=Ω(1). p_i=1- (1-q_i )^λ≥ 1- (1- 1eλ )^λ≥ 1-e^- 1e= (1). Hence, the expected time to leave each level is O(1)O(1). There are at most nδ=Θ(nloglogλlogλ) nδ= ( n λ λ) levels, thus summing these expected times over all levels yields the bound of E[TI]=O(nlog+log+λlog+λ)E[T_I]=O( n ^+ ^+λ ^+λ) iterations. Since each iteration costs exactly λ fitness evaluation (one per offspring), we obtain the desired bound E[TF]=O(nλlog+log+λlog+λ)E[T_F]=O( nλ ^+ ^+λ ^+λ) on the expected number of evaluations for D≥nlnλD≥ n λ. Medium target distance: nlnλ>D≥nλ n λ>D≥ nλ. We now use the following partition into levels. The target level A0A_0 stays the same, that is, A0=[n−D..n]A_0=[n-D..n]. For i∈[1..⌊nlnλ⌋−D]i∈[1.. n λ -D] we define Ai=n−D−iA_i=\n-D-i\ (these levels consist of a single fitness value). For larger i we define AiA_i as a set of fitness values from n−⌊nlnλ⌋−(i−⌊nlnλ⌋−D)δn- n λ -(i- n λ -D)δ to n−⌊nlnλ⌋−(i−1−⌊nlnλ⌋−D)δ−1n- n λ -(i-1- n λ -D)δ-1. In other words, these levels consist of δ consequent fitness values (where δ is the same as in the analysis for larger D). Figure 1 illustrates this partition. f(x)f(x)n−Dn-Dn−nlnλn- n λ0Levels with δ valuesLevels with a singlefitness valueTarget level A0A_0 Figure 1. Illustration of the fitness levels partition for small distances D<nlnλD< n λ. We have already showed that the probability to leave the levels AiA_i with i>⌊nlnλ⌋−Di> n λ -D (those that have δ different fitness values) is Ω(1) (1). Now we show the same bound for the rest of the levels. The probability qiq_i to create a better individual with mutation is at least the probability to flip one zero-bit, and no other bits. If the current individual x is in distance d from the optimum, it has d zeros. Since we now consider case when d>D≥nλd>D≥ nλ, we have qi≥dn(1−1n)n−1≥1λe, q_i≥ dn (1- 1n )^n-1≥ 1λ e, hence by Eq. (1) we have pi=Ω(1)p_i= (1), and the expected time until we leave the level is at most O(1)O(1). The number of levels that we need to leave is at most ⌈nδ⌉+⌈nlnλ⌉−D=O(nδ) nδ + n λ -D=O( nδ). Summation of the expected leaving times over all theses levels and multiplying by λ (the cost of one iteration) results into bound E[TF]=O(nλlog+log+λlog+λ)E[T_F]=O( nλ ^+ ^+λ ^+λ), which completes the proof of the lemma for D≥nλD≥ nλ. Small target distance: D<nλD< nλ. We use the same level partition as in the previous case, but the main difference now is that in some levels pip_i is no longer Ω(1) (1). The bounds from previous cases hold only for levels with fitness values at most n−nλn- nλ, hence if λ≥nλ≥ n, then the bound E[TF]=O(nλlog+log+λlog+λ)E[T_F]=O( nλ ^+ ^+λ ^+λ) holds. Consider a fitness level AiA_i with i<nλ−Di< nλ-D (that is, for which the previous bound on pip_i does not hold). Let di≔D+id_i D+i denote the distance to the optimum of x when the algorithm is in level AiA_i. Then we have qi≥din(1−1n)n−1≥dien. q_i≥ d_in (1- 1n )^n-1≥ d_ien. Using Lemma 2 from (Antipov et al., 2022), we obtain pi=1−(1−qi)λ≥λqi1+λqi≥12min1,λqi=λdi2en, p_i=1-(1-q_i)^λ≥ λ q_i1+λ q_i≥ 12 \1,λ q_i\= λ d_i2en, hence the expected time to leave level i is at most 2endiλ 2end_iλ. Summing these runtimes over all sub-optimal levels i with i<nλ−Di< nλ-D (or, in other words, over all di∈[D+1..⌊nλ⌋]d_i∈[D+1.. nλ ]), we obtain ∑di=D+1⌊nλ⌋2enλdi _d_i=D+1 nλ 2enλ d_i =2enλ∑di=D+1⌊nλ⌋1di≤2enλ(ln(nλ(D+1))+1) = 2enλ _d_i=D+1 nλ 1d_i≤ 2enλ ( ( nλ(D+1) )+1 ) =O(nλ(log(nλ(D+1))+1)), =O ( nλ ( ( nλ(D+1) )+1 ) ), where in the penultimate step we used an estimate of a part of the harmonic series from (Antipov et al., 2025, Lemma 2.4). Taking into account that this term is only added when nλ>1 nλ>1, multiplying this bound by λ and adding the time needed to leave all levels with i≥nλ−Di≥ nλ-D (computed before), we obtain for all D<nλD< nλ E[TF] E[T_F] =O(nλlog+log+λlog+λ+n(log(nλ(D+1))++1)) =O ( nλ ^+ ^+λ ^+λ+n ( ( nλ(D+1) )^++1 ) ) =O(nλloglogλlogλ+nlog(nλ(D+1))+).∎ =O ( nλ λ λ+n ( nλ(D+1) )^+ ). 4. Optimal Switch Time In this section, we bound the expected runtime of OAS which starts solving OneMax with running the (1+λ)(1+λ) EA with population size λ1 _1 and then as soon as it finds an individual in distance D from the optimum it switches to the (1+(λ,λ))(1+(λ,λ)) GA with population size λ2 _2. Obviously, this is not a realistic assumption that an algorithm would know the distance to the optimum on any real-world problem, but these estimates will help us understand what an optimal switching mechanism would look like. The main result of this section is the following theorem. Theorem 4.1. Let D∈[0..n]D∈[0..n]. Consider the OAS algorithm that solves OneMax by starting with running the (1+λ)(1+λ) EA with population size λ1 _1 until it finds an individual in distance at most D from the optimal all-ones bit string, and then it switches to the (1+(λ,λ))(1+(λ,λ)) GA with population size λ2 _2. Then the expected time until it finds the optimum of OneMax is at most E[TF] E[T_F] =O(nλ1log+log+λ1log+λ1+nlog(nλ1(D+1))+ =O ( n _1 ^+ ^+ _1 ^+ _1+n ( n _1(D+1) )^+ . +nλ2logD++Dλ2), + . n _2 D^++D _2 ), where (⋅)+(·)^+ denotes max⋅,1 \·,1\. This theorem trivially follows from Theorems 2.1 and 3.1. Since the expression given by this theorem is hard to interpret, in the rest of the section we give more explanations of how this bound looks in some particular cases. First, consider a trivial case, when λ1=1 _1=1, that is, we start by running the (1+1)(1+1) EA until we reach distance D, and then we switch to the (1+(λ,λ))(1+(λ,λ)) GA. The following corollary describes this case. Corollary 4.2. Consider the OAS algorithm optimizing OneMax by starting with running the (1+1)(1+1) EA and then switching to the (1+(λ,λ))(1+(λ,λ)) GA with population size λ as soon as it finds an individual in distance at most D from the optimum. Then the expected number of fitness evaluations until it finds the optimum of OneMax is at most (2) E[TF]=O(nlognD++nλlogD++Dλ). E[T_F]=O (n nD^++ nλ D^++Dλ ). This bound is asymptotically minimized by choosing D=npoly(logn)∩O(n(loglogn)2logn)D= npoly( n)∩ O( n( n)^2 n) and λ=Ω(lognloglogn)∩O(nDloglogn)λ= ( n n)∩ O( nD n), which results in the expected runtime being E[TF]=O(nloglogn)E[T_F]=O(n n). Proof. The general expression (2) for the bound on E[TF]E[T_F] follows directly from Theorem 4.1 by taking λ1=1 _1=1 and λ2=λ _2=λ. To show that this bound cannot be smaller than O(nloglogn)O(n n), we first note that for D=0D=0 the bound is O(nlogn)O(n n), hence we can ignore this case and write D instead of D+D^+. Then we note that by Theorem 2.1, the last two terms are minimized by taking λ=nlnDλ= n DD, which results in O(nlognD+nDlogD)O(n nD+ nD D) bound. Since the first term is decreasing with D and the second is increasing, this expression is minimized when they are asymptotically equal. This can be achieved by taking D=Θ(n(loglogn)2logn)D= ( n( n)^2 n), when both terms are Θ(nloglogn) (n n). Hence, the best bound that can follow from Eq. (2) is O(nloglogn)O(n n). We now show that O(nloglogn)O(n n) bound is achieved for the stated ranges of D and λ (since D is super-constant, we omit the D+D^+ notation). The lower bound on D implies O(nlognD) O (n nD ) =O(nloglogn). =O(n n). The upper bound on D implies that logD=O(logn) D=O( n). Together with the lower bound on λ this implies O(nλlogD) O ( nλ D ) =O(nloglognlognlognloglognlogn)=O(nloglogn). =O ( n n n n n n )=O(n n). The upper bound on λ implies that O(Dλ) O(Dλ) =O(D⋅nDloglogn)=O(nloglogn). =O (D· nD n )=O(n n). Hence, all three terms in Eq. (2) are O(nloglogn)O(n n), which completes the proof. ∎ We note that the conditions on the values of D and λ are tight, that is, if they are not satisfied, then Eq. (2) gives a bound that is asymptotically larger than O(nloglogn)O(n n) (but since this is just an upper bound, the actual runtime might be O(nloglogn)O(n n) for a wider range of D and λ). If λ is ω(nDloglogn)ω( nD n), then the term DλDλ is ω(nloglogn)ω(n n). If D is nlogω(1)n n ^ω(1)n, then the first term nlognDn nD is ω(nloglogn)ω(n n). If λ is o(lognloglogn)o( n n), then nλlogD=ω(nloglognlognlogD)=ω(nloglogn) nλ D=ω( n n n D)=ω(n n). Finally, if D=ω(n(loglogn)2logn)D=ω( n( n)^2 n), then the upper bound on λ is asymptotically smaller than the lower bound, hence we cannot choose λ with which DλDλ is O(nloglogn)O(n n). With Corollary 4.2 we prove that an OAS algorithm can asymptotically outperform the algorithms from its portfolio. The best expected runtime that the (1+1)(1+1) EA and the (1+λ)(1+λ) EA can achieve on OneMax is Θ(nlogn) (n n) (Lehre and Witt, 2012) and the best expected runtime of the (1+(λ,λ))(1+(λ,λ)) GA with static parameters is Θ(nlognlogloglognloglogn) (n n n n) (Doerr and Doerr, 2018). OAS allows to achieve a runtime that is by a super-constant factor Ω(lognlogloglogn(loglogn)3) ( n n( n)^3) better than the best runtime achievable by the (1+(λ,λ))(1+(λ,λ)) GA using static parameters. It is interesting to note that to satisfy conditions of Corollary 4.2, the (1+(λ,λ))(1+(λ,λ)) GA must use λ≈Θ(logn)λ≈ ( n), while the best runtime of the (1+(λ,λ))(1+(λ,λ)) GA on OneMax is achieved with much smaller λ, namely λ≈Θ(logn)λ≈ ( n) (apart from sub-logarithmic factors). This is not surprising in the light of the results of (Doerr and Doerr, 2018) who showed that the optimal fitness-dependent λ is n/d n/d, where d is the distance to the optimum, hence optimal λ grows as the algorithm approaches the optimum. It is also in line with Theorem 2.1, which indicates that the smaller the starting distance is, the larger the value of λ that minimizes the runtime. To extend Corollary 4.2 to the setting when we start with the (1+λ)(1+λ) EA with a non-trivial population size λ>1λ>1, we note that the bound in Theorem 3.1 is the smallest when λ=Θ(1)λ= (1), and it is the same as for λ=1λ=1. This bound is asymptotically larger when λ=ω(1)λ=ω(1). Hence, we cannot prove a better-than-O(nloglogn)O(n n) bound for OAS with a portfolio consisting of the (1+λ)(1+λ) EA and the (1+(λ,λ))(1+(λ,λ)) GA. However, in the following corollary we show that this bound holds for a wide range of population sizes of the (1+λ)(1+λ) EA. Corollary 4.3. Consider the OAS algorithm optimizing OneMax by starting with running the (1+λ)(1+λ) EA with population size λ1 _1 and then switching to the (1+(λ,λ))(1+(λ,λ)) GA with population size λ2 _2 as soon as it finds an individual at distance at most D from the optimum. Assume that (a) λ1=O(loglognlogloglognloglogloglogn) _1=O( n n n), (b) D=npoly(logn)∩O(n(loglogn)2logn)D= npoly( n)∩ O( n( n)^2 n), and (c) λ2=Ω(lognloglogn)∩O(nDloglogn) _2= ( n n)∩ O( nD n). Then the expected number of fitness evaluations needed by the algorithm to find the optimum satisfies E[TF]=O(nloglogn)E[T_F]=O(n n). We omit the proof for reasons of space, and only note that it follows from combining the proof of Corollary 4.2 with putting the conditions on λ1 _1 into Theorem 4.1. 5. Automatically Detecting a Good Switching Moment In the previous section we considered a case when the algorithm can decide to switch at a particular distance from the optimum. This is probably less relevant in practice, since it is rare when the algorithm has access to this information. However, the algorithm can estimate how hard the progress is. It can start with the (1+λ)(1+λ) EA and after it does not observe fitness improvement for some particular time, it can switch to the more complicated mechanics of the (1+(λ,λ))(1+(λ,λ)) GA, which allows faster convergence to the optimum. The problem here is that switching too early might make us use the (1+(λ,λ))(1+(λ,λ)) GA at distances where it is not efficient due to the big cost of each of its iterations (when the (1+λ)(1+λ) EA gives much better progress per fitness evaluation). In this section, we propose a mechanism to detect the necessity of switching when our portfolio consists of the (1+1)(1+1) EA 333In order to simplify the proofs (and to get rid of two population sizes λ1 _1 and λ2 _2), we only consider the (1+λ)(1+λ) EA with λ=1λ=1 in this section. However, without proof we note that the results can be easily adapted for the (1+λ)(1+λ) EA with λ that satisfies the condition (a) of Corollary 4.3. and the (1+(λ,λ))(1+(λ,λ)) GA with optimal population size λ=Θ(logn)λ= ( n), as suggested by Corollary 4.2. This mechanism starts with the (1+1)(1+1) EA and switches to the (1+(λ,λ))(1+(λ,λ)) GA after k consecutive iterations of the (1+1)(1+1) EA without progress. The choice of k plays an important role, as it defines the distribution of the distance at which we switch to the (1+(λ,λ))(1+(λ,λ)) GA. Our intuition suggests that we should switch when we understand that the (1+1)(1+1) EA is struggling to achieve progress in 2λ2λ iterations, since at this point the cost of search equals that of the one iteration of the (1+(λ,λ))(1+(λ,λ)) GA. However, it does not mean that we should choose k=2λk=2λ: if we are unlucky in one of the fitness levels before reaching the optimal switching distance, this would increase the expected runtime. Instead, to be sure that the algorithm should indeed switch, this threshold should be set more conservatively as k=Θ(λlogn)k= (λ n). This allows us not to switch too early by making unfortunate events of k failures in a row sufficiently unlikely before we reach the optimal interval of D. At the same time, it allows to switch to the (1+(λ,λ))(1+(λ,λ)) GA with minimal delay from the optimal moment. To demonstrate the efficiency of this switching mechanism, we show that it also achieves O(nloglogn)O(n n) runtime on OneMax, which is shown in the following theorem. Theorem 5.1. Consider optimization of OneMax with the OAS algorithm that starts with the (1+1)(1+1) EA and then switches to the (1+(λ,λ))(1+(λ,λ)) GA with population size λ=Θ(logn)λ= ( n) after the (1+1)(1+1) EA does not manage to create a better individual for k=Θ(λlogn)k= (λ n) iterations in a row. The expected number of fitness evaluations it takes this OAS algorithm to find the optimum is E[TF]=O(nloglogn)E[T_F]=O(n n). Before we start the proof, we state and prove two auxiliary lemmas. The first lemma shows that we do not switch to the (1+(λ,λ))(1+(λ,λ)) GA too early, and the second one shows that we do not switch to it too late. Lemma 5.2. In the setting of Theorem 5.1, let D≔2enlnnkD 2en nk. Then we have D=Θ(nlogn)D= ( n n) and the probability that the online algorithm selection mechanism switches to the (1+(λ,λ))(1+(λ,λ)) GA before reaching distance D from the optimum is at most 1/n1/n. Proof. First, since λ=Θ(logn)λ= ( n), we have k=Θ(log2n)k= ( ^2n), hence D=Θ(nlogn)D= ( n n). The probability that we switch at some distance d from the optimum is the probability that the (1+1)(1+1) EA has k unsuccessful iterations in a row when it is in this distance d. For any d≥Dd≥ D this probability is at most (1−den)k (1- den )^k =(1−den)end⋅dken≤exp(−dken) = (1- den ) end· dken≤ (- dken ) ≤exp(−2enlnnk⋅ken)=1n2. ≤ (- 2en nk· ken )= 1n^2. By the union bound, the probability that the switch occurs before the (1+1)(1+1) EA reaches distance D is at most the sum of these probabilities over all distances d≥Dd≥ D, that is, it is at most 1/n1/n. ∎ Lemma 5.3. In the setting of Lemma 5.2, after the (1+1)(1+1) EA finds an individual in distance at most D from the optimum for the first time, the expected time until it switches to the (1+(λ,λ))(1+(λ,λ)) GA is at most O(nloglogn)O(n n). Proof. Let D′≔nln2nD n ^2n. Let τ be the time it takes the (1+1)(1+1) EA that starts in distance at most D from the optimum to find an individual that is in distance at most D′D from the optimum or to make k consequent unsuccessful iterations in a row. This time is dominated by the time it just takes the regular (1+1)(1+1) EA to reach an individual in distance D′D from the optimum, which can be estimated via fitness levels technique, in the same way we did it in the proof of Theorem 3.1. For each distance d∈[D′..D]d∈[D ..D] the probability pdp_d to find an improvement is at least d/(en)d/(en), hence the total expected time it takes the (1+1)(1+1) EA to reach distance D′D from distance D (or smaller) is at most E[τ] E[τ] ≤∑d=D′+1D1pd=en∑d=D′+1D1d≤en(lnD′+1) ≤ _d=D +1^D 1p_d=en _d=D +1^D 1d≤ en ( DD +1 ) =en(ln(Θ(logn))+1)=Θ(nloglogn), =en ( ( ( n))+1 )= (n n), where we used an estimate of a part of the harmonic series from (Antipov et al., 2025, Lemma 2.4), similar to the proof of Theorem 3.1. If after τ iterations the algorithm still has not switched to the (1+(λ,λ))(1+(λ,λ)) GA, then its current individual x is in distance d≤D′d≤ D from the optimum. For such d the probability to have k unsuccessful iterations in a row is at least the probability that mutation does not flip any of d zero-bits in k attempts, which is, (1−dn)k=(1−dn)nd⋅dkn=(e−1−o(1))O(1)=Θ(1), (1- dn )^k= (1- dn ) nd· dkn= (e^-1-o(1) )^O(1)= (1), where we used dkn≤D′kn=nln2n⋅Θ(log2n)n=O(1) dkn≤ D kn= n ^2n· ( ^2n)n=O(1). Consequently, at these distances d≤D′d≤ D the probability that the (1+1)(1+1) EA performs k unsuccessful iterations in a row before finding an improvement is at least constant. Hence, the expected number of distances the (1+1)(1+1) EA visits before doing it (or finding the optimum) is also at most constant. In each distance it spends at most k=Θ(log2n)k= ( ^2n). Therefore, if the algorithm does not switch to the (1+(λ,λ))(1+(λ,λ)) GA after τ iteration, it does it in O(log2n)O( ^2n) iterations after that (in expectation). In summary, the expected time it takes the OAS algorithm to switch to the (1+(λ,λ))(1+(λ,λ)) GA after the (1+1)(1+1) EA finds an individual in distance D from the optimum is at most E[τ]+O(log2n)=O(nloglogn)E[τ]+O( ^2n)=O(n n). ∎ With these two lemmas at hand, we prove Theorem 5.1. Proof of Theorem 5.1. If the algorithm switches to the (1+(λ,λ))(1+(λ,λ)) GA before reaching distance D, then the expected runtime is at most the sum of the expected runtimes of the (1+1)(1+1) EA and the (1+(λ,λ))(1+(λ,λ)) GA (each starting with a random solution), that is, O(nlogn)O(n n). Since by Lemma 5.2 this event happens only with probability 1/n1/n, its contribution to the expected total runtime is at most O(logn)O( n). In the rest of the proof we condition on not switching before reaching distance D. We split the analysis into two parts: until the (1+1)(1+1) EA reaches distance D from the optimum and after that. Part 1. To prove the expected duration of this part, we can again use the fitness levels technique. We define a partition into levels, where each level corresponds to exactly one fitness value. For any particular fitness level i the time that the (1+1)(1+1) EA spends on this level conditional on not switching before reaching distance D is dominated by the same unconditional time, since the condition implies that the algorithm does not spend more than k iterations in this level. This means that this condition “cuts” the tail of the distribution of time, which leads to the domination. Therefore, the expected time it takes to leave a level which is in distance d from the optimum is at most end end. Summing this over all d>Dd>D, we have that the (1+1)(1+1) EA reaches distance D from the optimum in expected time that is at most ∑d=Dnend≤en(lnnD+1)=enln(Θ(logn))=Θ(nloglogn). _d=D^n end≤ en ( nD+1 )=en ( ( n))= (n n). Part 2. After the algorithm reaches distance D, the condition that it has not switched to the (1+(λ,λ))(1+(λ,λ)) GA does not affect the algorithm’s behavior, and it spends the same number of iterations at each fitness value as it would if it just started in distance D with the (1+1)(1+1) EA. This allows us to apply Lemma 5.3. Hence, the expected number of iterations that the (1+1)(1+1) EA makes in this second part of optimization is at most O(nloglogn)O(n n). Since we switch to the (1+(λ,λ))(1+(λ,λ)) GA in distance at most D from the optimum, by Theorem 2.1 it takes it at most O(nλlogD+Dλ)=O(nlognlogn+nlognlogn)=O(n) O ( nλ D+Dλ )=O ( n n n+ n n n )=O(n) expected fitness evaluations to find the optimum. Therefore, the second part of optimization takes at most O(nloglogn)O(n n) time. Combining the result for Parts 1 and 2, and also recalling the contribution of the runtime in case when the algorithm switches to the (1+(λ,λ))(1+(λ,λ)) GA before reaching distance D, we conclude that the total runtime is at most O(nloglogn)O(n n). ∎ We consider a very strict setting, where the OAS algorithm can only switch from the (1+1)(1+1) EA to the (1+(λ,λ))(1+(λ,λ)) GA once and has to proceed with the (1+(λ,λ))(1+(λ,λ)) GA until the end of optimization. This restriction is justified by our goal—to show the capabilities of OAS even with such a small portfolio. However, allowing the OAS algorithm to switch back to the (1+1)(1+1) EA (e.g., after the (1+(λ,λ))(1+(λ,λ)) GA makes improvements k′k times in a row, which indicates that the progress is too easy to spend 2λ2λ evaluations in each iteration) might allow to switch from the (1+1)(1+1) EA to the (1+(λ,λ))(1+(λ,λ)) GA more carelessly, for example after k=Θ(λ)k= (λ) failures of the (1+1)(1+1) EA. Finding a good mechanism to switch back to the (1+1)(1+1) EA and proving its effectiveness on a wider range of benchmarks than just OneMax would be a valuable complement of the results of this paper for practitioners. 6. On a Hyper-heuristic Approach It is possible to extend the results of the previous section on the hyper-heuristic approach to switching between algorithms. Most of the previous studies of HHs involved only HHs that switch between different operators in the (1+1)(1+1) EA. However, an iteration of the (1+λ)(1+λ) EA or of the (1+(λ,λ))(1+(λ,λ)) GA can be also considered as a more costly operator that creates an offspring, hence H can also switch between algorithms. The main difference between the OAS approach and the H approach is that the first aims at running each algorithm until it detects that it has become inefficient, while HHs usually iterate between operators using some strategy. Although this strategy can depend on the results of the previous iterations (which sometimes make HHs very similar to OAS), they usually decide which algorithm to use in every iteration following some pre-defined simple rules. This almost excludes different learning techniques that assess the efficiency of each operator (with exception being the H studied in (Doerr et al., 2018)), but it also gives the HHs more flexibility and faster adaptivity (if their rules are chosen well). We propose the following hyper-heuristic that at the start of each iteration chooses whether to run an iteration of the (1+1)(1+1) EA or of the (1+(λ,λ))(1+(λ,λ)) GA with population size λ. Initially it starts by running the (1+1)(1+1) EA. In each next iteration it makes a decision as follows. • If in the previous λ iterations there was no progress, it runs an iteration of the (1+(λ,λ))(1+(λ,λ)) GA. • Otherwise, it runs an iteration of the (1+1)(1+1) EA. In more simple words, in each fitness level this H runs the (1+1)(1+1) EA for λ times or until it escapes this fitness level. If after that it is still on the same level, it starts performing iterations of the (1+(λ,λ))(1+(λ,λ)) GA until it finds a better individual. The following theorem shows that this H can also achieve the runtime of O(nloglogn)O(n n) on OneMax. Theorem 6.1. The expected runtime of the described H with λ=Θ(logn)λ= ( n) on OneMax is O(nloglogn)O(n n). Proof. We will first show that this H reaches distance d≤nln2nd≤ n ^2n from the optimum in O(nloglogn)O(n n) expected time, and in the rest of optimization it spends at most O(n)O(n) more fitness evaluations. First, assume that the current distance to the optimum d is at least nln2n n ^2n and let tdt_d be the expected number of fitness evaluations spent by the H in this distance d before it finds progress. To estimate E[td]E[t_d], we will use slightly modified amortized analysis (Tarjan, 1985). First, let X be the number of fitness evaluations performed by the (1+1)(1+1) EA in this distance d. Let Y be the number of iterations that the (1+(λ,λ))(1+(λ,λ)) GA makes to find an improvement starting in distance d from the optimum (conditional on that the (1+1)(1+1) EA did not find an improvement). Then if we define the coin value as Y′=1+2Y =1+2Y, then after running the (1+1)(1+1) EA for at most λ iterations, even if it does not achieve progress, we have enough budget to do so with the (1+(λ,λ))(1+(λ,λ)) GA. Hence, the total cost of finding an improvement at distance d is at most X⋅Y′X· Y . To estimate E[X⋅Y′]E[X· Y ] we note that X and Y′Y are independent, since by definition Y′Y does not depend on whether the (1+1)(1+1) EA achieved progress in its λ attempts. Hence, E[X⋅Y′]=E[X]E[Y′]=E[X](1+2E[Y])E[X· Y ]=E[X]E[Y ]=E[X](1+2E[Y]). Since the probability that the (1+1)(1+1) EA finds an improvement in one iteration is den den (see the proof of Theorem 3.1), we have X∼minGeom(den),λX \Geom( den),λ\, and hence E[X]≤endE[X]≤ end. By (Doerr et al., 2015, Lemma 7), for some constant C, the probability that the (1+(λ,λ))(1+(λ,λ)) GA finds an improvement in one iteration is at least C(1−(1−1ln2n)λ2/2)=C(1−e−Ω(1))≥C′ C (1- (1- 1 ^2n )^λ^2/2 )=C(1-e^- (1))≥ C for some constant C′C that depends on the value of λ. Hence, E[Y]≤C′−1E[Y]≤ C -1, and the expected time spent in distance d from the optimum is at most end(1+2C′−1) end(1+2C -1). Summing up these times over all distances d≥nln2nd≥ n ^2n we obtain that the expected time until the H finds an individual in distance d<nln2nd< n ^2n is at most ∑d=⌈nln2n⌉nend(1+2C′−1)=O(nlog(n/ln2n))=O(nloglogn). _d= n ^2n ^n end(1+2C -1)=O (n ( nn/ ^2n ) )=O(n n). In smaller distances d<nln2nd< n ^2n, even if we pessimistically assume that (1+1)(1+1) EA never finds an improvement, the total time spent on the (1+(λ,λ))(1+(λ,λ)) GA is at most O(n)O(n), as we showed in the proof of Theorem 5.1. The total number of evaluations wasted on the (1+1)(1+1) EA on these small distances is at most λnlog2n=o(n)λ n ^2n=o(n). Hence, the total runtime is at most O(nloglogn)O(n n). ∎ We note that in contrast with the setting of our OAS algorithm, this H can switch to the (1+(λ,λ))(1+(λ,λ)) GA after just λ unsuccessful iterations of the (1+1)(1+1) EA instead of Θ(λlogn) (λ n) that is required by the OAS algorithm. This is because the H can switch back to the (1+1)(1+1) EA after each successful iteration, which allows it to ignore unlucky events when it switches to the (1+(λ,λ))(1+(λ,λ)) GA early. As a result of restricting the OAS algorithm from switching back to the (1+1)(1+1) EA, it has to switch only when it is really sure that the (1+(λ,λ))(1+(λ,λ)) GA will be more effective. Although it leads to some insignificant lag in switching, it avoids wasting fitness evaluations on the (1+1)(1+1) EA iterations in the late stages of optimization. However, both these downsides do not affect our upper bounds on the runtime of both the H and the OAS algorithm. 7. Discussion and Conclusion In this paper, we have demonstrated that an OAS algorithm can outperform the algorithms from its portfolio, even when the portfolio consists of only two algorithms. We proposed a mechanism to switch between them that is based on being sure that one of the algorithms is not effective anymore. This mechanism allows to solve OneMax in O(nloglogn)O(n n) expected time when using the (1+1)(1+1) EA and the (1+(λ,λ))(1+(λ,λ)) GA: the performance that is asymptotically superior to any of these two algorithms working alone, even with the best tuned (but static) parameters. We also proposed a hyper-heuristic based on the same algorithms which shows the same performance gain. Seeing this upper bound that is better than the Θ(nlogn) (n n) runtime of algorithms from the portfolio (or ≈Θ(nlogn)≈ (n n), if we allow the (1+(λ,λ))(1+(λ,λ)) GA to use differently tuned parameters) naturally raises the question what is the best runtime that we can achieve using m different algorithms in the portfolio. Trivially, using m≈nm≈ n is enough to be able to simulate the self-adaptive (1+(λ,λ))(1+(λ,λ)) GA that can solve OneMax in linear time, but what is the minimal portfolio size that achieves this runtime? And what is the best performance gain we can get by adding algorithms to the portfolio? This question is important in real-world applications, since, on the one hand, the practitioners want to use a sufficiently large portfolios of algorithms that would allow the best possible performance in any situation, but, on the other hand, large portfolios make it significantly more difficult to quickly (re-)learn the effectiveness of each algorithm without spending too much time. Addressing these questions in further theoretical research would be extremely useful for the algorithm users. From practical perspective, it is also important to verify if the proposed OAS methods can be used on practical problems with more complex landscapes. One of the essential elements of our analysis was the fixed-target results shown in Section 3. Together with the fixed-start results from (Antipov et al., 2025) they provided us enough information about behavior of each algorithm at the beginning and at the end of optimization. For analysis of larger portfolios it is necessary to extend these tools to be able to prove “fixed-start-fixed-target” results. This seems to be a trivial task for asymptotical upper bound as the ones we showed in Theorem 3.1, but proving the tight bounds with leading constants might be much more challenging, especially for population-based EAs. However, the outcome of such results will give us a solid foundation for analysis of more complex OAS. Finally, we address the tightness of our O(nloglogn)O(n n) bound shown for multiple settings. Although we do not use any tools that provide lower bounds, we note that our fitness-level arguments used in Theorem 3.1 are such that it is unlikely that the algorithm skips a super-constant fraction of levels, hence following the arguments of the fitness-levels method for lower bounds (Doerr and Kötzing, 2024) it is natural to say that our bound should be tight. The same argument suggests that the bounds from (Antipov et al., 2025) that we use are also asymptotically tight. Hence, our bound should also be tight. However, despite such simple intuition, proving it would require more effort, and we leave it for further studies. Acknowledgements.We acknowledge funding by the European Union (ERC, “dynaBBO”, grant no. 101125586). This research was also jointly funded by the French National Research Agency (ANR-23-CE23-0035) and the German Research Foundation (DFG; LI 2801/7-1), through project Opt4DAC. References F. Alanazi and P. K. Lehre (2014) Runtime analysis of selection hyper-heuristics with classical learning mechanisms. In IEEE Congress on Evolutionary Computation, CEC 2014, p. 2515–2523. Cited by: §1. D. Antipov, M. Buzdalov, and B. Doerr (2022) Fast mutation in crossover-based algorithms. Algorithmica 84 (6), p. 1724–1761. Cited by: §2.2, §3. D. Antipov, M. Buzdalov, and B. Doerr (2025) First steps toward a runtime analysis when starting with a good solution. ACM Transactions on Evolutionary Learning and Optimization 5 (2), p. 14:1–14:41. Cited by: §1, §1, §2.4, Theorem 2.1, §3, §5, §7, §7. A. Bendahi, B. Doerr, A. Fradin, and J. F. Lutzeyer (2025) Speeding up hyper-heuristics with markov-chain operator selection and the only-worsening acceptance operator. In International Joint Conference on Artificial Intelligence, IJCAI 2025, p. 8850–8857. Cited by: §1. M. Buzdalov, B. Doerr, C. Doerr, and D. Vinokurov (2022) Fixed-target runtime analysis. Algorithmica 84 (6), p. 1762–1793. Cited by: §3, §3. D. Corus, P. S. Oliveto, and F. Zheng (2025) Hybrid selection allows steady-state evolutionary algorithms to control the selective pressure in multimodal optimisation. In Genetic and Evolutionary Computation Conference, GECCO 2025, p. 881–889. Cited by: §1. B. Doerr, C. Doerr, and F. Ebel (2015) From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567, p. 87–104. Cited by: §2.2, Theorem 2.1, §6, 3. B. Doerr and C. Doerr (2018) Optimal static and self-adjusting parameter choices for the (1+(λ, λ)) genetic algorithm. Algorithmica 80 (5), p. 1658–1709. Cited by: §1, §2.2, §4, §4. B. Doerr and T. Kötzing (2024) Lower bounds from fitness levels made easy. Algorithmica 86 (2), p. 367–395. Cited by: §7. B. Doerr and M. Künnemann (2015) Optimizing linear functions with the (1+λ) evolutionary algorithm - different asymptotic runtimes for different instances. Theoretical Computer Science 561, p. 3–23. Cited by: §3. B. Doerr, A. Lissovoi, P. S. Oliveto, and J. A. Warwicker (2018) On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In Genetic and Evolutionary Computation Conference, GECCO 2018, p. 1015–1022. Cited by: §1, §6. B. Doerr (2020) Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, B. Doerr and F. Neumann (Eds.), Natural Computing Series, p. 1–87. Cited by: §3. C. Gießen and C. Witt (2017) The interplay of population size and mutation probability in the (1+λ) EA on onemax. Algorithmica 78 (2), p. 587–609. Cited by: §3. A. Kostovska, A. Jankovic, D. Vermetten, J. de Nobel, H. Wang, T. Eftimov, and C. Doerr (2022) Per-run algorithm selection with warm-starting using trajectory-based features. In Parallel Problem Solving from Nature, PPSN 2022, Part I, p. 46–60. Cited by: §1, §2.4. P. K. Lehre and E. Özcan (2013) A runtime analysis of simple hyper-heuristics: to mix or not to mix operators. In Foundations of Genetic Algorithms, FOGA 2013, p. 97–104. Cited by: §1. P. K. Lehre and C. Witt (2012) Black-box search by unbiased variation. Algorithmica 64 (4), p. 623–642. Cited by: §1, §2.3, §4. A. Lissovoi, P. S. Oliveto, and J. A. Warwicker (2017) On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisation. In Genetic and Evolutionary Computation Conference, GECCO 2017, p. 849–856. Cited by: §1, §1. A. Lissovoi, P. S. Oliveto, and J. A. Warwicker (2020) Simple hyper-heuristics control the neighbourhood size of randomised local search optimally for leadingones. Evolutionary Computation 28 (3), p. 437–461. Cited by: §1. A. Lissovoi, P. S. Oliveto, and J. A. Warwicker (2023) When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not. Artificial Intelligence 314, p. 103804. Cited by: §1. R. E. Tarjan (1985) Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods 6 (2), p. 306–318. Cited by: §6. D. Vermetten, H. Wang, T. Bäck, and C. Doerr (2020) Towards dynamic algorithm selection for numerical black-box optimization: investigating BBOB as a use case. In Genetic and Evolutionary Computation Conference, GECCO 2020, p. 654–662. Cited by: §1. D. Vermetten, H. Wang, K. Sim, and E. Hart (2023) To switch or not to switch: predicting the benefit of switching between algorithms based on trajectory features. In Applications of Evolutionary Computation, EvoApplications 2023, Lecture Notes in Computer Science, Vol. 13989, p. 335–350. Cited by: §1. D. Vinokurov and M. Buzdalov (2022) Towards fixed-target black-box complexity analysis. In Parallel Problem Solving from Nature, PPSN 2022, Part I, p. 600–611. Cited by: §3. [24] I. Wegener Cited by: §3. I. Wegener (2002) Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In Evolutionary Optimization, p. 349–369. External Links: ISBN 978-0-306-48041-6 Cited by: §3.