基于遗传算法的高职学院排课系统设计研究

朱良学

(酒泉职业技术学院，甘肃 酒泉 735000)

一、高职排课问题描述

排课因素主要包括：(授课)时间、(授课)班级、(所授)课程、(授课)教师、(授课)地点。排课主要就是解决这几个资源在排列组合中可能发生的矛盾和冲突，找到一组不发生冲突的较优合理搭配。

二、排课问题数学描述[1，2]

将排课问题所涉及的资源做如下表示：

C表示课程(course)集合{c1,c2,,,cK}；

T表示教师(teacher)集合{ t1, t2,,, tA}；

R表示教室(room)集合{r1,r2,,,rC};

N表示时间集合{n1,n2,,,,nd};

S表示班级集合{s1,s2,,,sf}。

这样排课问题就变成一个5元组CTRNS=(C，T，R，N，S)，排课的目标就是找出满足约束条件的(C，T，R，N，S)组合。排课要满足的约束条件通常我们归纳为硬约束条件和软约束条件两大类:硬约束条件指排课过程中必须满足的要求，软约束条件通常包括排课过程中需考虑的经验、常识、特殊情况等。

排课问题的硬约束条件至少有以下几个方面的考虑：

第一， 除选修课外，一个班级在同一时间只能有一门课；

第二，一个教师在同一时间段只能有一门课；

第三，一个教室(实训室)在同一时间段只能有一门课；

第四，一个教师所上的多门课程必须排在不同时间段；

第五，同一时间段准备的上课教室数应大于上课班级数。

通常软约束条件有以下考虑：

同一门课程的上课时间尽量间隔合理：也就是一周上多节的课程,各次课之间应该有合理的时间间隔；学生上课时间要尽量选择最适宜的上课时间片：也就是尽量将课程安排在最适合上该门课的时间段；适当考虑某些教师的特殊情况；各班级课表要尽量避免某些天满课,某些天少课或无课的情况发生。

三、以往手工排课过程[3]

按照J职院的排课习惯，学期伊始，教学干事会根据某班级的教学任务,先选取较难安排(或需优先安排)的课程,根据课程的周课时安排该门课在每周上课的节次，在教师课表和教室课表中选取相应的公共空闲时间。当然这个过程需要不断地回溯、反复调整，达到期望的排课效果。

当排课量巨大时,便会出现冲突,反复回溯、调整,直到所有课程全部排完。所以，排课工作十分繁复，以J职院来说，近百个专业，一万多名学生，六百多名教师，几百门课程，教师、教室等资源日趋紧张，要实现合理、较优排课，工作量、难度之大可想而知。

四、遗传算法思想

综上所述，由于排课问题的高度复杂性，特别是硬约束、软约束条件下要达到较优排课目标时，传统算法很难较好解决问题。大量研究人员对排课问题进行了探索，常用的方法包括贪婪算法、回溯法、图论法等等[4～6]。遗传算法以其思想简洁，解决问题思路清晰，搜索效率简捷高效，成为解决排课问题的一种重要方法[7]。

遗传算法(Genetic Algorithm, GA)在1975年被美国数学家JohnHolland率先提出，仿照生物界物种选择和进化原理，将问题转化为遗传编码，将含问题解的种群作为解空间，设计适应度函数对每个解进行筛选；以概率论为基础，在解空间进行随机搜索，最终一步步找到问题的最优解；是一种具有高度并行性的随机搜索算法。

在遗传算法中，类比来说，染色体可以看作给定问题的解，染色体构成的个体集合为初始种群；一个个体是问题的一个解，有多个个体组成的种群是问题的一组解。根据遗传进化原理，将当前种群中个体适应度较大的个体作为优秀个体，设计选择、变异、交叉等算子对个体进行操作，不断筛选掉适应度小的个体，种群的适应度不断提高；这样就使种群中的个体得到更新，整个种群不断演化，持续衍生出新一代更为优秀(即适应度值更大)的种群；在演化过程中，由适应度函数来评定个体的优劣，当最优个体的适应度达到给定的阈值，算法终止。如此，经过若干代的演进之后，最后得到的一个种群将是适应度最优之种群，也即最后一代种群就包含着问题的最优解。

