遗传算法在排课问题中的应用

摘　要：遗传算法作为一种启发式搜索方法已经被越来越多地应用到了各个领域，本文主要描述了如何将遗传算法运用到排课问题中，从而实现智能和自动的排课功能。本文首先从具体的排课问题入手，分析各种约束条件，抽象出数学模型，接着论述了如何将遗传算法运用到排课问题中，同时针对传统的遗传算法进行适当的改进，以便能够提高算法的效率，获得全局近似最优解。

关键词：遗传算法；排课
1. 引言
　　排课问题[1,2]就其实质而言，是一个有约束，非线性，多目标优化的时空排列组合问题。该类问题由于受到各种客观条件的制约，因此很难采用纯数学，或单一的算法，来寻找到一组较优的解。遗传算法作为一种启发式的搜索方法，由于其具有智能性和并行性等特点[3]，比较适合用来求解排课问题。遗传算法本身并不关注业务，它通过把具体问题的解抽象成数学模型，并通过适应度值来判断解的优劣，同时以优胜劣汰的方式，启发式地进行选择，交叉，变异等操作，并反复迭代，最终寻找到全局近似最优解。
2. 遗传算法简述
　　遗传算法（Genetic Algorithms,GA）是通过模拟自然界生物优胜劣汰的遗传进化规律演化而来的一种启发式搜索方法。美国Michigan大学的John Holland教授于1975年首先提出此算法，该算法的基本原理是：首先将具体问题的解抽象成数学模型，通常是使用一串二进制数字组成的字符串（染色体）来表示问题的解；接着随机地生成一组可能的解集（种群），解集中的每一个解，即是一个带有染色体特征的个体，然后根据问题来确定适应度函数（评价解的优劣性），根据适应度值对个体进行选择操作，随后再模拟生物基因的交叉和变异等操作，生成下一代群体，经过若干次的循环迭代以后，最终寻找到适应度最高的全局近似最优解[4,5]。
3. 排课问题的数学模型
3.1排课问题的约束条件
　　排课问题实质上是基于班级，教师，教室以及时间等元素的排列组合问题，由于受到实际情况的约束，随机产生的组合方案往往会存在大量的冲突，导致这样的编排结果是比较拙劣的，甚至是无法实施的。
　　通常情况下，我们可以把排课的约束条件分为两类：硬约束和软约束。
　　硬约束主要包含如下几点：
　　1）教师在同一时间只能上一门课程；
　　2）一间教室在同一时间只能有一个班级上课；
　　3）教室的座位数量不能小于班级的学生数量。
　　软约束可能包含如下几点：
　　1）教师对上课时间的偏好；
　　2）班级课表在时间安排上尽可能分布均匀；
　　3）特殊课程对上课时段，教室等的特别需求。
　　硬约束是一个排课方案必须要满足的条件，违反硬约束的编排是无效的，不可行的；而软约束是应该尽量满足的，是评价一个排课方案优劣的标准。
3.2数学模型的建立
　　通常情况下，教学以一个星期作为单位，一个学期的课程仅仅是一个星期课程的重复，因此，一个星期的课表编排可以作为一个学期的排课方案。
　　一个排课方案通常由班级，教师，教室，时间等元素构成，我们把一间教室的某一个上课时段称之为时空单元。假设某学校有m间教室，每周上课n天，每天有p个授课时段（比如上下午和晚上各上一节课，那么一天的授课时段为3个），则该学校每周共有m×n×p个时空单元；为了方便后续的操作，我们可以将这些时空单元按照一定的顺序进行排列，例如将同一个教室的时空单元放在一起，然后再根据星期，上下午等时段进一步排序，这样就构成了一个有序的时空单元数组，可以记为：
　　 T1 , T2 , T3 ,  ……  Tm×n×p  ;
　　在做排课操作前，应该按照教学计划提前设定好每个班级需要教授的所有课程，每门课程每周的上课次数，以及授课教师人选。如果我们用数据库中的一张表（表1）来保存这些设置的话，那么该课次表的主要字段包括：表主键，班级ID，课程ID，教师ID；如果某个班有某门课一周要上3次，那么在不考虑表主键的情况下，会出现3条重复的记录。该课次表中的所有记录即是所有需要被安排的课程，我们不妨把每一条记录看成是一个课程单元，那么这张表中的所有记录便是一个课程单元的集合。我们把所有课程单元记作：
　　    C1 , C2 , C3 ,  ……  Ck  ;
　　为一次具体的课程进行编排，即是把一个课程单元Ci分配给一个时空单元Tj （表2），那么一个排课方案实质上就是为所有的课程单元各分配一个时空单元。
　　一般来讲，课程单元的数量应该不大于时空单元的数量，即 k <= m×n×p ，我们可以在原先的课程单元集合中添加一些空白课程单元，使得课程单元的数量和时空单元的数量相同，新的课程单元集合可以记为：
　　C1 , C2 , C3 ,  ……  Cm×n×p  ;
接着我们很容易就可以想到，一个排课方案其实就是对所有课程单元进行一次全排列。如果一个空白课程单元和一个时空单元相对应，也就是说在这个时段此教室没有班级上课。
　　我们采用罚值的方法来评价解的优劣性，当一个排列违反了若干约束，我们就给这个排课方案添加罚值，罚值越高，排课方案越差，罚值是0的为最优。

课次表ID班级ID课程ID教师ID表1  课次表主要字段

教室ID上课时段课次表ID表2 时空单元和课程单元的组合即是一次课程安排
4. 遗传算法在排课问题中的应用与改进
　　遗传算法的基本流程如图1：
　　
　　
　　图1 遗传算法基本流程图

