仿真實(shí)現(xiàn)基于自適應(yīng)蟻群算法的公交查詢算法

摘要:公交查詢系統(tǒng)的設(shè)計(jì)可以解決在龐大的公交網(wǎng)絡(luò)中公交路線選擇的問題。該文將進(jìn)一步改進(jìn)基于自適應(yīng)蟻群算法的公交查詢算法，即提出了初始化的問題和解決了可以步行的問題。使得該文的算法具有更快的速度，更好的尋找最優(yōu)解的能力以及更廣泛的適應(yīng)范圍。文末給出了運(yùn)行的實(shí)例表明該文設(shè)計(jì)的方法是行之有效的。

關(guān)鍵詞:公交;換乘;仿真;

中圖分類號(hào):TP18文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)01-186-02

Simulating Bus Travel Transit Path Query Algorithm Based on Adaptive Ant Colony Algorithm

SUN Li-na1， ZHANG Li2， WANG Lin3

(1.Minsheng College， Henan University， Kaifeng 475004， China; 2.Chenggong College of Henan University of Finance and Economics Gongyi， Zhengzhou 451200， China; 3.School of Humanities and Social Science， Beijing Institute of Technology， Beijing 100081， China)

Abstract: Bus travel transit path query system can deal with the problem of searching the best routine among the huge and complex bus net. This paper will further improve the bus travel transit path query algorithm which based on adaptive ant colony algorithm， namely that the initialization of the problems and solutions to the problems you can walk This makes the paper's algorithm has a faster speed， better ability to find the optimal solution， as well as to adapt to a wider range .We also design a delayed updating pheromones method reducing the computational complexity sharply.Results based on experiments show our method is effective.

Key words: bus; ant algorithm; simulation

近年來，由于公交系統(tǒng)的發(fā)展，越來越多的城市居民可以方便的乘坐公交車出行，這使得城市的交通堵塞以及環(huán)境污染大大緩解。公交線路的增多的同時(shí)也帶來了多條線路的選擇問題，為此需要設(shè)計(jì)公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)以方便人們的出行選擇。

設(shè)計(jì)公交查詢系統(tǒng)的核心是給出任兩個(gè)站點(diǎn)之間尋找最優(yōu)路徑的算法，目前研究該算法設(shè)計(jì)的主要有三種方法。第一種方法是基于圖論的Dijkstra算法，結(jié)合公交乘車的特殊性進(jìn)行一些改進(jìn)。如文獻(xiàn)[1-2]等，但最短路算法本質(zhì)上不適合公交網(wǎng)絡(luò)。第二種方法是隱式枚舉算法，此類算法一般假定換乘次數(shù)不超過兩次，對(duì)兩個(gè)站點(diǎn)之間的所有路徑進(jìn)行搜索。如文獻(xiàn)[3-5]等，其中文獻(xiàn)[4]設(shè)計(jì)了新的矩陣運(yùn)算，文獻(xiàn)[5]設(shè)計(jì)了燃燒算法都大大降低了運(yùn)算的復(fù)雜度。第三種方法是啟發(fā)式算法，文獻(xiàn)[6]等運(yùn)用懲罰迭代的方法研究多路徑的尋找，文獻(xiàn)[7]等運(yùn)用蟻群算法尋求最優(yōu)路徑。對(duì)于非啟發(fā)式算法，當(dāng)處理的規(guī)模比較小時(shí)是可以采用的，但當(dāng)公交網(wǎng)絡(luò)的規(guī)模比較大時(shí)，算法計(jì)算量很大，要得到最優(yōu)解的代價(jià)很高，導(dǎo)致程序運(yùn)行時(shí)間過長(zhǎng)，這是無法滿足實(shí)時(shí)查詢系統(tǒng)的設(shè)計(jì)要求的。雖然有部分學(xué)者給出了啟發(fā)式的蟻群算法，但傳統(tǒng)的蟻群算法收斂速度慢容易早熟。

