严 宏

(1.中国民用航空飞行学院,四川 广汉 618307;2.四川大学 视觉合成图形图像技术国家重点学科实验室,四川 成都 610064)

教学资源配置优化中遗传算法的应用与改进

严 宏1,2

(1.中国民用航空飞行学院,四川 广汉 618307;2.四川大学 视觉合成图形图像技术国家重点学科实验室,四川 成都 610064)

对于临时新增教学任务，教学资源安排不同于学期开始前的教学资源配置，通常具有特定的配置需求。在教学资源有限的情况下，为了使新增教学班级配置的教室更加一致或接近，避免频繁变动教室给教学带来的不便，使用遗传算法进行教室资源的分配，并根据应用需求进行了改进。其中设计了更加适宜的十进制编码，提出的适应度函数能有效地对教室资源的一致或接近程度进行量化计算。根据染色体编码特点和优化目标，对遗传算子进行选择和改进，特别对单点交叉进行改进尽可能地提高交叉后的适应度，同时保持种群的多样性。实验结果表明，改进的遗传算法相对于标准遗传算法在用时更少的情况下得到的教学资源分配更加满足优化目标，计算效率得以提高，并且成功应用于实际的教学资源配置。

资源配置；遗传算法；十进制编码；适应度函数；交叉算子

0 引 言

近年来，随着部分高校招生专业的新增和招生规模的扩大，在一时难以增加相关教学资源的情况下，如何高效利用现有教学资源已成为教学实施过程中亟需解决的问题，关系着教学质量的保证和提高。教学资源配置的高效合理除了在学期开始前的排课过程中需要考虑外，对于开学后临时增加的教学计划，比如在职人员培训班、补修班或者重修班，由于此时教学资源更为有限，更需要进行资源的配置优化。从本质上讲，这些新增教学班级的安排其实是排课问题，而排课问题已被S. Even以及Cooper等证明为NP完全问题[1-2]。对于这类完全多项式非确定性问题，虽然可以在多项式时间内进行验算，然后再使用穷举法得到问题的解，但是这种方式下计算时间随问题复杂程度呈指数增长，因此这种求解算法不具有实际的应用价值。为了满足实际应用中对于计算性能的要求，对于NP完全问题通常采用求近似解的策略，此类算法中的遗传算法正是通过模拟自然进化过程搜索近似最优解，具有成熟的理论作为基础，应用较为广泛。

由美国的J. Holland教授在1975年提出的遗传算法[3]借鉴了基因遗传和生物进化的思想，通过选择、交叉、变异等遗传算子使种群不断进化，从而得到局部最优解或全局最优解。它是一种有效的随机搜索优化算法，具有并行性、自适应和学习性、鲁棒性以及易于与其他算法结合改进的特点，被广泛用于排课这类资源配置的组合优化问题。

文献[4]提出了遗传算法在课程安排问题中多点式搜索和优化方法；文献[5]论述了使用遗传算法解决排课问题中教师优先权的问题；文献[6]在遗传算法中引入排课规则解决了按优先级排课的问题；文献[7]在遗传算法应用于排课过程中提出优势群体有限策略和最优个体替换策略；文献[8]对用于排课系统的遗传算法在染色体编码和交叉变异概率选择方面进行了改进；文献[9]主要针对多校区排课问题进行优化；文献[10]在遗传算法中采用了群体优势策略。

文中论述的新增教学班级的教学资源配置优化问题虽然在实质上为排课问题，但是不同于多个班级的整体性排课，在应用环境及优化目标方面存在区别，比如上课时间事先已经确定和需要尽量固定的教室，难以完全利用针对整体性排课的编码方式、适应度函数以及交叉和变异算子，需要进行改进以便更好地符合应用需求。

1 数学模型和优化目标

1.1 数学模型

教学资源配置在教学过程中一项常见的工作就是进行课程安排，而排课涉及到的教学资源主要是教师、教室、课程、班级和上课时段。在此设定条件下，排课过程中教学资源配置优化问题可以描述为求构成解空间的五元组(C,O,T,R,S)。其中,C表示班级，O表示课程，T表示教师，R表示教室，S表示上课时段。

对于上述开学后临时增加的教学计划安排问题，由于教学资源的有限性，在新增教学班级的教学资源配置优化时必然存在资源的约束性，其中与现有排课数据之间存在上课时段和教室使用方面的约束关系。对应于现有排课数据和新增教学班级安排的两个五元组(Ci,Oi,Ti,Ri,Si)和(Cj,Oj,Tj,Rj,Sj)，必须满足如下关系：

