基于改進NSGA-Ⅱ的區(qū)域交通信號優(yōu)化控制

牟 亮，趙 紅，李 燕，仇俊政，崔翔宇，袁煥濤

(青島大學(xué)機電工程學(xué)院，山東 青島 266071)

0 引言

隨著中國經(jīng)濟的日益發(fā)展，城市規(guī)模以及汽車保有量迅速增加，各類交通需求也隨之增長[1]。交通擁堵問題亟需解決，道路渠化、增加車道等解決方案成本巨大并且周期較長，難以實施，因此交通信號控制成為一種可以有效解決交通擁堵問題的方法。目前城市內(nèi)的交通路口錯綜復(fù)雜，不同的路口之間具有一定的聯(lián)系，當(dāng)采用單交叉口優(yōu)化控制時易發(fā)生溢流現(xiàn)象，嚴(yán)重的話會導(dǎo)致區(qū)域路網(wǎng)交通癱瘓，因此單交叉口的研究已經(jīng)不能從根本上解決問題，區(qū)域交通優(yōu)化控制已經(jīng)是最快速以及最經(jīng)濟的方法。

以上文章在研究區(qū)域交通信號配時優(yōu)化時，未將車輛延誤與尾氣排放綜合考慮。本文旨在達到路網(wǎng)性能的綜合最優(yōu)，故選用多目標(biāo)優(yōu)化NSGA-Ⅱ算法，建立關(guān)于車輛延誤與排放的數(shù)學(xué)模型進行優(yōu)化。并且本文將在快速非支配排序遺傳算法的基礎(chǔ)上提出改進，根據(jù)該算法的迭代特性，建立更加符合的交叉算子。

1 選取交通信號配時優(yōu)化模型

為保證區(qū)域路網(wǎng)的交通能夠高效、安全通行，交通信號控制的目標(biāo)模型也需要由單目標(biāo)優(yōu)化向多目標(biāo)優(yōu)化發(fā)展。本文為提高區(qū)域路網(wǎng)的性能，將車輛延誤與尾氣排放作為優(yōu)化控制目標(biāo)來建立模型。

1.1 車輛延誤模型

可以選用Webster延誤模型和美國道路通行能力手冊(Highway Capacity Manual，HCM)延誤模型。Webster延誤模型經(jīng)廣泛的使用和驗證，得出僅適應(yīng)于飽和度0～0.67范圍內(nèi)。而HCM延誤模型適用于飽和度較高的干道協(xié)調(diào)控制的延誤計算。本文是在這兩種模型的基礎(chǔ)上來建立模型進行計算的，公式[16]為

其中，dijk為區(qū)域路網(wǎng)中第i個路口第j相位第k車道的車輛平均延誤;ci為第i交叉口周期長度;λij為第i交叉路口第j相位綠信比;qijk為第i交叉口第j相位第k車道的車流量;sij為第i交叉口第j相位的飽和流量;yijk為qijk與sij之比。

區(qū)域路網(wǎng)中的車均延誤為

1.2 尾氣排放模型

本文也將該效益作為目標(biāo)進行優(yōu)化。根據(jù)現(xiàn)有的研究[17]，區(qū)域交通的碳排放有很多因素影響，并且車輛在行駛過交叉口的過程中大都經(jīng)歷了4種工況，每種工況的汽車排放量不同，因此需要分情況進行考慮。

本文將以車輛的CO尾氣排放量作為優(yōu)化目標(biāo)，周申培[18]將車輛行駛過交叉口的尾氣排放量分為行駛排放和因車輛延誤引起的怠速排放，排放模型為

其中，eijk為區(qū)域路網(wǎng)第i交叉口第j相位第k車道的排放量;e1為標(biāo)準(zhǔn)小汽車單位排放因子;Lijk為第i交叉口第j相位第k車道的路段長度;e2為標(biāo)準(zhǔn)小汽車單位怠速排放因子;dijk為區(qū)域路網(wǎng)中第i個路口第j相位第k車道的車輛平均延誤。

區(qū)域路網(wǎng)中的車均尾氣排放量為

1.3 建立優(yōu)化目標(biāo)模型

