基于萬有引力搜索算法的低排放自適應配時

李世武,徐 藝,王琳虹,孫文財,別一鳴

（1.吉林大學交通學院,吉林長春130022；2.哈爾濱工業大學交通科學與工程學院,黑龍江哈爾濱150090）

基于萬有引力搜索算法的低排放自適應配時

李世武1,徐 藝1,王琳虹1,孫文財1,別一鳴2

（1.吉林大學交通學院,吉林長春130022；2.哈爾濱工業大學交通科學與工程學院,黑龍江哈爾濱150090）

結合自適應配時策略分析運算時間在低排放自適應配時中的重要性和基本萬有引力搜索算法（GSA）較常規搜索算法的優勢,以減少交叉口處機動車排放為目的,借鑒低排放自適應配時模型和GSA優化算法原理,提出基于GSA的低排放自適應信號配時方法.以實際交通狀態數據為基礎數據進行實例驗證.結果顯示,在相同精度下使用基于GSA配時方法較基于一般優化方法的配時的車均排放低2.82%,運算時間短36.56%.證明了基于GSA的低排放自適應信號配時方法具有較好的優化效果和較高的運算速度,適用于低排放自適應配時的優化.

交通工程；信號配時方法；萬有引力搜索算法（GSA）；低排放

作為路網中車流的集散交匯點,交叉口處的車輛排放日益受到關注,在無法于短時間內大規模降低單車排放的情況下,通過優化信號配時降低交叉口車輛平均排放是一種快速有效的方法.國內外已有學者對面向低排放的交叉口信號配時進行了研究并取得了顯著成果.Liao［1］基于燃油消耗進行了信號配時優化；李世武等［2］建立面向低排放的交叉口信號配時模型；Li等［3］面向通行效率、排放和油耗對信號配時的綜合優化進行研究；Kwak等［4-5］基于遺傳算法（GA）研究低排放信號配時；首艷芳等［6-7］建立包括排放的多目標動態決策模型,基于GA對模型進行求解.

當前低排放配時的相關模型日益成熟,但為適應交通系統的狀態變化需要提高低排放配時的實時性,因此制約低排放配時成果應用推廣的關鍵問題是尋求合適、高效的模型求解方式.在求解方式上,出現了可媲美GA的萬有引力搜索算法［8］,國內外學者已對基本萬有引力搜索算法（GSA）進行改進［9］并加以應用,如：Zhao［10］將GSA用于圖像增強；Esmat等［11］提出基于GSA的濾波模型；Zhang等［12］結合GSA和支持向量機（SVM）進行蒸汽渦輪熱效率的預測研究；牛培峰等［13］構建基于GSA的SVR（支持向量回歸機）模型,用于預測板型模式隸屬度；GSA還被應用于石油需求預測等領域［14-15］.

由于已有面向低排放的自適應信號配時模型較常規面向通行效率的Webster配時模型的復雜度與計算量均較高,從而易影響配時減排的效果.面向信號配時實時性和高精度的需求,本文提出基于GSA的低排放自適應信號配時方法,以期利用運算過程簡單、單位迭代時間短的基本萬有引力搜索算法求解低排放配時模型.面向排放模型的實際應用,以求解時間、求解精度為指標,通過仿真運行結果證明了基于GSA的低排放自適應信號配時方法的自適應性和有效性.

1 低排放自適應信號配時

1.1 面向低排放的信號配時模型

設交叉口不存在過飽和現象,周期為T,相位i（i＝1,2,…,n,n為相位總數）的綠燈時長為tgi,車均到達率為qi,車道的飽和流率為Si,排隊車輛平均車頭間距為,車型k在車輛總數中所占比例為fk（1≤k≤j,j為檢測車型總數）,車均速度為,單位時間內k型車減速排放量為mmk1、怠速排放量為mmk2、加速排放量為mmk3、勻速排放量為mmk0,完全停車車輛的減速持續時間為ta,不完全停車車輛的平均減速持續時間為ta2,i相位經歷完全停車和不完全停車的污染物排放量分別為mwi和mbi,借鑒文獻［2］的低排放信號配時模型可知,車均排放為

