如何优化一个 N x N 的表格？

Question

我希望对一个数据集进行优化（最大分数），其中每一行都是不重复选择的。这里有一个小例子，但我需要一个算法，能够处理30x30的表格。

opt_table = data.frame(player = c('A', 'B', 'C'), 
                       first = c(0.5, 0.4, 0.4), 
                       second = c(0.4, 0.7, 0.2), 
                       third = c(0.2, 0.4, 0.3))

最高得分是通过按列选择的分数总和最高的得分。在这里，它将是0.5（A）+ 0.7（B）+ 0.3（C）= 1.5。无法通过始终选择给定列的最大行来算法化解决，因为它是没有替换的。

- spazznolo

Answer 1

这是一个涉及IT技术的分配问题，可以使用lpSolve包中的lp.assign进行解决。

library(lpSolve)

z <- lp.assign(-as.matrix(opt_table[-1]))
maxscore <- -z$objval
assignment <- colnames(opt_table[-1])[which(t(z$solution != 0), arr.ind = TRUE)[, "row"]]

你将看到

> maxscore
[1] 1.5

> assignment
[1] "first"  "second" "third"

- ThomasIsCoding

---

哈，比我的解决方案好多了！至少我提到了“这可能是一个标准问题……”它可以在0.02秒内解决30x30的问题……我在5000万次迭代中得到了57.3的目标函数值，而lp.assign几乎瞬间得到了61.03。 - Ben Bolker

很棒的答案！我现在打算去了解一下分配问题哈哈。本，如果你认为你的方法很长，那么你应该看看在我决定发这个问题之前我是怎么做的。我也喜欢你的答案。 - spazznolo

@BenBolker 哈哈，谢谢！你的尝试也很棒 :P - ThomasIsCoding

Answer 2

我不知道这是否接近最优解，也许有一些聪明的方法可以将其简化为已知优化问题的类别。同时，采用蛮力蒙特卡罗交换和 optim(..., method="SANN") 看起来可行。

首先，定义目标函数和更新函数（随机交换两个位置）。

swap <- function(x,...) {
  s <- sample(length(x), 2, replace=FALSE)
  x[s] <- x[rev(s)]
  return(x)
}
objfun <- function(x,M) {
  sum(M[cbind(x,seq(ncol(M)))])
}

我已经检查过这在简单问题上的可行性，现在让我们在一个30x30的矩阵上尝试一下。

set.seed(101)
M2 <- matrix(abs(rnorm(900)),30)
start <- sample(30)
optim(par=start, fn=objfun, gr=swap, control=list(fnscale=-1, 
                                                  trace=TRUE, maxit=1e6),
      method="SANN", M=M2)

我将 fnscale 设置为 -1，因为 optim 喜欢最小化。在跟踪时，目标函数的 负值 将被打印出来...

它从22.1的值开始，并达到53.06。最后一次改进（从52.31到53.06）是在第796000步找到的。

在100万次 随机 抽样中，最好的结果是39.5（r <- replicate(1e6, objfun(sample(30), M=M2))）。

调整模拟退火参数可能会提高性能。或者您可以尝试一些其他的随机全局优化方法（例如遗传算法）。

- Ben Bolker

Answer 3

取每一列的最大值（不包括“player”列），并将它们相加。

library(dplyr)
data.frame(player = c('A', 'B', 'C'), 
           first = c(0.5, 0.4, 0.4), 
           second = c(0.4, 0.7, 0.2), 
           third = c(0.2, 0.4, 0.3)) %>% 
        summarise_at(vars(-player), funs(max)) %>% 
        rowSums()

请注意，看起来像是 0.5 (A) + 0.7 (B) + 0.3 (C) = 1.5 实际上应该是：
0.5 (A) + 0.7 (B) + 0.4 (C) = 1.6。

- B Williams

---

我的错，我应该解释得更清楚。限制条件是我们只能选择一列/行。这就是为什么C使用第三行的0.3作为其公式贡献的原因。一种蛮力的方法是尝试所有选项，但考虑到30x30表格时，这会导致计算上的昂贵。 - spazznolo