国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

交通網(wǎng)絡(luò)最優(yōu)路徑搜索的蟻群算法

2013-10-21 01:10:28周竹萍易富君
關(guān)鍵詞:路段螞蟻局部

周竹萍 易富君

1.南京理工大學(xué),交通工程系,南京 210094

2.招商局重慶交通科研設(shè)計(jì)院有限公司,重慶 404100

0 引言

動(dòng)態(tài)最優(yōu)路徑搜索算法是智能交通系統(tǒng)(ITS)技術(shù)應(yīng)用的關(guān)鍵問題之一。目前的路徑誘導(dǎo)系統(tǒng)不夠高效,在路徑選擇算法方面還不完善,缺乏實(shí)時(shí)性高、有效性強(qiáng)的路徑搜索算法,故交通最優(yōu)路徑選擇問題一直是各國(guó)交通領(lǐng)域投資研究的重點(diǎn)問題。

最優(yōu)路徑選擇是指在給定的城市道路網(wǎng)中尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)之間的最優(yōu)路徑的問題。解決該問題的經(jīng)典算法是Dijkstra 算法,是一種靜態(tài)的局部最優(yōu)算法[1]。該算法簡(jiǎn)單、易于實(shí)現(xiàn),但也存在如下的局限性:在網(wǎng)絡(luò)節(jié)點(diǎn)和路徑較多的情況下,搜索效率會(huì)大大降低,有時(shí)甚至找不到最短路徑,且對(duì)于路徑權(quán)值隨時(shí)間動(dòng)態(tài)變化的動(dòng)態(tài)網(wǎng)絡(luò),如反映路徑堵塞和暢通信息的實(shí)時(shí)交通系統(tǒng)網(wǎng)絡(luò)就不適用。

隨著群智能技術(shù)的出現(xiàn),基于群體仿生理論的蟻群算法為最短路徑選擇問題提供了一個(gè)新的解決方法。但是,由于蟻群算法本身的局限性,容易陷入局部最優(yōu)解,且其道路信息素初始值固定,使算法收斂速度較慢[2]。近年來,我國(guó)學(xué)者提出了一系列的改進(jìn)思路,如高尚、吳霜華等都考慮在蟻群算法中引入混沌理論[3-4],黃貴玲則在原始算法中加入直線優(yōu)化啟發(fā)信息,趙寶江提出了一種基于自適應(yīng)路徑選擇和動(dòng)態(tài)信息素更新的蟻群算法[5]。國(guó)外的重要研究包括:Guenther Fuellerer,Yuvraj Gajpal等也在信息素局部更新中加入幾種其它啟發(fā)式算法以提高算法效率,Alberto V.Donati 通過改進(jìn)更新規(guī)則完成了兩個(gè)及多個(gè)目標(biāo)的優(yōu)化[6-8]等。本文分析了傳統(tǒng)蟻群算法的不足,改進(jìn)了信息素更新方式,使算法更滿足求解交通系統(tǒng)的最優(yōu)路徑問題。

1 問題概述與模型

如果把城市道路網(wǎng)中的道路起始點(diǎn)、目標(biāo)點(diǎn)和交叉路口等表示為節(jié)點(diǎn),把道路表示為連接節(jié)點(diǎn)的?。ㄟ叄?,把道路的長(zhǎng)度、通行時(shí)間和擁塞程度等屬性表示為弧的權(quán),那么道路網(wǎng)就可以被抽象成為一個(gè)帶權(quán)的有向圖,如圖,1 所示。

圖1 由節(jié)點(diǎn)和弧構(gòu)成的有向道路網(wǎng)絡(luò)圖Fig.1 Traffic network composed of nodes and arcs with direction

在賦權(quán)有向圖G 上,一條以i 為始點(diǎn),j 為終點(diǎn)的路徑是一個(gè)弧的序列,其中前一個(gè)弧的終點(diǎn)是后一個(gè)弧的起點(diǎn),且第一個(gè)弧的起點(diǎn)是i,最后一個(gè)弧的終點(diǎn)是j,可用一個(gè)有序的點(diǎn)集來描述一條路。一條路的費(fèi)用是這條路徑上所有弧的費(fèi)用之和。用賦權(quán)有向圖來表示路徑的費(fèi)用即為該賦權(quán)有向圖中這條路徑上所有路徑權(quán)值之和。

