基于模擬退火改進人工魚群算法的交通信號配時優化

許佳佳,李雪梅

(安徽三聯學院 1 交通工程學院,2 電子電氣工程學院,安徽 合肥,230601)

交通信號配時優化對于減小交叉口的車均延誤和提升其通行能力有著重要的作用?；诖?相關學者對交叉口信號配時做了諸多研究和改進。如:運用傳統的信號周期配時方法進行交叉信號配時優化及通過軟件進行仿真評價[1～3];通過建立動優化控制模型對交叉口的信號方案進行動態控制研究[4,5];基于交叉口平均延誤最小化目標運用遺傳算法進行交叉口信號配時方案的求解與運行效果評價[6～8];以及運用熒火蟲算法、蜜蜂算法和粒子群算法等智能算法進行信號配時優化[9～11]。由于傳統的信號配時方法無法適用過飽和流量的交叉口優化[12],而單一智能算法在求解信號配時在解決實際問題時因自身的不足影響計算結果和工作效率,如遺傳算法存在編碼不規范和粒子群算法易于陷入局部最優解等問題[6,7]。為此,筆者綜合考慮周期時長和綠燈時間及飽和度等約束條件,以交叉口車均延誤最小為目標函數構建信號配時優化模型,選擇收斂精度高的模擬退火算法和初值魯棒性強的人工魚群算法組合構建模擬退火改進人工魚群算法,對信號配時優化模型進行求解,并對現狀方案和3種不同智能算法求解方案情況下的交叉口整體車均延誤進行對比,驗證模擬退火改進人工魚群算法的可行性與適用性。

1 模擬退火改進人工魚群算法

模擬退火(Simulated Annealing,SA)算法是根據物理知識中固體退火原理所開發的應用于求解最優化模型的一種通用的仿自然優化算法,SA算法中將物質的能量達到最低狀態的設定模擬成目標函數并根據固體物質的退火過程包括加溫、等溫和冷卻等3個過程進行求解[13]。SA算法由于在等溫過程中采用了Metropolis準則,能夠有一定的概率去接受惡化解,使其能夠跳出局部最優而有著較好的全局搜索能力。

人工魚群(Artificial Fish-Swarm,AF)算法是基于魚的覓食、聚群、追尾、隨機活動等行為所提出的一種應用于求解最優化模型的群智能優化算法,在迭代優化的過程中人工魚個體的最優狀態會被進行跟蹤和記錄,并且人工魚往往會在極值點特別是全局極值點進行聚集從而找到最優解[14～16],AF算法相較于傳統的求解方法具有分布處理的能力及參數和初值魯棒性強等特點。

AF算法雖然有著較好的全局收斂性,但由于感知能力和步長參數是固定的,參數設置過大會導致在接近最優解的附近來回振蕩而影響最終求解的精度,參數設置過小會導致在局部最優解中無法跳出即未達到最優值區域結束算法運算,因此可嘗試利用SA算法初值魯棒性和局部收斂精度高的特點對AF算法進行改進,構建模擬退火改進人工魚群(SAAF)算法。首先,通過AF算法對每一代人工魚中的全局最優個體進行搜索,再對其運用SA算法進行退火模擬運算以避免AF算法陷入局部最優解的情況,并將SA算法的尋優結果適應度與AF算法進行對比以更新人工魚群進行迭代。SAAF算法的運算邏輯過程見圖1。

2 交叉口信號配時優化模型

