基于多種群協同進化算法的混合交通流信號優化

陳 娟,荊 昊,方宇杰

(上海大學悉尼工商學院,上海201800)

在我國,由機動車、非機動車、行人形成的混合交通流,是造成交叉口交通擁堵的主要原因之一.研究混合交通流的實時變化性,設計出適合我國混合交通流的優化目標和優化控制方法,對解決我國城市交通擁擠問題有非常重要的現實意義.

隨著交通擁堵問題的日益嚴重,學者們意識到了混合交通流的復雜性,在混合交通流模型方面進行了相關研究.Xie等[1]在Nakayama等[2]的2維最優速度模型的基礎上,提出了一種2維跟車模型,用于描述包括機動車和非機動車的混合交通流的特征;Mu等[3]利用元胞自動機模型,對傳統汽車和微型汽車組成的混合交通流進行了分析;Luo等[4]研究由不同類型的車輛組成的混合交通流的操作特性,設計了元胞自動機模型,以描述雙向道路上的物理特性和不同車型的機械特征;Li等[5]利用元胞自動機建立了交通流模型,研究了在不同延遲概率下混合車流的車輛間隙分布,以及給定車輛密度的不同混合率.以上研究都只對機動車和非機動車進行研究,并未考慮行人的影響.Sharma等[6]指出,人為因素在理解交通流動態以及對混合交通流的有效操作和控制方面起著關鍵作用,并研究了行人在混合交通流中的作用,但該研究只是從行人的角度出發進行研究,并未綜合考慮機動車、非機動車、行人三者之間產生的共同影響.

由于實際交通系統具有動態性、非線性、模糊性等特點,相比定時控制和感應控制,智能控制能表現出更好的效果[7].交叉口智能信號控制方法主要包括專家系統、模糊控制、人工神經網絡和進化算法等.但是,模糊控制中模糊規則及隸屬度函數選擇的難度較大;而人工神經網絡需要大量的訓練及測試數據,且訓練時間長.

混合交通流環境下的信號配時問題,是一個典型的動態、高維、多目標優化問題.進化算法計算速度較快,能較好地保留解的多樣性,在該領域得到了廣泛的應用.王磊等[8]將總延誤時間、總停車次數、總通行能力這3個指標作為優化的對象,將多目標優化問題轉換為單目標優化問題,采用單目標方法進行求解,從而使得部分指標實現局部最優,但無法得到在所有目標上同時達到最優的信號配時方案;Shou等[9]建立了非飽和交叉口信號控制多目標動態決策模型,對信號周期時長、綠信比和相序3個信號配時參數同時進行優化,并應用混合遺傳算法求解最優決策變量;吳金順[10]綜合考慮信號交叉口通行能力最大、車輛平均延誤最小、交叉口停車次數最小這3個指標,建立了一個多目標信號配時模型,采用遺傳算法求解在該模型下的最優綠燈配時方案,并與經典Webster模型及不考慮平穩性的基礎模型進行比較,結果表明該模型的平均延時略長于Webster延誤模型,但平均停車次數和流量均優于Webster.陳娟等[11]提出了一種基于迭代預測非支配排序遺傳算法(iterative predictive nondominated sorting genetic algorithm-Ⅱ,IPNSGA-Ⅱ)的多目標相容控制方法,用于處理在過飽和狀態下相鄰交叉口的信號控制問題,提出的相容控制算法具有魯棒性、實時性、動態性的特點,能較好地處理有沖突的多目標控制問題,但模型僅考慮了機動車效益指標,沒有同時優化非機動車和行人的通行效益;沈峰等[12]將交通流模型嵌入到多目標優化算法中,替代以往傳統的目標函數,直接采用靜態多目標優化算法NSGA-Ⅱ進行求解,解決信號配時問題,但該算法并沒有考慮在動態需求環境下NSGA-Ⅱ算法收斂速度變慢的問題.

目前,有關在混合交通流環境下信號配時問題的研究主要存在如下問題:①在模型研究方面,綜合考慮機動車、非機動車、行人三者產生共同影響的模型的相關研究較少,尤其是在非機動車和行人方面的研究更少;②在考慮多目標優化性能指標方面,絕大多數的研究僅考慮機動車性能指標,較少考慮機動車、非機動車和行人的綜合性能指標;③在解決方法方面,雖然大多數的研究考慮了多個性能指標,但是采用的解決方法,不是把多個目標進行加權,轉化為單目標問題進行求解,就是采用靜態多目標優化算法來解決多目標優化問題,而這些方法都只考慮2個性能指標,很少涉及3個及3個以上的目標.而NSGA-II算法在解決高維多目標優化問題的時候,計算效率低,收斂速度慢.

