遗传算法在大学排课问题中的应用

摘要：针对排课问题，基于遗传算法的特点分析了解决排课问题的可能性，介绍了排课原则，以及遗传算法在排课问题上的应用性研究，利用遗传算法进行编码，交叉、变异，以及进行冲突检测，用遗传算法解决这一复杂的NP问题。

关键词：排课　遗传算法　最优解　冲突检测

中图分类号：O24　文献标识码：A　文章编号：1007-3973(2010)09-167-02

当今时代，伴随着计算机技术的快速发展，许多繁琐的人工操作已经被计算机系统所取代。排课系统作为高校教务管理系统中最重要也最复杂的部分之一，已经成为国内外众多高校以及软件公司的研究课题，在这方面也取得了许多的理论成果和实现方法。因此，研究开发一个实用的排课系统具有十分重要的现实意义。

1、研究背景

随着我国教育体制改革的不断深入和发展，高校的办学规模逐年扩大，因此，编排一张适用的、科学的课表已经成为每一所高校在新学期开始之前必须进行的一项极其重要工作。简而言之，它具体的工作内容就是将课程、教师、教室和学生四者之间进行合理的调度分配，从而达到四者之间的完美结合，从而使整个教学活动能够正常、有序地顺利进行。

大学课表的编排不但数量多、规模大、涉及的因素多、限制条件多，而且结构复杂，要想编排出合理、科学的课表必然要消耗大量的时间与精力，它复杂性的原因在于排课中资源约束条件与特殊要求对有限时空目标的限制。由于近几年各个高校连年扩招，使得课程安排的工作量逐年增大，学校自身问题的逐步暴露，这也给课程安排增加了许多的难度，这些问题主要包括：教室资源的不足、师资力量的不足、多媒体教学设备的不足等，这些问题的出现对排课工作提出更高的要求。

伴随着科学技术的不断发展和提高，计算机具有的强大功能已经被人们所深刻地认识，计算机应用技术也已经逐渐进入人类社会的各个领域，同时在各个领域都发挥着非常重要的作用。作为计算机应用技术的一部分，通过计算机进行排课，具有手工排课无法比拟的优点，包括：排课速度快、省时省力、查找方便、检索迅速、可靠性较高、保密性较好、存储量较大、人工成本较低、使用寿命较长等。这些优点可以极大地提高排课管理工作的效率。排课系统是对一个教育单位而言是不可缺少的重要组成部分，排课效果的好坏直接影响到教学工作能否有序地、正常地开展，对于学校的领导来说也是一项至关重要的工作，因此排课系统必须为用户提供充足的信息以及快捷的查询手段。利用计算机进行排课操作，任何具有使用者都能够清晰的看到教学中的各种信息，可以高效、快速的工作，这不但减轻了教务人员手工排课的工作，而且极大提高了管理工作的效率，可以合理高效地分配、利用教学资源，间接地提高了教学质量，推进了教学活动的良性循环。因此，研究并改进一个排课系统具有十分重要的实际意义。

2、排课原则

排课问题实质上一种资源竞争问题。在排课过程中要全面考虑教师、课程、教室、时间、学生人数等多方面因素，做到统筹兼顾，才能排出即符合教学规律，又满足各方面要求的课程表。一个好的课表应该既能符合学校的管理要求，又能满足所有参与者的基本要求，尽量使绝大多数课程的安排能够令学校师生满意。为了达到这样的目的，在排课中必须遵守以下六个基本原则：

(1)在同一时间段内，一位教师只能安排一门课程。

(2)在同一时间段内，一个班级只能安排一门课程。

(3)在同一时间段内，一间教室只能安排一门课程。

(4)根据能提供的教室总数安排同一时间段内安排的课程总数，二者要相适应。

(5)每门课程的学生人数不应大于所安排教室的座位数，二者也要相适应。

(6)多媒体教室应合理安排，因为有的科目用多媒体设备教学的效果比较好，但是有的科目并不需要多媒体教室，如果安排了多媒体，就造成了教学资源的浪费。

同时，为了使排出的课表更具人性化、更合理、更科学，排课还需要考虑以下五个因素：

(1)尽可能保证同一个班级连续的两门课之间更换教室的机率最小，或就近安排。