根據美國通行能力手冊中對于交叉口車輛延誤的定義,現有交叉口各進口各個方向車道的車均延誤由均勻延誤和隨機延誤兩部分組成,其中均勻延誤是指進口道車輛均勻到達所產生的均勻延誤,隨機延誤是指進口道車輛隨機到達并引起超飽和周期所產生的延誤,本次研究假設各交叉口各進口車道各個方向的車輛到達類型隨機,對應的各個方向內不同車道的車均延誤是相同的。針對現狀大部分十字型平面交叉口均采用的典型四相位配時方案,本次研究用di表示第i個相位的綜合車均信控延誤(i=1,2,3,4,分別代表東西直行、東西左轉、南北直行、南北左轉相位),單位為s/pcu;di j表示第i個相位中第j個進口方向對應車道的綜合車均信控延誤(i=1,2,3,4;j=1,2)(d11,d12,d21,d22,d31,d32,d41,d42), 單位s/pcu;di j z表示第i個相位中第j個進口方向中第z種單項車均延誤(i=1,2,3,4;j=1,2;z=1,2;其中z=1代表均勻延誤,z=2代表隨機延誤),單位s/pcu;gi表示第i個相位的顯示綠燈時間(i=1,2,3,4),單位s;Si j表示第i個相位第j個進口方向對應的平均單一車道的飽和流率,單位pcu/h;yi表示第i個相位的黃燈時間(i=1,2,3,4),單位s;li表示第i個相位的車輛啟動損失時間(i=1,2,3,4),單位s;t表示分析時段的持續時長,單位h,取0.25 h;e表示單個交叉口信號控制類型校正系數,定時信號取e=0.5。下面以第1個相位中第1個進口方向中的綜合車均延誤d11的均勻延誤d111和隨機延誤d112為例說明延誤計算式,具體見式(1)(2)(3),其它相位和進口方向車道的均勻延誤和隨機延誤可同理計算。

d11=d111+d112

(1)

(2)

(3)

交叉口整體的車均延誤數值越小代表交叉口的運行效果越好,即車輛在經過交叉口時平均延誤的時間越短越好,因此設定交叉口整體車均延誤最小化目標函數。交叉口的信號周期的時長需要設置合理。周期時長過短會直接影響到車輛是否安全通過和行人能否安全通過;而周期時長過長雖然能夠提升交叉口的通行能力,但提升的效率不明顯并會使通行延誤急速增長。因此,在設置周期時長時需要考慮下限和上限的約束,一般將周期時長的范圍限定在40～180 s之間。同理,對于各個相位的綠燈時間也需要進行上限和下限的約束設置。本次研究將各個相位綠燈時間的上限設置為100 s,下限的設置需要考慮車輛和行人通過交叉口的最短時間,用wimax表示為第i個相位中兩個對向方向車輛或行人通過交叉口需要經過的最大距離,vc表示車輛通過的區間速度,vp表示行人通過的區間速度。因大部分情況下通過交叉口的損失時間與黃燈時間相近,此處對各相位最短綠燈時間進行簡化處理,對應的直行相位因為要考慮行人通行,其綠燈時長的下限為wimax/vp,而對于只需考慮車輛通行的左轉相位綠燈時長下限為wimax/vc。為了克服經典Webster方法只適用于非飽和流量的情況,此處考慮將整個交叉口的飽和度作為約束條件進入模型,根據交叉口優化效果的經驗將飽和度設置在0.7～0.9的閉區間范圍內?；谏鲜瞿繕撕瘮岛图s束條件,結合前述延誤計算理論中的定義構建交叉口信號配時優化模型,具體見式(4)。

(4)

式中:z為交叉口整體的車均延誤,單位s/pcu;qi j為第i個相位中第j個進口方向的交通量,單位pcu;di j為第i個相位中第j個進口方向的車均延誤,單位s/pcu;gi為第i個相位的顯示綠燈時間,單位為s;yi為第i個相位的黃燈時間,單位s;wimax為第i個相位中兩個對向方向車輛或行人通過交叉口需要經過最大的距離,單位m;vc表示車輛通過交叉口的區間速度,單位m/s;vp表示行人通過交叉口人行橫道的區間速度,單位m/s;yi表示第i個相位的黃燈時間,單位s;li為第i個相位的車輛啟動損失時間,單位s。

3 實例分析

以安徽省合肥市紫云路與金寨路相交的典型四相位十字型平面交叉口(以下簡稱“紫金路口”)的交通流量數據為例,相位1對應東西直行,相位2對應東西左轉,相位3對應南北直行,相位4對應南北左轉,右轉不設專用相位(即車輛右轉不受信號控制),車道寬度>3 m,道路無縱坡,無自行車影響,大車比例很小不作特別分析,因此不考慮對飽和流率的影響與修正,確定一條直行車道的標準飽和流量為1 650 pch/h,一條直行車道的標準飽和流量為1 550 pch/h。該交叉口各方向流量與配時基礎數據見表1。

表1 安徽省合肥市紫云路與金寨路平面交叉路口各方向流量與配時數據

