小天管理 发表于 2024年6月20日 发表于 2024年6月20日 大佬们, 来请教这个使用遗传算法排课的问题了, 说起来有点绕:举个例子:教学任务: 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 是举例)非常感谢 ：）
已推荐帖子