基于遗传算法的优化排课系统研究

徐萍

摘要：该文基于学分制排课出现的问题，分析了遗传算法原理并对其进行了改进。指出了遗传算法中选择方法使用轮盘方法。最终将改进的遗传算法应用到选课系统中，结果表明改进算法对系统使用度有显著提升。

关键词：遗传算法；排课系统；交叉概率

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）14-0166-02

教学过程中，排课问题一直是一个让人头疼的问题，特别随着教学模式的改革，又对排课问题提出了新要求。实质上排课问题作为组合优化中的一种典型问题，早成为世界七大难题中的一种。遗传算法（genetic algorithm，简称GA）是一种进化算法，这种算法主要借鉴了生物学中适者生存、优胜劣汰的规律。由于遗传算法是最佳化的搜索算法，因此人们在研究复杂的排课问题时一般采用遗传算法，且取得了一定的研究成果。但在当前的研究成果中依然还存在两个问题，一是排课算法经过多次运行后发现终应值结果是不同的，这表面当前排课算法离完全收敛于全局最优解还有一定的差距；二是搜索最优解时一般采用完全随机方法进行搜索，这种方法搜索效率较低，没有一个十分明确的搜索方向。

生物学中有一个著名的杂种优势理论，这个理论认为不同遗传因素的动植物杂交产生的后代比着纯种亲本后代有着十分明显的优势，如其繁殖能力较强、抗逆性较强等，并认为这是自然界中普遍存在的一种现象。杂交优势主要表现为动植物遗传因素差异越大则其杂交优势就越为明显；动植物亲本越纯，其后代就具有较明显的杂交优势。

1 排课系统中遗传算法设计

遗传算法第一步是通过随机方式产生多个求解问题的编码，这些编码称为染色体，这些染色体可以组成群体。通过适度函数对群体中的每个染色体进行评估，选择适应度高的染色体，并将这些染色体参加到遗传操作中，通过遗传操作形成新的种群。采用迭代的方法，直到到达算法设置的终点条件，该算法结束。在高校排课系统中，每一次教学课程便是一个染色体，染色体的结构可以用向量表示：排课结果是由所有教学课程组成，该结构是一个二维数组，该结构比较复杂同时数据量大。遗传算法中引入适应函数用于选择优异的数据，排课系统中的适应函数是由约束条件转化得到的，这些因素包括：教室利用率、教师上课时间分布及班级课程分布等。

遗传算法为排课系统内核，因此性能优异的遗传算法直接影响到排课系统运行。遗传算法由4个参数控制：选择、交叉、变异及终止。

1）选择。排课系统中遗传算法的选择操作方法是使用轮盘赌博方法，根据轮盘上的区域比例进行分配。其中适应度高的所占的比例高，因而选中的可能性就高，适应度低的所占比例低，选中的可能性就低。轮盘方法作为选择操作可以避免基因缺失从而提高了计算效率及全局收敛性。

2）交叉。交叉参数是染色体与染色体之间形成新的染色体方法，遗传算法的全局搜索速度由交叉所控制。在高校排课系统中，涉及课表合理性，因此不能使用双点交叉及单点交叉，通常使用交叉时间段；在此需要考虑到班级内部交叉可能会影响到其他班级课表合理性。在使用交叉运算时需要进行冲突计算，确保生产的课表是合理的。如图1为交叉运算流程。

3）变异。变异参数在遗传算法中为新个体的产生提供辅助作用，遗传算法的局部搜索能力就是由变异决定的。为了算法搜索能力的提高需要将变异和交叉结合在一起。高校排课系统需要考虑到课表的合理性，使用简单的变异方法不能解决课表合理性。因此需要使用变异概率，算法中的变异概率通常很小，在变异时会产生一个随机数r（0

4）算法终止条件。当个体到达最有条件，同时适应度也刚好饱和，进行进化算法也不会找到更好结果。在排课系统中对进化次数进行限制，通常迭代次数在200到600之间。

2 优化排课系统实现

优化排课系统的实现是以服务器/客户机环境为基础的，在此系统中将排课、课程表管理、资源管理等结合在一起，学校各院系都分配到了排课的相关工作内容。各院系在排课时，首先通过客户机填写相关的开课信息，开课信息填写完毕后会通过网络传输至服务器中，服务器会根据开课信息进行排课，然后再讲排课安排发送至各院系，最后院系将排课表打印出来即可，如果排课相出现不合理的情况时，各院系可自行进行调整。如图3所示为优化排课系统流程图。

针对上述分析算法，本文使用C#语言进行代码编写。部分代码如下所示。

Class CourseUnit

{

List Schedule = new List（）；

private int ID；

private const int CourseCount = 8；

private const int WeekDay = 5；

private int[] Array = new int[WeekDay * CourseUnit.CourseCount]；

private CourseUnit （int id， int[]array）

{

Array = array；

ID = id；

}

}

结果表明：当处于1到350代时遗传算法可以很快很明显的在排课系统中得到提升，当处于400代时遗传算法的特点就开始显现出来，此时在4.810e-004之间进行收敛，此时的遗传算法会在最优解附近进行收敛和徘徊，甚至会停止。

3 结束语

除了基于遗传算法来优化排课系统外，要想进一步的对排课系统进行优化，还要从下面几个地方入手：对课程表问题出现的先行条件进行提取，再将这些条件集中起来通过对搜索引擎的优化对排课进行优化；对排课中出现的各种问题进行综合、全面的考虑，找出这些问题之间的规律；排课中会出现各种状况，但状况不同其权值是不同的，因此就需要去权值进行衡量、考虑。

参考文献：

[1] 汪晓飞， 李晓宁. GA编码方案在高校排课系统中的应用[J]. 计算机工程与设计， 2008， 29（17）： 4565-4567.

[2] 于娟， 尹积栋. 面向排课系统的遗传算法改进研究[J]. 太原理工大学学报， 2012（5）： 573-579.

[3] Srinivas M. Genetic algorithms： A survey[J]. Computer， 1994， 26（6）： 17-26.

[4] 苏仰娜. 基于遗传算法的优化排课系统[J]. 河南大学学报：自然科学版， 2005（1）： 76-77.

[5] 郭俊恩， 刁文广. 基于规则和遗传算法的实验室排课算法研究[J]. 河南大学学报（自然科学版）， 2014， 44（3）： 356-359.

[6] 彭复明， 吴志健. 基于多种群遗传算法的排课方法[J]. 计算机工程与设计， 2010（22）： 4877-4880.

[7] 傅亚莉. 基于遗传算法的高职院校排课系统的研究与实践[J]. 吉林广播电视大学学报， 2010（11）.

[8] 廖宇力. 基于遗传算法的排课问题适应度函数设计[J]. 现代计算机：专业版， 2010（4）：9.

[9] 滕姿， 邓辉文， 杨久俊. 基于遗传算法的排课系统的设计与实现[J]. 计算机应用， 2007（S2）.

[10] 胡义伟， 谢勇， 郑金华. 基于遗传算法的综合性大学排课系统研究[J]. 中国教育信息化， 2007（21）.