基于遗传算法的课程表中教师编码的优化

2011-10-17陈娟韩娜

网络安全技术与应用 2011年2期

陈娟韩娜

1 山西大学商务学院山西 030031

2 黑龙江科技学院黑龙江 150027

0 引言

排课算法设计的优劣是评价教务管理水平高低的一个重要标志之一。目前排课的算法有很多种，比较常用的有遗传算法、贪心算法、回溯算法等。排课问题是一个有约束的、多目标的组合优化问题。针对排课这个NP完全类问题进行深入的分析，研究科学排课需要遵循的原则以及所涉及的各种因素、问题，总结排课过程中所出现的各种时间、空间资源的冲突。本文根据课程表编排的特点，以实现时间和空间两种资源的优化为目标采用鲁棒性较好的遗传算法。针对遗传算法的收敛性较低的问题，对遗传算法进行了优化，构造了混合式的教师基因编码，该算法能够有效降低排课冲突。

1 排课研究

在排课的过程中，最关键是要编排一张科学性和技术性强的周课程表。但在这一过程中有许多制约因素及冲突。

在课程表编排问题中涉及到教师、班级、时间、教师、课程这五个相互制约的因素。排课问题的求解过程是，对任何一门课来说，要有一个合适的教师和合理的时间、教室以及班级与之对应，并且两两之间不能发生冲突，同时尽量满足实际需求。如：

（1）在同一时间给一个教师安排多个班级课程(合班除外)或同时讲授多门课程。

（2）在同一时间给一个教室安排多个班级上课(合班除外)或多位教师授课。

（3）在同一时间给一个班级安排多门课程或在多个教室上课。

（4）安排教室时，教室容纳人数小于实际上课人数。

这些冲突是排课过程中必须要解决的，所以要对冲突问题做透彻分析和适当处理是算法设计的基础。

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

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型。该算法按照“优胜劣汰、适者生存”的原则，通过快速随机搜索力求找到最优解或次优解。遗传算法因在解决各类非线性问题时表现出的鲁棒性、全局最优性、可并行处理性及高效率而深受广大软件开发爱好者喜爱。

2.1 设计思想

把课程和教师当作同一变量考虑，这样在编排课程表时只需将教师编码排入周课表。要打印课程表时，将教师编码改为课程名和教师姓名即可。设计步骤如下：

（1）教师编码：对每一门课程的任课教师进行编码。在教师编码中，每一门课程和授课教师姓名共同组合，以便于解决：“多课头”问题，“一师多班”冲突问题，“特别课”问题，“特定资源”冲突问题，“固定时段”问题。即：在教师编码中尽可能的把课程表的各种类型冲突解决掉。

（2）产生初始种群：使用数据表文件存放一个个体，其中记录行由班级名称和15个时间片字段所组成。这15个时间片字段的值将填入教师的编码，称为“基因”；一条记录行代表一个班级的课表，称为“染色体”；N个染色体组成的二维表格，称为“个体”；多个“个体”表组成“种群”(ZQ)。在个体表中，行表示每个班级的一周上课课程，用列表示该班的 T1-T15时间片。对每一班级的课表来说，首先把特定教学时间的教师编码填入时间片字段中。然后使用随机函数产生一个1-15的数，将该班的其它教师编码填入。如产生的随机函数对应的数组变量中已有数据，则重新分配，直到将所有教师编码无重复地填入表中。这样就有了一个初始的课程表。按种群的大小ZQS(班级数)，产生一定数量的初始表，构成初始种群。

（3）冲突检测和消除：对初始种群中的个体表进行冲突检测，如存在各类冲突，“一师多班”冲突、“特定资源”冲突等，则确定冲突的行、列，然后在它的同一行找另一个随机位置，将这两个位置的数互换，直到没有冲突存在。

（4）计算适应度值：按照适应度函数计算适应度值。

（5）选择操作：按照适应度值计算选择率和期望的选择数，进行选择产生下一代的种群。从选择数的算式可知，具有较高的适应度值的父本更有可能在下一代中产生一个或多个子代。

