Runtime Analysis of Evolutionary Algorithms

Follow this topic Ask about this topic

Momentum

1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 21

Sep 14, 2026cs.NE

Signed Sensitivity of Expected Hitting Time to Mutation Rate in the (1+1) EA: Per-State Sign Theorems and Verifiable Certificates for Non-Lumpable Families

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.

RenKai Wang

Institute of Automation, Chinese Academy of Sciences (CASIA) · University of Chinese Academy of Sciences (UCAS)

Runtime Analysis of Evolutionary Algorithms Sensitivity Analysis

Aug 11, 2026cs.NE

Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

Evolutionary multitasking is a recent approach that solves multiple related optimization problems within a single evolutionary run, rather than addressing each problem separately. We consider monotone submodular optimization problems with dynamic knapsack constraints and study a multitasking formulation in which all tasks share a common monotone submodular function

f

, but differ in their constraints. We focus on the case where elements within each constraint have uniform cost and show that this structure leads to small Pareto fronts in the multitasking formulation. This enables solution sharing across tasks and can improve performance compared to running standard evolutionary approaches independently, depending on the constraint regime. Using rigorous runtime analysis, we analyze the expected time until the proposed multitasking algorithms obtain a

(1 - 1/e)

-approximation for each task. Experimental results for the Maximum Coverage problem complement the theoretical analysis and provide further insight into the practical behavior of the approach across different budget settings.

Liam Wigney, Frank Neumann

Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

Submodular Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Jul 31, 2026cs.NE

Analysis of Memory-Runtime Trade-offs in Caching Strategies for Genetic Programming Symbolic Regression

Genetic Programming Symbolic Regression (GPSR) generates mathematical expressions to model input-output relationships using an evolutionary process. A significant challenge in GPSR lies in the repeated evaluation of entire expressions or their sub-expression, which inflates computational runtime. To address this inefficiency, caching mechanisms have been employed to reduce redundant computations. However, prior studies predominantly employ a single caching strategy, offering limited insights into their comparative performance or memory-runtime trade-offs. In this paper, we present a comprehensive analysis of caching mechanisms for GPSR on synthetic and real-world datasets. We also include an empirical study of key-value usage frequencies under an infinitely large cache, offering insights into optimal cache sizing. Furthermore, we provide actionable guidelines for configuring caching strategies based on computational and memory constraints. Our findings indicate that complex caching mechanisms necessitate a minimum cache size to achieve computational time reductions. Conversely, lightweight caching strategies, such as Least Recently Used (LRU) and, notably, First-In-First-Out (FIFO), can significantly decrease computation time for fitness evaluations, which are a substantial component of the overall runtime.

Jiaming Shi, Kei Sen Fong, Mehul Motani

National University of Singapore Department of Electrical and Computer Engineering Singapore, Singapore · National University of Singapore Department of Electrical and Computer Engineering, Institute of Data Science, N.1 Institute for Health, Institute for Digital Medicine Singapore, Singapore

Genetic Programming Runtime Analysis of Evolutionary Algorithms Symbolic Regression

Jul 26, 2026cs.NE

Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization

This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class CLIMB and analyze the runtime of GSEMO and the widely used NSGA-II on this problem. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a speedup of order

Ω(\sqrt{n}/\log n)

. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes we propose in this paper, can find the Pareto front of CLIMB in expected

O(n \log n)

fitness evaluations, whereas NSGA-II with a fixed population size requires

Ω(n^{1.5})

fitness evaluations in expectation. To the best of our knowledge, this is the first rigorous runtime analysis in multi-objective optimization demonstrating a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, like the evolution of population diversity over time, and employs the well-known family-three method to prove the lower bound.

Andre Opris

Faculty of Computer Science and Mathematics University of Passau

Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Jul 24, 2026math.NA

Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

Closed-loop generative selection has become a workhorse of computational drug discovery: a learned generative model proposes candidate molecules, a fitness oracle scores them, the best are kept, and the model is retrained on this elite set before the next round. Despite its wide use, the method has lacked a rigorous convergence theory, largely because retraining the model each round breaks the Markov property on which classical evolutionary-algorithm analysis relies. We develop a self-contained theory of convergence and expected running time for this class of algorithms. By recovering a Markov structure on an enlarged state space, we show that elitism makes the search absorbing, and we prove almost-sure convergence together with a runtime bound that decomposes the search into the time spent escaping each fitness level. We then analyse the role of the model's memory---how much of the past it is trained on. When learning improves steadily with more data, deeper memory never hurts; when it does not, an exit-time analysis pinpoints the optimal memory depth and shows that excess memory can actually slow convergence. The theory extends to multi-objective search and to noisy oracles: we quantify how many repeated evaluations certify progress under light-tailed noise, and how robust estimators restore guarantees under heavy tails. Recast in terms of oracle evaluations - the true bottleneck in drug design - the analysis yields a concrete, evaluation-minimal strategy. Areproducible study confirms the predictions, including the surprising cost of excess memory. We close with three open problems.

