崔玉连，杨新锋

0 引言

高校排课问题是一个多元分配问题，它研究如何把学生和老师分配给课程、课程单元或者班级，如何把上课事件分配给教室和时间[1]。1975年S.Even证明了高校排课问题在本质上属于NP完全问题。解决此类问题的常用方案有贪婪算法、遗传算法、模拟退火算法、专家系统算法、蚁群算法、图论算法等。因遗传算法具有群体搜索策略、群体中个体之间的信息交换不依赖于初始参数的特点和良好的并行性、通用性、稳定性，成为求解该类问题的主流方法[2]。

1 遗传算法

遗传算法(Genetic Algorithms, GA)是一种利用模拟自然进化过程而搜索最优解的算法，是通过研究达尔文生物进化论的自然选择和遗传学机理的生物进化过程而产生的，是一种运算速度较快、系统性较强的新型算法[3]。

遗传算法模拟自然进化过程，包括选择、交叉、变异等操作[4]。首先在基础问题数据中随机地选取若干个体形成初始种群，然后运用适应度函数计算个体的适应度函数值。根据适应度函数值，判断每个个体是否满足优化准则，如果不满足就继续生产下一代个体，可以通过交叉、变异操作生产新的个体，从而构成新的种群，再计算新种群中每个个体的适应度函数值，若满足优化准则就停止迭代，否则继续进行下一代种群的生产，直到满足优化准则为止。

2 排课问题描述

2.1 排课问题的约束条件

排课问题需要考虑的相关因素很多，包括课程、班级、教师、教室、时间及上课事件等，其概念模型，如图1所示：

图1 排课问题概念模型

需要解决的利益冲突有多种，排课过程中的冲突可以用约束条件来表示。排课问题中的约束条件分为3类：基本约束、硬约束和软约束。

（1）基本约束是指各因素之间不可能发生的冲突，属于不可调和矛盾，满足基本约束是排课的最基本要求。基本约束条件包括：1）班级的约束：一个班级在一个时间内只能上一门课程；2）教师的约束：一个教师在一个时间内只能上一门课程；3）教室的约束：一个教室在一个时间内只能有一门课程。

（2）硬约束是依据学校的实际情况，排课时必须遵循的原则，否则即使安排出课表，生成的课表也不能完整执行。硬约束条件包括：1）按照最小的时间单元（2学时）安排上课时间；2）每门课程都有特定的教学资源；3）教室容量既要能够容纳上课的班级，但又不能超出太多；4）对特定的不能排课时间进行预处理。

（3）软约束的满足与不满足不影响课表的正常执行。一个完美的课程表应该“人性化”，应该考虑的软约束条件包括：1）尽量在把必修课安排在上午，选修课安排在下午，晚上尽量不安排课；2）一门课在一个星期中的上课时间尽量分散；3）一个教师的课不能连续排满一整天；4）学生课表中的上课时间不能过分集中；5）同一班级或教师相邻时间段的上课地点不能相距太远；

2.2 建立排课问题数学模型

根据以上分析，编排课程表的过程中所涉及的实体集合有：课程、班级、教师、时间、教室，可以如下表示：

时间与教室组成的时间-教室对可以用时间集合与教室集合的笛卡尔积[5]来表示。

其中课程是关键实体，与其他实体都有关。课程包括如下属性：

其中hi为周学时，ci表示该课程的上课学生，可以为多个学生。pi为该课程的任课教师，可以为多个教师。ti表示该课程的上课时间，包括该课程各次上课的时间。ri为该课程的上课教室，每个时间唯一对应一个上课教室。

在以上的5元组中，前3个为已知元组，后两个为待求元组。

课表编排就是求L到N的幂集2N的一个映射，即ψ:L—＞2N，并满足基本约束条件。

3 改进遗传算法在排课中的应用

基于改进遗传算法的自动排课实现流程，如图2所示：

图2 基于改进遗传算法的自动排课实现流程

遗传算法可定义为一个8元组[6]：

其中，C为个体编码方式，P0为初始群体，M为种群规模，Φ为选择算子，F为交叉算子，N为变异算子，E为个体适应度评价函数，T为遗传运算终止条件。除了以上8元组之外，还有两个与遗传操作相关的参数：

Pc：交叉概率，一般取0.20～0.95;

Pm：变异概率，一般取0.0001～0.1。

自动排课的改进遗传算法设计就是要将以上 8元组具体化。

3.1 三维编码

遗传算法最常用的编码方式是二进制编码。结合实际应用需求，均衡考虑制约排课系统的各因素，采用三维编码，其优点为可方便地利用三维数组保存排课相关信息，编码和解码直观，进行交叉和变异运算时冲突检测和适应度计算方便以及程序实现复杂度低等。

一个采用三维编码表示的染色体可直观地看作一个立方体，如图3所示：

图3 三维编码图

图中，X轴为时间轴，每个时间间隔对应一个时间坐标，如X1、X2分别代表周一上午第一、二节课（大课）。以一周5个工作日、每个工作日四个时间段计，共有20个坐标值（X1-X20）。Y轴每一间隔代表一间教室，Z轴每一间隔代表一个授课事件。其中，Z坐标（授课事件）又可划分为Za（教师）、Zb（课程）和Zc（班级）三个分量。

三维坐标可唯一地确定的一个小方块，称作个体基因。其值定义如下：