交通狀態確定后,存在不隨配時方案改變的參數,令

在交叉口各相位最小綠燈時間tgi,min、最大綠燈時間tgi,max以及交叉口最大周期Tmax、最小周期Tmin的約束下,求解使得交叉口平均機動車排放增加量m最小的信號配時方案,即求解使得m最小的tgi.

1.2 面向低排放的信號配時策略

制定自適應配時策略如下：每周期結束時統計虛擬線圈（視頻檢測系統）檢測到的交通數據,將車型比例k、車均速度、該周期時長T、機動車排放因子代入低排放配時模型中,求解最優的tgi,將計算得到的低排放信號配時方案應用于下一信號周期中.

具體步驟如下.

1）檢測交叉口交通參數.

2）本周期開始時分別統計上一周期i相位中完全停車、不完全停車、不減速車輛的車輛數Qi,1、Qi,2、Qi,3、Qi,4,各自的車型比例k和車均速度.

3）將尾氣權重、排放因子和檢測到的交通參數代入優化模型中,使用目標優化方法得到本周期最優的信號配時.

4）判斷計算時間是否超過所得最優配時方案的第一相位時間tg1或缺省配時方案的第一相位時間td1.若均未超過,則使用計算得到的最優信號配時；若超過,則使用缺省信號配時.

2 基于GSA的低排放配時方法

2.1 GSA算法及優勢

2009年,伊朗克曼大學的教授Esmat Rashedi等提出萬有引力搜索算法（GSA）.通過研究發現,在對標準測試函數進行最優解搜索時,這種模擬物理學中萬有引力的群體智能優化方法的尋優精度和收斂速度均較高.

不同于GA和PSO,GSA算法（GSA原理參見文獻［7］）中粒子位置的更新規則是將當前每一個粒子按照萬有引力定律向最優解方向移動,避免了實際應用中因更新規則和移動規律選擇不當導致的收斂速度和搜索精度的降低,且粒子受到的引力（t）由全局粒子的質量Maj（t）和位置Xi決定,可以充分利用搜索空間全局解狀態和適應度信息,提高搜索效果.

2.2 基于GSA的低排放配時方法

由動態配時策略可知,為了提高低排放配時方法的有效性,應盡量使最優配時的求解運行時間（running time）小于tg1和td1,從而避免使用缺省的信號配時,因此需要選擇一種快速有效的搜索算法進行模型的求解.

使用GSA進行低排放自適應信號配時的優化計算,提出基于GSA的低排放自適應信號配時方法,方法流程如圖1所示.具體流程如下.

1）數據檢測.

檢測交叉口交通參數,運行步驟2）.

2）數據初處理.

統計Qi,1、Qi,2、Qi,3、Qi,4、k和,將尾氣權重、排放因子和檢測到的交通參數代入優化模型.設缺省配時方案的第一相位時間為td1,運行步驟3）.

圖1 基于GSA的低排放配時方法流程圖Fig.1 Flowchart of GSA based low emission signal timing method

3）GSA初始條件設定.

設適應度為fit＝m,搜索粒子數量為n,迭代次數為r（初始迭代次數為r＝1）,將每一相位的綠燈時間tg（r）（tg（r）＝｛（tg11,tg21,tg31）,（tg12, tg22,tg32）,…,（tg1n,tg2n,tg3n）｝）作為搜索粒子位置,GSA終止條件為適應度小于s,s∈R＋（或迭代次數大于c,c∈N＋）,設t為計算運行時間并開始計時,運行步驟4）.

4）GSA計算過程.

更新粒子位置為最小綠燈時間與最大綠燈時間范圍內的隨機數,按照GSA的相關公式計算M、a,搜索粒子的速度和位置、適應度fit,并更新引力常數G和最小值best.

5）過程迭代及結果輸出.

獲取計算運行時間t；若t≥td1,輸出缺省信號配時；若t＜td1且fit（r）＞sr,r＝r＋1,運行步驟4）；若t＜td1且fit（r）≤sr,則將tg（r）作為最終綠燈時間輸出信號配時方案.