基于交叉口的現狀交通流量和配時數據,考慮交叉口各個相位的啟動損失時間為3 s,計算結果顯示,整體交叉口的車均延誤為202.81 s/pcu,表明車輛通過該交叉口時的擁堵情況較為嚴重。下面試驗用SA算法和AF算法及SAAF算法進行交叉口的信號配時優化。

(1)SA算法的相關參數設置:隨機生成初始解,初始溫度T0=1 000,終止溫度Tend=0.001, 每次退火溫度下的迭代次數L=500,降溫速率q=0.9, 最大迭代次數count=100。

(2)AF算法的相關參數設置:人工魚的數量fishnum=100, 最大迭代次數MAXGEN=100,覓食行為中的最多試探次數try_number=30, 模擬魚感知半徑的感知距離visual=35, 擁擠度因子(模擬魚群的擁擠程度的擁擠度因子)delta=0.618, 最大移動步長step=4.5。

(3)交叉口延誤計算的其他相關參數設置:針對于交叉口信號配時的約束優化模型中的約束條件要求,行人過街步行速度vp取1.5 m/s, 車輛通過交叉口的速度vc為3 m/s, 4個相位中兩個對向方向車輛或行人通過交叉口需要經過最大的距離依次取40,50,30,50 m,各相位的綠燈損失時間均取3 s, 各相位的黃燈時間也設置為3 s。

基于交叉口的流量數據和相關的交叉口形式、交通流和信號配時的默認設置參數,代入上述交叉口信號配時的約束優化模型從而實現模型的實例化,先分別運用SA算法和AF算法對其進行啟發式求解和計算延誤,再將兩種方法基于前述模擬退火改進人工魚群算法的思路進行組合并進行實例模型的求解,最終得到單一智能算法和組合改進算法的信號配時方案解及對應的延誤數據,具體的交叉口信號配時現狀與優化方案及其運行效果評價數據見表2。

表2 安徽省合肥市紫云路與金寨路平面交叉路口信號配時現狀與優化方案運行效果

試驗結果表明,SA算法、AF算法和SAAF算法所得的信時配時方案中的時間數據之間較為接近,但相對于現狀信號配時方案有著較大變化,3種算法求解的信號配時方案對應的交叉口整體的車均延誤分別為98.94,97.88,96.66 s/pcu,相較于現狀交叉口車均延誤均減小了50%以上,說明通過智能算法進行交叉口信號配時優化的效果較為明顯,并且其中SAAF算法所得方案的車均延誤要更優于單一的SA算法和AF算法(圖2)。

圖2 交通信號配時優化3種算法迭代優化過程

計算結果表明,3種不同的算法的迭代過程變化情況有著較大的差異(圖2)。SA算法因為其全局搜索能力表現出迭代初期過程波動程度較大,而AF算法基于其較強的搜索能力使得其初期解的結果較優并且下降過程較為穩定。而SAAF算法結合了兩種方法的優點,在迭代的初期即非常接近最優解,在后續迭代過程中也表現非常穩定的持續下降趨勢,并且改進后的算法歷代迭代所得到的信號配時方案對應的交叉口整體車均延誤均優于另兩種算法,表現出SAAF算法求解約束優化模型的良好效果。

4 結論與討論

本次研究以交叉口車均延誤最小為目標函數和周期時長及綠燈時間等為約束條件構建信號配時優化模型,并基于SA算法對AF算法進行改進后對模型進行求解與分析交叉口的通行效果改進情況,得出以下結論:(1)AF算法由于其感知能力和步長參數是固定的,會使其容易跳過最優解和陷入局部最優解,利用SA算法初值魯棒性和局部收斂精度高的特點進行改進可以提升其搜索全局最優解的能力;(2)SA算法、AF算法和SAAF算法求解所得的信時配時方案中的時間數據之間較為接近,相對于現狀信號配時方案有著較大的優化效果,并且SAAF算法的效果要優于單一算法。(3)SA算法在迭代運算的初期過程波動程度較大,而AF算法初期解的結果較優并且下降過程較為穩定,SAAF算法在迭代的初期便能非常接近最優解和穩定下降趨勢表現出快速尋優的能力。本次研究主要針對典型的平面單點十字交叉道口,對于其它類型的交叉口信號配時點控和多個交叉口的線控還有待進一步論證和研究。