基于自適應蟻群算法在急救車輛調度上的應用

周桂宇　張桐

摘 要：針對基本型蟻群算法迭代次數多，搜素時間較長，收斂速度慢的缺陷，采用改進的自適應蟻群算法，根據全局最優解的分布情況自適應地進行信息素范圍的更新，從而動態地調整各路徑上的信息素強度，同時，建立數學模型，給出求解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.