基于改进遗传算法的排课系统

江民斌

一、引言

时间表(Timetabling)问题是一类优化组合受限多元资源的调度问题，其拥有非常广泛的应用领域，像医院病房调度、航班时刻表、列城市公路运营、车时刻表等等。到目前已经证明该类问题是一种NP完全问题，而NP完全问题不存在时间复杂度为多项式时间的算法。本文中的编排学校课程表是解决时间表问题的一个应用.

解决这类问题早期主要是以临界资源分配算法为主，后来美国Michigan大学学者Holland提出了遗传算法，遗传算法是一种借鉴了自然界遗传和选择机制的搜索算法，具有鲁棒性强、通用、简单等的优点。但遗传算法本身存在算法初期早熟现象、算法后期进化缓慢的现象，本文利用加权可控方法改进遗传算子,从而有效地克服了这一缺点。

二、遗传算法及编码

遗传算法是一种搜索最优解或局部最优解的方法，这种方法的实现是通过模拟自然的进化过程得来的。它结合了在生物科学中遗传的概念与计算机科学中的算法概念，由潜在的问题可能的解集的某个种群开始，以不断进化的方式持续地迭代种群, 逐渐地产生出互不相同的各种基因组合，不同的问题解，最终搜索出我们所期望问题的最优解或近似最优解。简单遗传算法只使用变异算子、交叉算子、选择算子这三个基本遗传算子，其操作过程可以说相当简单，但它们提供给了遗传算法一个很基本很简单的框架。定义：SGA=(E，M，P，C，Ψ，T,Φ，r)，式中，E为个体适应函数，M为群体的大小，通常取 20~100，P为初始种群，C为个体编码，可以用固定长度二进制符号串来进行编码，Ψ为使用基本位变异算子，T为终止条件，通常终止进化迭代数为100~500，Φ为使用比例选择算子，r为使用单点交叉算子。

首先是编码，使得能在此基础上可适用未来的遗传演化操作，本文中采用十进制数制编码方法。我们设定每条染色体代表每位任课老师的课表，基本的染色体编码为:任课老师编码+上课班级编码+选修课程编码+授课教室编码十时间安排。例：某任课老师的身份编号为1347要讲授“数据结构”这一门专业基础课程，“数据结构”课程的编号为8217，每一周的课时量大小为4，所授班级的编号设若为01801、01802，首先我们可以随机地产生上课时间，再随机选择合适的教室，这时我们就可以利用预定的组合规则生成染色体如:“134701801018028217024012241“，这里的后9位代表上课时间（星期二的34节和星期四的12节）。

三、适应度函数与种群初始化

遗传算法在进化中要是需要选取下一代种群个体，它是是以个体的适应度数值的大小为依据来进行的。因此一个适应函数的设计，其好坏最终结果，而其可能具体表现为遗传算法的收敛缓慢，不能在较短时间结束，失去了实际意义，另外也可能会导致这种算不并不能找到最优解甚至不能逼近近似最优解。本文中，设计适应函数的主要考虑是采用赋相应权值，最终对冲突进行加权求和来实现，比如：我们设计以权值Wi代表的是第i条规则的重要程度，若是某染色体违反了某条规则i，则将其值Pi置为1(若没有违反规则i，则Pi值为0)，其受到的惩罚值为Wi*Pi，对染色体中存在的冲突进行加权求和并加上1后，再求其倒数，即适应度函数可以设计为，染色体的加权总和与1相加的倒数值。

这样一来，我们得到的染色体适应函数数值越大，表示该染色体拥有越好的教室和授课时段，因此我们将其看成一个好的个体，使其在下一代的演化中的生存可能性变得更大。