3 實例驗證與結果分析

使用長春大街－大經路交叉口上午9：00－10：00期間可以反映大部分平峰時段交通特征的實際交通數據進行單周期低排放配時計算,比較3種搜索算法的效果.

長春大街-大經路交叉口渠化及相位相序如圖2所示,交叉口缺省配時如表1所示.

表1 長春大街與大經路交叉口缺省配時方案Tab.1 Default signal timing plan of Changchun Street-Dajing Road intersection

長春大街-大經路交叉口流量與車型比例如表2所示.

表2 長春大街與大經路交叉口流量與車型比例Tab.2 Traffic flow and vehicle type proportion at Changchun Street-Dajing Road intersection

將實時測量的指定捷達車和公交車排放因子作為小型車和大型車的排放因子均值（詳細數據見文獻［2］的表3）.設交叉口最大周期Tmax＝160 s,最小周期Tmin＝80 s,直行相位最大綠燈時間tgi,max＝60 s,最小綠燈時間tgi,min＝15 s,左轉相位最大綠燈和最小綠燈分別為40、12 s.

圖2 長春大街-大經路交叉口渠化及相位相序圖Fig.2 Phase scheme and channelization of Changchun Street-Dajing Road intersection

3.1 運算精度比較

設置GSA、PSO和RGA（實值遺傳算法）均為最小值搜索,函數維度取相位數4,最大迭代次數取500（Iteration＝500）；GSA和RGA粒子數量均為50,PSO粒子數量為250,3種搜索算法均隨機生成初始種群；PSO的全局學習因子和局部學習因子均取2,使用線性遞減慣性權重,權重初始值取0.95,權重終止值取0.4,收縮因子取0.7；RGA中使用輪盤賭選擇方式,設置交叉概率為0.3,變異概率為0.1.

計算當前配時方案下的車均排放后,使用Matlab編程,分別基于GSA、RGA和PSO運行30次,每種搜索算法的車均排放曲線如圖3所示.圖中,m為車均排放,ni為迭代次數.運算時間與搜索結果如表3所示.表中,tr為運行時間.

表3 GSA、RGA和PSO算法運行時間與搜索結果Tab.3 Operation time and search results of GSA,RGA and PSO

由圖3和表3可知,PSO算法的最終搜索結果與運行時間同GSA和RGA相比相差較大,PSO算法的前期收斂速度與GSA算法相近,但終止迭代收斂效果較差,使得最終搜索效果不佳；GSA與RGA的運行時間和最終搜索結果較接近,且在100～500次迭代范圍內RGA的收斂速度具有提高的趨勢.為了進一步比較兩者的效果,比較GSA與RGA迭代1 500次的搜索效果.

圖3 GSA、RGA和PSO算法求解單周期配時排放曲線Fig.3 Single cycle curves of low emission timing based on GSA,RGA and PSO

迭代1 500次的車均排放曲線如圖4所示,運算時間與搜索結果如表4所示.

圖4 GSA和RGA算法求解配時排放曲線Fig.4 Timing curves of low emission based on GSA and RGA

表4 GSA和RGA算法運行時間與搜索結果Tab.4 Operation time and search results of GSA and RGA

由圖4和表4可見,迭代約100次后GSA不隨迭代次數的增加而收斂,RGA的搜索精度隨迭代次數的增加而緩慢提高,但最終未能達到GSA迭代100次時的精度.可得結論如下：在求解低排放信號配時模型時,GSA比PSO和RGA收斂速度快、求解精度較高.

3.2 運算時間比較

由動態配時策略可知,優化算法的求解時間將決定是否使用缺省配時,因而有必要比較相同終止精度（termination tolerance on function value）下不同搜索算法的運算時間、最優解.設置RGA、GSA的終止精度為10－10,通過比較相同軟、硬件條件下GSA和RGA到達終止精度的運算時間,以判斷低排放自適應配時中的適用性.運行30次的計算情況如表5所示.表中,mc、ma分別為計算車均排放和實際車均排放.

