基于改进GWO算法的高校教学管理系统排课算法研究

田方

摘要：高校办学规模的扩大使得高校排课面临巨大挑战，对此采用改进的GWO算法对高校教学管理系统排课算法进行了研究。分析了GWO算法的原理和流程，在此基础上运用混沌理论，采用Chebyshev混沌序列生成GWO算法的初始化灰狼种群，同时采用莱维飞行来改进灰狼位置的更新公式，得到了改进的GWO算法。通过对A大学排课的优化仿真试验，验证了改进的GWO算法避免了算法陷入局部最优，达到了良好的排课优化效果。该研究对排课系统的优化具有一定的参考价值。

关键词：排课问题;改进GWO算法;Chebyshev混沌序列

中图分类号：TP301.6

文献标志码：A

ResearchontheCourseArrangementAlgorithmofUniversityTeaching

ManagementSystemBasedonImprovedGWOAlgorithm

TIANFang

（SchoolofContinuingEducation，ShanxiUniversityofTraditionalChineseMedicine，Xianyang712000，China）

Abstract：Theexpansionofthescaleofauniversitymakesthecoursearrangementoftheuniversityfaceagreatchallenge.Inthispaper，theimprovedGWOalgorithmisusedtostudythecoursearrangementalgorithmofuniversityteachingmanagementsystem.TheprincipleandflowofGWOalgorithmareanalyzed.Basedonthechaostheory，ChebyshevchaoticsequenceisusedtogeneratetheinitialgraywolfpopulationofGWOalgorithm.Atthesametime，Levyflightisusedtoimprovetheupdateformulaofgraywolfposition，andtheimprovedGWOalgorithmisobtained.Throughthesimulationexperimentofauniversitycoursearrangement，itisverifiedthattheimprovedGWOalgorithmcanavoidthealgorithmfallingintothelocaloptimumandachieveagoodeffectofcoursearrangementoptimization.Theresearchofthispaperhascertainreferencevaluetotheoptimizationofthecoursearrangementsystem.

Keywords：classschedulingproblem;improvedGWOalgorithm;Chebyshevchaoticsequence

0引言

國民经济的快速发展促进了我国高等教育的快速发展，各个高等院校纷纷扩招，在校大学生的数量快速增加，同时高校办学规模的不断扩大，其所开设的专业课程数目也在不断地增多。高校学生人数和开设专业课程数目的增加使得高校教务管理面临一个巨大的难题，即排课。采用手工排课的方式去排课要耗费大量的人力资源，且容易出现错误，特别是在当前高校学生人数和课程持续增多的环境下，这种排课的方式变得不现实。为了解决教学资源冲突，提高排课的效率，目前各大高校都采用了排课软件。高校教务部门采用排课软件可以解决一般的排课问题，但是依旧无法避免师生冲突、资源与课程冲突，因此在排课之后还需要手工调整，浪费了大量人力资源[1]。采用遗传算法、灰狼优化算法（GWO）能够解决高校教学管理系统排课问题，但是也存在一些缺陷。基于此，本文对GWO算法进行改进，同时将改进的GWO算法应用于高校教学管理系统排课中去，期待对解决比较复杂的排课问题提供参考。

1GWO算法

1.1GWO算法原理

2014年，Mirjalili等人受到受到大自然灰狼捕食猎物活动启发提出了灰狼优化算法，即GWO算法。相对于其它的智能优化算法，GWO算法具有结构简单、参数设置少等优点，被广泛应用于参数优化、车间调度、系统排课等问题中。灰狼是典型的肉食动物，主要是群居生活。在一个狼群中包含有10只左右的灰狼，而最厉害的狼仅有一只。在一个小型的狼群中，最厉害的那只大灰狼负责整个狼群中的各项事务，处于核心地位。对于灰狼群[2]而言，其遵循社会支配等级关系，可以分为四层，如图1所示。

α处于社会等级的第一层，为头狼，在整个灰狼群中处于领袖地位，其对整个灰狼群的捕食、栖息等活动做出决策，是管理层。也许在整个灰狼群中头狼捕食最厉害的，但是头狼的管理能力一定是最厉害的，其它的狼都必须服从头狼的管理，按照头狼的命令开展各种活动。

