基于差分和狀態空間遺傳混合算法的信號配時優化

陳小靜　李茂軍　張輝

摘 要：為了最大限度地挖掘現有道路的承載能力，提出了一種基于差分進化算法和狀態空間模型遺傳算法的兩階段混合優化算法，建立以車輛平均等待時間最小為目標的數學模型進行優化。為了解決差分進化算法在后期收斂速度變慢，容易陷入局部最優的缺點，引入改進后的狀態空間模型遺傳算法形成一種混合算法。然后，用所提出的混合算法對5個經典測試函數進行尋優測試，并與定時控制、差分進化算法以及狀態空間模型遺傳算法進行對比，實驗結果表明該混合算法不僅提高了收斂速度，并且在保證了算法收斂精度的前提下縮短了迭代次數。最后，以單交叉路口為例，驗證該混合算法在求解信號燈配時問題時的優化效果。

關鍵詞：差分進化算法;狀態空間模型遺傳算法;信號配時;混合算法;平均等待時間

中圖分類號：TP13????? 文獻標識碼：A

Signal Timing Optimization Based on Differential

and State-space Genetic Hybrid Algorithm

CHEN Xiao-jing1， LI? Mao-jun1， ZHANG? Hui2

（1.College of Electrical and Information Engineering， Changsha University of Science and Technology， Changsha，

Hunan 410114， China; 2. College of Robotics， Hunan University， Changsha， Hunan 410114， China）

Abstract：In order to maximize the capacity of existing roads， a two-stage hybrid optimization algorithm based on differential evolution algorithm and state-space model genetic algorithm is proposed， and a mathematical model with the goal of minimizing the average waiting time of vehicles is established for optimization.In order to overcome the slower convergence speed in the later stage of the differential evolution algorithm and easy to fall into local optimum， the improved state-space model genetic algorithm is introduced to form a hybrid algorithm.Then， 5 classical test functions are used to test the performance of the algorithm. The algorithm was compared with timing control， differential evolution algorithm， and state-space model genetic algorithm based on state-space model. Experimental results show that the algorithm not only improves the convergence speed， but also shortens the number of iterations while ensuring the accuracy of the algorithm's convergence. Finally， taking a single intersection as an example， verify the optimization effect of this algorithm in solving the signal timing problem.

Key words：differential evolution algorithm; genetic algorithm based on state-space model; signal timing;hybrid algorithm; average waiting time

單交叉路口交通信號控制系統大多采用多時段定時控制的方式，根據路口歷史通行數據把一天劃分為多個時間段，人為的設置不同的信號燈時間[1]。由于傳統的信號燈配時方法無法適應復雜的交通環境和實時多變的車流量要求，不少學者開始利用神經網絡、模糊控制、自適應控制、智能優化算法等研究信號燈的配時優化方案[2-5]，增強交叉路口的通行效率，使車輛擁堵情況得到改善 [6]。

Wu等提出了一種以十字路口的交通流量和周圍十字路口的交通流量為參數的霧計算交通燈控制系統[7]，它的主要原理是采用霧計算平臺計算和共享某一路口及相鄰路口的實時車流量情況，來協調多個路口之間的信號燈周期。陳丹利用混沌優化的遍歷性改進遺傳算法[8]，來提高初始種群的隨機性和多樣性，然后在變異操作后對部分種群進行混沌搜索，并用該算法對城市微觀交通仿真系統模型進行優化。Qu等以路口的通行承載力最大化為目標構造了綠燈利用率的數學模型[9]，而且并提出了一種能夠實時調整綠燈時間的自適應控制方案。張文泉將模糊控制和按照誤差逆向傳播的BP神經網絡融合，得到一種擁有自學習結構的多交叉口信號協調系統[10]。張小雨等綜合考慮車輛起步延誤、道路的通行能力和車輛尾氣排放等因素，構造多目標信號配時優化模型[11]并采用遺傳算法求最優解。

針對基本群體智能算法在解決信號燈配時優化問題上所出現的收斂速度緩慢、收斂精度不高以及易陷入局部最優的問題。建立了車輛平均等待時間的數學模型，并提出一種差分進化算法（Differential Evolution， DE）和改進的狀態空間模型遺傳算法（Modified Genetic Algorithm Based on State-space Model， MGABS）的混合算法。該混合算法在迭代前期采用DE算法來快速縮小搜索空間，在后期用MGABS算法加快收斂速度。仿真實驗結果證明，該混合算法可以快速精準的找到車輛平均等待時間的數學模型的最優解。

1 控制策略

