基于黃金分割點遺傳算法的交通信號多目標(biāo)優(yōu)化

楊文臣,張 輪,饒 倩,張 孟

(同濟大學(xué)道路與交通工程教育部重點實驗室,上海201804)

基于黃金分割點遺傳算法的交通信號多目標(biāo)優(yōu)化

楊文臣,張 輪,饒 倩,張 孟

(同濟大學(xué)道路與交通工程教育部重點實驗室,上海201804)

針對遺傳算法求解交通信號配時模型容易陷入局部最優(yōu)的問題,提出一種基于黃金分割點遺傳算法的城市交通信號建模與優(yōu)化方法.該方法采用數(shù)值模擬分析各交通信號常用性能指標(biāo)間的相關(guān)性及其與配時參數(shù)間的關(guān)聯(lián)程度,選取延誤、停車率和通過量構(gòu)建相對評價指標(biāo)體系;并采用加權(quán)系數(shù)法建立交通信號多目標(biāo)配時模型;同時,設(shè)計一種基于黃金分割點的自適應(yīng)遺傳算法對交通信號配時模型進(jìn)行求解.該算法采用實數(shù)編碼,引入黃金分割點算子增強遺傳算法的局部搜索能力.以典型城市單交叉口進(jìn)行試驗,設(shè)計多種交通場景,在三種控制策略下采用數(shù)值計算和VISSIM仿真對提出的模型及算法進(jìn)行效用評價.結(jié)果表明,所設(shè)計的算法求解質(zhì)量好和計算效率高,提出的配時模型具有良好的控制效果.

智能交通;交通信號;相關(guān)性分析;配時模型;遺傳算法;黃金分割

1 引 言

Akcelik在Webster的交通信號配時F.B方法的基礎(chǔ)上引入停車補償系數(shù),建立考慮延誤和停車系數(shù)的雙目標(biāo)配時模型,用以評價信號配時方案優(yōu)劣,使基于多目標(biāo)優(yōu)化的交通信號自適應(yīng)控制得到國內(nèi)外學(xué)者的長期關(guān)注[1].從TRANSYT和SCOOT的綜合性能指標(biāo)的采用,到利用智能優(yōu)化算法實現(xiàn)延誤、排隊長度、通行能力等多目標(biāo)優(yōu)化,以Hong[2]、楊曉光[3]等為代表的眾多學(xué)者均在綜合考慮交通損失和交通效益的基礎(chǔ)上,建立模擬各交叉口交通控制狀況的多目標(biāo)數(shù)學(xué)模型,并用遺傳算法和蟻群等智能算法求解配時模型,進(jìn)而對路口進(jìn)行最優(yōu)控制,以解決信號配時實時優(yōu)化問題.

遺傳算法模擬生物進(jìn)化過程,從問題解的種群開始全局搜索,已被廣泛應(yīng)用于交通控制的多目標(biāo)函數(shù)優(yōu)化領(lǐng)域[4].但是,交通信號多目標(biāo)控制模型存在各類約束條件,傳統(tǒng)的遺傳算法在求解時優(yōu)化速度慢,易陷入局部最優(yōu),致使控制方案質(zhì)量低,特別在路口交通流量較高時更為明顯.為此,眾多學(xué)者設(shè)計模型中的約束條件和懲罰轉(zhuǎn)換規(guī)則,并引入模擬退火、蟻群覓食和粒子群捕食等仿生機理[5,6],改進(jìn)遺傳算子計算規(guī)則或是組合兩類算法,以提高遺傳算法的局部搜索能力.但是,改進(jìn)的混合遺傳算法結(jié)構(gòu)復(fù)雜、計算量大,導(dǎo)致算法效率低且可移植性差,難以滿足交通信號控制在線實時優(yōu)化的需求.