β处于社会等级的第二层，其协助头狼α做决策和处理灰狼群中的各种活动。在灰狼群中，如果头狼不在、生病、死亡，那么β就转变为头狼，承担头狼的各种任务。对于β灰狼而言，其一方面要向灰狼群中的其它狼下达头狼的命令，同时还要将其它狼执行头狼α的命令情况反馈给头狼。

δ处于社会等级的第三层，其开展各种活动必须听从于α狼和β狼，同时指挥底层的狼。对于δ狼而言，其往往是从事放哨、侦查、狩猎、护理等工作。对于α狼和β狼而言，当其年纪比较大时，也会转变为δ狼。

ω处于社会等级的第四层，其各项工作的开展必须服从于α狼、β狼和δ狼。从表面上来看，ω狼在整个狼群中处于可有可无的地位。实际上，ω狼在整个狼群中的地位至关重要，由ω狼来负者整个狼群各个阶层之间的平衡。如果在整个狼群中没有ω狼的存在，那么就会出现自相残杀的情况。

1.2GWO算法流程

采用GWO算法必须构建灰狼群的社会等级层次模型。对灰狼群中的灰狼个体计算适应度，依据适应度的大小来选择适应度比较大的三只灰狼，

记为α狼、β狼和δ狼，其余的灰狼记为ω狼。大灰狼在大自然中搜索猎物时会采取逐步靠近再包围猎物的方式，其数学模型如式（1）—式（4）。

D=C·xp（t）-x（t）（1）

x（t+1）=xp（t）-A·D（2）

A=2ar1-a（3）

C=2r2（4）

式中，D为最优灰狼和候选灰狼之间的距离，A、C为协同系数向量，t为迭代次数，x为灰狼的位置向量，xp为猎物的位置向量，a在整个迭代过程中从2线性递减到0，r1、r2为闭区间[0，1]上的随机向量。

在自然界中，灰狼只有具有识别潜在猎物位置的能力，才能确保狼群的生存，整个灰狼群搜索猎物完全是在α狼、β狼和δ狼的命令下完成的。为了更好地对灰狼搜索猎物行为进行模拟，在GWO算法的每次迭代中均保留当前适应度值最好的三只灰狼，结合α狼、β狼和δ狼的位置信息来更新ω狼的位置信息。灰狼群的狩猎行为数学模型如式（5）—式（7）

Dα=C1·xα-x

Dβ=C2·xβ-x

Dδ=C3·xδ-x（5）

x1=xα-A1Dα

x2=xβ-A2Dβ

x3=xδ-A3Dδ（6）

x（t+1）=x1+x2+x33（7）

式中，Dα、Dβ、Dδ分別为候选灰狼和最优灰狼α、β、δ之间的距离，A1、A2、A3、C1、C2、C3为协同系数向量，xα、xβ、xδ分别为最优灰狼α、β、δ的位置向量，x为灰狼的位置向量。

对于GWO优化算法而言，其首先是设置最大迭代次数tmax，灰狼种群的规模N，结合随机参数生成初始化灰狼种群的位置，并计算灰狼个体的适应度，按照适应度值的大小来找出在灰狼种群中最优的三种灰狼，分别记为α狼、β狼和δ狼，保存α狼、β狼和δ狼的位置xα、xβ、xδ。其次是采用公式（5）～（7）对ω狼的位置进行更新，对更新后的位置采用公式（3）、（4）更新参数，并计算所有个体的适应度值，将其和上一次迭代的适应度值进行比较，选择适应度值最大的三只灰狼，继续寻找猎物。最后是判断迭代是否达到了最大值，如果达到了最大值，那么停止迭代，输出头狼xα的位置作为最优值。GWO算法流程[3]，如图2所示。

2改进的GWO算法

2.1混沌初始化种群

