基于黃金分割雙種群遺傳算法的區(qū)域交通信號(hào)控制

張?jiān)婌?，嵇啟春，孟月?/p>

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710000)

0 引言

據(jù)統(tǒng)計(jì)，在交通出行的高峰時(shí)段，處于擁堵或緩行狀態(tài)的城市占全國(guó)城市的61%，并且全國(guó)主要城市道路信控路口的服務(wù)水平較低[1]。城市交通信號(hào)控制是減少交叉口延誤、提高交通效率、緩解交通擁堵的重要手段[2-4]，而區(qū)域交通信號(hào)控制是城市交通控制中一種行之有效的信號(hào)配時(shí)方法[5-7]。信號(hào)控制技術(shù)的關(guān)鍵在于信號(hào)配時(shí)模型中控制參數(shù)的確定。文獻(xiàn)[8]同時(shí)考慮車輛自身延誤和下游延誤，構(gòu)建交叉口之間的預(yù)測(cè)模型和互動(dòng)模型，并采用滾動(dòng)時(shí)間窗進(jìn)行優(yōu)化，降低區(qū)域整體延誤時(shí)間；文獻(xiàn)[9]構(gòu)建以平均延誤時(shí)間為目標(biāo)的交通優(yōu)化模型，同時(shí)引入馬爾科夫鏈改進(jìn)固定相序信號(hào)控制模型，并采用遺傳算法優(yōu)化求解，提高了路網(wǎng)通行效率。但以上研究只考慮車輛延誤指標(biāo)，實(shí)際上對(duì)交通信號(hào)控制參數(shù)進(jìn)行優(yōu)化時(shí)，需要綜合考慮延誤時(shí)間、通行能力、排隊(duì)長(zhǎng)度等多個(gè)目標(biāo)。而權(quán)衡多個(gè)優(yōu)化目標(biāo)的關(guān)鍵在于怎樣將各個(gè)目標(biāo)結(jié)合起來(lái)達(dá)到綜合最優(yōu)控制。文獻(xiàn)[10]構(gòu)建以區(qū)域總通行量和總延誤為目標(biāo)的區(qū)域協(xié)調(diào)控制雙層規(guī)劃模型，并結(jié)合遺傳模擬退火算法求解模型，但優(yōu)化目標(biāo)分解分層控制，得到的不一定是全局最優(yōu)解；文獻(xiàn)[11]提出基于飽和度、延誤時(shí)間、通過(guò)量的多目標(biāo)區(qū)域協(xié)調(diào)控制算法，采用遍歷的方法求解模型的最佳方案，但計(jì)算量過(guò)大求解速度較低；文獻(xiàn)[12]以停車次數(shù)、延誤時(shí)間和排隊(duì)長(zhǎng)度的加權(quán)和為綜合目標(biāo)，并結(jié)合Q學(xué)習(xí)和粒子群算法對(duì)模型進(jìn)行求解，能夠有效提高城區(qū)的通行效率，但模型中權(quán)重的大小由設(shè)計(jì)者的重視程度選??；文獻(xiàn)[13]構(gòu)建以區(qū)域機(jī)動(dòng)車排放最小和路網(wǎng)通行能力最大為目標(biāo)的交通調(diào)控模型，并用改進(jìn)蟻群算法求解模型，能夠有效控制交通污染同時(shí)合理引導(dǎo)交通流的分布，但模型通過(guò)設(shè)置不同加權(quán)系數(shù)來(lái)平衡權(quán)重，求解過(guò)程繁瑣；文獻(xiàn)[14]構(gòu)建以車均延時(shí)、平均排隊(duì)長(zhǎng)度和通行能力為目標(biāo)的交通控制模型，結(jié)合快速非支配排序遺傳算法求解，能均衡車輛分布、提升路網(wǎng)效率，但計(jì)算復(fù)雜且耗時(shí)。

本文對(duì)信號(hào)配時(shí)優(yōu)化模型和遺傳算法兩方面進(jìn)行改進(jìn)，提出一種基于黃金分割雙種群遺傳算法的城市區(qū)域交通信號(hào)協(xié)調(diào)控制策略。在非均勻交通流的區(qū)域交通信號(hào)優(yōu)化控制研究中，以區(qū)域內(nèi)交叉口周期時(shí)間、相位時(shí)間和相位差為控制變量，以路網(wǎng)總通行能力和總延誤為優(yōu)化目標(biāo)，為獲取多目標(biāo)模型的綜合最優(yōu)解，引入目標(biāo)相對(duì)占優(yōu)策略處理多目標(biāo)優(yōu)化問題。由于遺傳算法在求解高維多變量的區(qū)域交通協(xié)調(diào)優(yōu)化問題時(shí)存在易早熟效率低的問題，故本文采用雙種群遺傳算法(dual population genetic algorithm,DPGA)，主種群采用動(dòng)態(tài)交叉變異算子進(jìn)行全局尋優(yōu)，次種群引入黃金分割法(golden ratio,GR)進(jìn)行局部尋優(yōu)，同時(shí)在兩種群間進(jìn)行個(gè)體交換。