本文以典型城市單交叉口為研究對象,從配時建模優(yōu)化和遺傳算法改進(jìn)兩方面,提出一種基于黃金分割點遺傳算法的城市交通信號優(yōu)化控制方法.采用數(shù)值分析的方法,分析傳統(tǒng)交通信號控制性能指標(biāo)間的相關(guān)性,建立基于相對評價指標(biāo)的動態(tài)配時模型.為克服混合遺傳算法求解帶約束優(yōu)化問題時效率低的不足,引入黃金分割點算子,設(shè)計了基于黃金分割點的改進(jìn)自適應(yīng)實數(shù)編碼遺傳算法求解配時模型.最后,以典型城市單交叉口進(jìn)行實驗,基于實測的交通流數(shù)據(jù)采用三種控制策略進(jìn)行大量的數(shù)值計算,并采用VISSIM微觀交通仿真軟件對三種交通信號控制策略的控制效果進(jìn)行仿真,對模型及算法進(jìn)行效用評價.

2 交通信號多目標(biāo)配時優(yōu)化建模

2.1 性能指標(biāo)相關(guān)性分析

交通信號常用的評價指標(biāo)包括交叉口飽和度、延誤、排隊車輛數(shù)、停車次數(shù)和通行能力.對典型雙向六車道、采用標(biāo)準(zhǔn)四相位控制的城市單路口,采用數(shù)值模擬的方法,在不同的車流量到達(dá)水平下,估算不同配時方案下路口修正的webster平均延誤(avgDelay)、webster平均停車率(avgStopRate)和通過量(Capacity)的數(shù)值,計算結(jié)果如圖1示.

從圖1可以看出,平均延誤與通行量及平均停車率與通過量之間呈拋物線關(guān)系,平均停車率和延誤之間呈指數(shù)趨勢,這說明停車次數(shù)與通過量、延誤與通過量,以及停車率和延誤之間沒有顯著的正負(fù)相位性.這是因為信號周期小,車輛到達(dá)路口經(jīng)常停車排隊,延誤和停車次數(shù)增大,路口通行能力得不到充分利用,而在合理的周期范圍內(nèi),通過量增大,延誤和停車率也隨之增大.因而,相關(guān)性分析結(jié)果表明:在路口交通條件確定的前提下,存在一個合理的周期范圍,其使延誤和停車次數(shù)盡可能小,并保障路口一定的通過量.

實地調(diào)查分析典型路口的周期時長及其相關(guān)因素的關(guān)聯(lián)程度,國內(nèi)外研究發(fā)現(xiàn),通過量與周期時長的關(guān)聯(lián)度最大、排隊長度次之、延誤與停車率接近,且飽和度與通過量、停車率與排隊長度直接正相關(guān)[7,8].在確保交通安全的前提下,信號控制目標(biāo)在于最大限度提高道路通過量,并使交叉口延誤和停車次數(shù)盡可能小.因此,可以選取延誤、停車次數(shù)和通過量作為交通信號控制方案的性能評價指標(biāo).

圖1 停車次數(shù)、延誤、通過量之間的相關(guān)性分析Fig.1 Correlation analysis among stop times, delay and traffic capacity

2.2 基于相對指標(biāo)的交通信號配時建模

目前配時優(yōu)化研究中多采用延誤、停車率和通過量的絕對值,但各性能指標(biāo)的量級、量綱不同,導(dǎo)致各指標(biāo)權(quán)重模型的物理意義不明確,或因某個指標(biāo)的量級過大,多目標(biāo)優(yōu)化實質(zhì)上為單目標(biāo)優(yōu)化.為使目標(biāo)函數(shù)無量綱化和克服性能指標(biāo)的量級差異,以經(jīng)典F-B配時法的控制方案(TRRL)對應(yīng)的各性能指標(biāo)值為標(biāo)準(zhǔn)數(shù),基于相對指標(biāo)的動態(tài)配時模型為

