一種基于蟻群思想的動態路徑尋優算法的實現及仿真

周秀娟，花　嶸，史　娟，高玉勵

(1.山東科技大學 信息科學與工程學院 山東 青島 266590；2.青島黃海學院 山東 青島 266427)

?

一種基于蟻群思想的動態路徑尋優算法的實現及仿真

周秀娟1，花嶸1，史娟1，高玉勵2

(1.山東科技大學 信息科學與工程學院 山東 青島 266590；2.青島黃海學院 山東 青島 266427)

摘要：為了提高路徑尋優算法的效率和實時性，本文實現了一種名為DPO-AC的基于蟻群思想的動態路徑尋優算法(the ant colony algorithm with dynamic path optimization)，在改進蟻群算法的基礎上結合神經網絡的實時預測方法和限定區域的搜索方式，解決算法在大型網絡路徑尋優時實時性差、收斂慢的問題。仿真實驗表明DL-ACO算法有比較好的穩定性、收斂性和實時性。

關鍵詞：路徑尋優；算法；蟻群；限定區域；阻塞矩陣

隨著城市人口的不斷增加，城市交通路網趨于大型化、復雜化，且隨著人均車輛保有量的快速增長，城市交通情況日漸復雜化。傳統的路徑尋優算法[1-3]不考慮路網的動態變化情況，把路網的拓撲性作為唯一依據，不考慮起點和終點的位置、方向，雖簡單易用，但效率偏低。近年來，隨著人工智能的發展，智能算法被越來越多的用于解決大規模、非線性、全局最優的復雜問題，將其應用于路徑尋優問題求解已成為城市交通研究的一個熱點。張學敏[4]在蟻群算法中引入了方向引導信息來提高城市路網求解的收斂速度，靳凱文[5]等人在蟻群算法的基礎上對信息素、啟發信息的重要性和信息素的保留率進行了分階段調整，提高了算法的穩定性。

用于交通路網路徑尋優的限定區域的方法主要有兩種:橢圓區域[6]和矩形區域[7]，相比于橢圓區域，矩形區域的算法搜索效率更高[7]。BP神經網絡[8]雖然能夠準確、有效的實現道路交通信息的實時預測，但也存在以下缺陷：因采用梯度下降法進行搜索，而梯度下降法固有的特點使得易形成局部極小值[9]，學習率較低使得訓練時間較長，而且BP神經網絡的隱層節點數目選取缺乏理論基礎。

本文為滿足大型路網路徑尋優的需要，結合交通網的動態特性，從避免局部最優的角度出發，對蟻群算法中的選擇策略進行了改進，并將限定區域和動態阻塞矩陣應用到蟻群算法中，設計了一種名為DPO-AC的基于蟻群思想的動態路徑尋優方法。

1經典蟻群算法及存在問題分析

經典的蟻群算法是20世紀90年代Dorigo M[10]等人受螞蟻覓食行為啟發提出的一種模擬進化算法，以人工螞蟻模擬自然螞蟻求解優化組合問題。經典的蟻群路徑尋優算法模型表述為：m只螞蟻從起點S出發,路網所有路段(i，j)的信息素濃度τij(t)在初始時刻為相同常量，啟發信息ηij(t)設為路段距離dij的倒數，在t時刻螞蟻k在路網交叉口(路網節點)i選擇下一節點j的概率表示為[11]：

(1)

其中，α和β分別表示信息素和啟發信息的重要性。

經過n個時刻，螞蟻從起點到達終點后對路段殘余信息素進行更新，參數ρ(0≤ρ≤1)表示信息素的保留率，各路段上的信息素按式(2)進行更新。

τij(t+n)=ρ·τij(t)+Δτij(t)。

(2)

Δτij(t)表示t時刻(i，j)路段殘存的信息素濃度。

根據更新策略的不同，Dorigo M提出了三種蟻群算法模型，蟻周模型、蟻量模型、蟻密模型，三者的區別在于：后兩種用的是局部信息，第一種用的是全局信息，故性能最佳。

蟻周模型公式如下：

(3)

其中，Q是一個常量表示信息素強度，L表示螞蟻本次循環經過路徑的長度。當所有螞蟻完成一次循環，記錄最優路徑，重復上面的過程，直到預設結束條件滿足。