筆者前篇論文《基于自適應(yīng)蟻群算法的公交查詢算法設(shè)計(jì)》中將利用蟻群算法設(shè)計(jì)公交查詢系統(tǒng)的核心算法，即搜索出一條從起始站點(diǎn)到目的站點(diǎn)的最優(yōu)路徑。上文將公交網(wǎng)絡(luò)按直達(dá)關(guān)系抽象成有向圖，用螞蟻在各個(gè)節(jié)點(diǎn)之間的行走代表公交線路的選擇。針對(duì)基本蟻群算法收斂速度和早熟之間的矛盾，提出了自適應(yīng)信息素更新的蟻群算法，并設(shè)計(jì)了遲滯更新信息素的方法，使得運(yùn)算量大大減少。與公交查詢的其它方法相比，上文所設(shè)計(jì)的方法具有更快的速度，更好的尋找最優(yōu)解的能力以及更廣泛的適應(yīng)范圍。本文將進(jìn)一步改進(jìn)基于自適應(yīng)蟻群算法的公交查詢算法和研究它的仿真實(shí)現(xiàn)。

1 算法改進(jìn)

1.1 初始化問題

為每個(gè)螞蟻建立一個(gè)標(biāo)志位，標(biāo)志它是否到達(dá)目的站點(diǎn)，初始化為0，并且為每個(gè)螞蟻建立一個(gè)禁忌表，記錄它走過的站點(diǎn)，初始化為空。在初始化每條邊的信息量時(shí)，常用的方法是每條邊均初始化為同一個(gè)常數(shù)。筆者就此方法曾做過實(shí)驗(yàn)，結(jié)果表明螞蟻的收斂速度很慢，它們漫無目的的游蕩在公交網(wǎng)絡(luò)上。為了加快螞蟻的收斂速度，需要給螞蟻一些啟示，即對(duì)離目的站點(diǎn)比較近的那些站點(diǎn)初始化時(shí)信息量要高一些，這樣螞蟻搜索時(shí)很容易收斂到目的站點(diǎn)，從而產(chǎn)生有效的路徑。用τij(0)表示初始的信息量:

1.2 可以步行的問題的解決

在基于自適應(yīng)蟻群算法的公交查詢的算法中都沒有考慮步行的情況，而實(shí)際中步行是常見的。比如從站點(diǎn)A到站點(diǎn)B，中間不步行，將至少轉(zhuǎn)乘三次才能到達(dá)，但是若從中間某個(gè)站點(diǎn)下車，步行到臨近的另外一個(gè)站點(diǎn)，則只需轉(zhuǎn)乘兩次。人們?cè)谵D(zhuǎn)車時(shí).并不是下車后直接在下車的站點(diǎn)處轉(zhuǎn)車，往往需要步行小段距離到附近的站點(diǎn)去轉(zhuǎn)車。人們選擇這種方式通常可以減少換乘次數(shù)。為了更加符合實(shí)際情況，必須考慮帶有步行的問題。上面建立的蟻群算法模型可以很容易的推廣到帶有步行的乘車方案。為了表示步行，添加一個(gè)0號(hào)的站點(diǎn)，任何一個(gè)1到m的站點(diǎn)都可以和0號(hào)站點(diǎn)相互直達(dá)。如果一條 路徑中有Si-0-Sj則表示Si到Sj之間為步行。0站點(diǎn)的出度也是需要關(guān)注的因素，因?yàn)樗婕暗睫D(zhuǎn)移概率計(jì)算中用到的啟發(fā)因子。由于從0點(diǎn)出發(fā)可以到任何點(diǎn)，則它的出度d0 = m，如果仍按照上面的方法，ηij(t) =(di+dj)/2;(i; j=1…m)，則ηij(t)=(di +d0)/2 =(di+m)/2，由于所有的dj比m小得多，則對(duì)同一個(gè)i來說，轉(zhuǎn)移到0的概率比j要大得多，這樣子螞蟻將總在0附近搜索，而無法得到最優(yōu)解。所以應(yīng)將螞蟻的出度強(qiáng)制修改為與dj相差不太多，當(dāng)然如果修改后d0太低了，則螞蟻將不會(huì)步行，這將退化為沒有步行的情況。記 ，可以令d0∈[D/2，2*D].

綜合上述，0站點(diǎn)的信息如下:

T00 = 0; T0i = 1; Ti0 = 1; i = 1， 2…m

D0 = 1，2…m; d0∈2 [M/2; 2*M]

按照上述信息可以將0站點(diǎn)加入到圖中去，就可以運(yùn)用已經(jīng)設(shè)計(jì)好的蟻群算法計(jì)算，唯一需要修改的地方是函數(shù)f(v)，設(shè)修改后函數(shù)為f(v)，當(dāng)v中不含0站點(diǎn)時(shí)，無論目標(biāo)是求最小換乘路線，最短時(shí)間，還是最小費(fèi)用，f(v)= f(v).

