摘 要：遗传算法是当前计算机领域的热门课题，将这一热门课题引入到教育技术学领域中来加以研究应用。排课问题本身是一个资源分配问题，随着多媒体教室的功能日益增加，需要引入一种将教室设备作为影响授课因素之一的排课算法。分析了多媒体教室排课算法的数学模型、约束条件以及算法设计。

　　关键词： 遗传算法；多媒体教室；排课问题

　　随着国家对教育的投入逐渐加大以及各高校对现代教育技术设备的重视，目前国内大多数高校的普通教室均已换为多媒体教室。有些多媒体教室还配备有数字展示台或者高解析度的多媒体液晶投影机以及带触摸功能的投影白板等设备。还有一些多媒体教室安装有摄录像系统，即装配有摄像机和拾音话筒，可以用来对老师和学生的教学活动过程进行摄录，并将摄像所得的视频信号以及话筒采集的音频信号传送到中心控制室，然后后台的教育技术工作人员可以将信息记录储存或直播到其他教学场所，从而实现大范围的观摩传播[1]。

　　但是考虑到实际需要，为所有多媒体教室全部配置这么多的电教设备是非常浪费的。因此大多数的多媒体教室仍然遵循着“少而精”的原则，只配备有最基本的设备包括：计算机、投影机、幕布、功放和话筒音箱。这就对传统的排课算法提出了一个新的要求，及要将需要特殊教学设备的教师排到有这些设备的多媒体教室之中。

1 高校多媒体教室排课问题分析以及描述

　　1.1 高校多媒体教室排课目标

　　高校多媒体教室的排课问题实际上是一个资源分配的问题,其本质就是要在满足一定条件的前提下，将教学资源分配给各个需要的教师[2]。即将有授课任务的教师、普通多媒体教室、带特殊设备的多媒体教室、班级、课程安排在一周内不发生任何冲突的授课时间段里。

　1.2 影响多媒体教室排课的若干因素以及约束条件

　　在进行多媒体教室排课时，需要考虑如下约束条件以及若干因素[3]。

　　⑴排课算法的约束条件

　　约束条件可以分为硬性约束条件和软性约束条件两类[4]，硬性约束条件是指排课时所必须遵循的条件，有如下4条：①某一班级在某一授课时段内只能安排不大于一门课的课程任务；②某一多媒体教室在某一授课时段内只能安排不大于一门课的课程任务；③一个教师在某一授课时段内不能同时安排有一门以上的课程任务；④某些课程对于多媒体教室的特殊要求应得到满足，并且教室的容量要大于上课的学生数。

　　软性约束条件是指在排课过程中需要尽量满足，但是无法满足时亦可以接受的条件。比如：①尽量满足教师对于授课时间和授课教室的要求；②要尽量将人文类课程与自然科学类学科交叉安排；理论课与实践课交叉安排；同一门课程的授课时间不宜安排过密，应进行间断而不要连排；③将课程尽量安排在授课效果比较好的授课时段内，如上午8:00~11:30的授课时段，或下午14:00~15:30的授课时段内；④尽量将课程安排在授课效果比较好，设备比较新的多媒体教室内。软性约束条件虽然不是一定要满足的，但它却是衡量一个排课算法优劣的重要条件。

　　⑵排课算法的若干因素

　　在排课时需要涉及如下若干因素。

　　①授课时间段：在排课时需要以教学周为单位来安排授课时间，而教学周的每一天又可分为上午一、二节，三、四节，下午五、六节，七、八节，晚上九、十、十一节，授课的最小单位是节，一门课的授课时间通常是两节或三节。

　　②多媒体教室：首先要保证教室的容量要大于上课学生的数量，其次要保证多媒体教室内拥有上这门课的必要设备。

　　③上课教师：每一个教师都要有一个唯一的编号。

　　④授课班级：每一个班级都有一个唯一的编号并有学生的数量信息。

2 交互式遗传算法的高校自动排课模型设计

　　2.1 交互式遗传算法简介

　　现在智能优化是目前国内信息学科的一个研究热点，而交互式遗传算法又是智能优化的研究方向之一。交互式遗传算法的主要特点是将传统的遗传算法进化机制与人的智能评价相结合，从而解决一些传统算法所不能解决的隐式性能指标优化问题[5]。

　　2.2 各个因素的数学模型建立