在混合交通流下的信號配時問題,其本質是一個非常典型的動態、高維、多目標優化問題,因此無論是采用單目標優化方法,還是采用常規的靜態多目標優化算法,都不能得到滿意的效果.

針對以上問題,本工作根據機動車、非機動車、行人延誤時間這3個目標,建立了相鄰交叉口動態多目標優化配時模型,并且提出了基于多種群協同進化的動態多目標優化算法(multipopulation coevolutionary dynamic-multi-objective genetic algorithm,MPCED-MOGA),對在混合交通流環境下信號配時多目標優化問題進行求解,并在測試函數和仿真環境下進行了驗證.

1 多種群動態多目標進化算法

多種群方法屬于協同進化理論.協同進化算法分為3種:基于種群間競爭機制的協同進化算法、基于種群捕食機制的協同進化算法和基于種群共生機制的協同進化算法.

1.1 多種群協同進化方式

本工作提出的多種群協同進化算法包含2個種群,即搜索種群和跟蹤種群.搜索種群用來尋優,且只在環境發生顯著變化時進行目標函數重估.跟蹤種群跟蹤環境變化,且隨環境變化目標函數不斷進行更新.在進化過程中,跟蹤種群不斷把收斂到的較優解分享給搜索種群.圖1給出了2個種群間的工作機制.

圖1 2個種群間的工作機制Fig.1 Working mechanism between two populations

圖1中,Qs、Qf分別為搜索種群和跟蹤種群,種群規模為pops、popf,種群規模一般設定pops:popf=2∶1.隨著時間的推進,跟蹤種群不斷更新自身的適應度值;只有當環境變化檢測因子檢測到環境發生顯著變化時,Qs才進行目標函數的更新.2個種群的交互機制如下:當進化過程處于2次環境變化之間時,跟蹤種群不斷把自身的最優解分享到搜索種群中,以增加Qs最優解的質量.如當時間t∈(t0,t1),Qf分享r·popf的個體到Qs中(r為交互比例,本工作設r=0.5).當t=t1時,環境變化檢測因子檢測到了環境的變化,算法儲存此時的Qs解,作為時間t∈t0算法輸出的最優解,同時把Qf中的所有解作為Qs在t∈t1時的初始解.隨著時間不斷的推進,2個種群按上述機制不斷進行更新.

1.2 多種群協同進化過程

通常,任何靜態多目標算法加上動態多目標協同進化機制都可以解決動態多目標優化問題.本工作提出的MPCED-MOGA算法步驟如下.

步驟1初始化搜索種群和跟蹤種群,種群規模分別為pops、popf;進化代數gen=1;環境變化參數為nt,τt;環境變化閾值為δ;最大環境變化次數為Timemax;初始化搜索種群和跟蹤種群的時間參數為ts和tf,且ts=tf=0.

步驟2分別對2個種群進行遺傳、變異操作,并從跟蹤種群中選出r·popf個體加入搜索種群中,對2個種群進行非劣排序后更新.

步驟3如果Time=Timemax,則輸出搜索種群中每個環境狀態下的最優Pareto最優解為,結束;否則,轉步驟4.

步驟4令tf=tf+1/(ntτt),重估跟蹤種群的目標函數值.

步驟5在gen為τt的整數倍數的情況下,根據環境變化檢測因子判斷環境是否發生變化.如果沒有發生變化,則轉入步驟2;如果發生了變化,則記錄下搜索種群中當前最優解,令Time=Time+1,,轉入步驟6.

步驟6對跟蹤種群進行交叉變異,得到pops規模的種群對搜索種群實現完全替代,轉入步驟2.

圖2給出了MPCDE-MOGA算法的流程圖.

圖2 MPCDE-MOGA算法流程圖Fig.2 MPCDE-MOGA algorithm flow chart

2 信號配時多目標優化模型

本工作對共信號周期時長、綠信比和相位差進行了優化.優化的性能指標有機動車延誤、非機動車延誤和行人過街等待時間.

2.1 機動車延誤