給定帶權(quán)有向圖G=(V,{E}),其中V 是包含n個(gè)頂點(diǎn)的頂點(diǎn)集,E 是包含m 條弧段的集合,<v,w>是從v 到w 的弧,c(v,w)是?。紇,w>的非負(fù)權(quán)值,設(shè) vs,vt為V 中的頂點(diǎn),Pst={vo=vs,v1=,…,vn=vt}為V 中由vs到 vt的一條路徑,則路徑 Pst的權(quán)值總和TW(Pst)可表示為[9]:

最優(yōu)路徑問題就是指在帶權(quán)有向圖中,尋找從指定起點(diǎn)到終點(diǎn)的一條具有最小權(quán)值總和的路徑問題,即尋找一條路徑使得TW(Pst)最小。

在交通路網(wǎng)最優(yōu)路徑選擇中進(jìn)行路徑選擇并不完全同于在賦權(quán)有向圖中求最短路徑問題的方法。在實(shí)際的交通中,路段的流量實(shí)時(shí)變化,單向行駛、交叉口轉(zhuǎn)向限制等也越來越復(fù)雜。伴隨著不同的實(shí)際應(yīng)用目的,最優(yōu)路徑規(guī)劃中也有很多優(yōu)化標(biāo)準(zhǔn),如最短行車距離、最少行車時(shí)間、最低費(fèi)用等。同時(shí)還要求有較快的速度和較高的效率。這就對(duì)最優(yōu)路徑選擇算法本身提出了一定的要求。只有選擇合適的算法才能找到滿足條件的最優(yōu)路徑。

2 蟻群算法原理與模型

2.1 基本原理

蟻群優(yōu)化算法(簡(jiǎn)稱蟻群算法),1991 年由Marco Dorigo 和他的同事1991 年首先提出[10-11]。作為一種多agent 的方法,較好地解決了一些復(fù)雜的組合優(yōu)化問題,如 TSP(Traveling salesman problem)問題以及指派問題。蟻群算法主要模擬螞蟻的食物搜索行為,當(dāng)螞蟻在食物源和巢穴之間行走時(shí),會(huì)在路上存儲(chǔ)信息素。螞蟻可以感知到環(huán)境中該物質(zhì)的存在及其強(qiáng)度,并在選擇移動(dòng)時(shí),傾向于選擇信息素濃度高的方向。當(dāng)某條路徑較短時(shí),會(huì)有較多的螞蟻使用這條路徑,使得該路徑上被存放較多的信息素,從而吸引更多的螞蟻使用這一路徑。最終,信息素濃度最高的路徑標(biāo)志出食物源和巢穴之間的最短路徑。

2.2 基本模型

以求解平面n 個(gè)城市的問題(用(0,1,…,n-1)表示城市序號(hào))來說明基本蟻群算法。引入如下記號(hào):m 為蟻群中的螞蟻數(shù);dij為城市和城市之間的距離;τij(t)為t 時(shí)刻路徑(i,j)上的信息量,n為城市的數(shù)量。

初始時(shí)刻,各條路徑上的信息素相等,設(shè)τij(0)=C,(C 為常數(shù)),螞蟻 k(k=1,2,…,m)在運(yùn)動(dòng)過程中根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向?;鞠伻核惴ㄋ褂玫臓顟B(tài)轉(zhuǎn)移規(guī)則被稱為隨機(jī)比例規(guī)則,它給出了位于城市i 的螞蟻轉(zhuǎn)移到城市j 的概率。為在t 時(shí)刻螞蟻k 由城市i 轉(zhuǎn)移到城市j 的狀態(tài)轉(zhuǎn)移概率:

式中:

α——螞蟻在行進(jìn)過程中所積累的信息素濃度對(duì)它已選擇路徑所起的作用大小,當(dāng)α=0 時(shí),算法就是傳統(tǒng)的貪心算法;

β——ηij的重要程度,當(dāng)β=0 時(shí),算法就成了純粹的正反饋的啟發(fā)式算法,可通過試驗(yàn)來確定參數(shù)α,β 的最優(yōu)組合;

ηij——由城市i 轉(zhuǎn)移到城市j 的期望程度,可根據(jù)某種啟發(fā)式算法而定,例如,可以取

Ak——螞蟻k 下一步允許走過的城市的集合,它隨螞蟻k 的行進(jìn)過程而動(dòng)態(tài)改變。

