基于改進蟻群算法的城市交通最短路徑算法

張水艦

(湖州職業(yè)技術(shù)學院，浙江 湖州 313000)

?

基于改進蟻群算法的城市交通最短路徑算法

張水艦

(湖州職業(yè)技術(shù)學院，浙江 湖州 313000)

蟻群算法作為一種尋優(yōu)性能良好的智能算法，是解決最短路徑問題的一種有效的方式。但是，基本蟻群算法真接運用于交通網(wǎng)絡(luò)中路徑的尋優(yōu)存在一些不足。文章針對基本蟻群算法的不足對其進行了改進，根據(jù)交通網(wǎng)絡(luò)的特點限定了解的搜索范圍和改進了蟻群算法的轉(zhuǎn)移規(guī)則，并對信息素的更新規(guī)則作了改進。仿真實驗結(jié)果表明，改進了的蟻群算法在求解最短路徑時比基本蟻群算法性能有較大的提高。

城市交通；蟻群算法；最短路徑；交通網(wǎng)絡(luò)

0 引言

隨著城市交通量的急劇增加，交通擁堵問題日益嚴重，已經(jīng)影響到了人們的出行，找到一條最短的出行路徑是出行者首先想要做的事情。最短路徑問題已成為眾多學者研究的一個熱點問題，此問題的解決可以為交通流分配、城市道路設(shè)計等交通網(wǎng)絡(luò)優(yōu)化提供理論基礎(chǔ)。可以說最短路徑問題是關(guān)系到城市

發(fā)展的一個重要問題，具有重要的理論和實踐意義。國內(nèi)外學者對在交通網(wǎng)絡(luò)中尋求最短路徑的算法進行了大量的研究，并取得了豐碩的成果。最有代表性就是Dijkstra算法，Dijkstra算法能找到全局最優(yōu)解[1]；為了提高算法的效率，許多研究者也提出了一些啟發(fā)式算法，如A*、遺傳算法、免疫算法等。最短路徑的選擇，最后都歸結(jié)為找到一條耗費成本最少的路徑，如時間最快、距離最短等。通過最短路徑的選擇，可以將無序的交通出行變得有序，減少出行的盲目性，以優(yōu)化交通流的分布，提高城市交通網(wǎng)絡(luò)的效率，緩解交通擁堵。智能優(yōu)化算法的興起為在復(fù)雜交通網(wǎng)絡(luò)中尋找最短路徑提供了可行的方式。意大利學者Colorni A，Dorigo M和Maniezzo V于1992年提出了一種新型的智能優(yōu)化算法——蟻群算法(Ant Colony Optimization，ACO)，實踐證明蟻群算法具有良好的尋優(yōu)性能[2-4]。該算法模擬蟻群搜尋食物的過程中按最短路徑運送食物的能力，這種找到最短路徑的能力跟在交通網(wǎng)絡(luò)中找到最短出行路徑是同一性質(zhì)的優(yōu)化問題，因此蟻群算法可以用在交通網(wǎng)絡(luò)最短路徑的尋找上。

1 最短路徑誘導(dǎo)蟻群算法

城市交通網(wǎng)絡(luò)是具有空間分布的地理網(wǎng)絡(luò)，具有路線長度、通行時間、路況等屬性。城市交通網(wǎng)絡(luò)是由交叉路口抽象成的節(jié)點和由路線抽象成的邊組成的網(wǎng)絡(luò)，并把交通阻抗表示為網(wǎng)絡(luò)邊的權(quán)值，因此城市交通網(wǎng)絡(luò)是一個加權(quán)的有向圖。交通網(wǎng)絡(luò)可以映射成一個連通帶權(quán)有向圖G：(V，E，W)。其中，V表示網(wǎng)絡(luò)上所有節(jié)點的集合，E表示網(wǎng)絡(luò)上所有邊的集合，W是網(wǎng)絡(luò)邊的非負權(quán)值。

1.1 基本蟻群算法

昆蟲學家在研究螞蟻時發(fā)現(xiàn)螞蟻在覓食過程中會釋放一種特有的物質(zhì)——信息素，螞蟻在尋找路徑的過程中能檢測到其它螞蟻所釋放的信息素，并利用信息素來引導(dǎo)自己的移動方向，且以較高的概率選擇信息素量較多的路徑，螞蟻在此路徑上行進時又釋放出信息素，因此信息素量多的路徑經(jīng)過的螞蟻會更多，經(jīng)過的螞蟻越多又會增加此路徑上的信息素量，由此大量螞蟻的覓食過程就構(gòu)成一種對信息素的正反饋過程，從而逐漸找到一條最短的覓食路徑。蟻群算法就是模擬螞蟻覓食過程中形成最短路徑的原理，設(shè)計出的一種群智能算法[5-6]。

如圖1所示，螞蟻從蟻穴出發(fā)去尋找食物，在最初階段由于兩條路徑上都沒有信息素，螞蟻以相同的概率選擇這兩條路徑，然而走短路徑的螞蟻會更快地回來，經(jīng)過路徑的次數(shù)也更多，留下信息素自然就多，經(jīng)過一段時間后，在短路徑上會有更多的信息素，誘使螞蟻選擇短路徑。

