Space-Partitioned ND-Trees for the Dynamic Nondominance Problem

We present techniques for improving the efficiency of ND-trees in the solution of the dynamic nondominance problem, i.e., for building and maintaining a Pareto archive. We propose algorithms for (re)building a tree from a set of nondominated points, either as a space-partitioned ND-tree or by a clustering approach. Numerical experiments confirm that rebuilding the tree at intervals, combined with modified strategies for updating the lower and upper bounds in each node and for computing the distances of points to subtrees in between the rebuilds, can lead to significant speedups over using plain ND-tree-based updates throughout, in particular for higher dimensions.