r - 守卫城墙的士兵——作业

Question

我在人工智能课上有一个作业。

这是一个我们必须使用 R 中的遗传算法(使用 GA 库)来解决的问题。我正在寻找一些想法来解决这个问题。

描述

野蛮人围攻一座城市。将军下令一天中每小时必须有多少士兵守卫城墙。这是他的 table :

Time of the day | Number of soldiers
00:00 - 01:00   150
01:00 - 02:00   160
02:00 - 03:00   160
03:00 - 04:00   170
04:00 - 05:00   350
05:00 - 06:00   380
06:00 - 07:00   400
07:00 - 08:00   420
08:00 - 09:00   450
09:00 - 10:00   470
10:00 - 11:00   500
11:00 - 12:00   500
12:00 - 13:00   450
13:00 - 14:00   350
14:00 - 15:00   300
15:00 - 16:00   300
16:00 - 17:00   310
17:00 - 18:00   350
18:00 - 19:00   350
19:00 - 20:00   330
20:00 - 21:00   300
21:00 - 22:00   250
22:00 - 23:00   200
23:00 - 24:00   170

国防指挥官希望士兵们在巡逻时完全集中注意力，所以他下达了这样的命令:

• 每个守卫城墙的士兵一天刚好 6 小时(24 小时):在城墙上 4 个小时，然后他休息 2 个小时，然后再回到城墙上再守 2 个小时
• 在午夜之前开始工作的士兵，在第二天早上继续工作——算法必须考虑天数的连续性。 需要多少士兵守卫城墙？

到目前为止我的想法

两种可能的方法(到目前为止):

第一种方法

GA 的适应度函数会接受一定数量的焊料然后进行模拟:

• 将初始分数设置为 0。
• 如果在模拟期间城市中的士兵不足或过多，则从分数中减去。
• 最优解是当分数为零时(所需士兵的数量是最优的)。

第二种方法

创建一个初始种群(士兵)并在适应度函数中应用来自指挥官的规则(我真的不知道如何在这里定义上述规则)然后运行 ​​GA 直到我们得到一些有用的分数。

Answer 1

由于作业已经结束(是的，我和 OP 上了同一个类(class))，这是一个非常有趣的问题，我在这里发布我的解决方案:

library(GA)

Fitness <- function(x) {
    x <- as.integer(x)
    # z represents required soldiers at each hour
    z <- c(150,160,160,170,350,380,400,420,450,470,500,500,450,350,300,300,310,350,350,330,300,250,200,170)
    y <- rep(0,31)
    for (i in 1:length(x)) {
        y[i] <- y[i] + x[i]
        y[i+1] <- y[i+1] + x[i]
        y[i+2] <- y[i+2] + x[i]
        y[i+3] <- y[i+3] + x[i]
        #resting 4, 5
        y[i+6] <- y[i+6] + x[i]
        y[i+7] <- y[i+7] + x[i]
    }
    for (i in 1:7) {
        y[i] <- y[i]+y[24+i]
    }
    y <- y[1:24]
    p <- y >= z
    if (FALSE %in% p) { return(-3000) }
return(-sum(x))
}

GA <- ga(type = "real-valued", fitness = Fitness, min = rep(0, 24), max = rep(150, 24), popSize = 24, suggestions = sol, maxiter = 5000, run = 5000, pmutation=0.9)

summary(GA)
sol <- (as.integer(GA@solution[1, ]))
sol
sum(sol)

GA 生成一个向量，其中包含每小时开始 watch 的士兵人数(有 24 小时，这就是为什么有 24 个零和 24 乘以 150)，并使用该向量调用 Fitness 函数。

Fitness 函数首先将实数转换为整数(R as.integer 函数只是去掉小数点后的任何数字，不四舍五入)，然后将士兵分配给其 6 小时的工作。它通过将从 x[i] 开始的士兵数量添加到 y[i, i+1, ... i+7] 而没有这两个小时士兵休息时。

因为士兵全天候守卫，y 中的最后 7 个小时被添加到 y 的前 7 个小时，然后只有 的前 24 个值>y 被考虑。

然后我们将 watch 上生成的士兵向量与所需向量进行比较，如果向量中有任何FALSE，Fitness 返回一个非常大的负值数字(GA 总是取较大的数字作为更好的数字)。

最后我们想“雇佣”尽可能少的士兵，这就是我们否定结果的原因(需要的士兵数量越少 = 否定数量越高)，以便 GA 找到最好的结果。

剩下的就很明显了，我们调用 GA 函数，修改它的设置并显示结果。