Si=Sj→Ti≠Tj

(1)

Si=Sj→Ri≠Rj

(2)

上述两个关系式中，式(1)表示不同教学班级在同一时段的教师不应相同，否则造成冲突，同样式(2)表示不同教学班级在同一时段安排的教室应该分属不同的教室。在实际的教学资源配置过程中，对于这类新增的教学班级，通常已通过教师上课时间的协调或外聘教师等方法做好上课时段和上课教师的安排，那么上述约束关系式(1)可以不予考虑，而约束关系式(2)必须满足，否则将引起教室使用方面的冲突。

1.2 优化目标

对于这类新增的教学班级，由于讲授的内容和参加学习的人员早已确定，对应于五元组(C,O,T,R,S)中课程O和班级C的值得以确定，而从以上论述可知对于新增教学班级的上课时段和上课教师已做好安排，即五元组(C,O,T,R,S)中上课时段S和教师T的值得以确定，那么就需要对五元组中还未确定的教室进行组合配置。

而对于这类新增教学班级的教室配置，满足上述式(2)这个硬性约束的解是可行解，求解的目标是从可行解中找出更加优化的解，优化的目标是尽量配置为同一教室或者相近的教室，也就是说最好将教室这个教学资源配置为同一教室，这样可以避免给参与教学的教师和学生带来教室变动的不便，也是为了尽量减少教室安排带来其他方面的事宜，如减轻物业管理工作量。在教室资源紧张难以配置为同一教室的情况下，不同时段配置的教室变动尽量减少，使教师和学生在教学任务的参与当中更加方便高效，这是文中使用遗传算法进行优化的目标，也是遗传算法中适应度函数设计的参考依据。

2 算法设计及流程

使用遗传算法求解问题通常包含如下的关键步骤：染色体编码、种群初始化、适应度函数的设计、选择操作、交叉操作、变异操作以及终止条件的确定。

2.1 可行解空间及染色体编码

在优化求解问题中，满足所有约束条件的解便是该问题的一个可行解，而所有的可行解便构成了可行解空间。优化解便是其中能够更好满足优化目标的可行解，因此寻求优化解需要确定可行解空间，非可行解即使能更好地满足优化目标也不能称之为优化解。

从上述论述可知，可行解中五元组(C,O,T,R,S)的C,O,T和S已确定，剩下R对应的教室应不和现有的排课数据冲突，而文中针对的教务管理系统能够提供接口获取在指定时段内空闲的所有教室，也就是说能获取上课时段S内满足约束的空闲教室R，从而组成五元组构成可行解。

为了便于描述并且不失一般性，假设新增教学班级有N个上课时段，这些时段按时间先后的顺序排序并表示成S1,S2,…,SN，那么可以通过系统接口获取各个上课时间段对应的空间教室集合，同样对应时间先后顺序依次表示为{R1},{R2},…,{RN}，依次选取各个集合中的教室组成五元组(Ci,Oi,Ti,Ri,Si)，通过这样的组合方式形成的所有五元组就构成了可行解空间。

遗传算法采用仿生过程搜索优化解，模拟的是基因重组与进化的过程，把待解决问题的解转换成特定形式的编码，这种形式编码中特定一段对应的称之为基因，这样若干基因中组成一个染色体，一个染色体便可以对应优化问题的一个解。染色体编码是把优化问题的解从其解空间中的形式转换到遗传算法所能处理的搜索空间中的形式，这个过程是应用遗传算法进行优化过程的首要步骤，关系到后续遗传操作算子的设计和效率,也和遗传算法的收敛速度紧密相关。

为了减小染色体编码的长度，缩小搜索空间，对于五元组中已确定的C,O,T和S不再编码，而只对各个上课时段的教室进行编码。为了实现存取的高效，将获取的各个时段空闲教室集合分别采用数组方式存储，那么对各个时段的配置教室就只需对相应的数组下标进行编码。文中采用十进制编码而并未采用最为常见的二进制编码方法[11]，原因在于二进制编码除了编码较长、搜索空间较大和编解码比较费时的缺点，还存在汉明悬崖(HammingCliff)的问题[12]，即相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越，而使用十进制编码对于数组下标来说更加直接高效。具体的编码方式为每一个可行解对应的染色体由多个基因构成，每个基因对应课程安排中的一个上课时段，其十进制编码经过解码转换后为对应时段空闲教室集合中配置教室的所在下标。染色体的编码方式和空闲教室集合的存储方式如图1所示。

