  The NSGA-II is proven to encounter difficulties for more than two objectives,
and the deduced reason is the crowding distance computed by regarding the
different objectives independently. The recent theoretical efficiency of the
NSGA-III and the SMS-EMOA also supports the deduced reason as both algorithms
consider the dependencies of objectives in the second criterion after the
non-dominated sorting but with complicated structure or difficult computation.
However, there is still a question of whether a simple modification of the
original crowding distance can help.
  This paper proposes such a variant, called truthful crowding distance. This
variant inherits the simple structure of summing the component for each
objective. For each objective, it first sorts the set of solutions in order of
descending objective values, and uses the smallest normalized L1 distance
between the current solution and solutions in the earlier positions of the
sorted list as the component. Summing up all components gives the value of
truthful crowding distance. We call this NSGA-II variant by NSGA-II-T that
replaces the original crowding distance with the truthful one, and that
sequentially updates the crowding distance value after each removal.
  We prove that the NSGA-II-T can efficiently cover the full Pareto front for
many-objective mOneMinMax and mOJZJ, in contrast to the exponential runtime of
the original NSGA-II. Besides, we also prove that it theoretically achieves a
slightly better approximation of the Pareto front for OneMinMax than the
original NSGA-II with sequential survival selection. Besides, it is the first
NSGA-II variant with a simple structure that performs well for many objectives
with theoretical guarantees.
