---
title: "A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update"
authors:
  - "Andre Opris"
doi: "10.24963/ijcai.2025/990"
url: "https://ijcai.org/proceedings/2025/990"
pdf: "https://ijcai.org/proceedings/2025/0990.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8903-8911"
track: "Main Track"
keywords:
  - "Search: S: Combinatorial search and optimisation"
  - "Search: S: Heuristic search"
  - "Search: S: Evolutionary computation"
---

# A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

Andre Opris

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8903-8911. DOI: [10.24963/ijcai.2025/990](https://doi.org/10.24963/ijcai.2025/990)

## Abstract

The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III of when and why it performs well are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(n^(k+d/2)+ N n ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size N is in 2^(O(n)) and at least (2n/d+1)^(d/2). Notably, NSGA-III is faster than NSGA-II by a factor of N/n^(d/2) for N=omega(n^(d/2)) . We also show that a stochastic population update provably guarantees a speedup of order (k/b)^(k-1) in the runtime where b>0 is a constant. Besides a paper of Wietheger and Doerr (PPSN 2024), this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved.