一种智能化排课算法的设计

张宗飞

（1.台州职业技术学院信息技术工程学院，浙江台州 318000；2.台州中小企业信息化应用技术协同创新中心，浙江 台州 318000）

排课是一个教学资源分配问题，由于各种教学资源在分配过程中的制约与冲突，使排课成为了多约束组合的优化问题[1-2]。

自从Gotlieb C C 在1962 年提出了排课问题的数学模型、Even S 等人在1976 年证明了排课问题属于NP 完全问题之后[3-4]，对该问题的求解都集中在启发式算法上，目标是在可接受的时间内搜索获得最优的课表[5-8]。其中比较有代表性的是采用遗传算法的解决方案，如文献[5]从教室调度、冲突检测和时间规划3 个方面着手，使用遗传算法设计了排课系统，实现了自动化排课；文献[6]按照遗传算法对排课问题编码，并进行选择、交叉操作，采用禁忌搜索算法进行变异操作，实现了比单纯遗传算法更优化的高校排课方案。对于排课问题，虽然采用遗传算法已取得了一些比较好的成果，但是由于排课问题的复杂性和遗传算法本身的缺陷，致使基于遗传算法的求解始终无法达到解的下界，对最优课表的探索仍在进行。

量子进化算法(Quantum Evolutionary Algorithm，QEA)是一种新型的智能化启发式算法[9-10]，自从提出之后就得到广泛关注和不断改进，在早熟收敛和全局寻优的平衡上优于其他启发式算法，成为求解组合优化问题的一种通用计算框架[11-15]。

为此，该文使用QEA 来求解排课问题，通过设计一种基于QEA 的排课算法，实现自动排课功能。

1 排课问题模型构建

1.1 排课的冲突要素

该文将制约排课的5 种教学资源：班级、课程、教师、上课时间、教学场所称之为排课的5 个冲突要素。为了合理解决排课过程中这5 个要素之间的冲突，将5个冲突要素进行分解，用相应的属性来描述。

1）班级：班级编号、班级名称、学生人数、所属学院、所属专业。

2）课程：课程编号、课程名称、开课班级、任课教师、场所要求、周课时、起止周、课程性质、课程类型。

3）教师：教师编号、教师姓名、所属学院、所属专业、职称。

4）教学场所：场所编号、场所类型、场所容量。

5）上课时间：用时间元来表示上课时间，每个时间元为2 课时。

1.2 排课的约束条件

排课过程中的约束条件可以分为硬约束和软约束。

硬约束是指排课时不能违反的原则，用来约束排课方案的可行解。该文定义了如下4个硬约束条件：

1）一位教师在一个时间元最多只能安排一门课程，即：

2）一个班级在一个时间元最多只能安排一门课程，即：

3）一个教学场所在一个时间元最多只能安排一门课程，即：

4）为课程cuk分配的教学场所crm可容纳人数ym要大于等于上课班级cli的学生人数xi，即：

软约束是指排课时人为的主观要求，用来逼近排课方案的最优解，软约束会因不同的要求而产生不同的约束条件。该文从时间元、班级课程分布、教师课程分布3 个指标要求来定义软约束条件。

1）时间元指标要求：一个班级的课程要尽量安排在较好的时间元上。

2）班级课程分布指标要求：一个班级的同一课程如果在一周中有多个时间元则要尽量均匀安排。

3）教师课程分布指标要求：一个教师的任教课程如果在一周中有多个时间元则要尽量均匀安排。

针对上述3 个约束条件，对学生和教师展开调查，根据调查结果定义了对应的罚值表，如表1、表2、表3 所示。

表1 时间元评价罚值表

表2 班级课程分布评价罚值表

表3 教师课程分布评价罚值表

1.3 排课的数学模型

如果高校的班级数为i，一周的时间元数目为j，课程门数为k，教学场所数目为m，任课教师人数为n，则可以定义如下集合。

1）班级集合：CL={cl1,cl2,…,cli}，各班级的学生人数为{x1,x2,…,xi}

2）时间元集合：TU={tu1,tu2,…,tuj}

3）课程集合：CU={cu1,cu2,…,cuk}

4）教学场所集合：CR={cr1,cr2,…,crm}，各教学场所可容纳的人数为{y1,y2,…,yd}

5）教师集合：TE={te1,te2,…,ten}

此时，排课问题的求解就是在满足相应的约束条件下，寻找课程的如下映射关系：

2 基于QEA的排课算法设计

按照QEA 求解组合优化问题的步骤，设计基于QEA 的排课算法，记为TA-QEA。

2.1 量子染色体构造

根据课表的结构，以[班级*时间元]的向量矩阵形式来构造染色体，一个染色体表示一种排课方案。根据1.3 节对班级和时间元集合的定义可得到一个如式（5）结构的a行b列矩阵，每一行代表一个班级的课表。矩阵元素作为染色体的基因，由1.1 节所描述的班级、课程、教学场所、教师4 个排课要素构成，提取这4 个要素的编号属性组成的向量按照式（6）结构进行编码，一个属性编号称之为基因段，每个基因段与对应的排课要素关联。