图1 染色体的编码方式和空闲教室集合的存储方式

基因编码的十进制整数Di并未直接用于表示所选教室的下标Ei，而是需要进行如下转换：

Ei=DiMODAi

其中，Ai为基因对应时段空闲教室集合中教室的总数，即存储教室集合的数组大小。

由于每个时段的空闲教室总数不同，那么每个基因对应数组的大小不一，选择这种取模的方式，可以在随机生成初始种群和后续交叉及变异操作中不用分别考虑每个数组的下标越界问题，编码和转换的方法更加统一和高效。

2.2 初始种群的生成

在确定好染色体编码方式后，遗传算法首先需要获得一组处于初始状态的染色体，这组染色体是后续选择、交叉、变异等操作的基础，是最终优化解获取的数据来源，通常被称为初始种群。进行初始种群的生成主要涉及两个方面的问题：种群规模的大小和初始种群各染色体的生成方式。其中，种群规模的大小直接影响到遗传算法的收敛性和计算效率。规模太小，染色体多样性的欠缺容易导致收敛到局部最优解；规模太大，计算复杂费时且难以收敛。

文中根据文献[12]中种群规模的建议范围，将群体规模设定为200。根据上述对编码方式的描述可知，在不考虑数组下标越界问题的情况下，可以使用随机生成的十进制无符号整数作为基因编码，按照新增教学计划所需的上课时段总数生成相同数量的基因，然后将这些基因连接从而生成初始种群中的染色体。

2.3 适应度函数的实现

使用遗传算法进行优化求解，目标是为了获取更好满足优化目标的可行解，体现为通过遗传算法使初始种群通过进化后得到对于优化目标来说更加优秀的染色体，在此过程中就需要度量指标去计算染色体的优化程度。在遗传算法的命名惯例中，适应度是群体中各个染色体优劣程度的量化指标。文中优化的目标是让可行解中各个时段选择的教室尽量一致或接近，其程度可以通过教学楼、楼层以及楼层中位置这三个参数计算。这个问题可以分解为逐次分析每个时段与后续时段在教室配置方面的一致或接近程度，并使用以下目标函数进行量化：

f(Ri,Ri+1)=0.5b(Ri,Ri+1)+0.3e(Ri,Ri+1)+ 0.2m(Ri,Ri+1)

其中，Ri和Ri+1分别表示前后两个时段配置的教室；b(Ri,Ri+1)、e(Ri,Ri+1)和m(Ri,Ri+1)三个函数分别对前后两个教室的所在教学楼、所在楼层以及楼层中位置的一致或接近程度进行量化计算，前面对应的系数可以实现按权重求和，系数对应的权重目前根据实际工作经验对教学楼、所在楼层以及楼层中位置的重要性来确定，待以后研究中再进行优化改进。f(Ri,Ri+1)的值越小，表示前后两个教室越接近，当f(Ri,Ri+1)的值为零时，前后两个教室相同。而遗传算法中染色体的适应度越大，该染色体对应可行解能更好地满足优化目标，也就是说染色体表示各个时段配置的教室更加接近，所以需要将目标函数进行适当的转换形成如下的适应度函数：

Fit(R1,R2,…,RN)=

该适应度函数的设计思路为依次将前N-1个时段的目标函数f累加，然后除以N-1求平均值，这样针对上课时段总数不同的情况更加公平，最后通过乘以系数β(文中取0.05)进行指数比例变换。这样当各个时段配置的教室越接近时，适应度越大，特别是在所有配置的教室相同时，适应度取得理想的最大值1，可以确定得到该种情况下教学资源配置的最优解。

2.4 遗传算子的实现

2.4.1 选择算子

从本质上讲，达尔文的自然选择学说是遗传算法的理论基础，其中选择是在群体中选择生命力强的个体产生新的群体的过程，为保留优良个体和种群多样性提供驱动力。目前，遗传算法中常用的选择算子有轮盘赌选择[13]、随机竞争选择、最佳保留选择、稳态复制等。

文中使用最佳保留选择作为选择算子，具体操作为：将所有个体按适应度从大到小排序，然后按一定比例选出前面适应度较大的个体直接复制到下一代，不足种群规模的个体用随机生成的方法补充。最佳保留选择的实现简单高效，既保留了进化过程中出现的优良个体并及时淘汰不良个体，又实现了个体的多样性，避免了优化过程过早地陷入局部最优解。文中使用的最佳保留选择比例因子为0.3。

