基于改进遗传算法的高校排课优化问题研究

李　阳,张　欣

(贵州大学 大数据与信息工程学院,贵州 贵阳　550025)



基于改进遗传算法的高校排课优化问题研究

李阳,张欣

(贵州大学 大数据与信息工程学院,贵州 贵阳550025)

摘要针对高校排课工作量大等问题,提出了基于改进遗传算法的课表优化方案。以教学任务为基因进行编码,总课表(行为时间段,列为班级)为DNA随机产生若干个满足强制规则的初始种群,将遗传算法中的随机交叉改进为局部列完整交叉算法,随机变异改进为列内部随机互换算法,并通过若干代的迭代优化,促使最终生成一个科学合理的排课方案。实验仿真表明,课表适应度由最初的76.0提升至123.0,优化效果显著。

关键词排课;优化;改进遗传算法

高校排课的实质是教务系统根据每个学期各个学院的教学任务,给每个班级合理安排课程,任课老师,上课地点等。排课问题涉及因素众多,各个因素之间互相影响,相互制约[1]。遗传算法是通过模拟达尔文的生物进化规律演变而来,具有高度并行、自适应的、随机的、全局寻优的搜索方法[2-3]。其通过对当前群体施加一系列的遗传操作,从而产生新一代群体,促使群体进化到接近最优解的状态,是一类具有较强鲁棒性的优化算法。简单的将遗传算法应用到排课优化问题中会出现收敛速度慢,易产生无用课表等问题[4]。本文采用改进遗传算法对排课问题进行研究。运算时间显著减少。

1高校排课问题限制因素

排课问题中的规则可分为两大类:强制规则和优化规则。强制规则是不可违背的,否则该课表是不可行的。优化规则应当尽量满足,满足的优化规则越多说明该课表越优秀。

强制规则:(1)依据教学计划,不得随意更改课程;(2)一个班级不能在同一时间被安排不同课程;(3)一位老师不能在同一个时间上不同课程;(4)一间课室不能在同一个时间段为两个班级所用,除非两个班级课程相同;(5)课室的座位数略大于等于上课的学生人数。

优化规则:(1)一个星期之内应间隔排列好各门课程;(2)课程应安排在学习效率较低时;(3)难度高的课程后应搭配难度低的课程;(4)共同科目可考虑合班上课。

优化规则还有诸多种,具体要根据实际情况而定。

2改进遗传算法解决排课优化问题

“适者生存,优胜劣汰”。这是遗传算法的主要思想。遗传算法是一种随机的全局搜索和优化算法[5]。其从一个种群开始,该群种可能是问题的一个可能潜在解集。该种群在进化过程中,遵守“优胜劣汰”规则。在每一次进化开始之前,计算当前种群中个体的适应度(Fitness)。种群的适应度越高,说明其基因越好,应遗传到下一代。接下来,借助代表自然遗传学的遗传算子(Genetic Operators),不断进行组合交叉(Crossover)和变异(Mutation)等操作,产生子代(代表新的解集的种群)[6]。周而复始,适应度低的个体被淘汰。按照这样的步骤操作下来,新生成的种群总比前一代更加优秀。因此,经过若干代的进化后,最后的一个种群将是最优种群。

遗传算法的一般步骤如下:首先初始化一个种群,然后利用适应度计算函数计算该种群中每个个体的适应度,然后根据指定规则计算个体是否满足优化准则的判定标准[7],若满足,则算法停止,当前种群就是最优的种群。若不满足,就选取适应度高的个体,对这个种群的个体进行遗传操作,经过演化后的子代种群利用已有规则,重新判定优化准则的满足程度,从而进化成新的种群。

本文通过改进遗传算法中的基因编码方法,交叉算法中的交叉方式,变异算法中的变异方式,解决了在交叉和变异过程中产生不满足强制条件的课表问题。

2.1排课优化算法与遗传算法相对应

