基于自适应蚁群算法在急救车辆调度上的应用

周桂宇　张桐

摘 要：针对基本型蚁群算法迭代次数多，搜素时间较长，收敛速度慢的缺陷，采用改进的自适应蚁群算法，根据全局最优解的分布情况自适应地进行信息素范围的更新，从而动态地调整各路径上的信息素强度，同时，建立数学模型，给出求解TSP问题的改进算法，仿真出通过改进的自适应蚁群算法得到的最优路径，应用到患者位置与急救调度站之间最优路径的选择。结果表明，该模型和算法在收敛速度和迭代次数上均优于基本型蚁群算法。

关键词：自适应蚁群算法；迭代次数；收敛速度；最优路径

中图分类号：TP312 文献标识码：A

Abstract：In view of the defects from the basic ant colony algorithm frequent iterations and slow speed in convergence，the solution in this paper are using improved adaptive ant colony algorithm，setting up mathematical model，simulating out the optimal path through improved adaptive ant colony algorithm and applying to the choice of the optimal path between emergency dispatching station and the patients' position.The results show that the model and algorithm in convergence speed and the number of iterations are better than the basic ant colony algorithm.

Keywords：adaptive ant colony algorithm；iterations；the rate of convergence；the optimal path

1 引言（Introduction）

120急救指挥系统在城市应急指挥体系中具有非常关键的作用，当患者拨入急救电话或者遇到重大事故和突发事件时，指挥中心需要根据患者位置或者事故位置选择最优路径快速将患者送往医院进行急救[1]。最优路径的选择需要考虑起点和终点之间的总里程数，人流量及客流量等外界因素。基本蚁群算法搜索时间较长，而且容易出现停滞，易陷入局部最优解等缺陷[2]。此次设计的自适应蚁群算法主要根据全局最优解的分布情况，通过计算得出迭代次数不断增加的同时，自适应地减小蚁群觅食过程中的视野范围，提高获取最优解的速度，从而动态地获取各路径上的信息量强度，提高了全局搜索能力，避免了局部收敛和早熟现象。在模拟寻找最优路径过程中，设置多个节点模拟起点和终点之间的障碍物，以类似蚂蚁觅食的方式在求解复杂组合优化的问题上取得了良好的仿真效果，能够对急救车辆到达患者位置之间的多条路径进行模拟和优化。

2 基本蚁群算法（The basic ant colony algorithm ）

基本蚁群算法是20世纪90年代由意大利学者M.Dorigo等人首先提出来的一种新型的模拟进化算法，称之为蚁群系统[3]。基本蚁群算法主要解决TSP（Traveling Salesman Problem）旅行商问题，QAP（quadratic Assignment Problem）分配问题、JSP（Job-shop Scheduling Problem）调度问题等，取得了一系列较好的实验结果。基本型蚁群算法分为正反馈以及分布式计算。正反馈过程的优势是能较快的找到问题的较好解；分布式的优势是易于并行实现，同时与启发式算法相结合，能使该方法易于找到更好的解，最后达到最优解[4]。基本蚁群算法的原理图如图1所示。

3 改进的自适应蚁群算法模型（Improved adaptiveant colony algorithm model）

从基本蚁群算法中发现，参数视野值对最优解的影响比较大，经过多次实验发现，在视野范围不变的情况下，算法后期的收敛速度较慢，迭代次数逐渐增加，并且当起点与终点之间节点越多，越容易陷入局部最优，无法达到全局最优；但是如果给定视野范围过小，收敛速度会有适当加快，但是更容易陷入局部最优。经过多次论证，当参数视野值为原始视野值60%时，收敛速度最快，且迭代次数最少，最接近全局最优解值。算法表达式为

算法实现的流程图如图2所示。其中，输入原始数据后会获取路网节点数、各节点的具体坐标位置，节点的权值矩阵、自适应蚁群的群体规模、最大迭代次数、蚁群的最大移动步长、拥挤度因子等参数。

4 算法的仿真（The simulation algorithm）

现将改进的自适应蚁群算法与基本蚁群算法求解最优路径进行仿真，并将两者结果进行对比，仿真工具为MATLAB 2010a，蚁群规模n=50，留在每个节点上的信息受重视程度α=0.1，启发式信息受重视程度β=0.5，蚂蚁数目20个，最大迭代次数100次。图3为起点与终点之间有七个信息节点，利用自适应蚁群算法得到的最优路径仿真示意图，得出的路径为1—2—3—5—9—8—4—6—7，其中最短路径为1—2—3—5—9。图4为自适应算法与基本型蚁群算法在寻优过程中的对比，两种算法分别在第二次和第五次迭代后搜索到全局最优解。

5 结论（Conclusion）

针对基本蚁群算法收敛速度慢，运算量大，陷入局部最优的缺陷，本文提出一种自适应蚁群算法，使其随着全局最优解的变化而适当的改变视野范围的值。实验结果表明，改进的自适应蚁群算法在收敛速度、迭代次数、计算量，寻优精度均优于基本型蚁群算法，适用于在急救车辆调度过程中实现最优路径的规划，为急救车选择最优路径到达患者位置提供了有利依据。

参考文献（References）

[1] 杨丽锦.浅析蚁群算法的原理及应用方向[J].电脑知识与技术，2009（6）：12-14.

[2] 杨琼.具有感知觉特征的蚁群算法在连续函数优化中的应用[D].四川师范大学，2009.

[3] 马宪民，刘妮.自适应视野的人工鱼群算法求解最短路径问题[J].通信学报，2014（1）：16-17.

[4] 蒋艳玲，张军.蚁群算法的参数分析[J].计算机工程与应用，2007（20）：34-35.

[5] 王晔，吴晓军.基于改进人工蚁群算法的RBF网络及其在人脸表情识别中的应用[J].计算机应用研究，2008（9）：28-30.