# A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)

arXiv: https://arxiv.org/abs/2406.16116 · HTML: https://mlsanity.com/paper/2406.16116/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2024.

## Built on by (most cited first, 5 of 5)

- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [Runtime Analysis of Evolutionary Algorithms for Multi-party Multi-objective Optimization](https://mlsanity.com/paper/2501.16336/) (2025)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Evolutionary algorithms (EAs) have emerged as a predominant approach for addressing multi-objective optimization problems. However, the theoretical foundation of multi-objective EAs (MOEAs), particularly the fundamental aspects like running time analysis, remains largely underexplored. Existing theoretical studies mainly focus on basic MOEAs, with little attention given to practical MOEAs. In this paper, we present a running time analysis of strength Pareto evolutionary algorithm 2 (SPEA2) for the first time. Specifically, we prove that the expected running time of SPEA2 for solving three commonly used multi-objective problems, i.e., mOneMinMax, mLeadingOnesTrailingZeroes, and m-OneJumpZeroJump, is O(μ n· minmlog n, n), O(μ n2), and O(μ nk · minmn, 3m/2), respectively. Here m denotes the number of objectives, and the population size μ is required to be at least (2n/m+1)m/2, (2n/m+1)m-1 and (2n/m-2k+3)m/2, respectively. The proofs are accomplished through general theorems which are also applicable for analyzing the expected running time of other MOEAs on these problems, and thus can be helpful for future theoretical analysis of MOEAs.