式中 PI是綜合性能指標(biāo)值;gi、xi、li分別為相位i的綠燈時間、飽和度和損失時間;n為相位總數(shù); gmin和gmax為相位i的最小、最大綠燈時間;Cmin、Cmax為最小、最大周期;avgD、avgH和Q分別是交叉口修正的Webster平均延誤、Webster平均停車率和HCM2000通過量,并按式(2)計算;avgDTRRL、avgHTRRL和QTRRL分別是TRRL控制方案下對應(yīng)計算得到的交叉口修正Webster平均延誤、Webster平均停車率和HCM2000通過量.

式中 avgDi、avgHi和Qi分別是相位i修正的Webster延誤、Webster停車率和HCM2000通過量; Si、qi、yi、ui分別為相位i的飽和流量、到達(dá)車輛數(shù)、到達(dá)流率和綠信比.

k1、k2、k3分別是延誤、停車率和通過量的權(quán)值系數(shù),其隨交通需求的變化而自適應(yīng)調(diào)整,并按式(3)計算.

式中 Ui為指標(biāo)i的臨時權(quán)重;Y為交叉口總流率;權(quán)值修正系數(shù)X為交叉口總飽和度.k1、k2隨著交叉口流率比的增加而減小,k3隨交叉口流率比的增加而增加,從而使得控制目標(biāo)在路口閑散狀態(tài)下側(cè)重降低延誤;在順暢狀態(tài)下側(cè)重減少延誤和停車;而在繁忙和擁堵狀態(tài)下則著重提高通過量,實現(xiàn)不同交通狀態(tài)下交通控制策略的優(yōu)化,使路口管理效能最大.采用交叉口“流率—占有率”組合描述路口交通流不同強度狀態(tài)的論述詳見文獻(xiàn)[9].

3 基于黃金分割點的遺傳算法

3.1 黃金分割點的局部優(yōu)化

經(jīng)典黃金分割比例已經(jīng)被廣泛應(yīng)用于建筑、美學(xué)、音樂、工業(yè)設(shè)計等領(lǐng)域,近幾年,黃金比例也被應(yīng)用于復(fù)雜系統(tǒng)優(yōu)化問題并取得了良好的效果[10].當(dāng)遺傳算法進(jìn)化到一定階段,兩個局部最優(yōu)個體將趨同于解空間的同一個“凹處”.可以假設(shè),在兩個局部最優(yōu)個體的基因之間,存在潛在的更優(yōu)的基因位置.為此,引入黃金分割比例確定局部最優(yōu)點的搜索位置.如圖2所示,A和B為兩個相鄰的最優(yōu)個體,C為通過黃金比例得到的潛在最優(yōu)點的位置,AC和AB的關(guān)系滿足黃金分割點定義.

圖2 基于黃金分割比例計算局部最優(yōu)點示意Fig.2 The diagram of local minima calculation based on the golden ratio

為了拓展遺傳算法解集的局部搜索空間,如圖3所示,運用反向原理(將C的位置旋轉(zhuǎn)180°)生成反向黃金分割的局部最優(yōu)點C',其中C'C和C'B的關(guān)系滿足黃金分割定義.

圖3 基于反向原理計算反向黃金分割局部最優(yōu)點示意Fig.3 The diagram of reverse golden ratio-based local minima calculation

3.2 基于黃金分割點的混合遺傳算法

基于黃金分割點的混合遺傳算法(GRGA)以改進(jìn)實數(shù)編碼遺傳算法(SRGA)每一代的m個優(yōu)秀個體作為初始向量,引入黃金分割點產(chǎn)生新個體向量集,拓展遺傳算法解空間的搜索范圍,逼近更好的解集.算法流程如圖4所示,GRGA采用實數(shù)編碼生成初始種群,該種群滿足信控約束條件和個體間互不相同準(zhǔn)則;在算法控制參數(shù)中:種群規(guī)模取100,進(jìn)化代數(shù)Gen取100,局部尋優(yōu)規(guī)模m取10;個體適應(yīng)度值取PI值,且每個方案的PI值采用式(1)計算;交叉和變異的概率及操作算子隨當(dāng)前代數(shù)G及個體PI值的優(yōu)劣自適應(yīng)動態(tài)調(diào)整[9,11].

