何小虎

（渭南师范学院 数学与信息科学学院，陕西 渭南 714000）

随着在校人数不断增多，合理利用教学资源，提高教学质量，是每个高校的首要任务。所以，有效组织各种软硬件资源，安排合理的课表显得尤为重要，因此，本文提出了利用改进蚁群算法来实现高校课程的排课问题，设计出符合教学规律和教学要求的课表。

1 排课问题概述

20世纪50年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出一个课表问题的数学模型[1]，1976年S．Even第一次证明了课表问题是NP完全问题，随后，许多学者开始研究TTP问题。

高校的排课是一项十分繁重而复杂的工作。我们学院的课表安排涉及到49个专业、几百名教师、16 000多名学生，同时要对几百门课程进行合理的组织安排，充分利用有限的教学资源，因此，合理安排一张高效的课表显得越发重要。高校课表要实现满意度高，冲突少，实现科学化，合理化，充分发挥空间、时间、人力的效益。就应遵循一定的规则，以满足各种约束条件，避免冲突的发生。

1）在同一时间，一个老师只能安排一门课。

2）在同一时间，一个班级只能安排一门课。

3）教师冲突问题，主要涉及到下面几个问题，

①在同时间里，教室总数要大于安排的总课程数。②教室的座位数必须满足上课学生人数。③相应的课程必修安排在所需要类型的教室中。

以上几点是最基本的硬性约束条件，但是还需要满足一些其他的软性要求：

①课程在一周有多次的，应有一定的时间间隔。②根据课程的需要，尽量安排在合理的时间内。③尽量满足特殊教师的需要。

2 改进蚁群算法解决排课问题

2.1 排课问题的数学模型

Carter和Laporte提出：高校排课问题是一个多元分配问题，它研究的就是如何把学生和老师分配给课程，课程单元或者班级，如何把事件（上课事件）分配给教室和时间[2]。解决排课问题可以转化为解决<课程、班级、教师>关系节点和<时间、教室>关系节点所构成的二分图的最大匹配问题[3]。