蟻群在覓食過程中,一方面通過螞蟻的行走會(huì)在路徑上留下新的信息素,另一方面隨著時(shí)間的推移已有的信息素會(huì)逐漸揮發(fā),所以,各條路徑上的信息素會(huì)根據(jù)蟻群的行動(dòng)和時(shí)間變化不斷更新。經(jīng)過n 個(gè)時(shí)刻,螞蟻k 可走完所有的城市,完成一次循環(huán)。此時(shí),要根據(jù)下式對(duì)各路徑上的信息素濃度作更新:

式中:

τij(t)——隨時(shí)間的推移會(huì)逐步衰減;

ρ——信息素?fù)]發(fā)參數(shù),其作用是使個(gè)體螞蟻忘掉過去從蟻群搜索過程中獲得的一部分經(jīng)驗(yàn),避免過早收斂于一個(gè)局部最優(yōu)解[12],用1-ρ 表示它的衰減程度;

Δτij——路徑上信息素濃度的變化量,

式中,Δτijk表示螞蟻k 在本次循環(huán)中在城市i 和城市j 之間留下的信息素濃度,其計(jì)算方法根據(jù)計(jì)算模型而定。

Dorigo Macro 曾給出了不同的蟻群算法模型,分別稱為 ant-cycle 模型(亦稱蟻周系統(tǒng)模型)、ant-quantity 模型(亦稱蟻量系統(tǒng)模型)和ant-density模型(亦稱蟻密系統(tǒng)模型),它們的差別在于Δτijk(t)的求法不同[13-14]。蟻密系統(tǒng)模型信息素增量為固定值 Q;而在蟻量系統(tǒng)模型中,信息素增量的值為,與路徑(i,j)的長(zhǎng)度有關(guān);在蟻周系統(tǒng)模型中,信息素增量為,它與具體的 dij無關(guān),只與 Q和搜索路線有關(guān)。這3 種模型中,ant-cycle 模型最適用于最短路徑問題[8]。在ant-cycle 模型中:

式中:Q 是信息素強(qiáng)度,它影響算法的收斂速度;Lk是第k 只螞蟻在本次循環(huán)中所走路徑的長(zhǎng)度。

2.3 采用蟻群算法求解最優(yōu)路徑的可行性

蟻群算法本質(zhì)是一種并行的算法。螞蟻搜索的過程彼此獨(dú)立,只通過信息素進(jìn)行間接的通訊。由于大規(guī)模的并行計(jì)算,可以顯著減少計(jì)算時(shí)間。它是一種正反饋算法。正反饋的存在,使得搜索收斂速度加快。它很容易與多種啟發(fā)式算法結(jié)合,以改善算法的性能。它具有較強(qiáng)的魯棒性。對(duì)算法模型稍加修改,便可以應(yīng)用于其他問題。

蟻群算法已被成功地應(yīng)用于許多可表達(dá)在圖表上尋找最佳路徑的問題。交通系統(tǒng)的最優(yōu)路徑選擇與螞蟻覓食行為類似。將車輛的起始點(diǎn)看作蟻巢,目的地看作是螞蟻所要尋找的食物源,車輛在從起始點(diǎn)開始經(jīng)過一些路段、節(jié)點(diǎn),最終到達(dá)目的地在路徑選擇的過程中,個(gè)體車輛根據(jù)本身的判斷選擇所需要的路徑行駛。在這里整個(gè)路網(wǎng)就是一個(gè)有向圖,車輛就是具有智能行為的人工螞蟻,并且該人工螞蟻只是找到從起始點(diǎn)到終止點(diǎn)的路徑,并不返回到原來的起始點(diǎn)[15]。通過對(duì)交通過程的抽象,將交通中實(shí)際的耗費(fèi)作為啟發(fā)信息,這樣可以建立起一個(gè)進(jìn)行最優(yōu)路徑選擇的人工蟻群系統(tǒng)。

3 基于信息素更新方式改進(jìn)的蟻群算法

為了克服基本蟻群算法的缺陷,通過自適應(yīng)地改變算法的信息素更新方式,可以在保證收斂速度的前提下提高解的全局性;通過改進(jìn)路徑選擇策略和模型,可以使該算法更符合交通網(wǎng)絡(luò)的運(yùn)行規(guī)律,提高算法的自適應(yīng)能力。

3.1 信息素限定原則

