大佬们, 来请教这个使用遗传算法排课的问题了, 说起来有点绕:
举个例子:
教学任务:
1 年级 1 班,一周有 3 节语文课, 4 节数学课
1 年级 2 班,一周有 3 节语文课, 4 节数学课
教师:
王老师: 教授 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 班(班级)+王老师(教师)+2(时间段)
基因 3: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+3(时间段)
染色体 2:
基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
基因 2: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+5(时间段)
基因 3: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+6(时间段)
基因 4: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+7(时间段)
个体:
染色体 1:
基因 1: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+1(时间段)
基因 2: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+2(时间段)
基因 3: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+3(时间段)
染色体 2:
基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
基因 2: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+5(时间段)
基因 3: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+6(时间段)
基因 4: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+7(时间段)
染色体 3:
基因 1: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+7(时间段)
基因 2: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+8(时间段)
基因 3: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+9(时间段)
染色体 4:
基因 1: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+10(时间段)
基因 2: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+11(时间段)
基因 3: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+12(时间段)
基因 4: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+13(时间段)
现在的问题是:
现在两个个体交叉操作时，是在种群中随机找到两个父代个体中的一个染色体索引位置,然后做交叉,生成两个子代
但是交叉后,会出现时间段冲突(会有相同的时间段): 个体内部的同一个班级内,出现了相同的时间段, 个体内部的同一个教师内,,出现了相同的时间段,这就不对了
因为同一个班级,在同一个时间段,没法上两节不同的课, 同一个教师,在同一个时间段,也没法上两节课
我现在的做法,是通过一个修复函数来处理这种冲突, 思路是:
交叉操作后, 将班级内冲突时间段, 都整理到一起, 将班级内还可以使用的时间段,也整理到一起
然后将教师的冲突时间段, 也整理到一起, 将教师还可以使用的时间段,也整理到一起
然后将班级冲突时间段,和教室冲突时间段, 通过班级可用时间段和教师时间段来替换
如果将班级冲突时间段,和教室冲突时间段，都能使用班级可用时间段和教师时间段替换调，则表示修复成功，反正就是无法修复
现在是会出现, 无法修复的情况，如果无法修复，那么就需要撤销此次交叉操作
实际情况是, 能实际修复的交叉操作很少，导致迭代很多代后，最优的个体，还是第 1 代的, 这就不对了。
请问该如何处理更好一些？
---------------------------------------------
上面的例子，为了表达，我做了一些简化，实际情况，会比这个更复杂一下，例如下面是我正在解决的排课问题：
九年级，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 年级 2 班(班级)+李老师(教师)+1_3(两个时间段,1,3 是举例)
非常感谢 ：）
举个例子:
教学任务:
1 年级 1 班,一周有 3 节语文课, 4 节数学课
1 年级 2 班,一周有 3 节语文课, 4 节数学课
教师:
王老师: 教授 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 班(班级)+王老师(教师)+2(时间段)
基因 3: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+3(时间段)
染色体 2:
基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
基因 2: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+5(时间段)
基因 3: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+6(时间段)
基因 4: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+7(时间段)
个体:
染色体 1:
基因 1: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+1(时间段)
基因 2: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+2(时间段)
基因 3: 语文(科目)+1 年级 1 班(班级)+王老师(教师)+3(时间段)
染色体 2:
基因 1: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+4(时间段)
基因 2: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+5(时间段)
基因 3: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+6(时间段)
基因 4: 数学(科目)+1 年级 1 班(班级)+李老师(教师)+7(时间段)
染色体 3:
基因 1: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+7(时间段)
基因 2: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+8(时间段)
基因 3: 语文(科目)+1 年级 2 班(班级)+王老师(教师)+9(时间段)
染色体 4:
基因 1: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+10(时间段)
基因 2: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+11(时间段)
基因 3: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+12(时间段)
基因 4: 数学(科目)+1 年级 2 班(班级)+李老师(教师)+13(时间段)
现在的问题是:
现在两个个体交叉操作时，是在种群中随机找到两个父代个体中的一个染色体索引位置,然后做交叉,生成两个子代
但是交叉后,会出现时间段冲突(会有相同的时间段): 个体内部的同一个班级内,出现了相同的时间段, 个体内部的同一个教师内,,出现了相同的时间段,这就不对了
因为同一个班级,在同一个时间段,没法上两节不同的课, 同一个教师,在同一个时间段,也没法上两节课
我现在的做法,是通过一个修复函数来处理这种冲突, 思路是:
交叉操作后, 将班级内冲突时间段, 都整理到一起, 将班级内还可以使用的时间段,也整理到一起
然后将教师的冲突时间段, 也整理到一起, 将教师还可以使用的时间段,也整理到一起
然后将班级冲突时间段,和教室冲突时间段, 通过班级可用时间段和教师时间段来替换
如果将班级冲突时间段,和教室冲突时间段，都能使用班级可用时间段和教师时间段替换调，则表示修复成功，反正就是无法修复
现在是会出现, 无法修复的情况，如果无法修复，那么就需要撤销此次交叉操作
实际情况是, 能实际修复的交叉操作很少，导致迭代很多代后，最优的个体，还是第 1 代的, 这就不对了。
请问该如何处理更好一些？
---------------------------------------------
上面的例子，为了表达，我做了一些简化，实际情况，会比这个更复杂一下，例如下面是我正在解决的排课问题：
九年级，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 年级 2 班(班级)+李老师(教师)+1_3(两个时间段,1,3 是举例)
非常感谢 ：）
1 条回复
 |
1
ga9 OP 核心问题，就是避免交叉后，出现时间段冲突.... 因为如果出现冲突, 有可能也无法修复。
想了好几天，想不到一个好的办法.... 😆 |
Select Language