表5 GSA與RGA的運算時間表Tab.5 Operation time of GSA and RGA

由表5可知,當收斂的終止精度相同時,RGA的運行時間為GSA運行時間的226.28%,計算得到的車均排放比GSA高1.6%.由于2次缺省配時的使用,RGA的車均排放在實際信號配時中比GSA高4.2%,表明在低排放自適應信號配時的實際應用中,優化算法的運算時間將對配時效果產生較大影響.

對10組交叉口信號配時進行實例驗證,設定終止精度為10－10.按照1.2節的配時策略,判斷計算時間是否超過所得最優配時方案的第一相位時間tg1或缺省配時方案的第一相位時間td1.若均未超過,則使用計算得到的最優信號配時；若超過,則使用缺省信號配時,使用判斷后的信號配時按式（7）計算實際車均排放量.最終的計算結果如表6所示.結果表明,GSA在優化低排放信號配時中的優化效果好,運算速度快,適用性較好.

由表6可見,在相同精度下使用基于GSA配時方法較基于RGA配時方法的車均排放低2.82%,運算時間短36.56%,證明了基于GSA的低排放自適應信號配時方法具有較好的優化效果和較高的運算速度.

表6 多組信號配時運算結果Tab.6 Results of multiple data sets

4 結 語

本文分析了基于低排放信號配時模型的自適應配時策略,闡明了使用運行時間評價低排放自適應配時效果的必要性,介紹了基本萬有引力搜索算法原理,分析了GSA較常規搜索算法的優勢.使用基本GSA對長春大街－大經路交叉口進行低排放自適應配時,以求解時間、求解精度、車均排放為評價指標比較了GSA、RGA、PSO算法在進行實際配時優化時的效果,證明了基本GSA在低排放自適應配時中優化效果好、運算速度快、適用性好.

本文為在低排放自適應配時中使用GSA的一次嘗試,僅研究了基本GSA和單目標配時優化而未對改進的GSA和多目標配時優化進行研究.本文僅使用平峰時段的數據進行實例驗證,未使用較高或較低時段的數據進行實例驗證.在后續研究中,將進一步研究GSA及其改進算法在多目標配時優化中的應用,研究GSA在不同道路交通狀態下低排放信號配時的有效性.

［1］LIAO Tsai-yun.A fuel-based signal optimization model［J］.Transportation Research Part D,2013,23（8）：1- 8.

［2］李世武,王琳虹,郭棟,等.基于機動車排放的自適應信號控制模型 ［J］.華南理工大學學報：自然科學版, 2011,39（3）：101- 106.

LI Shi-wu,WANG Lin-hong,GUO Dong,et al.Adaptive signal control model based on vehicle emission［J］.Journal of South China University of Technology：Natural Science Edition,2011,39（3）：101- 106.

［3］LI Xiu-gang,LI Guo-qiang,PANG Su-seng,et al.Signal timing of intersections using integrated optimization of traffic quality,emissions and fuel consumption：a note［J］.Transportation Research Part D,2004,9（5）：401- 407.

［4］KWAK J,PARK B,LEE J.Evaluating the impacts of urban corridor traffic signal optimization on vehicle emissions and fuel consumption［J］.Transportation Planning and Technology,2012,35（2）：145- 160.

［5］趙偉濤,楊威,岳一博.考慮車輛排放的城市信號交叉口優化控制研究 ［J］.武漢理工大學學報：交通科學與工程版,2012,36（5）：911- 915.

ZHAO Wei-tao,YANG Wei,YUE Yi-bo.Optimization research on signal timing for urban intersection by considering vehicle emission［J］.Journal of Wuhan University of Technology：Transportation Science and Engineering,2012,36（5）：911- 915.

［6］首艷芳,徐建閩.信號交叉口多目標動態決策模型及其優化方法［J］.公路交通科技,2012,29（11）：92- 97.

SHOU Yan-fang,XU Jian-min.Multi-objective dynamic decision-making model of signalized intersection and its optimization method［J］.Journal of Highway and Transportation Research and Development,2012, 29（11）：92- 97.

