一種基于蟻群思想的動態(tài)路徑尋優(yōu)算法的實現(xiàn)及仿真

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

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

?

一種基于蟻群思想的動態(tài)路徑尋優(yōu)算法的實現(xiàn)及仿真

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

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

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

關(guān)鍵詞：路徑尋優(yōu)；算法；蟻群；限定區(qū)域；阻塞矩陣

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

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

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

1經(jīng)典蟻群算法及存在問題分析

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

(1)

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

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

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

(2)

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

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

蟻周模型公式如下：

(3)

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

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

2DPO-AC算法思想

蟻群算法從結(jié)構(gòu)上分為數(shù)據(jù)預處理和算法迭代兩部分。本文的DPO-AC算法主要從以下兩個方面對蟻群算法進行了改進：在數(shù)據(jù)預處理部分，通過設定算法的搜索區(qū)域和采用改進的BP神經(jīng)網(wǎng)絡來實時確定動態(tài)阻塞因子；在算法迭代中，改進了選擇概率和選擇策略，并通過改進算法的啟發(fā)信息矩陣來確定算法的搜索方向，以防止算法出現(xiàn)局部最優(yōu)。

2.1 數(shù)據(jù)預處理部分改進

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

MD=f×Esv。

(4)

圖1　 限定區(qū)域的選定

圖2　矩形區(qū)域內(nèi)路網(wǎng)簡略圖

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

(5)

得到的最值即為矩形區(qū)域的邊界值：

(6)

(7)

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

權(quán)值的調(diào)節(jié)公式為：

(8)

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

(9)

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

針對BP神經(jīng)網(wǎng)絡的隱層節(jié)點數(shù)目選取缺乏理論基礎的問題，本文采用多值對比的方法確定隱層節(jié)點數(shù)。根據(jù)隱層節(jié)點的經(jīng)驗公式：

(10)

2.2算法迭代部分改進分析

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

(11)

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

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

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

j=max(Pallowed)，

(12)

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

3DPO-AC算法設計及分析

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

Procedure DPO-AC

Input:NC_Max,C,R,S,V‘NC_Max是最大迭代次數(shù)；C是路網(wǎng)節(jié)點；R是初始信息素矩陣；S是起點；V是終點。

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

W=call BPNetwork(Q);‘BP神經(jīng)網(wǎng)絡求解動態(tài)阻塞矩陣

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測試方案

以天津市的交通路網(wǎng)為例，該路網(wǎng)有124個節(jié)點，以出行時間最短為目標求解最優(yōu)路徑。

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

2)通過BP神經(jīng)網(wǎng)絡得到各個路段的阻塞矩陣，取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神經(jīng)網(wǎng)絡工具箱增量因子kin默認值取1.05，減量因子kde默認值取0.7，動量因子α默認值取0.9。隱層取4個節(jié)點，經(jīng)預測值計算t時刻39×39的阻塞矩陣，結(jié)果如下：

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

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

4.2測試結(jié)果

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

圖3　Dijkstra算法與DPO-AC算法靜態(tài)最短路徑

圖4　DPO-AC算法求解的動態(tài)最優(yōu)路徑

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

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

圖5　晚高峰實時路況

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

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

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

4結(jié)語

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

參考文獻：

[1]付夢印,李杰,鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[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調(diào)度系統(tǒng)中的應用[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].自動化技術(shù)與應用,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]陸鋒,盧冬梅,崔偉宏.交通網(wǎng)絡限制搜索區(qū)域時間最短路徑算法[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]葛哲學,孫志強.神經(jīng)網(wǎng)絡理論與MATLABR2007實現(xiàn)[M].北京:電子工業(yè)出版社,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]楊兆升.城市交通流誘導系統(tǒng)理論與模型[M].北京:人民交通出版社,2000.

[12]張可,凌海峰.基于均勻設計和混沌理論的蟻群算法參數(shù)調(diào)整[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

基金項目：山東省科技發(fā)展計劃項目(13GGX10118);青島經(jīng)濟技術(shù)開發(fā)區(qū)重點科技發(fā)展計劃項目(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—)，男，江蘇常州人，副教授，博士，主要從事高性能計算、多智能體等方面的研究，為本文通作者.