2.4.2 交叉算子

模仿两个染色体通过交配而重组形成新的个体的过程，遗传算法使用交叉算子来产生新的染色体，是区别于其他进化算法的重要特征。交叉算子的设计包括交叉点定位和基因交换方式两方面的内容。标准遗传算法中的交叉算子是使用单点交叉[14]，文中实现也采用此交叉算子并在如何确定交叉点的位置方面进行了改进，不再简单地直接使用随机确定的交叉点位置，而是从交换后是否可以得到一个适应度更大的染色体来考虑，具体流程描述如下：

(1)对于随机配对的两个染色体a和b，按交叉概率Pc进行下面的交叉互换操作。

(2)随机选择一个位置作为参考点i。

(3)从参考点i开始向后搜索一个位置k使得交叉配对的两个染色体a和b满足条件：

(4)如果向后未找到符合条件的位置k，则从参考点i向前搜索符合步骤(3)中条件的位置k；

(5)如果向前还是未找到符合条件的位置k，则k=i；

(6)使用k为交叉点位置，交换交叉配对的两个染色体的部分基因。

使用上述交叉算子，除了未找到符合条件的交叉点k的情况，都能够使交叉互换后的一个染色体在位置k和k+1上对应的教室相同，从而进一步提高适应度，得到更加优良的个体。另外对于交叉互换后的另一个染色体也保持了原有的单点交叉方式，用于维持种群的多样性。

2.4.3 变异算子

模仿生物遗传和进化过程中某些基因发生变异的环节，遗传算法使用变异算子在种群中产生出新的染色体，可以改善局部搜索能力和维持群体的多样性。针对文中染色体采用十进制编码的特点，为了更好地改善局部搜索能力以及防止搜索陷入局部次优解，设计的变异算子在借鉴现有常用变异算子的基础上实现针对性的改进，流程如下：

(1)按变异概率Pm选取进行变异操作的染色体；

(2)随机选择一个位置作为变异位置；

(3)根据位置的奇偶性分别对变异位置的十进制编码进行加1和减1，然后按编码范围取模，将所得结果替代原有十进制编码。

2.5 终止条件的确定

在种群的进化过程中需要制定优化终止的条件，从而能在适当的时间内得到优化解，满足计算性能方面的可行性。文中在常见的进化终止代数的基础上，还考虑到可能出现所有配置教室相同的最优解，设计的适应度函数将会出现最大值1，因此制定了以下两个条件：

(1)进化代数达到指定的最大进化代数；

(2)出现了适应度等于1的个体。

当这两个条件其中之一满足时，种群的进化过程终止，输出种群中适应度最大的个体对应的优化解。

2.6 遗传算法的实现

在上述几个遗传算法重要步骤的基础上，进一步确定各个步骤的执行条件和顺序，总结实现的遗传算法流程，如图2所示。

图2 遗传算法流程

3 实验结果及分析

将针对文中应用环境进行改进的遗传算法(DGA)和标准遗传算法(SGA)进行实验对比，试验中SGA使用和DGA一样的适应度函数，但是在染色体编码方面使用二进制编码，编码方法将DGA初始种群中的十进制编码转换为二进制编码，这样可以使对比实验在相同初始种群的条件下进行，更加公平。

SGA中选择算子使用经典遗传算法中常采用的轮盘赌选择[13]，交叉算子和变异算子分别使用针对二进制编码单点交叉和基本位变异。另外，DGA和SGA使用如下相同的参数：上课时段数为32，群体规模设为200，最大进化代数设为500，交叉概率Pc设为0.6，变异概率Pm设为0.05。

为了对比DGA与SGA在进化中的适应度变化情况，每进化5代就记录种群中的最大适应度。考虑到遗传算法的随机性，DGA与SGA的对比实验一共进行20次，取这20次数据的平均值作对比，结果如图3所示。

从图3中可以看出，DGA相对于SGA在进化过程中能产生更为优化的解，而且SGA相对较快地收敛到一个适应度较小的解，体现了SGA早熟的缺点。

为了对比DGA和SGA的用时，在上述实验中每进化5代就记录一个总共耗费时间，对比结果如图4所示。

