[问与答] 最近在做一个课程表的排课程序, 使用遗传算法排课, 苦思冥想不知道该如何处理, 有没有算法大牛能给点建议或者提示吗？

[小天管理]

最近在做一个课程表的排课程序, 使用遗传算法排课, 苦思冥想不知道该如何处理, 有没有算法大牛能给点建议或者提示吗？

下面是排课的要求：

九年级，14 个班，周一至周五，上午 4 节课，下午 4 节课，周一下午第 4 节统一班会课

每个班：

• 语文 7 节（两次两节课的连堂，排在周二和周四）
• 数学 7 节（一次两节课的连堂，排在周三）
• 英语 6 节（两次两节课的连堂，排在周三和周五，周二正课没有英语）
• 物理 5 节（一次两节课的连堂）
• 化学 5 节（一次两节课的连堂）
• 道法 4 节（一次两节课的连堂）
• 历史 4 节（一次两节课的连堂）
• 物理化学每天至少 1 节课，包括晚自习

任课方案：

• 语文 1: 1-2 班 语文 2: 3-4 班 语文 3: 5-6 班 语文 4: 7-8 班 语文 5: 9-10 班 语文 6: 11-12 班 语文 7: 13-14 班
• 数学 1: 1-2 班 数学 2: 3-4 班 数学 3: 5-6 班 数学 4: 7-8 班 数学 5: 9 班 数学 6: 10 班 数学 7: 11-12 班 数学 8: 13-14 班
• 英语 1: 1-2 班 英语 2: 3-4 班 英语 3: 5-6 班 英语 4: 7-8 班 英语 5: 9-10 班 英语 6: 11-12 班 英语 7: 13-14 班
• 物理 1: 1-3 班 物理 2: 4-6 班 物理 3: 7-9 班 物理 4: 10-11 班 物理 5: 12-14 班
• 化学 1: 1-3 班 化学 2: 4-5 班 化学 3: 6-8 班 化学 4: 9-11 班 化学 5: 12-14 班
• 道法 1: 1-4 班 道法 2: 5-8 班 道法 3: 9-10 班 道法 4: 11-14 班
• 历史 1: 1-4 班 历史 2: 5-9 班 历史 3：10-14 班

---

为了表达方便，我对问题做了一些简化，我查看了一些资料，现在使用遗传算法来解决这个问题，下面是我现在的数据结构：

背景信息：

• 教学任务：1 年级 1 班,一周有 1 节语文课, 1 节数学课； 1 年级 2 班,一周有 1 节语文课, 1 节数学课
• 教师：王老师：教授 1 年级 1 班和 1 年级 2 班语文；李老师：教授 1 年级 1 班和 1 年级 2 班数学
• 时间段：每周 5 天,每天 8 节课, 一周就是 40 个时间段, 用数组表示：[1,2,3....40]

数据结构：

• 基因：科目+班级+教师+时间段
• 时间段：例如每周 5 天,每天 8 节课, 一周就是 40 个时间段
• 染色体：相同科目,相同班级组成的多个基因组成的数组
• 个体：多个染色体组成的数组

个体,染色体,基因数据结构举例：

• 基因：
  • 基因 1: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+1(时间段, 1 是举例, 可以是 1...40 中的任意一个数字)
  • 基因 2: ...
• 染色体：
  • 染色体 1：
    • 基因 1: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+1(时间段)
  • 染色体 2：
    • 基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
  • 染色体 3：...
• 个体：
  • 染色体 1：
    • 基因 1: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+1(时间段)
  • 染色体 2：
    • 基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
  • 染色体 3：
    • 基因 1: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+7(时间段)
  • 染色体 4：
    • 基因 1: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+10(时间段)

现在的做法是：

现在两个个体交叉操作时，是在种群中随机找到两个父代个体中的一个染色体索引位置,然后做交叉(相互交换索引位置前后的染体)，生成两个子代。这样交叉后，会出现时间段冲突(会有相同的时间段)：个体内部的同一个班级内，出现了相同的时间段，个体内部的同一个教师内，出现了相同的时间段。这就不对了，因为同一个班级，在同一个时间段，没法上两节不同的课，同一个教师，在同一个时间段，也没法上两节课。

现在的解决方法是：

通过一个修复函数来处理这种冲突，思路是：交叉操作后，将班级内冲突时间段，都整理到一起，将班级内还可以使用的时间段，也整理到一起；然后将教师的冲突时间段，也整理到一起，将教师还可以使用的时间段，也整理到一起；然后将班级冲突时间段，和教室冲突时间段，通过班级可用时间段和教师时间段来替换。如果将班级冲突时间段，和教室冲突时间段，都能使用班级可用时间段和教师时间段替换调，则表示修复成功，反之就是无法修复。

但是现在是会出现，无法修复的情况，如果无法修复，那么就需要撤销此次交叉操作。实际情况是，能实际修复的交叉操作很少，导致迭代很多代后，最优的个体，还是第 1 代的，这就不对了。

现在的问题是：

应该如何执行交叉操作，才能避免同一个班级（如：1 年级 1 班），在交叉后，出现时间段冲突；才能避免同一个教师（如：王老师），在交叉后，出现时间段冲突；后续可能还有教学场地冲突等等...

请问该如何处理更好一些？

感谢看到这个帖子的兄弟姐妹大佬们 ：）