道路交通安全法規定，駕駛機動車在路口右轉彎不受信號燈限制，所以這里不考慮右轉車道，單交叉路口的車流一共分為8個方向，如圖1所示。因為n2和n5、n3和n7、n1和n6、n4和n8的車流互不干擾，所以只需要設置4個方向的綠燈時間。每個方向上有兩個車道是互不干擾的，取其中車流量較大的車道作為該方向上的實際車流量。

黃燈一般位于綠末紅初之間，時間一般為3 s，可以在此時從視頻檢測系統獲取各個方向的車流量和下一個分配點之前每輛車已經等待的時間[12]。例如在方向4的黃燈開始時獲取視頻檢測系統中的數據，那么接下來第一個信號周期的綠燈時長分別為t1、t2、t3、t4，第二個信號周期的綠燈時長分別為t′1、t′2、t′3、t′3，在分配點之前的4個方向的綠燈時間分別為t″1、t″2、t″3、t″4。

3.3 差分進化和狀態空間模型遺傳混合算法

信號燈定時控制的方式無法合理的分配紅綠燈時間，使得車輛通行效率低，容易造成交通擁堵，所以越來越多的研究人員嘗試用智能算法來解決信號燈配時問題。DE算法在初始階段能夠快速收斂，并且善于求解復雜的多變量函數優化問題[17]。但是，DE算法也有缺點，引起其后期收斂速度變慢的主要原因就是變異操作。而MGABS算法參數少、容易實現、收斂速度快、跳出局部最優點的能力強。因此，將DE算法與MGABS算法融合在一起，形成一種兩階段混合優化算法。

首先，用DE算法對初始種群進行優化，當種群迭代Q次后，尋優搜索空間被縮小，則進入下一階段;用MGABS算法在已被縮小的搜索空間中進一步尋優迭代，找出目標函數的最優解。關于兩階段混合算法迭代次數的分配問題，經過多次試驗總結，當Q=0.8M時，實驗結果相比其他迭代方式更接近最優值，而且標準差明顯小于其他分配方式。

DE和MGABS混合算法的基本步驟如下所示，該算法分為兩個階段。

第一階段采用DE算法：

Step1 初始化種群確定基本參數：迭代次數Q、種群規模N、總迭代次數M、粒子維度D、放縮因子F、交叉概率CR，在可行域內隨機產生且滿足約束條件的初始種群中選擇三個不同的個體;

Step2 變異和交叉操作：根據（8）式在種群中隨機選擇兩個個體進行向量差分后經過放縮，再加上第三個個體，得到變異后的新個體。將其按（9）式進行交叉操作來產生試驗個體;

Step3 選擇操作：比較試驗個體和上一代個體，選擇其中更優秀的粒子成為新的種群。

Step4 判斷是否滿足進入下一階段的條件，若kSymbolcB@Q次則轉至Step2，否則轉至Step5;

第二階段采用MGABS算法：

Step5按照（12）式構造狀態進化矩陣G，將DE算法迭代Q次后的種群作為初始種群X（k），按（11）式進行迭代，產生子代群體X（k+1）;

Step6計算子代群體X（k+1）的個體適應度值。從X（k）和X（k+1）中選擇N個優秀的個體設為下一代群體，然后置X（k+1）為X（k）;

Step7從X（k）中選出適應度較差的P個個體，若QSymbolcB@kSymbolcB@（M+Q）/2，則采用變異策略（1）;否則，采用變異策略（2）;

Step8判斷是否完成M次迭代，若滿足則終止進化;否則轉至Step5。

4 仿真結果

4.1 測試函數

為了驗證提出的差分進化和狀態空間模型混合算法在處理復雜優化問題上的尋優精度和收斂速度，選取了5個經典標準測試函數進行尋優能力測試。測試函數的表達式、取值范圍、全局最小值以及函數特性如下面表1所示。這5個函數分為單峰函數和多峰函數，單峰函數的作用是測試混合算法的收斂精度和收斂速度，而多峰函數具有多個的局部極大值，能夠很好的測試算法的全局搜索能力和跳出局部極值的能力。

該算法的測試環境為：采用MATLAB R2018a編程語言，在Intel（R）Celeron（R） CPU 1007@ 1.50 GHz、內存4 GB的電腦上運行程序。

4.2 測試結果分析

為了檢驗混合算法的優化能力，在仿真實驗中將種群規模均設為50，粒子維度設為20，總迭代次數設為200，比較5個測試函數獨立運行30次的平均值、最小值、標準差。DE算法、MGABS算法和該混合算法的性能對比結果如表2所示。

4.3 信號燈配時優化

