基于遗传算法的排课系统
面向中小学排课
可选——走班制
https://github.com/BeGifted/Course-Scheduling-System
硬约束:
- 一个教师在同一时间段内只能安排一门课程;
- 一个班级在同一时间段内只能安排一门课程;
- 一个学生在同一时间段内只能安排一门课程;
(由冲突消除和初始化种群解决)
软约束:
-
时段限制,即横向时间段限制,格式:对象+时间段+形式+次数。其中对象可选项为【科目,教师】,时间段可选项为【上午、下午、第一节、第二节、···】,形式可选项为【固定、最少、最多】,次数为【0、1、2、···】;(+10)
数据库:xingzhi_schedule_rule_time_limit
-
各天限制,即纵向时间段限制,格式:对象+时间段+形式+次数。其中对象可选项为【科目,教师】,时间段可选项为【每天、星期一、星期二、星期三、星期四、星期五】,形式可选项为【固定、最少、最多】,次数为【0、1、2、···】;(+10)
数据库:xingzhi_schedule_rule_day_limit
-
教师互斥,格式:教师A+教师B,A与B不同时上课;(+10)
数据库:xingzhi_schedule_rule_teacher_limit
-
科目互斥,格式:科目A+科目B,A与B不排在同一天;(+10)
数据库:xingzhi_schedule_rule_subject_mutex
-
科目相邻,格式:科目A+科目B,A与B在同一天相邻;(+10)
数据库:xingzhi_schedule_subject_two
-
禁止科目相邻,格式:科目A+科目B,A不排于B前面;(+10)
数据库:xingzhi_schedule_rule_subject_adjacent
-
科目预设,格式:年级+班级+科目+时间+限制,限制可选项为【一定排、尽量排、不排】;(6.2)
数据库:xingzhi_schedule_rule_subject_preset
-
教师预设,格式:教师+时间+限制,限制可选项为【一定排、尽量排、不排】;(6.4)
数据库:xingzhi_schedule_rule_teacher_preset
(将软约束纳入期望值的考察中)
名词解释:
基因:某个时间片的值。
染色体:一个班级所有的基因组成的基因串。
个体:包含所有班级的大课程表,即全校课表。
种群:M个不同的个体,即M个不同的全校课程总表。
流程图:
STEP:
-
获取开课任务;
List<String> classTaskList
-
将开课任务进行编码;
List<String> geneList
编码规则:是否固定+年级编号+班级编号+教师编号+课程编号+课程属性+开课时间
(isFix + gradeNo + classNo + teacherNo + courseNo + courseAttr + classTime)
按照一周上课次数(weeksNumber)拆分成单独的基因,一个班级对应5×6=30个基因。
开课时间若未指定,默认“00”。
-
开始进行时间分配;
List<String> resultGeneList
已固定的不分配,未固定的课程任务(基因)随机分配时间片,长度两位,01-30。
原则:随机不重复
-
对已分配好时间的基因进行分类,生成以所有班级为范围的个体;
Map<String, List<String>> individualMap
key值为年级+班级编号,value值为包含30个基因的列表(染色体)。
individualMap表示生成的一个个体,即全校课表。
-
重复3、4M次,生成规模为M的种群,即M个个体,用于遗传进化;
-
进行遗传进化操作;
6.1 冲突检测和消除:
冲突主要是指同一时间同一教师只能教授一门课程;消除的过程是指若基因A与基因B冲突,则选取与基因B位于同一染色体的基因C,进行时间片的互换,若基因C有特定的时间安排,则重新选取C。
6.2 课程时间片优先度$\overlineρ$:
主课、副课等都根据时间片优先级赋予不同的期望值。例如语文安排在星期一的第一节,则$ρ$累加对应的期望值10。最后总的$ρ$除以总的开课任务数量(基因数)得到$\overlineρ$。
语文、数学、英语星期一 星期二 星期三 星期四 星期五 第一节 10 10 10 10 10 第二节 8 8 8 8 8 第三节 6 6 6 6 6 第四节 4 4 4 4 4 第五节 2 2 2 2 2 第六节 0 0 0 0 0 星期一 星期二 星期三 星期四 星期五 第一节 0 0 0 0 0 第二节 0 0 0 0 0 第三节 4 4 4 4 4 第四节 6 6 6 6 6 第五节 8 8 8 8 8 第六节 10 10 10 10 10 星期一 星期二 星期三 星期四 星期五 第一节 4 4 4 4 4 第二节 8 8 8 8 8 第三节 10 10 10 10 10 第四节 8 8 8 8 8 第五节 4 4 4 4 4 第六节 2 2 2 2 2 星期一 星期二 星期三 星期四 星期五 第一节 6 6 6 6 6 第二节 6 6 6 6 6 第三节 6 6 6 6 6 第四节 6 6 6 6 6 第五节 6 6 6 6 6 第六节 6 6 6 6 6 星期一 星期二 星期三 星期四 星期五 第一节 0 0 0 0 0 第二节 0 0 0 0 0 第三节 0 0 0 0 0 第四节 6 6 6 6 6 第五节 10 10 10 10 10 第六节 8 8 8 8 8 6.3 课程分布均匀度$\overline{ε_c}$:
例如一年一班在一周内要上8节语文课,最好的情况就是一天上1-2节课,即课程在每天的分布尽量均匀。
其中——
$σ_i$ 指课程$i$的分布方差,越均匀则$σ_i$越小;$h_{id}$ 指课程$i$在星期$d$安排的节次;$\overline{h_i}$ 指课程$i$一周内的总节次$l_i$除以$dw$得到的平均值;$dw$ 指一周共5天;由于得到的方差$σ_i$越小越好,为了使得与其他适应度函数一样极大化,将其变形为——
其中——
$\overline{ε_c}$ 指所有课程的分布均匀度在适应度上的体现;$n$ 为课程总量;$l_i$ 为课程$i$一周内的总节次;6.4 教师期望时间满意度$\overline{w}$:
教师的课表上的时间片分为三种类型:期望、一般和不期望。分别把三种时间类型加以量化:$w_1$ = 1、$w_2$ = 0.5和$w_3$ = 0。分别统计教师$i$开课分别属于三种时间类型的节次为$h_1$、$h_2$和$h_3$。则有下式——
其中——
$\overline{w_i}$ 指教师$i$的满意度;求所有教师时间满意度的平均值得$\overline{w}$,即下式——
6.5 教师课时分布均匀度$\overline{θ}$:
例如教师A同时教一班和二班的语文,一个班一周共上8节语文课,要求教师A每天上的课时数尽量相同,即教师课时分布均匀度。
$\overline{θ}$ 同6.3中的课程分布均匀度$\overline{ε_c}$计算相同。6.6 软约束条件适应度计算:
赋予软约束一定的期望值权重,如当前种群中的一个个体里,满足教师A与教师B上课时间互斥,则累加一定的期望值。
6.7 选择算子:
选规模大小为M的种群中的个体,选择M次组成新的规模为M的种群。
轮盘赌方法,按不同比例大小将轮盘划分为不同的区域,种群中每个个体被选中的概率正比于它的适应度大小。轮盘中比例值越大的区域,其个体的适应度也越高,被选中并遗传给下一代的概率也越大。反之被淘汰的概率较大。
优化:多轮轮盘赌选择、轮盘赌+锦标赛选择。
6.8 交叉算子
将种群中的个体两两配对,记为个体A和个体B,随机选择A与B中的同一个班级,进行班级课表的交换,形成A’ 和B‘ ,选择A与A’ 中适应度较高的进入下一代,B与B’ 同理。
6.9 变异算子
针对个体中的染色体(班级课表),选择两条基因,对其进行开课时间的变异(互换)。
6.10 参数控制
种群规模M:20-100
交叉率Pc:0.4-0.9
变异率Pm:0.001-0.05
遗传代数T:100-500
适应度权重分配
-
分配教室——针对走班制;
-
存入数据库。