传统的GWO算法产生初始的灰狼种群是随机的，这使得灰狼种群的多样性受到影响，进而影响到GWO算法的迭代效率。混沌是自然科学中行为不可预测的确定性系统，可以借助混沌来对GWO算法的灰狼种群进行初始化，这样就可以在很大程度上提高初始灰狼种群个体的多样性，使得GWO算法的计算效率得到大大提升。在数学中，各种混沌行为往往借助于迭代函数来检测。对于不同的初始值，混沌函数所产生的序列不同，但是比较有趣的事情是伴随着迭代次数的不断增大，混沌函数所产生的序列极限值是一样的。在GWO群智能算法中，各种随机性对搜索产生巨大的影响。混沌序列目前被广泛应用于各种群智能算法中，同时取得了良好的效果。针对GWO算法的改进，采用Chebyshev混沌序列来生成GWO算法的初始化灰狼种群，使得种群个体多样性增加，改进算法的计算效率大大提升。Chebyshev的映射方程如

式（8）。

xk+1=cos（kcos-1（xk））（8）

2.2莱维飞行改进位置更新

采用传统的GWO算法可能存在优化陷入局部最优的情况，在对GWO算法进行改进时采用莱维飞行对GWO算法种群位置更新的公式进行改进，从而在一定程度上扩大GWO算法的搜索范围[4]。采用莱维飞行改进GWO算法位置更新公式如式（9）

xα（t+1）=xα（t）+alpha⊕Levy（β）

xβ（t+1）=xβ（t）+alpha⊕Levy（β）

xδ（t+1）=xδ（t）+alpha⊕Levy（β）（9）

式中，alpha为步长控制量，一般取值为0.01;⊕为点对点乘法运算规则;Levy（β）为GWO算法的随机搜索路径

如式（10）。

Levy（β）=uv1/β·（x（t）-xm（t））·randn（10）

式中，β的取值范围为[1，3]，v服从正态分布u∶N（0，1），x（t）为灰狼群t次迭代更新以后的位置，

xm（t）为灰狼群t次迭代时α狼、β狼和δ狼的位置，randn为服从正态分布的随机数，u服从正态分布

N（0，δ2），其中δ如式（11）。

δ=Γ（1+β）·sinπ·β2

Γ1+β2·β·2（β-1）/2

1/β（11）

通过对GWO算法位置更新的公式进行改进使得搜索的范围扩大，避免在迭代的过程中陷入局部最优。采用改进的GWO算法可以在很大程度上使得整个算法搜索的灵活性增强，提升了算法的鲁棒性。

3改进GWO算法在高校排课中的应用

3.1排课问题概述

高校的快速扩招使得高校的办学规模快速扩大，保证高校教学质量必须确保各种软硬件设施的同步发展。高校学生和高校开设专业的增多使得排课问题变得十分复杂，高校排课必须确保班级、教师、课程、教师安排等不发生冲突。排课问题必须满足以下五个硬约束[5]：

（1）在同一个时间段内不能为同一个教师安排两门课程的教学任务，否则就会出现教师上课时间的冲突，出现教学事故;

（2）在同一个时间段内不能为同一个学生安排两门课程的学习任务，否则就会出现学生上课时间的冲突，学生不知道应该去上什么课程，出现严重教学事故;

（3）在同一个时间内的同一个教室不能安排两门课程，否则就会在该教室出现多个班级和多个教室来同一个教室上课，出现教学混乱，影响正常教学工作的开展;

（4）安排课程的上课时间不能夠少于课程规定的时间，如果安排课程的上课时间少于规定课程规定的时间，那么就有可能出现这门课程还没有下课，而下一门课程已经上课，造成教学冲突，影响正常教学;

（5）教室的座位数不能够少于上课的学生数，如果教室的座位数不足，那么学生就无法正常上课。

采用GWO算法对高校教学管理系统进行排课，构造编码是算法设计的关键所在。对于高校排课问题而言，其涉及五个方面的因素，分别为教师、教室、班级、课程和时间。高校教学管理系统排课的基因构造，如图3所示。

排课基因构造完成之后，可以采用改进的GWO算法将适应度高的保留下来，反复循环，直到算法终止，找到问题的最优解。