1 城市區(qū)域交通信號(hào)多目標(biāo)優(yōu)化建模

1.1 交通信號(hào)控制目標(biāo)的選取

區(qū)域協(xié)調(diào)控制策略實(shí)際應(yīng)用必須具備高實(shí)時(shí)性、模型適應(yīng)多變的離散、非均勻交通流等條件，才能實(shí)現(xiàn)對(duì)區(qū)域交通的有效協(xié)調(diào)控制。通常在交叉口車流量較小且不會(huì)對(duì)上游交叉口有影響時(shí)，以延誤時(shí)間作為評(píng)價(jià)指標(biāo)構(gòu)建區(qū)域交通協(xié)調(diào)控制模型；當(dāng)交叉口的車流量接近甚至大于路網(wǎng)通行能力時(shí)，在交叉口必定會(huì)產(chǎn)生擁堵現(xiàn)象，此時(shí)在構(gòu)建區(qū)域交通協(xié)調(diào)控制模型時(shí)需要保證通行能力最大，能夠?qū)徊婵诘能嚵髁窟M(jìn)行疏導(dǎo)分流從而減小車輛排隊(duì)。因此本文綜合考慮通行能力和延誤時(shí)間2個(gè)決策目標(biāo)，建立城市區(qū)域交通信號(hào)協(xié)調(diào)控制模型。

1.2 基于目標(biāo)相對(duì)占優(yōu)策略的區(qū)域交通信號(hào)協(xié)調(diào)控制模型

本文所建的區(qū)域交通信號(hào)協(xié)調(diào)控制模型是一個(gè)高維多變量的多目標(biāo)優(yōu)化問題，它的解實(shí)際上是由多個(gè)Pareto最優(yōu)解組成的最優(yōu)解集。因此，為從Pareto最優(yōu)解集中選擇一個(gè)滿足目標(biāo)的“最好”解，使各子目標(biāo)函數(shù)之間達(dá)到某種平衡，讓各目標(biāo)函數(shù)都最接近滿意值，本文引入目標(biāo)相對(duì)占優(yōu)策略[15]對(duì)多目標(biāo)優(yōu)化問題進(jìn)行處理，其基本思想是：對(duì)種群中的所有個(gè)體分別計(jì)算各子目標(biāo)函數(shù)值，將每一個(gè)子目標(biāo)函數(shù)的最優(yōu)值記為該子目標(biāo)函數(shù)的基點(diǎn)，然后分別計(jì)算各個(gè)個(gè)體相對(duì)各基點(diǎn)的目標(biāo)值之和，目標(biāo)值之和最優(yōu)的個(gè)體即為該種群的最優(yōu)個(gè)體，也就是多目標(biāo)優(yōu)化模型的最優(yōu)解。

模型中對(duì)交叉口每條車道組的綠燈時(shí)間約束、公共周期時(shí)長(zhǎng)約束和相位差約束均可在算法的種群初始化時(shí)進(jìn)行調(diào)整。假設(shè)隨機(jī)個(gè)體k代表一種信號(hào)配時(shí)方案，則個(gè)體k基于目標(biāo)相對(duì)占優(yōu)策略的區(qū)域交通信號(hào)控制模型的目標(biāo)函數(shù)計(jì)算公式為：

(1)

區(qū)域交叉口總通行能力以美國(guó)交通研究委員會(huì)(TRB)的《道路通行能力手冊(cè)》中的通行量的計(jì)算方法為基礎(chǔ)，模型的具體形式為：

(2)

建立區(qū)域總延誤模型時(shí)，要考慮相位差對(duì)延誤的影響，區(qū)域的延誤分為路網(wǎng)邊緣進(jìn)口道延誤和路網(wǎng)中間交叉口延誤，計(jì)算公式為式(3)。

(3)

其中：路網(wǎng)邊緣進(jìn)口道延誤由路網(wǎng)邊緣進(jìn)入車流所產(chǎn)生，采用HCM2000延誤模型[3]進(jìn)行計(jì)算，如式(4)；而區(qū)域內(nèi)部交叉口延誤是由車流隊(duì)行駛到路網(wǎng)內(nèi)部的下游交叉口所產(chǎn)生的延誤，分為車隊(duì)頭部遇到紅燈和車隊(duì)尾部遇到紅燈兩種情況，其計(jì)算公式[6]為式(5)。

