基于改進(jìn)蟻群算法的城市交通最短路徑算法

張水艦

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

?

基于改進(jìn)蟻群算法的城市交通最短路徑算法

張水艦

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

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

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

0 引言

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

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

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

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

1.1 基本蟻群算法

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

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

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

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

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

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

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

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

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

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

圖2 基本蟻群算法流程圖

(1)

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

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

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

(2)

(3)

1.2 改進(jìn)的最短路徑蟻群算法

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

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

圖3 螞蟻搜索范圍示意圖

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

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

(4)

(5)

由(5)式可解得：

(6)

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

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

圖4 搜尋方向示意圖

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

ηij=1/wij·θ

(7)

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

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

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

2 仿真試驗(yàn)

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

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

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

3 結(jié)語(yǔ)

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

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

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

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

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

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

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

[6]馬 良，朱 剛，寧愛(ài)兵.蟻群優(yōu)化算法[M].上海：科學(xué)出版社，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)化。

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

U412.37

A

10.13282/j.cnki.wccst.2015.11.020

1673-4874(2015)11-0089-06

2015-10-15