Diversity-Preserving Mechanisms in NSGA-II: The Impact of Clustered Crowding Distance on Pareto Front Distribution

Abstract

One of the primary objectives in evolutionary multi-objective optimization is maintaining population diversity. The NSGA-II algorithm achieves this through an explicit diversity-preservation mechanism known as crowding distance. While the existing crowding distance calculation performs well for continuous multi-objective genetic algorithms, its effectiveness significantly decreases in problems that involve discrete design variables, especially when the Pareto-optimal front contains repetitive solutions. In discrete design variable cases, the likelihood of duplicate solutions is comparatively high. To address this challenge, a modified approach, termed the clustered crowding distance, is proposed. This method categorizes the set of solutions into several subgroups, ensuring that each subgroup contains only non-repetitive solutions. The crowding distance is then calculated within these subgroups sequentially until the population reaches the desired size. The proposed methodology was tested on three benchmark problems. Experimental results demonstrate that the clustered crowding distance provides superior performance compared to the traditional crowding distance approach. Across all test instances, the Pareto-optimal fronts generated using the clustered crowding distance exhibit a more uniform and balanced distribution of solutions.