結合圖1,在相鄰交叉口協調控制中,機動車延誤分為外部進口道延誤與內部進口道延誤[13].外部進口道延誤公式參照《道路通行能力手冊》[14]:

式中:d為交叉口每輛車平均信號控制延誤;d1為車輛在均勻到達時的信號控制延誤;d2為車輛隨機到達并引起超飽和情形所產生的附加延誤;d3為初始排隊附加延誤,即在車輛延誤計算初期,因上一時段留下積余車輛而使后續車輛產生的附加延誤.

本工作采用陳小紅[13]提出的模型進行內部進口道延誤的計算.車流在駛入下游交叉口時遇紅燈受阻,此時分2種情況:①車隊頭車到達下游交叉口時遇紅燈受阻,稱為車隊頭車受阻;②車隊頭車到達下游交叉口時遇綠燈,由于交叉口信號切換為紅燈,使得車隊后部車輛交通流受阻,故稱為非頭車受阻.

(1)車隊頭車受阻機動車延誤.

不考慮下游交叉口積余車輛的影響,如果車隊頭車在兩交叉口a、b間的行程時間大于相位差與綠燈之和,說明在車隊頭車到達下游交叉口時,信號綠燈時間已結束,車隊需排隊等待.此時車隊頭車受阻,根據車隊到達規律,延誤計算為

(2)車隊非頭車受阻機動車延誤.

當車隊頭車在兩交叉口間的巡航時間小于相位差與綠燈時長之和,且大于相位差時長時,車隊頭車到達下游交叉口時信號燈為綠,此時車隊頭車可順利通過交叉口,但車隊非頭車部分可能受阻.根據車隊到達規律,其車輛延誤為

2.2 非機動車延誤

設qb為下游交叉口的自行車到達流量;為信號紅燈時間;為信號綠燈時間.當下游交叉口綠燈亮起后,車輛以飽和流量駛離交叉口.由于啟動波的影響,仍有車輛在隊尾繼續停下來等待通行,經過M秒啟動波追上停車波,之后綠燈時期到達的N輛車輛連續通過交叉口.根據交叉口駛入與駛離的車輛數相等的原理,可得非機動車延誤db[13]:

2.3 行人過街等待時間

本工作假設交叉口行人的到達是均勻的,則行人的平均等待時間僅與其所用信號燈的紅燈時間有關[13],

式中:tR為行人過街信號紅燈時間.

2.4 相鄰交叉口動態多目標優化配時模型

上述3項評價指標分別從不同的角度反映了信號配時效果,在混合交通環境下相鄰交叉口動態多目標優化配時模型為

約束條件描述如下:

(1)相鄰交叉口相位差不應不大于公共信號周期,即

(2)交叉口周期時長應大于各相位的有效綠燈時間之和為

(3)各相位機動車車流量最大飽和度Xi滿足

式中:qi為第i相位車輛實際流量;qsi為第i相位飽和流量.

3 實驗研究

3.1 測試函數結果分析

本工作在Farina等[15]給出的3個測試函數下進行測試,采用反世代距離(inverted generational distance,IGD)評價指標和空間(Spacing,Sp)分布范圍作為算法的收斂性和分布性性能評價指標.將本算法與3種典型動態多目標算法的優化結果進行對比.這3個算法分別為Deb等[16]的動態多目標優化算法DNSGA-Ⅱ-A、DNSGA-Ⅱ-B和Hatzakis等[17]提出的基于簡單預測的動態多目標進化算法DNSGA-Ⅱ-PREM.

算法的參數設置如下:種群規模N=150;交叉概率為0.9;變異概率為1/n,n為決策空間的維數.本工作提出的MPCED-MOGA算法的搜索種群規模為100,跟蹤種群規模為50,交叉概率和變異概率同上.為了研究在不確定環境下各種算法動態變化的影響,本工作給出了不同的(τt,nt)組合,對每個問題的各種組合都做了20次獨立實驗,即各種算法統一跟蹤20次環境變化,環境變化的閾值設為0.01.

