When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

Denis Antipov; Carola Doerr

cs.NEApr 8, 2026

When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

Authors: Denis Antipov, Carola Doerr

Organizations: Sorbonne Université, CNRS, LIP6 Paris, France

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+λ)$ EA and the $(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(n\log\log n)$ expected time, faster than the $Θ(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+λ)$ to the $(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.

Figures & tables

Panel of Figure 1 — Figure 1. Illustration of the fitness levels partition for small distances $D<\frac{n}{\ln\lambda}$ .

Algorithm Selection

Algorithm selection predicts which solver, model, or strategy will work best for a given instance, context, or computational budget.

See all 50 papers

Jun 1, 2026

Evaluating Real-World Generalizability of Algorithm Selection Models

Algorithm Selection (AS) aims to automatically identify the most suitable optimization algorithm for a given problem instance by leveraging measurable problem characteristics and historical performance data. In this study, we investigate the generalization ability of AS models across both synthetic and real-world optimization landscapes. We consider two widely used academic benchmark suites (BBOB and CEC) and two real-world problem sets (robotics trajectory optimization tasks and unmanned aerial vehicle path-planning problems). Through a systematic cross-benchmark evaluation, we analyze how AS models transfer between domains, identify where generalization succeeds or breaks down, and highlight the challenges that arise when applying AS in realistic, domain-specific contexts. Our findings provide insights into the robustness of current AS approaches and inform the development of more reliable, broadly applicable AS systems for real-world optimization.

Gjorgjina Cenikj, Jakub Kudela, Eva Tuba +1

Computer Systems Department Jožef Stefan Institute Ljubljana, Slovenia · Brno University of Technology Brno, Czech Republic

Algorithm Selection Cross-Domain Generalization Cross-Dataset Generalization

Ask PDF

Apr 5, 2026

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by proposing a parent selection strategy for the

(μ+1)

genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, the resulting algorithm solves the Jump

_k

problem in

O(k4^kn\log(n))

expected time. This bound is significantly smaller than the best known bound of

O(nμ\log(μ)+n\log(n)+n^{k-1})

for any

(μ+1)

~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The main novelty of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.

Andre Opris, Denis Antipov

University of Passau Passau, Germany · Sorbonne Université, CNRS, LIP6 Paris, France

Evolutionary Optimization Genetic Algorithms 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

Abstract

Algorithm Selection

Explore similar work

Evaluating Real-World Generalizability of Algorithm Selection Models

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

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

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