蚁群算法下的开放式高校实验室预约系统优化

李舒明

（福建船政交通职业学院 航海学院，福建 福州 350007）

蚁群算法自20世纪90年代提出之后，经过不断地改善被应用于工作指派、旅游求决、车辆调度等众多领域[1]。其仿生学算法功能被广泛开发之后，具有较强的动态约束能力，不仅可以解决离散域问题，还可以解决连续域问题，其技术能力在我国研究领域开发程度更深，被传播范围也更为广阔[2]。高校实验室预约智能化指高校实验室预约管理中用计算机智能手段改进人工管理手段的过程。当前我国高校实验室管理过程中，将较多的精力投入到实验室设备、技术、环境的更新换代方面，忽视或很少关注实验室设备管理、设备调度、教学实验安排等柔性管理领域[3]，从而导致实验室资源利用效率低下、浪费严重、实验进度迟滞等问题。为改善当前我国高校实验室管理现状，引入蚁群优先排序算法，结合具体高校实验室管理结构，实现实验室预约智能化。

1 面向蚁群算法的开放式实验室预约智能系统优化设计

1.1 系统预约算法优化设计

蚁群算法优先排序原则指出，蚂蚁在进行最优路径选择之前首先须形成一个蚂蚁个体，蚂蚁个体须具有协作机制，其次具备信息素遗留能力即蚂蚁的记忆能力，最后通过信息素遗留情况，在多个蚂蚁协作的条件下进行最短路径选择[4]。在遇到路径破坏情况时，还具有再次协作进行重新最短路径选择的再生能力[5]。

根据蚁群算法原则实验室预约过程中，须首先进行个体间协作构造，即同类相识进行拾起放下过程。以单个学生进行预约机制为例，假定学生A为起始测试对象，则虚拟起始学生A会按照相似度决定是否拾起另一个随机测验对象，如果两者不相似则学生A会在大概率范围内重新转移拾起地点，直到找到相似对象地点。如果二者相似则会进行拾起动作，进行路径确认并产生信息素进行放下动作。再此寻找下一个物体进行以上相似度“拾起—放下—拾起”过程[5]。在经过数次迭代过程之后，整个算法才会结束。如以上分析，若一学生A在网格r的位置上遇到拾起对象Oi，则Oi与周围物体的相似度计算公式为

式中：Neighs×s（r）为学生A在r的位置所能够涉及到的全部范围，由于蚁群算法自身的特点限制，围是一个以r为中心的圆形区域。d（Oi，Oj）表示学生A从位置Oi到位置Oj的距离。n表示学生A在位置r能够接收到的所有学生的信息量。α为学生群体相似度系数，在相似度计算中，α的值越大则相似度值越大，此时由于对象Oi与对象Oj的区分度过小，会加大算法的收敛速度，也会造成将本不相似的对象群体归为一类的现象。反之，则相似度值较小，区分度较大，收敛速度会提升，也会加大对象群体的区分水平。在相似度迭代计算中，将拾起概率设为Pp，放下概率设为Pd，值在[0，1]，则一个循环过程中局部相似度计算为

局部相似度由拾起概率与放下概率共同决定。在公式（2）中，k1与k2都为阈值常量，且在拾起与放下的过程中都会产生一个随机数R，如果拾起与放下概率的值大于R，则进行拾起或放下工作，反之继续移动。根据公式（2）可知，拾起与放下概率与f（Oi）相关。f（Oi）值大时，Pp值越小，Pd值越大，表明此时易进行放下动作，不易进行拾起动作。反之f（Oi）值小时，Pd越小，Pp值越大。

在重复进行拾起与放下动作时，由于不同的蚂蚁之间的权值不同，因此在一个紧密预约周期内要尽量避免学生预约重复现象出现。信息素即权值在每一轮计算中都具有蒸发过程，即每一轮计算都必须排除前一轮过程中的较差路径。为避免重复预约现象出现，假设预约学生数为n，信息蒸发的概率为ρ，规定0＜ρ＜1，一般情况下将ρ值定位0.5，则第k个学生在t预约时刻的信息素量为Δτij，计算结果为

在学生未进行预约选择，在起始时刻时候，则其预约信息素大小用τ表示，设置为τ0。则τ0的大小直接决定学生信息素的遗留能力及学生个体间的协作机制，当τ0太小时，（1-ρ）τij值较小，则学生个体进行一次选择之后所留信息素较少。此时信息素对学生预约选择概率影响较大，学生进行自由选择的概率将缩小，提高收敛速度。反之当τ0值过大时，信息素对学生个体为构造能力影响较小，将不利于后来学生对先前路径的优劣感知，不利于路径合理性的构建。为确定τ0值的合理性，在具体设计算法设计过程中，引入贪婪算法中节点之间的路径长度Cn，使τ0=n/Cn。

为增强收敛速度，减少因个人预约造成的预约通道拥堵或者稀少问题，提高整个聚类过程的有效性、鲁棒性及算法收敛速度[6]。在相似度聚类过程中，对学生A的观察半径及概率转换函数变量进行优化控制，采用观察前后阶段半径发生先由大变小后由小变大的方法，对收敛速度进行改进，半径变化公式为

