基于約束粒子群算法的交叉口定周期信號配時

段鵬飛

(蚌埠汽車士官學(xué)校 裝備保障系，安徽 蚌埠233011)

道路交叉口的信號控制涉及包括機動車、人和環(huán)境在內(nèi)的多種影響因素，如何更全面地協(xié)調(diào)控制多個目標(biāo)，使其綜合效益最優(yōu)成為廣大學(xué)者研究的重點。文獻(xiàn)［1—5］分別采用蟻群算法、遺傳算法、強化學(xué)習(xí)法、免疫遺傳算法等優(yōu)化方法對交叉口的周期信號進行了優(yōu)化，都反映了各自算法的優(yōu)越性。然而這些研究雖然滿足了基本控制需求，卻無法獲得最優(yōu)的多相位配時方案。因此，針對定周期時長條件下的相位配時優(yōu)化進行研究非常必要。文獻(xiàn)［6—7］分別利用相容優(yōu)化算法和模式搜索算法研究了定周期時長情況下不同相位綠燈時間的優(yōu)化，取得了良好的效果，并與經(jīng)典的Webster 算法進行了比較，然而這些算法的收斂速度不高，仍有待做進一步改善。本文在此基礎(chǔ)上，將粒子群算法引入到定周期信號控制優(yōu)化中，并結(jié)合實際應(yīng)用中存在的約束條件限制和算法易陷入局部最優(yōu)解問題，對算法進行了改進，以單交叉口機動車延誤、行人延誤和停車率綜合最小為優(yōu)化目標(biāo)進行了優(yōu)化，達(dá)到了很好的收斂效果。

1 系統(tǒng)模型

以機動車流為控制對象，從機動車效益、人的效益和環(huán)境效益3 個方面考慮，選取機動車車均延誤、行人人均延誤以及機動車平均停車率三者綜合最小為優(yōu)化目標(biāo)，建立單交叉口信號控制多目標(biāo)優(yōu)化模型如下:

式中:ge=［ge1，ge2，…，gen］，gei為第i相位的有效綠燈時間;C為周期總時長;l為周期損失時間;fp(ge)，p=1，2，3 為第p個優(yōu)化目標(biāo)函數(shù)，這里分別代表機動車平均延誤函數(shù)、行人平均延誤函數(shù)和平均停車率函數(shù);λi為第i相位的綠信比;xij為第i相位第j進口道的車流飽和度;β為規(guī)定的交叉口最大車流飽和度。

機動車平均延誤采用Webster 經(jīng)典延誤模型，延誤時間由機動車流在非飽和狀態(tài)下的穩(wěn)態(tài)均勻到達(dá)延誤和隨機延誤2 部分組成，其計算公式為

式中:第1 部分為交通流均勻到達(dá)的一致延誤，s/pcu;第2 部分為車輛隨機到達(dá)并引起超飽和周期所產(chǎn)生的附加延誤，s/pcu;qij為第i相位第j進口道的車流量，pcu/h。

則其機動車平均延誤時間優(yōu)化目標(biāo)函數(shù)為

在假定交叉口行人均勻到達(dá)，且每個信號周期綠燈信號均能保證所有等待的行人通過，不存在跨周期滯留現(xiàn)象的前提下，建立行人延誤模型:

式中Ri為第i行人相位的紅燈等待時間。

不考慮不完全停車的情形，在均勻到達(dá)情況下，一個周期內(nèi)交叉口進口道機動車流的平均停車率可以按照Webster 的計算方法建立模型［8］。模型表達(dá)式為

式中Sij為第i相位第j進口道的設(shè)計飽和流量，pcu/h。

則平均停車率優(yōu)化目標(biāo)函數(shù)可表示為

本文重點針對固定周期時長的信號配時進行研究，因此在優(yōu)化過程中，一個周期內(nèi)各相位總的有效綠燈時間應(yīng)該滿足:

即該優(yōu)化問題事實上是帶有約束條件的多目標(biāo)優(yōu)化問題，與一般的無約束條件優(yōu)化相比，該類問題在模型求解過程中需要考慮約束條件的限制。

2 模型求解

2.1 約束優(yōu)化問題求解

本文所研究的是一種帶有約束條件的多目標(biāo)優(yōu)化問題，一個約束優(yōu)化問題通?？梢员硎緸?/p>

