蟻群算法在交通管理中的應(yīng)用研究

董新捷，韓偉娟

(1.中國電子科技集團公司信息科學(xué)研究院，信息系統(tǒng)研究所，北京 100086；2.中國科學(xué)院自動化研究所，北京 100190)

?

工程與應(yīng)用

蟻群算法在交通管理中的應(yīng)用研究

董新捷1，韓偉娟2

(1.中國電子科技集團公司信息科學(xué)研究院，信息系統(tǒng)研究所，北京 100086；2.中國科學(xué)院自動化研究所，北京 100190)

近些年來，隨著城市汽車數(shù)量的大幅增加，交通擁堵問題越來越嚴重，交通管理日益重要，但在交通擁擠問題、選擇最優(yōu)路徑等方面仍然面臨著很多亟待解決的問題。蟻群算法是一種解決最優(yōu)路徑的智能算法，基于蟻群算法提出了一種均衡路程長度和擁堵程度以解決交通問題的新方法，模擬實驗結(jié)果表明，該方法具有良好的性能，在一定目標函數(shù)下，通過小幅增加車程分散汽車流，大幅度降低了擁堵程度。該法具有一定的現(xiàn)實意義。

交通管理；蟻群算法；路程；標準差；信息素；擁堵系數(shù)

0 引 言

交通問題一直是困擾城市特別是大城市發(fā)展的一個重要問題，在現(xiàn)有交通基礎(chǔ)設(shè)施和機動車數(shù)量快速增長條件下,交通擁堵問題越來越嚴重。在錯綜復(fù)雜的城市路網(wǎng)中，如何使得行人車輛到達目的的路程距離和整體的交通擁堵程度之間取得一個最佳的平衡,是交通管理的一個重要研究方向，本文將這個問題進行探討。

從自然界的螞蟻在覓食時的行為中得到啟發(fā)，意大利科學(xué)家Dorigo等人于1991年提出了一種模擬螞蟻來尋找最優(yōu)路徑的算法即人工蟻群算法。蟻群算法不僅具有分布式計算的特征，而且能做到信息的正反饋和啟發(fā)式的搜索，不僅適用于離散系統(tǒng)的優(yōu)化，也適用連續(xù)問題的優(yōu)化。近些年來，蟻群算法被用于交通管理問題，進行路網(wǎng)的實時監(jiān)測處理。原有的以蟻群算法進行交通管理的論文大多集中于揮發(fā)系數(shù)和比例系數(shù)對結(jié)果的影響，本文將擁堵系數(shù)引入信息素更新參數(shù)因子，實現(xiàn)對路程長度和擁堵程度的平衡。

1 算法策略

1.1 目標函數(shù)

在交通問題中，一般有兩個重要指標，一個路程，一個是花費的時間，如公式(1)、(2)、(3)所示，P代表總體目標函數(shù)值，σ代表平均路程距離，φ代表交通擁堵程度標準差，α和β為兩者在整體目標中的調(diào)整系數(shù)，根據(jù)實際需要設(shè)置，代表兩者的重要程度。在實驗中隨機產(chǎn)生一批螞蟻，從某個節(jié)點出發(fā)，計算每個螞蟻到目的節(jié)點的平均路程，n為找到有效路徑的螞蟻數(shù)，Ai表示每一只螞蟻從起點到終點的路程長度，Lij為某一時刻一條路徑上的螞蟻數(shù)量，而L代表同一時刻所有路徑上的平均螞蟻數(shù)量，對于不連通的路徑，取Lij等于L，k代表連通的有效路徑數(shù)量。

P=α*σ+β*φ

(1)

(2)

(3)

實驗步驟如下：

Step1: 根據(jù)實際需要確定α和β；

Step2: 產(chǎn)生一批螞蟻，每只螞蟻根據(jù)信息素進行路徑選擇；

Step3: 進行一次迭代，計算螞蟻數(shù)標準差、平均路程長度以及目標函數(shù)值等，如果滿足一定終止條件，終止，否則進入Step4；

Step4: 根據(jù)一定策略更新信息素；

Step5: 轉(zhuǎn)到Step2。

終止條件包括找到目標的螞蟻數(shù)達到一定比例、搜素目標的時間耗盡、螞蟻總隨機次數(shù)達到一定數(shù)值仍未找到目標則丟棄等。蟻群算法流程圖如圖1所示，每次迭代后根據(jù)每只螞蟻的路徑長度重新計算信息素，然后進行下一次迭代。

圖1 蟻群算法流程圖

1.2 信息素更新策略

在一般的蟻群算法中，最優(yōu)路徑和非最優(yōu)路徑有著不同的信息素更新策略，在下一輪螞蟻的路徑選擇中發(fā)揮著選擇概率大小的不同作用，同時信息素以一定的系數(shù)揮發(fā)。在這里揮發(fā)系數(shù)以參數(shù)ρ表示，λ為最優(yōu)路徑信息素增加量，本實驗中采取某一定值，非最優(yōu)路徑乘以大小為μ的比例系數(shù)。Ιnfo-1表示迭代前某條路徑上信息素量,Ιnfoi表示迭代后更新的該路徑信息素量。最優(yōu)路徑信息素迭代如公式(4)所示，非最優(yōu)路徑信息素迭代公式(5)所示。

