遗传算法在自动排课中的应用研究

2012-05-12李英鹤

中国新技术新产品 2012年10期

李英鹤

（沈阳理工大学信息科学与工程学院，辽宁沈阳 110000）

排课问题在学校教学管理中十分重要，它是一个有约束的、多目标的组合优化问题，并且已经被证明为是一个NP完全问题。由于涉及信息较多且求解比较复杂资源的最优化配置不容易实现，因此使用计算机对排课信息进行管理，能够极大地提高学校教务管理的效率，也是各种体制学校管理科学化、现代化的重要条件。现在大多数的排课系统是以编程语言为实现语言，采用各种算法为实现手段，比如遗传算法、回溯算法、模拟退火算法等。作为对排课问题的探索，本文采用遗传算法的思想，提出一个课表方案的随机生成和优化算法，以期能够较大程度地反映实际排课情况和尽量达到多个目标最优。

1 排课问题分析

1.1 排课问题的因素

从手工排课的过程看出，排课问题需要考虑的条件很多，如周课时设置、课程信息、班级信息、教师信息、教室信息等等。从排课过程可能引起潜在冲突的角度，可以将排课问题涉及的因素考虑如下：

时间：在排课问题中涉及关于时间的概念有学年、学期、周、天、节。

课程：每个课程都有自己的编号、名称。每个课程都有指定的教师、教室等。某些课程由于上课班级较多难以协调或照顾教师要求等诸如此类原因，应该预先给定时间或教室。

教室：每个教室都有编号、门牌号和名称。每个教室在同一时间内只能接纳一门课程的授课，并且教室容量应该大于等于上课的人数。

班级：每个班级都有编号和名称。每个班级同一时间只能上一门课程。

教师：每个教师都有编号和姓名。每个教师同一时间只能上一门课程。

1.2 排课过程的约束条件

排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组合，以使教学正常进行。避免排课因素发生冲突是排课问题中要解决的核心问题。只有在满足全部约束条件和避免冲突的基础上，才能保证整个教学计划合理正常进行。而对教师、教室、学生及时间等资源进行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。

排课过程中常见的约束条件如表1所示：

1.3 排课问题的目标实现

排课问题是一个多目标的组合规划问题，要想制定出一个“合理、实用、有特色”的课表，必须保证所有的约束条件都不发生冲突。一套高质量的课表，在时间、教室资源、课程安排等很多方面都应该做到科学的安排，并且应该具有人性化的考虑。课表编排问题的难点在于：保证课表在时间及人员的分配上符合一切共性和个性要求，在此基础上，所有的课程都能够安排合适的时间和教室，使安排方案在各个目标上尽量达到全局最优。

遗传算法是1975年美国MIChiga大学的John.H.Holland教授及其学生们根据生物进化的模型提出的一种优化算法。作为一种随机的优化与搜索方法，遗传算法有两个主要特性：1智能性。即遗传算法在确定了编码方案、适应值函数及遗传算子以后，算法将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存概率，它是具有“潜在学习能力”的自适应搜索技术。2并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得遗传算法能以较少的计算获得较大的收益。正是由于遗传算法的这两个特性，使得遗传算法迅速被运用于求解组合优化的排课问题，且操作简单，可以更少地依赖于实际问题的情况，实现课表的优化。

2 遗传算法在课表编排中的应用

2.1 遗传算法的基本原理

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。一般的遗传算法都包含三个基本操作：复制、交叉、变异。

2.1.1 复制，是从一个旧种群中选择生命力强的个体字符串产生新种群的过程。复制操作过程中，目标函数是该字符串被复制或被淘汰的决定因素。遗传算法的每一代都是从复制开始的。

2.1.2 交叉，在由等待配对的字符串构成的匹配池中，将新复制产生字符串个体随机两两配对，然后随机地选择交叉点，对匹配的字符串进行交叉繁殖，产生一对新的字符串。

遗传算法的有效性主要来自复制和交叉操作，尤其是交叉在遗传算法中起着核心的作用。

2.1.3 变异，遗传算法中，变异就是某个字符串某一位的值偶然的随机的改变，即在某些特定位置上简单地把1变成0，或反之。变异操作可以起到恢复字符串字符位多样性的作用，并能适当地提高遗传算法的搜索效率。

2.2 遗传算法在课表编排中的设计

使用遗传算法编排课表，我们把课程和老师当作同一变量考虑，这样编排课表只需将教师编码排入周课表，在以后打印课表时，将教师编码改为课程名即可。于是我们设计以下步骤：对每一门任课教师进行编码；使用二维数组来构成初始群体；冲突的检验和消除；定义课表的适应度函数(x)(x∈{1,2,…,N}),其中x表示个体在群体中的位置。当函数值为0时，即找到了本次优化过程的最优值；复制操作：按照适配值计算选择率和期望的复制数；交叉操作：将种群中的个体配对产生的交叉点再分别交换；变异操作：将随机产生的同列的两个位置互换；再次进行冲突检测和消除，直至无冲突存在。

2.3 算法的实现

遗传算法结束后，可以得到综合效率函数值最好的个体。根据这个结果，即可生成相应的课程表。系统的流程分为以下几个主要的过程：（1）初始种群的产生：形成本学期教学信息二维表，对教师编码；产生染色体。（2）对各类冲突进行检测，如存在冲突则消除它。（3）计算适应度函数值、期望值及其复制数。（4）进行遗传操作。（5）可行课程表的产生。

这样，我们就有了一个课程表的数据库表。因此，可以打印其中某一班级的课程表或全校的课程表了。