使用 Genalg 在 R 中进行整数规划

Question

我正在尝试使用包 genalg 解决 R 中的问题，特别是这个包，因为我需要一个可以理解的 GA 包。

问题是我必须在城市附近建立消防站，但我的目标是救火车的数量最少。他们之间的距离不得超过 15 分钟。数据表示每个城市之间的时间。我已经为每个城市和运行 excel 中的 IP 做了限制，所以我知道答案应该是什么。我注释掉了这些约束，因为我无法弄清楚如何将它们与我用来存储在 GA 中解决的染色体的变量相关联。我还添加了一个惩罚以尝试使值符合约束条件。如果有人知道 CRAN 书之外的 genalg 的好教程，我将不胜感激。

代码如下：

#initilaize library
library(genalg)

#insert data

#set objective
#minimize the sume of x1,x2,x3,x4,x5,x6
datat = data.frame(city1 = c(0, 10, 20, 30, 30, 20), 
                   city2 = c(10, 0, 25, 35, 15, 30),
                   city3 = c(20, 25, 0, 15, 30, 20),
                   city4 = c(30, 35, 15, 0, 15, 25),
                   city5 = c(30, 15, 30, 15, 0, 14),
                   city6 = c(20, 30, 20, 25, 14, 0))

coeff = c(0, 10, 15, 15, 14, 0)

#constraints
#add in a penalty to run function
#how?? relate x to the defined variables
# Failed applications 1 x as a list
#2 x as a variable equal to 6 variables
#3 use x indices instead (zero length?)
#4 changed the dot product to a variable > 0
#5
evalFun = function(x){
  coefftot = x %*% coeff
  # x1 + x2 + x3 + x4 + x5 + x6 >= 1
  # x2 + x4 + x6 >= 2
  # x3 + x4 >= 1
  # x4 + x5 + x6 >= 2
  # x2 + x4 + x5 + x6 >= 3
  # x5 + x6 >= 1
  # if (x5 + x6 < 1) 
  #   #return(0)
  #   x[5] = 1
  if (coefftot <= 0) {
    return(0) else
      return(coefftot)

  }

}



#create function to create shortest path
lpiter = rbga.bin(size = 6,
                  popSize = 100,
                  iters = 100,
                  mutationChance = .01,
                  elitism = T,
                  evalFunc = evalFun)

Answer 1

为了将约束与问题中的变量相关联，我制作了一个与 constraints.Then 相关的向量，我创建了一个方程式来关联它们。例如

  # x5 + x6 >= 1
  x56 <- c(0, 0, 0, 0, 1, 1)
  con56 <-  sum(x*x56)

可能有更简单的方法，但我是这样关联的。如果有人有更有效的方法，我很想听听。运行通过 if 语句时，替换为零，所以我假设有一个更有效的选项。

使用 Genalg 在 R 中进行整数规划

Integer Programming in R Using Genalg

optimization

r

genetic-algorithm

integer-programming