引入信息素限定規(guī)則,將每條邊上的信息量限定在[τmin,τmax]之間,即為Max-Min Ant System 的主要思路。設(shè)置了信息素強(qiáng)度的下限 τmin,所以選擇某些邊弧的概率雖然可能性非常小,但永遠(yuǎn)不會(huì)為零,這樣就減少了停滯行為出現(xiàn)的機(jī)會(huì),從而使螞蟻能進(jìn)行更高程度的搜索;因?yàn)榛鞠伻核惴ㄔ趯ふ易顑?yōu)路徑時(shí),并不像交通規(guī)劃一樣要考慮路網(wǎng)的承受能力,因此,改進(jìn)的蟻群算法中也設(shè)置了信息素強(qiáng)度的上限 τmax,使得這兩者信息素的差別不會(huì)趨向于無窮大。

3.2 信息素局部更新算法的改進(jìn)

道路網(wǎng)絡(luò)中還存在這樣的特性:某條路徑的出行時(shí)間會(huì)隨著交通流量的增加而增加。因此,將螞蟻行走過程中的信息素更新方式設(shè)置為局部更新原則。局部信息素更新的作用是使已選的邊對(duì)后來的螞蟻具有較小的吸引力,從而使螞蟻對(duì)沒有被選中的邊有更強(qiáng)的探索能力。實(shí)驗(yàn)表明,局部更新規(guī)則可以有效避免螞蟻收斂到同一路徑[16]。MMAS為TSP 問題的解決提出了信息素軌跡平滑機(jī)制,讓軌跡濃度的增加與最大濃度 τmax和當(dāng)前濃度 τij之間的差值成正比。信息素軌跡平滑機(jī)制較好地考慮了交通網(wǎng)絡(luò)中路徑的不同狀態(tài)特性,但是,計(jì)算較為復(fù)雜。本文采用了平滑機(jī)制的思路,根據(jù)不同狀態(tài)設(shè)置不同的模型形式,簡(jiǎn)化為用分段函數(shù)表示。當(dāng)螞蟻從城市i 轉(zhuǎn)移到城市j 后,路徑(i,j)上的信息素量按下式進(jìn)行更新:

式中:ξ∈[0,1]的一個(gè)參數(shù);τ0為一個(gè)很小的數(shù),經(jīng)驗(yàn)觀測(cè)值為;n 為城市數(shù)目;Lbest為該次循環(huán)中最短路徑長(zhǎng)度;τm為臨界值,反映系統(tǒng)的狀態(tài),根據(jù)具體的實(shí)驗(yàn)情況而定。

3.3 信息素全局更新模型的改進(jìn)

螞蟻根據(jù)信息素留下的多少選擇路段,而當(dāng)所有螞蟻都選擇某路段時(shí),可能造成某路段的負(fù)荷過大,形成所謂的交通擁堵現(xiàn)象。雖然,在前述的局部信息修改的過程中考慮了路網(wǎng)容量的特性,但當(dāng)交通擁堵越嚴(yán)重,根據(jù)ant-cycle 模型公式(5)可得螞蟻在路網(wǎng)上留下的信息量仍然是最大的,即其它的螞蟻根據(jù)公式(2)繼續(xù)選擇該路段,最終造成該路段崩潰[17]?,F(xiàn)有研究較多的是對(duì)公式(4)做必要的調(diào)整,引進(jìn)路段上的阻抗函數(shù)。由于本文討論的是動(dòng)態(tài)最優(yōu)路徑搜索問題,所以要引進(jìn)能反映實(shí)時(shí)路況的廣義路阻來計(jì)算[18]。廣義路阻是在各種因素(如路段平均行駛速度、車輛行駛的通暢性、路段擁擠度、路口排隊(duì)長(zhǎng)度和平均延誤等)影響下,路段行駛時(shí)間和路口延誤的綜合表征量。路段(i,j)上的廣義路阻 T(i,j)計(jì)算式為:

式(7)中,t(i,j)為路段(i,j)的行駛時(shí)間;r(i,j)為在路段(i,j)上的車輛平均延誤。式(8)中,t0(i,j)表示交通流為零時(shí)路段(i,j)的行駛時(shí)間;V 為路段交通量當(dāng)量值;C 為路段實(shí)用通行能力;k1、k2分別為回歸參數(shù),根據(jù)道路交通量、車速調(diào)查數(shù)據(jù)用最小二乘法確定。式(9)中,r1為均勻延誤,r2為過飽和延誤,即隨機(jī)到達(dá)的增量延誤所引起的附加延誤:其中,k3、k4為常數(shù);T 為周期長(zhǎng)度;λ 為進(jìn)口道綠信比;X 為交叉口飽和度;C 為進(jìn)口道實(shí)用飽和通行能力;S 為路口影響修正系數(shù)。