圖1 螞蟻覓食所選路徑示意圖

基本蟻群算法的流程如下：

(1)蟻群A(t)初始化：確定蟻群規(guī)模等；

(2)根據(jù)螞蟻到達目的地的路徑長度計算每只螞蟻的適應(yīng)度；

(3)根據(jù)螞蟻的適應(yīng)度，對螞蟻所經(jīng)過的路徑按一定的規(guī)則釋放信息素；

(4)后面出發(fā)的螞蟻根據(jù)前面螞蟻在路徑上所留下的信息素濃度選擇到達目的地的路徑；

(5)留在路徑上的信息素隨著時間按一定速率不斷消散。

蟻群初始化使各條路徑上的信息素濃度相等，即當t=0時，τij(0)=C(C為常數(shù))，τij(0)表示初始時刻路段ij的信息素量。每只螞蟻k=(k=1，2，…，m)(設(shè)螞蟻的規(guī)模為m)在覓食過程中根據(jù)路徑上的信息素濃度按照隨機比例規(guī)則選擇下一行進路徑，即在t時刻處于位置i的螞蟻k按一定概率選擇移動到位置，此概率稱為轉(zhuǎn)移概率，按公式(1)計算：

圖2 基本蟻群算法流程圖

(1)

notcrossedk——螞蟻k從位置i下一步允許移動到的位置，notcrossedk={0，1，…，n-1}。

在所有螞蟻完成一次路徑的尋找后，各路段上信息素量按下式進行更新：

τij(t+1)=ρ·τij(t)+Δτij(t，t+1)

(2)

(3)

1.2 改進的最短路徑蟻群算法

如上所述蟻群算法是模擬螞蟻覓食過程中尋到最優(yōu)路徑的原理。實踐證明蟻群算法具有較強的尋優(yōu)能力。雖然蟻群算法在許多優(yōu)化問題中表現(xiàn)出優(yōu)良的性能，然而還得對基本蟻群算法進行改進才能適用某些特定領(lǐng)域的優(yōu)化問題。例如，當蟻群算法運用于在交通網(wǎng)絡(luò)中求解最短路徑時，會出現(xiàn)不適應(yīng)的問題：(1)基本蟻群算法中螞蟻的行進過程中選擇下一位置是遵循隨機原則，沒有對覓食方向進行引導(dǎo)，影響了搜索的速度；(2)由于信息素容易在局部最優(yōu)解附近增加過大，造成尋優(yōu)結(jié)果易于陷入局部最優(yōu)解。

本文充分利用基本蟻群算法的優(yōu)良性能，結(jié)合交通網(wǎng)絡(luò)最短路徑問題自身的特點，對基本蟻群算法進行了改進，提出了一種適合求解交通網(wǎng)絡(luò)最短路徑問題的蟻群算法。針對基本蟻群算法的不足之處，對基本蟻群算法作了如下改進：

圖3 螞蟻搜索范圍示意圖

(1)具有地理分布的城市交通網(wǎng)絡(luò)，相隔較遠的兩點之間一般不會有直接連接兩點的直通路徑，但兩點之間的最短路徑一般是沿著這兩點之間的連線分布的，不會偏離這條直線很遠的距離，為此可以限定搜索范圍，這是符合實際情況的，在實踐中是合理的。為此在算法的實現(xiàn)過程中可以將螞蟻的搜索行為集中到一定范圍內(nèi)，即限制在最優(yōu)解的附近，這可以提高搜索效率，加快收斂速度，提高解的質(zhì)量。

搜索范圍按如下方法確定，如圖3所示，假設(shè)點A和B是起訖點，以A和B點作為橢圓的焦點，以AB連線的直線距離作為橢圓的焦距2C。搜索范圍取圖中的橢圓，橢圓的面積取為以長軸2a為邊長的正方形的面積的三分之一，由此可以得到下式：

(4)

(5)

由(5)式可解得：

(6)

由此可以確定出橢圓的大小。

(2)為解決搜索的方向性問題，需改進蟻群算法的轉(zhuǎn)移規(guī)則。如上分析可知，在交通網(wǎng)絡(luò)中從起始點出發(fā)到終點的最短路徑不會偏離起始點與終點的連線很遠的距離，為此可用當前節(jié)點和下一節(jié)點的連線與當前點和終點的連線的交角來表示方向，這個夾角的取值在0～π之間。如圖4所示，假設(shè)A點為起點，B點為終點，某只螞蟻已從A點行進到了節(jié)點i，在選擇下一個節(jié)點時假設(shè)有兩個節(jié)點j和E可選擇，從圖上可以看出ij與CB的夾角θ小于iE與iB的夾角φ，這時可以看出ij自然更偏向于i跟B的連線。如果路段ij和iE上信息素量相等、路況大致相同，螞蟻將沿著路段iE行進，這也是符合平常人們選擇路徑的心理的。為此可對螞蟻的轉(zhuǎn)移規(guī)則進行改進。

圖4 搜尋方向示意圖