染色体全部基因块被赋值后，染色体就代表了一个课表编排方案。

3.2 产生初始种群

群体初始化的目的在于为后面的遗传操作提供初始群体P0。群体的规模M表示群体所含个体的数量。M取值一般为 20～100。

产生初始种群的步骤如下：

第1步：建立一个三维数组（三维数组表示染色体），把数组中所有元素的初值置0；

第2步：确定授课事件表中的第一个授课事件在一周内的授课次数，用M来表示，根据这个M值将染色体三维数组第一层（垂直Z轴的层）中随机的M个位置值置1，其它不变；

第3步：确定授课事件表中的下一个授课事件在一周内的授课次数，用N来表示，根据这个N值将对应的染色体三维数组中的那层（垂直Z轴的层）中随机的N个位置值置1，其它不变；

第4步：重复第3步，直到处理完所有的授课事件为止；

第5步：建立新的染色体三维数组，并重复第2步、第3步和第4步，直到染色体三维数组的个数达到种群规模的大小为止。

3.3 个体适应度评价函数

遗传算法是在个体适应度评价函数的引导下进行的。由于需要考虑的约束因素很多，因此在设计个体适应度评价函数时，要充分考虑各种因素对评价函数的影响。

针对高校在编排课程表过程中所考虑的实际约束因素，染色体的个体适应度评价函数可以定义为：

评价函数制约因素的期望值及其权值确定为：

期望值 Pl：对应教室利用率（上课人数/教室可容纳人数），权值w1=1；

期望值P2：对应同一门课程的均匀分布（如表1所示），权值w2=l；

期望值P3：对应体育课上课时间，权值w3=20。如表2所示：

表1 同一门课程的两次上课时间间隔及P2取值

表2 体育课上课时间及P3取值

计算个体适应度的方法为：如果存在教师冲突、班级冲突、资源冲突或教室容量冲突，则个体适应度值为 0；如果不存在任何冲突，则个体适应度值为：（同一门课程的均匀分布期望值×1）+（自习上课时间期望值×20）。

3.4 自适应地产生交叉、变异概率

根据以下两个表达式分别计算交叉概率和变异概率：

其中：0

3.5 选择操作实现

第1步：将当代种群中所有染色体的适应度函数值进行累加求和得到总的适应度函数值。

第2步：用每一个染色体的适应度函数值除以总的适应度函数值求出每个染色体的选择率。

第3步：根据选择率将每一个染色体复制到下一代种群中。

3.6 交叉操作实现

第 1步：从待交叉的个体集合中随机地选取两个个体（设为A和B）;

第2步：随机地选择A和B发生交叉的位置（设为N UM）;

第3步：将A中Z坐标大于NUM的所有基因块与B中相同位置的基因块交换基因值;

第4步：计算出新产生的两个个体的适应度函数值。

3.7 变异操作实现

第1步：从待变异的个体集合中随机地选取出一个个体（设为A）。

第2步：采用随机地方式确定A发生变异的位置，也即确定三维数组中垂直Z轴的某一层。

第3步：根据染色体发生变异的位置对应的授课事件的具体情况，给这个授课事件重新安排上课教室和上课时间，从而产生出新的个体。

第4步：计算出新产生个体的适应度函数值。

3.8 课程表的生成

第1步：在数据库中建立一个课程空表;

第2步：根据三维数组第一层（垂直于Z轴的层）对应的授课事件及该授课事件所处的上课时间和上课教室，填写课程表的第一条记录（如果该授课事件有多个上课时间则填写多条记录）

第3步：根据三维数组的下一层（垂直于Z轴的层）对应的授课事件及该授课事件所处的上课时间和上课教室，填写课程表的下一条记录（如果该授课事件有多个上课时间则填写多条记录）;

第4步：重复第3步，直到三维数组中所有的层（垂直于 Z轴的层）都处理完毕，即所有的授课事件都填入了课程表。

4 测试与分析

在某高校中，利用其原排课系统及采用本文改进算法优化的排课系统分别对某院计算机相关专业学生所上第一学期课程进行了排课测试，共涉及6个班级，35门课程，占用10个教室。测试结果，如表3所示：

表3 原排课系统与优化后系统排课情况对照表

通过上表分析，证明优化后的排课系统确实在很大程度上改善了原有排课系统的不足。

5 总结

本文的研究只是针对某高校的课表编排实际问题，对利用遗传算法求解排课问题作了一些有益的尝试，具有一定的局限性。对于比较完善的通用排课系统遗传算法求解方法还有待进一步的研究。

[1]Gotlieb.The Construction of Class Teacher Time Tables.[c]Proceeding IFIP Congress,Amsterdam,1963:73-74

[2]廖宇力.基于遗传算法的排课问题适应度函数设计.[J]现代计算机（专业版）,2010(4):18-20

[3]杜健,董玉才,王惠德.基于遗传算法的高等院校排课系统研究.[J]信息系统工程,2010(8):23-25

[4]赵晓庆,熊璋,方义.高校智能排课系统的设计与实现.[J]计算机与现代化,2004(11):103-105

[5]石慧,彭晓红,邬志红,舒远仲.求解多校区排课问题的基因对交叉遗传算法.[J]计算机工程与应用,2010(18)91-93

[6]姜静,谭博学,姜琳.基于改进自适应遗传算法的仿真研究.[J]山东理工大学学报（自然科学版）,2008,22(6):10-12