(4)

(5)

2 基于黃金分割的雙種群遺傳算法

為解決遺傳算法尋優(yōu)過(guò)程易早熟且收縮效率低的問題，同時(shí)達(dá)到區(qū)域交通協(xié)調(diào)控制的高效實(shí)時(shí)性要求，本文將黃金分割法引入雙種群遺傳算法中，兩個(gè)種群同時(shí)且獨(dú)立地進(jìn)行尋優(yōu)操作，并將次種群中最優(yōu)的個(gè)體遷移到主種群中替換最差個(gè)體，主種群中最優(yōu)個(gè)體代替次種群中的相似個(gè)體，提高算法的全局尋優(yōu)性能，使算法快速且準(zhǔn)確的尋找到最優(yōu)解。

2.1 基于黃金分割率的動(dòng)態(tài)交叉變異算子

針對(duì)遺傳算法收斂速度較慢的問題，在主種群中采用基于動(dòng)態(tài)交叉變異算子的遺傳算法進(jìn)行全局尋優(yōu)。通過(guò)黃金分割率選擇最佳自適應(yīng)交叉、變異算子，每次搜索空間縮小0.382倍或0.618倍，能夠快速尋找最優(yōu)自適應(yīng)點(diǎn)，提升算法搜索效率。改進(jìn)的交叉和變異概率公式如下：

(6)

其中：f為進(jìn)行變異操作的個(gè)體的適應(yīng)度值；f′為進(jìn)行交叉操作的兩個(gè)個(gè)體中較大的適應(yīng)度值。favg為種群的平均適應(yīng)度值；fmax為種群的最大適應(yīng)度值，Pcmax為最大交叉概率，Pmmax為最大變異概率。

2.2 基于黃金分割的局部尋優(yōu)算法

為提高算法的尋優(yōu)精度，在次種群中以黃金分割法為基礎(chǔ)進(jìn)行局部尋優(yōu)操作，依次對(duì)種群中各個(gè)體的每一維進(jìn)行黃金分割。在局部尋優(yōu)過(guò)程中，假設(shè)個(gè)體為X=(x1,x2,…,xn)，若對(duì)個(gè)體的第i維變量進(jìn)行優(yōu)化，需要固定其他n-1維的值，計(jì)算第i維變量的搜索區(qū)間，并在個(gè)體第i維的搜索區(qū)間內(nèi)進(jìn)行多次黃金分割，用優(yōu)化得到的高質(zhì)量的新個(gè)體替換舊個(gè)體；然后對(duì)個(gè)體第i+1維變量進(jìn)行優(yōu)化，固定其他維的值，求解第i+1維變量的搜索區(qū)間并對(duì)其進(jìn)行黃金分割，以此類推，直到對(duì)個(gè)體的每一維都進(jìn)行黃金分割，得到局部最優(yōu)解。其中，個(gè)體X第i維變量xi的搜索區(qū)間[ai,bi]的計(jì)算公式為：

ai=max(ai0,xi-ei),bi=min(bi0,xi+ei)

(7)

式中，[ai0,bi0]為個(gè)體第i維變量xi的初始搜索區(qū)間即該維變量xi的整個(gè)區(qū)間。

2.3 基于黃金分割的雙種群遺傳算法的流程

基于黃金分割雙種群遺傳算法(GRDPGA)的求解過(guò)程步驟如下，流程如圖1所示。

圖1 改進(jìn)算法的求解流程圖

步驟一：初始化。對(duì)遺傳算法和黃金分割算法的控制參數(shù)進(jìn)行初始化，并隨機(jī)生成初始種群PA和PB，PA和PB的種群規(guī)模M，最大迭代次數(shù)Gen，最大交叉概率Pc和最大變異概率Pm。

步驟二：算法的終止判斷。判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到則輸出最優(yōu)解；否則，進(jìn)入下一步。

步驟三：計(jì)算適應(yīng)度函數(shù)值。對(duì)種群PA和PB中的每個(gè)個(gè)體，根據(jù)本文的配時(shí)模型如式(1)，計(jì)算個(gè)體的目標(biāo)函數(shù)值。

步驟四：個(gè)體遷移。局部尋優(yōu)種群PB中的最優(yōu)個(gè)體遷移到種群PA中替換最差的個(gè)體；種群PA中最優(yōu)個(gè)體替換種群PB中與其最近似的個(gè)體，個(gè)體相似度的計(jì)算為：

(8)

