基于PSO-GA算法的交叉口仿真優(yōu)化研究

任永泰，鄧 朝，王紫陽

(1. 東北農(nóng)業(yè)大學(xué)文理學(xué)院，黑龍江哈爾濱 150030；2. 東北農(nóng)業(yè)大學(xué)工程學(xué)院，黑龍江哈爾濱 150030)

1 引言

隨著城市的快速發(fā)展，交通擁堵已成為城市中的嚴(yán)峻問題，直接影響是延誤增加，造成交通運(yùn)行效率的降低[1]。而交叉口發(fā)生擁堵的主要原因是信號周期的不合理分配[2]。因此，為了緩解交通擁堵、提高運(yùn)輸效率，交通信號的控制和優(yōu)化至關(guān)重要[3]。

針對交通信號配時及交通擁堵的問題，研究人員提出將自然啟發(fā)算法用于交通系統(tǒng)的控制和優(yōu)化[4-5]，根據(jù)該算法的更新技術(shù)，可分為兩種。第一種是進(jìn)化算法(EA)[6]，作為EA的代表算法，遺傳算法(GA)廣泛運(yùn)用于交通燈信號優(yōu)化配時中[7]。Kou[8]使用GA找到了最佳信號配時，提出的GA優(yōu)化模型取得了更好的效果。高云峰[9]以非飽和交叉口作為實(shí)驗(yàn)對象搭建了定周期信號控制的多目標(biāo)優(yōu)化模型，并運(yùn)用非支配排序遺傳算法求解。但是GA的局部搜索能力較差，后期搜索效率較低，整個迭代過程也比較費(fèi)時。第二種是群智能(SI)算法，作為SI算法之一，PSO所具有的全局最優(yōu)引導(dǎo)能力引起了研究人員的廣泛關(guān)注[10]。Dabiri[11]使用PSO優(yōu)化了動脈交通信號的時序參數(shù)。與信號優(yōu)化工具Vistaro的時序計劃相比，PSO生成的時序方案使時間延遲大幅降低。但是，PSO可能使問題陷入局部最優(yōu)。因此，結(jié)合兩種自然啟發(fā)算法的優(yōu)缺點(diǎn)，本文提出了一種遺傳算法-粒子群優(yōu)化算法(PSO-GA)，并將其用于交通信號配時的模型求解中。

PSO-GA算法是PSO的改進(jìn)算法，利用了PSO的全局引導(dǎo)能力并引入GA的交叉和變異算子，具有收斂速度快和強(qiáng)魯棒性的特點(diǎn)，能找到目標(biāo)函數(shù)的全局最優(yōu)解。PSO-GA可用于函數(shù)優(yōu)化并應(yīng)用于許多問題，如利用PSO-GA優(yōu)化神經(jīng)網(wǎng)絡(luò)，TSP問題，資源分配問題[12-13]。但就目前而言，很少有學(xué)者將PSO-GA運(yùn)用于交通信號時序優(yōu)化。

此外，Synchro[14]軟件作為一種典型的交通微觀仿真軟件，被廣泛應(yīng)用于交通流模擬和優(yōu)化。靈敏度分析也是檢驗(yàn)不同變量對目標(biāo)影響的有效工具[15]。綜上，本文提出使用PSO-GA求解交通時序優(yōu)化問題，用Synchro軟件進(jìn)行交通仿真并使用靈敏度分析討論了車流量對交通運(yùn)行的影響。

與現(xiàn)有研究相比，本文的研究有以下貢獻(xiàn)：①將PSO-GA運(yùn)用于交通信號時序優(yōu)化中，通過與其它方法對比驗(yàn)證了算法的有效性。②將交通信號時序優(yōu)化技術(shù)與交通模擬工具相結(jié)合，開發(fā)了一種基于模擬優(yōu)化的模型。③進(jìn)一步討論了高低車流量變化對交叉口運(yùn)行效率的影響，為相關(guān)交通運(yùn)輸部門提供理論支持和實(shí)踐指導(dǎo)。

2 建立信號控制多目標(biāo)優(yōu)化模型

為提高交通運(yùn)行效率，本文研究了交叉口信號周期的優(yōu)化調(diào)整策略，以周期時長和飽和度作為配時參數(shù)，將車輛延誤、停車次數(shù)和交叉口通行容量作為路口信號配時優(yōu)化的三個重要指標(biāo)，建立了多目標(biāo)優(yōu)化模型，以優(yōu)化現(xiàn)有時序方案。

