Speeding Up the NSGA-II via Dynamic Population Sizes
For practitioners using multi-objective evolutionary algorithms, this work offers a principled way to reduce runtime by dynamically adjusting population size, with theoretical guarantees on benchmark problems.
The paper proposes a dynamic NSGA-II that starts with a small population and doubles it periodically, proving it computes the Pareto front of OneMinMax in O(n log^2 n) evaluations versus Θ(n^2 log n) for static NSGA-II, and O(n^k log^2 n) for OneJumpZeroJump versus Θ(n^{k+1}).
Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-offs (the Pareto optima) simultaneously, MOEAs are typically run with a large population of solution candidates. This slows down the algorithm and renders the choice of the population size a crucial design decision. In this work, we aim to overcome these difficulties by proposing the dynamic NSGA-II, a variant of the well-known NSGA-II that starts with a small initial population and doubles it after a user-specified number $τ$ of function evaluations, up to a maximum size of $N_{max}$. We prove that the dynamic NSGA-II with optimal parameters computes the Pareto front of the OneMinMax benchmark of size $n$ with high probability in $O(n \log^2 n)$ function evaluations, which is considerably faster than the $Θ(n^2 \log n)$ runtime of the static NSGA-II with optimal parameters. For the OneJumpZeroJump benchmark with gap size $k$, we show a runtime of $O(n^k \log^2 n)$, improving upon the known runtime of $Θ(n^{k+1})$. We also propose a variant that uses the initial population size for a longer period and achieves slightly better performance. Finally, we show that a simple concurrent-run strategy turns our dynamic NSGA-II variants into parameter-less algorithms that exceed the above runtimes only by a logarithmic factor and hence still outperform the static NSGA-II by a factor of $\tildeΩ(n)$.