將兩個優(yōu)化目標(biāo)放到同一量級上進行比較，實地對區(qū)域路網(wǎng)的原始配時進行采集，運用上述模型求得初始的延誤d0以及初始排放e0，最終構(gòu)建交叉口的優(yōu)化模型為

2 NSGA-Ⅱ基本概念

NSGA-Ⅱ(帶精英策略的非支配排序的遺傳算法)，是基于遺傳算法的多目標(biāo)優(yōu)化算法[19]?？焖俜侵渑判驎鶕?jù)個體的優(yōu)劣程度對種群進行分層，分到多個不同的前沿面中。擁擠距離描述了種群中個體的分散程度，擁擠度可以保證種群的多樣性，計算公式為

為了維持種群的多樣性，需要對擁擠度進行比較。擁擠距離比較算子定義為

i>j?irankCj

對于處于同一前沿面的個體，優(yōu)先選取擁擠度小的，以保證個體的多樣性。

精英策略：將父代種群Pt和子代種群Qt組合成大小為2N的新種群，對Qt進行快速非支配排序和擁擠度計算，選擇前N個個體進入種群Pt+1。如果某個相同前沿面的所有個體加入會導(dǎo)致超過種群上限。

3 改進的快速非支配遺傳算法

3.1 自適應(yīng)交叉算子

為提高該算法的收斂性以及尋優(yōu)能力，在原方法的基礎(chǔ)上提出一種自適應(yīng)交叉算子的改進方法。

基本的NSGA-Ⅱ算法中是采用的二進制交叉，該交叉算子實現(xiàn)起來非常簡單，但是移動空間不足，算法搜索空間小，易陷入局部最優(yōu)解。因二進制交叉算子的不足，引入一種新的交叉算子，正態(tài)分布交叉算子(Normal Distribution Crossover)。正態(tài)分布交叉算子搜索范圍大，適合前期的要求[20]，因此在算法迭代的前期將大比例采用正態(tài)分布交叉算子。當(dāng)進行到算法迭代后期，種群中個體大都接近最優(yōu)解，不需要再進行大范圍的搜索，此時要求算法可以迅速收斂，因此將交叉算子大比例分配給二進制交叉算子，以加快算法的收斂。

引入一個可以根據(jù)算法迭代次數(shù)自適應(yīng)調(diào)整算法交叉度的因子，前期加大個體的交叉，后期適當(dāng)減小交叉度，自適應(yīng)交叉算子的更新公式為

其中，M=P1+P2,N=P1-P2,P1,P2為選中進行交叉的父代個體；g為算法當(dāng)前的迭代次數(shù)，G為算法的總迭代次數(shù)；beta為正態(tài)分布隨機變量。

3.2 自適應(yīng)調(diào)節(jié)種群規(guī)模

在算法前期，當(dāng)采用更大規(guī)模的種群時，可以提高算法的尋優(yōu)范圍，在后期經(jīng)迭代的個體基本都已趨向最優(yōu)值，要求快速收斂，所以不再需要大規(guī)模的種群，此時將種群規(guī)模適當(dāng)縮小，可以加快算法的收斂。

需要添加一個條件來判斷何為算法前期何為算法后期，這里采用每迭代m次產(chǎn)生的m個最優(yōu)值，采用線性擬合的方法求得這m個點的斜率，當(dāng)該斜率的絕對值小于某個數(shù)值時，說明尋優(yōu)過程已經(jīng)逐漸平穩(wěn)，基本得到最優(yōu)解，此時不再需要大規(guī)模的種群。判斷公式為

其中，左側(cè)為所取g個點的斜率的絕對值，ε表示判斷算法前后期的標(biāo)準(zhǔn)。

3.3 算法流程

改進后NSGA-Ⅱ的算法流程如下：

1)隨機產(chǎn)生2N個個體的初始種群P0；

2)進行自適應(yīng)交叉和變異操作生成數(shù)量為N的新種群Qt;

3)將種群Pt與Qt合并得到Rt，并對合并種群進行快速非支配排序；

4)計算擁擠度距離，利用精英策略選擇N個個體作為新的父代種群Pt+1；