蟻群算法具有很好的路徑尋優能力，但是在實際的路徑尋優中還存在著如下問題：1)在經典蟻群算法中沒有方向引導，面對大型網路時容易出現“之”字搜索結果，影響搜索速度；2)公式1的概率函數缺乏對動態因素的考慮；3)因算法在搜索時的概率性和正反饋作用，容易出現局部最優。

2DPO-AC算法思想

蟻群算法從結構上分為數據預處理和算法迭代兩部分。本文的DPO-AC算法主要從以下兩個方面對蟻群算法進行了改進：在數據預處理部分，通過設定算法的搜索區域和采用改進的BP神經網絡來實時確定動態阻塞因子；在算法迭代中，改進了選擇概率和選擇策略，并通過改進算法的啟發信息矩陣來確定算法的搜索方向，以防止算法出現局部最優。

2.1 數據預處理部分改進

給定起點S(xs,ys)和終點V(xv,yv)，最短路徑的極限值ESV(歐式距離)即為定值，采用延長SV的方法得到橢圓長軸MD(如圖1)。延長系數可以用樣本分析的方法，確定最短距離Pab和歐式距離Eab的比值系數f，把f作為SV的延長系數。橢圓長軸計算公式為：

MD=f×Esv。

(4)

圖1　 限定區域的選定

圖2　矩形區域內路網簡略圖

利用長軸MD的值求解橢圓方程

(5)

得到的最值即為矩形區域的邊界值：

(6)

(7)

針對BP神經網絡存在的缺陷，本文采用自適應調節法根據輸出誤差大小自動調整學習率，當連續兩次權值迭代中梯度下降方向相同，則表明梯度下降的速度過慢，此時應該增加學習率，學習率乘以增量因子kin；當連續兩次權值迭代中梯度下降方向相反，則表明梯度下降的速度過快，需要減小學習率，學習率乘以減量因子kde。

權值的調節公式為：

(8)

自適應調節方法可以提高算法的學習速度，但是容易出現波動導致局部最優，本文采用附加動量法來避免此問題。具體公式為：

(9)

其中：α表示動量因子，一般取值介于0和1之間。

針對BP神經網絡的隱層節點數目選取缺乏理論基礎的問題，本文采用多值對比的方法確定隱層節點數。根據隱層節點的經驗公式：

(10)

2.2算法迭代部分改進分析

為了提高蟻群算法對動態路網的適應性，在經典蟻群算法選擇概率(公式(1))的基礎上加入改進的BP神經網絡算法得到的路網動態因子，得到新的概率選擇公式如下：

(11)

其中，Pij表示i到j的概率，τij表示i到j路段的信息素濃度，ηij表示i到j路段的距離的倒數，ωij表示i到j路段的阻塞值，α，β，γ為各參數的比重。

針對由于螞蟻尋找路徑的隨機性而帶來的易出現局部最優的問題，本文依據2-8定律，提出采用2-8分批方式對蟻群算法的選擇策略進行改進。

2指的是前20%的螞蟻采用最大概率方法選擇下一節點，公式為

j=max(Pallowed)，

(12)

其中：Pallowed=(pi1,pi2,…,pin)，表示可選下一節點的概率集合；

3DPO-AC算法設計及分析

針對上面的改進方案，本節設計了DPO-AC算法，偽代碼如下：

Procedure DPO-AC

Input:NC_Max,C,R,S,V‘NC_Max是最大迭代次數；C是路網節點；R是初始信息素矩陣；S是起點；V是終點。

New_C=call Relimited(C);‘矩形限定區域法得到新的數據集

W=call BPNetwork(Q);‘BP神經網絡求解動態阻塞矩陣

for each edge

set initial pheromone valuePhe0

end for

Whileinot more thanNC_Max

for each antk

set it toS

if the visited node is notV

20% of ant choose next node by maxPij,80% of ant choose next node by roulette wheel selection

end if

end for

Compute the lengthCkof the tour constructed by thekthant

for each edge

Update the pheromone value

end for

end while

print result

end procedure

4DPO-AC算法仿真測試及分析

4.1測試方案

以天津市的交通路網為例，該路網有124個節點，以出行時間最短為目標求解最優路徑。

