智能排课优化算法研究

吴　琼

( 黎明职业大学 信息与电子工程学院， 福建 泉州 362000 )



智能排课优化算法研究

吴琼

( 黎明职业大学 信息与电子工程学院， 福建 泉州 362000 )

摘要：为解决高校排课优化问题，建立了以教学效果好评度最大化为优化目标的排课数学模型.针对传统遗传算法的不足，给出了一种混合遗传算法，该算法不仅能够对传统遗传算法的交叉率、变异率进行自适应改进，还能够实现冲突检测与消除功能.测试结果表明，该算法比传统的遗传算法、贪婪算法和蚁群算法耗时短，而且教学效果好评度最高，这说明该算法能有效缩短排课时间，提高排课质量和效率，实现高校排课智能化. 高校排课； 教学效果好评度； 自适应调整； 冲突检测与消除； 混合遗传算法 TP391.9

文献标识码：A

随着高校规模的扩大，许多高校教学资源短缺的情况日益凸显，使得排课问题成为教务管理中较为困难的一项工作.目前，国内高校排课还主要依赖人工操作为主，为了避免排课冲突，工作人员需反复进行调整，缺乏智能性和科学性[1]，而且工作量巨大、效率低；因此，寻求一种科学排课的智能方法，对于提高排课效率和教学效果具有重要意义.

目前国内许多高校针对排课系统进行了研发，如清华大学的TISER系统、西北工业大学的科教排课系统和南京工学院的UTSS系统.这些系统在一定程度上提高了排课工作的效率，但这些系统毕竟都是依照自身院校实际情况研发的，并不具有普遍的通用性，其他高校引入后仍需大量的人工调整.针对这些情况，本文依据排课规则，以教学效果好评度为优化目标，构建了排课数学模型，实现了排课优化设计和排课冲突检测与消除功能，大大减少了后期人工调整的工作量.众所周知，排课问题即教室、课程、教师、学生、时间等多因素的组合，是一个NP组合优化问题，解决该类问题常用的方法有遗传算法(GA)[2-3]、贪婪算法[4]、蚁群算法[5]等智能算法，其中贪婪算法由于度量标准难以把握往往会导致难以真正实现智能排课，蚁群算法由于搜索时间过长，容易因较优解的信息强化而出现早熟、停滞现象.因此，本文设计了一种混合遗传算法(HGA)进行排课，并将其结果与遗传算法、贪婪算法和蚁群算法进行了比较，以此验证了本文算法的有效性和优越性.

1排课问题

1.1　排课问题数学描述

课程-时间-教室关系如下：

1.2　约束条件

合理排课就是令教师、教室、班级、课程和时间5个因素不发生冲突，以便教学活动能正常进行.因此本文将这5个因素作为约束条件，当满足所有约束条件时，即实现排课无冲突.约束条件[6]描述如下：

(R1)同一时间，1位教师只能承担1门课程；

(R2)同一时间，1个教室只能安排1门课程；

(R3)同一时间，1个班级只能安排1门课程；

(R4)同一时间，上课的课程数应少于或等于教室数；

(R5)上课班级的学生数应少于或等于教室容量；

(R6)将1天分为上午2个、下午和晚上各1个共4个教学时间段，1周5天为19个时间段(星期三下午空置)，1个时间段至少有1个班级有课；

(R7)同一班级所上同一门课程时间安排起码应有1天的间隔；同一班级同一个半天教室安排应尽量接近；同一教师同一个半天教室安排应尽量接近；每一个班级周课时应尽量均衡等.

上述约束条件中，R1—R5为硬约束条件，R6为算法有解保证，R7为软约束条件.

1.3　教学效果好评度分析

由于师生的个人喜好、学生对知识的接受能力和记忆强弱等原因，不同的授课时间会造成教学效果的差异，即教学效果好评度[7].通过对某校师生进行调查后，获得了不同节次、不同周次对应的教学效果好评度表，如表1和表2所示.

表1　上课节次教学效果好评度表

表2　上课周次教学效果好评度表

注：表2中，周次(一、一)上课时间为周一搭配周一，以此类推.

1.4　排课问题数学模型的建立

综上分析，将教学效果好评度作为排课问题的优化目标，构建排课问题优化模型：

(1)

约束条件R1—R7.

式(1)中，目标函数中的Fmax为多种排课方案中教学效果好评度最大化对应的排课方案.

2混合遗传算法

遗传算法是一种搜索启发式算法，它不受问题本身的限制，仅在目标函数的准则下进行全局自适应搜索，其强大的鲁棒性非常适合求解如排课这种NP的数学问题最优解，但传统的遗传算法在NP问题的求解过程中容易因早熟而导致局部收敛.为了解决这一问题，本文在传统遗传算法的基础上对交叉率和变异率进行了改进和优化[8]，使其具有自适应调整功能，从而获得全局最优解.

