[R] Making a ranking algorithm more efficient

Waichler, Scott R Scott.Waichler at pnl.gov
Tue Jun 1 22:05:27 CEST 2004


I would like to make a ranking operation more efficient if possible.
The goal is to rank a set of points representing objective 
function values such that points which are "dominated" by no 
others have rank 1, those which are dominated by one other point 
have rank 2, etc.  In the example with two dimensions below, objective
functions 1 and 2 are to be minimized.  Points a-e are non-dominated,
rank 1 points.  Point f is rank 2 because point b is superior, and 
point g is rank 2 because point d is superior.  Point h is rank 3 
because points c and d are both superior.

       | a 
       |    f
       |  b
       |       h          (figure requires monospaced, plain-text
display)
Obj 1  |     c    
       |         g 
       |      d     
       |            e
       |____________________

              Obj 2
 

I need to compute the ranks of the rows of a matrix, where each row
represents a point in objective space and the columns
contain the objective function values to be minimized.  
Rank is defined as the number of points with objective function 
values less than or equal to the current point (including the current 
point).  I've written the following function with two loops:

  PARETO.RANK <- function(obj.array) {
    obj.array <- unique(obj.array)
    
    ind.row <- 1:nrow(obj.array)
    ind.col <- 1:ncol(obj.array)

    rank.vec <- rep(NA, length(ind.row)) # initialize

    # Loop thru rows (points in objective function space)
    for(i in ind.row) { 
      set <- ind.row
      for (j in ind.col) {  # Loop thru objective functions
        set <- set[ obj.array[set,j] <= obj.array[i,j] ]
      }
      rank.vec[i] <- length(set)
    }
    return(rank.vec)
  } # end PARETO.RANK3()

Can anyone think of a way to do this more efficiently, for example by
vectorizing further?  

Thanks,
Scott Waichler
scott.waichler at pnl.gov




More information about the R-help mailing list