步驟五：PB進(jìn)行局部尋優(yōu)操作。對(duì)種群PB進(jìn)行2.2中的局部尋優(yōu)操作，更新種群PB，并保留種群PB中一定數(shù)目的最優(yōu)個(gè)體。

步驟六：PA進(jìn)行遺傳操作。先對(duì)種群PA進(jìn)行輪盤賭選擇操作；然后對(duì)種群PA進(jìn)行交叉操作和變異操作，具體的交叉概率和變異概率公式如式(6)；更新種群PA，并保留種群PA中一定數(shù)目的最優(yōu)個(gè)體。

3 實(shí)例驗(yàn)證

3.1 GRDPGA算法的實(shí)驗(yàn)分析

在4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上對(duì)GRDPGA算法和標(biāo)準(zhǔn)遺傳算法進(jìn)行對(duì)比分析。仿真實(shí)驗(yàn)環(huán)境基于Windows 7操作系統(tǒng)，使用MatlabR2017a進(jìn)行編程仿真。具體測(cè)試函數(shù)如下：

1)Sphere Model函數(shù)：

2)Rastrigin函數(shù)：

3)Griewank函數(shù)：

4)Rosenbrock函數(shù)：

4個(gè)測(cè)試函數(shù)的具體參數(shù)設(shè)置如表1所示。

表1 測(cè)試函數(shù)參數(shù)設(shè)置

在對(duì)比實(shí)驗(yàn)中，設(shè)置遺傳算法參數(shù)：M=100，Gen=200，Pc=0.8，Pm=0.1。對(duì)各測(cè)試函數(shù)的適應(yīng)度函數(shù)的迭代過(guò)程進(jìn)行比較，結(jié)果如圖2所示。

圖2 4種標(biāo)準(zhǔn)函數(shù)進(jìn)化適應(yīng)度曲線

從圖2中可以看出，GRDPGA算法和GA算法最終都會(huì)收斂，得到一個(gè)最優(yōu)解，但本文的GRDPGA算法具有更高的尋優(yōu)精度，且算法收斂速度較快。為了進(jìn)一步證明GRDPGA算法的有效性，對(duì)5個(gè)標(biāo)準(zhǔn)函數(shù)進(jìn)行20次獨(dú)立測(cè)試，測(cè)試結(jié)果如表2所示。

表2 測(cè)試實(shí)驗(yàn)結(jié)果對(duì)比

GRDPGA算法綜合性能較高，其標(biāo)準(zhǔn)差均小于GA算法，說(shuō)明GRDPGA算法具有較穩(wěn)定的尋優(yōu)過(guò)程。總體來(lái)說(shuō)，本文提出的GRDPGA算法是可行有效的，能夠快速穩(wěn)定的的獲得全局最優(yōu)解。

3.2 區(qū)域配時(shí)實(shí)例分析

3.2.1 實(shí)例描述

選定文獻(xiàn)[16]中大連市內(nèi)的一塊交通區(qū)域?yàn)檠芯繉?duì)象，此區(qū)域有9個(gè)路口，區(qū)域內(nèi)并沒有單獨(dú)的左轉(zhuǎn)相位，因此設(shè)東西直行相位和南北直行相位為協(xié)調(diào)相位，所有交叉口全部采用兩相位進(jìn)行控制，且每個(gè)信號(hào)相位的綠燈間隔時(shí)間均為5 s，其中黃燈時(shí)間3 s，全紅2 s，路段上的平均行駛車速為40 km·h-1，各交叉口的車流信息如表3所示，各交叉口之間的距離如圖3所示。

表3 各交叉口的車流信息

圖3 測(cè)試路網(wǎng)

3.2.2 基于目標(biāo)相對(duì)占優(yōu)策略的控制模型結(jié)果分析

為驗(yàn)證本文所構(gòu)建的基于目標(biāo)相對(duì)占優(yōu)策略的區(qū)域交通信號(hào)協(xié)調(diào)控制模型的效用，采用GA算法分別對(duì)本文所建模型(模型1)、總延誤時(shí)間和總通行能力固定加權(quán)的優(yōu)化模型(模型2)進(jìn)行50次仿真計(jì)算。設(shè)分析時(shí)間長(zhǎng)度取T=240 s，反映上游交叉口影響的校正系數(shù)K=0.5，種群規(guī)模M=100，最大迭代次數(shù)Imax=100，交叉概率Pc=0.8，變異概率Pm=0.2，最大信號(hào)周期為Cmax=180 s，最小信號(hào)周期為Cmin=80 s，直行最小綠燈相位時(shí)間15 s，每車道飽和流率1 650 veh·h-1，2種情況的仿真結(jié)果統(tǒng)計(jì)如表4所示。