在改進的最短路徑蟻群算法中，在計算螞蟻在行進過程中選擇下一位置的轉(zhuǎn)移概率時，對式(1)中的系數(shù)ηij進行了改進，加入了方向的啟發(fā)信息。ηij按下式計算：

ηij=1/wij·θ

(7)

其中wij為路段ij的交通阻抗，θ如上所述。從式(7)中可以看出，當路段的阻抗越小，路段越朝向終點時ηij的值就越大，此路段被選擇的概率也就越大。

(3)對信息素更新規(guī)則的改進

在一次循環(huán)之后，基本蟻群法要取每只螞蟻經(jīng)過的路徑進行信息素的更新，這種信息素更新規(guī)則可以防止算法的尋優(yōu)解陷入局部最優(yōu)解，但會減慢收斂速度。為了提高搜索質(zhì)量，改進算法的性能，引進遺傳算法中的選擇機制，對基本蟻群算法的信息素更新規(guī)則進行改進。首先選出適應(yīng)度的螞蟻，即選出前m只所經(jīng)路徑最短的螞蟻，然后再對選出的螞蟻所經(jīng)過的路徑進行信息素的更新，信息素的釋放量也根據(jù)路徑的長短依次遞減。信息量的增量仍然按公式(2)、(3)計算，此時m表示所經(jīng)路徑為最短的前m只螞蟻。為避免搜索的停滯，規(guī)定交通網(wǎng)絡(luò)上的每條邊的信息素量的值限制在[τmin，τmax]，某條邊的信息量大于τmax時按τmax計算，當信息素小于τmin時，按τmin計算。

2 仿真試驗

圖5 某城市交通網(wǎng)絡(luò)圖

對以上所述最短路徑蟻群算法進行試驗，以1015個節(jié)點，1006條路段的交通網(wǎng)絡(luò)作為試驗對象(圖5)，在ArcGIS10.2的環(huán)境下，以C#作為開發(fā)工具仿真試驗了改進蟻群算法。選取了三組起訖點做試驗，試驗結(jié)果如表1所示(解為到達目的地的最短時間)。從結(jié)果中可以看出改進了的蟻群算法比基本蟻群算法性能有明顯的提高。

表1 試驗結(jié)果表(單位：min)

3 結(jié)語

蟻群算法是性能優(yōu)良的智能優(yōu)化算法，本文對基本蟻群算法進行了改進，使蟻群算法適合在交通網(wǎng)絡(luò)上進行路徑尋優(yōu)。本文在充分利用基本蟻群算法良好的尋優(yōu)性能的基礎(chǔ)上，根據(jù)交通網(wǎng)絡(luò)地理空間分布特征，以及起訖點之間最短線路的方向性，對算法的搜索范圍和信息素更新規(guī)則等作了改進。

試驗表明，與直接運用基本蟻群算法求解最短路徑相比，改進的最短路徑蟻群算法能夠有效地找到起訖點之間的最短路徑。本文提出的最短路徑蟻群算法可用于人們出行中尋求最短的出行路徑，也可用于交通流的分配中，具有一定的理論和現(xiàn)實意義。

[1]郝新剛，任傳祥，劉法勝.基于改進Dijkstra算法的路徑優(yōu)化仿真研究[J].西部交通科技，2010.11：19-22.

[2]梁滿朝，李文勇，李福祥.基于蟻群算法和群決策理論的動態(tài)路徑優(yōu)化研究[J].西部交通科技，2012(2)：58-63.

[3]宋錦娟，白艷萍.基于改進蟻群算法的最短路徑問題研究及應(yīng)用[J].數(shù)學的實踐與認識，2013，43(3)：156-164.

[4]馬 軍，王 巖.改進的蟻群算法求解旅行Agent問題[J].計算機工程與應(yīng)用，2010，46(11)：35-37.

[5]李士勇，陳永強，李 研.蟻群算法及其應(yīng)用[M].哈爾濱工業(yè)大學出版社，2004.

[6]馬 良，朱 剛，寧愛兵.蟻群優(yōu)化算法[M].上海：科學出版社，2008.

Shortest Path Algorithm of Urban Traffic Based on Improved Ant Colony Algorithm

ZHANG Shui-jian

(Huzhou Vocational and Technical College，Huzhou，Zhejiang，313000)

The ant colony algorithm is an intelligent algorithm with good optimization search performance，and is also an effective way to solve the shortest path problem.However，the path optimization search of directly using the basic ant colony algorithm in transport network has some shortcomings.This article improved the inadequacies of basic ant colony algorithm，confined the search scope and im-proved the transfer rules of ant colony algorithm based on the characteristics of transport network，and improved the updating rules of pheromone.Simulation results showed that the improved ant colony al-gorithm has much better performance than the basic ant colony algorithm in terms of solving the shortest path.

Urban traffic；Ant colony algorithm；Shortest path；Transportation network

張水艦(1972—)，講師，研究方向：交通網(wǎng)絡(luò)優(yōu)化。

浙江省教育廳自然科學研究計劃項目(Y20 1432450)；湖州市科技局項目(2014YZ09)。

U412.37

A

10.13282/j.cnki.wccst.2015.11.020

1673-4874(2015)11-0089-06

2015-10-15