Runtime Analysis of Evolutionary Algorithms

Follow this topic Ask about this topic

Runtime analysis asks how many fitness evaluations evolutionary algorithms need to reach an optimum or approximation, and how that cost depends on the problem and algorithm settings. Researchers use drift and fitness-level arguments, hitting-time and probability methods, and Markov models to analyze algorithms such as the (1+1) EA, genetic algorithms, and multi-objective methods on benchmarks including OneMax, Jump, and Pareto-front problems. The work examines mutation and crossover, population size and diversity, adaptive parameters, and settings such as dynamic or noisy objectives. A central challenge is that performance can change sharply with problem structure and parameter choices, while the complex population dynamics that may explain practical behavior remain difficult to bound tightly.

Latest papers

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

Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean
Oct 26, 2026Per Kristian LehreAutomated Algorithm Discovery Black-Box Optimization
School of Computer Science, University of Birmingham, UK
Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up
Oct 26, 2026Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca +1Multi-Objective Evolutionary Optimization Evolutionary Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees
Oct 26, 2026Benjamin Doerr, Martin S. Krejca, Noé WeeksMulti-Objective Evolutionary Optimization Multi-Objective Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Normale Supérieure, Paris, France
First Mathematical Runtime Analyses of Evolutionary Multitask Multi-Objective Optimization
Oct 15, 2026Danyang Zhang, Weijie ZhengEvolutionary Multitask Optimization Multi-Objective Evolutionary Optimization
School of Computer Science and Technology, State Key Laboratory of Smart Farm Technologies and Systems, International Research Institute for Artificial Intelligence, Harbin Institute of Technology, Shenzhen, China · Pengcheng Laboratory, Shenzhen, China
Early-Stopping Thresholds for ES-HyperNEAT: A Data-Driven Approach from Fitness Dynamics
Sep 11, 2026Romain Claret, Arthur Gygax, Michael O'Neill +2Early Stopping Evolutionary Optimization
University of Neuchâtel, Switzerland · Information Management Institute · Computer Science Department +1
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
Sep 11, 2026RenKai WangRuntime Analysis of Evolutionary Algorithms Sensitivity Analysis
Institute of Automation, Chinese Academy of Sciences (CASIA) · University of Chinese Academy of Sciences (UCAS)
On Scaling Coordinate-Based Neuroevolution: The Quadtree Bottleneck in ES-HyperNEAT
Aug 25, 2026Romain Claret, Michael O'Neill, Paul Cotofrei +1Neuroevolution Hypernetworks
University of Neuchâtel, Information Management Institute, Neuchâtel, Switzerland · University College Dublin, Natural Computing Research & Applications Group, Dublin, Ireland
Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints
Aug 11, 2026Liam Wigney, Frank NeumannSubmodular Optimization Evolutionary Multitask Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
Analysis of Memory-Runtime Trade-offs in Caching Strategies for Genetic Programming Symbolic Regression
Jul 31, 2026Jiaming Shi, Kei Sen Fong, Mehul MotaniGenetic Programming Cache Replacement
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
Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization
Jul 26, 2026Andre OprisMulti-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms
Faculty of Computer Science and Mathematics, University of Passau
Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles
Jul 24, 2026Konstantin Fackeldey, Christof SchütteStochastic Optimization Runtime Analysis of Evolutionary Algorithms
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
Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions
Jul 15, 2026Anton V. Eremeev, Valentin A. TopchiiRuntime Analysis of Evolutionary Algorithms Genetic Algorithms
Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values
Jun 16, 2026Narges Tavassoli Kejani, Andrew M. Sutton, Frank NeumannMulti-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms
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
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
Jun 14, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisBoolean Function Learning Genetic Programming
University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany
Comparison Patrols on Drifting Orders: Certified Rank Maintenance, Evolving Planar Maxima, and Selection under Drifting Fitness
Jun 12, 2026Faruk Alpay, Levent SariogluPairwise Comparison Evolutionary Optimization
Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey
The $(1 + 1)$ -EA in Dynamic Environments
Jun 11, 2026Georg Hasebe, Johannes Lengler, Raghu Raman RaviEvolutionary Optimization Black-Box Optimization
Eidgenössische Technische Hochschule Zürich, Switzerland
Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
Jun 11, 2026Joris Belder, Johannes Lengler, Raghu Raman RaviEvolutionary Optimization Black-Box Optimization
ETH Zürich, Switzerland
Runtime Analysis of the $(μ+ 1)$ -ES in a Homogenous Progress Model
Jun 11, 2026Johannes Lengler, Raghu Raman RaviEvolutionary Optimization Evolution Strategies
Eidgenössische Technische Hochschule Zürich, Switzerland
SPEA2 $^+$ : Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
Jun 10, 2026Duc-Cuong Dang, Andre Opris, Dirk SudholtEvolutionary Optimization Multi-Objective Evolutionary Optimization
University of Passau, Passau, Germany
Gray-Box Optimization and the Vertex Coloring Problem
Jun 6, 2026Johanna Gasse, Antonia Heinen, Hendrik Higl +1Evolutionary Optimization Metaheuristic Optimization
Hasso Plattner Institute University of Potsdam Potsdam, Germany
Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function
May 28, 2026Martin S. Krejca, Carsten WittStochastic Optimization Evolutionary Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, IP Paris, France · DTU Compute, Technical University of Denmark, Denmark
A Fresh Look at Lamarckian Evolution and the Baldwin Effect
May 27, 2026Inès Benito, Johannes F. Lutzeyer, Benjamin DoerrEvolutionary Optimization Combinatorial Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, France
Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization
May 20, 2026Ryoki Hamano, Kento Uchida, Shinichi ShirakawaEvolutionary Optimization Evolution Strategies
CyberAgent · Yokohama National University
Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination
May 17, 2026Xiaolei Fang, Peilan Xu, Wenjian LuoMulti-Party Multi-Objective Optimization Evolutionary Optimization
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.
First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables
May 14, 2026Mingfeng Li, Zheng Cheng, Weijie Zheng +1Evolutionary Optimization Multi-Objective Evolutionary Optimization
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
On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III
May 11, 2026Andre OprisEvolutionary Optimization Multi-Objective Evolutionary Optimization
Chair of Algorithms for Intelligent Systems, University of Passau, Passau, Germany
Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems
Apr 16, 2026Liam Wigney, Frank NeumannSubmodular Optimization Evolutionary Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
Apr 8, 2026Denis Antipov, Carola DoerrAlgorithm Selection Runtime Analysis of Evolutionary Algorithms
Sorbonne Université, CNRS, LIP6 Paris, France
Anytime Analysis on BinVal: Adaptive Parameters Help
Apr 8, 2026Timo Kötzing, Jurek SanderRuntime Analysis of Evolutionary Algorithms Evolutionary Optimization
Hasso Plattner Institute University of Potsdam Potsdam, Germany
Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
Apr 5, 2026Andre Opris, Denis AntipovEvolutionary Optimization Genetic Algorithms
University of Passau Passau, Germany · Sorbonne Université, CNRS, LIP6 Paris, France

