基于C#运用遗传算法的排课系统

王军，陈建云

（南京信息工程大学计算机软件学院，江苏南京210044）

随着高校的发展，课程安排已成为教务部门头痛的事情，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去一个教室上不同的课程，有些教师在特定时间不可以上课但却安排有课。如果没有很好地解决这些冲突，必将产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。

1 排课问题的数学模型

学校排课问题本质上是时间表问题的一类典型应用实例，是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中，需要考虑课程教学效果、满足教师特殊要求等多项优化指标，将各门课程安排到相应的时间和教室需要付出一定的成本。

1.1 符号与约束条件

设课程集合：P={p1，p2，...，pm，...，pM}；教师集合：M={m1，m2，...，mp，...，mP}；教室集合：S={s1，s2，...，sk，...，sK}；班级集合：C={c1，c2，...，cn，...，cN}；时间集合：T={t1，t2，...，td，...，tD}；时间与教室对的笛卡尔积为：G=T·S=（t1，s1），（t1，s2），...，（tD，sK）；G中的元素称为时间教室对；课表问题的求解过程就转化成为每一门课程寻找一个合适的时间教室对。

排课过程中必须满足各种约束条件，各种约束条件可以归纳成2类，这样能简化分析过程。

1.1.1 硬 约束条件

硬约束条件是在排课过程中由于各类资源的有限，因此必须满足而无法变更的约束条件，通常只要满足下面3类硬约束条件就能够保证在排课的过程中不发生此类冲突。

1）同一时间，一个教师只能上一门课程，记为X1，且X1≤1，其中：p=1，...，P；d=1，...，D。当X1=1时，教师mp在时间td和教室sk上课pm；当X1=0时，不成立。

2）同一时间，一个班级只能上一门课，记为X2，且X2≤1，其中：n=1，...，N；d=1，...，D。当X2=1时，班级cn在时间td上教师mp的课程pm；当X2=0时，不成立。

3）同一时间，一个教室只能上一门课，记为X3，且X3≤1，其中：k=1，...，K；d=1，...，D。当X3=1时，教室sk在时间td由教师mp上课程pm；当X3=0时，不成立。

1.1.2 软 约束条件

软约束条件是在排课过程中可以满足又可以不完全满足的约束条件，是排课过程中在满足硬约束条件的基础上能尽量要求满足的约束条件。软约束条件会因不同的教学情况而有所差异。通常也可以通过调节软约束条件的满足程度而改变排课的效果，可以将一定要满足的软约束条件转换为“硬约束条件”。

以下是排课过程中常用的软约束条件：

1）教师①老师一天之中连续上课节数；②老师课程大部分在上午或下午；③总学分为奇数的课程一次连上三小节；④早上8点（第一节）是否排课；⑤下午4点以后（最后一节）是否排课；⑥中午12点（第五节）是否排课；⑦一门课尽量分散在一个星期中。

2）学生①中午（12：00）尽量不要排课；②上完体育课尽量不要排课；③共同科目同班级一起上；④选修科目各班级分开选课；⑤对于总学分为偶数的课程采取两学分课连上；⑥对于总学分为奇数的课程采取三学分课连上；⑦学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。

2 排课问题的算法

2.1 算法流程

遗传操作流程如图1所示。

图1 遗传操作流程图Fig.1 Flow chart of Genetic operation

2.2 染色体编码

遗传算法（GA）中首要考虑的是如何表现其问题，即如何对染色体编码，使之适用于GA操作。在经典的遗传算法中，常采用浮点数或二进制的编码方法，而研究中，每条染色体代表每位教师的课表，其结构表示如图2所示。

图2 课表用染色体表示的结构Fig.2 Structure of schedule of chromosomes

班级ID染色体在程序中可用十进制数编码，例如：某一个教师编号为1234，要教“计算机基础”这门课，课程编号为5678，周学时为4，班级为JSJ08001、JSJ08002，随机产生上课时间，随机选择大于两班总人数的教室，则可生成染色体如：“JSJ08001 JSJ0800256781234024012241”其中02401，2241分别代表教室及上课时间星期二第二个教学单元（即上午3、4节）和星期四第一个教学单元（即上午1、2节）。

按如上编码，两条染色体对后9位作交叉操作，不会影响到每位教师所教授的课程，也不会造成教师课表内含其他教师的教授课程或每代演化后染色体结构不合理等问题。

2.3 初始种群生成

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

2.4 选择操作

在排课表问题中，选择操作方式采用轮盘赌方法，按照轮盘中的比例进行区域的分配。适应度较高的方案占据区域较大，选中的概率也较大，适应度低的方案占据区域较小，选中的概率也较小。

2.5 交叉操作