2.1 車輛延誤

常用的時延是基于Webster模型的。但是，在低飽和度條件下Webster模型才比較適合。因此，本文對Webster模型進(jìn)行了改進(jìn)，將延誤定義為

(1)

2.2 平均停車次數(shù)

停車次數(shù)即一個周期信號中完全停車次數(shù)的總和，它的增加會帶來延誤的增加，與飽和度成反比，交叉口第i相位的平均停車次數(shù)可定義為

(2)

2.3 交通容量

相位交通容量即指相位通行能力，它是指相位關(guān)鍵車道的通行能力，定義如下

(3)

這里Si是指相位i的飽和流量。

2.4 多目標(biāo)優(yōu)化模型的構(gòu)建

考慮實(shí)際狀況，將交叉口信號配時優(yōu)化的三個目標(biāo)采用加權(quán)方式轉(zhuǎn)化為單目標(biāo)求解問題。這樣簡化后的目標(biāo)函數(shù)表示為

(4)

(5)

3 算法設(shè)計與模型仿真

3.1 混合PSO-GA算法的簡介

PSO算法可以記住全局最優(yōu)狀態(tài)和個體最優(yōu)狀態(tài)來影響粒子的運(yùn)動模式，而這種全局最優(yōu)導(dǎo)引能力可以導(dǎo)致快速收斂。但是，這也會使PSO容易陷入局部最優(yōu)。為此，將GA的交叉和變異算子引入到PSO算法中，以便將兩種算法的優(yōu)點(diǎn)結(jié)合起來，從而更好，更快地獲得最優(yōu)解。為進(jìn)一步加快優(yōu)化速度，可通過共享全局最優(yōu)方法來實(shí)現(xiàn)兩種算法的獨(dú)立性和協(xié)同操作。具體步驟如下：

1)初始化參數(shù)值，包括種群大小(設(shè)為1000)，交叉率(0.7)和突變率(0.2)，最大迭代次數(shù)(50)。為了避免迭代過程陷入局部最優(yōu)，同時減小計算時間，這里采用較大的種群規(guī)模。同時通過交叉和變異算子來增加群體的多樣性，進(jìn)一步達(dá)到避免局部最優(yōu)，達(dá)到全局最優(yōu)的目的。

2)隨機(jī)生成n個粒子的初始化種群，并計算所有粒子的目標(biāo)函數(shù)值，尋找并記錄個體和全局最優(yōu)解。

3)將種群分為兩組，規(guī)模分別為n×P和n×(1-P)，然后分別在這兩組中采用PSO算法和GA算法。這里P是混合概率，設(shè)為0.3。

4)采用Clerc提出的帶約束因子的PSO算法。速度更新公式如下：

v1=wv1+c1·r1·(pi-xi)+c2·r2·(pg-xi)

(6)

φ=φ1+φ2

(7)

c1=wφ1

(8)

c2=wφ2

(9)

與標(biāo)準(zhǔn)PSO相同，這里，vi是第i個粒子的當(dāng)前速度；r1和r2是0-1均勻分布的兩個偽隨機(jī)數(shù)；xi是粒子當(dāng)前位置，pi和pg分別是微粒的歷史最佳位置和粒子群體的全球最佳位置。并且φ1和φ2都設(shè)置為2.05。在飛行過程中，粒子的速度受到vmax的限制，定義為

vmax=(xmax-xmin)/10

(10)

這里xmax和xmin分別是自變量的上限和下限。

通過更新的速度和當(dāng)前位置以獲取下一時刻的位置

xi=xi+vi

(11)

根據(jù)上式更新位置后，計算所有粒子目標(biāo)函數(shù)值，尋找并記錄新的個體和全局最佳解。

5)采用GA算法：采用輪盤賭策略來選擇個體進(jìn)行交叉操作。兩個體x1和x2的交叉按下列公式

(12)

(13)

突變的粒子是隨機(jī)選擇的，并將變異操作定義如下

xnew=x+w·(xmax-xmin)

(14)

6)將PSO和GA算法過程產(chǎn)生的后代群體組合，并選擇適應(yīng)度值最大的n個粒子形成新種群。

7)重復(fù)3)-6)，直到滿足最大迭代次數(shù)為止。

