DDA-ENS: Dominance Degree Approach based Efficient Non-dominated Sort

In Pareto based multi- and many-objective evolutionary algorithms (MOEAs and MaOEAs), non-dominated sorting is an important step that divides the set of solutions into different disjoint non-dominated fronts. In the last 20 years, there have been various approaches proposed for non-dominated sorting. Recently, an approach known as Dominance Degree Approach for Non-Dominated Sorting (DDA-NS) has been proposed. This approach guarantees that the number of floating-point comparisons is always bounded by O(M N log N) for N solutions and M objectives, which is not true for various approaches. However, the worst-case time complexity of DDANS is recently proved to be Θ(MN² + N³). In this paper, we develop an approach on the top of DDA-NS, which also guarantees (M N log N) floating-point comparisons and its worst-case time complexity is proved to be Θ(MN²) as opposed to Θ(MN² + N³) of DDA-NS.

I. Introduction

Non-dominated sorting is one of the essential steps in Pareto based MOEAs and MaOEAs [1], [2]. It has application in other domains like data clustering, graph theory, computer vision, economics and game theory, database and others [2]. Non-dominated sorting sorts the solutions into different non-dominated fronts which are arranged in decreasing order of their dominance. In MOEAs, the set of solutions are often referred to as the population. Let be a population of N solutions in M-dimensional objective space. i^th solution of ; s_i is denoted as . A solution s_i in M-dimensional objective space is a vector of size M represented as where is the objective value of solution s_i for m^th (1 ≤ m ≤ M) objective.