基于遗传算法解决排课问题的探索

马传志，吕志武，曲思龙，周 虹，王 蕊，明艳春

（佳木斯大学，黑龙江 佳木斯 154007）

在学校的教务管理工作中，排课工作是一项繁重而复杂的工作。排课工作涉及的因素众多，波及面广，这一工作的结果直接影响教学工作的有序进行。作为一个涉及多因素的优化组合问题，学校的排课工作已经被证明是一个NP完全类问题，利用常规算法进行求解会面临诸多问题，很难有效求解，常常引起大量的冲突而使得排课无法进行下去。近年来，这一问题引起了很多人的重视，进行了多种不同方式的尝试，取得了一定的成果。遗传算法作为一种解决NP完全类问题的有效算法，可以被应用于排课问题中。

1 排课问题的约束条件

排课问题涉及的因素比较多，包括任课教师、授课班级、所学课程、学习教室、上课时间等，众多的因素必须满足一定的条件进行组合才是合理的，所排出的课表才是可行的，否则将导致教学任务无法有效完成，影响教学工作正常进行。为了研究算法，首先要将排课问题进行有效表示，分析在排课过程中要满足的各种条件。

1.1 数学模型表示

分析了排课问题所涉及的因素后，可将一个排课问题进行如下模型表示：

任课教师集：P＝｛p1，p2，p3，…，pn｝

所学课程集：L＝｛l1，l2，l3，…，ln｝

授课班级集：C＝｛c1，c2，c3，…，cn｝

学习教室集：R＝｛r1，r2，r3，…，rn｝

上课时间集：T＝｛t1，t2，t3，…，tn｝

其中，任课教师、授课班级和所学课程可以组合为一个授课安排，学习教室和上课时间可以组合为一个教室时间安排，组合简化后，排课问题就演变成为一个授课安排寻找合理的教室时间安排的任务。

在此基础上，可以进一步分析排课问题过程中要满足的条件，经过分类简化，条件可以分为两类：硬约束条件和软约束条件。

1.2 硬约束条件

硬约束条件是在排课过程中必须满足的条件，硬约束条件是无法改变的客观条件，只有在解决这类条件的基础上，排课工作才具有实际意义，才是一个可行的结果。一般来说，硬约束条件有如下几种：

（1）一名任课教师在同一时间只能上一门课。

（2）一个上课班级在同一时间只能上一门课。

（3）一个学习教室在同一时间只能上一门课。

1.3 软约束条件

软约束条件是相对于硬约束条件而言的，这类条件不是必须满足，不具有强制性，在可能的情况之下尽量满足这类条件会使排课的效果得到改善，有利于教学工作顺利进行。而且这类条件对不同的课程、不同情况会有变化，不完全固定。常见的软约束条件有如下几种：

（1）一门课程的多次课程应尽量分散开，不要连续。

（2）学生的所有课程不应过分集中，尽量避免某天空课的情况。

（3）同一教师的多次课程尽量不连续安排，最好隔天安排。

（4）主要课程应尽量安排在上午。

（5）晚间尽量不安排课程。

（6）周六、周日尽量不安排课程。

（7）保证教室的利用率。

（8）某些课程对教室的要求，如尽量为多媒体等条件。

有些软约束条件在某一特定条件下可能要求必须满足，这时可转化为硬约束条件来进行排课。

2 算法设计

有了上述模型表示和约束条件后，可在此基础上进行算法设计。本算法以基本遗传算法为基础，进行相应改进和参数设置，适应于排课问题的求解。

2.1 遗传算法基本流程（如图1所示）

图1 遗传算法基本流程

2.2 排课问题染色体编码

综合分析排课问题中所涉及的各种因素，其染色体编码方案如图2所示：

图2 排课问题染色体编码方案

2.3 设置遗传参数

遗传参数是遗传过程进行下去的一个关键，在运行之前设置。参数的设置对遗传迭代次数和收敛都有影响。其中变异概率应取较小的值，否则，会对遗传进程产生不利影响，使得运算效率下降。

2.4 生成初始种群

初始种群是进行遗传迭代的基础，后续遗传过程在此种群上进行。种群规模不宜过大。

2.5 选择操作

选择操作以适应度的值为基本参考，所以适应度的计算较为重要。在排课问题具体操作时，适应度值的高低与被选中的概率直接对应。

2.6 交叉操作

在基本遗传算法中，原则上可以在任意位置进行交叉操作。本排课算法中，考虑到实际情况，对数据进行授课安排和教室时间安排的分解，交叉时不破坏此分解单位，以此来保证交叉操作的实际意义。在此基础上，两个染色体进交叉操作，保持课表有效性。

2.7 变异操作

变异操作是保持遗传多样性的一种重要手段，本排课算法设计过程中以变异操作来产生新个体。考虑到课表编排工作的特殊性，照顾到课表本身的特点，变异操作在基因内部进行，不越界，使得新生个体的合理性得到了有效保证。另外，为避免对求解产生不利影响，变异操作以较低概率进行。

3 实例

在实验中采用了我校新生的数据信息，种群规模为100，交叉概率采用0.4，变异概率采用0.01，排课取得了满意的结果，无冲突，满足了所设定的约束条件。实际排的结果如图3所示。

图3 实际排课结果

4 总结

根据排课问题本身的特点，采用所设计的遗传算法进行排课取得了较好的效果。排课问题是一个复杂的NP完全性问题，因素多，数据量大，在冲突解决过程中需要的知识较多，本文中的算法对实际问题做了部分简化，仍有待改进之处，在今后的研究中将继续完善。

［1］ 陈静.自动排课系统算法的分析与设计［J］.科技情报开发与经济，2007，17（34）：199－201.

［2］ 王小平，曹立明.遗传算法—理论、应用与软件实现［M］.西安：西安交通大学出版社，2002.

［3］ 许秀林，胡克瑾.基于约束满足和遗传算法的排课算法基于约束满足和遗传算法的排课算法［J］.计算机工程，2010，36（14）：281－284.

［4］ 苏仰娜.基于遗传算法的优化排课系统［J］.河南大学学报，2005，35（1）：75－78.

［5］ 陈皓，崔杜武，崔颖安，等.族群进化算法［J］.软件学报，2010，21（5）：978－990.