应用混合遗传算法求解高校排课的系统创建
应用混合遗传算法求解高校排课的系统创建 排课问题是一个多目标优化问题，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 O.Incorporating constraint propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence，1999，12（3）：241-253. [6]RUHUL SARKER，CHARLES NEWTON.A genetic algorithm for solving economic lot size scheduling problem[J].Computers and Industrial Engineering，2002， 42：189-198.