式中:X={x1，x2，…，xn}∈F?S?Rn為優(yōu)化控制變量，集合S?Rn為問題的搜索空間;F為搜索空間中的可行域，即滿足約束條件的解所構(gòu)成的空間;X的每維向量取值于區(qū)間［ai，bi］，i=1，2，…，n;F(X)為目標(biāo)函數(shù);gk(X)≤0 和hk(X)=0 分別為約束優(yōu)化問題的不等式約束和等式約束。

目前，針對約束優(yōu)化問題的求解算法主要分為精確算法和現(xiàn)代啟發(fā)式算法2 種，前者通常需要目標(biāo)函數(shù)具有良好的性質(zhì)，如連續(xù)、可微等。而現(xiàn)代啟發(fā)式算法在求解一般約束問題時，不需要借助目標(biāo)函數(shù)的這些性質(zhì)條件限制。粒子群算法(particle swarm optimization，PSO)作為一種基于群體的進化算法，與其他啟發(fā)式算法相比，被證明是一種極具競爭力的求解算法。為了利用該算法收斂速度快的特點，將其引入以解決交叉口相位配時優(yōu)化問題。

2.2 帶雜交算子的粒子群算法

在標(biāo)準(zhǔn)的PSO 中，問題的每個解均可以看作是搜索空間中的一個粒子，所有粒子都有一個由優(yōu)化目標(biāo)函數(shù)決定的適應(yīng)度值，此外每個粒子還有一個速度決定他們下一步所要移動的方向和距離。所有粒子根據(jù)個體和全體的飛行經(jīng)驗綜合分析動態(tài)調(diào)整自身速度，以完成在解空間的迭代搜索，直到找到最優(yōu)解。每一次迭代過程中粒子的更新方程［9］為

式中:wt為前一代速度對當(dāng)前速度的影響權(quán)重和分別為第i個粒子在第t次迭代中第j維的速度和位置，二者均有一定的范圍限制;c1和c2為2個加速因子，他們是粒子飛向全局和局部最好位置的速度權(quán)重;r1和r2為2 個介于［0，1］之間的隨機數(shù)分別為粒子的個體極值和全體極值。

標(biāo)準(zhǔn)的PSO 收斂速度較快，但與其他進化算法一樣易于陷入局部最優(yōu)的缺陷。為了有效避免這種收斂早熟，借鑒遺傳算法中雜交操作思想，通過在算法中引入一個雜交算子，使粒子獲得新的基因，來保持粒子群多樣性，從而使算法搜索到解空間中更大的范圍，減少了算法陷入局部極值的可能性［9］。但是，其沒有考慮當(dāng)前最優(yōu)解參與雜交時會使最優(yōu)粒子受到破壞的情況，因此，為了保持最優(yōu)解的完整性，對其做進一步改進，規(guī)定當(dāng)代最優(yōu)粒子不參與雜交。具體操作中，以雜交概率ps(0 ＜ps＜1)選取一定數(shù)目粒子兩兩參與雜交。設(shè)為T代參與雜交的2 個粒子，p0為雜交因子，則雜交操作計算公式為

2.3 約束處理機制

標(biāo)準(zhǔn)的粒子群算法針對的是無約束條件優(yōu)化問題的求解，本文采用一種廣泛應(yīng)用于處理該類問題的基于懲罰函數(shù)的約束粒子群算法，有效解決了模型求解中的實際問題。

定義處在可行域F內(nèi)的粒子為可行粒子，反之處在非可行域S-F內(nèi)的粒子稱為非可行粒子。為了消除非可行粒子對算法搜索最優(yōu)解的干擾，對這些粒子對應(yīng)的適應(yīng)度值添加懲罰函數(shù)。以最小化目標(biāo)函數(shù)為例，對其增加一個懲罰值，使得這些非可行粒子的適應(yīng)度函數(shù)遠(yuǎn)離最優(yōu)解搜索區(qū)域。

這里給出的約束優(yōu)化問題的PSO 中，對于可行粒子保持其適應(yīng)度函數(shù)值不變，而對于非可行粒子通過下面的目標(biāo)函數(shù)f(X)來評價其適應(yīng)度［10］:

式中:fk(X)為非可行粒子對第k約束的約束違背測 度φ(X，t)為在算法執(zhí)行的t代對于非可行粒子的附加啟發(fā)值

3 信號配時優(yōu)化算法

以交叉口各相位、各進口道的機動車平均延誤時間、行人平均延誤時間和平均停車率的歸一化加權(quán)和為目標(biāo)函數(shù)，以n個相位的有效綠燈時間ge1，ge2，…，gen為優(yōu)化變量(gei∈［T］，［T］為各相位有效綠燈時間的取值范圍)，給出的粒子群算法優(yōu)化步驟簡單概括如下:

