遗传算法在高校排课中的应用

刘海燕

摘要：随着我国高等教育的发展，各高校都力争在有限的资源下，更为有效地提高教育教学质量，在这个过程中合理地安排培养方案中的课程是一个非常重要的环节，因为这个环节包括教师、学生、教室三个方面的合理应用，本文通过研究高校排课的具体环节和所遇到的问题，针对教室安排、冲突判断和时间设定三个方面来设定遗传算法的参数，利用遗传算法对种群进行初始化和进化，寻找最佳的排课结果，并对算法进行仿真验证，结果表明，遗传算法可以应用在高校智能排课当中。

关键词：排课 遗传算法 多目标 优化

中图分类号：G642  文献标识码：A  文章编号：1009-5349（2019）03-0153-02

随着各高校学生数目的增多;教学质量和教学效果日益被重视;教室、教师、多媒体越来越紧缺;那么如何能将这些资源更为合理地利用，优化各种资源，把最有限的资源最大化地让学生们利用是各大高校面临的最难的一个课题，而且各高校为了学生们的个性发展，有一些课程需要选课，有一些课程不需要选课，这无形中加大了排课的难度，因此传统的手工排课很难满足学校的要求，应用计算机技术结合智能算法进行排课已经成为高校教学管理发展的必然趋势。各种智能算法也就随之产生了。在诸多的排课要求当中，如何综合地考虑这些要求，并应用算法编排出合理的课表已经是各研究人员和教务一线人员研究的方向。

排课算法是实现智能排课的核心部分，本文将结合学校的实际情况分析课表编排的实际原则和具体要求，综合各种课表的约束，挖掘排课当中会遇到的各种因素，在设定遗传算法的各个参数，并通过实际仿真验证算法的可行性与可信性。

一、遗传算法

遗传算法的思想是根据生物进化论的基本思想，将需要解决的问题建立起数学模型，模拟生物进化的整个过程，仿生基因的复制、交叉以及突变来不断优化个体，从而找到最优化的解，并不断地淘汰适应度比较低的解。

（1）编码。计算机识别的是0～1代码，所以需要将所面向的问题数字化，编辑成二进制数组的形式。遗传算法中的编码选择、交叉和突变都必须是数字类型的编码进行改变。

（2）选择。选择更优化的解作为算法的结果，也就是个体适应度高的就会被留下，适应度函数低的就会被舍弃，如果个体数目为N，那么每个个体被选中的概率就是f（Xi）/（f（X1）+f（X2）+…+f（Xn），也就是所谓的轮盘赌算法。

（3）适应度函数。适应度函数是遗传算法来衡定个体是否是最佳结果的标准，然后确定该值是否再向下遗传，有很多问题是直接将目标函数设定为适应度函数，从而确定选定的值是否为最佳。

（4）交叉函数。交叉运算是遗传算法很关键的一步，是以一定的概率将个体当中某处进行交换，一般的步骤是先将群体中的多个个体进行随机配对，然后再随机设定交叉点的位置，最后交换染色体相应位置的基因，计算产生新基因的适应度。

（5）变异运算。变异运算是对一个染色体的某一位或者是某一段进行变异操作使其成为新的染色体，首先挑选染色体变异的位置，然后对相应位置的数值进行变异操作。

二、排课问题分析

（一）排课分析指标

1.排课最基本的要求

排课最基本的要求是不能冲突，同一时间同一批学生只能上一门课，同一时间一名教师只能上一门课，教室容量要满足学生数的要求，教室类型也要和要求保持一致。

其中td表示某一天学生上课的节数，n表示学生们则可以有课的天数，全校各个班级平均值用总数除以班级总数，一般来说，大学里课程平均每天三节左右，因此如果平均值特别高就可能说明教学环节设计不合理或是排课时分布很不均匀。全校课程分布均匀也说明教室利用率高，因此是一个重要指标。此外，要将上课时间设定优先级，尽量将必修课安排在优先级比较高的时间，如果课程超过两学时，尽量保证有两节课是间隔分布，教室要根据人数来设定选择，学生连续的课不要两个校区来回跑。

（二）排课问题的具体设计

1.遗传算法编码