［7］BIE Y,WANG L,WANG D,et al.A signal coordination algorithm for two adjacent intersections based on approximate dynamic programming［J］.Journal of Southeast University,2012,28（1）：112- 118.

［8］ESMAT R,HOSSEIN N P,SAEID S.GSA：a gravitational search algorithm［J］.Information Sciences,2009, 179（13）：2232- 2248.

［9］ESMAT R,HOSSEIN N P,SAEID S.BGSA：binary gravitational search algorithm［J］.Natural Computing, 2010,9（3）：727- 745.

［10］ZHAO Wei-guo.Adaptive image enhancement based on gravitational search algorithm［J］.Procedia Engineering,2011,15（3）：3288- 3292.

［11］ESMAT R,HOSSIEN N P,SAEID S.Filter modeling using gravitational search algorithm［J］.Engineering Applications of Artificial Intelligence,2011,24（1）：117- 122.

［12］ZHANG Wei-ping,NIU Pei-feng,LI Guo-qiang.Forecasting of turbine heat rate with online least squares support vector machine based on gravitational search algorithm［J］.Knowledge-Based Systems, 2013,39（2）：34- 44.

［13］牛培峰,李鵬飛,李國強,等.基于萬有引力優化的支持向量機模型在板形識別中的應用［J］.鋼鐵,2013, 47（12）：45- 49.

NIU Pei-feng,LI Peng-fei,LI Guo-qiang,et al.Application of GSA-SVR model in flatness pattern recognition［J］.Iron and Steel,2013,47（12）：45- 49.

［14］BEHRANG M A,ASSAREH E,GHALAMBAZ M, et al.Forecasting future oil demand in Iran using GSA（gravitational search algorithm）［J］.Energy,2011, 36（9）：5649- 5654.

［15］DUMAN S,GüVEN?U,Y?RüKEREN N.Gravitational search algorithm for economic dispatch with valve-point effects［J］.International Review of Electrical Engineering,2010,5（6）：2890- 2895.

Gravitational search algorithm based adaptive low emission signal timing

LI Shi-wu1,XU Yi1,WANG Lin-hong1,SUN Wen-cai1,BIE Yi-ming2
（1.Transportation School,Jilin University,Changchun 130022,China；2.School of Transportation Science and Engineering,Harbin Institute of Technology,Harbin 150090,China）

The importance of the operation time in adaptive low emission signal timing was analyzed combining with adaptive signal timing strategy,and the advantages of gravitational search algorithm（GSA）over normal search algorithms were analyzed.The adaptive low emission signal timing model and the gravitational search algorithm were referred to propose the GSA based adaptive low emission signal timing method in order to reduce vehicle emission at intersections.The real traffic data were used to verify the method.Results show that under the same accuracy,the vehicle emission of GSA based adaptive low emission signal timing method is 2.82%lower than the vehicle emission of the normal optimization based signal timing method,and the operation time is 36.56%shorter than the normal optimization based signal timing method.The GSA based adaptive low emission signal timing method has better optimization effect and faster operation speed,and is suitable for adaptive low emission optimization.

traffic engineering；signal timing method；gravitation search algorithm（GSA）；low emission

10.3785／j.issn.1008-973X.2015.07.016

U 495

A

1008- 973X（2015）07- 1313- 06

2015- 01- 02. 浙江大學學報(工學版)網址：www.journals.zju.edu.cn／eng

國家自然科學基金青年基金資助項目（51308250）；國家自然科學基金青年基金資助項目（51308251）；吉林大學科學前沿與交叉學科資助項目（2013ZY06）；中國博士后科學基金資助項目（2013M541306）；吉林大學研究生創新研究計劃資助項目（2014054）；吉林大學競業杯研究生創新創業項目（2014CXCY032）.

李世武（1971－）,男,教授,從事交通環境與安全技術的研究.ORCID：0000-0001-6010-7422.E-mail：lshiwu＠163.com

王琳虹,女,講師.ORCID：0000-0002-6418-1520.E-mail：wanghonglin0520＠126.com