Fast non dominated sorting

Specific Domains Optimization (Mathematical)
21

It seems to me that most presented algorithm have quadratic complexity. They are O(n\ \log n) versions for planar points (see below). Maybe this could be adapted to your case. Nevertheless, complexity analysis seems absent from this thread.

S. Felsner and L. Wernisch. Maximum k-chains in planar point sets:
Combinatorial structure and algorithms. SIAM Journal on Computing;
28(1):192–209, 1999.
M. Jensen. Reducing the run-time complexity of multiobjective EAs:
The NSGA-II and other algorithms. IEEE Transactions on Evolutionary
Computation, 7(5):503–515, 2003."

4 Likes
22

NDS algorithms mentioned here are more or less naive versions of NDS. But, non-dominated sorting is a very delicate process with significant dependence on the “scores” space distribution and number of points (algorithm complexity is very important in a case of large number of score points).

So, firstly, I propose to implement some more sophisticated NDS algorithms. See Maxim Buzdalov github and the following slides for more info.