4.1编码
　　遗传算法需要将问题的解编码成一串字符串，字符串就类似于生物的染色体。我们可以用上述提到的课次表的主键来构建染色体编码。首先我们设定该课次表的主键为固定长度，然后假定目前已存在一个排课方案，那么它一定是课程单元的一个排列，我们就按照该排列的顺序，将课次表的主键串联起来，则拼接成的字符串就是排课的编码。在这样的编码规则下，课次表主键和课程单元是一一对应的，在进行算法的交叉或变异操作时，主键是最小的基因片段，不可再分割。
4.2产生初始种群
　　遗传算法的操作总是从初始种群开始的，初始种群的规模一般在50-100之间，初始种群在解空间上分布得越是均匀，搜索空间就越大，越有利于寻找到全局最优解。通常情况下初始种群是随机产生的，我们可以在此做一些改进：每随机产生一个个体，我们就用它来和已经存在的个体进行比较，如果有连续若干个课程单元的排列顺序和已存在的相同，我们就抛弃这个个体，重新再产生新的个体，这样就可以保证初始群体中没有相似的个体。
　　另外，根据上述讨论的数学模型，通过对课程单元进行排列产生的排课方案，已经满足了一间教室在同一时间只能有一个班级上课的硬 约束，但是仍然可能存在教室容量不够大，或者一名教师在同一时间不止上一门课的冲突，因此我们略微调整一下遗传算法的流程，在产生初始种群后，直接进行变异的操作，并且采用定点突变的方法，将产生硬冲突的课程单元直接和一个随机的空白课程单元进行交换，这样可以减少个体的硬冲突，提高个体的适应度。
4.3适应度评价
    我们采用罚值的办法来评价个体的适应度，我们可以对排课问题的硬约束和软约束分别设定权值，由于硬约束是必须要满足的约束条件，相对软约束来讲其权值就比较大。每个个体在进行适应度评价时必须对所有约束逐一进行检查，将不满足约束的权值相加，权值之和即为罚值，罚值越高，适应度越差，罚值为0，则表明该个体满足所有约束条件，是全局近似最优解。
4.4选择
    遗传算法中最常用的选择方法是比例选择法，如果在某代种群中个体适应度差距比较大，适应度高的个体很可能被多次选中，适应度低的则很可能提前被淘汰，这样就会降低群体的个体多样性，使得算法提前收敛于局部最优解。竞技选择法(Tournament Selection)能较好地解决此类问题：该方法首先从种群中随机选取一定数量的个体，形成一个新的群体，然后在这新的群体中确定性地选择适应度最高的个体进入下一代种群，被选中的个体返回父代种群中，继续重复上述步骤，直至生成子代种群。但是竞技选择法存在一个问题，即适应度最小的几个个体可能永远不会有被选中的机会，例如：从父代种群中先随机选择10个个体形成一个新的群体，然后确定性地从中选择适应度最大的个体进入下代种群，则该父代种群中适应度排最后的9个个体，永远也不可能被选中。因此我们改进竞技选择法，颠倒其操作步骤，即：首先从父群体中采用比例选择法（如轮盘法）选择一定数量的、并且无重复的个体形成一个新的群体，然后从该群体中随机选择一个个体进入下一代种群，然后将被选中的个体放回父代种群，重复上述操作，直至生成下一代种群。该改进型的竞技选择法同样能够选择较优的个体进入下一代，而且适应度小的个体也有被选中的可能，同时也能防止适应度特大的个体被反复多次选中。
4.5交叉
    交叉操作一般是通过随机产生的一个交叉点，将2个父个体的染色体分成2段基因片段，然后2个父个体交换对应的基因片段，形成2个子个体。但是此方法无法适用于上述的数学模型中，因为交换后可能会产生重复的排课，因此我们采用单点的，对称的，大片段基因保留，小片段基因保序的交叉方法[6]。下面我们举例说明，假定将要进行交叉操作的父个体A的染色体为：123456789，父个体B的染色体为：987654321，随机产生的交叉点位置为6，则父个体A被分成2个基因片段：123456789，父个体B被交叉点的对称点分割成：987654321：接着将这2个个体中的较长的基因片段保留，较短的基因片段进行重新排序，排列的顺序是参照它们在另一个个体中的顺序；交叉后产生的2个子个体分别为：123456987；789654321。
4.6变异
　　变异操作采用定点突变+随机突变的组合变异法，即：对于违反硬约束的课程单元，强制性地令其与一个随机的空白课程单元对换，在定点突变过后，再根据变异概率随机地选择2个课程单元进行交换。
4.7遗传算法的终止条件
　　遗传算法通常的迭代次数为200至500次，如果在到达迭代次数之前提前出现了罚值为0的个体，则算法提前结束，该个体即为全局近似最优解；如果到达了迭代次数，则取该代群体中罚值最小的个体作为问题的解。
5. 总结
　　以上讨论的遗传算法可以满足通常的排课需求，可以按照上述算法开发出一套排课系统。如果能够根据实际经验确定初始种群的数量，算法迭代的次数，以及在上述的各个操作步骤中加入其它的启发式算法，则可以改善算法的运行时间，提升算法的效率。
参考文献：
[1] 辛延军. 课表问题及其求解策略的研究: 天津大学硕士学位论文,1996.
[2] Gotlieb C. The Construction of Class—Teacher Time—Tables . Proc .62,1963.
[3] 孙艳丰,戴春荣. 几种随机搜索算法的比较研究[J]. 系统工程和电子技术, 1998, 2：43-47.
[4] 陈国良,等. 遗传算法及其应用[M]. 北京:人民邮电出版社,1996.
[5] 周明,孙树栋. 遗传算法原理及应用[M]. 北京:国防工业出版社,1999.
[6] 梁艳春,等.遗传算法求解旅行商问题时的基因片断保序[J].系统工程与实践.2000(7).