Identify, remove and rank dominated points according to Pareto optimality

Identify nondominated points with is_nondominated() and remove dominated ones with filter_dominated().

any_dominated() quickly detects if a set contains any dominated point.

pareto_rank() ranks points according to Pareto-optimality, which is also called nondominated sorting (Deb et al. 2002) .

Usage

is_nondominated(x, maximise = FALSE, keep_weakly = FALSE)

filter_dominated(x, maximise = FALSE, keep_weakly = FALSE)

any_dominated(x, maximise = FALSE, keep_weakly = FALSE)

pareto_rank(x, maximise = FALSE)

Arguments

x: matrix()|data.frame()
Matrix or data frame of numerical values, where each row gives the coordinates of a point.
maximise: logical()
Whether the objectives must be maximised instead of minimised. Either a single logical value that applies to all objectives or a vector of logical values, with one value per objective.
keep_weakly: logical(1)
If FALSE, return FALSE for any duplicates of nondominated points, except the last one.

Value

is_nondominated() returns a logical vector of the same length as the number of rows of data, where TRUE means that the point is not dominated by any other point.

filter_dominated() returns a matrix or data.frame with only mutually nondominated points.

any_dominated() returns TRUE if x contains any (weakly-)dominated points, FALSE otherwise.

pareto_rank() returns an integer vector of the same length as the number of rows of data, where each value gives the rank of each point.

Details

Given \(n\) points of dimension \(m\), the current implementation uses the well-known \(O(n \log n)\) dimension-sweep algorithm (Kung et al. 1975) for \(m \leq 3\) and the naive \(O(m n^2)\) algorithm for \(m \geq 4\). The best-known \(O(n(\log_2 n)^{m-2})\) algorithm for \(m \geq 4\) (Kung et al. 1975) is not implemented yet.

pareto_rank() is meant to be used like rank(), but it assigns ranks according to Pareto dominance, where rank 1 indicates those solutions not dominated by any other solution in the input set. Duplicated points are kept on the same front. When ncol(data) == 2, the code uses the \(O(n \log n)\) algorithm by Jensen (2003) . With higher dimensions, it uses the naive \(O(n^3)\) algorithm.

References

Kalyanmoy Deb, A Pratap, S Agarwal, T Meyarivan (2002). “A fast and elitist multi-objective genetic algorithm: NSGA-II.” IEEE Transactions on Evolutionary Computation, 6(2), 182–197. doi:10.1109/4235.996017 .

M T Jensen (2003). “Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms.” IEEE Transactions on Evolutionary Computation, 7(5), 503–515.

H T Kung, F Luccio, F P Preparata (1975). “On Finding the Maxima of a Set of Vectors.” Journal of the ACM, 22(4), 469–476. doi:10.1145/321906.321910 .

Author

Manuel López-Ibáñez

Examples

S = matrix(c(1,1,0,1,1,0,1,0), ncol = 2, byrow = TRUE)
is_nondominated(S)
#> [1] FALSE  TRUE  TRUE FALSE
is_nondominated(S, maximise = TRUE)
#> [1]  TRUE FALSE FALSE FALSE
filter_dominated(S)
#>      [,1] [,2]
#> [1,]    0    1
#> [2,]    1    0
filter_dominated(S, keep_weakly = TRUE)
#>      [,1] [,2]
#> [1,]    0    1
#> [2,]    1    0
#> [3,]    1    0
any_dominated(S)
#> [1] TRUE
any_dominated(S, keep_weakly = TRUE)
#> [1] TRUE
any_dominated(filter_dominated(S))
#> [1] FALSE
path_A1 <- file.path(system.file(package="moocore"),"extdata","ALG_1_dat.xz")
set <- read_datasets(path_A1)[,1:2]
is_nondom <- is_nondominated(set)
cat("There are ", sum(is_nondom), " nondominated points\n")
#> There are  583  nondominated points

if (requireNamespace("graphics", quietly = TRUE)) {
   plot(set, col = "blue", type = "p", pch = 20)
   ndset <- filter_dominated(set)
   points(ndset[order(ndset[,1]),], col = "red", pch = 21)
}


ranks <- pareto_rank(set)
str(ranks)
#>  int [1:23260] 13 24 20 22 22 5 23 5 16 20 ...
if (requireNamespace("graphics", quietly = TRUE)) {
   colors <- colorRampPalette(c("red","yellow","springgreen","royalblue"))(max(ranks))
   plot(set, col = colors[ranks], type = "p", pch = 20)
}