基于遗传算法的排课系统的研究与实现

穆雪

摘 要：介绍是排课问题，分析了排课的数学模型，分析了基于遗传算法的排课算法的基本原理及及其算法特點，利用时间模式，提出了基于遗传算法解决排课问题的方法，并验证了该方法的有效性。

关键词：排课；遗传算法；多目标优化；时间模式

1.引言

人工编排课程表是教务人员在进行教学管理中最为头疼的工作之一。它涉及到很多的软件 硬件资源和内外部因素，如：时间、地点、教师、学生及课程等。尤其是随着高职院校的不断扩招而软硬件设备没有及时更新和增加，造成了人多教室省、课程多时间少等状况。这些问题使得学校的教学管理无法正常进行。传统的人工排课方式存在有以下几个方面的问题：人工编排课程表工作量大人工编排课程表依赖于人为因素；人工编排课程表可维护性差；人工编排课程表安全性差。

排课系统就是在教师、教室和时间这3大资源数量有限，约束不同的条件下，合理安排班级的课程，使得学生和教师获得较为合理的上课时间和空间，是一个多目标的调度问题。如何实现课表的合理安排是当前高校教学管理人员值得研究的问题。

遗传算法（Genetic Algorithm，简称GA）是一种自适应随机搜索算法，具有全局收敛性和并行性，且对模型是否线性、连接、可微等不作限制，也不受优化数目、约束条件的束缚，所在工程优化、图像处理和模式识别等领域取得广泛的应用。本文将结合实际排课中所涉及到的各类约束、优化目标设计一种特定的基因编码方法，和相应的目标评价函数，并在实际应用中取得了较好的效果。

2.数学模型分析

排课问题是求解三元组（Lecture，Time，Room）课程、时间和教室的统筹调度，即给指定的课程安排适应时间、空间等教学资源，使学校课程整体达到一个较为合理的状态，其中课程又包含了（Classes，Lesson，Teacher）三个元素，即每个授课的班级、课程名称和对应的老师是相关的，这些授课计划数据是系统的输入部分，而一个合理的排课结果是指使目标函数达到优值，表现为课程的时间安排均匀、教室利用率高、尽可能多满足教师偏好等。实现此结果关键在于如何解决排课过程的众多约束和有效目标函数的建立。

对于一个班级的某一个时刻不能上一门以上的课程，而在高校中由于资源紧张许多课程大班开课，因此对一次授课要求所有上该课的班级在该时刻没有其他课程，则对于任何一门课程开设时间为t的课程lec有 =0

对于每个教师任何时刻只能参加一次授课，约束模型与班级约束相似，只是一次授课只有一个教师，冲突检测只需对某个教师所授所有课程集合进行统计即可。

教学资源的约束，要求任何一个时刻作何一种类型的教学资源安排量不可超过学校拥有该类资源的总量；一个授课的安排要求该教学班级人数不可超过教室（或者其他教学资源）的容量，对于需要r类型教学资源，在t时刻授课的集合

3.时间模式

时间模式是一种上课时间的安排形式，由时间模式代码表和时间模式明细表两个表组成，其中时间模式代码表是主表，定义了时间模式的基本信息，时间模式明细表是从表，定义时间模式所对应的上课时间。使用时间模式安排课表具有以下优点：

通过时间模式可以有效地安排课程，防止周学时较大的课程被安排在同一天或相邻的两天。

时间模式基本表中定义了优先级，可实现按照会优先级的顺序安排班级的课表，可避免随机安排班级课表所造成的课程上课时间的不合理问题。

时间模式的比较灵活，实现较容易，能满足学校实际上课的需求，只定义较为合理上课时间的组合即可。

4.基于遗传算法的排课算法

遗传算法的基本原理：首先采用编码方式将解空间映射到编码空间，每个编码对应问题的一个解（称为染色体）。通过随机方法确定初始的一群个体（称为种群），在种群中根据适应度值或某种竞争机制选择个体，利用各种遗传操作算子（交叉、变异等）产生下一代，如此进化下去，直到满足期望的终止条件。

4.1 染色体编码

根据排课的实际情况，使用十进制来对的个体进行验证码，每个个体利用m*26 的数组表示。

4.2 初始种群生成

一个染色体就是一个可能的排课结果，是一个m*26 的数组，需处理的数据量较大，结构相对比较复杂。因此，如果初始种群中个体的分布不好，将很容易使整个排课结果陷入局部最优而得不到好的排课结果，因此初始种群的生成对整个算法的影响较大。

将时间模式引入到遗传算法中进行初始种群的生成。基本思想：首先确定班级的数量及所要上的课程；接着随机选取一个班所上的课程产生所需要的时间模式编号，判断是否冲突，不冲突，则在个体相应的上课时间上记录课程号，否则重新产生随机模式编号；真至所有个体的所有班级的课程都安排完成。

算法：GAInit（T，W，n）

Input：时间模式T，教学任务W，初始种群大小n

Output：初始种群GAI

步骤1：定义初始种群GAI结构，确定班级个数m，种群大小n.。

步骤2：确定所有的上课班级及其所要上的课程CL，初始化i=1，j=1，p=1。

步骤3：初始化种群中第i个个体。

步骤4：取第j个班的课程ID（p），确定其周学时zxs。

步骤5：根据zxs随机生成时间模式，确定一上课时间。

步骤6：判断上课时间是否冲突，没有冲突，则将课程号ID（p）记录于第i个个体的相应的时间位置。否则，转到步骤5。

步骤7：判断第j个班的课程是否安排完成，如果没有完成，p=p+1，转到步骤4，直到j班的所有课程都安排完成。

步骤8：否则j=j+1，转到步骤4，直到所有班级的课程安排完成。

步骤9：i=i+1，直到所有的个体的初始化完成。

4.3 适应度函数

根据排课的软约束条件定义适应度函数，适应度值越小，个体越优。适应度由下面公式计算：F=a1×C1+a2×C2+a3×C3

其中C1为课程上课时间评价，C2 是一周多次课程的分布评价，C3教师课表分布评价。a1、a2和a3为评价系数，三者和为1。

4.4 选择操作

采取轮盘选择方法，根据个体适应度的大小，将种群中F值较小的个体以较大的概率保存到下一代中。

5.结论

以20个班级，120课程，课程的周学时为2和4两种情况，基于MatLab平台实现了排课系统。结果证明本文的算法能较快地收敛，且能得到较为理想的课表。

本文提出了时间模式的概念，并将其与遗传算法结合，提出了新的基于遗传算法的排课算法。在算法中利用时间模式求解了遗传算法的初始种群，且根据软约束设置了不同的课表的评价指标，避免了冲突，实现了课表的有效优化。

参考文献

[1]杨宇.高校排课系统理论研究与开发---遗传算法在课表问题中的应用.北京：北京理工大学，2003.

[2]沈丽荣，陈明磊.基于遗传算法的高校排课系统研究.计算机科学与技术，2006（112）.

[3]膝姿，邓辉文，杨久俊.基于遗传算法的排课系统的设计与实现.计算机应用， 2007 （12）.

[4]谢勇，郑金华.基于遗传算法的综合性大学排课系统研究.中国教育信息化， 2007 （11）.

[5]张春梅，行飞.用自适应的遗传算法求解大学课表问题.内蒙古大学学报（自然科学版）， 2002.