所以,在全局信息素更新規(guī)則中公式(5)改進(jìn)為:

式中,T(i,j)是路段(i,j)上的廣義路阻。

式(10)作為信息素更新規(guī)則可以使廣義路阻較大的路段獲得的信息素更新量較小。

在廣義路阻的基礎(chǔ)上,運(yùn)用該算法可以完成最優(yōu)路徑規(guī)劃的多種優(yōu)化標(biāo)準(zhǔn)要求,如最短行車距離、最少行車時(shí)間、平均車速、最低費(fèi)用等。

4 計(jì)算機(jī)仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)算法

根據(jù)蟻群優(yōu)化算法的思想,本文的最優(yōu)路徑搜索過程分幾步進(jìn)行:首先,初始化起始節(jié)點(diǎn)、終止節(jié)點(diǎn)和交通量,確定循環(huán)次數(shù),讓一定數(shù)量的人工螞蟻的每個(gè)螞蟻代表一定的交通量并分批置于交通出行始點(diǎn)上進(jìn)行循環(huán),初始循環(huán)可以隨機(jī)地讓人工螞蟻進(jìn)行路徑的選擇。每循環(huán)一次人工螞蟻根據(jù)上一次循環(huán)信息素軌跡分布概率進(jìn)行路徑的選擇,逐個(gè)在路網(wǎng)上移動(dòng),從起點(diǎn)到達(dá)終點(diǎn)的螞蟻成功完成一次循環(huán),并在相應(yīng)路徑上留下成功的信息素軌跡,局部更新軌跡強(qiáng)度,并檢查信息素?cái)?shù)量是否處于規(guī)定的范圍之內(nèi)。然后,當(dāng)一批螞蟻完成循環(huán)后,尋找最優(yōu)路徑,再對(duì)軌跡強(qiáng)度全局更新。至此,完成了一次最優(yōu)路徑搜索。最后尋找全局最優(yōu)解,即到當(dāng)前迭代次數(shù)為止。在所建立的所有局部最優(yōu)解中,值最小的解作為當(dāng)前迭代次數(shù)的全局最優(yōu)解。當(dāng)有足夠的螞蟻數(shù)量和循環(huán)次數(shù),交通系統(tǒng)將向平衡分配方向發(fā)展,結(jié)果亦更加趨近于最優(yōu)解。

針對(duì)本文將要解決的實(shí)際的動(dòng)態(tài)交通路徑問題,給出蟻群算法進(jìn)行路徑選擇的算法步驟如下:

Step 1 信息初始化 初始化將螞蟻逐個(gè)放置于起點(diǎn);初始化α,β,k,tmax,τij(0),m,Q等系數(shù)。其中 tmax為最大迭代次數(shù)。

蟻群算法中的參數(shù)設(shè)定目前尚無理論上的依據(jù),參數(shù)Q,C,α,β,ρ 可以用實(shí)驗(yàn)確定其最優(yōu)組合。經(jīng)驗(yàn)結(jié)果為:1≤α≤5;1≤β≤5;0.5≤ρ≤0.99,ρ 取0.7 左右為佳;1≤Q≤10000[19]。

Step 2 選擇原則 對(duì)每只螞蟻用轉(zhuǎn)移概率在禁忌表中沒有的匯點(diǎn)中選擇要移動(dòng)的下一個(gè)匯點(diǎn),位于第i 個(gè)節(jié)點(diǎn)的螞蟻k,按(3)式選擇策略選擇邊(i,j)。將所選匯點(diǎn)放入禁忌表每只螞蟻環(huán)游一圈后,計(jì)算這只螞蟻在此環(huán)游路徑的綜合系數(shù)值。

Step 3 局部更新原則 當(dāng)螞蟻選中邊(i,j)后,就更新邊(i,j)上的信息量,即每當(dāng)螞蟻選中一條邊后,就按(7)式更新減少邊上的信息量,從而增加螞蟻選擇其它邊的概率。

Step 4 局部搜索 當(dāng)m 只螞蟻從起點(diǎn)到終點(diǎn)搜索完后,則求得m 個(gè)解。為了盡可能遍歷所有解,分別在這些解的鄰域中,采用局部搜索算法,求出局部最優(yōu)解。