圖4 基于黃金分割點的混合遺傳算法流程Fig.4 The golden ratio-based hybrid genetic algorithm

為保持種群的多樣性,在SRGA算法的每一新生代中,挑選最好的30個個體構(gòu)成算法的子種群,并從子種群中隨機選取2 m個優(yōu)秀個體作為初始向量,調(diào)用黃金分割算子強化遺傳算法的局部尋優(yōu)搜索,具體步驟如下:

(1)由3.1節(jié)的黃金分割函數(shù)產(chǎn)生m個新個體向量;

(2)采用式(1)評估新個體向量集;

(3)采用Metropolis準(zhǔn)則概率選擇新個體,并用接收的優(yōu)秀個體依次替換SRGA新生代中最差的個體,個體接收概率P(X)按式(4)計算,為逼近最優(yōu)空間及加速收斂,P(X)隨進(jìn)化代數(shù)的增加而增大,即在進(jìn)化后期對局部尋優(yōu)的依懶度加大.式中 α為比例系數(shù),控制算法對進(jìn)化代數(shù)的依懶程度,研究取α=0.6.

4 模型驗證

4.1 實例描述

以佛山市三水區(qū)某典型十字路口作為模型和算法的驗證實例.路口道路交通組織和VISSIM仿真模型如圖5所示,該路口為主干道與次干道相交,平峰和高峰期間的流量差異明顯,采用三相位的兩時段定周期控制(平峰/高峰),且相位1和相位2之間無黃燈過渡.在平峰期間,南北主路左轉(zhuǎn)車流及東西支路的車流量小,而在高峰期間,路口周期達(dá)98 s,綠燈時間的浪費現(xiàn)象嚴(yán)重.

采用實地調(diào)查的平峰期(Non-peak)和高峰期(Peak-hour)的車流量(5min統(tǒng)計間隔)均值作為模擬交通場景的駛?cè)肓髁?平峰和高峰路口流量的流向圖如圖6所示.

4.2 仿真場景

(1)數(shù)值計算.

為驗證GRGA的效用,采用GRGA與基于模擬退火的混合實數(shù)編碼遺傳算法(HRGA)[9]分別求解平峰期和高峰期下的配時模型,計算機數(shù)值計算采用Visual C#編程.兩種優(yōu)化算法在兩種狀態(tài)下各進(jìn)行100次仿真計算.選取最優(yōu)、最差和平均適應(yīng)度、平均迭代次數(shù)、收斂次數(shù)、可行解/不可行解、優(yōu)化時間為遺傳算法性能評價指標(biāo),并對比分析GRGA、HRGA兩種算法的最佳配時方案及路口現(xiàn)行信號控制方案(ExpT)的控制性能.

(2)VISSIM仿真.

微觀交通仿真是評價信號控制策略的有效方法,采用微觀交通仿真軟件VISSIM4.30對實驗交叉口的基礎(chǔ)路網(wǎng)和交通控制設(shè)施進(jìn)行可視化建模,并設(shè)置仿真路網(wǎng)OD和統(tǒng)計分析參數(shù),對GRGA、HRGA和ExpT的方案進(jìn)行仿真.仿真場景設(shè)計如下:

①平峰/高峰的仿真時長均為1h,且為模擬路口短時車流到達(dá)的波動特性,在VISSIM Inputs的Time intervals文件中根據(jù)實地調(diào)查的結(jié)果設(shè)置1 h內(nèi)5 min間隔的車輛發(fā)車比例.

②根據(jù)國內(nèi)城市道路通行能力的設(shè)計規(guī)范,車頭時距、駕駛員反應(yīng)時間校準(zhǔn)為1.8 s和1.5 s.