具體流程圖如圖1所示。

3.2 模型仿真模擬及優(yōu)化

為了對交叉口現(xiàn)狀信號配時進(jìn)行仿真評價，本部分利用Synchro系統(tǒng)信號配時優(yōu)化功能實(shí)現(xiàn)。Synchro系統(tǒng)是信號配時優(yōu)化的專業(yè)仿真軟件，能夠優(yōu)化信號相位、周期、配時等，并做出信號配時的方案的相關(guān)評價。為了分析高低流量對車輛運(yùn)行的影響，將運(yùn)用靈敏度分析法進(jìn)行研究。靈敏度分析即模型中某一影響因素(模型參數(shù)或外部環(huán)境)發(fā)生變化對模型輸出的影響程度，常用于模型參數(shù)化過程和模型校正。本文在現(xiàn)有交通流量的基礎(chǔ)上增加高流量(1.2Q)和低流量(0.8Q)兩種情景，討論不同情景下的評估指標(biāo)變化。

4 案例研究

案例中選取了武漢某一典型十字交叉口為研究對象，東西南北各進(jìn)口均設(shè)置左、直、右三個專用道，采用包含東西直行、東西左轉(zhuǎn)、南北直行和南北左轉(zhuǎn)典型四相位控制，如圖2。信號周期為140s，四個相位的時間分別為56s、23s、35s、26s，各相位時間均有3s黃燈時間、3s啟動損失時間和1s紅燈時間。

圖2 交叉路口相位控制圖

此次調(diào)查在早高峰時段(7∶30～8∶30)進(jìn)行，獲得的車流量數(shù)據(jù)如表1所示。

表1 高峰時段交叉口各進(jìn)口道流量數(shù)據(jù)

這里東西進(jìn)口方向的飽和流量為3600PCU·h-1，南北向飽和流量為3200PCU·h-1。

4.1 不同配時方案的比較

實(shí)驗(yàn)中首先運(yùn)用Webster法重新配時計算，然后在Matlab環(huán)境下將建立的信號配時優(yōu)化模型分別運(yùn)用PS0和PSO-GA算法求解。

將GA算法運(yùn)用于交叉口時序優(yōu)化問題，這里GA算法是利用Matlab的Optimization工具箱來求解的。設(shè)置GA的初始種群個數(shù)為1000，根據(jù)個體的適應(yīng)度值來選擇最優(yōu)解。其中涉及到的選擇、交叉和變異操作設(shè)置的參數(shù)(包括交叉率和變異率)與PSO-GA算法一致，在此不再贅述。此外，實(shí)驗(yàn)中函數(shù)值精度1e-6，非線性約束為1e-3，初始值(100；0.7)，當(dāng)?shù)降?20代時，實(shí)驗(yàn)終止，此時模型的最優(yōu)解為c=120，x=0.609，迭代過程如圖3。

圖3 GA的迭代過程

從圖3可以看出，GA算法在迭代70次左右才獲得最優(yōu)解，并不會出現(xiàn)太大的波動，迭代120次時尋優(yōu)結(jié)束。整個迭代過程較為平穩(wěn)，沒有出現(xiàn)來回振蕩的情況。

然后，將混合PSO-GA算法用于解決信號時序優(yōu)化問題，按照前一章介紹的PSO-GA的算法流程和參數(shù)設(shè)置，利用相關(guān)程序，得到模型的最佳周期為c=112.6s，迭代過程如圖4。

圖4 PSO-GA的迭代過程

圖4顯示了PSO-GA的實(shí)驗(yàn)結(jié)果。與GA類似，在PSO-GA模型中，適應(yīng)度值在一開始就保持穩(wěn)定，然后在第25次迭代后最優(yōu)解就開始急劇下降，經(jīng)過36次迭代，就可以獲得最優(yōu)解，而不會產(chǎn)生太大波動。上述特征表明，與GA相比，PSO-GA的收斂速度和穩(wěn)定性更好。該結(jié)果與PSO-GA的優(yōu)勢相吻合，可以更好、更快的獲得問題的優(yōu)質(zhì)解。

為了評價本文提出模型的性能，將現(xiàn)行配時方案、Webster模型、GA模型和PSO-GA模型的各項(xiàng)交通數(shù)據(jù)輸入Synchro軟件得到了一系列的評價指標(biāo)，數(shù)值比較如表2。

