蜂群算法在智能交通中的應用研究

摘 要:為了使路網狀態趨于通暢的最佳狀態，給出了一種基于蜂群算法的自適應路徑誘導方法，通過智能蜂群在路徑選擇時的交互作用實現車輛路徑動態誘導，從而使交通需求合理分配在路網中，為每個車輛提供最佳行駛路徑環境。模擬實驗的結果表明，本方法能夠根據交通路網的實際情況選擇出最優的實時路徑，實現了系統動態誘導的目的。

關鍵詞:Agent; 蜂群; 路徑導航; ITS

中圖分類號:TP911.6; TP301.6 文獻標識碼:A

文章編號: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)的各種方式提高現有交通資源的利用率，使交通流的分布更加合理，動態路徑誘導就是一個重要手段[2]。隨著車輛數和城市路網規模的增大以及交通流在信息、控制方面固有的分布性，采用多Agent系統進行構建城市交通控制系統的計算環境已成為發展趨勢[3]。在這樣一個動態計算環境中，利用智能方法來實現ITS也是一個必然的趨勢。國內學者已有相關研究，如朱志勇利用蟻群算法來進行車輛動態路徑導航[4]，楊兆升利用遺傳算法來進行交通控制[5]等。本文在一種基于Agent路徑誘導系統的基礎上，利用基于蜂群算法的自適應路徑選擇方法實現路徑誘導功能。

1 蜜蜂群算法

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

2 基于蜂群算法的車輛動態路徑導航方法

本文中的路段對應的是每個路段Agent。蜂群由每個路段Agent生成，并向其他路段移動。路段Agent維護和更新本地交通路網的路徑表，基于路徑表來完成全局路徑選擇信息的刷新計算。交通路網的拓撲結構為路段Agent發出的蜂群感知，由這種方法得出的交通路網拓撲圖能反應出最新的交通路網的拓撲結構，由此選擇的路徑是符合實時交通狀況的。基于蜂群算法的車輛動態路徑導航方法的基本思想就是在源路段和目的路段之間利用蜂群，通過周期性地計算包含的全局信息，以分布的形式做少量的計算來刷新全局路徑選擇信息，影響交通需求在路網中的分配，使路網狀態趨于通暢的最佳狀態。

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

表1 人工蜜蜂的堆棧結構

標識角色 路段1飽和度1行程時間1…路段n飽和度n行程時間n目的路段

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

表2 路徑表

覓食蜂序號11覓食蜂序號12…覓食蜂序號1n

覓食蜂序號21覓食蜂序號22…覓食蜂序號2n



覓食蜂序號m1覓食蜂序號m2…覓食蜂序號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為下一路段的控制信息，與蜜蜂所跟隨的覓食蜂是否經過此路段有關;α，β為權重參數;l(u)為與路段u直接相連的所有相鄰路段的集合;quv為蜜蜂選擇路段v為下一路段的啟發信息，與路段v的當前行程時間和飽和度有關;xv與u相鄰的路段v的飽和度;f(t)是關于到達路段v的行程時間的函數，距離路段v越遠的路段，路段v的飽和度對它的影響越小，因此，在式(2)中設置參數f(t)來反映交通流動態變化的特性。

當蜜蜂的角色為探測蜂時其wuv根據式(3)計算，其中l為與路段u直接相連的所有相鄰路段的個數。

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

當蜜蜂的角色為觀察蜂時，如果它的標示位恰好與路徑表中覓食蜂的一個序號相等，且觀察蜂選擇覓食蜂的路徑，則其wuv取值為γ(γ為覓食蜂對觀察蜂的引領性強弱參數);如果觀察蜂不選擇覓食蜂的路徑，根據式(4)計算;如果可選路徑不包含覓食蜂走過的路徑，則根據式(1)計算[10]。

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

3 路徑導航方法的詳細描述及實驗

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

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

(3) 之后路段Agent只發出觀察蜂和偵查蜂，考查路網的交通運行狀態，搜尋最佳路徑。

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

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

(6) 當某路段發生路障或進入不甚暢通狀態時，經過此路段的蜜蜂會發現行程時間和路段飽和度的增加，相應的Pij將變小，通過Pij在不同路徑上的變化，經過一段時間的正反饋后，蜜蜂會重新選擇出新的最優路徑。

(7) 車輛在行駛過程中選擇最優路徑上的路段前進。

根據上述步驟，在一個簡單的仿真實驗環境中對它進行的驗證，實驗系統如圖1所示。

圖1 實驗系統

仿真實驗主要考察節點1~節點2的路徑選擇。實驗環境由5臺計算機構成。以1-3這種形式表示路段。在運行過程中，不斷改變各個路段飽和度，系統根據蜂群算法能自適應地選擇出最佳行駛路徑。

4 結 語

本文提出的基于蜂群算法的車輛動態路徑導航方法能夠根據實際情況選擇出合適的路徑。該算法無論在計算復雜度還是在收斂性能上，都具備一定的優勢。它利用智能蜂群技術實現動態路徑選擇，在各個中間路段，智能蜂群依據路段中路徑表自主的選擇下一個路段。它使交通路網達到交通平衡狀態，使各路段達到通暢，實現了誘導系統的目的。

參考文獻

[1]黃衛，陳里德. 智能運輸系統(ITS)概論[M].北京:人民交通出版社，2006.

[2]國家智能交通系統工程技術研究中心.中國智能交通系統文集[C].北京:中國鐵道出版社，2006.

[3]郭建鋼.多智能體技術在交通系統協調控制中的應用[J].華東交通大學學報，2005，12(6):38-41.

[4]朱志勇.車輛動態路徑導航系統框架及自適應路徑選擇方法的研究[D].武漢:武漢大學，2005.

[5]樣兆升.基于混合遺傳算法的多Agent 交通控制系統[J].交通運輸系統工程與信息，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]袁振洲.確定動態交通分配中路段行駛時間方法的研究[J].交通運輸系統工程與信息，2002，2(2):54-56.

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

[10]李峰磊.蜂群算法的研究與應用[D].南京:河海大學，2008.