编排课时，根据点交叉算子的思想，可在p个开课时间和教师课表中随机采样两个Li，对所有Pij和Tij的值进行互换。将互换后的两个个体作为两个子代插入新种群。也可以选择某个班级的课表TC和学生课表sij，对TC集合和S集合中的所有时间安排进行互换。此时，交换的基因是若干个L时间安排组成的集合。

2.6 变异操作

变异虽然以很小的概率发生，但是它保证种群的多样性，防止搜索得到的解陷入次优解，有效抑制遗传早熟现象的发生。随机的方法可以保证个体的迥异，从而保证初始解在解空间的均匀性。在变异操作中随机选择一个个体的基因，这个基因可以是时间也可以是教室等，让它随机变换成另一个时间或者教室，使其在原始空间位置做轻微扰动，有利于搜索空间逐渐向全局最优空间靠拢。

2.7 适应函数

编排课表主要将以下几方面因素作为排课表所要达到的目标：教师对时间的期望满意度、教师课时分布密度、班级课时日分布均匀度、大多数学生愿意上此节课的程度。将以上4个目标分别赋予不同的权值wi，运用线性加权法，得适应函数为中，α代表可行系数，当进行交叉形成不可行的课表（出现了教师、教室、时间等的冲突）时，则该方案的适应度为0，在求解过程中直接被剔除。由于在交叉过程中会产生许多适应度为0的方案，所以采用随机生成初始种群的办法不断形成等量的可行解，以保持群体规模，避免算法的过早收敛。

2.8 停止规则

如果一轮适应度计算比较以后，利用轮盘赌的方法按照一定的概率进行选择操作，将适应度较高的个体选择出来，以便于保留优秀的个体为以后的操作，没有达到理想的状态，则按照一定的交叉概率进行个体之间的交叉和遗传变异操作，重组个体后再计算下一代的适应度。直到有一代的适应度达到预期要求。如果遗传的代数达到了最大数，则将结果输出，若满足适应度，且各个约束条件都已经不存在冲突，则认为排课结果比较合理，宣告遗传算法正常结束。

3 系统结果展示

开发排课系统，简要介绍C#运用遗传算法的实现过程。在VS2005运行，生成主页面排课系统，有排课向导，如图3所示。然后输入教师ID号、教师姓名、所教课程与优先级排课，输入完之后点击下一步，到最后有开始排课，就会给出排课的各种方案，如图4所示。

图3 排课系统主页面Fig.3 Main page of timetabling system

图4 排课后的方案Fig.4 Scheme after the timetabling

4 结论

该模型与求解方法已在实际中得到应用，取得了较好的效果。在使用遗传算法优化后排课算法的实际效率有极大的提高。因此用遗传算法实现类似排课问题的最优解也是一种比较简单实用的方法，收敛速度很快，时间段分配均匀。但是在实际应用中也可能没有终止条件，目的是可以依次提供不同的可行解以供使用者选择直到所有解给完或者使用者终止。如果只考虑最优解的问题，可以使用迭代的适应度几乎不变作为终止条件或者规定迭代次数。值得一提的是，有些实际问题的可行解可能是唯一的，比如教学场地或教师资源紧缺的情况，更严重的是如果约束条件太苛刻，甚至可能没有可行解，在此类情况下人工干预还是有必要的。

[1]李敏强.遗传算法的基本理论与应用[M].北京：科学出版社.2002.

[2]韦玉，冯速.免疫遗传算法在排课问题中的应用[J].北京师范大学学报，2008，44（2）：168-172.

WEI Yu，FENG Su.The application of immune genetic algorithm int the proble of timetabling[J].Journal of Beijing Normal University，2008，44（2）：168-172.

[3]魏平熊，伟清.用遗传算法解组卷问题的设计与实现[J].微电子学与计算机，2002，8（4）：44-50.

WEI Ping-xiong，WEI Qing.Test paper problem solving by generic algorithm[J].Microelectronics&Computer，2002，8（4）：44-50.

[4]Salem M，AlYakoob，Hanif D S.A mixed-integer programming approach to a class timetabling problem：a case study with gender policies and traffic considerations[J].European Journal of Operational Research，2007（180）：1028.

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

QI Zi，DENG Hui-wen，YANG Jiu-jun.Timetabling system’s design and implementation based on the genetic algorithm[J].Journal of Computer Application，2007，27（12）：199-201.

[6]陈静.自动排课系统算法的分析与设计[J].科技情报开发与经济,2007，17（34）：217-219.

CHEN Jing.Analysis on and design of the algorithm of the auto-arranging curriculum system[J].Sci-tech in formation development&economy，2007，17（34）：217-219.

[7]唐慧丰.遗传算法原理与应用[EB/OL].（2006-05-20）

[2010-03-20].http：//wenku.baidu.com/view/0732d180d4d8d-15abe234e35.html.