表2 多種配時方案的數(shù)值比較

由表2可以看出，綜合網(wǎng)絡(luò)性能的各項(xiàng)指標(biāo)，PSO-GA模型的性能比其它模型更好。特別是周期時長，僅有112.6s，遠(yuǎn)低于其它配時方案。與現(xiàn)行方案相比，PSO-GA算法獲得的周期時長，平均車輛延遲顯著減少，其中周期時間減少達(dá)19.5%，平均時間延遲為14.5%，通行狀況明顯改善。與Webster相比，雖然通行能力在減少，但PSO-GA算法獲得的周期時間，平均延遲時間也減少了一定程度。此外，與GA相比，PSO-GA獲得的通行能力、周期時間和時間延遲均實(shí)現(xiàn)了一定程度的改善。雖然相比其它方案，停車次數(shù)有一定程度的增加，但所占的比例很小。因此，可以得出PSO-GA算法能夠?qū)崿F(xiàn)更好的性能，滿足交叉口配時的需要，并達(dá)到更好的效果，是解決交叉路口時序優(yōu)化問題一種行之有效的方法。

4.2 車流量對道路交通的影響

由于交通流對車輛行駛的重要影響，基于PSO-GA配時模型，運(yùn)用靈敏度分析討論車流量變化對于評估指標(biāo)的影響，由于交通容量的變化十分微小，所以不作具體分析，重點(diǎn)研究對平均時間延遲和停車次數(shù)的影響。

表3給出了交通流量增加和減少20%后平均延誤和停車次數(shù)的變化情況。(括號里為與原有方案相比變化的百分比)

表3 平均延誤和停車次數(shù)相對現(xiàn)狀的變化情況

從表3可以看出1.2Q(原車流量1.2倍)時車輛平均時延增長幅度顯著，高達(dá)89.36%。0.8Q(原車流量0.8倍)時，平均時間延遲和停車次數(shù)的減小幅度卻只有20%，這說明高流量狀況對道路交通有較大的影響。

上述分析表明，流量增加會加劇交通擁堵，降低車速，使平均時間延遲大幅增加；流量減少能使交通狀況有一定好轉(zhuǎn)，加快車速，平均時間延遲和停車次數(shù)也都發(fā)生一定程度的減少。綜上可知，應(yīng)合理控制交通網(wǎng)絡(luò)流量，避免產(chǎn)生過高流量，使車輛運(yùn)行狀況得到改善。

5 結(jié)論

本文介紹了一種基于PSO-GA的交叉路口信號配時優(yōu)化算法，它可以使得時間延遲更小，停車次數(shù)更少，流量更大。將Synchro交通仿真軟件與各種配時方案結(jié)合，幫助尋找交通信號配時優(yōu)化問題的最佳方案。結(jié)果表明，對于信號時序優(yōu)化問題，PSO-GA算法比現(xiàn)有配時方法、Webster模型和GA更具優(yōu)勢，可以有效地獲得最優(yōu)解，使交通狀況得到明顯的改善。這表明，PSO-GA算法在交通信號控制和優(yōu)化領(lǐng)域擁有廣泛的應(yīng)用前景和實(shí)用價值。文章的最后運(yùn)用靈敏度分析，討論了高低流量狀況對于車輛運(yùn)行指標(biāo)的影響。結(jié)果表明，高流量情境下，平均延誤時間增加多達(dá)89.36%。為此，應(yīng)嚴(yán)格控制過高流量情況的發(fā)生，這對于改善道路交通狀況具有重要意義。

對于交叉路口信號配時優(yōu)化的未來研究可能有以下幾個方向。首先，分析更多類型的信號時序交叉點(diǎn)，以測試本研究中提出的方法的適用性。其次，本文沒有考慮某些現(xiàn)實(shí)世界的約束和動態(tài)事件(如事故，緊急車輛，天氣情況等)。通過考慮這些現(xiàn)實(shí)因素，可將本文研究的理論應(yīng)用于特定的區(qū)域或城市交通網(wǎng)絡(luò)。最后，未來可以考慮能耗減少的目標(biāo)。目前能耗問題是運(yùn)輸中的熱門話題，而實(shí)際解決排放的文獻(xiàn)僅占很小一部分，這也是文章未來研究的重點(diǎn)。