2.1　初始种群和编码设置

传统遗传算法的初始种群通常是采用随机方式产生，所生成的初始种群存在分布不均匀、优化性能不好等问题；因此,本文采用归一化方法对初始种群进行处理，保证其解尽可能均匀地分布于解空间，以避免早熟现象，从而能有效地获得全局最优解.选择十进制编码，生成一条共18位的染色体，如图1所示.染色体5102-0018-3105-0400-52包含的信息为：工号为5102的教师给编号为0018的班级上代码为3105的课程，上课地点为编号0400的教室，上课时间为周五的第2个时间段(即上午3、4节).

图1　排课表染色体基因组成结构图

2.2　适值函数的确定

在遗传算法的进化过程中，个体的适值大小将决定其是否会被淘汰，通过合理设置适值函数[9]可有效避免算法过早收敛，获得全局最优.鉴于排课问题是一个多目标优化数学问题，本文的适值函数的设计思路是将多目标优化和适值函数相结合，构建基于各目标值的贡献大小分配对应权值的个体适值函数，则适值函数为：

(2)

式(2)中fi为各影响因素的教学效果好评度， ai为各影响因素对应加权值.适值F(x)越大，则说明课表编排越合理.

2.3　遗传算子操作

1)选择.基于适者生存的进化机制，在已生成的种群群体中，通过对个体的适值进行评价，将适值较高的个体选择出来并将其优秀的基因通过交叉变异操作遗传至下一代.假设排课种群规模为N， 各个个体对应的适值为fi， 采用轮盘赌选法，则个体被选中的概率为：

(3)

由式(3)可看出，适值越高的染色个体被选中的机会越大.

2)带自适应功能的交叉和变异.从种群中随机抽取2个父代染色个体，对其一部分进行交叉组合操作，使其重组产生更为优秀的2个子代染色个体插入新群体中.变异操作是在对种群中的个体基因进行变异以获得更为优秀的染色个体.由于交叉概率Pc和变异概率Pm决定后代个体的多样性，为提高搜索能力，避免局部最优解产生，本文对传统交叉、变异操作进行了改进，设置了自适应调整的交叉率和变异率，以此提高算法的全局最优性.具体设置为：

(4)

(5)

式(4)和式(5)中fmax为最大适值， favg为平均适值， f为父代染色个体中适值较大的个体.当父代适值高于平均适值时，应减小当前交叉率和变异率，以保证拥有优秀基因的染色个体能够顺利进入子代；当父代适值低于平均适值时，保持当前交叉率和变异率.

2.4　冲突检测与消除操作

当生成的种群解不满足排课约束条件时，会导致课表安排不合理，即出现课表冲突现象，如同一时间同一班级上2门课程；因此，需对每代新生产的种群进行冲突检测，并及时对存在的冲突进行处理.以同一时间一位教师教授2门(含2门)以上课程为例，其冲突检测与消除实现步骤如下：

1)将19个时间段与n门课程信息编制为一个二维数组课表TC，行为时间，列为课程，形成19×n个单元格.

2)将在染色体信息中提取的对应时间-课程信息，在二维数组表中找到对应单元格后填入教师编号.

3) i=1， j=1.

4)判断TC(i,j)与TC(i,j+1)的教师编号是否相同.若相同，令I′=(1~20的任一随机整数)，再将TC(i,j+1)和TC(I′,j+1)教师编号调换，跳转4);若不相同， j=j+1， 跳转5).

5)判断j等于n否，若不相等，跳转4)；若相等，令i=i+1， 跳转6).

6)判断i等于20否，若不相等，跳转4)；若相等，完成冲突检测与消除.

2.5　混合遗传算法的实现步骤

混合遗传算法的实现步骤为：

1)初始化参数.将种群规模设置为100，设定变异概率Pm初值为0.07，交叉概率Pc初值为0.95；

2)十进制编码，生成初始种群，做归一化、冲突检测和消除处理后，根据式(2)计算初始种群各个个体的适值作为个体评价依据；

3)遗传操作.基于轮盘赌选法原理，根据式(3)计算选择概率Pi并进行选择操作；

4)对交叉概率Pc和变异概率Pm进行自适应调整.若当前子代个体适值大于平均适值，则根据式(4)和式(5)调整Pc和Pm，否则保持Pc和Pm不变；

5)以交叉概率Pc和变异概率Pm进行交叉变异操作生成子代种群，进行染色体冲突检测和消除操作；

6)计算各个个体的适值，若子代个体适值大于父代个体适值，则采取替换操作，否则保持父代个体；

