r - R 中的遗传算法(或优化)

Question

我正在尝试在 R 中使用 GA 探索优化领域。我意识到 R 可能不是我这样做的最佳场所，但这是我现在所知道的。

所以问题来了:我可以挑选一组人来最有效地 build 我的房子。我愿意为这项工作花费最多 100,000 美元(超出此解决方案不再有效的限制)，我必须从 500 或所以(这项工作共有 7 个人)。

这些人中的每一个都有他们将为工作收取的费率以及他们将为手头工作提供的总体值(value)(总值(value)需要最大化)。看这里的数据:

Data

我查看了 R 包 genalg 和 DeOptim，您可以在其中使用二元函数来选择能够以给定价格最大化整体值(value)的人，但我无法弄清楚如何限制选择的 worker 类型。解决方案可以是所有电工，虽然他们都提供了巨大的值(value)，但他们无法完成工作。所以基本上我正在寻找一种控制人口的方法，而这些软件包似乎都不允许这样做。

有没有关于我如何解决这个问题的想法？我相信你们中的许多人已经看过这个问题的变体并且有很好的洞察力。非常感谢您的帮助。

这是我从这里的论坛获得的代码:

library(genalg)

iter = 10
population = 500

# import csv file
brank = read.csv("GA_Data.csv")


dataset <- data.frame(item = brank$Person.ID, survivalpoints = brank$Value, weight = brank$Labor.Cost)


weightlimit <- 100000


monitor <- function(obj) {
  minEval = min(obj$evaluations);
  plot(obj$mean, obj$best, type="p", main = obj$iter); 
}

evalFunc <- function(x) {
  current_solution_survivalpoints <- x %*% dataset$survivalpoints
  current_solution_weight <- x %*% dataset$weight

  if (current_solution_weight > weightlimit) 
    return(0) else return(-current_solution_survivalpoints)
}


GAmodel <- rbga.bin(size = length(brank$Person.ID), popSize = population, iters = iter, mutationChance = 0.01, 
                    monitorFunc = monitor, elitism = T, zeroToOneRatio = 200, evalFunc = evalFunc)

cat(summary.rbga(GAmodel))

########################
# STOP and replace "space" with "comma" in a text file

solution = c(0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0)
# dataset[solution == 1, ]
brank[solution == 1, ]

sum(brank$Value[solution == 1])
sum(brank$Labor.Cost[solution == 1])

Answer 1

您的问题是 线性规划 (LP) 任务，应该这样解决。 R 有几个用于线性规划的包，这里我将使用 lpSolve .

我把你的数据放入数据框D (299 名 worker )。

str(D)
# 'data.frame': 299 obs. of  4 variables:
#  $ ID   : int  1 2 3 4 5 6 7 8 9 10 ...
#  $ Type : Factor w/ 4 levels "Cleanup Guy",..: 4 4 4 4 4 4 4 4 4 4 ...
#  $ Cost : int  5100 3900 5000 4500 6700 5000 4000 3500 7500 4500 ...
#  $ Value: int  25 18 23 20 29 21 17 15 32 19 ...

# Prepare constraint matrix
A <- matrix(0, nrow = 5, ncol = 299)
A[1, c(1:27, 279:299)] <- 1     # Plumbers
A[2, 28:97] <- 1                # Electricians
A[3, 98:190] <- 1               # Const Workers
A[4, 191:278] <- 1              # Cleanup
A[5, ] <- D$Cost                # cost <= 100000

# Prepare input for LP solver
objective.in <- D$Value
const.mat <- A
const.dir <- c(">=", ">=", ">=", ">=", "<=")
const.rhs <- c(1, 2, 2, 2, 100000)

# Now solve the problem
require(lpSolve)
sol <- lp(direction = "max", objective.in, # maximize objective function
        const.mat, const.dir, const.rhs,   # constraints
        all.bin = TRUE)                    # use binary variables only

# View the solution
sol
## Success: the objective function is 589
sum(D$Cost[inds])
## 100000
inds <- which(sol$solution == 1)
D[inds, ]
##      ID         Type Cost Value
## 1     1      Plumber 5100    25
## 51   51  Electrician 5000    24
## 54   54  Electrician 3500    16
## 101 101 Const Worker 3500    18
## 102 102 Const Worker 4400    21
## 103 103 Const Worker 5800    27
## 147 147 Const Worker 5600    29
## 149 149 Const Worker 3700    17
## 196 196  Cleanup Guy 6200    30
## 197 197  Cleanup Guy 4200    20
## 256 256  Cleanup Guy 4000    27
## 263 263  Cleanup Guy 3800    22
## 264 264  Cleanup Guy 3800    33
## 266 266  Cleanup Guy 3700    23
## 267 267  Cleanup Guy 4200    30
## 273 273  Cleanup Guy 3600    35
## 274 274  Cleanup Guy 5900    28
## 275 275  Cleanup Guy 3700    28
## 282 282      Plumber 7000    37
## 287 287      Plumber 3800    30
## 297 297      Plumber 3600    37
## 298 298      Plumber 5900    32

有关输入的说明，请参阅 lp() 的帮助页面功能。