根据上述编码，结合QEA 中量子染色体的结构，构造TA-QEA 的量子染色体结构如下：

2.2 种群初始化

首先，随机生成一组如式（7）结构的量子染色体构成初始种群（n为种群的大小），然后，将染色体的各量子比特概率幅(αi,βi)初始化为。

2.3 种群观测

对染色体的每一个量子比特进行测量，随机产生[0,1]之间的一个常数r，若(αi为染色体第i个量子比特的概率幅)，则该量子比特(xi) 取1，否则取0。对量子态种群Q(t) 观测后，就得到了观测态种群其中，观测态个体是长度为m的二进制串(x1x2…xm),xi∈{0,1}。

2.4 冲突检测

观测态种群中的个体就是TA-QEA 解空间中解的集合，一个个体代表一种排课方案，由1.2 节中的约束条件可知，这些个体都必须满足硬约束条件，因此需要对观测态种群中的各个体按照式（1）、（2）、（3）、（4）进行检测，将不满足这4 个约束条件的个体删除。

2.5 适应度函数设计

分析1.2 节中的约束条件可知，硬约束是排课原则，算法中的每一个随机解都要求必须满足，而软约束是排课方案的优化目标，最接近软约束条件的解可视为最优解，因此排课问题的目标函数只需考虑软约束。根据1.2 节中定义的软约束条件设计TAQEA 适应度函数的步骤如下。

Step1 为软约束指标分配权重得到排课的目标函数：

式中，δtu、δcl、δte分别为时间元评价罚值、班级课程分布评价罚值、教师课程分布评价罚值，ωtu、ωcl、ωte分别为对应评价罚值的权重。

Step2 采用比例放大方法将目标函数转换成适应度函数：

式中，ρ为放大系数。

2.6 种群进化

种群进化包含染色体的更新和交叉过程[16]。染色体更新使用式（10）所示的量子旋转门作为更新算子，按照式（11）所示将量子旋转门作用于染色体的量子比特，使量子比特朝着目标方向偏转，从而实现染色体的更新。

式中，θ为旋转角度。

式中，θi=s(αi βi)·Δθi,Δθi、s(αi βi) 分别表示旋转角的大小和方向，可以通过查表获得。

为了维持种群的多样性，避免算法陷入早熟收敛，需要对更新后的染色体进行交叉操作。为了减少冲突检测的计算量，以矩阵的行为断点进行全干扰交叉方式实现染色体的交叉操作。

2.7 循环停止设定

算法通过循环，使个体的适应度不断增大，达到进化的目的。为了使算法能够在可接受的时间内获得满意解，设置一个最大进化代数T作为TA-QEA的循环停止条件。

3 实验验证

3.1 实验方案设计

实验数据：实验所用数据来源于某职业技术学院2019-2020 学年第一学期的开课任务表，共有学生9 871 人、开课教师521 人、班级249 个、开课课程984 门（同一门课程不同教师上课编号不同）、教学场所237 个，可安排的上课时间为星期一到星期五，每天8 课时（上午4 课时、下午4 课时），时间元为20 个。

实验环境：为了验证该文排课算法的性能，选取文献[6]算法（记为TA-GA）作比较，两者使用相同的染色体编码方案和适应度评价函数。实验在一台Intel(R)Pentium(R)4 CPU 2.60 GHz、1.00 GB Memory、Microsoft Windows XP Professional SP2 OS 的单机上进行，在Eclipse 集成开发工具中使用Java 语言完成算法代码。

实验中各参数设置：种群大小n为200，最大进化代数T为1 000，排课软约束指标的权重ωtu、ωcl、ωte分别为0.5、0.3、0.2，适应度函数的比例放大系数ρ为100。

3.2 实验结果与分析

分别运行TA-QEA 和TA-GA 进行排课测试，以算法的优化能力和优化效率为评价指标，每进化100代记录一次，实验进行了10 次排课测试，TA-QEA 和TA-GA 均成功了8 次，分别取这8 次测试的平均值进行统计。算法优化能力的统计结果如图1 所示，算法优化效率的统计结果如图2 所示。

从图1 数据可以看出，从第400 代开始，TA-QEA获得的最优个体适应度值就超过了TA-GA，而且TAQEA 从第800 代开始最优个体适应度值就趋于稳定，先于TA-GA 100代左右。从图2数据可以看出，在10次记录点上，TA-QEA 的运行时间均要少于TA-GA，而且在进化后期，这种优势更加明显。分析图1、图2 的数据，可以得出结论：对于文中的排课问题，TA-QEA的寻优能力和寻优速度均优于TA-GA，表明TA-QEA在完成排课的质量和效率上都优于TA-GA。

图1 算法优化能力的统计结果比较

图2 算法优化效率的统计结果比较

4 结束语

针对高校排课工作的重要性与复杂性，将量子进化算法应用到排课问题中，使用优化的方法进行求解，在获得可行课表后进一步优化逼近最优排课方案。实验结果表明，该文算法能够自动完成排课过程，排课的质量和效率都比较好。但是，算法生成的课表是在设置3 个软约束条件下得到的满意解，如果排课的人为要求更加复杂时，就可能需要对算法生成的课表进行人工修正。