當(dāng)v中有0站點(diǎn)時(shí)， 設(shè)0站點(diǎn)的上一個(gè)站乘路線，根據(jù)f(v)的求法可知，仍可以利用f(v)來求v的最小換乘次數(shù)。若要求最短時(shí)間，只需用Si到Sj的步行時(shí)間代替Si -0 -Sj的時(shí)間。若要求最小費(fèi)用，只需記Si -0-Sj這一段的費(fèi)用為零。

2 仿真試驗(yàn)

為了檢驗(yàn)本文提出的蟻群算法的效率，筆者搜集了北京市公交的部分?jǐn)?shù)據(jù)。數(shù)據(jù)中共有3957個(gè)站點(diǎn)，520條線路。對(duì)于蟻群算法的參數(shù)，取α=β=0.5， ρmax=0.8， ρmin=0.2，螞蟻數(shù)量為20只，迭代次數(shù)100次。表格1顯示了總站點(diǎn)數(shù)分別取500/2000/3957個(gè)站點(diǎn)，分別從中隨機(jī)取50對(duì)站點(diǎn)三種算法的運(yùn)行情況 [7-8]。

從表1中可以看出隱式枚舉與基本蟻群算法的運(yùn)行時(shí)間隨著站點(diǎn)數(shù)的增多迅速的增加，特別是基本蟻群算法在3957個(gè)站點(diǎn)時(shí)竟達(dá)到33s，而運(yùn)用自適應(yīng)以及遲滯更新的方法運(yùn)行時(shí)間大大減少。從平均最優(yōu)值可以看出，基本蟻群算法比隱式枚舉的三組數(shù)據(jù)高很多，這是因?yàn)榛鞠伻核惴ㄈ菀紫萑朐缡欤赃m應(yīng)的蟻群算法可以很好的避免這種現(xiàn)象，可以搜索出來的更優(yōu)的值，所以自適應(yīng)蟻群算法的三組最優(yōu)值相比于隱式枚舉就很接近了。值得一提的是，本文的自適應(yīng)蟻群算法沒有對(duì)換乘的次數(shù)限制，而隱式枚舉在換乘次數(shù)大于2次時(shí)，計(jì)算量會(huì)猛增，有些甚至根本無法實(shí)現(xiàn)。圖1是迭代過程中ρ(t)隨時(shí)間的變化，可以發(fā)現(xiàn)ρ(t)是動(dòng)態(tài)變化的，隨著迭代而逐漸降低。

3 結(jié)束語

與公交查詢的其它方法相比，本文所設(shè)計(jì)的方法具有更快的速度，更好的尋找最優(yōu)解的能力以及更廣泛的適應(yīng)范圍。

近年來蟻群算法出現(xiàn)了很多變化，例如混沌蟻群算法，蟻群算法與遺傳算法的結(jié)合等等，這些新的發(fā)展將為蟻群算法的應(yīng)用開闊更為廣闊的前景。本文只使用了最簡(jiǎn)單的蟻群算法，那些更有效的蟻群算法在公交查詢算法的設(shè)計(jì)中的應(yīng)用是值得進(jìn)一步研究的。公交查詢算法中的步行問題是亟待解決的問題，蟻群算法良好的靈活性為該問題的解決展現(xiàn)了一線曙光。

參考文獻(xiàn):

[1] 王莉，李文權(quán).公共交通系統(tǒng)最佳路徑算法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版，2004，34(2):264-267.

[2] 嚴(yán)寒冰，劉迎春. 基于GIS 的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào)，2000，25(3):210-215.

[3] 趙巧霞，馬志強(qiáng)，張發(fā).以最小換乘次數(shù)和站數(shù)為目標(biāo)的公交出行算法[J].計(jì)算機(jī)應(yīng)用，2004，24(12):136-137.

[4] 鮑江宏，關(guān)毅璋.基于矩陣運(yùn)算的公交查詢高效算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44(10):198-200.

[5] 張?chǎng)危瑒⒃婪澹嵔A，等.針對(duì)公交的最優(yōu)路徑算法[J].計(jì)算機(jī)工程與應(yīng)用，2006(22):207-209.

[6] 閆小勇，牛學(xué)勤.公交網(wǎng)絡(luò)多路徑選擇啟發(fā)式算法研究[J].城市交通，2005(3):23-26.

[7] 李文勇，王煒，陳學(xué)武.公交出行路徑螞蟻算法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4(4):102-105.

[8] 趙寶江，李士勇，金俊.給予自適應(yīng)路徑選擇和信息素更新的蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(3):12-14.