遗传算法在排课系统中的应用与设计研究

江萧 弋改珍 袁岚清

摘要：为了方便教学管理方面的课程安排，在研究遗传算法的基础上，以软件工程的思想研究了排课系统的设计过程，并使用Java语言实现了基于遗传算法的排课系统。经过测试，该系统能自动完成自动排课和手动调整功能。

关键词：遗传算法；排课系统；Java

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）05-1032-04

排课是教学管理中十分重要、又相当复杂的管理工作，课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突并且要满足教师的要求和资源限制等约束条件。

为了利用计算机来解决这个实际问题，减轻工作人员的负担，自20世纪60年代起就有学者投入研究，研究者对于排课系统的解决方案大致分为以下几种：第一种是基于简单的经验法则解决教学规模不太大的问题[1]；第二类是建立排课模型，将排课问题归结为图的边染色问题[2]；第三种方式是先将固定时段的课程优先排入，然后依序填入其他课程[3，4]；第四种方法是采用模块化方式[5]；图形着色法[6]；搜索法[7]，总之这些方法适合处理小规模排课问题，当问题的约束条件增多时，问题变得相对复杂，求解过程会变得非常困难。

我国在排课方面的解决方案总结为两种：一是图着色模型[8]；而是数学模型[9，10]。

本文在讨论遗传算法的基础上，研究了遗传算法在排课系统中的应用和设计。

1 遗传算法

遗传算法最早于1968年由Holland教授提出，并建立了遗传算法原型，形成了遗传算法的理论基础。遗传算法是从生物进化论观点出发，用计算机模拟自然界演化的方式，对既定问题求最优解的方法，是基于自然选择和基因遗传、进化机制基础上的一种高度并行、自适应的优化算法[11]。遗传算法的操作步骤如图1所示。

图1 遗传算法流程图

2 排课系统的设计

2.1 总体设计

在充分调研教学排课管理业务后，经过分析，总结排课系统管理的信息和完成的功能有：

1） 基础信息管理

排课系统中所需要管理的基本信息有：教室信息、教师信息、课程信息、和班级信息；对这些信息管理的主要操作有、搜索、查看、添加、修改和删除。

2） 学期计划管理

学期计划管理模块主要依据学生的培养方案设置课程所在的学期、对应的专业（班级）、课程的名字以及课程所需的学时数；并为每一门课程指定相关的任何教师。

3）排课管理

排课管理有自动排课和手动课表调整两个方面的功能。自动排课是根据遗传算法的工作原理，对排课系统所管理的基本信息和学期计划进行杂交、编译操作后得到基本满足硬约束、软约束条件的课表；然后，在自动排课的基础上，将不满足条件的部分内容进行调整，最后生成教师课表、班级课表。

系统的总体功能模块图如图1所示。

图2 系统功能模块图

2.2 数据库设计

根据排课系统所涉及到的实体有：课程、教师、教室、班级、学期；这五个实体中教师和课程之间有授课关系；学期和課程之间有学期计划关系；班级与课程之间有班级课程关系；教室和课程之间有哪些课程在哪个教室上课的关系。关系E-R图如图3所示。

图3 排课系统中各实体及其关系E-R图

2.3 排课系统详细设计

1） 表示结构

在遗传算法排课系统中，一条染色体中应包含所有排课DNA分子，每个排课DNA分子又包含班级课程信息、老师信息、教室信息和时间信息，以及院系和学期信息。由于院系和学期在处理中是提前设定好的，在每次处理时都是一个给定的值，所以在染色体中可以不考虑他们。

2）初始种群

采用系统的随机数，生成初始种群。将排课任务表示为CyKwTx，在进行排课时，初始化种群中的个体就是用随机函数生成染色体中的RzMN的组合。

3） 约束条件

硬约束：

l每个指定时间段一个班级、一个教师、一个教室分别只能对应一门课程；

