Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization
Andre Opris
This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class $\text{CLIMB}$, where the parameter $\ell$ determines the size of the Pareto front. On this problem class, we analyze the runtime of GSEMO and the widely used NSGA-II. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a super-constant speedup for $\ell \in ω(\log(n)) \cap o(\sqrt{n \log(n)})$ in terms of fitness evaluations. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes that we propose in this paper, can cover the Pareto front of $\text{CLIMB}$ in expected $O(n \log(n) + \ell^2 \log(en/(n-2\ell+3)))$ evaluations, and that this bound is tight for $\ell = O(\sqrt{n \log(n)})$. In contrast, NSGA-II with a fixed population size of at least $4\ell$ requires expected $O(n\ell + n\log(n) + \ell^2 \log(en/(n-2\ell+3)))$ evaluations to cover the entire Pareto front of $\text{CLIMB}$, while still requiring expected $Ω(\ell n)$ evaluations to even find a Pareto-optimal search point. To the best of our knowledge, this is the first rigorous runtime analysis in bi-objective optimization that demonstrates a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, such as the evolution of population diversity over time, and employs the well-known family-tree method to prove the lower bound.
尚无 AI 解读，展示原文摘要