基于粒子群算法的机房排课问题研究

王文君

(闽江学院，福州 350108)

0 引言

机房排课问题被认为是典型的NP问题，涉及对多目标和多因素进行优化。传统的人工排课在少量班级和机房的情况下还可满足，但随着班级数量和课程对机房需求的增加，会出现越来越多的冲突，并且工作量也激增。由此，针对该问题，需要借助现代智能算法来解决该问题。目前，针对机房排课问题，从20世纪的50年代就开始进行，到目前为止，已提出包括图论、拉格朗日松弛法、二次分配法等在内的多种方法[1-5]。随着这些方法的应用，人们开始越来越关注多种约束条件下优化的精确度。而粒子群算法在约束优化、极大极小问题、多目标优化等方面具有良好的优势。因此，本文则将粒子群算法应用到机房排课中，从而对机房排课问题进行优化求解。

1 排课问题的数学建模

1.1 主要要素

在机房排课问题所相关的要素中，最核心的要素为机房、时间、课程、班级以及教师。对于机房排课的求解问题，可以看做上述各个主要要素间的笛卡尔集。在这5个主要要素中，通常在排课前已经能够确定课程、班级以及教师等3个要素间的关系。

1)机房要素。对于机房要素而言，主要考虑各机房的规模大小、计算机等相关核心设备的性能情况，以及在机房实际条件下所适合开展的课程类型。具体来说，根据机房的规模大小以及核心设备的性能情况对各机房进行分类，再根据机房的类别开展与之相适应的计算机应用基础、多媒体、设计类、网络等不同类型的基础与专业课程。

2)时间要素。时间要素方面主要包括每周的教学工作日、每天的教学时间以及前后课时的间隔。

3)课程要素。通常在排课前会预先确定班级和教师，再根据相应的算法来确定机房和时间。

4)班级要素。在同一时间内，一个机房只单独为某个班级开设一个类型的课程，并且学生为开课班级的固定人数。

5)教师要素。在同一时间内，一位教师只能单独进行某个班级一个类型的课程，并且教师同一天内的排课上限设为4节。

1.2 机房排课问题的数学描述

机房排课问题，其本质就是将任课的教师、机房、课程和不同的班级能够合理地安排在星期一到星期五，每个班级使用的机房不冲突，并且最大限度地利用学校的计算机机房资源。因此，结合上述的描述，分别构建5个不同因素集：

教师集合J={J1，J2，J3，...，Jj}，

班级集合B={B1，B2，B3，...，Bb}，

课程集合C={C1，C2，C3，...，Cc}，

时间集合T={T1，T2，T3，...，Tc}，

教师集合R={R1，R2，R3，...，Rr}。

设一个教室对应一个班级，一个教师教一个班级。以上5个集合的笛卡尔乘积J×B×C×T×R构成了机房排课问题的一个解空间。由此，排课表可以被看成是在这个解空间中满足各种约束条件的可行解。

2 机房排课问题的求解

2.1 粒子群算法基本原理

鸟群在飞行觅食时，整体上具有同步性。人们通过观察研究鸟群觅食行为的特点并进行建模仿真，由此提出了各种不同的鸟群模型。据Craig Reynols和Frank Heppner所提出的鸟群模型来看[6]，鸟群中每个个体间共享位置信息是实现整个群体同步性的基础。RussellEherhart等学者则在上述鸟群模型的基础上，进一步提出了粒子群算法。

在粒子群算法中，问题解空间的位置对应食物的位置，无质量无体积的粒子对应鸟群中的个体，粒子间的信息共享与相互协作则对应鸟群觅食时每个个体间的位置信息共享与彼此协作。在粒子间的信息共享与相互协作的基础上，通过各粒子改变运动方向与速度来实现求取最优解。粒子群算法的具体流程如图1所示。

图1 粒子群算法流程图

根据粒子群算法的原理可知，影响该算法的主要因素为粒子的位置、运动速度、自我学习以及社会学习等。

2.2 适应度函数构建

2.2.1 排课问题的约束条件

根据上述的分析看出，要得到排课表这个可行性解，即需要满足各种约束条件。对机房排课问题，可将约束条件分为硬约束和软约束。其中，硬约束是必须满足的条件，软约束是在满足硬约束的前提下进一步优化。在排课问题中，硬约束主要满足以下几个条件：

1)同一教师在同一时间只能上1门课，满足则有A1(i)=1，反之A1(i)=0；

