改进遗传算法求解新高考背景下的排课问题

徐向阳 刘文伟 傅蝶 徐刚 金澈清 王祥丰 王江涛

摘要： 我国提出新高考改革政策后， 越来越多地区和高中开始采用走班制教学模式. 相对于传统的行政班教学模式， 走班制教学模式使排课问题的约束条件进一步增多， 学校教育资源匮乏的现象进一步凸显. 传统的排课算法不适于求解走班制教学模式下的排课问题， 而纯粹的手动编排课表不仅费时费力， 排出的课表还可能存在大量冲突， 难以保证课表的可行性和合理性. 根据走班制教学模式的特点，设计了一种获取优质可行解的方法： 首先针对走班课程提出了一种自动生成教学班组合的方法; 然后运用改进的遗传算法高效合理地求解排课问题. 实验结果表明， 该算法可获得优质的课表安排， 并且已经加入到实际应用中.

关键词： 走班制; 遗传算法; 排课问题; 排课算法; 组合优化

中图分类号： TP311 文献标志码： A DOI： 10.3969/j.issn.1000-5641.201921008

0 引言

2014 年， 我国出台了新高考教育改革政策， 在上海和浙江两地试点， 随后新高考政策逐渐开始在全国范围内推广. 该政策引入了走班制教学模式， 赋予了学生选学选考的权利[1]. 新高考模式下， 学生的高考成绩将由统一高考的语文、数学、英语科目的成绩和高中学业水平测试的任意三门课的成绩组成， 学生可以根据自己的兴趣和特长选择相应的科目， 学生个性化教育的需求得到了满足. 在走班制教学模式下， 同一个行政班中学生的选课可能各不相同; 而传统的班级授课模式中， 学生在固定的行政班里上课， 每位同学上的课程完全一样. 实施走班制教学会造成教学班与行政班交错的情况， 课表的安排更加复杂， 对教学资源的需求会增加， 课表编排的约束条件也更加苛刻， 而很多学校都存在着教学资源匮乏的问题， 这种情况下实施走班制教学困难重重. 单纯手动排课不仅费时费力， 而且不能保证遵循所有的约束条件， 排出的课表难以满足教师和学生的需求. 课表安排是否合理， 对学校教学质量有着较大的影响， 因此需要一种高效智能的排课方法来求解走班制度下的排课问题.

排课问题的重要性、复杂性， 使其长期受到很多专家学者的关注与研究. 1962 年， Gotlieb[2] 提出了排课问题对应的数学模型， 为以后的研究奠定了一定的数学基础. Even 等[3] 在1975 年证明了排课问题是一个NP 完全（Non-deterministic Polynomial Complete） 问题， 让人们对排课问题的复杂性有了理论上的初步认识. 然而在20 世纪90 年代之前， 大多数的解决方案靠的是教务管理者的经验， 通用性和实用性较低. 进入90 年代后， 随着计算机理论和技术的不断发展， 越来越多的智能优化算法陆续被用于求解排课问题， 且取得了相应的成果. 近些年的解决方案有遗传算法（Genetic Algorithm，GA）[4-6]、模拟退火算法[7]、蚁群算法[8]、禁忌搜索算法[9] 以及混合算法[10] 等， 但是這些方案在约束条件的考虑上有所欠缺， 且基本上是针对高校或者普通行政班教学模式的排课问题， 不适用于解决行政班和教学班交错情况的高中走班制排课问题.

目前针对新高考走班排课问题的研究较少， 文献[11-12] 使用改进的遗传算法求解走班制排课问题， 做出了一定的贡献， 但是还存在了一些问题， 如要求初始种群中的个体均无冲突， 但是在高中走班教学的实际情况中， 教学资源匮乏， 一个老师可能要教授多个年级下的多个班级， 一个教室也可能要安排多个班级的课程， 随机生成的课表很大概率都会有冲突， 若要保证种群中的个体均无冲突， 则排课所耗费的时间会大大增加; 此外， 适应度函数的设计不够灵活， 实际情况下教务老师会针对本校的情况设定一些约束条件， 而文中的适应度函数只考虑了固定的几种约束条件， 如果要加入新的约束条件， 则需要对适应度函数进行更改， 使得排课系统的可维护性降低. 现有的一些走班排课系统， 如科大讯飞的智能排课系统， 也是对一些学校复杂性的个性化需求缺少有效的解决方案， 比如长短课程、导师班以及校本课程走班的安排等.

本文围绕上述这些问题设计了走班排课问题的求解方法， 针对走班课程， 提出了走班组合的概念，给出了自动划分教学班的方法： 针对长课时课程（长课时课程占用1.5 个课时）， 为避免和正常课时课程的安排相冲突， 将两节长课时课程安排在相邻的授课时段; 针对走班排课问题， 建立排课模型， 使用改进的遗传算法解决排课问题， 在生成初始种群时， 不考虑课表的冲突， 打破了初始种群中个体应当为可行解的约束; 另外在变异算子中创新性地加入了基因编辑的思想， 以一定概率自动定位课表中的一次资源冲突并消除冲突， 并有针对性地在适应度函数中引入惩罚度的设计. 实例验证表明，本文算法在实际的走班排课问题中取得了很好的效果.

1 走班排课的基本问题

1.1 问题描述

排课问题属于调度问题的研究范畴， 其核心任务是将课程、班级、教师、教室资源不冲突地安排在各个授课时间段， 并保证其能够满足教务老师事先设定好的各种约束条件， 且使结果达到最优或者近似最优. 而走班制教学模式的引入， 使排课问题变得更加复杂， 排课的约束条件进一步增多， 学校教学资源匮乏的现象进一步凸显.

