Abstract
This work conducts a first theoretical analysis studying how well theNSGA-III approximates the Pareto front when the population size $N$ is lessthan the Pareto front size. We show that when $N$ is at least the number $N_r$of reference points, then the approximation quality, measured by the maximumempty interval (MEI) indicator, on the OneMinMax benchmark is such that thereis no empty interval longer than $\lceil\frac{(5-2\sqrt2)n}{N_r-1}\rceil$. Thisbound is independent of $N$, which suggests that further increasing thepopulation size does not increase the quality of approximation when $N_r$ isfixed. This is a notable difference to the NSGA-II with sequential survivalselection, where increasing the population size improves the quality of theapproximations. We also prove two results indicating approximation difficultieswhen $N<N_r$. These theoretical results suggest that the best setting toapproximate the Pareto front is $N_r=N$. In our experiments, we observe thatwith this setting the NSGA-III computes optimal approximations, very differentfrom the NSGA-II, for which optimal approximations have not been observed sofar.