守卫城墙的士兵 - 家庭作业

这是一个问题，我们必须解决使用R遗传算法（使用GA库）。我正在寻找一些如何解决这个问题的想法。

描述

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

防御

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小时
在午夜之前开始的焊料，继续在第二天 - 算法必须考虑日子的连续性。需要多少名士兵才能守护城墙？

我的想法而已

可能aproaches中的两个（到目前为止）：

第一种方法

GA的

健身功能会接受一些焊料，然后进行模拟：

将初始分数设置为0.
如果在模拟将会有城市中的士兵缺乏或多余，然后从分数中减去。
最佳解决方案是当分数为零时（所需士兵数量最佳）。

第二条本办法

创建初始群体（焊料），并在健身功能指挥官适用规则（我真的不知道如何定义这里的上述规则），然后运行GA直到我们得到一些有用的分数。

来源

2014-01-10 Simon G.

最后我用非GA的方法。谢谢大家的回答。 –

由于分配结束（是的，我去同一个类作为OP），这是一个真正有趣的问题，我在这里发布我的解决方案：

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([email protected][1, ])) 
sol 
sum(sol)

的GA产生的矢量每小时开始观看的士兵人数（有24小时，这就是为什么24个零和24个150），并且用所述向量调用Fitness函数。

健身功能首先将实数转换为整数（R as.integer功能只消除小数点后的任意数字，不舍入），并为士兵分配6小时的工作时间。它通过在士兵休息时没有那两个小时的情况下将x[i]开始的士兵人数增加到y[i, i+1, ... i+7]来实现。

由于士兵全天候守护，在y那些最后7小时被添加到第一7小时的y然后仅第一24的y值被考虑。

然后我们会比较手表所需的一个士兵所产生的载体，如果有任何FALSE S IN的矢量，Fitness返回一个非常大的负数（GA始终把比较大的数字作为一个更好的）。最后，我们希望尽可能地“雇用”尽可能少的士兵，这就是为什么我们否定了结果（需要的士兵数量更少=否定数更高），因此GA找到了最好的结果。

其余的都很自我解释，我们称GA功能，我们摆弄它的设置并显示结果。

来源

2014-01-29 17:50:53 Issak

干得好的队友:)互联网真的是一个小地方... –

。这是我们需要为每个小时

soldiers 
# 150 160 160 170 350 380 400 420 450 470 500 500 450 350 300 300 310 350 350 
# 330 300 250 200 170

战士因此，我们需要：

sum(soldiers) 
# 7770

但每个士兵工作6小时守着墙这样：

sum(soldiers)/6 
# 1295

现在问题来了如何适应规则：我会说，休息2小时是最小的不是必须的。我没有看到它的重点，它会导致问题（我们将需要更多的士兵比1295）
这是一个起点，而不是0从1295开始。所以我会去第一种方法，即使我对GA图书馆一无所知。

来源

2014-01-10 14:17:03 Llopis

我认为第一种方法不是遗传算法。据我所知，遗传算法从一些初始种群开始，用适应度函数来选择种群中最好的个体。

但是，我会以与你不同的方式定义初始人口。它应该是一组数字，其中每个数字表示城市中的士兵数量。例如，个人1代表10个士兵，个人2代表120个士兵，个人N代表680个士兵。

然后在遗传算法的每一步中，您应该选择（基于适应度函数）最佳个体，即最优的个体。这些人将被用来创造使用遗传算子如交叉和变异的新一代。例如，交叉可以被定义为计算两个数字的平均值。

至于健身功能。它应该确定给定数量的士兵是否最优。通过最优化，我的意思是说，如果城市中有太多（有些士兵无聊）或太少（墙上没有足够的士兵）士兵，就会有信息。

你应该运行GA，直到最好的个人从你的角度来看足够好。

请注意，这是一个家庭作业，这个问题可以解决没有遗传算法。

来源

2014-01-10 14:24:15

我的方法是让人口中的个人代表一些士兵并指派这些士兵轮班。因此，对于300名士兵来说，染色体需要0到23之间的300个数字（假设每个士兵每天都进行相同的移位），标记他开始6小时的时间，但并不是每个人都有相同的染色体长度。有些人将分配300名士兵，其他人则是500名士兵。我不熟悉R中的GA库，但这是他们应该能够处理的。

现在，考虑到一个人和每个士兵的轮班任务，您可以使用问题规则轻松计算每个小时有多少士兵守卫隔离墙。您的目标是尽可能接近一般订单，因此您的健身功能（GA将最大化）应该与生成的时间表和常规订单之间的差异成反比。当差值为0时，您已找到最佳解决方案。

您可以添加其他偏见和约束。比如说，如果你不想在墙上有人看守的地方提供任何解决方案，你可以给这些人特别低的健身。

来源

2014-01-14 07:05:13 alejandrorm

守卫城墙的士兵 - 家庭作业

描述

我的想法而已

第一种方法

第二条本办法

回答

相关问题