排课问题是一个多目标优化问题，S·Even等人证明了排课是一个NP完全问题。求解排课问题的方法目前主要有两类：模拟手工排课的直接启发式算法和各种改进的遗传算法。直接启发式算法的特点是简单、直接、快速，往往根据具体问题获得启发性知识，算法通用性通常较差，但能快速得到较好的解。然而，不能保证直接启发式算法求出的解是最优解。遗传算法提供了一种求解复杂优化系统的通用框架，具有很强的鲁棒性。使用遗传算法求解排课问题可可以获得全局最优解，但存在收敛速度慢的问题。实验证明，采用直接启发式算法与改进的遗传算法相结合的混合遗传算法以较快获得全局最优解。
1 排课问题描述
目前高校排课问题具有以下特征：每学期一个班级要上多门课程，每个班级上课的教室不固定，一门课程由一个或多个教师教授，一个教师可以上一门或多门课程。每门课程根据学时总数决定每周授课的次数和每次授课的节数。
为了描述方便，将每次授课涉及的元素（课程，班级列表，教师，周学时）称作课元，将一周内可供授课的时间划分为时间片，最小的时间片为一节课，将（时间片，教室）组成的有序对称为时空片。对同一个教室的时空片，若其时间片连续，则将这组时空片称为时空片簇。所以排课的任务就是要为所有的课元安排合理的时空片簇。求解排课问题就是要在满足全部硬约束条件的情况下，为所有课元按照每门课程课时总数的要求，为其分配互不相交的时空片簇，从而获得问题的可行解，即一张满意的课表。
一个解如果满足所有约束条件，则此解为最优解，但实际上并不是所有的约束都能得到满足，因此为了表示解的满意程度，引入以下两个函数。将所有约束条件依次编号为1，2，…，z，并根据这些条件的重要程度为其赋予相应的权重wi≥0（1≤i≤s）。设解为t，定义函数f（i，t）=w1x1+w2x2+…+ wsxs表示课元i在可行解t中的满意度。其中xj（1≤j≤s）表示在解t中对课元i的安排是否违反了第j个约束条件，若违反xj=0，否则xj=1。设课元集合为C，定义函数O（t）=∑i€Cf（i，t）为可行解t的满意度。对于多个可行解，如果某个解的满意度最高，则这个解就是要求解的最优解。所以取maxO（t）作为目标函数。使用启发式算法求解，就是求取尽可能使O（t）达到较大值的可行解t。
2 应用混合遗传算法求解排课问题
2.1 遗传算法
遗传算法（Genetic Algorithm，GA）是模拟自然选择和遗传的一种随机搜索算法。该算法的最初目的是研究自然系统的自适应行为，由密执安大学的JohnHolland提出。遗传算法是一种迭代算法，它模拟自然的遗传和进化，最初随机生成一组解，然后在这组解的基础上进行多次迭代，每次迭代时通过遗传和进化操作产生一组新的解，使用目标函数对生成的每个解进行评价。这一过程不断重复，直至达到某种形式上的收敛。新的一组解不但可以有选择地保留一些目标函数值高的旧解，而且可以包括一些与其它解相结合而得到的新解。在遗传算法的设计过程中，其关键在于编码和遗传操作的设计。
2.2 直接启发式算法
直接启发式算法，通常是根据各课元的约束条件赋予课元不同的优先权，然后按优先权次序来依次给各课元安排满足约束条件的时空片簇，如此反复，直到得到整张课表。直接启发式算法通常要涉及如下两个策略：优先权策略和最佳分配策略。
（1）优先权策略
为确定课元的优先权，可采用课元属性的线性组合来确定。课元具有很多属性，如：授课教师，授课班级，授课类型，周学时等。为每个属性分配权重，然后采用这些属性的线性组合来确定每个课元的优先权。由于课元的优先权值越大，说明课元的约束越多，可供选择的符合条件的时空片簇就越少，所以应该优先满足优先权大的课元。所谓优先权策略就是按照课元的优先权值由大到小，给课元安排时空片簇。
（2）最佳分配策略
设C是课元集合，TP是时空片集合。在任一时刻，设Csub为已经安排了时空片簇的课元子集，设TP（Csub）为Csub所占用的时空片集合，称为TP（Csub）系统在此时刻的格局。目标格局（即可行解）是所有课元均己被安排了时空片簇的格局。在满足约束条件的情况下，称剩余课元中如果尚有可合法安排的非目标格局为活格局，否则称为死格局。在某活格局TP（Csub）下，对于课元i（i∈C-Csub），称TP（Csub）中每一个能合法安排下i的空闲时空片簇为课元i的可行时空片簇。最佳分配策略就是通过计算可行时空片对课元i的满意度，挑选满意度最高的时空片分配给课元i。
2.3 混合遗传算法
遗传算法、直接启发式算法有其各自的优点和不足。二者结合却能取长补短、相得益彰。对于初始种群，通常是采用随机生成的方法获得，这样可以避免早熟想象。但是这种随机初始种群有可能适应度较差，需要进化很多代才能得到全局近优解，也即收敛速度过慢。采用将直接启发式算法获得的解加入随机初始种群，提高初始种群的适应度，从而克服遗传算法收敛速度慢的问题。
（1）编码
应用遗传算法求解问题首先要进行编码，编码也是遗传算法中的关键步骤。个体的染色体排列形式外，个体从搜索空间的基因型变换到解空间的表现型时的解码方法，都取决于编码方法。同时，编码方法还会影响交叉算子、变异算子等遗传算子的运算方法，并决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。目前主要有三大类编码方法，分别是二进制编码方法、浮点数编码方法、符号编码方法。
排课问题涉及多个参数，可以考虑使用多参数级联编码方法，但鉴于产生的编码较复杂且不便于后期的选择变异操作，因此，将排课问题的多个参数进行简化，将多个参数简化为上述的课元和时空片。排课问题简化为将课元合理分配到时空片的问题。设一周有n个时间片，用T（1≤i≤n）表示，设有m个教室，用P（1≤j≤m）表示，则共有n×m个时空片，用TP（1≤i≤n，1≤j≤m）表示对应的时空片中分配的课元，若TP=0表示该时空片未被占用。可以采用二维时空数组来表示排课问题的个体染色体，如表1。设需安排的课程数为小于1024门，则一个数组元素的长度可用8位表示，则一个染色体的编码长度为8×n×m位。
（2）解码
为了从染色体个体推出问题的解，需要设计三个数组，分别是课元信息表（课程编号班级编号教师编号），课程信息表（课程编号上课周数周次数时间片1时间片2时间片3时间片4）。通过染色体个体很容易获得课程信息表，再使用课元信息表，很容易获得班级课程安排表和教师课程安排表。
（3）适应度函数
群体中各个个体在优化计算中有可能达到或接近最优解或有助于找到最优解的优良程度使用适应度函数来度量。适应度较低的个体遗传到下一代的概率相对较小，适应度较高的个体遗传到下一代的概率相对较大。而适应度函数是通过目标函数获得的。
排课问题的目标函数是maxO（t），其中O（t）即为所需的适应度函数，即可行解t的满意程度。要计算个体的适应度，首先将个体的染色体编码转换为课程安排表，通过课程安排表和教师意愿表（教师编号课程编号教师意愿）可以很容易确定各种软约束是否被满足，从而计算出可行解t的不满意程度。
（4）选择
选择运算确定从父代群体中选取哪些个体遗传到下一代群体。选择运算是建立在对个体的适应度进行评价的基础之上，其主要目的是为了避免基因缺失、提高全局收敛性和计算效率。常用的选择算子有比例选择、最优保存策略、确定式采样选择等。
为使下一代获得较优基因，并且避免陷入局部最优，采用最优保存策略和比例选择相结合的方法。对父代个体的适应度按从小到大进行排序，将前10%的个体直接选入下一代，用于替换交叉、变异等遗传操作后所产生的适应度最低的个体；其余90%的个体按适应度大小按比例进行选择复制。
（5）交叉
常用的交叉算子有单点交叉、多点交叉、均匀交叉等，根据积木块假设，单点交叉能保证具有良好的组块不致被拆开。根据单点交叉的思想，在时空数组中随机选择一块，将配对个体中该块中的各元素进行交换，如图一和图二所示。个体A和个体B交换随机选中的块A和块B中的课元。
交叉后形成的新个体在教师、教室和时间方面不会形成冲突，但可能存在课元冲突，例如某些课元安排多了，而某些课元安排少了。课元冲突的消解只需对新个体中块A和块B中的课元进行检查，如果课元多排了，则删除块外多余的课元；如果课元少排了，则为少排的课元重新安排新的时空片。
（6）变异
变异虽然发生的概率较小，但变异可以改变遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。这里采用基本位变异，在时空数组中随机选择若干个课元重新安排。通过对解空间的轻微扰动，有利于搜索空间渐渐向全局最优范围靠拢。
3 算法测试
我们采用了c++语言实现了混合遗传排课算法和单纯遗传排课算法，并采用了西华师范大学计算机学院2012年第一期和第二期的课表数据进行了测试和比较。实验表明使用混合遗传算法排课收敛速度远远优于单纯的遗传算法，在教师满意度方面也以单纯遗传算法排课具有更高的满意度。
4 结语
我们将直接启发式算法和遗传算法相结合形成了一种简单易行的混合遗传算法，克服了直接启发式算法不能获取全局最优（近优）解和遗传算法收敛速度慢的问题，能够以较快的速度收敛到全局最优（近优）解上。在遗传算法的编码方面，提出了二维时空数组编码。由于排课问题的复杂性，以往采用的编码方法过于复杂，造成交叉和变异产生大量冲突，消解这些冲突将耗费大量计算时间。而二维时空数组编码方式简单直观，而且在交叉和变异时仅产生少量的课元冲突，用很短的时间简单的方法就可以消解，从而大大提高了求解速度。利用此算法进行实际排课时，求解速度较快，所获得的排课方案满意度较高，获得更好的效果。
参考文献：
[1]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.
[2]谭保华，彭伟.基于蚁群遗传算法的高校排课系统[J].计算机仿真，2008，25（12）：294-297.
[3]陈卫东，李吉桂.基于拟人策略的高校排课系统[J].计算机科学，2003，30（12）：172-175.
[4]滕姿，邓辉文.基于蚁群遗传算法的排课系统的设计与实现[J].计算机应用，2007，27（12）：199-204.
[5]SAFAAI D，SIGERU orating constraint propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence，1999，12（3）：241-253.
.Computers and Industrial Engineering，2002，42：189-198.
作者简介：舒兰英（1973-），女，四川新都人，讲师，硕士，主要研究方向：人工智能、软件工程。
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。