为了给后面的遗传操作（选择、交叉、变异）提供进化的进化的基础，所以首先需要初始化种群得到最初起始代。在本文中，由于是采每次对具体的某一位任课老师进行遗传操作，这时的初始化时参数设定就一定要考虑到时间和教室，做好其参数的设定，目的是为了避免一个遗传进化得到一个不合理的结果――小班级占用大教室，这里面我们可以设定额外的参数包括教室可容人数的最优逼近，此外还需要考虑到上课时间合理性安排等。本系统中，为了生成初始课表，我们采用随机搜索空闲空间的方法来生成。再对保留一个空闲集给每一个班级，idleTime(c)和一个未搜索空间SearchTime(c)，对从Lc(c∈C)令nosearchTime(c)=idleTime(c)，产生随机时间p ∈nosearchTime (c)。若是发现有冲突的话，则nosearchTime (c)=nosearchTime (c)-l，然后接着继续搜索。否则timetable(c，p)=Lc(c∈C)。idleTime (c)=idleTime(c)-l。反复循环上述过程，直到生成了我们目标需要的课表。

四、遗传算子的改进

在对课程编排问题的分析过程中，对于任何一种编排策略的评价相对来说比较难，情况也显得非常复杂，因为这中间包含有许许多多的来自任课老师、上课班级、授课教室等方方面面的要求与规则。课程编排中的规则，我们一般使用预定义约束条件的这种方式来约定遵守，从而要求可以把它们描述为我们对课程安排策略的目的，而这可以按照课程编排的一些关键因素对时间有要求的共性，借由统计所安排的时间这种方式来满足要求。

（一）节次优先级问题

我们对有特殊要求的课进行的优先度表示，是学生是否愿意上此节课的程度刻画，也可以是对于人们上这节课所得到的效率的高低。时间优先度 （O 1）反映对课程的每个节次的级别，由管理员借经验或一些历史数据的统计来设置，体现不同学生在不同学期的特殊要求。

在节次优先级的基础上，我们可以对交叉运算作一个调整，即在操作上对优先级相差更大者给予更高的交叉概率，概率计算方式为两个优先度的距离与优先度和的一个比值。这样一来，对结果的节次优先级满意度采用节次优先级平均值来进行评估分析了。

我们用 表示在一次课程编排中第i个开课第j课次上第k节课的优先度,p是总的开课数，Si是第i个开课的课次数，Tij是第i个开课第j课次的上课节数。于是我们可以用所有的 的和去除以所有Tij的和即可以得到节次优先级平均值，假设结果用 表示，可以看出， 值越大越好，因为它意味着安排的节次越好。

（二）课时分布均匀度问题

在排课的具体要求上，应该避免课程在班级课表上的安排异常地某一个整天无课或课程集中于某一天的现象，本文用课时分布均匀度来评估课程编排中在每天的日课程的均匀程度，我们用 表示班级每天上课的平均节数，参数 为班级参数Ci在第d日的节数，参数dw为总的工作日数量，则关于一个班级的课时分布日方差值 可以用dw个工作日内所有 的几何平均值来计算得到。

定义了这样的衡量标准后，为达到目标的极大化，可采取的策略是结合遗传算子，对变异运算进行加权控制，当某天课程较满时，加大变异的权重，调适后判断课时分布日方差值 的大小，班级课时日分布方差越小，则体现了相应的课时日分布也就越均匀，这样就在总体上为我们保证了学校课时的日分布走势趋向于均匀，也就可以避免在某天中里面的某节次排课教室使用的高峰，这样一来就可以在一定程度上提高了授课教室的利用率。

五、实验结果

实验首先对拥有527个教师，312个班级，以及412门课程和165个大小教室的输入按周一至周五仅排白天第1节到第8节进行自动排课，其中上午时间优先，另外对一些特殊课程，特殊教师的相应课程在初始化参数的时候作了优先级设置，在演化过程中进行人工加权参数干预，最终得到了较好的排课效果。另一组实验表明，当输入数据逼近饱和需求――需要的教室*时间接近可支配的教室*时间数时，演化过程明显变慢，在没达到理想解的情况下，出现了“高原现象”。

潘伟.基于遗传算法的鲁棒控制问题研究［D］东北大学,2006