Best Order Sort: A New Algorithm to Non-dominated Sorting for Evolutionary Multi-objective Optimization

Finding the non-dominated sorting of a given set vectors has applications in Pareto based evolutionary multi-objective optimization (EMO), finding convex hull, linear optimization, nearest neighbor, skyline queries in database and many others. Among these, EMOs use this method for survival selection. The worst case complexity of this problem is found to be O(Nlog(M-1) N) when the number of objectives M is constant and the size of solutions N is varying. But this bound becomes too large when M depends on N. In this paper we are proposing a new algorithm with worst case complexity O(MN logN + MN2), however, with reduced running time in many objective cases. This algorithm can make use of the faster implementation of sorting algorithms. It removes unnecessary comparisons among the solutions which improves the running time. The proposed algorithm is compared with four other competing algorithms on three different datasets. Experimental results show that our approach, namely, best order sort (BOS) is computationally more efficient than all other compared algorithms with respect to running time.