表4 兩種情況的仿真結(jié)果統(tǒng)計(jì)

從表4中可以看出，兩種情況下總通行能力和總延誤的最優(yōu)值和平均值的相對(duì)誤差比較小分別為4.02%，4.73%和3.48%，7.07%，也就是說(shuō)，相比以延誤為主通行能力為輔的優(yōu)化模型，本文所建模型與對(duì)交叉口通行能力和總延誤的尋優(yōu)結(jié)果改善不明顯，但綜合目標(biāo)優(yōu)化模型的尋優(yōu)時(shí)間大大縮短了17.81%，并且符合最大限度提高道路通行量，并使交叉口延誤盡可能小的城市交通控制目標(biāo)，因此文中所構(gòu)建的信號(hào)配時(shí)控制模型是有效的。

3.2.3 GRDPGA算法對(duì)信號(hào)配時(shí)模型的效用分析

為驗(yàn)證GRDPGA算法在求解信號(hào)配時(shí)模型時(shí)的效用性，分別采用GRDPGA和GA算法求解本文構(gòu)建的信號(hào)配時(shí)優(yōu)化模型，計(jì)算機(jī)數(shù)值計(jì)算采用Matlab編程。在采用兩種算法進(jìn)行優(yōu)化求解時(shí)，取種群規(guī)模M=100，最大迭代次數(shù)Imax=50。并對(duì)兩種優(yōu)化算法進(jìn)行50次獨(dú)立仿真計(jì)算，對(duì)比分析兩種算法的最佳配時(shí)方案的控制性能。

1)GRDPGA的算法性能分析：

GRDPGA和GA兩種算法性能指標(biāo)的統(tǒng)計(jì)結(jié)果如表5所示，其中，最大總通行能力maxQ為50次運(yùn)行結(jié)果中總通行能力的最大值，平均總通行能力avgQ為50次運(yùn)行結(jié)果中總通行能力的平均值，最小總延誤minD為50次運(yùn)行結(jié)果中總延誤的最小值，平均總延誤avgD為50次運(yùn)行結(jié)果中總延誤的平均值，優(yōu)化時(shí)間為50次運(yùn)行的平均時(shí)間。從表5中可以看處，GRDPGA與GA算法均可得到可行解，但在最大總通行能力maxQ、平均總通行能力avgQ、最小總延誤minD、平均總延誤avgD和優(yōu)化時(shí)間等指標(biāo)GRDPGA均優(yōu)于GA，說(shuō)明對(duì)本文區(qū)域交叉口控制實(shí)例設(shè)計(jì)的基于黃金分割的雙種群遺傳算法具有較好的應(yīng)用效果。

表5 GRDPGA和GA兩種算法50次數(shù)值計(jì)算的統(tǒng)計(jì)結(jié)果

2)控制方法的控制效能分析：

進(jìn)行50次獨(dú)立仿真運(yùn)算，分別采用GRDPGA和GA兩種算法求解區(qū)域信號(hào)配時(shí)模型，得到50組信號(hào)配時(shí)方案及其對(duì)應(yīng)的區(qū)域交叉口性能指標(biāo)，從中選擇一組配時(shí)方案及性能指標(biāo)統(tǒng)計(jì)結(jié)果如表6所示。采用GRDPGA算法優(yōu)化

表6 兩種算法的一組配時(shí)方案及性能指標(biāo)

模型相比GA算法在區(qū)域總通行能力性能和整體延誤性能上均得到了明顯改善，分別約有15.71%,25.11%的改進(jìn)，大大提升了城市交通區(qū)域協(xié)調(diào)控制的綜合能力。

4 結(jié)束語(yǔ)

本文通過(guò)引入目標(biāo)相對(duì)占優(yōu)策略構(gòu)建區(qū)域交通信號(hào)協(xié)調(diào)優(yōu)化模型，并將黃金分割法與雙種群遺傳算法相結(jié)合，改善了遺傳算法易早熟、搜索速度慢的問題。通過(guò)利用4個(gè)測(cè)試函數(shù)和實(shí)際路網(wǎng)數(shù)據(jù)仿真實(shí)驗(yàn)，結(jié)果表明：所提的區(qū)域信號(hào)配時(shí)方法能夠最大限度提高道路通行量，并使交叉口延誤盡可能小，符合城市區(qū)域交通控制的優(yōu)化目標(biāo)；改進(jìn)的GRDPGA算法能夠有效地實(shí)現(xiàn)區(qū)域信號(hào)配時(shí)，是一種高效穩(wěn)健的全局優(yōu)化算法。