方锦烽

[摘 要] 以高校課程排课问题为研究对象，分析了常见的几类排课问题求解算法以及算法应用情况，并对课程排课算法的未来发展提出展望。

[关 键 词] 课程排课；局部搜索算法；人工智能方法

[中图分类号] G712 [文献标志码] A [文章编号] 2096-0603（2018）23-0068-01

一、引言

课程排课问题就是在各种资源约束条件下能够满足一系列给定目标的分配问题，该问题主要有硬性和软性两大约束，硬性约束主要包括一个班级或教师不能在同一时刻有多门课程、教室的座位数不能少于学生人数等，软性约束主要包括班级或教师前后课程的教室间距离、教师利用率等，该约束主要用于问题求解算法评价。

二、课程排课算法研究综述

课程排课算法主要有构造性方法和近似方法，由于课程的排课问题属于NP-hard问题，因而在求解时，大部分文献采用近似方法进行求解，因为近似方法可以在合理的时间内产生比较满意的次优解，该类方法广泛应用于较大规模的排课问题，近似方法又具体分为局部搜索算法和人工智能方法。

（一）构造性方法

在排课问题中，有优先分配规则等构造性方法，如陈谊等基于划分等价类设计基于优先级的自动排课算法，孙建平等使用关联规则进行排课的处理。

（二）局部搜索算法

局部搜索算法是使用人工智能技术，对基本局部搜索算法进行推广扩展发展而来的，目的是克服基本算法容易陷入局部最优的缺点，目前形成了以模拟退火算法、禁忌搜索算法等为代表的算法。模拟退火算法由Kirkpatrick等在1983年提出，它对物理中固体物质退火的过程进行模拟，使用Metropolis接收准则以一定概率接受新的较差解或继续在当前的领域内进行搜索；禁忌搜索算法由Glover和Hansen在1986年提出，该算法使用一个禁忌表保持以前达到过的局部最优点，在接下来的搜索中利用禁忌表中的信息不再搜索这些点，从而避免陷入局部最优。如Bellio以及Song使用了模拟退火算法，在算例分析中，大部分算例都能在合理的时间内找出可行解；Burke等使用禁忌搜索算法求解排课问题，Lu等使用了自适应禁忌搜索算法，初始解通过快速贪婪启发式生成，并和另外五种参考算法进行了比较。

（三）人工智能方法

用于课程排课的人工智能方法主要有遗传、粒子群、多智能体等几种算法，遗传算法由Holland在1975年提出，它通过模拟生物遗传和自然选择的机理，用人工的方式构造的一种优化搜索算法，该算法包括初始种群、选择/交叉/变异、适应度函数等关键要素。粒子群优化算法由Kennedy和Eberhart在1995年提出，它对鸟群的捕食行为进行模拟，通过粒子在解空间内追随最优的粒子进行搜索。蚁群优化算法是上个世纪90年代由Dorigo、Maniezzo和Colorni在研究蚂蚁寻找路径的自然行为的基础上提出的，该算法最初用于求解旅行商问题，后来在组合优化方面得到了广泛应用。多智能体是分布式人工智能的研究热点技术，该技术能够充分体现人类的社会智能，对动态和开发的现实环境具有良好的灵活性和适应性。

唐勇等设计了基于遗传算法的排课系统，并使用Matlab进行编程，Alsmadi等提出了机器学习系统模型，并用遗传算法进行求解，该方法具有尽可能少地破坏软性约束以及消除使用外部教室的优点，Akkan等提出了双目标优化模型，并使用混合多目标遗传算法求解，王念桥和姚四改提出了离散粒子群的排课算法，解决了粒子群算法后期收敛速度慢、易早熟的缺点。谭保华和彭伟将蚁群算法和遗传算法相结合，结果发现该算法可以有效地减少搜索空间，使种群在遗传过程中按规则分区。Babaei等使用了多智能体、元启发式方法求解排课问题。

三、发展与展望

以上回顾了近来学术界对课程排课问题求解算法的研究情况，其中的绝大部分算法都是使用单一算法进行问题的求解，而且一般只考虑到单个目标的情况，在接下来的课程排课问题研究中，重点将是混合算法以及多目标优化的应用。

参考文献：

[1]陈谊，杨怡，张国龙，等.基于优先级自动排课算法PCSA的设计与实现方案[J].北京工商大学学报（自然科学版），2002，20（2）：32-5.

[2]孙建平，梅晓勇，肖政宏，等.关联规则在高校智能排课系统中的应用[J].计算机应用，2002，22（5）：37-8.

[3]唐勇，唐雪飞，王玲.基于遗传算法的排课系统[J].计算机应用，2002，22（10）：93-4.

[4]Akkan C，Gülcü A.A bi-criteria hybrid Genetic Algorithm

with robustness objective for the course timetabling problem[J].Comput Oper Res，2018（90）：22-32.

[5]王念桥，姚四改.基于改进粒子群优化算法的排课问题[J].计算机应用，2013，33（1）：207-210.

[6]谭保华，彭伟.基于蚁群遗传算法的高校排课系统[J].计算机仿真，2008，25（12）：294-297.

[7]Babaei H，Karimpour J，Hadidi A.A survey of approaches for university course timetabling problem[J].Computers & Industrial Engineering，2015（86）：43-59.