五、遗传算法的高职排课系统设计

(一)排课问题向遗传算法的转化

要用遗传算法思想解决排课问题，就必须将排课问题转化为遗传算法能处理的对应问题。遗传算法最基本的概念即是基因，进化就是发生在基因为基础的个体上的。所以如何将课表转化为基因是实现利用遗传算法解决排课问题的首要问题。这一过程通常称之为编码。编码后，基因、个体、种群就构成了遗传算法解决排课问题的解空间。

排课问题向遗传算法的对应转化如下:

1.基因

根据学院的实际排课情况，设定基因的组合形式如下 ：

教师工号课程代码班级代码教室编号课程周课时课程类型

基因编码中包含了排课的主要因素：教师信息(谁上课)，课程信息(上什么课)，班级信息(在哪个班级上课)，教室信息(在哪儿上课)；教师上多少节次课程就产生多少条这样的基因。再者，基因编码中尽可能把课程表的各种冲突因素包含其中。课程周课时指该门课程每周占用几个节次，教师每上一个节次就会对应一个基因编码。课程类型一般指该门课程的特别情况，如该门课有何特别要求等等。

2.染色体

染色体的构成规则如下：基因+班级名称+时间片。基因如上所示，时间片指学院课程时间安排的如下情形：学院正常上课5天，每天5个时间段:

第1时段:上午1、2节, 8∶00-9∶40;

第2时段:上午3、4节,10∶00-11∶40

第3时段:下午5、6节, 15∶00-16∶40;

第4时段:下午7、8节, 17∶00-18∶40;

第5时段:下午9、10节, 19∶30-21∶10;

一般第5时段排课较少，主要排形势政策课等等。这样每天有5个时间段(T1-T5),每周5天共有25个时间段(T1-T25)。25个时间段构成时间片。

这样每一个“染色体”对应的其实是班级的一个课表，即一个染色体就是一个班级课表。整个课表就是这一个个班级课表就构成的。

3. “个体”

有多个染色体构成个体；有多少个班级就有多少个染色体；所以一个个体对应的其实就是一张完整课表，它包含了所有班级课表。

4. 种群

有多个个体构成种群。所以种群包含了多种可能排课课表的情形。

5.初始种群产生

先产生染色体，这类同于排一个班级的初始课表，按照学院人工排课的习惯，为了减少冲突，应先排固定时段的教师课程，因为他们只有这个时间段可以排课上课；然后再次第排其他教师的课程。相应的做法就是：先在固定教学时段填入含对应教师的基因编码，再将含该班其他教师的基因编码逐次填入随机产生的相异时间段。如是直到所有含该班授课教师信息的基因编码填写完成。如此就生成了一个该班的初始课表。显然，这样的课表将来必然隐含大量的冲突。

有多少个班级就这样生成多少个班级初始课表；所有班级初始课表就组成了完整排课课表，也即生成了一个遗传个体。

设定一个种群数，按这个数生成一定数量的遗传个体，就形成初始种群；它包含了所有可能的排课情形。

(二)基于遗传算法的排课系统算法设计

1. 检测和消除冲突

由于在做编码设计时已经考虑到硬约束条件的因素，由此可能导致的冲突将不会发生；我们只需对每个教师在同一时间段上一门以上课程的冲突进行检测和消除就可以了。

2.适应度函数设计

根据J职院教学实际情况，考虑了以下3个因素：课程安排是否太集中或分散；课程安排的上课时间段是否合理或高效；上课地点或设备对学生上课的影响。

第一，课程安排是否太集中或分散。同一门课上课时间太集中或分散，都不利于学生学习。每周时间片共有25个时间段，两个时间段的差值就反映了课程安排的均衡情况。每个差值赋予一个期望值，这个期望值就表示了这种均衡。

课程的均衡用

Fjh=∑Fjh(i)

(5-1)

函数表示。

第二，课程安排的上课时间段是否合理或高效。每周时间片共有25个时间段，这25个时间段中有些时间段上课效率较高，这些时间段就赋予较高的期望值。用函数

Fgx=∑Fgx(i)

(5-2)