由图4得知，DGA相对于SGA用时更少，主要原因在于针对文中应用环境，十进制编码相对二进制编码编解码更加简单高效，提高了计算效率，而且十进制编码长度更短，这也降低了算法的空间复杂度。

图3 DGA和SGA的适应度对比

图4 DGA和SGA的用时对比

4 结束语

改进后的遗传算法除了已在中国民航飞行学院教学工作中满足了实际应用需求，还在对比试验中相对于标准遗传算法用时更少，而且得到的解更加优化。另外，量化教室配置优化程度的适应度函数可以在不同应用需求下进行改进，比如权重系数调整。这种根据应用环境特点改进遗传算法的思路还可以针对其他类型的教学资源配置优化进行功能拓展。

[1]EvenS,ItaiA,ShamirA.Onthecomplexityoftimetableandmulti-commodityflowproblems[C]//ProcofIEEEsymposiumonfoundationsofcomputerscience.[s.l.]:IEEE,1975:184-193.

[2]TimB,CooperJ,KingstonH.Thecomplexityoftimetableconstructionproblems[C]//ProcofICPTAT’95.[s.l.]:[s.n.],1995.

[3]HollandJH.Adaptationinnatureandartificialsystems[M].Michigan:UniversityofMichiganPress,1975.

[4]LimkarS,KhalwadekarA,TekaleA,etal.Geneticalgorithm:paradigmshiftoveratraditionalapproachoftimetablescheduling[C]//Proceedingsofthe3rdinternationalconferenceonfrontiersofintelligentcomputing:theoryandapplications.[s.

l.]:Springer,2015:771-780.

[5]SbeityI,DboukM,KobeissiH.Combiningtheanalyticalhierarchyprocessandthegeneticalgorithmtosolvethetimetableproblem[J].EprintArxiv,2014,5(4):39-50.

[6] 郭俊恩,刁文广.基于规则和遗传算法的实验室排课算法研究[J].河南大学学报:自然科学版,2014,44(3):355-359.

[7] 刘仁诚,冯秀兰.基于改进遗传算法的排课问题研究[J].科技通报,2013,29(5):160-163.

[8] 于 娟,尹积栋.面向排课系统的遗传算法改进研究[J].太原理工大学学报,2012,43(5):572-574.

[9] 石 慧,彭晓红,邬志红,等.求解多校区排课问题的基因对交叉遗传算法[J].计算机工程与应用,2010,46(18):240-243.

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

[11] 孙 彤,郭倩倩.基于新型免疫遗传算法的高校排课仿真研究[J].计算机仿真,2012,29(2):386-391.

[12] 雷英杰,张善文.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2014.

[13] 祝勇仁,曹焕亚.应用遗传算法求解排课问题[J].计算机应用与软件,2007,24(12):130-132.

[14] 刘青凤.遗传算法在教学任务分配中的应用[J].制造业自动化,2010,32(10):203-205.

Application and Improvement of Genetic Algorithm for Optimization in Allocating Teaching Resources

YAN Hong1,2

(1.Civil Aviation Flight University of China,Guanghan 618307,China;2.National Key Laboratory of Fundamental Science on Synthetic Vision,Sichuan University,Chengdu 610064,China)

For temporarily added curriculum,the arrangement of teaching resources which usually has some specific requirements is different from that done before a semester begins.In the case of limited teaching resources,an improved genetic algorithm was proposed for optimizing the consistency and nearness of the classrooms allocated for temporary curriculum,with aim to avoid the inconvenience to teaching caused by frequent change of classrooms.Based on the requirement of the given application in this paper,a more efficient decimal encoding was developed.Correspondingly,a suitable fitness function was proposed to quantitatively calculate the consistency and nearness of the allocated classrooms.According to the characteristic of the chromosome encoding and the optimization goal,the algorithm selected existing genetic operators and improved them,especially the modified one-point crossover that attempts to enhance the fitness value and maintain the diversity of population.The experimental results show that the improved genetic algorithm,which has been successfully applied,can achieve more optimal solution within a shorter period of time when compared with the standard genetic algorithm.

resources allocation;genetic algorithm;decimal encoding;fitness function;crossover operator

2015-05-20

2015-08-21

时间：2016-01-

中国民用航空局民航科技创新引导资金(C2013041)

严 宏(1984-),男,讲师,博士研究生,研究方向为最优化计算、机器学习。

TP18

A

1673-629X(2016)03-0130-05

10.3969/j.issn.1673-629X.2016.03.031