基于遗传算法的排课系统

基于遗传算法的高校排课系统论文

基于遗传算法的高校排课系统

张燕 宋锦斌 刘红兵 王安家

（长沙医学院 湖南省长沙市）

摘 要：近年来随着大学的扩招和规模的扩大，排课问题已成为一个非常棘手的问题，在教室资源有限的前提下课程编排显得更加繁重，同时课程的编排也更成为教学管理工作的关键，在一定程度和深度上影响着学生培养与教学质量的提高。利用计算机进行自动排课，不但能使教务人员从繁杂的排课任务中解脱出来，提高教务管理工作效率，而且能改善教学管理质量，合理、高效地利用有限的教学资源，使学校的各种教学活动、教学管理及其它相关的工作能够有序、规范地进行，维持正常的教学秩序，同时对推动教务管理的信息化起到非常重要的作用。

排课问题是一个有约束的、多目标的、难解的组合优化问题，是属于NP-完全问题。研究者提出了多种其他排课算法，例如模拟退火、列表寻优搜索、约束满意等，而遗传算法是很有效的求解最优解的算法。 遗传算法通过交叉、变异、选择三种遗传算子来实现遗传和变异的功能,并采用适应度函数保证排课结果趋于最优，对现有教学资源进行科学合理的安排，在实践中具有一定的应用价值。所以本文以遗传算法为基础，对排课问题进行了深入的研究，在实际应用中有一定的意义。

关键字：排课系统；遗传算法；自动排课系统；人工智能 中文分类号 T301

Abstract In recent years, with the University Expansion and expansion of the scale.timetabling has become a very difficult problem. Limited resources in the classroom context, Curriculum has become more onerous. The courses become the key to teaching management at the same time. It affects students in developing and improving the quality of teaching to some extent. Arranging automatically by computer, not only to academic staff from the cumbersome task of freeing Arranging, improve efficiency of educational administration, but also to improve the quality of teaching management. Rational and efficient use of limited teaching resources, making variety of teaching activities, teaching management and other related work orderly and standardized manner, keeping the normal teaching order, At the same time promoting the academic management of information technology play a very important role.

Timetabling problem is a constrained, multi-objective, intractable combinatorial optimization problems, it belongs to NP-Complete problems. Researchers have proposed many other Timetabling Problem, such as Simulated Annealing, List of search optimization, Constraint satisfaction and so on. But genetic algorithm is very effective algorithm for solving the optimal solution .GA carry out genetic and functional variation through Crossover, mutation and selection of three genetic operators. And adopt fitness function ensure Arranging Results tend to the best. On existing teaching resources to conduct a scientific and rational arrangements, it has a definite value in practice. So this article is based on GA ,On arranging for in-depth study of the application have a certain

1

基于遗传算法的高校排课系统论文

significance.

Key words curriculum arrangement; genetic algorithm; Priority strategy

1 基于遗传算法排课系统的问题背景：

随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去一个教室上不同的课程，一些公共课程需要几个班合上(如计算机基础课)，一些英语的基础课程必需安排在拥多媒体的语音室进行教学，有些教师在特定时间不可以上课等。如果没有很好地解决这些冲突，必将产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。

20世纪70年代中期，就有人论证了课表问题是NP完全问题。当课表所涉及的任何信息量稍有变化将会导致课表编排选择方案的剧增。课表问题存在固定的数学模型，能找到相应的解，且是一组解集。为此，现提出一些关于高校教学管理系统排课的算法。

2 遗传算法用生物学在计算机科学中的描述：

在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性遗传算法搜索的假设空间中，可以如下描述遗传算法。

? 遗传算法（GA）是一种受生物进化启发的学习方法，它不再是从一般到特殊

或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设 ? 每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设

的后代替代群体的某个部分

? 这个过程形成了假设的生成测试的柱状搜索，其中若干个最佳当前假设的变体

最有可能在下一步被考虑

3 遗传算法一般共同结构及流程：

首先产生一个初始种群，然后对这个种群中的每一个个体进行适应度计算，适应度即表示了个体对环境的适应程度。计算后的个体进行是否满足优化准则判定，如果满足，那么算法找到了这个个体并停止，如果不满足准则，那么算法将对这个种群进行选择、复制、交叉、变异操作，遗传操作的目的是从初始种群中筛选出较优异的个体进行演变，这其中包括复制优秀个体重生、两个父个体进行交叉和单个个体的变异这三种方式，对演变后的子代群体，重新进行优化准则判定，如此循环下去，直到找到一个最优个体，或者达到其它循环条件为止。其基本结构如 图2.1所示。

