Limiting Index Sort: A New Non-Dominated Sorting Algorithm and its Comparison to the State-of-the-Art

摘要

An important problem in the realm of evolutionary multi-objective optimization (MOO) is that of finding all non-dominated fronts (NDFs). We specifically address the computational efficiency of the non-dominated sorting algorithm for finding the non-dominated fronts for the NSGA-II algorithm. We introduce the Limiting Index Sort (LIS) algorithm which improves on the existing state-of-the-art algorithm for datasets which are positively correlated or uncorrelated. LIS indexes individuals based on their scores in each objective, and intelligently iterates through the index to limit the number of comparisons required between individuals. LIS also makes use of a stopping condition, allowing it to exclude some individuals from the skyline without comparing them to any other individuals. LIS was compared to two other state-of-theart non-dominated sorting algorithms, the Sort and Limit Skyline Algorithm (SaLSa), and the Divide-and-Conquer (D&C) approach. LIS outperformed SaLSa in all tests, and it outperformed D&C when sorting individuals with positively correlated or uncorrelated objective scores, except for sorting large, uncorrelated, datasets on many objectives. LIS outperformed D&C for sorting small, negatively correlated datasets on three or five objectives. By understanding the appropriate non-dominated sorting algorithm to use in different situations, NSGA-II can be utilized more efficiently for MOO. This will allow optimizations to be run with larger population sizes, more objectives, or for more generations, which should ultimately increase the quality of solutions returned by the algorithm.