Algorithms: Non‐Dominated Tree

@article{ ens-ndt,
    author     = {Patrik Gustavsson and Anna Syberfeldt},
    title      = {A New Algorithm Using the Non-Dominated Tree
                  to Improve Non-Dominated Sorting},
    journal    = {Evolutionary Computation},
    year       = {2017},
    doi        = {10.1162/EVCO_a_00204},
    note       = {Early Access},
    publisher  = {MIT Press},
    langid     = {english}
}

This is a new algorithm, called ENS-NDT, based on k-d trees to significantly improve performance of domination queries.

When used in evolutionary multiobjective settings, this algorithm is typically insanely fast, since the assumptions, which it is built atop, align well with the practices of evolutionary computation. However, it can be squared out when most objectives are positively correlated: a test consisting of N points like (x, x, ..., x, -x) makes this algorithm work in Θ(N^2 * M) time. If you look for more predictable performance, check this family of algorithms.

This algorithm technically belongs to the ENS family, so its instances can be achieved using:

• ENS.getENS_NDT(int threshold) -- returns an instance of ENS-NDT using the given threshold to stop splitting tree nodes. The optimal threshold is currently an open question, however, it seems that 8 is quite a good value.
• ENS.getENS_NDT_Arrays() -- returns an instance of ENS-NDT using the array-based implementation and a threshold size of 2. This implementation is faster than getENS_NDT(2), however, it might be slower on some inputs than, say, getENS_NDT(8). This implementation also is garbage-free (no load for a garbage collector).