5)判斷當(dāng)前迭代次數(shù)g是否不小于最大迭代次數(shù)G，是，則算法的迭代結(jié)束，否則g=g+1，并進行下一步判斷；

6)當(dāng)前迭代次數(shù)g達到了m次后，每迭代一次就選取m代的m個最優(yōu)值，進行以下判斷：

若成立則返回第2)步，否則進行下一步。

7)隨機產(chǎn)生N個種群，與父代種群Pt+1合并產(chǎn)生個數(shù)為2N的種群Pr；

8)對種群Pr進行快速非支配排序、精英策略，找出最優(yōu)的N個個體，返回第2)步。

本文算法的流程圖如圖1所示。

圖1 改進NSGA-Ⅱ的算法流程圖

4 算法案例分析

為驗證本文方法應(yīng)用于區(qū)域交通方面的有效性，使用matlab R2015b對該方法進行編程，在CPU型號Core i7-8565U，內(nèi)存為8G的電腦中運行。選取青島市青島理工大學(xué)附近路網(wǎng)，如圖2所示，該路網(wǎng)為典型區(qū)域路網(wǎng)，并對該路口的數(shù)據(jù)進行實地采集。

圖2 本文案例的路網(wǎng)結(jié)構(gòu)

4.1 交叉口數(shù)據(jù)信息

該區(qū)域路網(wǎng)由4個交叉路口組成，每個路口每個相位由兩條對向車道組成。并設(shè)置相位最小綠燈時間為20s，令行人有充足的時間穿過馬路，最大相位綠燈時間為50s，防止某相位綠燈時間過長對其他相位造成積壓車流的現(xiàn)象；最小周期時長為80s，最大周期時長為150s。

機動車相位飽和設(shè)置為1 500 pcu/h，選取CO作為本文尾氣排放的目標(biāo)，標(biāo)準(zhǔn)小汽車CO的排放因子為45g/(pcu.km)，標(biāo)準(zhǔn)小汽車怠速排放因子為53g/(pcu.h)。

對該路網(wǎng)高峰時期(16：00～17：00)的小時車流量進行采集，采集結(jié)果如表1所示。

表1 路網(wǎng)小時車流量(16：00～17：00)

4.2 優(yōu)化結(jié)果對比

為驗證本文的改進方法相對于未改進方法的優(yōu)勢，將上述案例分別用標(biāo)準(zhǔn)NSGA-Ⅱ以及改進的NSGA-Ⅱ進行優(yōu)化，并利用迭代圖的形式形象展示改進后的優(yōu)點。在迭代圖中會展示每代中的最優(yōu)值以及平均值，這里每代最優(yōu)值是在經(jīng)快速非支配排序中第一前沿面中選取，并通過擁擠度距離的計算選取擁擠度最佳的一個，因為兩個優(yōu)化目標(biāo)均放在同一標(biāo)準(zhǔn)下，故在迭代圖中將表示兩個目標(biāo)的平均值。迭代圖如圖3和圖4所示。

圖3 標(biāo)準(zhǔn)NSGA-Ⅱ迭代圖

圖4 改進NSGA-Ⅱ迭代圖

通過圖3和圖4的比較，可以明顯地發(fā)現(xiàn)改進后的NSGA-Ⅱ方法尋找最優(yōu)值的速度以及精度均優(yōu)于未改進的，在100代左右就找到了最優(yōu)值，而未改進的到200代左右才慢慢收斂；并且改進后的每代平均值波動劇烈，說明改進方法的搜索范圍擴大。

通過采集得到的原始區(qū)域路網(wǎng)的信號配時及上述兩種方法的優(yōu)化結(jié)果，進行對比分析，如表2所示。

表2 改進前后NSGA-Ⅱ的優(yōu)化配時方案

將得到的優(yōu)化值取平均值，標(biāo)準(zhǔn)NSGA-Ⅱ的延誤平均優(yōu)化值為0.901 8，排放平均優(yōu)化值為0.949 3；改進NSGA-Ⅱ的延誤平均優(yōu)化值為0.844 0，排放平均優(yōu)化值為0.924。經(jīng)過對比可知，改進后的方法不管是在迭代過程還是在優(yōu)化值上均優(yōu)于標(biāo)準(zhǔn)的方法。