7)重复步骤3)—步骤6)，直至满足算法终止条件；

8)输出最优解.

混合遗传算法流程图如图2所示.

图2　混合遗传算法流程图

3实验数据测试及分析

以黎明职业大学排课为例，测试数据为：106名教师、4 400名学生、88个班级、129间教室和324门课程.算法最大进化代数设置为100~500，各自进行20次测试后取平均值，其结果如表3所示.

表3　进化代数测试对比表

由表3可看出:进化代数由300增加到500时，其最优适值并无明显改善,且当进化代数为300时，其计算耗时仅为400代所需耗时的68.3%， 500代的51.9%；其运行次数仅为400代运行次数的70.2%， 500代的53.6%.从运行耗时和次数的节约考虑，本文将进化代数设置为300.

由图3可以看出，函数在前100代上升迅速，约在150代后趋于稳定，并达到函数最佳适值，由此说明混合遗传算法具有快速收敛性，其解收敛于全局最优解.表4为混合遗传算法(HGA)、传统遗传算法(GA)、贪婪算法和蚁群算法的优化结果.

图3　适值与进化代数关系曲线图

指标HGA算法GA算法贪婪算法蚁群算法平均耗时/s164.868175.633179.845180.329平均教学效果好评度/%91848885

由表4优化结果可知：采用混合遗传算法进行排课，其计算时间比传统遗传算法节省了6.53%，比贪婪算法节省了9.08%，比蚁群算法节省了9.38%;优化后的教学效果好评度比传统遗传算法高7.7%，比贪婪算法高3.3%，比蚁群算法高6.6%.这说明了本文提出的混合算法的合理性和优越性.此外，在排课中，当涉及的班级、教师和课程等数量越多时，其优化效果会更加明显.

4结束语

本文以教学效果好评度最大化为优化目标，构建了高校排课优化设计数学模型，并提供了一种将自适应调整功能融入交叉变异操作的混合遗传算法.该算法既提高了算法搜索能力和全局最优性，还实现了课表冲突检测与消除功能.测试结果表明，该混合算法可获得较高的教学效果好评度，节省排课耗时时间，很好地提高排课的效率及质量，具有较好的实际应用意义.本文获得的测试结果并未涵盖本校所有的排课资源，下一步的研究内容应全面覆盖所有排课数据以及尝试与其他智能算法进行结合以进一步改进和完善本文算法.

参考文献：

[1]孙丹莹.高校排课问题与算法分析[J].信息与电脑,2012,10:210-211.

[2]钟耀广,刘群锋.基于遗传算法的高校排课数学模型[J].东莞理工学院学报,2012,10(19):4-8.

[3]陈行平,陈江,陈启华.基于遗传算法的高校排课系统设计[J].绍兴文理学院学报,2004,34(20):25-28.

[4]赵耀锋.基于贪婪算法的多媒体教室排课算法设计[J].信息技术,2013,13:80-82.

[5]何小虎.一种改进蚁群算法在排课中的应用研究[J].电子设计工程,2012,8(20):28-29.

[6]宗薇.高校智能排课系统算法的研究与实现[J].计算机仿真,2011,28(12):389-392.

[7]范文广.基于遗传算法的排课设计[J].齐齐哈尔大学学报,2011,27(5):27-29.

[8]刘化龙,胡钋,青志明.基于混合遗传算法的变压器局部放电超声定位法[J].兰州理工大学学报,2014,12(40):105-109.

[9]刘秋红,寒枫,张钰，等.基于分层的自适应遗传算法在UTP中的应用研究[J].贵州大学学报(自然科学版),2007,24(2):184-187.

Research of optimization algorithm for course timetabling problem

WU Qiong

(CollegeofInformationandElectronicsEngineering,LimingUniversity,Quanzhou362000,China)

Abstract：In order to solve the problem of university course timetabling, a mathematic model was established based on the objective function of maximum teaching effect praise degree. Aiming at the shortcoming of traditional genetic algorithm, a hybrid genetic algorithm which combined with self-adaptive crossover and mutation were put forward. The conflict detection and elimination function were realized. The test result show that hybrid algorithm was faster than traditional genetic algorithm, greedy algorithm and ant colony algorithm but the highest teaching effect praise degree. It proved that the algorithm shorten the time consuming, improve the quality and implementation the intelligence of course timetabling effectively.

Keywords：university course timetabling; teaching effect praise degree; self-adaptive adjustment; hybrid genetic algorithm; hybrid genetic algorithm

文章编号：1004-4353(2015)04-0331-06

作者简介：吴琼(1979—)，男，讲师，研究方向为网络技术与智能优化算法.

收稿日期：2015-07-25