Konstantin Fackeldey, Christof Schütte

Zuse Institute Berlin, Takustraße 7, 14195 Berlin, Germany · Institute for Mathematics, Technical University Berlin, Fasanenstr 89,10623 Berlin, Germany · Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, 14195 Berlin, Germany

Stochastic Optimization Runtime Analysis of Evolutionary Algorithms Drug Discovery

Jul 15, 2026cs.NE

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

as

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

Jun 16, 2026cs.NE

Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values

Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.

Narges Tavassoli Kejani, Andrew M. Sutton, Frank Neumann

Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStal, F-59000, France · University of Minnesota Duluth, Minnesota, USA · Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms Multi-Objective Optimization

Jun 14, 2026cs.NE

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound

O(n D^5)

for the expected number of fitness evaluations of CGP to construct a conjunction of

n

inputs using at most

D \geq n-1

binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to

O(n D^4)

. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.

Duc-Cuong Dang, Roman Kalkreuth, Andre Opris

University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany

Boolean Function Learning Genetic Programming Runtime Analysis of Evolutionary Algorithms

Jun 12, 2026cs.DS

Comparison Patrols on Drifting Orders: Certified Rank Maintenance, Evolving Planar Maxima, and Selection under Drifting Fitness

Rank-based selection in dynamic environments acts on order information that becomes stale while it is being used. Tournaments, elitism, truncation, and Pareto selection may therefore consume rankings that no longer match the current fitness order, while full re-evaluation competes with search for the same budget. This paper formulates the missing information layer as a data-structure problem. A hidden total order on

n

items drifts by adjacent transpositions, while a maintainer receives one truthful pairwise comparison per step and must answer rank queries continuously. We introduce the comparison patrol, a constant-time maintained-order structure using

3n+O(1)

words, one comparison per update, deterministic verification-age bounds, and per-item displacement certificates. We prove lower bounds showing that oblivious and location-oblivious maintainers incur expected Kendall error

Ω(\min(α,1)n)

, and show that the patrol operates at the same order. A bump invariant yields exact self-stabilization after drift-free corruption: if the maximum rank overstatement is

L

, recovery takes at most

L

aligned cycles and cannot finish before

L-1

. This gives a deterministic shock-recovery calculus and a crossover with full rebuild near

L\approx \log_2 n

. The maintained order is then transferred to evolving planar maxima and to evolutionary selection rules, giving deterministic bounds for truncation, tournament, elitist, and two-objective Pareto decisions under drifting fitness. Experiments up to

n=65{,}536

audit the certificates, recovery laws, equilibrium behavior, and equal-budget dynamic evolutionary loops, identifying when certified local rank maintenance outperforms global re-evaluation and when it should hand over.

Faruk Alpay, Levent Sarioglu

Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey

Pairwise Comparison Evolutionary Optimization Pairwise Ranking Runtime Analysis of Evolutionary Algorithms

Jun 11, 2026cs.NE

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

Jun 11, 2026cs.NE

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

Jun 11, 2026cs.NE

Runtime Analysis of the $(μ+ 1)$ -ES in a Homogenous Progress Model

We introduce a new simple model to study the fitness progress of Evolution Strategies (ES) in generic problems. In this model, we bypass the underlying fitness landscape and assume that the mutation of any individual produces an offspring whose fitness relative to the parent is given by an invariant distribution

Z

, such as a mean-shifted Gaussian. This serves as a prototypical model for the optimisation landscape when an evolution algorithm operates far from the global optimum. This simple model can be used to approximate the optimisation process for problems where it is intractable to model the exact fitness function, including tasks such as hyperparameter tuning in machine learning models. We rigorously analyse the expected growth rate

\mathcal{R}_μ

of the continuous steady-state

(μ+1)

-ES in this model. Unlike comma-selection strategies, the steady-state

(μ+1)

-ES maintains overlapping generations, introducing complex mathematical dependencies among surviving parents that make it harder to analyse. We give a general technique to analyse the the

(μ+ 1)

-ES by constructing modified processes whose growth rates provably sandwich that of the original process. These modified processes are then easier to analyse but still close enough to the true process to give a tight bound on the expected growth rate. When

Z = \mathcal{N}(-δ, 1)

and

μ\le e^δ

, we show that

\mathcal{R}_μ = \frac{\log^{1 + o(1)} μ}μ \mathcal{R}_1