式中：Tmax为全部计算过程中的迭代次数，n（t）为局部迭代次数，s（t+1）表示学生在进行第t+1次迭代使得观察半径，Int（）表示向下取整函数，N和M分别表示观察半径的下界与上界M=s（0），算法每迭代一次半径缩减或增加值为1。

在拾起与放下概率转换过程中，学生预约过程之间的距离d（Oi，Oj）采用欧式计算法则。但是在学生相似度计算过程中，不仅要考虑对象之间的相似度，还需考虑两个正在使用预约系统的学生之间的选择趋势是否相似。因此研究在距离控制变量中加入余弦距离计算，使距离线性之间的互补效果更加明显。距离变量控制为

除了考虑到距离之间的趋势因素之外，实验室预约计算过程中还应加入对相似度动作速度的考量。研究设定前期相似度迭代速度较快后期速度较慢，迭代过程中通过速度的改变，可以在快速的整理对象的分类数目，提高对象组合的精细度[8]。速度设定之后的相似度计算为

由于蚁群算法更新规则往往只是加强每次迭代最短路径时的信息素浓度，而信息素浓度的增加会造成算法只对出局部最优解进行计算，因此需要将每次迭代的最优解结果充分利用，才可以找到局部与全局最优解之间的关联。所以在本次研究中引入最优解控制参数中的自适应动态因子σ（σ∈（0,1）），其主要对单次迭代最优解信息素浓度的更新比重进行自适应控制，加大优秀路径的信息素浓度，进而更好的显示路径信息。全局更新每次迭代完成后的最优路径信息素浓度的规则为

式中：τij（t+1）为示第t+1次迭代时在节点i和节点j之间路径上的信息素强度。自适应动态因子其中：γ表示控制反正切函数形状的参数表示目前能够通过搜索到的局部最优路径的平均长度；Lmin表示当前全局最优解；表示本次目前能够通过搜索到的局部最优路径的长度。σ的反正切函数为

结合式（9）、式（10）来看反正切函数f（x）具有平滑的输出曲线，范围在［0,1］之间。若Llocalmin值越高且搜索路径越长时，σ值越靠近0；反之，σ值越靠近1。在不同参数γ下f（x）与经典蚁群算法的σ曲线对比，如图1所示。

图1 动态因子函数曲线图Fig.1 Curve of dynamic factor function

1.2 系统预约流程优化设计

实验室预约过程中，由于用户对实验室设备资源的不熟悉，会造成部分设备使用过度，而部分设备长期闲置的现象[6]。为提高设备使用效率，提高用户对设备资源的合理利用。按照设备信息状况对实验室设备预约系统进行两种模式流程设计并优化[6]。

一种流程是针对在一个周期内（一周），设备使用频率不足设备使用最高负荷。则表明在此周期内，可根据具体使用设备情况，在保留原设备预约安排的前提下，进行空余时间筛选并安排新的预约请求，直接生成到结果计算中，设计流程如图2所示。

图2 预约模式一流程图Fig.2 Flow chart of reservation mode 1

如图2所示，用户在登录界面之后，变会进入预约请求界面，可进行最近一周期内实验预约请求。在用户进行预约筛选之前，计算机系统会对当前已经存在的预约请求和空余时间进行计算并生成结果。若当前预约时间小于设备可使用时间，则根据用户意愿则进入预约界面并形成预约结果。保证下一位预约用户正常选择同时也可保证系统的稳定性与准确性。

若一个周期内设备使用量高于设备可使用时间，则需要对用户请求进行合理配置。在系统开始之前根据设备一周期可使用时间进行容量设定[7]。在具体预约操作过程中，以最大预约数为界限，按照预约时间先后顺序，对超出使用容量的客户进行拦截。并按照最优路径计算方法，对拦截客户进行最优预约结果进行处理。具体操作流程如图3所示。

图3 预约模式二流程图Fig.3 Flow chart of reservation mode 2

如图3所示，对于第二种预约模式中被拦截的用户进行重新路径计算，按照周期内实验次数最少，设备利用最小，可使用率较高原则，进行重新预约安排。蚁群计算最优计算结果如图4所示。

图4 预约模式二过程优化计算过程流程图Fig.4 The flow chart of the optimization calculation process of reservation mode 2

如图4所示，按照相似度原则分别对设备数量、使用时间、损耗程度进行控制。在具体的预约程序中设备数量与时间是一一对应的关系，因此首先对时间和设备量进行控制。从预约信息的第一条开始，对预约设备损耗进行计算。计算每一条预约信息之前都需要对该预约进行计算与否判断，若无计算则进入计算流程，若已计算则进入下一条预约记录，直至所有预约记录计算完成为止。通过对预约设备损耗程度的累计结果与可使用损耗累计结果对比判断预约请求并生成结果。按照以上操作流程对实验室设备管理智能化流程实现如图5所示。

图5 开放式实验室预约智能管理程序设计流程图Fig.5 Flow chart of design of intelligent management program for open laboratory appointment