以下是遗传算法的伪代码。 Void yichuan() {

Int I=0 //循环参数

Initialize P(i) //先产生一个新的种群

2

基于遗传算法的高校排课系统论文

Infitness(i) //计算种群适应度 While ( not Terminate-Condition) {

Reprodureperator C(I); // 选择操作 Crossoverperator C(I); //交叉操作 Mutationperator C(I); //变异操作 Infitness(i) //再次计算机种群适应度 I++ // 循环函数加一 } }

一般的遗传算法都包含三个基本操作： 1、选择操作(Reprodureperator) 2、交叉操作(Crossoverperator) 3、变异操作(Mutationperator)

4 遗传算法排课问题的数学模型：

设课程集合：L={l1，l2，…，lp，…，lP}；班级集合：C = {c1，c2，…，cm，…，cM} ；教室集合：R = {r1，r2，…，rn，…，rN} ；教师集合：S={s1，s2，…，sk，…，sK} ；时间集合：T={t1，t2，…，td，…，tD}；时间与教室对的笛卡尔积为：G=T·R=(t1，r1)，(t1，r2)，…，(tD，rN)；G中的元素称为时间教室对；课表问题的求解过程就转化成为每一门课程寻找一个合适的班级、时间、教室对。

排课过程必须满足各种约束条件，可以将各种约束条件归纳成两类以简化分析过程。

? 实际条件约束

实际条件约束是在排课过程中由于各类资源的有限，因此必须满足而无法变更的约束条件，通常只要满足下面三类硬约束条件就能够保证在排课的过程中不发生此类冲突。 ① 同一时间，一个教师不能同时有一门以上的课程，记为R1：R1≤1，其中：k=1，…，K；d=1，…，D0=1 教师sk 在时间td 和教室rn 上课程lp；0则否。 ② 同一时间，一个班级不能同时有一门以上的课程，记为R2：R2≤1，其中：m=1，…，M；d=1，…，D0=1班级cm 在时间td 上教师sk 的课程lp；0则否。 ③ 同一时间，一个教室不能同时有一门以上的课，记为R3：R3≤1，其中： n = 1，…，N；d = 1 ，…，D0=1教室rn在时间td由教师sk上课程lp；0则否。

? 软件工程方面约束

3

基于遗传算法的高校排课系统论文

在这里要考虑软件工程中软件开发各个方面的因素，如面向对象开发的边界值确定，等价类划分等，还有一些软件开发带来的风险对软件项目的影响，这些都是我们在排课系统中要考虑的核心问题。

遗传算法的伪代码

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 termination condition) do PC(t)=crossover {P(t)}； Pm(t)=mutation {PC(t)}； Evaluate [Pm(t)]；

P(t+1)=select [Pm(t)∪Q]； t：= t+1

if t mod T=0 then Qi：=Xbest (*) od

print Xbest，f(Xbest)； End

5 排课系统中的遗传基因及应用： 排课过程：

1、产生遗传因子：产生初始的因子序列。

2、对因子序列进行杂交：将产生的两个因子序列充分杂交。 3、对杂交后的因子序列优化、筛选，产生最优课程解。

排课的过程中，首先产生一个以时间、教室、课程、班级为基数的课程因子，如用字符串0000 0000 0000 0000基因来表示一组初始因子，即第0号时间段，在0号教室，上0号课程，上课的班级为0号班级。用1111 1111 1111 1111基因来表示另一组初始因子，即第n号时间段，在n号教室，上n号课程，上课的班级为n号班级。

利用这两个初始因子，开始进行杂交，然后产生一系列的课程因子。利用优化函数对课程因子进行筛选，再重新杂交，直到得到满意的结果为止。

在此过程中，掌握好判定因子是否达到最佳状态是关键。我们可以利用一个判定函数来进行确定。

首先，将产生的新因子与前面因子进行比对，如果因子已经存在，则舍弃。 其次，在比对的过程中，如果发现因子之间违背了数学模型的实际约束时，也应当进行舍弃，以保持因子的独立性，节省资源。

在这个过程中，先将所有产生的课程因子看成一个二维数组。可以利用判别函数来判定是否存在同一班级，同时上多门课程。其判别过程如下：

1、取出各行的时间、班级段因子，组成一个新的数组time-class。

2、将第1行的字符串与后面的所有元组进行比对。如果存在相同元组，则舍弃。

4

基于遗传算法的高校排课系统论文

退回到杂交过程，重新产生因子。

3、如果不存在相同元组，则将下一行元组与后面的所有元组进行比对，如果存在相同元组，则舍弃，退回到杂交过程，重新产生因子。

4、反复执行2、3，直至所有元组不存在相同元组时结束。

判别完同一班级同时上多门课程的条件之后，还要判别是否存在同一教室同时上多门课程的结束。

其过程与testClassCourse()函数过程相似，在此便不再赘述。

最后，对具有独立性的因子进行适应度检测，如某些有特殊要求的课程是否已经满足条件。像体育课，一般是下午时间上，如实验课。如果不满足，则要求重新组合。

经过这几个过程之后，产生的课程因子就相对稳定了，最后就是要将这些课程因子转化为真实的课程。这时，我们就需要利用一个转化函数，将课程因子序列转化为课程信息，如0010 0001 0111 1001转化为第2号时间段在1号教室上7号课程，上课的是9号班级。转化完成之后，就得到我们所想要的课表，最后，将课表存入数据库供查询使用。

参考文献:

[1]张燕，宋锦斌 基于遗传算法的排课系统[j].计算机知识与技术，2010（11）

[2] 孙建平，梅晓勇.关联规则在高校智能排课系统中的应用[j].计算机应用，2002（5）：37，38，42 [3] 王力，高校通用排课管理信息系统设计与实现[j].贵州工业大学学报，1999，28（1）：87-90

通讯作者：张燕（1981），女，湖南岳阳人，讲师，主要从事数据库研究、软件开发及管理工作。 宋锦斌，助教，主要从事与软件开发，数据库研究，网络安全方面。 主持院级课题一项（长医研字[2008]27号）

此项目系第二批湖南省大学生研究性学习与创新性实验基金项目（湘教通[2009]320号--369） 湖南省教育厅课题一项（编号09C163）

5