將改進NSGA-Ⅱ算法執(zhí)行后，會得到Pareto最優(yōu)解集，該解集說明了車輛延誤與尾氣排放之間的關(guān)系，如圖5所示。從圖5可以看出尾氣排放與車輛延誤呈遞減關(guān)系，當(dāng)需要更小的尾氣排放時，這會以犧牲車輛延誤為代價，同樣當(dāng)需要更小的車輛延誤也會導(dǎo)致尾氣排放的增加。

圖5 改進NSGA-Ⅱ的Pareto最優(yōu)解集

4.3 算法實時性分析

對于區(qū)域交通信號優(yōu)化控制，最根本的是根據(jù)現(xiàn)實交通情況，實時優(yōu)化并調(diào)整交通信號的配時。為對本文算法的實時性進行分析，分別將改進前后的算法應(yīng)用到本文案例與ZDT1測試函數(shù)中，并記錄兩種算法尋到最優(yōu)值的時間。其中ZDT1是一種多目標(biāo)測試函數(shù)，公式為

兩種算法在本文案例和ZDT1測試函數(shù)上的尋優(yōu)時間如表3所示。從表3的算法尋優(yōu)時間可以看出，改進后的算法比改進前找到最優(yōu)值的時間更短。同時可知算法的計算時間也可以滿足交通信號配時優(yōu)化對實時性的要求。

表3 算法尋優(yōu)時間

4.4 VISSIM仿真

VISSIM是一種微觀的、基于時間間隔和駕駛行為的仿真建模工具，用于城市交通和公共交通運行的交通建模[21]。它可以分析各種交通條件下，如車道設(shè)置、交通構(gòu)成、交通信號、公交站點等，城市交通和公共交通的運行狀況，是評價交通工程設(shè)計和城市規(guī)劃方案的有效工具。根據(jù)本文提到的案例，在VISSIM中搭建仿真模型，如圖6所示。

圖6 本文案例的VISSIM仿真模型

為驗證本文方法的有效性，將原始配時以及利用改進NSGA-Ⅱ方法得到的優(yōu)化值進行對比，利用VISSIM的輸出文件對該區(qū)域路網(wǎng)的車輛延誤以及尾氣排放進行評價。仿真周期設(shè)置為1h，采樣周期設(shè)置為60s，對該路網(wǎng)的各種數(shù)據(jù)進行采集，采集得到數(shù)據(jù)之后進行處理，如圖7和圖8所示。

圖7 優(yōu)化前后配時的車輛平均延誤對比

圖8 優(yōu)化前后配時的平均CO排放量對比

經(jīng)過VISSIM仿真后，對比仿真得到的數(shù)據(jù)，本文改進的方法對于交叉口性能的優(yōu)化十分有效。在CO的排放方面，相比于原始配時降低了8.213%；在車輛平均延誤方面，降低19.023%。并且改進后的全局搜索能力較之前更強，相對于標(biāo)準(zhǔn)NSGA-Ⅱ具有一定的優(yōu)勢。

5 結(jié)論

針對標(biāo)準(zhǔn)NSGA-Ⅱ方法易陷入局部最優(yōu)以及精度不夠的問題，提出的改進交叉算子的方法，根據(jù)迭代過程每個階段的特點進行自適應(yīng)調(diào)節(jié)，前期加大交叉擴大搜索的范圍，后期加速收斂。建立車輛延誤及尾氣排放的優(yōu)化模型，將各個交叉口的有效綠燈時長作為變量，并利用改進前后的NSGA-Ⅱ求解該模型，最后利用VISSIM進行仿真分析，經(jīng)驗證改進后的NSGA-Ⅱ能夠有效應(yīng)用到區(qū)域交通信號配時優(yōu)化中，提高區(qū)域路網(wǎng)性能，減少延誤以及尾氣排放。這個方法綜合考慮了路網(wǎng)的機動車效益以及環(huán)境效益，并且達到了整體上的優(yōu)化，得到了車輛延誤以及尾氣排放之間的關(guān)系，克服了單目標(biāo)優(yōu)化的弊端。