如何在遗传算法中进行二进制编码以获得更好的时间表调度问题结果？

Question

我有一个大学时间表安排问题，我正在尝试用遗传算法解决。我想知道这个问题的最佳编码类型，这也可以帮助我满足一些约束。对于这个问题，时间表将具有以下结构，

• 总共有5天的时间安排（周一至周五）。
• 每天会有5个不同的时段，每个时段有一场讲座。
• 但是，实验室讲座将在两个连续时段进行。
• 时间表还将告知每个讲座的房间号（或实验室号）以及每个讲座的讲师姓名。

现在，时间表看起来像这样，（图中有多个时段，但我只会考虑 5 个时段，而不是将时间表分成这么多时段）

这是只有一个部分的时间表。一张时间表大约包含 25 个部分。

现在，我所做的是将每门课程、其部分及其讲师的数据以如下格式写入一个文件中，

1
Object Oriented Programming 
CS-3B
Dr Ali Hassan 
,
2
Object Oriented Programming 
SE-3A
Dr Ali Hassan 
,
3
Remote Sensing and GIS 
CS-7F
Dr Tom Baker

为了表示时间表，我制作了这样的文件，

0
1
2 2 9
3 2 9
0
2
2 1 9
3 1 9
0
3
2 5 36
4 1 36

• 0 是分隔符，它将一个对象与另一个对象分开。
• 第一个数字基本上是课程的 ID。“1”实际上代表我的第一个文件中的第一个对象（即面向对象编程，CS-3A，Ali Hassan 博士）。
• 第二行代表时间表中课程的第一堂课（id = 1）。格式如下，第一个数字是日期。第二个数字是Slot。第三个数字是房间号。。因此，在本例中，表示课程 id = 1 的第一堂课将在“星期二”、“第 2 个时段”和“9 号房间”举行。
• 第三行代表同一课程的第二个讲座。

现在我需要对该时间表进行编码。我现在选择使用二进制编码（显然，我可以转向其他编码，但需要知道哪种编码以及如何编码）并完成这样的编码，

00000001 00000010 00000010 00001001 00000011 00000010 00001001 
00000010 00000010 00000001 00001001 00000011 00000001 00001001 
00000011 00000010 00000101 00100100 00000100 00000001 00100100 
00000100 00000010 00000001 00001101 00000100 00000010 00000110 
00000101 00000010 00000010 00001101 00000011 00000001 00000011 

由于课程总数可能在 200-220 之间，所以我选择了8 位编码。

编码是以这种格式完成的，

Course_ID First_Lecture_Day First_Lecture_Slot First_Lecture_Room 2nd_Lec_Day 2nd_Lec_Slot 2nd_Lec_Room

现在，我想了解一些与此相关的事情，

• 这种编码方法正确吗？或者我应该以其他方式做到这一点？
• 一个严重的问题是我有以下两个限制，

SS

1. 实验室讲座必须在连续的两个时段进行。
2. 课程讲座必须在不同的日子进行，即任何课程都不应在同一天进行两次讲座。

现在，我可以通过在健身功能中实现它来解决第二个问题（我假设。我还没有去过那里，但我想我可以在那里解决这个问题）

但是，我不知道如何解决第一个问题？有没有什么特殊的方法可以指示遗传算法始终将实验室讲座保持在连续的位置？例如，我在二进制编码中使用了另一位，就像这样，

00000001 00000010 00000010 00001001 00000011 00000010 00001001 00000000

00000010 00000010 00000001 00001001 00000011 00000001 00001001 00000001

最后一位将告诉您该课程是实验课程还是当然课程。根据该位，如果您要更改讲座时段，那么如果实验室位已打开，则更改两个讲座时段，以便它们保持不变彼此，因此，实验室是在连续的时隙上进行的？我怎样才能确定这一点？有人可以指导我吗？

另外，我是否应该在遗传算法的编码过程中使用任何其他方法？谢谢。

Answer 1

如果您的实验室房间与普通房间不同，那么您应该分别解决实验室和普通课程。

如果您希望课程始终使用同一个房间，则无需对房间进行两次编码，只需对课程将占用的多个插槽使用位掩码即可。

[课程 ID][房间 ID][插槽位掩码]

[课程 ID] 是一个字节 1-255

[Room Id]是一个字节，假设少于256个房间

[Slot Bit Mask] 是一个 UInt32 位掩码，为您提供 32 个插槽，但您只需要使用 25 个（5 天 * 5 个插槽/天）

[课程 ID] 和 [房间 ID] 对应于您单独的普通和实验室、课程和房间列表。

普通课程的 [槽位掩码] 限制为 2^n (n = 0-24) BitwiseOr 2^m (m = 0-24)，其中 Floor(n / 5) != Floor(m / 5)。这相当于每周有 2 天，每天 1 个时段。

实验课程的[槽位掩码] 限制为 3 * 2^n (n = 0-3, 5-8, 10-13, 15-18, 20-23)，其中 Floor(n / 5) != Floor （米/5）。这相当于每周 1 天，每天 2 个连续时段。编辑仅需 1 个实验日

你的适应度函数只是误差分数。当 [Room Id A] == [Room Id B] AND ([Slot Bit Mask A] BitwiseAnd [Slot Bit Mask B]) > 0 时出现错误。Fitness = (Total - Error) / Total。

编辑示例编码：

课程 ID = 1，房间 ID = 2，正常课程时段 = 周一第 3 个时段和周五第 4 个时段。星期一第三个时段（2^n，n = 2）。周五第四个时段（2^m，m = 23）。Floor(n / 5) = 0 且 Floor(m / 5) = 4，因为 0 和 4 不相等，因此它是有效的正常过程时隙位掩码。

槽位掩码 UInt32 位索引 31 至位索引 0

(ZZZZZZZ5 43215432 15432154 32154321)

(0000000F FFFFTTTT TWWWWWTT TTTMMMMM)

全编码球场、房间、老虎机

00000001b 00000010b 00000000 10000000 00000000 00000100b