遗传算法在高校排课系统中的应用

遗传算法在高校排课系统中的应用

王园园

(淮北职业技术学院 教务处，安徽 淮北235000)

摘要：对于排课的问题研究应该归于NP-完全问题的研究，它是综合化的问题，具有一定的目标性和约束性。对于排课的算法，和列表寻优、模拟退火等算法相比，遗传算法是最佳的。遗传算法通过整合当下教学资源，以交叉、变异以及选择等方式进行遗传和变异，为解决高校排课系统中存在的问题，深入研究了遗传算法在高校排课系统中的应用。

关键词：排课系统；遗传算法；自动排课系统；人工智能

收稿日期：2015-05-25

作者简介：王园园(1982-)，女，安徽淮北人，淮北职业技术学院讲师，硕士，研究方向为网络技术。

中图分类号：TP301.5;TP311.521文献标识码：A

受众多因素影响，高校排课很久以来受到人们的关注，但是实际排课过程中使用软件的情况却十分少见，原因之一就是很难选择适当的算法。1975年S.Even就排课问题展开了研究，他认为排课问题一定要通过“穷举法”的方式得出答案。但是这种方法也难以实现，因为穷举法本身所耗费的成本和时间都较多，难以通过计算机来解决问题。例如，一个教师要参与一周S时段的课程安排，而他要一周大概约有M节课，如果这个学校有N个教师需要进行排课，那么就有SN*M种可能性，显而易见，算法耗费时间较多。所以，为了解决该问题，笔者对列表寻优、模拟退火等算法进行了分析，同时提出了遗传算法(Genetic Algorithm, 简称GA)。[1]41-44

遗传算法可以认为是一种解决排课困难的最优方法，是由美国芝加哥大学的知名教授Holland提出。1962年Holland教授把遗传算法结合生物遗传、变异等理论知识，总结出了遗传算法，同时将其转移到图像管理、函数优化以及生产处理等广泛的领域。

一、关于遗传算法排课系统的发展概况

由于当下许多高校生源扩招，而学生数量的增多带来的问题之一就是学校教师排课困难。排课发生矛盾非常常见，经常有一些教师被迫“分身”上课，而有的课程安排不仅教室安排有问题，教师的安排上也发生冲突。因此上课混乱现象时有发生。只有解决排课问题才能更好的促进教学效率的提高，最大程度地发挥教学的作用。

对于NP完全问题的认证，自1970年开始就多次被提及。然而，课表的编排随着课表信息的增加而不断变化，其中潜在的问题也不断诱发了不同的解集。本文对于高校教学管理系统的排课方法进行了分析和研究。

二、以生物学和计算机为基础的遗传算法

从生物学角度出发，遗传算法可以理解为是一种建立在生物进化上的算法，其搜索假设的方法已经逐渐从简单到复杂过渡，以变异和重组来生成最终的假设。[2]93-94进化是生物成功地适应自然的方法，而以此为基础研究出的算法以假设的生成测试柱状展开搜索，有些假设则会以变体的形式在之后被涉及和考虑到。

三、遗传算法

遗传算法的演示过程和基因演化的过程差不多，大体如下：

1.以随机的方式构成数量相当的初始种群；

2.评测和估算个体的适应度，符合优化标准的可以输出其最优解，完成计算过程，不符合者继续下一步；

3.以适应度为根据对再生个体进行重新选取 ；

4.根据相应的交叉方法和概率重新生成个体；

5.根据相应的变异方法和概率重新生成个体；[3]

6.以变异和交叉的方式构成新的种群，然后返回第2步，如图1所示：

图1　遗传算法示意图

以下是遗传算法的伪代码。

ALOGRITHM GA(i)

Begin

t=0;

Initialize P(t);

P(t)={X1(t), X2(t),…, Xn(t)}

Evaluate P(t);

f(P(T))={f(X1(t), f(X2(t), …, f(Xn(t)) };

while (not terminate condition) do

Pc(t)=crossover{P(t)};

Pm(t)=mutation{ Pc(t)};

Evaluate [Pm(t)];

P(t+1)=select{ Pm(t)UQ};

t=t+1;

if t mod t=0 then Qi=Xbest;

od

print Xbest,f(Xbest);

end

通常情况下遗传算法是经过下列操作完成的：

(1)初始化[Initialize]

必须进行初始化操作,以便给遗传操作提供一个初始种群。

在算法设计时，因为进行遗传操作时仅仅针对老师，在初始化的过程中，时间和教室如何安排要被重复考虑到，其中包含了在教室内安排最合理的人数(即防止能够容纳200人的教室被30人所占用的情况发生)及安排合理上课时间。

(2)选择[Select]

生物界中自然选择能够剔除劣品保留优品，选择算法亦是如此。它能够将旧种群内适应能力强的染色体挑选出来，准备进一步的配对，使得在交叉与变异运算之后能够得到新的种群。染色体适应能力越强，越容易被选择，选择操作包含了锦标赛选择法(tournament selection)、轮盘赌选择法(roulette wheel selection)和局部选择法(local selection)等几种方法。[4]31-33本文运用了截断选择法(truncation selection)，它属于局部选择法。

(3)交叉[Crossover]

经过选择得出结果之后，父个体由选出的两条染色体组成，然后随机选取一个值(用r表示)，同事先设置的交叉率值(用t表示)对比，当r

(4)变异[Mutate]

任意将染色体内的上课时间进行更改，任意选择时间内的一点进行改动，但是不能超出设定的范围，这一过程称为变异。变异运算类似于自然界中生物的遗传，因为环境或其他无意的原因而导致的基因突变，虽然变异之后，染色体的适应能力会发生改变，但是它保证了这一物种拥有多种类型的遗传基因，保证了搜索范围的最大化，提高了最优解获取的可能性。

设置变异概率pm，在变异过程中随机数r会首先产生，如果r>pm，那么不能进行变异操作，反之则执行变异操作。这一过程与交叉相同。

四、冲突问题的处理

冲突问题在排课过程中是无法避免的问题，无论排课的方法是什么，最常见的突出问题为同一时间同一老师被安排了两门课程。[5]37-38本文利用了冲突检测函数fConflict()来防止冲突发生，如果确定了一名老师需要上的课，冲突检测函数就会自动检查该老师是否存在排课冲突，同时根据结果进行更正。

排课是高校教学管理工作中较为复杂的工作，遗传算法可以很好地解决高校排课系统中出现的问题，采用适应度函数以及染色体编码方案可以得到我们想要的结果，当进化代数不断上升时，适应度函数的值也不断增加，而染色体编码的方案，将被运用于更为复杂的排课中。

参考文献：

[1]业宁,梁作鹏,董逸生. 一种基于遗传算法的TTP问题求解算法[J].东南大学学报：自然科学版,2013(1).

[2]唐勇,唐雪飞,王玲.基于遗传算法的排课系统[J]. 计算机应用,2012(1).

[3]张燕,宋锦斌.基于遗传算法的排课系统[J].计算机知识与技术,2011(11).

[4]王小平,曹立明.遗传算法：理论、应用与软件实现[M].西安:西安交通大学出版社,2012.

[5]孙建平,梅晓勇.关联规则在高校智能排课系统中的应用[J].计算机应用,2012(5).

责任编辑：净草