遗传算法需要对所分析的问题进行编码，设定为最基本的基因，班级号、教师编号、课程信息组成编码，需要说明的是大学里每门课程都是两小节连上，也就是如果周一到周五全上课的话将是25个时间段;课程编号包含了课程的所有信息，在课程编号前面加上一位设定教师的第几节课，从而更能全面地考虑课程安排;同理，班级序号和教师编号也包含了班级信息和教师信息，因此，系统要得到完善的课表就需要对编码进行分析和处理。

2.产生初始基因和冲突的检测

遗传算法首先需要生成初始群体，这初始群体的设定要避免各种冲突，如果算法运行当中产生冲突，就需要将冲突的时段换掉，消除冲突。

3.适应度函数的选择

排课问题是一个多种约束的问题，在数学里也就是所求目标在有多个条件束缚的条件下寻找最佳解，遗传算法需要根据适应度函数的值来确定解的改进和进化方向，因此适应度函数是一个非常关键的问题，为了各个方面达到最优，我们设定多个子函数，然后将子函数的和作为整个算法的适应度函数。

4.选择函数

采用轮盘赌来选择基因，该方法将一个轮盘分为多个区域，区域的大小是根据适应度的大小来劃分，适应度值高，所占的比例就大，也就是下一代会更适应目标。

5.交叉和变异

在排课中最简单的交叉就是交换班级，首先判断交换的班级是否合适，如果合适，将两条染色体相应位置进行交叉，遗传算法变异是以特定的概率找到两个染色体，交换相应的位置，然后判断是否满足各种不冲突的条件。

6.遗传算法流程

具体的遗传算法流程是：①首先将排课问题数字化，初始化各个指标产生种群;②计算每一个排课方法的适应度;③选择优异的染色体，进行下一代子体;④对种群中的个体交叉和变异，从而新生个体，再计算新的个体适应度来确定是否进入下一代;⑤判断是否目前是最优的排课方案，如果是就可以结束程序否则再转换到②继续进行计算。

三、实例分析

（一）测试数据

测试数据来自于我校建工学院2017—2018第二学期秋季课表，所有测试过程采用VC++进行编程，基本数据见下表：

其中交叉概率和变异概率通过程序运行的结果可以进行调整。本文通过多次试验得出当交叉率为0，2，变异概率为0.05时取得了较好的排课结果。

（二）仿真结果分析

由图表可知当迭代次数达到设定次数的时候算法的适应度值已经趋于稳定，适应度值也是很高，且整个算法对排课的计算过程在10分钟以内。尽管如此，在实验过程中，遗传算法的排课结果还存在着一些问题，比如单双周的课程还不能很好地排课，特殊教室不能满足课程的需求，特殊时段要求过多导致程序出现问题，因此出现问题的课程还需要进行再次检验，当然这也是少数的特殊情况，也是由于人性化要求过多导致的。因此，在录入排课要求的时候下属学院也要衡量其可行性，尽量减少过多要求的课程。

四、结论

通过对排课问题的分析，判断是一种多目标的优化问题，为了减少人工排课效率低下，容易发生错误的问题，本文提出采用先进的遗传算法来完成该项复杂的任务。仿真结果表明，遗传算法可以在一定程度上解决排课过程中产生的问题，大量减少了教务工作者的劳动力，是值得推广的。但是由于排课是一个数据量非常大，考虑问题非常多，约束条件十分复杂，并且不断变化的综合性问题，本课题在排课算法思考当中还有很多地方不完备，设计还不是很完美，比如单双周课程、特殊课程以及提高运行速度等方面，以后也将继续思考该方面的问题，将遗传算法的一些方面进行改进，从而达到最佳的排课效果。

参考文献：

[1]马传志，刁树民，张晓勇等.基于改进遗传算法的排课方法研究[J].中原工学院学报，2013（2）.

[2]姜静，谭博学，姜琳.基于改进自适应遗传算法的仿真研究[J].山东理工大学学报（自然科学版），2008（6）.

[3]宋岐.基于遗传算法的排课系统开发探究[J].电子测试，2016（Z1）.

[4]张旭.基于遗传算法的中职在线排课系统的设计与实现[J].计算机产品与流通，2017（11）.

责任编辑：赵慧敏