將4種算法在解決不同動態多目標優化基準問題的收斂性和分布性的結果進行對比分析.在分析算法結果時,考慮到不同算法輸出的最終滿意解的個數不等,為了保證最后進行對比分析的種群數量相等,本工作從DNSGA-Ⅱ-A、DNSGA-Ⅱ-B、DNSGA-Ⅱ-PREM每次變化輸出的150個種群中,根據非劣排序與擁擠距離選出100個較優個體進行分析.表1和2分別為4個算法獨立運行20次的收斂性指標IGD指標和分布性指標Sp的統計結果.表中(nt,τt)表示為環境變化的頻率和幅度;Mean代表各算法當前指標的均值,std為各算法當前指標的標準差.從表1中可以看出,對于3種不同的測試函數,MPCED-MOGA相對于其他算法收斂到不錯的結果;從表2可以看出本工作提出的MPCED-MOGA在具有較好的追蹤性能的同時,分布性能也是不錯的;對于不同的(nt,τt)對,MPCED-MOGA都獲得了較好的效果,說明算法在不確定環境下能夠對環境的改變做出快速反應,同時能快速地向問題的最優解集靠近.

表1 獨立運行20次算法IGD指標Table 1 IGD values of algorithm running independently for 20 times

表2 獨立運行20次算法Sp指標Table 2 Sp values of algorithm running independently for 20 times

對于FDA1函數,實驗結果證明,在不同的環境變化情況下MPCED-MOGA的性能是最好的.圖3是測試函數FDA1在(nt,τt)為(5,30)時,環境變化5次的結果.圖3給出了4種算法所得的Pareto前沿與其真實Pareto前沿的對比圖.由于該測試問題的真實帕累托最優前沿(Pareto optimal front,POF)是不變的,本工作對不同時刻的目標函數值進行了平移.令(F1+t/5,F2+t/5),其中t表示為不同時刻.顯然MPCED-MOGA在5個不同的時刻都比其他3個算法的收斂性能優越,其收斂得到的最優解集與FDA1真實解的距離最近.

圖3 FDA1不同算法Pareto最優解集Fig.3 Pareto optimal solution sets of different algorithms for FDA1

與FDA1不同,DMOP2問題是為了測試算法是否能夠找到多樣性優良的POF.MPCEDMOGA的收斂性能明顯優于其他3種算法,且其分布性也比其他算法好一些,這是由于采用多種群進化策略增加了解的多樣性.圖4顯示了不同算法對于DMOP2的最優前沿與其真實POF的對比情況.為了能更清晰地對比結果,亦采用(F1+t/5,F2+t/5)的方法對不同時刻的最優前沿進行平移,同樣MPCED-MOGA得到的結果更靠近真實的問題POF.

圖4 DMOP2不同算法Pareto最優解集Fig.4 Pareto optimal solution sets of different algorithms for DMOP2

對于FDA3函數,FDA3的最優解的某些分量是隨著環境(時間)發生改變的,同時其真實POF也隨著環境(時間)改變,解的密度也隨環境(時間)變化.該測試問題考驗算法在搜索最優解的同時,跟蹤最優前沿變化的能力,因此對算法的分布性能要求較高.從表1可以明顯看出,MPCED-MOGA的收斂性最佳,且分布性能也表現不俗.圖5給出了不同算法對FDA3的最優前沿與其真實POF對比情況.從表5可見,在收斂性能和分布性能方面,MPCED-MOGA都明顯優于其他算法.

在評價一個多目標算法的過程中,算法復雜度決定了算法的執行效能.在MPCEDMOGA中,時間開銷主要由步驟2對2個種群進行遺傳、變異操作,對2個種群進行非劣排序,排序算法最壞情況下的時間復雜度為O(mnlogn),計算個體聚集距離的時間為O(mn).因此,步驟2的復雜度為O(mnlogn)+O(mn).單一種群總的算法復雜度為O(mnlogn).考慮到本工作存在搜索種群和跟蹤種群這2個種群,算法的時間復雜度為O(m(n1+n2)log(n1+n2)),其中m為目標數,n1為跟蹤種群個體數目,n2為搜索個體數目.

3.2 混合交通流信號配時多目標優化仿真分析

3.2.1 相鄰交叉口基本信息

本工作以上海天目西路為交通主干道,進行相鄰信號動態配時分析.2個交叉口相鄰僅230 m,高峰期交通負荷大.采用定周期4相位機制行信號控制,公共周期時長為126 s,不考慮進口道坡度影響.2個交叉口采用同周期相同信號配時方案,各相位黃燈信號時長同為3 s.通過實地調查獲得2個交叉口在一周內的早高峰期的交通流數據,此相鄰交叉口外進口道的機動車交通流數據[18]和內進口交通流數據由外進口道進入內進口道的流量決定.表3給出了此相鄰交叉口非機動車和行人流量數據.