基因是组成染色体的基本单元,在排课问题中,基因应包括:课程-教师-教室-时间段-班级信息。通过计算机排课就必须考虑编码的问题。好的编码方式能大幅提高算法的效率。针对此问题,文中采用十进制编码,其可更好的提升计算机的运算效率,更小的减少内存占用。这里采用十进制意味着我们要将每一门课程重新编码,以贵州大学为例:公共课外语(英语)的课程编号为:10657M101,而英语这门课又分为上下两个学期,上学期课程编号为10657M101-1,共十一位,其中包含数字,英文字母,特殊符号。这在后续的计算机运算当中会增加大量的开销。所以将其直接编码为4位十进制码0001;教师ID由于每个学校采用的方式不统一,因此重新编码可增加该系统的扩展性,这里也采用4位十进制码。教室的编码方式与之前有所区别,在此将最高位1表示普通教室(无多媒体),2表示普通教室(多媒体),3表示阶梯教室,4表示实验机房,针对具体情况还可细分。后3位表示教室编号。时间段代码采用2位十进制,这里假设每天划为4个时间段上课,一周上5天。即将一周划为20个时间段,用01～20表示。班级采用4位十进制表示,如用0022表示通信2班。然后一个基因就编为18位十进制码,如000100252110050022表示英语课编号为0025的老师授课,地点在多媒体教室110,上课时间是周二上午前两小节,上课班级为通信2班。至此基因编码结束。

染色体则对应问题的一个可能解,是基因的综合体。是遗传算法操作的基本对象。在此对应的就是一种排课方案。遗传算法中要求随机产生若干个染色体,即随机产生若干个课表,但在实际中这些随机产生的课表有较大一部分不满足强制规则的无效课表。这些课表在后续的遗传算法操作中已经没有必要。因此,这里要求进入后续交叉变异等操作的课表都必须是有效的。之前的冲突检测是在课表生成之后再开始检测,若发现某张课表中出现冲突,则将该课表删除,重新生成一张。因一张课表的强制条件较多,这种方法会带来较大开销。本文采用的方法是在随机产生的一张课表基因过程中就进行冲突检测将各个冲突排除。由此可为后续的计算减少大量开销。为了更好的消除冲突,在此采用一张二维表的方法,横轴是班级,纵轴是时间段。

表1　全校总课表

冲突消除方法如下:(1)同一个时间、班级上不同课的冲突。因这是张二维表,同一时间同一班级对应的是表中的某行某列的一个元素,填表的时候不会产生冲突;(2)一个老师不能在同一个时间段上不同的课程。这只需要检测同一行教师代码,若教师代码相同则要求课程代码不允许相同,若课程代码也相同则重新随机产生一个教学任务;(3)一间教室在同一个时间段不能为两个班级所用。

检测每一行。若课程编号相同,则两个班级可合并上课,若课程编号不同则重新随机生成一个新教室。

至此,排课表的主要冲突检测和解决完毕。一张满足强制规则的课表在后续优化中才有意义,否则只能给计算机增加额外的无用开销。

适应度评价函数使用计算染色体特征值的方式,其表示个体对应解的优劣[8]。在此考虑两个因素,第一个是时间优化度,即表示课程应当尽可能的安排在学生学习效率高的时间段;第二个是节次优化度,即表示若一门课每周上两次,其应被间隔开。若连续两次相同的课,学生和教师均会感觉到力不从心。这里采用适应度函数为e=w1a2+w2b2;a和b分别表示时间优化度适应度和节次优化度适应度。w1和w2代表对应的权值。

初始群种随机生成若干种排课方案的集合,表示基于遗传算法的排课的搜索空间。

选择操作采用最经典的轮盘赌算法,其思想是不同个体的适应度在一个种群中所占比例的总和为 1,呈现在一个轮盘上,个体的适应度越大,被选中的机会越高[9]。

交叉算子,父个体按照一定的概率随机交换基因形成新的个体,在本课题中采取局部列完整交叉操作。例如选中第1张课表的班级3和第5张课表的班级7,则将这两张课表中的这两列完全互换。采用此交叉方法的原因是:若完全随机选择若干个基因进行交换,必然会带来同一列中的课程冲突,而一旦产生冲突,此时只能删除课表,将导致课表总量下降,不满足遗传算法思想。

变异操作,变异的目的:一是产生新的个体,使遗传算法维持种群的多样性;二是当种群的所有个体差异已较小时,交叉操作已没有意义,只能靠变异来产生新的个体;第三个目的是变异算子既能加速向最优解的方向收敛,又能有效抑制遗传操作过早地结束收敛。但变异概率只能取较小值,否则可能破坏已确定的最优解区域。这里采用改进型的变异算法,以往的变异算法通常变异是完全随机的,这样有较大的概率会使生成的课表不满足强制规则,成为无用解。而采用的变异算法是直接互换某一列中的若干位基因,这样在同一列上不会产生冲突。可避免将一个有效解变异为无效解。

