遗传-蚁群混合算法解决高校排课问题的研究

2013-02-26叶靖喻昕

大众科技 2013年10期

叶靖喻昕

（广西大学计算机与电子信息学院，广西南宁 530004）

排课是教务部门的常务性工作，现在许多高校仍然采取计算机辅助人工排课的方式编排课程表。最近十几年，我国的高等教育事业迅猛发展，但教学资源却相对有限，很多学校都面临着教室和教师资源紧张的问题，在这种现状下，排课工作的难度和复杂度都增加了。目前的排课方式，已经越来越不易于充分利用已有的资源解决变化着的需求，而且在效率方面的不足也有待提高[1]。因此，研究高效、灵活的自动排课系统，极具现实意义。

排课问题作为时间表问题(Timetable Problems，TTPs)，已被公认是NP难解问题，作为组合优化问题的一个分支，它是国内外许多学者研究的热点。智能算法是目前求解复杂优化问题的一类有效方法，它在求解问题时不需要或者只需要很少的关于问题的先验信息。这类算法具有很强的鲁棒性，而且在多数情况下都能求得比较满意的解。常用的方法有：遗传算法、蚁群算法、模拟退火算法、禁忌搜索等。这些方法都在排课问题中有过应用，但每种方法在实际应用中又各有优劣。本文提出一种遗传-蚁群混合算法，将遗传算法与蚁群算法融合，依靠遗传算法生成信息素分布，利用蚁群算法求精确解，通过优势互补来获得良好的优化性能与时间性能。

1 排课问题描述

排课问题主要涉及的因素有：教师、班级、课程、教室、时段等，要求课程表的安排在这几个方面不能发生冲突[2]。为了避免冲突，引入了“约束条件”的概念。排课过程的约束条件可分为“硬约束”和“软约束”两类。

硬约束是衡量排课方案可行与否的标准，是排课中必须满足的。硬约束包括：

（1）同一教师在同一时段只能安排在一个教室授课；

（2）同一个班级在同一时段只能在一个教室上课；

（3）同一教室在同一时段只能安排一门课程；

（4）一门课程被安排的教室座位数应大于或等于该门课程上课人数。

软约束是衡量排课方案优劣的标尺，排课过程中满足更佳，不能满足也无妨，满足与否往往与排课实际情况相关。软约束包括：

（1）尽量为专业课程或较难掌握的课程安排上课效果好的时间段；

（2）同一个班级一周内某门课程有多次，则几次课在时间上必须有一定的间隔；

（3）体育课应安排在下午或者上午的第二大节，体育课后面要避免安排讲授课；

（4）实验课等实践课程应排在下午或晚上。

2 用遗传-蚁群混合算法解决排课问题

2.1 遗传算法

遗传算法（Genetic Algorithm，GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一类借鉴生物界的适者生存、优胜劣汰进化规律演化而来的随机化搜索方法。它是由美国Michigan大学的John Holland教授1975年首先提出。

遗传算法是从随机产生的一个种群开始的，这个种群代表了问题可能潜在的解集，每个种群由经过编码的N个个体组成，每个个体实际是染色体带有特征的实体。在每一代，根据个体适应度的大小挑选个体，适应度大的则被认为是优良的个体，继续进化，并借助遗传学中的遗传算子进行交叉、变异，产生出代表新解集的种群。这一过程就像自然界的物种进化，子代比父代更适应环境。经过逐代演化，最终可以产生问题的近似最优解。

遗传算法应用到排课中的主要演算步骤[3]如下：

（1）随机产生一定数目的初始种群；

（2）对个体的适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第（3）步；

（3）依据适应度选择再生个体；

（4）按照一定的交叉概率和交叉方法生成新的个体；

（5）按照一定的变异概率和变异方法生成新的个体；

（6）由交叉和变异产生新一代的种群，然后返回第（2）步。

2.1.1 编码

常用的编码方法有二进制编码和浮点数编码。为增强程序的可操作性，本文采用十进制编码。每条染色体代表一位教师的课表，其结构如下：

教师ID 班级ID 课程ID 教室上课时间

例如：数信学院的张三老师要给林学院林学专业 2010级1班的同学上高等数学这门课，张三老师的ID为“3692”，林学院林学专业2010级1班ID为“1802101”，高等数学这门课程的ID为“110075”，经选择，选定1号楼2层第5间教室，排定的上课时间为星期二第一大节，则生成的染色体为：“3692 1802101 110075 010205 21”。

