基于自適應(yīng)蟻群算法在急救車輛調(diào)度上的應(yīng)用

周桂宇　張桐

摘 要：針對基本型蟻群算法迭代次數(shù)多，搜素時間較長，收斂速度慢的缺陷，采用改進(jìn)的自適應(yīng)蟻群算法，根據(jù)全局最優(yōu)解的分布情況自適應(yīng)地進(jìn)行信息素范圍的更新，從而動態(tài)地調(diào)整各路徑上的信息素強(qiáng)度，同時，建立數(shù)學(xué)模型，給出求解TSP問題的改進(jìn)算法，仿真出通過改進(jìn)的自適應(yīng)蟻群算法得到的最優(yōu)路徑，應(yīng)用到患者位置與急救調(diào)度站之間最優(yōu)路徑的選擇。結(jié)果表明，該模型和算法在收斂速度和迭代次數(shù)上均優(yōu)于基本型蟻群算法。

關(guān)鍵詞：自適應(yīng)蟻群算法；迭代次數(shù)；收斂速度；最優(yōu)路徑

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：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急救指揮系統(tǒng)在城市應(yīng)急指揮體系中具有非常關(guān)鍵的作用，當(dāng)患者撥入急救電話或者遇到重大事故和突發(fā)事件時，指揮中心需要根據(jù)患者位置或者事故位置選擇最優(yōu)路徑快速將患者送往醫(yī)院進(jìn)行急救[1]。最優(yōu)路徑的選擇需要考慮起點(diǎn)和終點(diǎn)之間的總里程數(shù)，人流量及客流量等外界因素?；鞠伻核惴ㄋ阉鲿r間較長，而且容易出現(xiàn)停滯，易陷入局部最優(yōu)解等缺陷[2]。此次設(shè)計(jì)的自適應(yīng)蟻群算法主要根據(jù)全局最優(yōu)解的分布情況，通過計(jì)算得出迭代次數(shù)不斷增加的同時，自適應(yīng)地減小蟻群覓食過程中的視野范圍，提高獲取最優(yōu)解的速度，從而動態(tài)地獲取各路徑上的信息量強(qiáng)度，提高了全局搜索能力，避免了局部收斂和早熟現(xiàn)象。在模擬尋找最優(yōu)路徑過程中，設(shè)置多個節(jié)點(diǎn)模擬起點(diǎn)和終點(diǎn)之間的障礙物，以類似螞蟻覓食的方式在求解復(fù)雜組合優(yōu)化的問題上取得了良好的仿真效果，能夠?qū)本溶囕v到達(dá)患者位置之間的多條路徑進(jìn)行模擬和優(yōu)化。

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

基本蟻群算法是20世紀(jì)90年代由意大利學(xué)者M(jìn).Dorigo等人首先提出來的一種新型的模擬進(jìn)化算法，稱之為蟻群系統(tǒng)[3]?；鞠伻核惴ㄖ饕鉀QTSP（Traveling Salesman Problem）旅行商問題，QAP（quadratic Assignment Problem）分配問題、JSP（Job-shop Scheduling Problem）調(diào)度問題等，取得了一系列較好的實(shí)驗(yàn)結(jié)果?；拘拖伻核惴ǚ譃檎答佉约胺植际接?jì)算。正反饋過程的優(yōu)勢是能較快的找到問題的較好解；分布式的優(yōu)勢是易于并行實(shí)現(xiàn)，同時與啟發(fā)式算法相結(jié)合，能使該方法易于找到更好的解，最后達(dá)到最優(yōu)解[4]?；鞠伻核惴ǖ脑韴D如圖1所示。

3 改進(jìn)的自適應(yīng)蟻群算法模型（Improved adaptiveant colony algorithm model）

從基本蟻群算法中發(fā)現(xiàn)，參數(shù)視野值對最優(yōu)解的影響比較大，經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，在視野范圍不變的情況下，算法后期的收斂速度較慢，迭代次數(shù)逐漸增加，并且當(dāng)起點(diǎn)與終點(diǎn)之間節(jié)點(diǎn)越多，越容易陷入局部最優(yōu)，無法達(dá)到全局最優(yōu)；但是如果給定視野范圍過小，收斂速度會有適當(dāng)加快，但是更容易陷入局部最優(yōu)。經(jīng)過多次論證，當(dāng)參數(shù)視野值為原始視野值60%時，收斂速度最快，且迭代次數(shù)最少，最接近全局最優(yōu)解值。算法表達(dá)式為

算法實(shí)現(xiàn)的流程圖如圖2所示。其中，輸入原始數(shù)據(jù)后會獲取路網(wǎng)節(jié)點(diǎn)數(shù)、各節(jié)點(diǎn)的具體坐標(biāo)位置，節(jié)點(diǎn)的權(quán)值矩陣、自適應(yīng)蟻群的群體規(guī)模、最大迭代次數(shù)、蟻群的最大移動步長、擁擠度因子等參數(shù)。

4 算法的仿真（The simulation algorithm）

現(xiàn)將改進(jìn)的自適應(yīng)蟻群算法與基本蟻群算法求解最優(yōu)路徑進(jìn)行仿真，并將兩者結(jié)果進(jìn)行對比，仿真工具為MATLAB 2010a，蟻群規(guī)模n=50，留在每個節(jié)點(diǎn)上的信息受重視程度α=0.1，啟發(fā)式信息受重視程度β=0.5，螞蟻數(shù)目20個，最大迭代次數(shù)100次。圖3為起點(diǎn)與終點(diǎn)之間有七個信息節(jié)點(diǎn)，利用自適應(yīng)蟻群算法得到的最優(yōu)路徑仿真示意圖，得出的路徑為1—2—3—5—9—8—4—6—7，其中最短路徑為1—2—3—5—9。圖4為自適應(yīng)算法與基本型蟻群算法在尋優(yōu)過程中的對比，兩種算法分別在第二次和第五次迭代后搜索到全局最優(yōu)解。

5 結(jié)論（Conclusion）

針對基本蟻群算法收斂速度慢，運(yùn)算量大，陷入局部最優(yōu)的缺陷，本文提出一種自適應(yīng)蟻群算法，使其隨著全局最優(yōu)解的變化而適當(dāng)?shù)母淖円曇胺秶闹?。?shí)驗(yàn)結(jié)果表明，改進(jìn)的自適應(yīng)蟻群算法在收斂速度、迭代次數(shù)、計(jì)算量，尋優(yōu)精度均優(yōu)于基本型蟻群算法，適用于在急救車輛調(diào)度過程中實(shí)現(xiàn)最優(yōu)路徑的規(guī)劃，為急救車選擇最優(yōu)路徑到達(dá)患者位置提供了有利依據(jù)。

參考文獻(xiàn)（References）

[1] 楊麗錦.淺析蟻群算法的原理及應(yīng)用方向[J].電腦知識與技術(shù)，2009（6）：12-14.

[2] 楊瓊.具有感知覺特征的蟻群算法在連續(xù)函數(shù)優(yōu)化中的應(yīng)用[D].四川師范大學(xué)，2009.

[3] 馬憲民，劉妮.自適應(yīng)視野的人工魚群算法求解最短路徑問題[J].通信學(xué)報(bào)，2014（1）：16-17.

[4] 蔣艷玲，張軍.蟻群算法的參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用，2007（20）：34-35.

[5] 王曄，吳曉軍.基于改進(jìn)人工蟻群算法的RBF網(wǎng)絡(luò)及其在人臉表情識別中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2008（9）：28-30.