基于遗传算法和禁忌搜索算法的排课系统研究
基于遗传算法和禁忌搜索算法的排课系统研
引言
排课是高校教学管理中十分重要而又复杂的管理工作之一，由于排课问题涉及的因素
有时间、教师、教室、课程、班级等，因此排课问题是一个有约束条件、多目标、模糊性
极强的组合优化问题[1]。由于各学校资源差异较大，约束条件复杂，排课系统难以具有普
遍适用性。一般教务排课仍以手工为主，计算机为辅，效率低下。研究灵活、高效、自动
化程度高的排课系统需求迫切，具有现实意义。
国外很早就有人本文由论文联盟 收集整理研究课表的编排问
题，一般利用启发式函数，并且大多数启发式方法都是模拟手工排课的过程实现的。国内
对排课问题的研究较晚，并且大部分学者研究的排课系统都依赖于各个学校的教学体制，
不具有普遍适用性[2]。从实际使用情况看，国内研究的排课系统软件在性能上也达不到使
用要求。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、自适应的随机
搜索算法；而禁忌搜索算法是对局部领域的一种扩展，是一种全局逐步寻优的搜索算法。
通过对比分析，遗传算法和禁忌搜索算法在解决复杂优化问题中有明显的优势，因而本文
采用遗传算法和禁忌搜索算法来实现排课系统。
1 排课系统分析
排课问题的主要任务是将班级、教师、课程安排在一周内某一不发生冲突的时间和教
室中，保证课表在时间分配上符合一切共性和个性要求，使安排在各个目标上尽量达到最
优。
根据是否必须满足，可以将约束条件分为硬约束和软约束。硬约束是指教师、
班级、教室在时空概念上发生了冲突，它是在排课过程中必须满足的约束条件，否则
将会使排课结果毫无意义。软约束是指排课过程中需尽量满足的约束条件，它能够使课表
更加合理。排课的目标是要满足所有的硬约束条件，同时尽可能多地满足软约束条件，实
现一个使用方便、效率高的排课系统。
2 基于遗传算法与禁忌搜索算法的排课系统
在整个排课过程中，首先需要确定教学计划，然后根据教学计划生成教学任务，教学
任务确定了课程、教师、班级 3 者之间的关系。在排课问题中，由于涉及到教师、教室、
课程、班级、时间这 5 个因素，可以将课程、教师、班级这 3 个因素绑定为一个整体，作
为一个元组，并对这个元组随机分配时间与教室，生成一个可行的课表。
本文应用遗传算法对排课问题进行编码，然后再进行选择、交叉、变异等操作，计算
适应度函数。在遗传算法的运算过程中使用禁忌搜索算法来代替变异算子，从而得到更优
的个体解，最终生成有效的课表。
遗传算法编码
遗传算法的编码方法有很多种，针对排课系统，本文采用混合式编码方式，将混合式
编码作为排课系统遗传算法的基因。该基因由教师编号、课程编号、班级编号组成，每个
教师都有一个唯一的教师编号，用八位数字表示。课程编号用一位数字表示，表示该教师
教的第几门课程。班级编号也用一位数字表示，表示该教师教的第几个班级。这种编码方
式解决了特定时段教师课程的安排问题和普通时段课程的分配问题。系统只要按照算法流
程对编码进行处理，对结果进行不断的筛选，就可以得到完善的课程表，通过混合式编码
将教师、课程、班级这 3 个因素的关系表示出来。
混合式编码在时间上主要采用时间片划分，上课时间分为周一到周五，一天有 10 节
课（上午 4 节，下午 4 节，晚上 2 节），上课方式为一个课次两个相邻小节。所以以一
个课次为一个时间片，一天可划分为 5 个时间片。这样一周就可划分为 25 个时间片。可
以构造一个三维矩阵来表示排课系统，其中 X 坐标表示时间片，Y 坐标表示教师、班级和
课程，Z 坐标表示教室，通过三维矩阵将影响排课系统的 5 个因素联系起来。
遗传算法适应度函数
适应度函数用于评价某个染色体的适应度，随着排课的进行，课表空间在不断变化，
个体的适应度也随着课表空间的改变而改变，本文采用的方法是调整随机生成的初始群体
，但是在遗传算法运行过程中，交叉和变异都可能产生冲突，为了减少冲突，可以引入负
适应度值来降低冲突个体被选入的概率，同时记录冲突未消除的个体，并在下次迭代中继
续消除。对有时间段冲突的两个个体，可以用个体的冲突时间段与该个体的空闲时间段互
换来消除冲突，这样就消除了遗传算法运行过程中存在的冲突，增加了个体的适应度。
遗传算法运行
选择操作
首先采用计算机模拟方法计算个体的选择概率，这种方法的基本思想就是用事件发生
的频率来决定事件的概率。接着采用轮盘选择法进行下一代个体的选择。其基本思想就是
将整个群体根据个体的适应度不同分布在轮盘上，适应度大的个体占的比例多。在选择算
法过程中随机转动轮盘，指针所指区域的个体被选中并生存。这种选择方法对适应度大的
个体选中的机会较大，实现了个体的优胜劣汰。
传统遗传算法的缺陷是初始种群分布不均匀，为了改进这个缺陷，本文采用分区域的
初始种群选择，将整个解空间分成 m 个区域，初始化种群时，分别在每个 1/m 小区域中
随机选择 1/m 个体，最后将 m 个小种群合并为初始种群，这样产生的种群就覆盖了整个
解空间，保证了初始种群的均匀分布
交叉操作
本文采用的是两点交叉，其基本思想是在两个相互配对的编码串中随机选择两个交叉
点，将这两个交叉点之间的基因相互交换得到两个子个体，两个 11 位的父个体，交叉点
的位置为 2、6，通过两点交叉运算得到两个子个体。两点交叉运算如下所示：
父个体 1 11110011010 子个体 1 11101011010
父个体 2 10101000101 子个体 2 10110000101
通过这种方式解决了选课学生人数和教室座位人数之间的冲突，交叉操作产生的新个
体遗传到下一代。
改进的遗传算法
传统的遗传算法收敛速度慢、局部寻优能力差、产生的最优解精度不高，同时由于交
叉算子使种群染色体之间存在局部相似性，这样就很可能导致搜索停止。如果变异率降低
，还会导致“早熟”现象发生。遗传算法在进化过程中，每代总要维持一个较大的群体规模
，从而容易使个体后代过多，造成算法“局部收敛”而不能得到全局最优解。因此，必须对
个体以变异概率进行局部搜素，跳出局部收敛，获得全局最优解。
禁忌搜索算法在搜索过程中可以接受劣解，具有较强的“爬山"能力，新解不是在当前
解领域中随机产生的，而是从中选择的最好解，即最好解产生的概率大于其它解。该算法
通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则赦免一
些被禁忌的优良状态，增加获得全局最优解的概率，因此禁忌搜索算法适合作局部搜索[3]
。
由于传统的遗传算法存在许多缺点，因此本文在变异阶段用到了禁忌搜索算法，用
TS 代替变异算子，防止“早熟”现象发生，使个体呈现多样性。
改进后的遗传禁忌搜索算法
为了使原算法优点保留，弱点被克服或被削弱，提高算法的力度，本文先用 GA 进行
全局搜索，搜索出所有可能的排课情况，并将其分布在解空间的大部分区域，然后在每个
个体课表中用 TS 进行局部变异搜索，得到最优排课情况 [4]。下面给出遗传禁忌搜索算法
的算法流程，见图 1。
改进后的遗传禁忌搜索算法
遗传禁忌搜索算法终止条件为：①在种群中找到了能够接受的最优排课单元；②最适
应种群的个体占群体比例达到了预定的比例；③达到了预定进化代数；④达到了指定的最
大时间。
在遗传算法的迭代中，只要满足上述 4 个条件之一，算法就终止。
TS 运用于 GA 的局部搜索中，避免了 GA 过度早熟的现象，但是如果一直调用 TS 会
浪费时间[5]，因此调用 TS 要根据 GA 的收敛情况来定，开始时调用 TS 的次数很少，随着
迭代的进行，调用 TS 的次数也越来越多[6] ，因为各个排课单元越接近最优排课单元，局
部搜索的作用也越大，因此在 GA 中要合理地使用 TS。
3 结语
本文介绍了国内外排课系统问题研究现状，对排课系统的实质进行了分析，并对排课
系统的实现提出了相应的解决方法。本文采用遗传算法和禁忌搜索算法实现排课系统，首
先对排课问题按照遗传算法进行编码，然后定义好适应值函数后进行选择、交叉操作，并
引入了禁忌搜索算法来代替遗传算法中的变异因子，完成了排课系统的算法设计，达到了
预期目的。
图 1 改进后的 GA TS 混合算法流
