改进的自适应遗传算法在排课系统中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇改进的自适应遗传算法在排课系统中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 在各院校的教务管理中，排课系统是非常重要的。本文首先论述了改进的自适应遗传算法，并通过研究排课问题中的影响因素、主要约束条件，阐述了基于改进的自适应遗传算法的排课系统的设计方案。

Abstract： The course scheduling system is very important in academic management of college. The improved adaptive genetic algorithm was discussed firstly, and then the design scheme of course scheduling system based on improved adaptive genetic algorithm was expounded through studying influence factors and main constraint condition in course scheduling problem in this thesis.

关键词： 自适应遗传算法；排课系统；应用

Key words： adaptive genetic algorithm；course scheduling system；application

中图分类号：G47文献标识码：A文章编号：1006-4311（2011）04-0170-02

1对自适应遗传算法进行改进

1.1 采用三维编码方法个体的编码方法对交叉、变异等遗传算子的运算方法及程序实现的复杂度都有很大影响。遗传算法最常用的编码方法是二进制编码，结合实际应用需求，均衡考虑制约学校排课系统的各因素，采用了三维编码。它具有以下优点：可方便地利用三维数组保存排课相关信息；编码和解码直观；进行交叉和变异运算时方便进行冲突检测和适应度计算以及程序实现复杂度低等。

一个采用三维编码表示的染色体可以直观地被看作是一个立方体，X轴表示时间轴，X轴上的每个时间坐标对应一个单位时间的间隔，根据学校实际情况，一个单位时间为一节大课的时间（两个课时），假如一周五个工作日、每个工作日三个时间段，那么X轴共有15个坐标值。Y轴每一坐标间隔代表一间教室，Z轴每一坐标间隔代表一个授课事件。其中，Z轴坐标（授课事件）又可以被分为Za（教师）、Zb（课程）和Zc（班级)三个分量。这样由三维坐标唯一地确定的那个小方块被称作个体的基因。在染色体全部基因块被赋值后，染色体就代表了一个课表编排方案。

1.2 采用基于符号函数的自适应遗传算法为了避免染色体早熟，改善了交叉与变异概率。采用基于符号函数的自适应遗传算法。将遗传的进化过程分成两部分：前期和后期分别取值。在前期，变异概率指定的区间内逐渐增大，变异概率逐渐减低，当适应度的值超过平均适应度值时，交叉概率下降，变异概率增加，从而能够很好地防止早熟现象的发生。基于符号函数的优化遗传算法，算法描述如下：①利用三维编码，进行编码／解码设计，组成初始群体；②定义适应度函数，计算各个个体的适应度；③以交叉概率Pc和变异概率Pm进行；

Pc=sinarcsin■-SGN■-1■■arcsin■

Pm=sinarcsin■-SGN■-1■■arcsin■

④若满足终止条件则退出算法，输出最优解。终止条件可以设定为指定最大代数或指定若干代无法取得更好的最优个体；⑤否则回到第2步。

2排课问题中的基本原则以及需要考虑的教学因素

课程表的编排工作就是要根据学校具体的教学资源情况，按照教学计划的要求，将课程、教师、学生在时间与空间上进行科学合理的排列组合。为了使编排的课程表更加符合教学规律，需要遵循以下原则：①某门课程只能为某一专业的学生安排一次；②同一位教师在同一时间段内只能安排一门课程；③在一个时间段内某专业的学生只能上一门课程；④教室的类型和容量要与学生人数和课程的需求相匹配；⑤同一教室在同一时间段只能安排一门课程。

