An Efficient Nondominated Sorting Algorithm for Large Number of Fronts
提出一种利用标量排序和加权二分搜索的非支配排序算法，在存在大量前沿时显著减少计算量，实验表明比现有算法更高效。
Nondominated sorting is a key operation used in multiobjective evolutionary algorithms (MOEA). Worst case time complexity of this algorithm is O(MN <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), where N is the number of solutions and M is the number of objectives. For stochastic algorithms like MOEAs, it is important to devise an algorithm which has better average case performance. In this paper, we propose a new algorithm that makes use of faster scalar sorting algorithm to perform nondominated sorting. It finds partial orders of each solution from all objectives and use these orders to skip unnecessary solution comparisons. We also propose a specific order of objectives that reduces objective comparisons. The proposed method introduces a weighted binary search over the fronts when the rank of a solution is determined. It further reduces total computational effort by a large factor when there is large number of fronts. We prove that the worst case complexity can be reduced to Θ(MNC <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (F + 1)), where the number of fronts is F and the maximum number of solutions per front is C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> ; however, in general cases, our worst case complexity is still O(MN <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). Our best case time complexity is O(MNlogN). We also achieve the best case complexity O(MNlogN + N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), when all solutions are in a single front. This method is compared with other state-of-the-art algorithms-efficient nondomination level update, deductive sort, corner sort, efficient nondominated sort and divide-and-conquer sort-in four different datasets. Experimental results show that our method, namely, bounded best order sort, is computationally more efficient than all other competing algorithms.