A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization
针对NSGA-II在多目标（三个及以上）优化中因拥挤距离失效的问题，设计了“真实拥挤距离”，并通过数学分析证明新算法在多个基准问题上达到多项式时间，优于原算法的指数时间。
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 OJZJk 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.