A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization

Recent mathematical runtime analyses have shown that the crowding distance used by the NSGA-II multi-objective optimizer does not well reflect how isolated, and hence worth keeping, solutions are. This has provably led to drastic difficulties when the number of objectives is three or more. Based on the insights of these works, we design a variant of the crowding distance, called truthful crowding distance, and analyze the resulting truthful NSGA-II with mathematical means. (i)We show that it solves the many-objective versions of the OMM, COCZ, LOTZ, and OJZJ_k problems in the same (polynomial) asymptotic runtimes as the NSGA-III and the SMS-EMOA, contrasting the exponential lower bounds for the classic NSGA-II. (ii) For the bi-objective versions of these problems, our NSGA-II maintains the good performance of the classic NSGA-II, but is successful already with population sizes smaller by a constant factor. (iii) For the bi-objective OMM problem, we observe a (minimally) better performance in approximating the Pareto front. These results indicate that our truthful crowding distance is an interesting alternative to the classic crowding distance.