基于灰狼算法的高校实验课网络排课问题研究

阮德致, 梁荣, 迟军, 季英萍

(宁波工程学院 杭州湾汽车学院， 浙江 宁波 315000)

0 引言

随着我国高等教育规模的扩大和在校人数的增加，排课的工作量和难度不断增加，因此研究高校实验课网络排课系统算法具有重要的理论价值和实际意义[1]。传统的人工排课算法具有任务量大、费时和效率低下的缺点，随着人工智能算法、运筹学和计算机科学的发展，很多群智能算法被应用于课程编排领域，比如粒子群算法和遗传算法[2、3]，为课程编排提供了新的方法和途径。然而，粒子群算法不能单独解决课程排课约束问题，遗传算法虽然可以解决约束问题，但存在计算时间过长的缺点。

灰狼优化算法(Grey Wolf Optimization Algorithm，GWO)是模仿灰狼等级划分和灰狼捕食行为而提出的群智能搜索算法[4]。该算法具有控制参数少、收敛速度快和计算简单等优点，已在机器学习、函数寻优、数据挖掘、电力调度、控制器设计调优等方面得到广泛应用[5-6]。为提高高校实验课网络排课的效率，节约排课时间和工作量，提出一种基于GWO的高校实验课网络排课优化算法。

1 排课问题数学模型

1.1 排课问题数学描述

教师T={t1,t2,…,tn}，ti具有教师工号、姓名和职称等属性，其中教师号是唯一标志。课程C={c1,c2,…,cn}，ci具有课程号、总课时量、周课时量以及周数等属性，其中课程号是唯一标志。班级B={b1,b2,…,bn}，bi具有班级号和班级人数等属性，其中班级号是唯一标志。课堂CU={cu1,cu2,…,cun}，cui具有课堂号、班级号和人数等属性，其中课堂号是唯一标志。排课问题可以简化为作业调度问题[7]：若教室个数为m、上课周数为w、某天上课次数为j，那么有m×w×j个可以分配的教室时间段，如何分配n个教师号课堂号ticui使得所有排课时间最短。定义ti为安排第i个教师号课堂号ticui所耗费的最短时间；Ti为安排第i个教师号课堂号ticui所等待的时间，包括时间冲突检测、课堂冲突检测、班级冲突检测和教师冲突检测。

1.2 排课问题数学模型

排课目标函数为式(1)。

(1)

式中，kmαmtj+Tj>0。目标函数minT表示某一个教师号课堂号分配到第j个教室时间段内所耗费的时间最少或最短。

约束条件为式(2)、式(3)。

(2)

其中：

(3)

式(2)中，ti∩tj=∅，∀WiJi≠WjJj用来约束同一周、同一节次的教师不能是同一个教师；cui∩cuj=∅，∀WiJi≠WjJj用来约束在同一时间、不同课堂号不能包括同一个自然班。

2 GWO算法

GWO算法中，灰狼个体分为α、β、δ和ω。α负责狼群的决策与管理；β和δ为适应度次于α的灰狼个体；ω为其它灰狼个体。GWO算法主要包括包围、捕猎和攻击三种行为[8]：

2.1 包围行为

首先灰狼包围猎物，数学模型如式(4)和式(5)。

(4)

(5)

2.2 捕猎行为

包围猎物之后，狼群将捕猎猎物。假定α、β、δ分别为全局最优解、全局第二解以及全局第三解，对α、β、δ重新定位,如式(6)—式(8)。

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2.3 攻击行为

狼群捕食的最后阶段就是攻击捕获猎物，攻击过程主要通过调节参数a实现。当|A|≤1时，狼群将接近猎物(X*,Y*)集中攻击猎物；当|A|>1时，狼群将远离猎物。

3 基于GWO的高校实验课网络排课系统优化

基于GWO的高校实验课网络排课系统优化流程如图1所示。

图1 基于GWO的高校实验课网络排课系统优化流程图

基于GWO的高校实验课网络排课系统优化算法步骤可以详细描述为：

步骤1：读取课程信息、时间信息和教室信息以及相关约束信息；

步骤2：GWO算法初始化：设定灰狼种群数量N、最大迭代次数Maxgen和参数维度D、并初始化灰狼种群位置X=(X1,X2,…,XN)和灰狼个体的位置Xi=(xi1,xi2,…,xiD)，其中i∈{1,2,3,…,N}；

步骤3：计算不同灰狼个体的适应度值fi并排序，将适应度值前三位的灰狼个体的位置分别记作为Xα、Xβ和Xδ。

步骤4：按式(9)分别计算各ω狼与α、β、δ狼之间的近似距离，并按式(10)和式(11)更新α、β、δ狼的位置和猎物的位置；

步骤5：更新参数a、A和C；

步骤6：判断算法终止条件：若达到最大迭代次数Maxgen，则输出最优解，即最优排课信息；否则，返回步骤3。

4 仿真试验与结果分析

为验证GWO进行高校实验课网络排课系统优化的可靠性和有效性，选择Matlab2015(a)为仿真软件平台，PC机系统为Windows7、CPU主频2.2GHz、中央处理器为Intel core i5以及内存为4G。课程信息、时间信息和教室信息分别如表1—表3所示。

表1 课程信息

将GWO和PSO、GA进行对比[9-12]，不同算法参数设置如下：(1)GWO参数：种群规模N=50、最大迭代次数Maxgen=500。(2)粒子群算法(particle swarm optimization algorithm，PSO)：种群规模N=50、最大迭代次数Maxgen=500、学习因子c1=c2=2、惯性权重w=0.2。(3)遗传算法(genetic algorithm，GA)：种群大小N=50、最大迭代次数Maxgen=500交叉概率Pc=0.7和变异概率Pm=0.1，对比结果如图2—图4和表4所示。

表2 时间段信息

表3 教室信息

表4 GWO、PSO和GA对比结果

由表4和图2—图4可知，与PSO和GA相比，GWO算法进行课程排课优化的分配时间minT为337.675 5 s，优于PSO的565.800 1 s和GA的603.003 1 s，从而验证了GWO进行高校实验课网络排课的有效性和可靠性。

图2 GWO寻优收敛图

图3 PSO寻优收敛图

图4 GA寻优收敛图

5 总结

为解决高校实验课网络排课问题，将灰狼优化算法应用于网络排课问题优化求解，有效解决了网络排课问题，提高了网络排课的效率，降低了排课时间和减少了排课工作量。然而，本研究只研究了简单约束条件下的网络排课数学模型，未来将研究多冲突、多约束的网络排课问题，从而提高模型的适用性和应用性。