一般排课问题所涉及的元素主要有以下5种：班级集合：Class={C1，C2，…，Cn}；教师集合：Teacher={T1，T2，…，Tn}；教室集合：Classroom={CR1，CR2，…CRn）；课程集合：Lesson={L1，L2，…，Ln}；时间集合：Time={T1，T2，……，Tn}，

设一个三元组关系<教师，班级，课程>为R1和一个二元组关系为<教室，时间>为 R2。 其中 R1=Teacher×Class×Lesson，表示教师、班级和课程三者有关联的集合，R2=Classroom×Time。 则 R=R1×R2，这样就形成了一个新图 G（N，S），其中 N就 是 图 G 中 的 所 有 节 点 ，N=R1∪R2，S 表 示 边 ，S={（n1，n2）|n1∈R1，n2∈R2}，排课算法也就变成了二分图匹配的问题了。排课算法就是在属于R1中的节点中为属于R2的某一个节点寻找一个合适的节点进行匹配。

2.2 蚁群算法基本原理

蚁群算法是模拟真实蚁群觅食过程寻求最短路经的原理，由意大利学者M Dorigo等人首先提出的[4]。自然界中的蚂蚁是以外激素（pheromone）为媒进行信息传递的，从而蚂蚁个体能相互协作，完复杂的任务。蚁群的行为表现出一种信息正反馈现象：某一路径上经过的蚂蚁越多，则后到者选择该路径的概率就越大[5]。

蚁群算法可以表述如下：初始时刻，各条路径上的信息素量相等，设 τij（0）=C（C 为常数），蚂蚁 k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息量决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻t，蚂蚁k从城市i选择城市j的转移概率（t）为：

其中，Jk（i）={1，2，……，n}-tabuk表示蚂蚁 k 下一步允许选择的城市。列表tabuk记录了蚂蚁k在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次周游，此时蚂蚁 k所走过的路径便是 TSP问题的一个可行解。（1）式中的ηij是一个启发式因子，被称为能见度因子。在AS算法中，ηij通常取城市 i与城市 j之间距离的倒数。α和β分别反映了在蚂蚁的运动过程中已积累的信息和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（2）式更新。

其中ρ（0<ρ<1）表示路径上信息素的挥发系数，1-ρ表示信息素的持久系数；Δτij表示本次迭代边（ij）上信息素的增量。表示第 k只蚂蚁在本次迭代中留在边（ij）上的信息素量。如果蚂蚁 k 没有经过边（ij），则的值为 0。表示为：

其中，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度[6]。

2.3 运用蚁群算法的改进策略

针对蚁群算法容易出现停滞现象、陷入局部最优，搜索时间过长等缺陷，要使算法保持高效的搜索能力同时又能够避免停滞现象的关键是在“探索”和“利用”之间建立一个平衡点，也就是说既要使算法的搜索空间尽可能的大，以寻找那些可能存在最优解的解空间；同时又要充分利用群体内当前的有效信息，使算法搜索的侧重点放在那些具有较高适应值的个体所在的空间内，即缩小算法的探索空间，从而使算法在可以接受的时间内收敛到全局最优解[7]。

2.3.1 构造人工蚂蚁，使得蚂蚁具有一定的特殊能力

1）蚂蚁能够记住在周游过程所达到过的结点。2）蚂蚁具有路径识别能力。

2.3.2 信息素的更新策略

信息素的更新策略是对优质解进行更大限度的增强，而对劣质解进行削弱，使得属于优质路径的边与属于劣质路径的边之间的信息素量差异进一步增大，从而使蚂蚁的搜索行为更集中于最优解的附近。该改进算法主要修改了蚁群系统中的全局更新公式。当所有蚂蚁完成一次循环后，增加对最差蚂蚁所经过的路径信息素的更新，信息素量按下面公式进行调整[8]。

其中，K为该算法引入的一个参数，Lworst表示当前循环中最差蚂蚁的路径长度，Lbest表示当前循环中最优蚂蚁的路径长度，τij（r，s）表示两个目标之间的信息素轨迹量。

2.3.3 状态转移规则

状态转移规则[9]为更好更合理地探索新路径和利用先验知识提供了方法。在基本蚁群算法中，蚂蚁完全依赖概率进行路径选择，使用的是随机比例规则，蚁群系统使用了不同的决策规则，称之为伪随机比例规则。这个决策规则具有双重功率。决策规则既可以利用关于问题的先验知识，也可以有倾向性的搜索。

其中J是根据（1）式计算出来的。参数q0的大小决定了利用先验知识和探索新路径之间的相对重要性。每当蚂蚁要选择下一个城市时，它就选取一个随机数0≤q≤1，如果q≤q0，则根据先验知识公式来选择最好的边，否则就按照公式概率的选择一条边。

该优化的蚁群算法在我们学院课表编排中得到实际应用，通过在200个普通教室，105个多媒体教室，15个机房（15×50=750台），各类实验室若干。在校学生16 000多个，任课教师689人应用本算法编排结果来看，排课的效率和课表质量一定提高，冲突现象也明显减少。

3 结 论

状态转移和信息素在蚁群算法中起着关键性的作用，文中优化的蚁群算法结合了蚁群系统中的状态转移规则和最优最差蚂蚁系统中的信息素更新策略，从而有效地引导蚂蚁向更优的路径移动，有效地克服了基本蚁群算法存在的容易出现停滞现象、陷入局部最优，搜索时间过长的缺点。

[1]张林.基于蚁群算法的排课系统研究与设计[D].安徽：安徽大学，2005.

[2]李玉吉.蚁群遗传算法在高校智能排课系统中的应用[J].现代电子技术，2010（14）:121-123.LI Yu-ji.Application of ant-colony genetic algorithm in smart course schedule systems of colleges [J].Modern Electronics Technique，2010（14）:121-123.

[3]赵惠怡，刘道源，傅英亮.探讨如何利用蚁群算法解决排课问题[J].科技信息，2007（9）:26.ZHAO Hui-Yi，LI Dao-yuan，FU Ying-liang.Discusses how to use the ant colony algorithm class arrangement system[J].Science Information，2007（9）:26.

[4]王凌．智能优化算法及其应用[M]．北京：清华大学出版社，2001．

[5]徐宁，李春光，张健．几种现代优化算法的比较研究[J]．系统工程与电子技术，2002（12）：100-103．XU Ning，LI Chun-guang，ZHANG Jian.Several modern comparative study of optimization algorithm [J].Systems Engineering and Electronics，2002（12）：100-103．

[6]段海滨.蚁群算法原理及其应用[M].北京：科学技术出版社，2005.

[7]张忠.基于蚁群算法的时间表问题的研究与实现[D].苏州：苏州大学，2006.

[8]张献.蚁群算法在排课问题中的应用研究[J].长春大学学报，2007，17（10）:80-82.ZHANG Xian.Ant colony algorithm based on the research of theproblem and realize the schedule [J].Journalof Changchun University，2007，17（10）:80-82.

[9]Dorigo.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）:53-66.