摘 要:為了使路網(wǎng)狀態(tài)趨于通暢的最佳狀態(tài)，給出了一種基于蜂群算法的自適應(yīng)路徑誘導(dǎo)方法，通過(guò)智能蜂群在路徑選擇時(shí)的交互作用實(shí)現(xiàn)車輛路徑動(dòng)態(tài)誘導(dǎo)，從而使交通需求合理分配在路網(wǎng)中，為每個(gè)車輛提供最佳行駛路徑環(huán)境。模擬實(shí)驗(yàn)的結(jié)果表明，本方法能夠根據(jù)交通路網(wǎng)的實(shí)際情況選擇出最優(yōu)的實(shí)時(shí)路徑，實(shí)現(xiàn)了系統(tǒng)動(dòng)態(tài)誘導(dǎo)的目的。

關(guān)鍵詞:Agent; 蜂群; 路徑導(dǎo)航; ITS

中圖分類號(hào):TP911.6; TP301.6 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)14-0134-02

Application Research of Bee Colony Algorithm in ITS

HUANG Xiao-lun

(Chongqing Information Technology College，Chongqing 404001，China)

Abstract: A kind of bee colony -based adaptive path selection methods is proposed for making the road network into the best situation. Dynamic route guidance is realized through the interaction role of path choice by the intelligent bee colony， and the best driving environment is provided. Simulation experiment results show that the method can choose the optimal path according to the corresponding situation and achieve the dynamic guidance system.

Keywords: Agent; bee colony; path guidance; ITS

0 引 言

利用ITS[1](intelligent transporttation system)的各種方式提高現(xiàn)有交通資源的利用率，使交通流的分布更加合理，動(dòng)態(tài)路徑誘導(dǎo)就是一個(gè)重要手段[2]。隨著車輛數(shù)和城市路網(wǎng)規(guī)模的增大以及交通流在信息、控制方面固有的分布性，采用多Agent系統(tǒng)進(jìn)行構(gòu)建城市交通控制系統(tǒng)的計(jì)算環(huán)境已成為發(fā)展趨勢(shì)[3]。在這樣一個(gè)?jiǎng)討B(tài)計(jì)算環(huán)境中，利用智能方法來(lái)實(shí)現(xiàn)ITS也是一個(gè)必然的趨勢(shì)。國(guó)內(nèi)學(xué)者已有相關(guān)研究，如朱志勇利用蟻群算法來(lái)進(jìn)行車輛動(dòng)態(tài)路徑導(dǎo)航[4]，楊兆升利用遺傳算法來(lái)進(jìn)行交通控制[5]等。本文在一種基于Agent路徑誘導(dǎo)系統(tǒng)的基礎(chǔ)上，利用基于蜂群算法的自適應(yīng)路徑選擇方法實(shí)現(xiàn)路徑誘導(dǎo)功能。

1 蜜蜂群算法

在蜂群中，蜜蜂個(gè)體分為3類角色:覓食蜂、觀察蜂和探測(cè)蜂。每個(gè)覓食蜂有一個(gè)確定的食物源(食物源代表各種可能的解)，并在迭代中對(duì)食物源的鄰域進(jìn)行搜索(搜索過(guò)程也就是搜尋最優(yōu)解的過(guò)程)，在每次返回之后，覓食蜂將食物源的信息反饋給觀察蜂，觀察蜂將在不同的覓食蜂中選擇一個(gè)作為目標(biāo)，并進(jìn)行搜索。觀察蜂選擇覓食蜂的依據(jù)是覓食蜂反饋的關(guān)于食物源的收益率(食物源的價(jià)值由收益率體現(xiàn))。若覓食蜂在設(shè)定的限定(limit)值內(nèi)沒(méi)有獲得更好的食物源，便成為探測(cè)蜂，并隨機(jī)搜索可行的新食物源[6-7]。

2 基于蜂群算法的車輛動(dòng)態(tài)路徑導(dǎo)航方法

本文中的路段對(duì)應(yīng)的是每個(gè)路段Agent。蜂群由每個(gè)路段Agent生成，并向其他路段移動(dòng)。路段Agent維護(hù)和更新本地交通路網(wǎng)的路徑表，基于路徑表來(lái)完成全局路徑選擇信息的刷新計(jì)算。交通路網(wǎng)的拓?fù)浣Y(jié)構(gòu)為路段Agent發(fā)出的蜂群感知，由這種方法得出的交通路網(wǎng)拓?fù)鋱D能反應(yīng)出最新的交通路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，由此選擇的路徑是符合實(shí)時(shí)交通狀況的。基于蜂群算法的車輛動(dòng)態(tài)路徑導(dǎo)航方法的基本思想就是在源路段和目的路段之間利用蜂群，通過(guò)周期性地計(jì)算包含的全局信息，以分布的形式做少量的計(jì)算來(lái)刷新全局路徑選擇信息，影響交通需求在路網(wǎng)中的分配，使路網(wǎng)狀態(tài)趨于通暢的最佳狀態(tài)。