圖5 FDA3不同算法Pareto最優解集Fig.5 Pareto optimal solution sets of different algorithms for FDA3

表3 相鄰交叉口非機動車及行人流量數據Table 3 Non motor vehicle and pedestrian flow data at adjacent intersections

3.2.2 算法運算結果分析

根據3.4節中提出的相鄰交叉口動態多目標優化配時模型,采用本工作提出的MPCEDMOP算法對其進行求解,確定相鄰交叉口的最優協調優化控制方案.這里,MPCED-MOGA算法搜索種群規模為100,跟蹤種群的規模為50,單個時間窗最大迭代次數取100,其他參數同4.1.

(1)優化目標間的沖突關系分析.

圖6為3個目標Pareto解集兩兩間對比的結果.圖6(a)中,隨著機動車延誤的減小,行人過街等待時間隨之增加,2個優化目標相互沖突;從(b)中可以看到,機動車延誤與非機動車延誤也是相互沖突的目標;(c)表明,對于相鄰交叉口而言,非機動車延誤與行人過街等待時間表現出近似的線性關系,表明二者之間不具有沖突性.

圖6 各個性能指標的Pareto前沿Fig.6 Pareto fronts of each performance index

(2)配時方案決策及對比

利用Topsis決策方法[19],從MPCED-MOGA得到的候選配時方案集中選出最滿意配時方案,并分別與其他3個算法(DNSGA-Ⅱ-A、DNSGA-Ⅱ-B和DNSGA-Ⅱ-PREM)的結果進行比較.表4給出了不同算法在不同的時間窗下得出的最優方案所對應的性能指標.從表4可以看出,相對于其他算法,MPCED-MOGA優化了決策方案,機動車平均延誤、非機動車平均延誤、行人過街等待時間這3項指標都有不同程度的降低,即減少了各種交通流滯留在交叉口處的時間.

(3)Matlab與Vissim仿真平臺結果分析.

首先,在Vissim平臺上搭建在混合交通環境下相鄰交叉口路網,本工作建立了相鄰交叉口Vissim、Matlab集成仿真平臺.

為了驗證本工作提出的相鄰交叉口實時協調控制的優化效果,首先對比基于不同算法的動態控制方法的控制效果.當2個交叉口流量變化值大于150 pcu/h時,認定交通狀態發生了變化,此時啟用動態多目標優化算法優化出實時最優配時方案.為清楚地表達仿真結果,設置仿真時長為2.5 h.通過比較交叉口車輛平均延誤時間、停車次數以及行人過街等待時間來證明本算法的先進性.

表4 相鄰交叉口優化配時方案對比結果Table 4 Comparison results of signal timing at adjacent intersections

表5給出了基于不同算法的信號配時方法的配時效果對比.從表中可以看出,與DNSGA-Ⅱ-PREM算法相比,本工作提出的MPCED-MOGA算法得到的配時方案中,機動車和非機動車停車次數較多,但是機動車延誤降低了3.8%,行人等待時間減少了2.6%.同時,表5也對比了本算法和Wester[20]提出的單點配時方法TRRL算法.從表5也可以看出,在本算法下機動車延誤降低了34.5%,非機動車降低了25.9%,行人等待時間減少了30.7%,機動車和非機動車的停車次數也分別減少了42.4%和21.8%,提高了交叉口的服務水平.

表5 相鄰交叉口不同算法配時效果對比Table 5 Signal timing comparison results of different algorithms at adjacent intersections

4 結束語

針對考慮機動車、非機動車、行人的混合交通流的擁堵狀況,本工作根據機動車、非機動車、行人三者的滯留時間均最短為目標,建立了動態多目標優化配時模型;設計了一種基于NSGA-Ⅱ的MPCED-MOGA算法,該算法能更好地解決動態多目標優化問題,與DNSGA-Ⅱ-A、DNSGA-Ⅱ-B、DNSGA-Ⅱ-PREM算法相比,MPCED-MOGA算法的收斂性能和分布性能均更好,且計算時間更短.從仿真實驗也可以看出,MPCED-MOGA算法對于機動車、非機動車、行人這3個目標建立的模型,能夠更好地求解,并保留解的多樣性,從而縮短交叉口的延誤時間,提高了道路的通行效率.