　　可以把学校内的各个班级定义为集合C={c1,c2,c3,…,cc},并且每个班级对应着{p1,p2,p3,…,pc}个学生数。

　　课程集合K={k1,k2,k3,…,kk},这里需要将所有的课程都编上唯一的号，即使同一教师为不同班级上的同一门课也要有自己的编号，这样做可以简化问题的求解。并且每一门课程都要有自己对于多媒体教室设备的要求{y1,y2,y3,…,yk}。

　　多媒体教室集合R={r1,r2,r3,…,rr},以及各个教室的最大容量{m1,m2,m3,…,mr}，并且可以根据多媒体教室的设备多少给他们加上一个设备属性{z1,z2,z3,…,zr}。并且可以将多媒体教室分级，即包含设备最全的给与其等级5，其次的分别为4,3,2,1。这样定义的课程对于设备的要求属性{y1,y2,y3,…,yk}以及多媒体教室的设备属性{z1,z2,z3,…,zr}就均可用1~5的数值来进行赋值。

　　上课教师定义为集合T={t1,t2,…,tt}，并且每一位老师都对应着集合K内的若干课程。

　　授课时间段集合S={s1,s2,s3,…,ss}。在这里考虑求解问题的需要，求出授课时间段集合S与多媒体教室集合R的笛卡尔积为：D=S×R=(s1,r1),(s1,r2),(s1,r3),…,(s2,r2),…，(ss,rr)。这样多媒体教室排课问题就可以转化为一个目标分配问题，也就是将课程集合K分配到授课时间段集合S与多媒体教室集合R的笛卡尔积集合D之中，亦可以将D写为{d11,d12,d13,…,d1r,…,dsr}。

2.3 约束条件的数学模型

　　之前所规定的硬性约束条件也可以转化为如下的数学模型即：

。即任意班级Cc在任意一个多媒体教室的某一授课时段Dsr内能上课程数目为1或者是0。而由于对课程编号时已经将同一教师为不同班级(非合班课程)上的同一门课也分别编号，因此也就排除了一个教师在某一授课时段内同时安排有一门以上的课程任务的可能。而且采用授课时间段集合S与多媒体教室集合R的笛卡尔积来进行计算也保证了某一多媒体教室在某一授课时段内只能安排不大于一门课的课程任务。

　　并且还要满足多媒体教室的容量mr≥班级Cc所对应着的学生个数Pc。而且多媒体教室的设备属性Zr应当≥课程Kk对于教室设备的要求属性Yk。

3 算法设计

　　3.1 编码方案

　　本文跟据实际情况将编码结构采用如表1所示的形式。

　　在单个染色体中，根据实际情况可以对教师ID、班级ID、课程ID、时间ID及多媒体教室ID，分别赋予不同位数十进制数据。由于本校在用的正方教务系统设计教师ID为6位十进制数，而班级ID为7位十进制数，课程ID为9位十进制数，而时间ID需要给与其6位十进制数，而多媒体教室ID则根据实际情况仅需要4位十进制数。这样例如一个编号为200021的教师，如果要对B11英语1班编号为1111011的同学教授“现代教育技术”编号为048972635这门课（现代教育技术，周学时4，总学时32，上课周数为1~8周），随机产生上课时间，并选择总人数以及教室设备等级符合课程要求的任意教室，即可产生染色体：“20002104897263511110111813331216”。其中最后面的181333表示上课时间是1~8周的周一下午一二节，周三下午一二节，1216表示多媒体教室编号为1号楼216教室。

　　这样按照如上的编码方式，仅需要让染色体的后8位产生交叉变异，就既不会影响教师教授本课程，也不会影响其他课程的数据。

　　3.2 优化方案

　　在完成编码之后，还需要设计一些适应度函数，来使得算法可以尽量满足软性约束条件，从而可以实现资源分配的最优效果。

　　⑴尽量满足教师对于授课时间和授课教室的要求。可以将教师的集合T={t1,t2,…,tt}按照职称加权，比如按照助教、讲师、副教授、教授，分别赋权1、2、3、4，然后将其意愿分为α1=0和α2=1，表示不愿意和愿意。 排课的最后目标应实现max(f1)=Σ(ti×αj)。

　　⑵将课程尽量安排在授课效果比较好的授课时段内。首先将课程k根据其类型和重要程度分别给予赋权ε={1,2,3,4}，然后将授课时间s为上午一二节，三四节和下午五六节的时间段赋权为2，其余赋权为1。 最后再从算法生成的结果中挑出符合max(f2)= Σ(k×s)的来获取下一段种群。