终止条件可分为两种,第一种是达到了自定义的适应度要求,通常人们均想以这种方式完成迭代获得最优解。但一般由于不了解适应度值该如何设置,因此通常不适合;第二种是达到一定的迭代次数,这个更易设置,算法上实现也较为简单。

2.2基于遗传算法排课优化流程描述

(1)对课程信息进行编码;(2)初始化遗传算法种群;(3)计算种群适应度,若满足终止条件则跳转至(7)。否则跳转至(3);(4)计算个体适应度,进入轮盘赌选择操作。被选中个体跳转至(4)。未被选中个体直接进入子代;(5)被选中个体进行交叉、变异操作后进入子代种群;(6)获得子代种群后跳转至(3);(7)译码输出,算法结束。

2.3软件运行结果

本文算法的主要目的是提高课表适应度,先将课程信息进行编码,0表示休息,1～8表示不同课程。生成的初始种群如图1所示,最上方表示该DNA的适应度。经过若干代迭代后,适应度由76提升至123,编码后的课表如图2所示。对该DNA进行译码处理后,第一列表示第一和第二个班级课表如图3所示。

图1　初始种群中的一个DNA 适应度为76.0

图2　改进遗传算法优化后DNA,适应度到达123.0

图3　第一个和第二个班级课表输出结果

3结束语

本文以所在学校为背景,首先分析了排课问题的复杂性,接着简要分析了遗传算法思想及解决排课优化问题的可行性。给出一般遗传算法的计算步骤、排课问题的强制条件和优化条件,然后分析了使用遗传算法解决排课优化问题的方法即详细步骤。在根据学校的情况验证了整个排课过程,印证了此排课优化算法的科学性和合理性。通过该方法能够显著减轻教务员工的工作量,提升工作效率。此智能排课算法虽可实现智能排课优化,但使用范围有限,只能针对公共课的排课问题,目前诸多高校已开设不同的选修课,班级不再固定,对智能排课系统提出了更高的要求,这也是本课题后续研究的方向。

参考文献

[1]丁健.基于遗传算法的排课系统的设计与实现[D].武汉:华中科技大学,2011.

[2]周德全.免疫遗传算法及认知无线电参数优化决策[J].通信技术,2012,45(2):53-55.

[3]夏磊,俞能海.基于遗传算法的小卫星任务调度[J].通信技术,2013,46(11):64-68.

[4]王彦,王超,刘宏立.模拟退火遗传算法在多用户检测技术中的应用[J].电子技术应用,2011,37(4):102-105.

[5]侯福均,吴祈宗.基于遗传算法和模拟退火算法优化神经网络的铁路营业里程预测[J].北京理工大学学报,2004,24(3):247-250.

[6]Holland J.Adaptation in natural and artificial systems[M].England:A Bradford Book,1975.

[7]林茂,李孝全,苏杨.基于改进免疫遗传算法的电网故障诊断研究[J].电子技术应用,2012,38(8):66-68.

[8]冯阿芳.基于遗传算法的自动组卷策略[J].哈尔滨师范大学自然科学学报,2008,24(4):27-28.

[9]彭新竹.遗传算法的改进策略及其应用[J].华东船舶工业学院学报:自然科学版,2002,16(3):53-58.

Arrangement and Optimization of College Curriculum Schedule by Improved Genetic Algorithm

LI Yang,ZHANG Xin

(Big Data and Information Engineering College,Guizhou University,Guiyang 550025,China)

AbstractIn order to solve the problem of the large amount of work multi condition and high complexity in the course of the college arrangement,we propose a schedule optimization scheme based on the improved genetic algorithm with the teaching mission and total schedule as the gene and DNA,respectively and the initial population randomly generated to meet the mandatory rules for the DNA.Some improvements of the genetic algorithm are discussed,including changing random cross column to be a local full cross algorithm,and random mutation to be random swap algorithm for the inside of column.The final form of a scientific and rational arrangement plan is obtained through several generations of iterative optimization.Experiment results show that the fitness schedule increases from 76 to 123,indicating a good optimization effect.

Keywordscourse scheduling;optimization;improved genetic algorithm

doi:10.16180/j.cnki.issn1007-7820.2016.05.034

收稿日期:2015-10-14

作者简介:李阳(1989—),男,硕士研究生。研究方向:移动通信技术。张欣(1976—),男,博士,副教授,硕士生导师。研究方向:下一代无线通信及应用等。

中图分类号TP391

文献标识码A

文章编号1007-7820(2016)05-127-04