目前大多数实行走班制的高中学校采用的走班模式是， 主课和艺体课固定在行政班上课， 选考科目进行走班[13]. 因此本文使用的排课模式是， 英语、数学、语文等主课以及艺体课固定在行政班上课，选考课程以及校本课程进行走班安排.

5 结束语

随着新高考政策在全国范围内的推广， 走班制教学模式逐渐代替了传统的行政班教学模式， 而走班制教学模式的引入， 使得排课的约束条件大大增加， 传统的排课方案已经不适用于解决走班模式下的排课问题， 而单纯的手动排课不仅费时费力， 且难以满足学生个性化教育的需求， 因此需要一个切实可行的智能排课方案来解决走班排课问题. 本文立足于上海市实验性示范性高中背景下的学校的实际需求来解决走班排课问题， 创新点主要有以下3 个方面： ①课表中加入了长课时课程和走班课程组合的安排， 针对走班课程提出了自动划分教学班组合的方法， 每一个走班组合内部的教学班相互不冲突; ②遗传算法中的遗传算子创新性地引入了基因编辑思想， 以一定概率去自动定位课表中的一次冲突并消除该冲突， 大大提升了遗传算法的进化效果; ③针对本文提出的遗传算法的初始种群生成策略， 在适应度函数中引入了惩罚度设计， 也在一定程度上提升了遗传算法的进化效果.

测试结果表明， 本文算法能够高效合理地求解走班排课问题， 在不考虑课时设置错误的情况下，算法能够消除所有的资源冲突并在最大程度上符合教务老师设定的各种排课约束条件， 极大降低了教务老师在课表编排上所花费的时间精力， 满足了学生个性化教育的需求， 该排课方法实践起来也更为简单且通用性良好， 具有很好的实际应用意义.

[ 参 考 文 献]

[ 1 ] 夏永庚， 朱琴. 走班制背景下高中班主任德育工作的挑战与应对 [J]. 现代基础教育研究， 2019， 33（1）： 215-220.

[ 2 ] GOTLIEB C C. The construction of class-teacher timetables [J]. Communications of the ACM， 1962， 5（6）： 73-77.

[ 3 ]EVEN S， ITAI A， SHAMIR A. On the complexity of time table and multi-commodity flow problems [C]//16th Annual Symposium onFoundations of Computer Science （SFCS 1975）. IEEE， 1975： 184-193. DOI： 10.1109/SFCS.1975.21.

[ 4 ]张艳红， 王玲玲， 腾东兴. 基于空间模型和遗传算法的高校排课系统 [J]. 计算机系统应用， 2015， 24（9）： 49-55. DOI： 10.3969/j.issn.1003-3254.2015.09.008.

[ 5 ] 袁俊毅. 基于遗传算法的高校教务排课系统设计与实现 [D]. 长沙： 湖南大学， 2017.

[ 6 ] 姜婧， 白似雪. 遗传算法的改进及其在排课问题中的应用 [J]. 南昌大学学报（理科版）， 2018， 42（4）： 388-392.

[ 7 ] 唐环， 高健. 在中学排课问题中实用的模拟退火算法应用 [J]. 计算机系统应用， 2017， 26（10）： 225-230.

[ 8 ]THEPPHAKORN T， PONGCHAROEN P， HICKS C. An ant colony based timetabling tool [J]. International Journal of ProductionEconomics， 2014， 149： 131-144. DOI： 10.1016/j.ijpe.2013.04.026.

[ 9 ] 張媛， 祁兰. 基于禁忌搜索的排课系统的设计 [J]. 电子设计工程， 2016， 24（22）： 71-73.

[10]FONG C W， ASMUNI H， LAM W S， et al. A novel hybrid swarm based approach for curriculum based course timetabling problem[C]//2014 IEEE Congress on Evolutionary Computation （CEC）. IEEE， 2014： 544-550.

[11]王卫红， 李文琼. 基于改进遗传算法的高中走班制排课算法 [J]. 浙江工业大学学报， 2016， 44（6）： 601-607， 670. DOI： 10.3969/j.issn.1006-4303.2016.06.002.

[12] 陈璐， 王秀. 改进遗传算法求解走班制下的排课问题 [J]. 计算机工程与应用， 2019， 55（6）： 218-224.

[13] 马辉辉. 走班制的实施与注意问题 [J]. 教育与教学研究， 2016， 30（2）： 99-103. DOI： 10.3969/j.issn.1674-6120.2016.02.019.

[14] 张贵军， 陈安， 胡俊. 基于蒙特卡洛遗传算法的排课问题研究 [J]. 实验技术与管理， 2019， 36（3）： 170-174.

[15] 冯智莉， 易国洪， 李普山， 等. 并行化遗传算法研究综述 [J]. 计算机应用与软件， 2018， 35（11）： 1-7， 80.

[16] 葛继科， 邱玉辉， 吴春明， 等. 遗传算法研究综述 [J]. 计算机应用研究， 2008， 10： 2911-2916. DOI： 10.3969/j.issn.1001-3695.2008.10.008.

[17] 王赞， 樊向宇， 邹雨果， 等. 一种基于遗传算法的多缺陷定位方法 [J]. 软件学报， 2016， 27（4）： 879-900.

[18] 雷英杰， 张善文. MATLAB遗传算法工具箱及应用 [M]. 西安： 西安电子科技大学出版社， 2014.

[19]董玉锁， 贺波， 尹迎， 等. 利用改进遗传算法破解排课难题 [J]. 中国教育技术装备， 2018（1）： 16-19. DOI： 10.3969/j.issn.1671-489X.2018.01.016.

（责任编辑： 李 艺）