(2)每门课程在一周内的上课时间尽可能合理分布。

(3)同一门课程的不同上课时间应尽可能安排在同一间教室，同时要隔一天以上再安排，以给任课教师留出充足的备课和批改作业的时间，使学生也有足够的时间复习和消化所学的内容，并有时间预习下次课的内容。

(4)学生每天必修课的安排尽可能趋于合理、平衡，应尽量避免出现全天有课，而第二天一天没课的情况。

(5)满足个别教师(如外聘教师)的特殊上课时间要求。

3、遗传算法在排课问题中的应用

遗传算法应用类似基因演化的循环过程，它的演算过程如下：

(1)根据排课的因素产生相关基因编码和染色体，并随机产生一定数目的初始种群，即一定数目的班级课程表。

(2)对个体，即班级课程表适应度进行评估，如果个体的适应度与优化准则相符，则输出最佳个体和它所代表的最优解，并结束计算，否则进入第(3)步。

(3)依据适应度情况选择再生个体。

(4)按照一定的交叉概率及交叉方法生成新个体。

(5)按照一定的变异概率及变异方法生成新个体。

(6)由交叉和变异产生新一代种群，之后返回第(2)步，最后进行冲突检测与消除。

通常可利用编码技术对变量进行编码，将变量转化成适合群体进化的表达形式。对目标函数进行处理操作，使其能够蕴含遗传算法的适应度函数。这样，在群体进化的过程之中，适应度就能够反映模型的目标函数。当群体进化结束的时候，适应度值最大的那个个体对应的目标函数值最小，这个个体即为最优解。最佳个体的产生过程是这样的：首先产生一个初始化种群，然后对初始化种群中的每一个个体进行适应度的计算，得出个体对环境的适应程度。计算后的这个个体能否满足准则判定，如果能够满足，那么算法就找到了这个个体并停止计算，如果不满足准则判定，那么算法将会对这个种群进行选择、交叉、变异等相关操作。遗传操作的目的是从初始化种群中筛选出较优的个体，之后进行演变，对演变后的子代群体，再重新进行优化准则的判定，如此循环下去，直到找到一个最优的个体，或者不满足其它循环条件为止。

约束条件和优化的目标有轻重缓急的分别，约束条件必须满足，优先级别必须最高，同时，各种优化目标之间也有优先级的分别，应尽量满足级别较高的优化目标。将它们都转化成罚值，而其罚值权则是不同的，高一级的罚值权比所有低级的罚值的和值还要大。由此可以得出，采用静态定标罚值权的方法是不可取的，因此我们采用动态罚值权的定标方法。遗传进化在进行选择的操作过程中，我们着眼于目标函数或者适应度函数的相对值而并不关心它的绝对值，确定这个个体目标函数的真正目的在于确定该个体在群体中的优劣，因此我们可以根据整个群体情况进行罚值权的统一定标，把各级的罚值用向量进行表示，此时，目标函数就是各级罚值的带权和。

如果想终止可以采用以下方法：

(1)给定一个迭代步数；

(2)当设定与估计的最优解的距离小于某个范围时，就终止搜索：

(3)当与最优解的距离连续若干步保持不变时，就终止搜索。

排课问题同样是一个N-P问题，无论应用哪种方法冲突问题的出现都不可能避免。但是，解决冲突问题的方法有很多种，这里采用一种利用二进制0、1矩阵检测冲突的方法。在冲突检测过程中其基本的约束条件为：

(1)任何教师在同一时间最多只能安排一门课。

(2)任何班级在同一时间最多只能安排一门课。

(3)任何教室在同一时间最多只能有一门课程被安排。

为了避免冲突的出现，在本系统的设计、实现过程中引进了冲突检测函数，保证当排完一位教师的所有相关课程后，系统就会通过该冲突检测函数对这位教师课程安排的冲突情况进行检测并做出相应的修正。

参考文献：

[1]毕晓君，信息智能处理技术[M]，北京：电子工业出版社，2010

[2]陈强，通用高校排课算法研究[J]，科技广场，2006年第07期

[3]张文修，粱怡，遗传算法的数学基础(第2版)[M]，西安：西 安交通大学出版社，2003

[4]潘以锋，高校智能排课系统的算法[J]，上海师范大学学报(自然科学版)，2006，(10)