Identify, remove and rank dominated points according to Pareto optimality

Usage

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

filter_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. Which of the duplicates is identified as nondominated is unspecified due to the sorting not being stable in this version.

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.

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$.

pareto_rank() is meant to be used like rank(), but it assigns ranks according to Pareto dominance. Duplicated points are kept on the same front. When ncol(data) == 2, the code uses the $O(n \log n)$ algorithm by Jensen (2003) .

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

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)
}