Optimal Distributions of Solutions for Maximizing the Minimum Crowding Distance for Two-Objective and Three-Objective Linear Pareto Fronts: Search Behavior Analysis of NSGA-II

In this paper, we discuss the optimal distributions of solutions for maximizing the minimum crowding distance on linear Pareto fronts of two- and three-objective problems. Our discussions are twofold. One is theoretical discussions to analytically derive the optimal distributions. The other is empirical discussions, which are based on a newly implemented indicator-based algorithm to maximize the minimum crowding distance. First, we show the upper bound on the minimum crowding distance, which is derived from the upper bound on the total crowding distance. Next, we theoretically derive the optimal distributions for maximizing the minimum crowding distance on two-objective linear Pareto fronts. Our analysis shows that two solutions always overlap in the optimal distributions when the population size is an even number. For an odd number population size, the optimal distribution cannot be uniquely specified except for some anchor solutions (i.e., many different distributions are optimal). The theoretically obtained optimal distributions are compared with experimental results by our indicator-based algorithm. Then, we show an example of optimal distributions for a three-objective linear Pareto front where the population size is a multiple of three. Our indicator-based algorithm is also compared with the standard NSGA-II algorithm and its steady-state variant.