　　⑶同一门课程的授课时间不宜安排过密，应进行间断而不要连排。当一门课在一周内的授课节数≥4的时候，应当考虑将其分隔1天以上的时间来进行授课。这里保留第一条中根据课程重要程度而进行的赋权ε，并且引入新的集合θ={1,2,3,4}分别表示课程间隔为0天，3天，1天和2天。然后最终目标应当实现max(f3)= Σ(k ×θ)。

　　⑷要提高设备较新的教室的利用率。所用的思路同上述方法一样，也是根据多媒体教室R的设备属性赋值{z1,z2,z3,…,zr}，将尽量多的课程k(保留第一条中根据课程重要程度而进行的赋权ε)排在其中，以实现max(f4)= Σ{r×k}。

　　3.3 算法的实现

　　本算法的具体流程图如图1所示。

　　在具体实现上，可以通过英国The University of Sheffield所开发的基于MATLAB的遗传算法工具箱来完成[6]。

　　这里调用函数crttrp来完成种群初始化，schedule =crttrp(nind,FieldDR)可以创建一个随机实值矩阵，这里的nind制定了种群中的个体数量，FieldDR则限定了每个个体变量的边界。在本例中需要通过FieldDR来保证每一个个体都是符合上文所述的编码逻辑。

　　⑴满足停止准则。这里可以设计算法的迭代数，当完成最后一次迭代时，算法终止。

　　⑵计算个体适应值。在这里需要计算符合算法硬性条件和软性条件的最优值。

　　⑶选择。可以调用工具箱中的select函数来从种群schedule中选择优良个体，并将选择的个体返回到子种群selSC中。具体调用方法为selSC=select（sel_f, schedule,Fitnv,Ggap）,其中sel_f是一字符串，它包含低级选择的函数名，它决定函数进行选择的方式是sus(随机变量抽样)或者rws（轮盘赌选择）。这里采用sus即按照个体在当前种群中的适应度，fitnv为繁殖概率性选择个体。Fitnv是一个列向量，包含种群schedule中个体适应度的值，表明了每个个体被选择的与其概率。Ggap是一可选参数，指出了代沟，部分种群被复制。

　　⑷交叉。本例中只需要对染色体的后8位产生交叉变异即可，在这里选用两点交叉即指在个体编码串中设置两个交叉点，然后再进行部分基因交换。具体过程如图2所示。

　　在MATLAB工具箱中可以调用函数xovdp来实现，具体调用方法为newschedule=xovdp(oldschedule,xovr)，Xovr为一可选参数。

　　⑸变异。为了改善算法的局部搜索能力以及维持群体的多样性，避免早熟现象出现，需要对个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换。在MATLAB工具箱中可以调用函数mutate来实现。具体调用方法为newschedule=mutate(mut_f,oldschedule,FieldDR),mutate执行种群oldschedule中个体的变异，并在新种群中返回变异后的个体。

　　通过这些工具箱函数，就可以在MATLAB中实现本算法。

　　遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，是目前计算机科学方面的研究热点之一。而如何将这一技术运用到教育技术学领域中，让其运用到教育教学工作之中也是教育技术工作者所要关注的事情。教育技术工作者们不能仅限于成熟技术的移植，还应当考虑从算法层面来对目前的教育教学设备进行改良。

　　参考文献

　　[1] 辛蔚峰.高校信息技术应用成本—效益评估模型建构与分析[J].现代教育技术，2013（4）：16-20.

　　[2] Pillay N, Banzhaf W. A study of heuristic combinations for hyper-heuristic systems for the incapacitated examination timetabling problem[J]. European Journal of Operational Research ,2009,197(2):481-491.

　　[3]李红婵，户刚，朱颢东.基于群体优势遗传算法的高校排课问题研究[J]. 计算机工程与应用，2011,47(10):233-236.

　　[4] Zhang Defu, Liu Yongkai,Hallah R M. A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems[J].European Journal of Operational Research,2010,203(3):550-558.

　　[5] 巩敦卫，郝国生，周勇，等. 交互式遗传算法原理及其应用[M]. 北京：国防工业出版社，2007.

　　[6] 雷英杰，张善文，李续武，等.MATLAB遗传算法工具箱及应用[M]. 西安：西安电子科技大学出版社，2011.