Update on non-dominated sorting measurements

This is an update on a previous post [Sch25] about a new implementation of non-dominated sorting for PGAPack. Non-dominated sorting is a central component of most multi-objective optimization implementations.

In the recent post I did not mention how many generations my test ran. The number of generations in the last and in the following tests was 200. In the last test the code was compiled without optimization. The following measurements were made with -O3 the best optimization gcc offers. I noticed that my implementation of the evaluation function for the DTLZ-1 test [DTLZ05] is quadratic in the number of objectives so I feared this would influence the tests. It turns out it didn't, the overhead even for 20 objectives is still too low to be noticeable.

In addition to the first tests I'm now measuring – in addition to the overall time – the time just for the non-dominated sorting. So in the following we have two types of graphics, the ones where the title is starting with "Overall" include the time of evaluation function and whatever the algorithm is doing for bookkeeping. The ones starting with "Non-dominated" just measure the time for the non-dominated sorting.

So lets first see the overall times, compared to my last post [Sch25] this time with optimization turned on.

I've also plotted the absolute difference between measurements in the following. Note that the absolute difference when measuring non-dominated sorting times only vs. the difference when measuring overall times are visually identical, they differ only by a few milliseconds (as we would expect). We see that the absolute differences grow faster than linear which we would expect since the old non-dominated sorting algorithm grows quadratically with the population size and this drowns out the smaller growth of the new algorithm.

Finally the following graphics displays the speedups I'm getting. Note that now similar to Jensen [Jen03] I'm getting higher times for the new algorithm for large numbers of objectives and small number of individuals. The absolute difference is very small, in the previous graphics you can see the difference only when you zoom in on the first two measurements with population size 100 and 200. The absolute difference is below 30ms for 200 generations. So I'm not going to code special cases for different population sizes – this would also be difficult as the population size when this would make sense differs with CPU speed as we can see in my previous blog post [Sch25] where we did not see a slowdown (with optimization turned off) with the new algorithm. In addition you typically need larger populations when using more objectives to cover the Pareto front [Jen03].

The following graphics contain the measurements for just the computation of the non-dominated sorting. When looking at the speedup (both, in the previous plot as well as the one at the end of the following graphics), especially when we turn off the traces for 2, 3, and 5 objectives (you can do this yourself in legend on the right of the graphics), we see that the growth is sub-linear. We're dividing here times that grow quadratically by times that grow (a little) more than linear. So the fraction is growing sub-linear as expected. But don't underestimate the efficacy of the new algorithm: The absolute difference (as seen in one of the graphics above) is growing faster than linear.

The script used for the measurements, the script for plotting and the measured data (and the old measured data) are available if someone want to reproduce this. The example is in PGAPack in the directory examples/nsgaii but the version with the new non-dominated sorting algorithm and timing instrumentation for the test is not yet released as of this writing.