基于遗传算法的排课系统

面向中小学排课

可选——走班制

https://github.com/BeGifted/Course-Scheduling-System

硬约束：

1. 一个教师在同一时间段内只能安排一门课程；
2. 一个班级在同一时间段内只能安排一门课程；
3. 一个学生在同一时间段内只能安排一门课程；

（由冲突消除和初始化种群解决）

软约束：

1. 时段限制，即横向时间段限制，格式：对象+时间段+形式+次数。其中对象可选项为【科目，教师】，时间段可选项为【上午、下午、第一节、第二节、···】，形式可选项为【固定、最少、最多】，次数为【0、1、2、···】；（+10）

   数据库：xingzhi_schedule_rule_time_limit

2. 各天限制，即纵向时间段限制，格式：对象+时间段+形式+次数。其中对象可选项为【科目，教师】，时间段可选项为【每天、星期一、星期二、星期三、星期四、星期五】，形式可选项为【固定、最少、最多】，次数为【0、1、2、···】；（+10）

   数据库：xingzhi_schedule_rule_day_limit

3. 教师互斥，格式：教师A+教师B，A与B不同时上课；（+10）

   数据库：xingzhi_schedule_rule_teacher_limit

4. 科目互斥，格式：科目A+科目B，A与B不排在同一天；（+10）

   数据库：xingzhi_schedule_rule_subject_mutex

5. 科目相邻，格式：科目A+科目B，A与B在同一天相邻；（+10）

   数据库：xingzhi_schedule_subject_two

6. 禁止科目相邻，格式：科目A+科目B，A不排于B前面；（+10）

   数据库：xingzhi_schedule_rule_subject_adjacent

7. 科目预设，格式：年级+班级+科目+时间+限制，限制可选项为【一定排、尽量排、不排】；（6.2）

   数据库：xingzhi_schedule_rule_subject_preset

8. 教师预设，格式：教师+时间+限制，限制可选项为【一定排、尽量排、不排】；（6.4）

   数据库：xingzhi_schedule_rule_teacher_preset

（将软约束纳入期望值的考察中）

名词解释：

基因：某个时间片的值。

染色体：一个班级所有的基因组成的基因串。

个体：包含所有班级的大课程表，即全校课表。

种群：M个不同的个体，即M个不同的全校课程总表。

流程图：

STEP：

1. 获取开课任务；

   List<String> classTaskList
   

2. 将开课任务进行编码；

   List<String> geneList
   

   编码规则：是否固定+年级编号+班级编号+教师编号+课程编号+课程属性+开课时间

   （isFix + gradeNo + classNo + teacherNo + courseNo + courseAttr + classTime）

   按照一周上课次数（weeksNumber）拆分成单独的基因，一个班级对应5×6=30个基因。

   开课时间若未指定，默认“00”。

3. 开始进行时间分配；

   List<String> resultGeneList
   

   已固定的不分配，未固定的课程任务（基因）随机分配时间片，长度两位，01-30。

   原则：随机不重复

4. 对已分配好时间的基因进行分类，生成以所有班级为范围的个体；

   Map<String, List<String>> individualMap
   

   key值为年级+班级编号，value值为包含30个基因的列表（染色体）。

   individualMap表示生成的一个个体，即全校课表。

5. 重复3、4M次，生成规模为M的种群，即M个个体，用于遗传进化；

6. 进行遗传进化操作；

   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

   校1、校2、综1、综2、综3

   	星期一	星期二	星期三	星期四	星期五
   第一节	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

   适应度权重分配

7. 分配教室——针对走班制；

8. 存入数据库。