Dynamic population sizes speed up multiobjective evolutionary algorithms by 10x+

A new arXiv paper by Andre Opris provides the first rigorous theoretical proof that dynamic population sizes in evolutionary multiobjective optimization can yield provable speedups. The study focuses on the widely used NSGA-II and GSEMO algorithms, testing them on a novel bi-objective problem class called CLIMB. The key finding: NSGA-II with a fixed population size requires Omega(n^{1.5}) fitness evaluations, while a dynamic variant (NSGA-II-DYN) achieves O(n log n) – a super-constant improvement. GSEMO, which inherently uses a dynamic population, matches that O(n log n) bound.

The analysis builds on concepts from single-objective optimization, particularly population diversity dynamics, and employs the family-three method to prove the lower bound. This work marks a milestone because, until now, the benefits of dynamic population sizing in multiobjective algorithms were poorly understood despite widespread heuristic use. By formally demonstrating when and why dynamic sizes help, the paper provides both a theoretical foundation for practitioners and a benchmark (CLIMB) for future algorithm comparisons. It also highlights that GSEMO can outperform NSGA-II on certain problems – a result with immediate implications for research teams working on multiobjective optimization in AI, engineering, and operations research.