如何在遗传算法中进行二进制编码以获得更好的时间表调度问题？
How to do Binary Encoding in Genetic Algorithm for better results in Timetable Scheduling Problem?
我有一个大学时间表安排的问题，我正在尝试使用 遗传算法 来解决。我想知道这个问题的最佳编码类型，它也可以帮助我满足一些约束。对于这个问题，时间表将具有以下结构，
- 一共排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，Dr. Ali Hassan）。
- 第二行代表时间表中的第一堂课（id = 1）。格式如下，第一个数字是天。 第二个号码是插槽。 第三个号码是房间号。。
因此，在这种情况下，表示课程 id = 1 的第一堂课将在“星期二”的“2nd Slot”和“Room Number 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
- 实验室讲座必须在两个连续的时段进行。
- 课程讲座必须在不同的日子进行，即任何课程都不应在同一天进行。
现在，我可以通过在 健身功能 中实现它来解决第二个问题（我假设。我还没有去过那里，但我认为我可以解决这个问题在那里发布）
但是，我不知道如何解决第一个问题？有什么特别的方法可以指示遗传算法始终将实验室讲座保持在连续的位置吗？例如，我在我的二进制编码中使用了另一个位，可能像这样，
00000001 00000010 00000010 00001001 00000011 00000010 00001001 00000000
00000010 00000010 00000001 00001001 00000011 00000001 00001001 00000001
最后一位将说明该课程是实验室课程还是当然课程.. 根据该位，如果您要更改讲座时段，则 如果实验室位已打开，则更改两个讲座时段，使它们彼此保持一致，因此，实验是在连续的时段进行的？我怎样才能确定这一点？有谁能指导一下吗？
还有我应该在遗传算法的编码过程中使用的任何其他方法吗？谢谢。
如果您的实验室房间与普通房间不同，那么您应该分别解决实验室和普通课程。
如果您希望课程始终使用同一个房间而不需要对房间进行两次编码，只需对课程将占用的多个插槽使用位掩码即可。
[课程 ID][房间 ID][插槽位掩码]
[课程 ID] 是一个字节 1-255
[Room Id]为一个字节，假设少于256个房间
[Slot Bit Mask] 是一个 UInt32 位掩码，给你 32 个 slot 但你只需要使用 25 (5 days * 5 slots/day)
[Course Id] 和 [Room Id] 对应于您单独的 Normal 和 Lab、Courses 和 Rooms 列表。
[Slot Bit Mask] for Normal Courses 被限制为 2^n (n = 0-24) BitwiseOr 2^m (m = 0-24)，其中 Floor(n / 5) != Floor(m / 5).这相当于每周 2 天，每天 1 个时段。
[Slot Bit Mask] for Lab Courses 被限制为 3 * 2^n（n = 0-3、5-8、10-13、15-18、20-23），其中 Floor(n / 5) != 楼层(m / 5)。这相当于每周 1 天，每天 2 个连续时段。 编辑 只需要 1 个实验日
你的适应度函数就是错误分数。当 [Room Id A] == [Room Id B] AND ([Slot Bit Mask A] BitwiseAnd [Slot Bit Mask B]) > 0 时出现错误。适合度 =（总计 - 错误）/总计。
编辑 编码示例：
课程 ID = 1，房间 ID = 2，普通课程时段 = 星期一第 3 个时段和星期五第 4 个时段。星期一第 3 个时段 (2^n, n = 2)。星期五第 4 个时段（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
我有一个大学时间表安排的问题，我正在尝试使用 遗传算法 来解决。我想知道这个问题的最佳编码类型，它也可以帮助我满足一些约束。对于这个问题，时间表将具有以下结构，
- 一共排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，Dr. Ali Hassan）。
- 第二行代表时间表中的第一堂课（id = 1）。格式如下，第一个数字是天。 第二个号码是插槽。 第三个号码是房间号。。 因此，在这种情况下，表示课程 id = 1 的第一堂课将在“星期二”的“2nd Slot”和“Room Number 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
- 实验室讲座必须在两个连续的时段进行。
- 课程讲座必须在不同的日子进行，即任何课程都不应在同一天进行。
现在，我可以通过在 健身功能 中实现它来解决第二个问题（我假设。我还没有去过那里，但我认为我可以解决这个问题在那里发布）
但是，我不知道如何解决第一个问题？有什么特别的方法可以指示遗传算法始终将实验室讲座保持在连续的位置吗？例如，我在我的二进制编码中使用了另一个位，可能像这样，
00000001 00000010 00000010 00001001 00000011 00000010 00001001 00000000
00000010 00000010 00000001 00001001 00000011 00000001 00001001 00000001
最后一位将说明该课程是实验室课程还是当然课程.. 根据该位，如果您要更改讲座时段，则 如果实验室位已打开，则更改两个讲座时段，使它们彼此保持一致，因此，实验是在连续的时段进行的？我怎样才能确定这一点？有谁能指导一下吗？
还有我应该在遗传算法的编码过程中使用的任何其他方法吗？谢谢。
如果您的实验室房间与普通房间不同，那么您应该分别解决实验室和普通课程。
如果您希望课程始终使用同一个房间而不需要对房间进行两次编码，只需对课程将占用的多个插槽使用位掩码即可。
[课程 ID][房间 ID][插槽位掩码]
[课程 ID] 是一个字节 1-255
[Room Id]为一个字节，假设少于256个房间
[Slot Bit Mask] 是一个 UInt32 位掩码，给你 32 个 slot 但你只需要使用 25 (5 days * 5 slots/day)
[Course Id] 和 [Room Id] 对应于您单独的 Normal 和 Lab、Courses 和 Rooms 列表。
[Slot Bit Mask] for Normal Courses 被限制为 2^n (n = 0-24) BitwiseOr 2^m (m = 0-24)，其中 Floor(n / 5) != Floor(m / 5).这相当于每周 2 天，每天 1 个时段。
[Slot Bit Mask] for Lab Courses 被限制为 3 * 2^n（n = 0-3、5-8、10-13、15-18、20-23），其中 Floor(n / 5) != 楼层(m / 5)。这相当于每周 1 天，每天 2 个连续时段。 编辑 只需要 1 个实验日
你的适应度函数就是错误分数。当 [Room Id A] == [Room Id B] AND ([Slot Bit Mask A] BitwiseAnd [Slot Bit Mask B]) > 0 时出现错误。适合度 =（总计 - 错误）/总计。
编辑 编码示例：
课程 ID = 1，房间 ID = 2，普通课程时段 = 星期一第 3 个时段和星期五第 4 个时段。星期一第 3 个时段 (2^n, n = 2)。星期五第 4 个时段（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