分別采用定時控制、DE算法、MGABS算法、遺傳算法、蟻群算法以及混合算法對單交叉路口4個方向的綠燈時間進行優化配時。其中種群規模N=50，總迭代次數M=30，搜索空粒子間維度設為20，在[0，180]秒之間隨機選擇的5組車流量數據和各車的實際等待時間。設置每個方向的綠燈時間范圍為[15，60]秒，綠燈周期上限Tmax =180 s，車輛駛出交叉路口的速度為t =3 s/輛，設置分配點之前的4個方向的實際綠燈時間t″1、t″2、t″3、t″4分別為30 s、22 s、35 s、26 s。為了更直觀地體現該混合算法的優越性，與4種不同控制方式下車輛的平均等待時間進行比較，仿真實驗結果如表3所示。

圖2為表3中第1例的車輛平均等待時間優化曲線圖，橫坐標代表算法的迭代次數，縱坐標代表車輛平均等待時間。從圖2中能夠發現，隨著迭代次數的增多，除定時控制外其他5種算法的車輛平均等待時間逐漸減小。雖然蟻群算法較早的收斂到最優值附近，但后期尋優效率低且優化效果不如該混合算法。在遺傳算法的控制方式下，在迭代21次時找到了最優解，此時車輛平均等待時間最短，但迭代過程不夠穩定。該混合算法前12次迭代時快速收斂到最優值附近，最終在第20次迭代時搜索到最小值153.4s，該混合算法與其他五種控制方式相比優化效果最好，證明DE和MGABS混合算法的有效性。

5 結 論

在合理的交通環境假設及約束條件下，綜合考慮了分配點之前車輛已經等待的時間和在當前配點后2個綠燈周期內預計需要等待的時間，建立了以車輛平均等待時間最小為目標的數學模型。鑒于DE算法早期能夠快速收斂、在求解復雜的多變量函數問題上優化效果明顯，但迭代后期收斂速度變慢、全局搜索能力差的情況，將DE算法和MGABS算法相結合，形成一種兩階段的差分進化和狀態空間模型遺傳混合算法。實驗結果證明，差分和狀態空間遺傳混合算法能夠尋到最合適的綠燈時間分配方式，完成提高交叉路口通行效率的目標。

參考文獻

[1] 柳長源，任宇艷，畢曉君.基于改進螢火蟲算法的區域交通信號配時優化[J].控制與決策，2020，3：1-6.

[2] 羅文慧.智慧交通背景下道路交叉口交通流控制模型與算法研究[D].北京：北京交通大學，2019.

[3] HITCHCOCK O， GAYAH V. Methods to reduce dimensionality and identify candidate solutions in multi-objective signal timing problems[J].Transportation Research Part C，2018：398-414.

[4] 劉暢，魏麗英.考慮人均延誤和人均排放的信號配時優化模型[J].哈爾濱工業大學學報，2018，50（9）：83-88.

[5] 趙盼明，劉釗，劉玉，等.基于模糊控制的小區域交叉口群過飽和狀態信號協調優化[J].交通信息與安全，2018，36（4）：51-59.

[6] 雷洋，黃承鋒.城市交通擁堵治理的研究綜述和建議[J].綜合運輸，2018， 40（4）： 8-11.

[7] WU Qiong， HE Fan-fan， FAN Xiu-mei. The intelligent control system of traffic light based on fog computing[J].Chinese Journal of Electronics，2018，27（6）： 1265-1270.

[8] 陳丹.城市交通信號燈的仿真優化研究[D].武漢：武漢理工大學，2011.

[9] QU Xin-ming， YAO Hong-yun， WANG Yu-gang， et al. Adaptive control strategy based on effective utilization ratio of green light time [J].Transportation Research，2015（1）：54-58.

[10]張文泉.城市區域交通信號智能控制算法分析與研究[D].成都：西南交通大學，2016.

[11]張小雨，邵春福.城鄉結合部道路交叉口多目標信號配時優化模型[J].系統仿真學報，2019，32（04）：709-717.

[12]王鼎湘，李茂軍.基于車流量的交通燈智能控制算法[J].計算機應用與軟件，2015，32（06）：241-244.

[13]王鼎湘.單交叉口智能交通燈配時優化控制策略[D].長沙：長沙理工大學，2015.

[14]張新明，涂強，康強，等.灰狼優化與差分進化的混合算法及函數優化[J].計算機科學，2017，44（9）：93-98.

[15]李茂軍，劉黃，李奇，等.基于狀態空間模型的實數編碼遺傳算法[J].山東科技大學學報（自然科學版），2015，34（03）：1-7.

[16]齊戰，李茂軍，肖雨荷，等.基于改進狀態空間模型遺傳算法的分數階PID控制器優化設計[J].控制與信息技術，2019，06：18-23.

[17]杜松，周健勇.一種差分進化和模擬退火粒子群混合算法[J].計算機仿真，2015，32（12）：218-221.