Runtime Analysis of Evolutionary Algorithms

Overview

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

CardsList

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

  1. A Finite Markov Chain Analysis of the Simplified Swarm Optimisation Update Rule

    Nov 12, 2026Wei-Chang YehEvolutionary OptimizationRuntime Analysis of Evolutionary Algorithms

  2. Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

    Nov 11, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisGenetic ProgrammingRuntime Analysis of Evolutionary Algorithms

  3. 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 +1Cooperative Co-EvolutionMulti-Objective Evolutionary Optimization

  4. A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees

    Oct 26, 2026Benjamin Doerr, Martin S. Krejca, Noé WeeksMulti-Objective Evolutionary OptimizationMulti-Objective Optimization

  5. First Mathematical Runtime Analyses of Evolutionary Multitask Multi-Objective Optimization

    Oct 15, 2026Danyang Zhang, Weijie ZhengEvolutionary Multitask OptimizationMulti-Objective Evolutionary Optimization

  6. Early-Stopping Thresholds for ES-HyperNEAT: A Data-Driven Approach from Fitness Dynamics

    Sep 11, 2026Romain Claret, Arthur Gygax, Michael O'Neill +2Early StoppingEvolutionary Optimization

  7. On Scaling Coordinate-Based Neuroevolution: The Quadtree Bottleneck in ES-HyperNEAT

    Aug 25, 2026Romain Claret, Michael O'Neill, Paul Cotofrei +1NeuroevolutionHypernetworks

  8. Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

    Aug 11, 2026Liam Wigney, Frank NeumannSubmodular OptimizationEvolutionary Multitask Optimization

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

    Jul 31, 2026Jiaming Shi, Kei Sen Fong, Mehul MotaniGenetic ProgrammingCache Replacement

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

    Jul 24, 2026Konstantin Fackeldey, Christof SchütteStochastic OptimizationRuntime Analysis of Evolutionary Algorithms

  11. 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 OptimizationRuntime Analysis of Evolutionary Algorithms

  12. Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

    Jun 14, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisBoolean Function LearningGenetic Programming

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

    Jun 12, 2026Faruk Alpay, Levent SariogluPairwise ComparisonEvolutionary Optimization

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

    Jun 11, 2026Georg Hasebe, Johannes Lengler, Raghu Raman RaviEvolutionary OptimizationBlack-Box Optimization

  15. Improved Runtime Bound for the (μ+1)(μ+ 1) EA on BinVal

    Jun 11, 2026Joris Belder, Johannes Lengler, Raghu Raman RaviEvolutionary OptimizationBlack-Box Optimization

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

    Jun 11, 2026Johannes Lengler, Raghu Raman RaviEvolutionary OptimizationEvolution Strategies

  17. Gray-Box Optimization and the Vertex Coloring Problem

    Jun 6, 2026Johanna Gasse, Antonia Heinen, Hendrik Higl +1Evolutionary OptimizationMetaheuristic Optimization

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

    May 28, 2026Martin S. Krejca, Carsten WittStochastic OptimizationEvolutionary Optimization

  19. A Fresh Look at Lamarckian Evolution and the Baldwin Effect

    May 27, 2026Inès Benito, Johannes F. Lutzeyer, Benjamin DoerrEvolutionary OptimizationCombinatorial Optimization

  20. Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization

    May 20, 2026Ryoki Hamano, Kento Uchida, Shinichi ShirakawaEvolutionary OptimizationEvolution Strategies

  21. 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 OptimizationEvolutionary Optimization

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

    May 14, 2026Mingfeng Li, Zheng Cheng, Weijie Zheng +1Evolutionary OptimizationMulti-Objective Evolutionary Optimization

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

    May 11, 2026Andre OprisEvolutionary OptimizationMulti-Objective Evolutionary Optimization

  24. Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems

    Apr 16, 2026Liam Wigney, Frank NeumannSubmodular OptimizationEvolutionary Optimization