基于改進NSGA-Ⅱ的區域交通信號優化控制

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

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

0 引言

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

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

1 選取交通信號配時優化模型

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

1.1 車輛延誤模型

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

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

區域路網中的車均延誤為

1.2 尾氣排放模型

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

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

其中，eijk為區域路網第i交叉口第j相位第k車道的排放量;e1為標準小汽車單位排放因子;Lijk為第i交叉口第j相位第k車道的路段長度;e2為標準小汽車單位怠速排放因子;dijk為區域路網中第i個路口第j相位第k車道的車輛平均延誤。

區域路網中的車均尾氣排放量為

1.3 建立優化目標模型

將兩個優化目標放到同一量級上進行比較，實地對區域路網的原始配時進行采集，運用上述模型求得初始的延誤d0以及初始排放e0，最終構建交叉口的優化模型為

2 NSGA-Ⅱ基本概念

NSGA-Ⅱ(帶精英策略的非支配排序的遺傳算法)，是基于遺傳算法的多目標優化算法[19]。快速非支配排序會根據個體的優劣程度對種群進行分層，分到多個不同的前沿面中。擁擠距離描述了種群中個體的分散程度，擁擠度可以保證種群的多樣性，計算公式為

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

i>j?irankCj

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

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

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

3.1 自適應交叉算子

為提高該算法的收斂性以及尋優能力，在原方法的基礎上提出一種自適應交叉算子的改進方法。

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

引入一個可以根據算法迭代次數自適應調整算法交叉度的因子，前期加大個體的交叉，后期適當減小交叉度，自適應交叉算子的更新公式為

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

3.2 自適應調節種群規模

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

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

其中，左側為所取g個點的斜率的絕對值，ε表示判斷算法前后期的標準。

3.3 算法流程

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

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

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

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

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

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

6)當前迭代次數g達到了m次后，每迭代一次就選取m代的m個最優值，進行以下判斷：

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

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

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

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

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

4 算法案例分析

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

圖2 本文案例的路網結構

4.1 交叉口數據信息

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

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

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

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

4.2 優化結果對比

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

圖3 標準NSGA-Ⅱ迭代圖

圖4 改進NSGA-Ⅱ迭代圖

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

通過采集得到的原始區域路網的信號配時及上述兩種方法的優化結果，進行對比分析，如表2所示。

表2 改進前后NSGA-Ⅱ的優化配時方案

將得到的優化值取平均值，標準NSGA-Ⅱ的延誤平均優化值為0.901 8，排放平均優化值為0.949 3；改進NSGA-Ⅱ的延誤平均優化值為0.844 0，排放平均優化值為0.924。經過對比可知，改進后的方法不管是在迭代過程還是在優化值上均優于標準的方法。

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

圖5 改進NSGA-Ⅱ的Pareto最優解集

4.3 算法實時性分析

對于區域交通信號優化控制，最根本的是根據現實交通情況，實時優化并調整交通信號的配時。為對本文算法的實時性進行分析，分別將改進前后的算法應用到本文案例與ZDT1測試函數中，并記錄兩種算法尋到最優值的時間。其中ZDT1是一種多目標測試函數，公式為

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

表3 算法尋優時間

4.4 VISSIM仿真

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

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

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

圖7 優化前后配時的車輛平均延誤對比

圖8 優化前后配時的平均CO排放量對比

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

5 結論

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