Nondominated points and sorting#
Identifying nondominated points#
The following plots compare the speed of finding nondominated solutions, equivalent to moocore.is_nondominated(). We test both keep_weakly=False (the default) and keep_weakly=True. The former is only supported by BoTorch and paretoset. Thus, for the purpose of benchmarking the other packages with keep_weakly=False, we remove duplicated points from the data and exclude this time from the results. This makes all packages, except moocore, BoTorch and paretoset, seem faster than they actually are, because the user is forced to remove duplicated points when using them.
For 2D and 3D, the plots show that moocore is 10 times faster than DESDEO and paretoset and 100-1000 times faster than the other packages. fast-pareto claims to implement a \(O(n\log n)\) algorithm for 3D, but the benchmarks below indicate a \(O(n^2)\) complexity, similar to other packages and significantly slower than moocore.
For dimensions larger than 3, moocore.is_nondominated() uses the
best-known \(O(n\log^{m-2} n)\) algorithm. fast-pareto claims to be
using a \(O(n\log^{m-2} n)\) algorithm, but the benchmarks suggest that it
uses a \(O(m n^2)\) algorithm, although slower than most other packages and
almost 100 times slower than moocore. The following plots with
keep_weakly=True show that moocore is at least 10 times faster than the
other packages, even for 10D.
Similar results are obtained with keep_weakly=False, however, this setting
is only supported by moocore, BoTorch and paretoset, thus the other
packages are actually slower to use than reported here, because the user is
forced to remove duplicated points when using them.
Nondominated Sorting (Pareto ranking)#
Nondominated sorting (or Pareto ranking) assigns a rank to each point according
to Pareto-optimality. It can be used to split a set of points into layers of
nondominated fronts. For more details, see moocore.pareto_rank(). This
function in moocore uses a \(O(n \log n)\) algorithm for 2 dimensions
and a \(O(n^2\log n)\) algorithm for 3 dimensions. As the plots show, this
makes moocore significantly faster than paretoset, pymoo and
DESDEO. With higher dimensions, moocore uses a \(O(n^2\log^{m-2}n)\)
algorithm instead of the \(O(n^3)\) algorithm in paretoset and DESDEO
(latter is compiled with Numba). In these benchmarks points are sampled
uniformly at random within the hypercube.