步驟1:根據(jù)約束條件確定n個參數(shù)的取值范圍以及PSO 的控制參數(shù)vmax后，在參數(shù)范圍內(nèi)初始化一群粒子，即隨機產(chǎn)生位置x1和速度v1。

步驟2:在第t次迭代時，根據(jù)產(chǎn)生的新位置xt和速度vt，確定每個粒子的適應(yīng)度值Jt。

步驟3:找出所有可行粒子，求出其中最差的粒子，即適應(yīng)度函數(shù)值最大的粒子。對剩余的非可行粒子按照式(11)加上對應(yīng)的懲罰函數(shù)。

步驟4:對每個粒子計算其個體極值pbestt和全體極值gbestt，更新粒子當(dāng)前最優(yōu)解和對應(yīng)位置數(shù)組:如果Jt＞pbestt，則pbestt=Jt，Pt=xt;如果Jt＞gbestt，則gbestt=Jt，Pg=xt，P為粒子的位置。

步驟5:利用式(9)更新粒子的速度與位置，這里c1，c2為［0，2.5］中的隨機數(shù)。

步驟6:保持當(dāng)前最優(yōu)粒子位置不變，以雜交概率ps選擇一定數(shù)量的粒子按式(10)進行兩兩雜交。

步驟7:若未達(dá)到預(yù)設(shè)的迭代終止條件，返回步驟2。

4 仿真實例

以典型的單交叉口四相位信號控制為例進行問題研究，假設(shè)有東、西、南、北4 個車流入口，每個方向有左轉(zhuǎn)、直行和右轉(zhuǎn)3 個車道，東西直行和右轉(zhuǎn)車輛在相位1 中放行，東西左轉(zhuǎn)車輛在相位2中放行，南北直行和右轉(zhuǎn)車輛在相位3 中放行，南北左轉(zhuǎn)車輛在相位4 中放行。假設(shè)該交叉口的車流有關(guān)數(shù)據(jù)見表1。

表1 某交叉口機動車流量統(tǒng)計 pcu/h

4.1 優(yōu)化目標(biāo)有效性仿真

針對多目標(biāo)優(yōu)化問題，合理的優(yōu)化目標(biāo)選取對于問題研究具有重要意義，如果選擇的是呈線性關(guān)系的一組目標(biāo)，則二者不能同時作為僅有的目標(biāo)函數(shù)出現(xiàn)。道路交叉口的信號配時涉及到包括機動車、行人和環(huán)境在內(nèi)的諸多因素，在實際優(yōu)化模型建立中選擇合理的多個目標(biāo)是有效求解該類問題的重要前提。

圖1—3 為選取的3 個優(yōu)化目標(biāo)在解空間中的關(guān)系曲線。從圖中可以看出，在假定車輛均勻到達(dá)且交叉口處于非飽和狀態(tài)條件下，機動車平均延誤與行人平均延誤之間呈線性關(guān)系，為非沖突目標(biāo);機動車平均延誤與平均停車率、行人平均延誤與平均停車率之間均為相互沖突的關(guān)系。因此，后兩組之間為有效的優(yōu)化控制目標(biāo)。

4.2 配時算法性能仿真

圖1 機動車平均延誤與行人平均延誤的關(guān)系

圖2 機動車平均延誤與平均停車率的關(guān)系

圖3 行人平均延誤與平均停車率的關(guān)系

假設(shè)交叉口信號周期C為130 s，總的損失時間l為10 s，各進口道車流量見表1，各相位最小綠燈時間為10 s，各相位各進口道的最大車流飽和度β為0.9。同時，設(shè)定最大粒子種群規(guī)模Ν=80，加速因子c1=c2=2，采用文中給出的粒子群優(yōu)化算法，計算得到交叉口4 個相位有效綠燈時間分別為ge1=45.63 s;ge2=22 s;ge3=36.36 s;ge4=17 s。

文中算法與經(jīng)典Webster 算法以及模式搜索算法的優(yōu)化結(jié)果比較見表2?？梢钥闯?，在等周期時長條件下，文中給出的算法優(yōu)化得到的機動車平均延誤和平均停車率均明顯優(yōu)于Webster 算法，同時與模式搜索算法差別不大。而在行人平均延誤方面，文中算法較其他2 種算法差別均小于1 s。