在本環(huán)境中，人工蜜蜂是一個(gè)具有堆棧結(jié)構(gòu)與群體合作的個(gè)體，其結(jié)構(gòu)如表1所示。角色位用來(lái)表明蜜蜂是觀察蜂還是探測(cè)蜂，如果是觀察蜂，對(duì)應(yīng)的標(biāo)識(shí)位將記錄所跟隨的覓食蜂的序號(hào)。同時(shí)將蜜蜂所進(jìn)過(guò)的路段及相應(yīng)的行程時(shí)間和飽和度記錄下來(lái)。在交通狀況良好、交通需求不大時(shí)，各路徑的行程時(shí)間對(duì)出行者而言作為誘導(dǎo)信息是準(zhǔn)確的，但是當(dāng)路網(wǎng)的某些路段接近飽和時(shí)，僅以路徑的行程時(shí)間這個(gè)全局信息進(jìn)行誘導(dǎo)容易引起交通擁塞或擁塞轉(zhuǎn)移等現(xiàn)象。當(dāng)路段處于不甚暢通狀態(tài)時(shí)，如果經(jīng)過(guò)此路段的整個(gè)路徑的行程時(shí)間比其他路徑的行程時(shí)間短，那么此時(shí)此路段的吸引度較大，蜜蜂會(huì)優(yōu)先選擇這個(gè)路段，這樣就會(huì)引起車輛在此路段產(chǎn)生嚴(yán)重的阻塞。因此，必須把全局信息和局部信息結(jié)合起來(lái)，即把行程時(shí)間和飽和度結(jié)合起來(lái)[8-9]。

表1 人工蜜蜂的堆棧結(jié)構(gòu)

標(biāo)識(shí)角色 路段1飽和度1行程時(shí)間1…路段n飽和度n行程時(shí)間n目的路段

路徑表(表 2)中覓食蜂序號(hào)記錄當(dāng)前路段上所經(jīng)過(guò)的覓食蜂的序號(hào)，用于引導(dǎo)對(duì)應(yīng)的觀察蜂，如果沒(méi)有覓食蜂選擇此路段，則賦值-1。觀察蜂將根據(jù)車輛的不同目的路段，根據(jù)標(biāo)識(shí)位是否與其中的一個(gè)值相等，作為其選擇下一個(gè)行程路段的依據(jù)。這樣可以綜合考慮到流量平衡的原則，充分利用交通資源，使交通需求合理分配在路網(wǎng)中，使路網(wǎng)狀態(tài)趨于通暢的最佳狀態(tài)，同時(shí)，為每個(gè)車輛提供最佳行使路徑。

表2 路徑表

覓食蜂序號(hào)11覓食蜂序號(hào)12…覓食蜂序號(hào)1n

覓食蜂序號(hào)21覓食蜂序號(hào)22…覓食蜂序號(hào)2n



覓食蜂序號(hào)m1覓食蜂序號(hào)m2…覓食蜂序號(hào)mn

公式(1)給出了在路段u中選擇到目的路段d的相鄰路段v的概率公式。

puv=[wuv]α[quv]β∑d∈l(u)[wud]α[qud]β (1)

quv=f(t)(1-xv/∑d∈l(u)xd) (2)

式中:wuv為蜜蜂選擇路段v為下一路段的控制信息，與蜜蜂所跟隨的覓食蜂是否經(jīng)過(guò)此路段有關(guān);α，β為權(quán)重參數(shù);l(u)為與路段u直接相連的所有相鄰路段的集合;quv為蜜蜂選擇路段v為下一路段的啟發(fā)信息，與路段v的當(dāng)前行程時(shí)間和飽和度有關(guān);xv與u相鄰的路段v的飽和度;f(t)是關(guān)于到達(dá)路段v的行程時(shí)間的函數(shù)，距離路段v越遠(yuǎn)的路段，路段v的飽和度對(duì)它的影響越小，因此，在式(2)中設(shè)置參數(shù)f(t)來(lái)反映交通流動(dòng)態(tài)變化的特性。

當(dāng)蜜蜂的角色為探測(cè)蜂時(shí)其wuv根據(jù)式(3)計(jì)算，其中l(wèi)為與路段u直接相連的所有相鄰路段的個(gè)數(shù)。

wuv=1/l (3)

當(dāng)蜜蜂的角色為觀察蜂時(shí)，如果它的標(biāo)示位恰好與路徑表中覓食蜂的一個(gè)序號(hào)相等，且觀察蜂選擇覓食蜂的路徑，則其wuv取值為γ(γ為覓食蜂對(duì)觀察蜂的引領(lǐng)性強(qiáng)弱參數(shù));如果觀察蜂不選擇覓食蜂的路徑，根據(jù)式(4)計(jì)算;如果可選路徑不包含覓食蜂走過(guò)的路徑，則根據(jù)式(1)計(jì)算[10]。

wuv=(1-γ)/(l-1) (4)

3 路徑導(dǎo)航方法的詳細(xì)描述及實(shí)驗(yàn)

(1) 當(dāng)路段Agent接收到搜索路徑的指令時(shí)，進(jìn)行初始化，此時(shí)所有蜜蜂為偵查蜂，隨機(jī)選擇路段。

