周秀娟，花　嶸，史　娟，高玉勵(lì)

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

?

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

周秀娟1，花嶸1，史娟1，高玉勵(lì)2

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

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

蟻周模型公式如下：

(3)

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

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

2DPO-AC算法思想

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

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

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

MD=f×Esv。

(4)

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

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

利用長(zhǎng)軸MD的值求解橢圓方程

(5)

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

(6)

(7)

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

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

(8)

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

(9)

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

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

(10)

2.2算法迭代部分改進(jìn)分析

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

(11)

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

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

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

j=max(Pallowed)，

(12)

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

3DPO-AC算法設(shè)計(jì)及分析

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

Procedure DPO-AC

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

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

W=call BPNetwork(Q);‘BP神經(jīng)網(wǎng)絡(luò)求解動(dò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算法仿真測(cè)試及分析

4.1測(cè)試方案

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

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

2)通過(guò)BP神經(jīng)網(wǎng)絡(luò)得到各個(gè)路段的阻塞矩陣，取i-1，i-2，i-3，i-4，i-5，i-6，i-7，i-8，i-9，i-10，以10個(gè)時(shí)間段(每個(gè)時(shí)間段5 min)各路段的交通流量為輸入，i時(shí)刻的交通流量為輸出，參照MATLAB神經(jīng)網(wǎng)絡(luò)工具箱增量因子kin默認(rèn)值取1.05，減量因子kde默認(rèn)值取0.7，動(dòng)量因子α默認(rèn)值取0.9。隱層取4個(gè)節(jié)點(diǎn)，經(jīng)預(yù)測(cè)值計(jì)算t時(shí)刻39×39的阻塞矩陣，結(jié)果如下：

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

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

4.2測(cè)試結(jié)果

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

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

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

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

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

圖5　晚高峰實(shí)時(shí)路況

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]付夢(mèng)印,李杰,鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報(bào),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算法的物流運(yùn)輸最短路徑研究[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)中的應(yīng)用[J].機(jī)械設(shè)計(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]張學(xué)敏,張航.基于改進(jìn)蟻群算法的最短路徑問(wèn)題研究[J].自動(dòng)化技術(shù)與應(yīng)用,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)絡(luò)限制搜索區(qū)域時(shí)間最短路徑算法[J].中國(guó)圖象圖形學(xué)報(bào),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]葛哲學(xué),孫志強(qiáng).神經(jīng)網(wǎng)絡(luò)理論與MATLABR2007實(shí)現(xiàn)[M].北京:電子工業(yè)出版社,2007:111.

[9]高慧,趙建玉,賈磊.短時(shí)交通流預(yù)測(cè)方法綜述[J].濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版),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]楊兆升.城市交通流誘導(dǎo)系統(tǒng)理論與模型[M].北京:人民交通出版社,2000.

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

(責(zé)任編輯：李磊)

收稿日期：2016-03-25

基金項(xiàng)目：山東省科技發(fā)展計(jì)劃項(xiàng)目(13GGX10118);青島經(jīng)濟(jì)技術(shù)開(kāi)發(fā)區(qū)重點(diǎn)科技發(fā)展計(jì)劃項(xiàng)目(2013-1-65)

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

中圖分類(lèi)號(hào)：TP391.9

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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—)，男，江蘇常州人，副教授，博士，主要從事高性能計(jì)算、多智能體等方面的研究，為本文通作者.