基于改进的蚁群算法的教室管理优化问题

怀丽波，崔荣一，赵亚慧

(延边大学工学院 计算机科学与技术系，吉林 延吉 133002)

0 引言

近年来高校招生规模呈不断扩大趋势，使得许多高校都存在着学生数量多而相应的教室资源有限的情况，因此教室的安排是否合理直接影响到学校教育资源的有效利用.教室管理问题作为排课问题的子问题，主要完成课程的教室分配任务.排课问题作为一个多目标、带有模糊约束条件的组合优化问题，1975年E.nen等证明了其属于NP完全问题.目前，解决这个问题的方法有很多，主要有模拟退火算法、图着色算法、遗传算法、粒子群算法，以及几种算法的混合方法等[1-4].针对教室管理问题的优化，文献[5]给出了从课程表到教室调度表的实现方法，文献[6]针对减少教室流动性问题，提出固定一定教室比例的方法，但目前综合考虑教室管理优化问题的研究还很少.基于此，本文利用改进的蚁群算法对该问题进行研究.

1 教室管理问题的数学描述

教室管理问题主要涉及5个要素：时间、教师、教室、班级、课程.作为排课问题的一个子问题，教室管理优化问题假设时间、教师要素已经排好，故只涉及到3个硬性约束条件:①同一个教室在相同时间只能安排一门课；②每个教室的教室容量要大于上课班级的学生人数；③教室总数量在所有的时间里要满足课程总门数.

1.1 教室管理问题优化要点

针对教室管理的优化，本文研究主要集中在以下几个软约束条件：

1) 减少空闲座位，提高教室利用率；

2) 为提高学习效率，连续上课的同一班级尽量安排在同一教室，减少学生的课间流动性；

3) 选择教室时，尽量使教室资源集中使用，多余教室可作为自习室或社团活动室灵活使用；

4) 为使教室最大化利用，单周和双周同一时间上课的课元使用同一个教室.

1.2 教室管理优化问题的二部图模型

1.2.1构造二部图的节点

1) 课元结点GLCT由数组〈课程,班级,教师〉组成：课程集合包含课程代码、课程名称、上课时间、需要的教室类型等属性；班级有班级编号、名称、人数等属性；教师包括教师编号、姓名、所在部门、职称等属性.课元是最小单位，每个课元有不同的编号，每周一次以上的课按不同的课元处理.

2) 目标结点GPR由数组〈上课时间，教室〉组成：上课时间有〈单双周,星期,节次〉 3个属性；教室集合包含教室编号、名称、容量、教室类型等属性；同时需满足|GLCT|≪|GPR|.

1.2.2构造二部图的边和权值 作为教室管理优化问题，课元的上课时间已经确定，所以每个课元结点不是和所有的目标节点连边，二部图的边需要满足以下条件：①课元结点的上课时间和目标结点的上课时间相同；②教室的容量大于上课学生人数；③教室类型要匹配.

边的权值w(i,j)=教室容量-学生人数.教室管理优化问题转化为为每个课元结点寻找一个对应的目标节点，即转化为带权二部图的完备匹配问题.

2 改进的蚁群算法求解教室管理优化问题

蚁群算法是对蚂蚁群落食物采集过程的模拟，其主要特点是正反馈、分布式计算.蚁群算法先后被应用至TSP问题、车间作业调度问题、车辆路径问题等多个经典组合优化问题[7-8]；近年来，一些学者针对蚁群算法进行了改进，比如应用比较广泛的最大最小蚂蚁系统[9]等.

2.1 基本蚁群算法的数学模型

(1)

其中:allowedk={0,1,2,…,n-1}-tabuk(k=1,2,3,…,m)表示蚂蚁k下一个可以选择的节点;ηi j代表启发函数，一般取ηi j=1/di j，di j代表结点i,j之间的长度;α代表信息量残留的重要程度;β代表启发函数的重要程度.每条路径的信息量要在每只蚂蚁走完一步或完成遍历后,根据公式(2)做出调整：