(2) 在蜜蜂向著目的路段移動(dòng)的過(guò)程中，它將保存所經(jīng)過(guò)的路段地址和此路段的行程時(shí)間及飽和度。當(dāng)蜜蜂到達(dá)目的地后，根據(jù)堆棧中的行程時(shí)間及飽和度，使用式(2)計(jì)算收益率，根據(jù)收益率和限定值確定蜜蜂的角色。然后根據(jù)堆棧中的路段信息，往回發(fā)送消息，根據(jù)當(dāng)前被確定為覓食蜂的序號(hào)來(lái)更新路徑表。

(3) 之后路段Agent只發(fā)出觀察蜂和偵查蜂，考查路網(wǎng)的交通運(yùn)行狀態(tài)，搜尋最佳路徑。

(4) 在蜜蜂移向一個(gè)路段時(shí)，根據(jù)公式(1)計(jì)算概率Pij選擇鄰接路段作為蜜蜂移向的下一個(gè)路段。

(5) 如果循環(huán)次數(shù)小于設(shè)定值并且非所有的蜜蜂選擇同一路徑，重復(fù)執(zhí)行步驟(2)~步驟(4)。

(6) 當(dāng)某路段發(fā)生路障或進(jìn)入不甚暢通狀態(tài)時(shí)，經(jīng)過(guò)此路段的蜜蜂會(huì)發(fā)現(xiàn)行程時(shí)間和路段飽和度的增加，相應(yīng)的Pij將變小，通過(guò)Pij在不同路徑上的變化，經(jīng)過(guò)一段時(shí)間的正反饋后，蜜蜂會(huì)重新選擇出新的最優(yōu)路徑。

(7) 車輛在行駛過(guò)程中選擇最優(yōu)路徑上的路段前進(jìn)。

根據(jù)上述步驟，在一個(gè)簡(jiǎn)單的仿真實(shí)驗(yàn)環(huán)境中對(duì)它進(jìn)行的驗(yàn)證，實(shí)驗(yàn)系統(tǒng)如圖1所示。

圖1 實(shí)驗(yàn)系統(tǒng)

仿真實(shí)驗(yàn)主要考察節(jié)點(diǎn)1~節(jié)點(diǎn)2的路徑選擇。實(shí)驗(yàn)環(huán)境由5臺(tái)計(jì)算機(jī)構(gòu)成。以1-3這種形式表示路段。在運(yùn)行過(guò)程中，不斷改變各個(gè)路段飽和度，系統(tǒng)根據(jù)蜂群算法能自適應(yīng)地選擇出最佳行駛路徑。

4 結(jié) 語(yǔ)

本文提出的基于蜂群算法的車輛動(dòng)態(tài)路徑導(dǎo)航方法能夠根據(jù)實(shí)際情況選擇出合適的路徑。該算法無(wú)論在計(jì)算復(fù)雜度還是在收斂性能上，都具備一定的優(yōu)勢(shì)。它利用智能蜂群技術(shù)實(shí)現(xiàn)動(dòng)態(tài)路徑選擇，在各個(gè)中間路段，智能蜂群依據(jù)路段中路徑表自主的選擇下一個(gè)路段。它使交通路網(wǎng)達(dá)到交通平衡狀態(tài)，使各路段達(dá)到通暢，實(shí)現(xiàn)了誘導(dǎo)系統(tǒng)的目的。

參考文獻(xiàn)

[1]黃衛(wèi)，陳里德. 智能運(yùn)輸系統(tǒng)(ITS)概論[M].北京:人民交通出版社，2006.

[2]國(guó)家智能交通系統(tǒng)工程技術(shù)研究中心.中國(guó)智能交通系統(tǒng)文集[C].北京:中國(guó)鐵道出版社，2006.

[3]郭建鋼.多智能體技術(shù)在交通系統(tǒng)協(xié)調(diào)控制中的應(yīng)用[J].華東交通大學(xué)學(xué)報(bào)，2005，12(6):38-41.

[4]朱志勇.車輛動(dòng)態(tài)路徑導(dǎo)航系統(tǒng)框架及自適應(yīng)路徑選擇方法的研究[D].武漢:武漢大學(xué)，2005.

[5]樣兆升.基于混合遺傳算法的多Agent 交通控制系統(tǒng)[J].交通運(yùn)輸系統(tǒng)工程與信息，2006，2(1):64-68.

[6]BONNIE R M，VICTORIA Y.Agent learning in the multi-agent contracting system[J].Decision Support Systems，2008，45(1):140-149.

[7]TERESHKO V， LOENGAROV A.Collective decision-making in honeybee foraging dynamics[J]. Comput. Inf.Syst.， 2005.

[8]袁振洲.確定動(dòng)態(tài)交通分配中路段行駛時(shí)間方法的研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2002，2(2):54-56.

[9]莊焰，曾文佳.信號(hào)交叉口延誤計(jì)算模型研究[J].深圳大學(xué)學(xué)報(bào):理工版，2006，10(4):309-312.

[10]李峰磊.蜂群算法的研究與應(yīng)用[D].南京:河海大學(xué)，2008.