Step 5 全局更新原則 當(dāng)所有的m 只螞蟻都得到局部最優(yōu)解后(否則跳入Step2),按照(4)、(5)、(11)式全局更新信息量,即全局更新路段流量,更新路段阻抗。比較所有環(huán)游得出的系數(shù)值,找出最好的環(huán)游路徑。

Step 6 求全局最優(yōu)解 到當(dāng)前迭代次數(shù)為止,在所建立的所有局部最優(yōu)解中,值最小的解作為當(dāng)前迭代次數(shù)的全局最優(yōu)解。

Step 7 不斷迭代直到滿足停止的條件。

4.2 算例仿真

給定一個(gè)如圖2 所示的路網(wǎng),為簡(jiǎn)化計(jì)算,路網(wǎng)直接標(biāo)定了實(shí)時(shí)的廣義路阻值(邊上的數(shù)字),求該時(shí)刻從起點(diǎn)①到終點(diǎn)?在該時(shí)刻的最優(yōu)路徑。

圖2 示例的路網(wǎng)Fig.2 Example network

按照4.1 中的算法步驟進(jìn)行計(jì)算,參數(shù)取值見表1。在軟件Matlab 7.0 環(huán)境下實(shí)現(xiàn),迭代5 次即搜索到了最優(yōu)路徑:①→②→⑦→?→?→?。說明本文改進(jìn)的螞蟻算法因其本質(zhì)并行特性用于路徑尋優(yōu)中具有較高搜索效率和一定準(zhǔn)確性,能夠?qū)崿F(xiàn)快速的全面尋優(yōu)。

表1 參數(shù)值Tab.1 Parameter values

與基本蟻群算法相比,改進(jìn)后的算法的探索新路徑點(diǎn)則是在局部更新規(guī)則的作用下出現(xiàn)的,算法經(jīng)過一定的循環(huán)次數(shù)后收斂于一個(gè)最優(yōu)解,為避免此最優(yōu)解為局部最優(yōu)解,在局部更新規(guī)則的作用下,不斷地減少此最優(yōu)路徑上的信息素,從而促使螞蟻跳出局部最優(yōu)解,尋找一條新的路徑。在算法的準(zhǔn)確度和效率方面,本文的算法也有優(yōu)勢(shì)。

另外,文中給出的示例網(wǎng)絡(luò)不算復(fù)雜,很快就能搜索到正確的最短路徑。當(dāng)交通網(wǎng)絡(luò)相對(duì)比較復(fù)雜時(shí)或者是動(dòng)態(tài)變化時(shí),雖然可能在規(guī)定的較短時(shí)間內(nèi)搜索不到最短路徑,但可通過迭代的方式,在較少迭代次數(shù)下搜索到的“次優(yōu)”路徑將也能夠避開交通稠密地區(qū),滿足路徑誘導(dǎo)要求。而且對(duì)于動(dòng)態(tài)路徑誘導(dǎo)。該算法對(duì)目標(biāo)函數(shù)、初始數(shù)據(jù)和模型復(fù)雜程度均無特殊要求,特別是當(dāng)目標(biāo)函數(shù)為非線性時(shí),其優(yōu)勢(shì)更為明顯,因此更適用于動(dòng)態(tài)最優(yōu)路徑的搜索。

5 結(jié)束語

本文嘗試用蟻群算法來求解最優(yōu)路徑選擇問題,并根據(jù)交通網(wǎng)絡(luò)的要求對(duì)基本模型進(jìn)行了改進(jìn),且通過實(shí)驗(yàn)仿真取得了較為滿意的效果。同時(shí)也證明了該方法具有一定的理論參考價(jià)值和實(shí)際意義。將蟻群算法應(yīng)用于交通網(wǎng)絡(luò)最優(yōu)路徑的選擇過程中,能充分發(fā)揮算法的協(xié)作性、正反饋和分布式并行計(jì)算的特點(diǎn)。但由于蟻群算法的發(fā)展還在起步和探索階段,目前仍存在一些待研究的問題,如算法的收斂性、參數(shù)的合理設(shè)置及如何降低時(shí)間復(fù)雜度等。而且,對(duì)于動(dòng)態(tài)交通網(wǎng)絡(luò)中如何應(yīng)用蟻群算法,如何通過迭代的方法求出最短路徑,也是值得進(jìn)一步深入研究的問題。但是,可以肯定的是,隨著蟻群算法的深入開展,它必將成為交通規(guī)劃和交通組織網(wǎng)絡(luò)化的優(yōu)化算法,從而促進(jìn)整個(gè)交通網(wǎng)絡(luò)優(yōu)化的發(fā)展。