2.1.2 适应度函数

遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的。在本系统中，适应度函数由以下评价函数构成：节次优度a、日组合优度b、组合可行性c、分布优化度d、资源优化度e。单门课程的适应度函数为：

F=(a*x+b*y)*c*d*e

其中，x和y分别表示节次优度和日组合优度所占的权重，x+y=1，适应度函数的最大值为1。

全局课表的适应度函数为：

其中，n是种群中课程的门数。

2.1.3 种群操作

（1）初始化种群

在本文中，采取以教师课表作为染色体。根据教学计划中的安排，教师、班级及课程之间的对应关系是已经确定的，首先对这三者的ID进行编码并组合，然后安排上课时间，最后安排上课教室。

（2）选择操作

选择操作的目的，是为了从当前群体中选出优良的个体，使它们有机会作为父代繁殖下一代。个体适应度越高，其被选择的机会就越多。选择操作实现的方法有很多，如适应度比例方法、最佳个体保存方法、期望值方法等。本文采用期望值方法。

在适应度比例方法中，当个体数不太多时，依据产生的随机数有可能会出现不正确地反映个体适应度的选择，即存在统计误差。为克服这种误差，期望值方法用了如下思想：

①计算群体中每个个体在下一代生存的期望数目：

M=fi/∑fi/n

②若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减去 0.5；若不参与配对和交叉，则该个体的生存期望数目减去1。

③在上一步的两种情况中，若一个个体的期望值小于零时，则该个体不参与选择。

（3）交叉操作

交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体。根据前面选择操作的结果，选取两条染色体作为父代，再取一随机值r（0＜r＜1）与系统预设的交叉概率PC比较，若r＜PC，就执行交叉操作，否则不执行。

本文选用一点交叉方式。一点交叉又叫简单交叉，具体操作是：在个体串中设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生产两个新个体。本文中的交叉点设置在第17和第18个基因座之间。交叉时，该交叉点后的两个个体的部分码串互相交换，即交换两个染色体的教室编码和上课时间编码，这样既不会影响到每位教师所教授的课程，也不会造成教师课表内含其他教师的教授课程或每代演化后染色体结构不合理等问题[4]。

（4）变异操作

变异操作的目的在于挖掘群体中个体的多样性，克服有可能限于局部解的弊病。变异操作与交叉操作相似，在变异时先产生一个随机值 r（0＜r＜1），与变异概率 Pm比较，若 r＜Pm，则执行变异操作，否则不执行。

基于排课问题的特性，本文采用基本位变异，即随机选择一个染色体的两个或多个基因座，将基因值互换。例如，有一染色体编码为：

3692 1802101 110075 010205 21

它表示星期二的第一大节有“高等数学”这门课，执行变异操作后，该染色体变成：

3692 1802101 110075 010205 41

“高等数学”这门课调整到星期四的第一大节进行，这样染色体的适应度就得到了极大的提高。

在变异操作中，Pm不能取得太大，如果 Pm＞0.5，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特征和搜索能力也不复存在了[5]。

2.2 蚁群算法

蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo 1992年在其博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

昆虫学家经过长期的观察研究发现：蚂蚁在寻找食物时，会在其通过的路径上释放一种特殊的分泌物——信息素，并通过此分泌物来寻找路径。当它们行进到一个未走过的路口时，会随机选择一条路径进行前行，同时释放与路径长度有关的信息素。蚂蚁走过的路径越长，释放的信息量越小。后面的蚂蚁会根据路径上信息量的大小来选择路径，信息量较大的路径被选择的概率也越大，这就形成了一个正反馈机制。随着时间的推移，最优路径上的信息量越来越大，而其他路径上的信息量则逐渐减弱，最终蚁群会以此找出最优路径。蚁群对环境还有很强的适应能力，它们在行进途中遇到障碍物时，也能很快地重新找到最优路径。蚁群在觅食的过程中，虽然单个蚂蚁的能力有限，但整个蚁群内部依靠信息素的作用交换着路径信息，使得整个蚁群具有很高的自组织性，并最终依靠集体的力量找出最优路径。

蚁群算法只能解决用图结构描述的问题。因此要将蚁群算法应用到排课问题中，首先要将排课问题用图结构G来描述：

其中：N ——图的顶点集合；

S ——边的集合；

C ——边集有关的权值的集合。