③由于仿真效果受隨機種子影響,對每個控制方案批量仿真20次.選取平均延誤(Delay)、平均速度(Speed)、平均排隊長度(Queue)和平均停車時間(Stop Time)為VISSIM仿真的性能評價指標(biāo).

圖6 平峰(左)和高峰(右)的路口流量的流向圖Fig.6 The flow diagrams in the non-peak(Left)and peak period(Right)

4.3 結(jié)果分析

(1)GRGA的算法性能分析.

GRGA算法性能指標(biāo)的統(tǒng)計結(jié)果如表1所示:在100次獨立運行中,GRGA均可得到可行解,而且在最好解、平均迭代次數(shù)和優(yōu)化時間等指標(biāo)方面均優(yōu)于HRGA,說明對本文的單路口控制實例,設(shè)計的黃金分割局部搜索具有好的應(yīng)用效果.尤其優(yōu)化時間得到大幅縮短,更好滿足控制系統(tǒng)實時性需求,這是因為相比模擬退火算子,采用黃金分割局部搜索算子的計算量小.

表1 GRGA和HRGA兩種算法100次數(shù)值計算的統(tǒng)計結(jié)果Table 1 Statistical results for 100 calculations with GRGA and HRGA

(2)控制方法的控制效能分析.

GRGA、HRGA的最佳配時方案及ExpT方案的數(shù)值計算和VISSIM仿真的統(tǒng)計結(jié)果分別如表2和圖7所示:在平峰和高峰期間,GRGA算法與各狀態(tài)下制定的控制目標(biāo)一致,在平峰狀態(tài)下能大幅減小延誤和減小停車次數(shù),而在高峰狀態(tài)下在減小延誤和停車次數(shù)同時,大幅度增加路口通過車輛數(shù),仍能獲得穩(wěn)定的控制性能.以GRGA和ExpT的仿真結(jié)果對比為例,在平峰和高峰交通狀態(tài)下, GRGA在車輛延誤、路口行車速度等指標(biāo)上均得到了明顯改善,約有15%-33%的改進(jìn),大大提升了路口的運營效能.

表2 GRGA、HRGA和ExpT的性能指標(biāo)計算結(jié)果Table 2 The calculation result of the GRGA,HRGA and ExpT

圖7 GRGA、HRGA和ExpT方案性能指標(biāo)的VISSIM仿真統(tǒng)計結(jié)果Fig.7 VISSIM simulation results of the GRGA,HRGA and ExpT

5 研究結(jié)論

本文提出了一種基于黃金分割點遺傳算法的城市交通信號優(yōu)化控制方法,其采用數(shù)值方法模擬交通信號常用性能指標(biāo),分析了指標(biāo)間的相關(guān)性及其與配時參數(shù)的關(guān)聯(lián)程度,并綜合考慮控制效率和效益,構(gòu)建了基于相對性能指標(biāo)的交通信號多目標(biāo)動態(tài)配時模型,提出一種基于黃金分割點的自適應(yīng)遺傳算法,為單交叉口交通信號實時優(yōu)化控制提供了一種解決方案.以典型的實證路口進(jìn)行試驗,在實地的平峰和高峰交通場景下,采用三種控制策略對路口進(jìn)行大量的數(shù)值計算和VISSIM仿真.與HRGA等控制方法相比,分析結(jié)果表明:在算法性能方面,通過引進(jìn)黃金分割局部搜索機制,改進(jìn)的遺傳算法求解質(zhì)量好、計算效率高;在控制效果方面,能有效降低路口延誤和停車次數(shù),并提高行車速度,與實際的交通管理目標(biāo)吻合.

[1] 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:Emerging Technologies,2008,16(4):454-470.

[2] Hong L.Traffic adaptive control for oversaturated isolated intersections:Modeldevelopmentandsimulation testing[J].Journal of Transportation Engineering, 2004,130(5):594-601.