表示课程上课时间段是否合理或高效。

第三，上课地点设备对学生上课的影响。J职院由于上课地点、设备的差异，影响了学生上课的积极性。这种差异也赋予一个期望值，用函数

Fds=∑Fds(i)

(5-3)

表示。

这样课表适应度函数就可以表示为：

Fit= (k1×Fjh+k2×Fgx+k3×Fds)3

(5-4)

K1,K2,K3为加权因子。

根据学校的实际情况，合理设置k1,k2,k3的值，对每一个期望值及其所占比例也要合理配置，以便使所设计的排课系统更加符合实际、方便高效。

3.遗传算子设计

生成的初始种群，从生物角度来说，其个体的适应性还处于较差的程度，表现在个体的适应度函数上，其值还较小。根据生物逐代进化的原理，下一代比上一代更适应环境，也就是下一代比上一代有更高的适应度函数值。遗传算法就是依据这个原理，以适应度函数值作为评价个体优劣的标准，逐代优化，一步步搜索到最优解。

下面是遗传算法所涉及的几个典型算子:

(1)选择算子(Reproduction )

根据生物界适者生存、择优弃劣的自然选择法则，从种群中选择出适应性较好的个体，作为产生下一代的基础。遗传算法模仿这个原理，从种群中选择出适应度值较高的个体，作为染色体进行后续运算之基础。

现在选择算法比较常见的是轮盘赌方法。选择概率计算方法为:

P1=f1/∑f

(5-5)

各个个体的选择概率和其适应度值成比例。选择算子从父代个体中选出适应度函数值最高的替代当前子代个体适应度函数值最低的，这样，就从上一代种群中保留了适应度函数值高的染色体，作为后续进化迭代之基础。

(2)交叉算子(Crossover )

通过选择算子从上一代种群的父代个体中继承了适应度函数值高的染色体，但并没有生成新的染色体。要生成新的优秀个体，就必须增加新的操作，通常简单有效做法是交叉操作：在配对父本中的对应染色体之间进行交叉。本文采用配偶对的交叉方式，只进行单点交叉。

(3)变异算子(Mutation )

生物由于自然环境的变化，基因发生突变，生物学称之为遗传变异。遗传算法依照这个原理，设计了变异算子。变异算子有反转变异、插入变异、移位变异等。通过变异算子，人为改变了群体中个体的某些值，为新个体的产生提供机会，在随机搜索时避免了过早收敛，也使算法增强了随机搜索能力。

(4)设置控制参数

控制参数的选取对遗传算法性能有极大影响，在后面的实验中可清晰看到。遗传算法需要设置的控制参数通常有：

1)编码长度

由于尽可能要把排课过程中包含的各种冲突因素考虑其中，编码长度一般由问题求解结果的精确性决定。

2)种群规模

根据实际的排课要求和实验条件，确定种群规模的大小。但一般的情况是：种群规模太小，搜索找到最优解的可能性就小；种群规模过大，搜索找到最优解所花费的时间就多，致使收敛时间增长，算法求解效率低。一般种群数目取20-160之间。

3)选择率

根据遗传原理，只有适应度高的优秀个体被延续至下一代，它的优越性才可能保持。因此可设计下面的选择率及选择数计算公式:

期望的选择率：

Px=Fit(i)/Fit

(5-6)

其中Fit(i)为其中某个个体适应度值，Fit为种群的适应度值总和，i=1, 2, 3,种群数；得到的个体期望的选择数如下:

XZ(S)=INT(Px×种群数)

(5-7)

个体的适应度值占整个种群适应度值的比值决定了选择数的大小。

4)交叉率

交叉操作是种群生成新个体的主要操作，交叉概率又决定了交叉操作发生的频率；因此，交叉概率通常应取一个合理的较大值。但若过大，会使高适应度值的优良结构很快被破坏掉，太小又会使搜索停滞不前。故通常pc取0.5-1.0之间，本系统pc取0.8 。

5)变异率

变异概率Pm是增大种群多样性的又一个因素，变异概率太小，不会生成新个体;变异概率太大，又会使遗传算法变成随机搜索。通常Pm取0.001-0.1之间。本系统取0.02。