要想使每一次教学活动都能够顺利进行，那么编排课程表时就必须满足以上五条原则，否则就会出现教学冲突，比如：同一位教师在同一时间段内被安排两门课程等。为了使排出的课程表更优化、合理，需要手工调整的内容较少，根据学院的具体实际情况排课时还应考虑以下因素：①同一门课程不能连续上，应该尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课。②尽量上午第一节课不安排自习课。③课程表中的上课时间不能过分集中，应该尽量避免一天课程很满而另一天却没有课的情况。④给两个或者三个教学班上同一门课程的老师，应尽量能上连续课程。比如一个老师给两个教学班上同一门课程，应尽量安排这位老师上完第一个班的课，在这一天内立即上第二个班的课，以保持两个班的教学进度一致。⑤尽可能满足个别教师的特殊上课时间要求。⑥尽量不使某一个教师在一周内总是上上午的第一节课。

3把改进的自适应遗传算法应用于排课系统，排课系统的设计方案

遗传算法可定义为一个8元组：GA=（C，P0，M，Φ，Γ，N，E，T）

式中，C―个体编码方法；Po―初始种群；M―种群规模；Φ―选择算子；Γ―交叉算子；N―变异算子；E―个体适应度评价函数；T―遗传运算终止条件。除了以上8元组之外，还有两个与遗传操作相关的参数：Pc交叉概率，Pm变异概率。

3.1 采用三维编码方法一个采用三维编码表示的染色体可直观地看作一个立方体。采用三维数组来分别表示X、Y、Z轴上的数据。

3.2 确定初始种群与种群规模在遗传算法中要产生初始种群，就必须进行种群群体的初始化处理，在初始种群产生的过程中，种群规模大小的确定非常重要。种群规模的大小会直接对遗传算法的执行效率和问题求解的最终结果产生影响。经过理论研究和实践证明，一般种群规模确定在20到100之间。本论文中优化后的排课系统经过测试，种群规模确定为35。

3.3 设计遗传算子

3.3.1 选择算子的具体实现过程如下：第一步：累加当前代种群中所有染色体的适应度函数值，得到总的适应度函数值；第二步：用每一个染色体的适应度函数值除以总的适应度函数值，便得到该染色体的选择率；第三步：根据每一个染色体的选择率复制该染色体进入下一代种群中。

3.3.2 交叉算子交叉算子在遗传算法中起着关键作用，是产生新个体的主要方法。交叉策略是：以垂直于z轴的平面将两个个体分割，交换两个个体的z>z’部分(z’为分割点)。

3.3.3 变异算子在遗传算法中属于辅的搜索操作，它的主要目的是维持群体解的多样性。变异策略是：随机地确定垂直于z轴的一个平面，为这个平面上的所有基因块重新随机地赋值0或1。

为了避免染色体早熟，改善交叉与变异概率。采用上述的基于符号函数的自适应遗传算法来确定交叉概率Pc和变异概率Pm。

3.4 确定适应度函数遗传算法是在个体适应度评价函数的引导下进行的。在设计个体适应度评价函数时，要充分考虑课程表的诸多约束因素。染色体的个体适应度评价函数定义为：fitness（Chromosome）=y（wi+pi）。（pi是约束因素的期望值，wi是pi的权重）

3.5 确定遗传算法的终止条件遗传运算的终止条件通常有以下几种：①一个个体已经满足最优解的条件，即最优解已经找到；②适应度已经达到饱和，继续进化不会产生适应度更好的个体；③进化次数的限制；④计算耗费的资源限制（例如计算时间、计算占用的内存等）；本排课系统中的遗传运算终止条件为：连续10代最大适应度函数值不改变。

4结束语

实验证明，把改进的自适应遗传算法应用到排课系统中，可以较好地完成整个学院的排课，同时提高排课效率。对于极个别产生冲突的课程，可人工进行调整。

参考文献：

[1]张建安，杨学俊，吴文一.基于关联规则算法的排课系统设计与实现.现代电子技术，2010，33(2):60-64.

[2]金民锁.基于遗传算法的实验室排课系统设计与实现.实验室研究与探索，2010，29(3)：66-69.

[3]任志刚.基于优先级模式的计算机排课系统的算法设计.太原师范学院学报（自然科学版），2009，8(4)：42-44.