[1]殷 超.基于改進(jìn)Dijkstra 算法的最短路徑搜索仿真[J].山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,24(6):33-36.

[2]黃貴玲,高西全,靳松杰,談飛洋.基于蟻群算法的最短路徑問題的研究和應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(13):233-235.

[3]高 尚.解旅行商問題的混沌蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2005,(9):100-104.

[4]吳霜華,付 洋,葛 亮,基于混沌蟻群算法的最短路徑選擇研究[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,26:126-128.

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

[6]Fuellerera Guenther,Doernera Karl F.,Hartla Richard F.,Iorib Manuel.Ant colony optimization for the two-dimensional loading vehicle routing problem[J].Computers &Operations Research,2009,36(3):655-673.

[7]Yuvraj Gajpal,PrakashAbad.An ant colony system(ACS)for vehicle routing problem with simultaneous delivery and pickup[J].Computers &Operations Research,2009,36(2):3215-3223.

[8]Donati Alberto V.,Montemanni Roberto,Casagrande Norman et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185(3):1174-1191.

[9]Sheffi Yosef.Urban transportation networks:equilibrium analysis with mathematical programming methods[M].New Jersey,USA:PRENTICEHALL,INC.,1985.

[10]Dorigo M.Optimization,learning and natural algorithms[D].Milano,Italy:Dipartimento di Elettronica,Politecnico di Milano,1992.

[11]Dorigo M.,Gambardella L.M.Ant colony system:a cooperative learningapproach to the traveling salesman problem[J].IEEE Transactionson Evolutionary Computation,1997,1(1):53-66.

[12]陳小強(qiáng),杜呈欣,熊偉清.蟻群算法求解函數(shù)優(yōu)化中的參數(shù)設(shè)置[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(17):53-55.

[13]Bonabeau E.,Dorigo M.,Theraulaz G.Inspiration for optimization from social insect behavior[J].Nature,2000,406(6):39-42.

[14]靳凱文,李春葆,秦前清.基于蟻群算法的最短路徑搜索方法研究[J].公路交通科技,2006,3(23):128-134.

[15]夏立民.交通系統(tǒng)中最優(yōu)路徑選擇算法的研究[D].北京:首都師范大學(xué),2007.

[16]方麗君.基于蟻群算法的交通分配模型研究[D].南京:河海大學(xué)土木與交通學(xué)院,2006.

[17]王 勇,雷 黎,紀(jì)壽文,趙 琳等.基于改進(jìn)蟻群算法的交通分配研究[J].公路交通技術(shù),2007,6(3):159-161.

[18]陸 駿,王小平,曹立明.一種基于蟻群算法的車輛導(dǎo)航系統(tǒng)模擬模型[J].計(jì)算機(jī)應(yīng)用與軟件,2005,22(4):17-19.

[19]馬 良.全局優(yōu)化的一種新方法[J].系統(tǒng)工程與電子技術(shù),2000,22(9):62-64.

猜你喜歡
路段螞蟻局部
冬奧車道都有哪些相關(guān)路段如何正確通行
局部分解 巧妙求值
部、省、路段監(jiān)測(cè)運(yùn)維聯(lián)動(dòng)協(xié)同探討
非局部AB-NLS方程的雙線性B?cklund和Darboux變換與非線性波
A Survey of Evolutionary Algorithms for Multi-Objective Optimization Problems With Irregular Pareto Fronts
基于XGBOOST算法的擁堵路段短時(shí)交通流量預(yù)測(cè)
我們會(huì)“隱身”讓螞蟻來保護(hù)自己
螞蟻
局部遮光器
吳觀真漆畫作品選
桂平市| 巴南区| 常熟市| 大田县| 河间市| 雅安市| 淮安市| 科尔| 连云港市| 琼结县| 河间市| 正阳县| 江安县| 阿克苏市| 合山市| 酒泉市| 印江| 西和县| 昆明市| 惠水县| 和田市| 绥德县| 洪雅县| 扶沟县| 安新县| 南漳县| 星座| 饶平县| 灵石县| 工布江达县| 旺苍县| 红桥区| 砀山县| 临沧市| 阜康市| 新乐市| 锡林浩特市| 云阳县| 云南省| 叙永县| 天等县|