6)进化代数

当编码长度较长时，进化代数要取小一些，否则会影响算法执行效率。但取值太小，各目标不收敛。取值较小，虽收敛但不是全局最优。因而要取较大值。进化代数的选取还可采用某种判定准则，准则成立时，即停止。

六、J职院排课实验结果及分析

选择MATLAB_R2008a及其汉化包；由于实验条件所限，缩小排课规模至二级学院，按照J职业技术学院机电工程学院2019一2020学年第二学期的教学计划安排为例,进行了模拟排课实验，设置的数据如下:

时段:每周上课5天,每天排5次课,总时段数为25,各时段期望值根据学院实际情况确定(这里不必列出，实验设置是直接填入);

教室:36个(含所有可排课的教室及计算机室);

实训室:12个;

教师(含外聘教师)90人;

课程:224(所有专业，所有课程);

班级:42个(每班人数最大值为50);

学生:1620人;

根据遗传算法搜索最优解的原理，实验考虑了如下几个因素：

第一，种群规模对排课的影响：主要是参考找到最优解所需的时间；多大的种群规模比较适中，这样对于排课性价比比较高。因此，要找到一个适中的种群规模。

第二，交叉概率对排课的影响：交叉概率的大小影响到搜索最优解的收敛性，值越大收敛越快，但太大会过早收敛,不能较好的进行全局搜索。因此，要找到一个适中的交叉概率值。

第三，变异概率对排课的影响：变异概率太大,会引起遗传算法不稳定；变异概率太小,又会使全局搜索难于进行。因此，要找到一个适中的变异概率值。

第四，收敛时的遗传进化代数。

表1 种群规模对排课的影响 时间:秒

按照习惯性的做法，种群规模暂定为50、100、150，三组进行测试，每组实验记录了6次结果；显然，与我们对此问题的常识与预测一致，种群规模越小,找到一个合理解的时间越短。但种群规模太小在有限的遗传代数内无法找到最优解。从实验可看出种群规模100是一个较适中的结果。

表2 交叉概率对排课的影响 时间:秒

本文对交叉概率为0.7,0.8,0.9进行了实验。

从以上实验数据可以看出，交叉概率越大,找到一个合理解花费的时间越少，这其实是搜索过程收敛越快。但太大会过早收敛,不能较好的进行全局搜索。故本系统交叉概率pc取值0.8是一个较适中的结果。

表3 变异概率对排课的影响

变异概率太大,会引起算法不稳定。按照遗传常识，太大量的变异不仅不能进化出好的个体,反而会使得每条染色体极不稳定, 大量产生冲突的结果。变异概率太小,产生新的个体太少，全局搜索难于进行。本文对变异概率为0.01,0.02,0.04进行了实验。从实验结果可以看出不同的变异概率之间实验结果的差异。本系统变异概率Pm为0.02是一个较适中的结果。

表4 遗传迭代与收敛情况

续表4

表1-4中可以看出，初始种群规模越大，得到的最优个体的特征值也越大， 得到最优搜索解所耗费的时间也越多。初始种群为50时，遗传算法的收敛在遗传代数为320左右就基本稳定，但特征值却是420左右，这是由于初始种群的数量不够充足而停止了进化；初始种群为100 时，随着遗传代数的增加，染色体的特征值也逐步升高，在迭代360次左右时基本找到了最优解442 ，而以后的32次迭代几乎是在最优解附近浮动；初始种群150时，在表4中可以清晰地看到当遗传代数到达390次时，已经搜索到最优解451，而其后的60次迭代基本就无必要 。通过上表数据可以看出，初始种群选择100，遗传代数360次，可以搜索找到最优解 。

结论

本文较实际全面地讨论了高职院校排课问题中的主要影响因素，约束条件，求解目标；将遗传算法与排课问题相结合，解决了排课的编码问题，设计了简洁有效的适应度函数，通过排课模拟实验得到了种群规模、交叉概率、变异概率等因素对排课的影响；最后实验得到了寻求一个最优解时收敛和迭代的情况。由此，提出了用遗传算法求解排课问题的总体框架和思路，使高职院校排课问题得到了一种有效解决方案。