1)確定矩形搜索區域，產生起點和終點，對天津市的路網采樣統計確定比例系數f=1.96,由前面提到的求解方法確定矩形區域內的節點，運行代碼得到矩形區域的節點數為39。圖2是矩形區域內路網的MATLAB簡略圖(圖2只表示各節點的位置關系，并不是實際位置)。

2)通過BP神經網絡得到各個路段的阻塞矩陣，取i-1，i-2，i-3，i-4，i-5，i-6，i-7，i-8，i-9，i-10，以10個時間段(每個時間段5 min)各路段的交通流量為輸入，i時刻的交通流量為輸出，參照MATLAB神經網絡工具箱增量因子kin默認值取1.05，減量因子kde默認值取0.7，動量因子α默認值取0.9。隱層取4個節點，經預測值計算t時刻39×39的阻塞矩陣，結果如下：

其中，阻塞等級分為5級(0.2,0.4,0.6,0.8,1)，值越大說明該路段暢通性越好，0表示對角元素或不連通。

3)采用DPO-AC算法求解t時刻路網兩節點的最優路徑，根據文獻[12]，參數設定為：信息啟發因子為1；期望因子為5，信息強度為100；螞蟻數目為50；最大迭代次數為50；期望矩陣是距離的倒數；矩形內40節點的信息素矩陣為：

4.2測試結果

首先測試算法的正確性。將本文算法中的動態阻塞因子ω設為定值，即每個路段的阻塞程度相同，求出s到v的靜態最短路徑，并與Dijkstra算法求出的靜態最優路徑進行對比，結果如圖3，可看到兩路徑完全重合，為3-6-7-12-19-34-35，驗證了本文算法的正確性。

圖3　Dijkstra算法與DPO-AC算法靜態最短路徑

圖4　DPO-AC算法求解的動態最優路徑

其次仿真驗證本文算法的動態性。在MATLAB下對DPO-AC算法中的動態阻塞因子進行了調整，具體是增大3-6路段的阻塞因子，DPO-AC算法避開了該阻塞路段，求得的動態最優路徑為：3-10-7-12-19-34-35(如圖4)。

然后驗證算法的實時性。如圖5是某日晚高峰時的搜狗地圖交通實況信息，從A點到C點的靜態最短路徑為線路1(A-B-C路段)。實時路況信息顯示，當前時刻線路1的B-C段出現了車速緩慢和擁堵的情況，DPO-AC算法選擇了各路段均為暢通狀態的線路2(A-D-C路段)為當前實時最優路徑。

圖5　晚高峰實時路況

圖6　兩種算法的迭代次數和平均最短路徑對比圖

最后驗證算法的穩定性和收斂速度。在相同的數據集和螞蟻數量(測試中為50只)前提下，將本文的DPO-AC算法與靳凱文[5]算法從迭代次數和平均最短路徑兩方面進行了對比。由于DPO-AC算法采用了分批的選擇策略并指定搜索方向，僅需迭代15次結果就已經趨于穩定，靳凱文算法卻一直處于浮動狀態(見圖6)，這說明DPO-AC算法的穩定性比較好。從達到收斂狀態所用時長來看，Dijkstra算法為20.103s，靳凱文算法迭代100次的時間為31.002s，DPO-AC算法迭代15次的時間為10.672s，可以看出DPO-AC算法在收斂速度上也具有較大優勢。

綜上，相對于經典的路徑尋優方法來說，DPO-AC算法有很明顯的靈活性，適應現代交通中存在的不確定因素；與以往的蟻群算法相比，所需要的螞蟻數和迭代次數都很小，收斂速度更快。

4結語

本文分析了現有蟻群算法在求解動態路網最優路徑中存在的問題，并針對其中存在的局部最優、缺乏動態因子以及搜索速度慢的問題做了相應的改進。測試結果表明DPO-AC算法在保證正確性的前提下，收斂速度和穩定性上有較大提高。但是本文還存在一定的不足，比如限定區域的延長比值不夠精確，BP神經網絡的時間間隔有待縮小。

參考文獻：

[1]付夢印,李杰,鄧志紅.限制搜索區域的距離最短路徑規劃算法[J].北京理工大學學報,2004,24(10):881-884.

FU Mengyin,LI Jie,DENG Zhihong.Route planning algorithm for the shortest sistance within a restricted searching area[J].Transactions of Beijing Institute of Technology,2004,24(10):881-884.