Oct 26, 2026J/K move · Enter open · S save

Agentic Algorithm Design: LLMs that Propose, Formalise, and Prove Runtime Bounds for Evolutionary Algorithms in Lean

Per Kristian Lehre

School of Computer Science, University of Birmingham, UK

Automated Algorithm Discovery Black-Box Optimization LLMs for Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Open paper AskPDF arXiv

LLMs now prove hard theorems in Lean. Can they also design algorithms and prove their correctness and efficiency? LLM-guided design of optimisation heuristics (such as AlphaEvolve) is purely empirical. Automated theorem provers with LLMs prove given statements. So far, there has been little evidence that LLMs can do both: design an algorithm and guarantee its efficiency by a mathematical proof. We present a staged pipeline modelled after research methodology in design and analysis of evolutionary algorithms. The agent proposes black-box optimisation algorithms, and Lean guards filter out flawed designs. The agent then defines a potential function and proves drift bounds that guarantee an expected runtime improvement over the baseline algorithm. At no point in the pipeline are the algorithms compared empirically. The agent generates a black-box optimisation algorithm with expected runtime

O(n^2)

on a CycleUncover problem, where the classical (1+1) EA needs runtime

e^{Ω(n)}

. The pipeline also designs and analyses a black-box optimisation algorithm for integer-valued submodular minimisation with expected runtime

O(n^{2+2c})

, and it matches the classical runtime

O(n^2)

on LeadingOnes. Across 8 problem classes, 12 of 15 runs with frontier models complete the pipeline with a machine-checked expected-runtime bound. An ablation study shows that removing the staging and asking the agent to zero-shot an algorithmic design with a runtime guarantee leads to a copy of the seeded baseline algorithm (random search) or to incomplete proofs. Our study suggests that machine-checked specifications in Lean can replace empirical evaluation in open-ended algorithm discovery. To the best of our knowledge, this is the first example of an automated pipeline that designs efficient black-box optimisation algorithms with machine-checked runtime bounds in Lean.