.

Johannes Lengler, Raghu Raman Ravi

Eidgenössische Technische Hochschule Zürich, Switzerland

Evolutionary Optimization Evolution Strategies Runtime Analysis of Evolutionary Algorithms

Jun 10, 2026cs.NE

SPEA2 $^+$ : Improved Density Estimation in SPEA2 with Provable Runtime Guarantees

The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a popular and prominent evolutionary algorithm for solving multi-objective optimisation problems. Despite its popularity, theoretical analyses of SPEA2 have only appeared recently. Moreover, these analyses focus exclusively on how SPEA2 handles non-dominated solutions and disregard the algorithmic components responsible for handling dominated solutions. We conduct a first runtime analysis of SPEA2 for which these components are analysed. We prove that, unlike other prominent algorithms, including NSGA-II, NSGA-III and SMS-EMOA under the same setting of constant population size and duplicate elimination, SPEA2 is unable to cover the Pareto front of the OneTrapZeroTrap benchmark efficiently. Our results indicate that using k-th nearest-neighbour distance in the fitness assignment provides an insufficient signal to maintain diversity among dominated individuals. To address this issue, we propose an improved variant, SPEA2

^+

, that considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the performance of the original SPEA2 on simpler problems. Experimental results complement our theoretical findings.

Duc-Cuong Dang, Andre Opris, Dirk Sudholt

University of Passau, Passau, Germany

Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Jun 6, 2026cs.NE

Gray-Box Optimization and the Vertex Coloring Problem

Gray-box optimization is an approach for making some problem-specific information available to the algorithm while still relying on fitness information as the main guide to an optimum. This approach was shown to be beneficial in various combinatorial optimization tasks and neatly captures the continuum between fully black-box algorithms and tailored algorithms. In this work, we discuss different flavors of gray-box algorithms. We show that RLS can find a proper

2

-coloring in a bipartite graph starting from a random

2

-coloring, in an expected time of

\mathcal{O}(n \log n)

. In contrast, when starting from a proper

n

-coloring, the (1+1) EA cannot find such a coloring except when offered additional guiding on plateaus of the search space. Finally, we show the run time for this setting can be much improved by using gray-box operators.

Johanna Gasse, Antonia Heinen, Hendrik Higl +1

Hasso Plattner Institute University of Potsdam Potsdam, Germany

Evolutionary Optimization Metaheuristic Optimization Combinatorial Optimization Runtime Analysis of Evolutionary Algorithms

May 28, 2026cs.NE

Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function

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.

Martin S. Krejca, Carsten Witt

Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, IP Paris, France · DTU Compute, Technical University of Denmark, Denmark

Stochastic Optimization Evolutionary Optimization Combinatorial Optimization Runtime Analysis of Evolutionary Algorithms Genetic Algorithms

May 27, 2026cs.NE

A Fresh Look at Lamarckian Evolution and the Baldwin Effect

Baldwinian and Lamarckian evolution have existed for a long time in evolutionary algorithms (EAs) without ever dominating the academic literature or practical applications. In this work, we use modern empirical and theoretical methods to revisit Lamarckian and Baldwinian evolution and rigorously compare them with the generic Darwinian evolution. On the empirical side, we run a comprehensive suite of experiments on graphs from six different datasets from the recent GraphBench benchmark on Maximum Independent Set and Maximum Cut problems. Our results show that Baldwinian and Lamarckian evolution consistently outperform Darwinian evolution, confirming the great potential of local search augmented evolutionary algorithms. Notably, in the great majority of cases, all EAs outperform recent deep learning baselines and approach the performance of highly specialised heuristic and exact solvers. We furthermore report a high-performing set of generalist parameters for all studied evolution types that we hope will be of use to practitioners in future. On the theoretical side, we extend the existing DeceptiveLeadingBlocks benchmark to arbitrary block length

k

. For all constant

k

, we then prove asymptotically tight runtime bounds for the

(1+1)

EA in the three evolution types on this benchmark. For Baldwinian evolution, these are independent of

k

, whereas for the other two evolution types, the runtimes steeply increase with growing value of

k

.

Inès Benito, Johannes F. Lutzeyer, Benjamin Doerr

Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, France

Evolutionary Optimization Combinatorial Optimization Runtime Analysis of Evolutionary Algorithms

May 20, 2026cs.NE

Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization

Mixed-integer extensions of evolution strategies (ES) that discretize selected coordinates of sampled continuous vectors often impose a lower bound on the standard deviation of integer variables to prevent premature convergence. While these methods show promising empirical results, this handling can slow the convergence of continuous variables, and its impact has lacked a clear theoretical account. In this paper, we provide a convergence analysis of evolution strategies for mixed-integer optimization, inspired by the drift analysis of the (1+1)-ES in the continuous domain. Specifically, we consider two (1+1)-ES variants for mixed-integer domains: (1+1)-LB-ES, which introduces a lower bound on the standard deviation for integer variables, and (1+1)-LUB-ES, which combines both lower and upper bounds to enhance the convergence of the continuous variables. Focusing on the optimization phase after the integer variables have been optimized, we rigorously analyze their convergence behavior on a benchmark function designed for mixed-integer domains. Our results show that (1+1)-LB-ES can suffer from premature convergence when the number of integer variables is large, while (1+1)-LUB-ES achieves linear convergence under suitable parameter settings. These findings provide theoretical insights into the impact of integer handling on convergence performance and guidance for the design of mixed-integer ES.

Ryoki Hamano, Kento Uchida, Shinichi Shirakawa

CyberAgent · Yokohama National University

Evolutionary Optimization Evolution Strategies Runtime Analysis of Evolutionary Algorithms

May 17, 2026cs.AI

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination

Multi-party multi-objective optimization problems (MPMOPs) require consensus among autonomous decision makers and therefore differ from flattened many-objective formulations. Existing runtime theory for multi-objective evolutionary algorithms is largely tailored to single-party Pareto-front approximation and does not directly explain common-solution search in MPMOPs. We investigate cross-party recombination in two representative settings. On MP-JCG, a pseudo-Boolean benchmark with an explicit gap region, we prove that a payoff-guided mutation baseline faces a gap-crossing bottleneck requiring

Θ(n^2)

expected fitness evaluations. In contrast, an analytical CPR-NSGA-II variant discovers both common Pareto-optimal solutions in

O(n\log n)

expected evaluations by directly assembling complementary prefix and suffix templates distributed across party populations. Comparing this with the flattened four-objective formulation F-JCG, our full-front coverage analysis illustrates the additional coverage burden introduced by flattening. For BPBOMST, the bi-party, two-objective-per-party specialization of the multi-party multi-objective minimum spanning tree problem, we develop a layered support-cover analysis. For each common Pareto objective vector, the symmetric average projection induces an auxiliary bi-objective MST instance, and suitable support representatives yield a

2λ

-common approximation cover with

λ\in[1,2]

. We further derive an instance-parameterized expected runtime bound for a representative-pool CPR-NSGA-II variant using edge-union recombination and uniform repair. This bound separates the effects of local auxiliary-front filling, cross-party recombination shortcuts, and edge-union repair ambiguity.

Xiaolei Fang, Peilan Xu, Wenjian Luo

School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China.

Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms Multi-Objective Optimization

May 14, 2026cs.NE

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number

r > 2

of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an

r

-valued counterpart of the classic \oneminmax benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of

O(n^2 r^2 \log n)

and a near-tight lower bound of

Ω(n^2 r (r + \log n))

. We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of

O(n^2 r (r + \log n))

, matching our lower bound (which also holds for this variant). Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.

Mingfeng Li, Zheng Cheng, Weijie Zheng +1

School of Computer Science and Technology, National Key Laboratory of Smart Farm Technologies and Systems, International Research Institute for Artiﬁcial Intelligence, Harbin Institute of Technology, Shenzhen · 2Pengcheng Laboratory, Shenzhen, China · 3Laboratoire d’Informatique (LIX), CNRS, ´Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France

Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

May 11, 2026cs.NE

On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

In recent years, a theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical

m

-objective

m

-OneJumpZeroJump function (

m

-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes

m

-OJZJ asymptotically faster than NSGA-III without crossover for any number

m

of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on

4

-OJZJ when crossover is turned off.

Andre Opris

Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany

Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms Multi-Objective Optimization

Apr 16, 2026cs.NE

Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems

Pareto optimization via evolutionary multi-objective algorithms has been shown to efficiently solve constrained monotone submodular functions. Traditionally when solving multiple problems, the algorithm is run for each problem separately. We introduce multitasking formulations of these problems that are an effective way to solve multiple related problems with a single run. In our setting the given problems share a monotone submodular function

f

but have different knapsack constraints. We examine the case where elements within a constraint have the same cost and show that our multitasking formulations result in small Pareto fronts. This allows the population to share solutions between all problems leading to significant improvements compared to running several classical approaches independently. Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a

(1-1/e)

-approximation for each of the given problems. Our experimental investigations for the maximum coverage problem give further insight into the dynamics behind how the approach works and doesn't work in practice for problems where elements within a constraint also have varied costs.

Liam Wigney, Frank Neumann

Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

Submodular Optimization Evolutionary Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms Multi-Task Optimization