（6）杂交操作：对已选择好的个体两两配对，随机产生一个杂交行。该行即为：某个染色体(一个班级课表)，然后将父本中的这两行分别交换，产生二个新子代。

（7）变异操作：按概率决定变异的次数。对参与变异的个体随机选一行(某班课表)，在该行随机生成两个变异的位置，然后将这两个位置的教师编码互换。注意：当这两个编码中至少有一个是固定教学时段码时，则取消本次交换，重新执行步骤7，直到交换完成。

（8）冲突检测和消除：经过杂交和变异操作后，可能会产生冲突，因此要进行冲突检测，并解决冲突。

这样经过一次遗传算法迭代步骤，新一代种群的适应度值可能有所提高，问题的解决朝着最优解的方向前进了一步，只要将这个过程一直进行下去，最终将逼近全局最优解，而每一步的操作却是非常的简单，而且对问题的依赖性小。

2.2 构造基因编码和染色体

实施遗传算法的第一步，就是把与求解目标相关的实际参数进行基因编码，这是算法的关键与难点。

2.2.1 混合式教师编码

遗传算法能否顺利实现的关键是构造合适的基因结构。设定混合式的教师编码作为本系统遗传算法的“基因”。基因构成规则为：教师名㈩教学班序号㈩课程序号。课程特点，分别对应的位宽为：6+1+1+3共11位。

（1）教师姓名

由于教师在课表的构成元素中占据核心的地位，为使算法直观与简单化，故直接使用了教师的姓名在教师编码中，如张三、李四等，教师名取6位，不足6位用空格补足，超过6位则截取前6位字符。同名的教师必须给予区分。

（2）教学班序

为了解决“一师多班”问题，在教师名后加上一位自然数表示该教师的教学班序号，如用1表示该教师所教学的第一个班级，用2表示该教师所教学的第二个班级，依次类推。

（3）课程序号

为了解决“多课头”问题，在教师编码中加上一位自然数表示该教师的课程序号，如用1表示该教师所教授的第一门课程，用2表示该教师所教授的第二门课程，依次类推。

（4）课程特点

为了解决“特定资源”冲突问题，可在教师编码中加上三个字符表示该教师所教授的课程的特点。每一门课程都有其各自不同的特点，比如上机课需要在机房上课，英语口语需要在语音室上课。另外，有的教师可能因为某些原因需要特定的教学时段。因此，给每一门课程对应的教师编码中补充了三位表示课程特点的代码。

2.2.2 染色体的表示

对于每一门课程既可能只上一次(规定 2学时课占用一个时间片)，也可能上多次，如4学时、6学时等。上2学时课时，该教师编码只能出现1次，上4学时课时该教师编码出现2次，依次类推。

通过以上特点把班级与教室等同、课程与教师和功能室(机房、语音室等)等同的处理后，原课表的五要素(班级、教室、课程、时间、教师)转化为三要素(班级、课程、时间)。

为了更好地阐述排课遗传算法，定义排课遗传算法名词。

（1）“基因”：混合型的教师编码，即T-T15时间片中的值。

（2）“染色体”：班级名称与Tl-T15中的“基因”组成的串。

（3）“个体”：由BJS个染色体组合而成的二维数据表，即对应于一张课表。其中BJS为参与课表编排的班级总数。

（4）“种群”：由ZQS个个体构成。其中ZQS为种群大小。

2.3 产生初始种群

每一个“染色体”都是班级的一个课表，是数据库KCB(课程表)表中的一条记录行。首先把固定教学时间的教师编码填入该行中，然后使用随机函数产生一个 1～15的数，将该班的其它教师编码填入其中。如产生的随机数对应的时间片中己有数据，则重新产生，直到将所有教师编码无重复地填入该行中。这样就有了一条染色体。如此循环BJS次，产生了与班级数目对等的染色体数目。于是，一个初始个体便产生了。按种群规模的大小ZQS，产生一定数量的个体，每个个体都存放到一个序编号的表中，由这些个体组成初始种群。很明显，由上述方式产生的个体通常含大量的冲突。