[3] 馬瑩瑩,楊曉光,曾瀅.信號控制交叉口周期時長多目標(biāo)優(yōu)化模型及求解[J].同濟大學(xué)學(xué)報:自然科學(xué)版,2009,37(6):761-765.[MA Y Y,YANG X G, ZENG Y.Multi-objective cycle length optimization model and solution[J].Journal of Tongji University (Natural Science),2009,37(6):761-765.]

[4] Michalewicz Z.A survey of constraint handling techniques in evolutionary computation methods[C].Proceeding ofthe4thAnnualConferenceonEvolutionary Programming,1995:135-155.

[5] Teklu F,Sumalee A,Watling D.A genetic algorithm approachforoptimizingtrafficcontrolsignals considering routing[J].Computer-Aided Civil and Infrastructure Engineering,2007,22(1):31-43.

[6] Ceylan H,Bell M G H.Traffic signal timing optimization basedongeneticalgorithmapproach,including drivers'routing[J].Transportation Research Part B: Methodological,2004,38(4):329-342.

[7] 楊錦冬,楊東援.城市信號控制交叉口信號周期時長優(yōu)化模型[J].同濟大學(xué)學(xué)報,2001,29(7): 789-794.[YANG J D,YANG D Y.Optimized signal time model in signaled intersection[J].Journal of Tongji University,2001,29(7):789-794.]

[8] Anderson J,Sayers T,Bell M.The objectives of traffic signal control[J].Traffic Engineering&Control, 1998,39(3):167-170.

[9] 何兆成,楊文臣,梁詩,等城市單交叉路口交通信號實時優(yōu)化控制與仿真[J].計算機工程與應(yīng)用, 2010,46(33):239-243.[HE Z C,YANG W C, LIANG S,et al.Study of real-time traffic signal optimized control and simulation for urban isolated intersection[J].ComputerEngineeringand Applications,2010,46(33):239-243.]

[10] Sun Y X,Van B J,Wang Z H.A new golden ratio local search based particle swarm optimization[C].2012 International Conference on Systems and Informatics (ICSAI),2012:754-757.

[11] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on System,Man and Cybernetics,1994, 24(4): 656-667.

Multi-objective Optimization for Traffic Signals
with Golden Ratio Based Genetic Algorithm

YANG Wen-chen,ZHANG Lun,RAO Qian,ZHANG Meng
(Key Laboratory of Road and Traffic Engineering,Ministry of Education,Tongji University,Shanghai 201804,China)

Aiming at the problems of the local optimum of the genetic algorithm in solving traffic signal timing models,this paper presents an optimized traffic signal controller with a golden ratio-based genetic algorithm(TSCGRGA)for urban signalized intersections.This controller employs numerical simulation to analyze the correlation between the traditional performance indicators of traffic signal benefit and their correlation degree with timing parameters,select time delays,stop rate and throughput to establish relative evaluation indices of traffic signals,and a multi-objective timing model of traffic signals is developed by weighted coefficient method.Then,an adaptive golden ratio-based genetic algorithm is presented to solve the optimized models,which uses real number encoding,and introduces golden ratio calculator to enhance the local optimal capability of genetic algorithm.Experiments are conducted on a typical urban isolated intersection and the performance of the developed model and algorithm is validated by comparison with those of fixed-time,actuated,and simple real-coded genetic algorithm-based controllers for different trafficconditions.Extensive numerical circulation and VISSIM simulation results have demonstrated the potential of the developed algorithm in the quality of solutions and time efficiency,and indicated that the signal strategies derived from TSCGRGA have better performance.

intelligent transportation;traffic signal;correlation analysis;timing model;genetic algorithm;golden ratio

U491.51,TP391.9

: A

U491.51;TP391.9

A

1009-6744(2013)05-0048-08

2013-04-02

2013-05-14錄用日期:2013-06-13

國家自然科學(xué)基金資助(No.50408034).

楊文臣(1985-),男,云南昌寧人,博士生.

*通訊作者:Lun_zhang@#edu.cn