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

摘要：新形势高校的发展，高校教务管理中的排课问题显得更为复杂。排课问题是一个典型的组合优化和不确定性调度问题，也是一个完全问题。该文根据高校实际情况，从遗传算法的基本理论着手，研究如何利用遗传算法解决高校排课中的资源冲突、课表优化等问题，并引用了哈希表和时间粒度的概念，对传统遗传算法染色体的编码模式进行了有益修正，增强了模式的灵活性。实验证明，遗传算法能够简化程序的复杂度和减少生成最佳课表的时间。达到了较高的师生满意度。

关键词：排课；遗传算法；哈希图；时间粒度；适应度函数

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)28-0175-03

The Making Class Schedule System of High School Based on Genetic Algorithms

XIA Xiao-yun1, GAO Wu-jun2

(1.Faculty of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2.Faculty of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China)

Abstract: As the ongoing development in the higher education institutions, the class arrangement model in the management system is also becoming more and more complicated. Course Scheduling is a typical portfolio optimization and uncertainty of scheduling problems, but also a complete problem. Based on the actual situation in high school. In addition, on the basis of GA basic theory, studies how to utilize GA to solve the conflict problem that aroused in schedule arranging system and improve schedule arrangement. We quoted a hash table and time granules, and amend the traditional genetic algorithm chromosome coding models, enhance the flexibility of the model. The practice has proved that GA can simplify the program complexity and shorten the time in generating new perfect schedule. And the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.

Key words: making class schedule; genetic algorithms; hash map; time granules; fitness function

1 引言

随着高校规模的扩大，学生人数也逐渐增加，高效教务部门排课问题也变得越来越复杂。高校排课问题是在给定教师资源、教室资源、学生人数和开课计划的前提下，如何合理安排课表的问题。排课问题是一个NP难问题[1]。对于较为单一的排课问题来说，可以采取启发式搜索算法找到最优解，而对于复杂的排课问题，该算法很难找到合理和满意的解。遗传算法[2]作为一种有效的全局搜索方法，具有良好的并行性，通过对可行解进行选择、交叉、变异等遗传算子的作用使种群不断进化，从而得到全局最优解或近似最优解。基于遗传算法的鲁棒性，适用范围广，有组织性、自适应和学习性、并行性等许多有点，其应用范围也较为广泛。本论文引入哈希表和时间粒度对编码模式进行修正，并充分利用遗传算法特点，给出了排课问题的有效求解方法，对高校教务管理排课研究具有重要的意义。

2 排课问题中的约束条件及优化目标

在实际排课过程中，以某一等长的时间段为课表的时间安排单位，称之为时间单元[3]。一个可行的课表安排应满足以下约束条件：课表以一个星期为一周期，一个星期的课表就是一个学期的课表；课表应满足班级、教师、教室上课不冲突；教室的座位应该满足上课班级学生的需要；其他一些特殊要求。

高校排课问题实际上是时间表安排的问题[4]。在实际排课过程中，需要考虑到教师、学生、班级、教室、教室的大小、实验设备等方面的问题。这些条件可以根据重要性将其分为硬件约束和软件约束。为了更好的解决问题，我们假设硬件约束为：

某些课程需要安排在特定的教室。

同一时间，同一个教师，同一个学生，同一个教室不允许同时上一门以上课程。

教室必须有足够的座位容纳学生。

对于需要试验设备的课程，教室需要有相应的配套设备。比如计算机课需要电脑。

硬件约束条件是在排课过程中必须满足而无法变更的约束条件。

软件约束为：

安排教师喜欢的特定时间上课。

安排教师喜欢的特定教室上课。

在相应的时间或教师给学生或老师安排特定的课程。

软件约束条件是在排课过程中可以满足但又可以不完全满足的约束条件。

排课问题[5-7]的关键就是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。排课的优化目标就是使得各类冲突为零，并且尽可能满足教师、学生的要求，达到较好的教学效果 。

3 用遗传算法解决排课问题

3.1 排课问题中的对象描述

1）教师

■

2）学生组（大班）

■

3）教室

■

4）课程

■

5）教学班

■

3.2 染色体编码及适应度函数

为了更灵活的进行染色体编码，我们假定每周上课时间为周一至周五共五天，而每天从上午9点至晚上9点共十二个小时。规定一小时为一时间片段。我们可以定义一个大小为12*5*教室数量的向量，并使用哈希表存放上课的班级、时间及教室。

遗传算法的进化过程是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。本文中，我们仅考虑硬件约束方面的因素，在本研究中,适应度函数的设计思想是由于课表问题的优化目标有多个，同时约束也有多个，因此采用多目标化和适应度函数相结合的个体适应度评价函数[8]。

每个教学班级有0――5的得分；

如果教学班级使用矛教室，就增加分值；

如果上课教室需要电脑并且安排上课的教室里有电脑，或者上课教室不需要电脑，就增加分值；

如果安排上课的教室没有足够的座位，就增加分值；

如果教师在上课时间没有其它的课程，我们再一次增加分值；

如果学生在上课时间没有其它的课程，我们就增加分值；

如果教学班级在任一时间间隔点破坏了上述规则，不再增加分值。

因此，我们可以定义适应度的计算公式如下：

■

其中， schedule_score代表所有教学班级总得分数， Maximum_score=教学班级数*5，适应度值为0~1之间的单精度浮点型值。

3.3 交叉和变异操作

交叉操作就是对选取的两个父个体哈希表中数据进行组合，然后根据新的哈希表中的内容创建向量。交叉操作对随机产生的部分父个体哈希图进行分裂。分裂的部分由染色体特征中交叉点的数量决定。最终从父个体交替复制到新的染色体中，形成新的向量。

变异操作是很简单的。它是随机的选取课程然后随机的放入所选择的时间段。课程随机移动的数量由变异的染色体特征决定。

4 结论

本文在对遗传算法研究的基础上设计实现了高校智能排课系统。并对传统的编码模式进行了有效的改进。从排课的结果分析得出所编排的课程表满足排课原则，有效解决冲突问题，课时安排比较均匀。并且这种编码模式具有较高的扩展性，算法的性能有待于进一步提高。

参考文献：

[1] GAREY M R, JOHNSON D S, Compute and Intractability: A guide to the theory of NP completeness[M].San Francisco: W.H.Freeman & Co Ltd,1979.

[2] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[3] SAFAAI D,SIGERU O. Incorporating constrain propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence,1999,12(3):241-253.

[4] 滕姿,邓辉文,杨久俊.基于遗传算法的排课系统的设计与实现[J].计算机应用,2007,27(12):199-204.

[5] 苏仰娜.基于遗传算法的优化排课系统[J].河南大学学报:自然科学版,2005,35(3):47-50.

[6] 杨宇.高校排课系统理论研究与开发遗传算法在课表问题中的应用[M].北京:北京理工大学出版社,2003:35-67.

[7] 王健,董改芳,许道云.自动排课系统的模型与实现[J].贵州大学学报:自然科学版,2004,21(2):34-36.

[8] 胡义伟,谢勇,郑金华.基于遗传算法的综合性大学排课系统研究[J].中国教育信息化,2007,(11):54-55.