排课工作是根据教学计划来安排的，在教学计划中，已经确定了课程、教师、班级之间的匹配关系，排课人员需要做的就是为其合理安排时间和教室。因此，课程、教师、班级、时段、教室五个元素之间的匹配可转化为＜课程、教师、班级＞关系与＜时间、教室＞关系，排课问题也就转化为解决＜课程、教师、班级＞与＜时间、教室＞所构成的二分图的最大匹配问题。

（1）二分图的顶点集

定义＜课程、教师、班级＞关系为 RLSC，RLSC= L×S×C，RLSC中所有元组组成的集合为GLSC，为二分图左侧的顶点集合；定义＜时间、教室＞关系为 RTR，RTR= T×R，RTR中所有元组组成的集合为GTR，为二分图右侧的顶点集合；|GTR|＞＞|GLSC|。

（2）二分图的边集

在安排教室的时候，要满足两个条件：一是要满足课程对教室类型的要求，二是要满足班级人数对教室容量的要求。因此，GLSC不是满映射于 GTR，只有满足上述两个条件的节点才可进行连接。

（3）二分图中边的权值

对每条边上的权值，可依据具体课程的时间期望度来构造。例如，较难掌握的课程（如高等数学）最好安排在上午第一大节，那么GLSC中所有的高等数学课程与GTR中时间段为上午第一大节的所有节点连线的边的权值要尽量小。通过对权值的设置，才能让蚂蚁排出较高质量的课程。

为了克服基本蚁群算法的不足，结合排课问题的特点，本文采用改进的蚁群算法——最大-最小蚂蚁系统（Max-Min Ant System, MMAS）。改进的蚁群算法求解排课问题的步骤如下：

（1）初始化参数，nc=0，每条边的信息量ij(0)=c；

（2）把m只蚂蚁放在二分图左侧的顶点集合GLSC中，为每只蚂蚁建立禁忌表tabuk以及允许选择的RTR表allowedk；

（3）计算蚂蚁k在当前点i（i点位于集合GLSC中）的转移概率，通过计算结果选择下一步将转移到的位置j点（j点位于集合GTR中）；

（4）把j点从allowedk表中删除，同时把j点放入tabuk表中；

（5）判断集合GLSC中是否还有节点未与集合GTR中节点匹配，若有，i加1，返回第（3）步，反之，表示蚂蚁k已完成一次周游，执行下一步；

（6）若k＜m，表明还有蚂蚁未完成周游，k加1，返回第（3）步，否则执行下一步；

（7）比较m只蚂蚁周游的代价大小，找出最小代价路径的蚂蚁；

（8）对对优路径上的信息素进行更新；

（9）判断nc是否达到最大迭代次数，若是，终止循环，求得最优路线，否则nc加1，返回第（2）步。

2.3 遗传-蚁群混合算法

遗传算法、蚁群算法作为两大仿生优化算法，有其各自的优点和不足。遗传算法具有在大范围内快速全局搜索的能力，但对系统中的反馈信息利用不够，往往求解到一定范围时就开始做大量无用的冗余迭代，导致求精确解效率降低。蚁群算法原理是一种正反馈机制，具有更好的分布并行计算能力以及全局优化能力，但在搜索初期由于信息素的匮乏，导致求解速度过慢。

因此本文将遗传算法与蚁群算法融合，首先利用遗传算法生成信息素分布，再利用蚁群算法求精确解，通过两者的优势互补，来获得良好的优化性能和时间性能。

在本文的遗传-蚁群混合算法中，设置遗传算法的终止条件为：算法运行10次，每次迭代100代，取得的最优解作为蚁群算法的初始解；或者运算过程中，运算结果的差值小于0.005的情况连续出现两次，则终止运算，直接进入蚁群算法。设置蚁群算法的终止条件为：最大迭代次数取值 100，当算法达到最大迭代次数时，就停止运算。

遗传-蚁群混合算法求解排课问题的步骤如下：

（1）遗传算法参数初始化；

（2）随机生成初始种群P(0)，设置迭代次数nc=0；

（3）计算各个体的适应度函数值；

（4）选择、交叉、变异操作；

（5）进化代数nc=nc+l；

（6）判断是否满足结束条件，满足，执行下一步，不满足，返回第（3）步；

（7）把遗传算法生成的较优解转化为蚁群算法的初始信息素；

（8）蚁群算法参数初始化，迭代次数gen=0；

（9）把m只蚂蚁放在二分图左侧的顶点集合GLSC中；

（10）对每只蚂蚁根据转移概率和排课约束条件进行路径选择；

（11）记录m条路线，完成一次迭代；