Fast optimized non dominated sorting algorithms

General Usage
1

I am looking for any Julia fast non dominated sorting (NDS) code. I just found the following thread, but algorithms here are very naive with quadratic complexity and no parallelization.

Are there any more sophisticated NDS algorithms implemented in Julia?

Add remark: I am speaking about NDS problem on ~ 100k-500k points in 5 dimensional space. For this size of problems takes available O(N^2) NDS algorithms unacceptable computing time.

Thanks in advance for any help…

2

I’m not familiar with this field of work, so I’ll just post a bunch of links to code that seems to be related:

The last one seems to be a copy of the code from the third link (or maybe vice versa).

These generally mention Deb2002 (“A fast and elitist multiobjective genetic algorithm: NSGA-II”) as the reference, and it doesn’t seem like there’s anything that references the 2018 algorithm you link to.

2 Likes
4

Thanks … But all these algorithms are more or less identical copies of the basic naive version of NDS algorithm.

I am looking for more sophisticated Julia implementations based on algorithms mentioned here.

5

I understand. As I said in my last sentence, it doesn’t seem like that’s been implemented in Julia yet, at leats in any publicly available package.

Would you be interested in doing such an implementation? Would that be a general improvement to the algorithm applicable to most users (and so perhaps belonging as a PR to Metaheuristics.jl), or would it only be relevant in massively parallel use cases?

6

Yes, you are probably right.

If you take a look on codes at Maxim Buzdalov GitHub, you can see, that these codes are far more complex. I am not able now to rewrite these codes from Java to Julia.

All these, more sophisticated, NDS codes are significantly better than the naive version, even in a case of serial run. So, its implementation to the Julia will be beneficial for everybody.

Just for info:
N = 1e5 % number of point
D = 5 % dimension

single-thread run of
Julia naive NDS implementation (optimized for speed by Julia Sarrays): 6.5sec
Java ( Jensen-Fortin-Buzdalov divide-and-conquer method): 0.6 sec

multi-thread (6 thread) run of
Julia naive NDS implementation (optimized for speed by Julia Sarrays): no support
Java ( Jensen-Fortin-Buzdalov divide-and-conquer method): 0.28 sec

N = 2e5 % number of point
D = 5 % dimension

single-thread run of
Julia naive NDS implementation (optimized for speed by Julia Sarrays): 26.4sec
Java ( Jensen-Fortin-Buzdalov divide-and-conquer method): 1.5 sec

multi-thread (6 thread) run of
Julia naive NDS implementation (optimized for speed by Julia Sarrays): no support
Java ( Jensen-Fortin-Buzdalov divide-and-conquer method): 0.35 sec

2 Likes
7

Thanks a lot for the info and for doing the comparisons.

With the Java implementation, which one of the implementations did you use for these measurements? getRedBlackTreeSweepImplementation ?

By the way, it looks like the Python implementation is relatively simpler in terms of code, implementing only the Buzdalov2014 paper rather a combination of three papers as the Java version does. So, for anyone interested in implementing this, the Python version would probably make for a good starting point.

8

I do not know exactly, sorry. I am using compiled nds_buzdalov.jar file prepared by Maxim Buzdalov for me. Furthermore, I am running this JAR file from MATLAB.

Actually, I am starting my transition from MATLAB to Julia. So, I am looking for native equivalents of my crucial codes. So far, the transition looks like a long-run, and I am not sure if I will be successful :frowning:

1 Like
9

The fact that we have 4 different implementation of the bad version in Julia really suggests a need for a good version. I think Julia’s compiler also has a bad version for one of it’s analysis passes as well.

1 Like