3.2GWO算法适应度函数

高校的教学管理部门在排课的时候必须注意以上五个硬性的约束，但是在满足影响约束的情况下还有一些软约束。例如尽量提高教室的利用率，避免部分教室在一个学期没有安排一门课程。采用加权的方式来设计GWO算法的适应度函数，使得其排课达到最优化。本文主要考虑两个方面的软约束[6]：

（1）教室的利用率

高校具有许多的教室，在每一个教室都安装有教学所需的各种设备。高校的教务系统在排课时必须考虑教室的利用率，避免有的教室每节课都在使用，而有的教室经常不使用。采用如下公式来评价教室的利用率，如式（12）。

s1=∑ni=1sn（i）·ch（i）cr（i）

∑ni=1ch（i）（12）

式中，n为课元个数，sn（i）为第i个课元所包含的学生个数，ch（i）为第i个课元所包含的学时数，cr（i）为第i个课元所用教室的教室容量大小，s1为教室的利用率。

（2）上课时间均匀安排

考虑到学生学习的实际情况，为了提高学生的学习效率和学习质量，高校教务系统在排课时必须考虑学生上课时间的均匀安排，使得学生在上完一门课程之后可以得到休息和完成相应的作业，然后再去上第二门课程。对一个课元而言，其时间分布均匀度T（i），如式（13）。

T（i）=

0ch（i）=1或者ch（i）>3

∑chj=1（Day（i，j+1）-Day（i，j））其它（13）

式中，Day（i，j）为第i个课元的第j个上课时间输入第几个上课日。

对排课方案进行上课时间均匀安排评价的计算公式，如式（14）。

s2=∑ni=1T（i）（14）

对GWO算法所采取的个体适应度计算公式是对教室利用率s1和上课时间均匀安排评价s2进行加权得到，

如式（15）。

fitness（s）=a·s1+b·s2（15）

式中，fitness（s）为个体适应度，a、b为待定系数。

3.3试验结果对比

为了验证改进GWO算法的有效性，以A大学为例，采用传统的GWO算法和改进的GWO算法进行仿真试验，仿真试验测试的相关数据，如表1所示。

分别采用GWO算法和改进的GWO算法对其进行排课优化，不同迭代次数下适应度的比较，如图4所示。其中待定系数

a、b均为0.5。

由图4可见，改进后的GWO算法最优适应度增长速度明显大于传统的GWO算法，在迭代120次左右，传统的GWO算法陷入局部最优状态，而改进的GWO算法并没有陷入局部最优的状态，而是伴随着迭代次数的增加呈现出良好的增加趋势。由此可见，采用改进的GWO算法可以更好地对高校进行排课，使得排课达到良好的效果，为提升高校的教学质量提供参考。

4总结

排课问题关系到高校的教学质量，在当前高校办学规律不断扩大的大环境下，对排课的优化至关重要。本文对GWO优化算法进行了改进，采用Chebyshev混沌序列来生成GWO算法的初始化灰狼种群，同时采用莱维飞行来改进灰狼位置的更新。通过将GWO算法和改进的GWO算法应用于排课系统中验证了改进的GWO算法避免了陷入局部最优，使得排课达到了良好的效果。本论文的研究对于高校排课管理系统的优化具有一定的参考价值。

参考文献

[1]范明杰，怀丽波.基于改进遗传算法的排课问题研究[J].计算技术与自动化，2018，37（1）：8994.

[2]韩麟，陈宏伟.基于Spark的灰狼优化算法研究[J].湖北工业大学学报，2019，34（5）：6063.

[3]王梦娜.灰狼优化算法的改进及其在参数估计中的应用[D].西安：西安理工大学，2019.

[4]方晓玉，李晓斌，郭震.一种改进的混合灰狼优化SVM预测算法及应用[J].激光与光电子学进展，2012，12（6）：341347.

[5]王璐，杨亚伟.一种改进的遗传算法在年度排课问题中的应用[J].计算机与数字工程，2016，44（8）：16191624.

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

（收稿日期：2020.03.11）