表2 3 種算法優(yōu)化結(jié)果比較

優(yōu)化粒子群算法與傳統(tǒng)的標(biāo)準(zhǔn)粒子群算法以及模式搜索算法的性能比較如圖4 所示。

圖4 優(yōu)化粒子群算法性能比較

從圖中可以看出，粒子群算法收斂速度明顯優(yōu)于模式搜索算法，這主要得益于該算法是一種基于群體的進化算法，具備優(yōu)秀的尋優(yōu)能力。同時，帶改進雜交算子的粒子群算法較標(biāo)準(zhǔn)的粒子群算法性能有所提升，這主要是因為引入改進雜交算子后，在保持當(dāng)前最優(yōu)解完整性的同時，提高了算法對全局最優(yōu)解的搜索能力。因此，優(yōu)化粒子群算法在優(yōu)化結(jié)果與傳統(tǒng)算法差別不大的情況下，收斂速度得到了明顯提升。

不同的周期時長情況下，機動車平均延誤和行人平均延誤優(yōu)化結(jié)果的變化趨勢如圖5 所示。

圖5 不同周期時長條件下優(yōu)化結(jié)果

從圖中可以看出，隨著周期時長的增加，機動車和行人通過交叉口的平均延誤都相應(yīng)線性增加，且機動車延誤對周期時長的靈敏性要大于行人延誤對周期時長的靈敏性。這主要是因為，隨著周期總時長的增加，各相位綠燈時間也相應(yīng)增加，導(dǎo)致機動車和行人的排隊時間相應(yīng)增加。因此，在實際的道路交叉口信號控制中，應(yīng)綜合考慮各種因素，使綜合效益達(dá)到最優(yōu)。

5 結(jié) 語

本文在傳統(tǒng)粒子群算法的基礎(chǔ)上，針對交叉口定周期信號相位配時中存在的傳統(tǒng)算法收斂速度較慢以及約束條件限制等問題，通過引入雜交算子，采用基于懲罰函數(shù)的約束粒子群算法，使得旨在處理無約束優(yōu)化問題的高效粒子群進化算法有效解決了交叉口定周期信號多相位配時問題，仿真結(jié)果證明了給出算法的有效性。由于道路交叉口的交通控制涉及到機動車延誤、燃油消耗率、停車率、排隊長度、行人延誤以及汽車尾氣排放、噪音污染等諸多效益指標(biāo)，本文僅以其中部分因素為優(yōu)化目標(biāo)，還不能全面反應(yīng)優(yōu)化控制需求，下一步可對于更全面的優(yōu)化目標(biāo)進行分析研究。

［1］ 馬瑩瑩，楊曉光，曾瀅. 信號控制交叉口周期時長多目標(biāo)優(yōu)化模型及求解［J］. 同濟大學(xué)學(xué)報:自然科學(xué)版，2009，37(6):761-765.

［2］ Schmocker J D，Ahuja S，Bell M G H. Multi-objective signal control of urban junctions-framework and a london case study［J］. Transportation Research Part C，2008，16(4):454-470.

［3］ 萬偉，陳峰.基于遺傳算法的單交叉口信號優(yōu)化控制［J］.計算機工程，2007，33(16):217-219.

［4］ 溫凱歌，楊照輝. 基于CMAC 強化學(xué)習(xí)的交叉口信號控制［J］.計算機工程，2011，37(17):152-154.

［5］ 顧榕，曹立明，王小平. 免疫遺傳算法在在交叉口信號配時中的應(yīng)用［J］. 同濟大學(xué)學(xué)報:自然科學(xué)版，2007，35(2):208-212.

［6］ 高云峰，徐立鴻，胡華，等.交叉口定周期信號控制多目標(biāo)優(yōu)化方法［J］.中國公路學(xué)報，2011，24(5):82-87.

［7］ 劉爽，岳芳，郭彥東，等.基于模式搜索算法的交叉口信號配時優(yōu)化研究［J］.交通運輸系統(tǒng)工程與信息，2011，11(1):29-35.

［8］ 全永燊.城市交通控制［M］.北京:人民交通出版社，1989.

［9］ 黃友銳.智能優(yōu)化算法及其應(yīng)用［M］. 北京:國防工業(yè)出版社，2008.

［10］ 李相勇，田澎，孔民.解約束優(yōu)化問題的新粒子群算法［J］.系統(tǒng)管理學(xué)報，2007，16(2):120-129.