l要求教室的个数大于或等于指定时间段将要安排的课程数；

l安排教室时，要求教室容量必须大于或等于班级人数；

l教室类型与课程要求一致。

软约束：

l优先安排全校公共基础课；

l一周内课次多于2次以上的多课时课程，在时间安排上要求尽量隔天安排；

l较难课程应安排在上午第一节或下午第一节；

l体育课后尽量避免直接排课；

l同一门课程尽量安排在固定的教室。

4） 评价函数

评价函数是对种群中的每个染色体设定一个概率，使得高概率地选择某染色体，适应性值高的染色体被选择产生后代的机会更大。

评价函数的定义因各种问题而异，参数的个数也不一致。一般情况下，都是根据某种性的函数将各基因所获得的适应值进行统计，以求得整条染色体的适应值。

5）洗牌杂交

遗传算法中的杂交算法主要有：多点杂交、均匀杂交和洗牌杂交。本系统设计中使用的是洗牌杂交，即从每个父本中取它们一般的基因重组成新的个体。

6）变异操作

变异是随机改变一个染色体中某一基因的值，使得染色体出现新的基因特性，有时候将求解过程中趋于局限制时出现新的解决方法。变异的染色体个数根据变异率而定，如果变异率过高，将近似于随机数，难以达到最优解，如果变异率过小，将无法达到变异的效果。

基于遗传算法的排课流程图，如图4所示。

图4 基于遗传算法的排课流程图

3 实现与测试

自动排课系统按照学期进行，首先在学期课程计划中对教室、教室、课程、班级进行设置，在自动排课管理中选择“自动排课”，自动排课窗口如图5所示。

图5 自动排课窗口

自动排课功能并不一定能得到恰当的课表，这时可以手动对自动生成的课表进行调整。手工排课及课表调整窗口如图6所示。

4 结论

排课系统的求解的方法在实际中有许多解决方案。基于遗传算法的排课系统在实际效率上有很大的提高，这也是遗传算法在解决实际问题的一个简单应用。该文使用Java语言设计实现了基于遗传算法的排课系统，该系统实现了排课的自动化、智能化，使教务人员从繁杂的排课任务中解脱出来，而且对于推动教学的发展也起到非常重要的作用。

但是在非常复杂的应用中，使用遗传算法不一定能够得到最优解，即通过若干次迭代，算法不一定能收敛于某个最优解。这是可以提供不同的可行解供使用者进行选择，直到使用者得到一个解决方案为止。

参考文献：

[1] 周建新. 课表编排专家系统[J].计算机应用，2000，20（5）：76-78.

[2] Bondly J. A Graph Theory with Application[J].The Macnulan Press Ltd，1976：10-23.

[3] Selim S M. An Algorithms for Constructing a University Faculty Timetable[J].Compute Edue，1982（1）：323-332.

[4] Selim S M. An Algorithm for Producing Course and Lecture Timetable[J].Compute Edue，1983（2）：323-332.

[5] Dowsland W B，Lim S.Computer Aided School Timetable – part2：the Micro-computer for School Timetabling[J].Compute Education，1982（1）：2-4.

[6] Dde Werra. Restricted Coloring Models for Timetabling[J]. Discrete Mathematics，1997（1）： 161-179.

[7] Hertz A.Finding a Feasible Course Schedule Using Tabu Search[J].Discrete Applied Mathematics，1992（3）：255-270.

[8] 胡順仁，邓毅，王铮.基于高校排课系统中图论问题研究[J].计算机工程与应用，2002（4）：221-222.

[9] 孙建平，梅晓勇.关联规则在高校智能排课系统中的应用[J].计算机应用，2002，22（5）：37-38.

[10] 余斌，谢昕.基于减小教师流动性的排课算法研究[J].计算机时代，2004，10（2）：22-23.

[11] 周水庚.基于遗传算法的排课系统设计与实现[D].上海：复旦大学，2006.