如图5所示开发式高校实验室预约智能系统，不仅涉及前台用户的管理设计，更为重要的是后台运行控制设计[7]。在最优路径几率型蚁群算法控制下，算法模型的建构可以实现后台参数的最优计算参数设定，在流程模型的优化设计可以为前台用户提供更为快捷的预约服务、查询服务、监护服务、设备录入及更新服务，极大提高整个开放式高校实验室预约智能系统使用效率。

2 基于蚁群算法的开放式高校实验室预约系统评测

2.1 系统优化路径评测

在残留信息的相对重要程度取值为3，期望值的取值为1，信息素的挥发系数，信息素更新常数为5，信息素更新时间控制在[1，5]之间。分别选取规模为8×6，55×49，110×98，350×487条件下，对12名学生进行50次路径选择评测。最终生成贪心算法、HGS算法、GRE算法和蚁群算法的对比结果如图6所示。

图6 几种算法最优解及误差对比分析结果Fig.6 Optimal solutions and error comparison analysis results of several algorithms

从图6（a）为各种算法在不同规模下的最优解对比，图6（b）为各种算法在不同规模下的偏差对比。从5（a）中可以看出，在小规模测试结果中，各种算法结果不存在较大差别，甚至结果基本一致，都能够得到与已知最优解一致的答案。但是随着规模的增大，蚁群算方法的最优解分别为2.87、2.12、3.28，相对于其他三种算法而言，其最优解相对于已知最优解而言，偏差趋势明显提高，偏差度显著降低。图6（b）中从误差对比结果分析可得规模为55×49时，误差率为4.4%；规模为110×98时，误差率为6.1%；规模为350×487时，误差率为9.0%。平均误差率降低6.5%左右。相比于其他几种算法误差率平均降低7.5%。误差率显著降低，提高系统计算精准度，能够为高校实验室预约智能提供良好的设计效果。

2.2 系统运行时间评测

对高校实验室预约智能系统进行有效评测，除要考虑系统运行的精准度之外，一个重要参数就是计算时间的评测。较短的计算时间可以直接提高系统的使用效率，增强系统流程度，减小系统因计算量过大而导致的崩溃现象，提高学生使用感受。在原有参数不变情况下对个算法计算时间进行对比分析，结果如图7所示。

图7 四种规模下不同算法的对比结果Fig.7 Comparison results of different algorithms at four scales

由于不同规模条件下规模计算所需时间差距较大，因此将8×6，55×49，110×98和350×487规模按照两两对比形式分开对比，以更加清晰的比较四种算法计算时间差距。图7（a）为8×6和55×49规模对比结果，图7（b）为110×98和350×487规模对比结果。从图7中可以看出，无论是哪种规模下，相较于其他三种算法蚁群分析算法的计算时间都较短。规模分别为8×6，55×49，110×98和350×487时，蚁群算法的计算时间分别为7、52、110、340 s。相较于其他三种算法，计算时间平均缩短分别为2、28.67、93.33、310 s。极大程度上缩短计算时间，并且随着规模的不断扩大，蚁群算法在计算时间方面的优势就更为明显。表明在蚁群算法指导下，高校实验室预约智能系统的设计具有较强的合理性。

2.3 系统运行效应评测

相较于系统运行路径与时间的优势，蚁群算法不仅能够实现局部区域优化，更为重要的是它能够在实现局部优化的基础上，进一步实现全局优化。不仅能够实现离散域的优化，更能够实现连续性的系统优化。在原有参数不变的情况下，选取贪心算法与蚁群算法进行对比分析，结果如图8所示。

图8 贪心算法与蚁群算法50最优路径选择对比结果Fig.8 Comparison results of optimal path selection between greedy algorithm and ant colony algorithm 50

图8（a）、（b）分别为贪心算法和蚁群算法对学生和教师50次最优路径选择中的其中一次迭代仿真结果。从图8（a）中可以看出，基于贪心算法的最优解大于470，而优化设计后的蚁群算法最优解小于460。从图8（b）中可以看出，基于贪心贪心算法的最优解大于520，而优化设计后的蚁群算法最优解小于510。并且两幅图都表现出，蚁群算法的曲线都率先实现节点转折。这表明蚁群算法相较于贪婪算法而言，能够优先跳出局部最优，进而实现全局最优目标。

3 结论

高校实验室预约智能化系统建构的合理性，不仅能够极大程度上减少设备损耗、提高设备使用效率，还能够降低人工成本、提高学生的实验能力，从而增强高校教学实力。基于此研究引入蚁群算法，对预约系统的预约算法及流程进行优化设计，建立起高校实验室预约智能管理系统并对其进行了效用评测。结果表明，经过优化设计后的高校实验室预约系统，其计算偏差在规模分别为55×49，110×98，350×487时，误差率分别为4.4%、6.1%、9.0%。平均误差率在6.5%左右，相比于其他几种算法误差率平均降低7.5%，极大提高了系统计算精准度。同时相比于其他三种算法平均计算时间分别降低2、28.67、93.33、310 s，极大提高了系统计算时间。除此之外还能够实现较高程度的全局优化能力，验证了系统建构的合理性。