会话调度的遗传算法

Question

我从Mike那里观看了这段视频，在那里他需要一个算法来为像PDC或TechED这样的大型活动制定会议计划。我在想什么是最好的解决方案。他的方法非常简单，他有一个数组，其中他将索引映射到时隙房间，解决方案是一个简单的数组，其中包含这些索引的列表，其中每个时隙空间元素在被选择后从数组中被删除。

例如，给定3个时隙和3个房间，这是映射timeslots+rooms的数组：

0:时隙0，房间0

1:时隙0，1号房间

2:时隙0，2号房

3:时隙1，0室

4:时隙1，1号房间

5:时隙1，第2室

6:时隙2，0室

7:时隙2，第1室

8:时隙2，2号房

假设有9个会议要安排在其中。样本溶液为5，5，2，1，2，3，1，0，即：

第0场，时隙1，第2室

第1场会议，时隙2，0室

第2场会议，时隙0，第2会议室

第3场会议，时隙0，第1室

第4场会议，时隙1，第1会议室

第5场会议，时间安排2，第2会议室

第6场会议，时隙1，0室

第7场会议，时间安排2，第1会议室

第8场会议，时隙0，0室

(如果不清楚的话，视频很快就解释了25:30的cleary )。

现在，我有一些遗传算法的经验，如果我错了就纠正我，但我一直认为，交叉和变异个体产生的解决方案必须类似于生成它的解决方案？也就是说，如果我在两个解之间进行交叉，生成的解必须与生成它的解非常相似(对于突变的情况也是相似的)。进化不是这样运作的吗？看起来，Mark代表解决方案的方式并没有考虑到它。

例如，在交叉的情况下：

父母1: 5，5，2，1，2，3，1，0

父母2: 0,0,0,0,4,3,2,1,0

儿童: 5,5,2,1,4,3,2,1,0 (这种情况下交叉指数为4)

孩子和父母1有4个共同的基因，5和父母2有共同的基因。但是如果你像我上面所做的那样写下实际的解决方案(会话x，时隙x，房间x)，你会很快意识到孩子的解决方案与父母2几乎没有任何共同之处。这不是一个问题吗？

另一个例子是，这次变异：

突变前: 5,5,2,1,2,3,1,1,0

突变后: 0,5,2,1,2,3,1,1,0

这一小变化导致了实际最终解决方案中的9项更改中的6项。

这些是我提出的实际问题吗？或者根本不重要，因为遗传算法无论如何都会运行得很好？如果这些都是问题，你能提出更好的解决方案吗？

我的另一个问题是:如果一个会议要安排几次，怎么办？在这种情况下，您将如何表示解决方案？

任何帮助都非常感谢。

谢谢!

Answer 1

如果一个会话必须安排几次呢？

为每次需要安排会话时创建一个讲课实例，以安排讲座而不是会话。