τi j(t+n)=(1-ρ)τi j(t)+△τi j,

(2)

2.2 针对教室管理问题改进的蚁群算法

教室管理优化问题是为带权二部图寻找最小的完备匹配，即寻找一个单射f∶GLCTGPR，在尽量满足软约束条件下，总权值最小.

2.2.1数据准备 1) 排序.为提高蚁群算法的局部搜索能力，将课元按照班级学生人数降序排列(人数多的优先级高)，同一个班级按照上课时间的先后排序；目标集按照教室容量升序排列,教室容量相同的按照上课时间先后排序；并将同一个班级单双周的课程合并成一个课元.2)分组.为缩小蚂蚁的搜索空间，将两个节点集按匹配的教室类型进行分组，将二部图划分为几个二部子图.

2.2.2算法的主要内容 1) 转移概率.使用蚁群系统的伪随机比例规则：

(3)

其中：ηi j=1/wi j；q0(0≤q0≤1)是初始设定的参数；q是一个随机数，q∈[0，1]；参数q0的大小决定了利用先验知识和探索新路径之间的相对重要性.每当蚂蚁要选择下一个目标时，它就选取一个随机数0≤q≤1，如果q≤q0，则根据先验知识公式来选择最好的边，否则J按照公式概率(1)选择.该转移策略将确定性选择和随机选择相结合，既保证搜索收敛性好,又避免过早陷于搜索停滞.

2) 信息素更新策略.更新策略使用基于超立方框架的最大最小蚁群算法[13],通过设置信息素的上下限，将各路径初始化信息素浓度设为τmax，这样可解决应用过程中出现的停滞和扩散问题，避免信息素的无限制累加和可能出现的信息素为零的现象，提高算法的鲁棒性.

同时为进一步增大最优路径边与劣质路径边之间的信息素量差异，引入负反馈机制，使蚂蚁的搜索行为更集中于最优解的附近.每条路径的信息量在迭代后根据公式(4)做出调整：

τ∈[τmin,τmax],

(4)

其中K为引入的一个参数，Lworst表示当前循环中最差蚂蚁的路径长度，Lbest表示当前最好的路径长度，τmin和τmax表示信息素的上下限.

2.2.3算法的主要步骤 本文提出的教室管理优化问题的蚁群算法的实现步骤为：

step 1 参数初始化：设置蚂蚁个数m，迭代次数N=0；最大迭代循环次数Nmax，初始化新信息素τi j(0)=τmax, 将m只蚂蚁随机分布在GLCT中的起点上;

step 2N∶=N+1；

step 3 当N

step 4 选择具有最大状态转移概率的元素j，修改蚂蚁k的禁忌表，将j加入禁忌表中；

step 5 若没有遍历完GLCT中的所有点，跳转到第3步，否则转到第6步;

step 6 计算蚂蚁k的路径长度Lk，通过比较其大小求得最短长度Lbest和最长长度Lworst；

step 7 按照(4)式进行信息素更新;

step 8 如果满足结束条件，即N=Nmax，迭代结束，输出结果；否则，清空禁忌表，跳转到第2步.

3 实验结果与分析

为验证算法的有效性，以延边大学工学院69门课程、6个班级、16个教室为数据进行仿真实验，实验参数设置参照文献[14].对基本蚁群算法和改进蚁群算法进行对比试验，对每次试验记录下最优解Length_best，以实现算法性能的比较.

图1和图2分别给出了基本蚁群算法和改进蚁群算法得出的类型相同、容量相同的教室排课表：教室编号6和7的教室容量和类型相同，矩阵表示的是周一到周五每天5个时间片安排的课程.比较图1和图2可以看出：在没有冲突的情况下，基本蚁群算法在课程分布上比较均匀；而改进的蚁群算法尽量把课程集中在一个教室，这样可以空出其他教室作为自习室或社团活动室，满足教室资源的合理利用.