2)同一班级在同一时间只能上1门课，满足则有A2(i)=1，反之A2(i)=0；

3)同一机房在同一时间只能上1门课，满足则有A3(i)=1，反之A3(i)=0；

4)机房座位数需大于学生人数，满足则有：A4(i)=1，反之A4(i)=0；

5)机房数量在同一时间要大于或等于上课班级数量，满足则有A5(i)=1，反之A5(i)=0；

软约束条件主要有：

1)上机课程尽可能安排在上午的3～4节，或者是下午；

2)上机课尽量安排在理论课程后；

3)同一班级的同一门上机课在一周内尽量间隔安排；

4)课程尽可能满足部分老师的特殊要求。

由此，满足上述硬约束和软约束条件的，就是机房排课问题的解。

2.2.2 机房排课问题适应度函数构建

本文在上述约束条件的基础上，选择时间优秀度f1、教师座位使用率f2、班级日课时均匀度f3、教师日课时均匀度f4作为适应度函数的因子，由此得到：

f=α1f1+α2f2+α3f3+α4f4。

(1)

各因子具体计算为：

(2)

式中：Wi为第i门课程的时间优秀度取值；φ表示课程数量。

f2=O/r，

(3)

式中：r为所有已安排课程所需教室数量；O为某教室座位的使用率。

f3=L/b，

(4)

式中：L为某班级日课时平均值；b为全校所有班级数。

f4=U/j，

(5)

式中：j为全校教师总数；U为该教师的日课时平均值。

3 适应度函数的求解

为求解上述的适应度函数，提出采用粒子群算法对式(1)进行求解。

3.1 编码设计

采用粒子群算法进行求解，首要的问题是进行编码。而根据排课问题特征，排课问题的调度编码方式主要包括三维编码、布尔矩阵编码和矩阵表示法3种[7-8]。结合本文的问题，选择矩阵表示法进行编码。将每周从周一到周五上课课时总计划分为20节，分别用T1～T20表示，R表示可用的实验教室数量。由此T～R之间构成了一个二维矩阵，见表1。

表1 时间—教室二维表

在表1中看到，格子中有课元的地方说明在第三间实验教室的周一下午的4节课有上机安排。如果没有，则说明没有任何的课程安排。由此，在进行编码时，每一个粒子对应数据库中的每一个以时间段为列、以教室为行的表。同时，在编排过程中存在很多约束条件，不是所有的粒子都为好的可行解，所以会针对目标函数，采用更新粒子位置的方式来不断调整粒子，进而找到一个最优解。

3.2 粒子群算法设计

根据上述的编码，采用以下的步骤进行求解：

1)设置初始种群大小N，最大迭代次数为M，惯性常数ω，rand1，rand2，加速系数c1，c2。

2)将种群平均分为∂个，在∂个中选择一个作为主种群，其余的作为子种群，计算初始粒子的适应度值，并得到每一离子的历史最佳值和全局最佳值。

3)判断适应度值是否满足结束条件，如满足则终止算法；如不满足，则转入4)。

4)更新粒子速度和位置

(6)

(7)

5)计算新生成粒子的适应度值，如满足结束条件，则返回3)；如不满足，则将新种群与∂-1种群组成新的种群，重新生成新的粒子，并继续计算适应度函数值。

4 实验验证

为验证粒子群算法在排课问题求解的可行性，以某院校为例，假设2018下—2019年上的教学任务见表2。

表2 某院校具体的教学任务

设定c1=c2=2，ω=0.5，种群个数分别为20、30、40、50进行实验，迭代次数为30。同时为比较该算法的可行性和优势，将PSO算法与多变异位自适应遗传算法(MMAGA)进行比较，仿真软件采用Matlab6.0。由此，得到表3的实验对比结果。

表3 PSO与MMAGA算法排课比较

通过表3结果显示，PSO算法进行排课得到的适应度值要明显大于MMAGA算法得到的适应度函数值。而适应度函数值是反应计算结果好坏的一个重要指标。由此说明，PSO算法在求解机房排课问题上，具有明显的优势，编排课表质量更好。

5 结语

针对机房排课难题，提出离散粒子群算法对机房排课数学模型进行求解，进而得到在相同约束条件下，PSO算法得到的适应度函数值要明显优于MMAGA算法，说明PSO算法具有良好的编排效果。而本文最大的特点在于对传统的PSO算法进行了适当的改进，即不是采用随机的方式寻找主种群，而是将其平均分为∂个种群再来寻优。