Infoi=Infoi-1*(1-ρ)+λ

(4)

Infoi=Infoi-1*(1-ρ)+λ*μ

(5)

本實驗將改進信息素更新策略，每一次迭代后，在根據(jù)路程長度更新信息素后引入擁堵系數(shù)，即實時計算此次迭代中每一條路徑上平均經(jīng)過的螞蟻數(shù)，對于大于平均數(shù)的路徑計算其差值，如果差值大于1，以信息素除以這個差值縮小信息素值，以減少其被后來的螞蟻選擇的概率，對于小于螞蟻平均數(shù)的路徑，得以相對增大信息素量從而增大其被選擇的概率。Lij為某一時刻一條路徑上的螞蟻數(shù)量，而L代表同一時刻所有路徑上的平均螞蟻數(shù)量，Infoij表示該路徑的信息素量，γ為調(diào)整系數(shù)，信息素更新在經(jīng)過公式(4)和公式(5)的處理后，對于大于螞蟻數(shù)平均值的路徑如公式(6)處理。

(6)

2 實驗設(shè)計

本實驗算例如圖2所示，起始節(jié)點0，目的節(jié)點20。進行兩組實驗，第一次實驗使用路程優(yōu)先的蟻群算法，每次螞蟻信息素根據(jù)路程長度進行更新，如公式(4)和公式(5)所示。第二次實驗在公式(4)和(5)的基礎(chǔ)上，引入擁堵系數(shù)更新信息素，如公式(6)所示。

圖2 本次實驗節(jié)點和距離示意圖

實驗平臺intel i7-4790處理器，主頻3.6 GHz，內(nèi)存16 GB，程序編譯工具VS2010，仿真工具Matlab R2012a。

3 實驗結(jié)果

第一次實驗采取路程長短為導(dǎo)向的蟻群算法，即每次迭代中信息素量以路程長短為標準更新，基于公式(4)和公式(5)。每次實驗采用100只螞蟻，僅將到達目的的螞蟻納入計算范圍，計算其平均路程長度和路程標準差，將標準差除以到達目的地的螞蟻數(shù)量，ρ取0.1，μ取0.01，α取1，β取150，進行100次迭代，最后10次獲取的結(jié)果如表1所示，保留兩位有效數(shù)字。從實驗結(jié)果可以看出，以路程為導(dǎo)向的蟻群算法能夠在平均路程上取得較好的結(jié)果，但是各個道路經(jīng)過的螞蟻數(shù)量和平均經(jīng)過的螞蟻數(shù)量的標準差較大。

第二次實驗在每次迭代后，計算每條路徑上的螞蟻數(shù)，引入擁堵系數(shù)。每條路徑上經(jīng)過的螞蟻數(shù)表明這條路徑較為擁擠，反之則較為順暢，那么在根據(jù)公式(4)、(5)計算信息素后，在根據(jù)公式(6)進一步更新信息素，將導(dǎo)致信息素在擁擠程度較大的路徑上減少，將縮小后來的螞蟻對這條道路的選擇概率，在順暢的道路上信息素相對增大，增加被后來的螞蟻選擇的概率。經(jīng)過調(diào)整進行實驗，同樣進行100次迭代后，最后10次的目標函數(shù)值如表2所示，保留兩位有效數(shù)字。從實驗結(jié)果可以看出，螞蟻到達目的地所經(jīng)過的平均路程明顯增加，但所有路徑上的螞蟻數(shù)的平均標準差顯著降低。ρ取0.1，μ取0.01，α取1，β取150，γ取1。

表2 第二次實驗函數(shù)值

兩次實驗的路程對比如圖3所示，藍色虛線表示第一次實驗螞蟻平均路程長度，每只螞蟻從起點到終點路程長度迅速收斂，穩(wěn)定在10以下。紅色實線表示第二次實驗路程長度，可以看出，引入擁堵系數(shù)后每只螞蟻所經(jīng)過的路程長度變化較大，收斂不明顯，且明顯大于第一次實驗中螞蟻的路程。

圖3 兩次實驗路程對比圖

兩次實驗的時間對比如圖4所示，藍色虛線表示第一次實驗每次迭代所花費的時間，每次迭代花費時間迅速下降，穩(wěn)定在50毫秒左右。紅色實線表示引入擁堵系數(shù)后每次迭代花費時間，大致在200毫秒到350毫秒之間浮動。

圖4 兩次實驗時間對比圖

在每次迭代后，首先計算每條路徑上經(jīng)過的平均螞蟻數(shù)，然后計算每條路徑的螞蟻數(shù)和平均數(shù)之間的標準差，第一次實驗如圖5的藍色虛線所示，第二次實驗如圖5的紅色實線所示?？梢悦黠@看出，前者的標準差明顯大于后者的標準差，表明沒有引入擁堵系數(shù)時每條路徑的螞蟻數(shù)更偏離平均數(shù)，每條路上螞蟻數(shù)分布更不均。而引入擁堵系數(shù)后，有效縮小了標準差，表明降低了擁堵程度，分散了螞蟻流量，達到路程和螞蟻數(shù)的均衡。