[2]李晶,閆軍.基于Dijkstra算法和Floyd算法的物流運輸最短路徑研究[J].科技信息,2012,34:575-576.

LI Jing,YAN Jun.Shortest path of logistics transportation based on based on Dijkstra algorithm and Floyd algorithm[J]. Science and Technology Information,2012,34:575-576.

[3]張偉,張秋菊.Dijkstra算法在AGV調度系統中的應用[J].機械設計與制造工程,2015,44(5):61-64.

ZHANG Wei,ZHANG Qiuju.Application of Dijkstra algorithm in AGV scheduling system[J].Mechanical Design and Manufacturing Engineering,2015,44(5):61-64.

[4]張學敏,張航.基于改進蟻群算法的最短路徑問題研究[J].自動化技術與應用,2009,28(6):4-7.

ZHANG Xuemin,ZHANG Hang.Research on shortest path problem based on improved ant colony algorithm[J].Automation Technology and Application,2009,28(6):4-7.

[5]靳凱文,李春葆,秦前清.基于蟻群算法的最短路徑搜索方法研究[J].公路交通科技,2006,23(3):128-130.

JIN Kaiwen,LI Chunbao,QIN Qianqing.Study on shortest path search method based on ant colony algorithm[J].Technology of Highway and Transport,2006,23(3):128-130.

[6]STIG N,BENGT R.Computer cartography shortest route program[M].Lund:The Royal University of Lund,1969.

[7]陸鋒,盧冬梅,崔偉宏.交通網絡限制搜索區域時間最短路徑算法[J].中國圖象圖形學報,1999,4(10):849-853.

LU Feng,LU Dongmei,CUI Weihong.The traffic network searching region limited time shortest path algorithm[J].Journal of Image and Graphics,1999,4(10):849-853.

[8]葛哲學,孫志強.神經網絡理論與MATLABR2007實現[M].北京:電子工業出版社,2007:111.

[9]高慧,趙建玉,賈磊.短時交通流預測方法綜述[J].濟南大學學報(自然科學版),2008,22(l):88-94.

GAO Hui,ZHAO Jianyu,JIA Lei.A review of short term traffic flow forecasting methods[J].Journal of University of Jinan (Science and Technology),2008,22(l):88-94.

[10]COLORM A,DORIGO M,MINIEZZO V.Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life.Paris,France:Elsevier Publishing,1991:134-142 .

[11]楊兆升.城市交通流誘導系統理論與模型[M].北京:人民交通出版社,2000.

[12]張可,凌海峰.基于均勻設計和混沌理論的蟻群算法參數調整[J].計算機工程,2012,38(14):141-143.

ZHANG Ke,LING Haifeng.Parameter turning of ant colony algorithm based on uniform design and chaos theory[J].Computer Engineering,2012,38(14):141-143.

(責任編輯：李磊)

收稿日期：2016-03-25

基金項目：山東省科技發展計劃項目(13GGX10118);青島經濟技術開發區重點科技發展計劃項目(2013-1-65)

作者簡介：周秀娟(1990—)，女，山東聊城人，碩士研究生，主要從事智能交通研究. E-mail:hrfy@263.net

中圖分類號：TP391.9

文獻標志碼：A

文章編號：1672-3767(2016)04-0114-07

Implementation and Simulation of a Dynamic Path Optimization Algorithm Based on Ant Colony Thoughts

ZHOU Xiujuan1,HUA Rong1,SHI Juan1,GAO Yuli2

(1.College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266590,China ;2.Qingdao Huanghai College,Qingdao,Shandong 266590,China )

Abstract:In order to improve the efficiency and instantaneity of path optimization algorithms,a dynamic path optimization algorithm named the ant colony algorithm with dynamic path optimization(DPO-AC) was proposed.On the basis of the improved ant colony algorithm and combined with neural network real-time prediction and limited area search,the proposed algorithm solved the problem of poor real-time performance and slow convergence of large network path optimization algorithms.Simulation results show that DL-ACO has better stability,convergence and instantaneity.

Key words:path optimization;algorithm;ant colony;limited area;block matrix

花嶸(1969—)，男，江蘇常州人，副教授，博士，主要從事高性能計算、多智能體等方面的研究，為本文通作者.