图3是以班级为单位生成的课表，矩阵表示的是周一到周五5个时间片所使用的教室情况.从图3可以看出：基本蚁群算法中，班级1在相邻时间片占用15231、15221两个多媒体教室和两个机房15252和23062；改进的蚁群算法中，班级1在相邻的时间片占用一个多媒体教室15221和一个32062机房；班级2情况类似.由以上知改进的蚁群算法减少了学生的课间流动性，有利于改善教学秩序.

图1 ACS算法的教室排课表(教室编号6和7)

图2 改进的蚁群算法的教室排课表(教室编号6和7)

(a)基本蚁群算法的班级编号为1和2的排课表 (b)改进蚁群算法的班级编号为1和2的排课表

图4为两种算法随迭代次数的增加而生成的最优解的变化曲线图.由图4也可以看出，随着迭代次数的增加，两种算法都收敛，其中改进的蚁群算法在迭代次数30～40之间的效果最好，这与所选数据的规模有关.

表1给出了两种算法最优值的对比数据(单位：座位数).从图4可以看出，迭代次数在35左右时的效果最好，所以对比数据的迭代次数选为35次.结果表明，改进的蚁群算法权值更低，得到了更优解.

图4 两种算法的迭代次数和最短距离的对比曲线

表1 两种算法的最优值的对比

4 结论

本文实验结果表明,改进的蚁群算法能够满足硬性约束，未出现教室冲突或教室类型不匹配现象，达到了优化的目的.通过在边的权值优化方面加以改进，可保证学生人数少的课程尽量占用容量小的教室，也可解决大部分连续两节课之间的教室距离问题、单双周课程安排问题；本文的研究对教室资源有限的高校教室管理有一定的应用价值.本文的算法只针对教室管理进行了优化，课元的上课时间预先给定，没有考虑时间冲突，下一步的工作将主要解决排课问题的时间冲突，对蚁群算法信息素做进一步改进，以提高算法效率.

参考文献：

[1] 侯文静，马永杰,张燕，等.求解TSP的改进蚁群算法[J].计算机应用研究,2010,27(6):2087-2089.

[2] 崔旭,崔荣一,金小峰，等.基于时间资源的大学排课问题研究[J].延边大学学报：自然科学版,2006,32(4):256-258.

[3] 詹亚坤.基于模拟退火算法的高校排课系统研究[D].东北师范大学,2012.

[4] 王凤，林杰.高校排课问题的图论模型及算法[J].计算机工程与应用,2009,45(27):240-242.

[5] 景雪琴,朱玉芳,杜栋，等.从排课表到教室调度表的设计与实现[J].计算机应用与软件,2004,21(2):123-125.

[6] 余斌,谢昕.基于减小教室流动性的排课算法研究[J].计算机时代,2004(2):22-24.

[7] 倪庆剑,邢汉承,张志政.蚁群算法及其应用研究进展[J].计算机应用与软件,2008,25(8):12-15.

[8] 池元成，蔡国飙.基于蚁群算法的多目标优化[J].计算机工程,2009,35(15):168-169.

[9] Thomas Stützle, Holger H Hoos. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000,16(8):889-914.

[10] 何小虎.优化蚁群算法在排课中的应用策略[J].计算机与数字工程,2012,40(7):33-35.

[11] Broderick Crawford, Ricardo Soto. A Max-Min ant system algorithm to solve the software project scheduling problem[J]. Expert Systems with Applications, 2014(41):6634-6645.

[12] 吴小娟,吕强.新蚁群算法模型在大学课程时间表问题中的应用[J].计算机应用与软件,2009,26(6):80-83.

[13] Christian Blum. The Hyper-Cube framework for ant colony optimization[J]. IEEE Transactions on Systems Man, and Cybernetics Cybernetics-part B:Cybernetics, 2004,34(2):1161-1171.

[14] Li Zhiyong, Wang Yong, Dai Yun, et al. The cloud-based framework for ant colony optimization[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation. Shanghai, 2009:279-286．