网站原创摘 要 ：随着全国各大高校的扩招,如何正规、科学、合理地安排好课程、教师、教室等诸多资源进行排课已经成为学校教务管理的重点与难点.随着人工智能领域的不断完善与发展,遗传算法由于其超群的并行搜索能力,以及在解决优化问题中体现出来的高度健壮性,迅速被应用于求解组合优化的排课问题.
关 键 词 ：遗传算法；排课系统；优化
中图分类号：TP301
近些年来,伴随着“数字化校园计划”快速并逐步的向深入发展,传统高校中的教学管理模式也面临着重大的转变.有效运用计算机作为日常教学和教务的辅助管理已经成为各个高校实现数字化校园的工作重点.
遗传算法（Geic Algorithm――GA）是一类借鉴生物界的进化规律演化而来的高度并行、随机、自适应的搜索算法.S.even等人在1975年的研究证明了排课问题是NP-Complete问题[1],非“枚举法”之外不能找出最优可行解.国内外,已有众多学者将遗传算法的原理应用于排课系统之中,如,乔树青将遗传算法的运行区分为多种不同的机制应用于排课系统之中[2]；石慧运用基因对交叉遗传算法求解多校区排课问题[3].但是由于约束条件过于宽泛,计算结果常常无法收敛于全局最优解.本文尝试利用遗传算法的原理对排课系统进行优化求解.
1遗传算法描述
遗传算法不同于传统的搜索算法[4].遗传算法依据编码方式以及初始条件随机生成一组解,这组解被称为种群（Population）.构成种群的每个解都被称为染色体（Chromosome）.染色体通常是一组数据,这组数据被用来作为表示问题的解的代码,其本身不一定是一组可行解[5].这些染色体在后续的迭代过程中部分会不断的进入到下一代的染色体之中这被称为遗传.在每一代种群中用适应度值（Fitness）来表示染色体的优劣程度,并利用适应度函数来对一组染色体进行适应度的测量.测量后根据选择算法进行选择是否遗传到子代之中.由此生成的下一代染色体称为后代（Offspring）.后代是还有可能是通过父代交叉和变异产生的个体.新一代形成中,根据适配值的大小选择部分后代,淘汰部分后代,从而保持种群大小是常数,适配值高的染色体被选中的概率较高.据此,经过若干代之后,算法可能收敛于最好的染色体,它很可能就是问题的最优解或较优解.
2排课问题分析及算法设计
从数学角度来讲排课问题,实质上是在时间、班级、教师以及教室和课程的5维空间上,以教学计划中的各种要求所产生一些约束条件的组合规划问题[6].所需要采取的就是对排课问题中的各个维度上的对象按照各个约束条件解决对象间的冲突.
在解决冲突之前,首先由理清一下四种关系：
（1）课程与教师之间的映射,即每门课程的任教的教师有哪些.
（2）课程与的互斥关系,即在拓扑关系图中以时间描述的先后顺序.
（3）课程与班级之间的映射,即需要学习本门课程的班级有哪些.
（4）课程与时间的映射,即课程不能被安排在相同的时间段（更复杂的逻辑关系）.
经过对高校排课系统的需求分析知道,若将教室维度加上很难在有限的时间和空间存储条件下进行求解,并且在需求方对于教室安排并不是必须的,因此我们检测设教室资源充足的前提下进行排课算法的设计.
2.1个体表示
在系统中笔者使用BYTE类型的三维数组来表示染色体个体（记为P）.其中第一维度（记为I维度）为班级编号classListSize,第二维度（记为J维度）为教师编号teacherListSize,第三维（记为K维度）度为时间片编号timeSliceTotal.个体中存的值则为教师授课程编号.个体表示I班级在K时间上J教师所教授的第P门课程.如图1：
byte[][][]chromosome等于new byte[classListSize][teacherListSize][timeSliceTotal]；
图1染色体个体数据结构定义
2.2评价函数
评价根据班级所有相同课程的时间间隔度量值ti、班级教师教授课程的时间间隔度量值tj、班级主干课程重要度度量值之和Sumi、班级上课教师的要求与课程安排符合程度度量值Sumj,在此定义排课系统状态的评价特征特征向量X等于{ti,tj,Sumi,Sumj}.
在域X上存在一个集合P,设存在一个数x与αPi（x）∈[0,1]（x∈X）一一对应.定义个体差异度为ηki等于max{αPi,等αPk}/min{αPi,等αPk}.
定义适应度函数为 ,n为特征值个数（n等于4）.
2.3选择算法
选择算法选用赌算法,依据评价分值进行选择下一代种群轮.其中赌算法是依据个体的分值在整体分值总和中所占的比例,并使这个比例为该个体被选中的比率.然后通过设置伪随机数来进行个体选择并重复多次.
2.4交叉算子与变异
交叉运算是产生新个体的主要方法[7],它是遗传算法的全局搜索能力的核心因素.为了保证排课系统自动生成的课表的合法性,不能直接使用单点交叉和双点交叉.因此,本文中的遗传算法采用的是交叉时间片的思想,并采取暴力搜索的方式检测冲突.
在初始阶段随机选取一个个体,按照一定概率随机改变该个体串结构数据中某个串位的值.将变异率P与时间关联,使得交叉进化的初期,个体变异的阈值相对较大,随着进化的推进,个体变异趋于稳定.
3结束语
本文结合高校排课的实际问题,简要介绍了遗传算法的原题以及排课过程中的一系列问题,致力于运用遗传算法解决排课问题并取得了初步的成果,但想要对约束条件进一步细化、求得全局最优解以达到较好的排课效果还需要进一步的深入探索.