圖5 兩次實驗標準差對比圖

4 結(jié) 語

本文首先討論了交通管理系統(tǒng)中路程和擁堵目標函數(shù)方程，然后用路程優(yōu)先的蟻群算法和引入擁堵系數(shù)的蟻群算法進行兩次實驗。實驗表明，引入擁堵系數(shù)后，螞蟻的路程變長，而標準差變小，路程和標準差存在一定的替代關(guān)系，每個區(qū)域可根據(jù)實際情況設(shè)置路程和擁堵的權(quán)重系數(shù)，實現(xiàn)兩者之間的平衡。

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

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

[3] 程世娟,盧偉等.基于蟻群算法的最短路徑搜索方法研究[J].科學(xué)技術(shù)與工程,2007,7(21):1671-1819.

[4] 李士勇等著.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社,2004:53-77.

[5] 鄭宇軍,石海鶴,陳勝勇著.算法設(shè)計[M].北京：人民郵電出版社,2012:70-150.

[6] 段海濱著,蟻群算法原理及其應(yīng)用[M],北京：科學(xué)出版社,2005:46-222.

[7] 劉經(jīng)宇,方彥軍.蟻群算法在城市交通路徑選擇中的應(yīng)用[J].西南交通大學(xué)學(xué)報,2009,44(6):912-917.

[8] 聞育,吳鐵軍.基于蟻群算法的城域交通控制實時滾動優(yōu)化[J].控制與決策,2004,19(9):1057-1063.

[9] 楊士勇,揚丹.基于改進蟻群算法的巡航導(dǎo)彈航跡規(guī)劃[J],宇航學(xué)報,2007,28(4):903-907.

[10]稅薇,葛艷,韓玉等.基于混合蟻群算法的無人機航路規(guī)劃[J].系統(tǒng)仿真學(xué)報,2011,23(3):574-577.

[11]胡中華,趙敏,姚敏.引入導(dǎo)引因子蟻群算法的無人機二維航跡規(guī)劃[J].中國機械工程,2011,22(3):322-325.

[12]王緒芝,姚敏,趙敏等.基于蚊群算法的無人機航跡規(guī)劃及其動態(tài)仿真[J].指揮控制與仿真,2012,34(1):29-32.

[13]羅雪暉,楊燁,李霞.改進混合蛙跳算法求解旅行商問題[J].通信學(xué)報,2009,30(7):130-134.

[14]余劍峰,李原,于海山.基于自適應(yīng)蟻群算法的協(xié)同制造項目資源優(yōu)化配[J].計算機集成制造系統(tǒng),2008,14(3):576-580.

[15]劉森琪,段海濱,余亞翔.基于Voronoi圖和蟻群優(yōu)化算法的無人作戰(zhàn)飛機航路規(guī)劃[J].系統(tǒng)仿真學(xué)報,2008,20(21):5936-5939.

[16]夏媛媛,馬立云,王曉原.基于混沌蟻群算法的動態(tài)用戶最優(yōu)配流方法[J].山東理工大學(xué)學(xué)報(自然科學(xué)版),2011,25(3):17-21.

[17]聞育,吳鐵軍.基于蟻群算法的城域交通控制實時滾動優(yōu)化[J].控制與決策,2004,19(9):1057-1063.

[18]劉經(jīng)宇,方彥軍.蟻群算法在城市交通路徑選擇中的應(yīng)用[J].西南交通大學(xué)學(xué)報,2009,44(6):912-917.

[19]谷遠利,李善梅,邵春福.基于蟻群算法的交通控制與誘導(dǎo)協(xié)同研究[J].系統(tǒng)仿真學(xué)報,2008,20(10):2754-2761.

董新捷(1985—)，河南人，工程師，主要研究方向為智能算法、圖像處理等；

E-mail：dong3841919@163.com

韓偉娟(1986—)，河南人，工程師，主要研究方向為無線傳感網(wǎng)絡(luò)等。

Application Research of Ant Colony Algorithm in Traffic Management

Dong Xin-jie1, Han Wei-juan2

(1.Information Science Academy of CETC, Institute of Information System, Beijing 100086, China; 2.Institute of automation, Chinese Academy of Science,Beijing 100190, China)

City traffic congestion is becoming more and more serious with the increasing cars in recent years. Traffic management takes a very important part, but which still faces the difficulties such as traffic congestion and choice of the best path. Ant colony algorithm is an intelligent algorithm to solve the optimal path problem, and a new method is proposed based on ant colony algorithm to solve the traffic problem in a balanced path length and congestion degree. Simulation experiment shows that the method has good performance. Under a certain objective function, the method greatly reduces the degree of congestion and disperses traffic flow through a little increase in car distance. The method has certain practical significance.

traffic management; ant colony algorithm; distance; standard deviation; pheromone; congestion ratio

10.3969/j.issn.1673-5692.2016.06.019

2016-06-01

2016-09-02

：A

1673-5692(2016)06-663-04