Hot off the Press: Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms

Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing performance guarantees for classic MOEAs on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we consider a large class of MOEAs including the (global) SEMO, SMS-EMOA, balanced NSGA-II, NSGA-III, and SPEA2. For these, we prove near-tight runtime guarantees for the four most common benchmark problems OneMinMax (OMM), CountingOnesCountingZeros (COCZ), LeadingOnesTrailingZeros (LOTZ), and OneJumpZeroJump (OJZJ), and this for arbitrary numbers of objectives. Our bounds depend only linearly on the size of the largest incomparable set, showing that MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of MOEAs. This paper for the Hot-off-the-Press track at GECCO 2025 summarizes the work Simon Wietheger and Benjamin Doerr. Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms. In Parallel Problem Solving from Nature – PPSN XVIII. 153-168, 2024. [12].