基于差分和狀態(tài)空間遺傳混合算法的信號(hào)配時(shí)優(yōu)化

陳小靜　李茂軍　張輝

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

關(guān)鍵詞：差分進(jìn)化算法;狀態(tài)空間模型遺傳算法;信號(hào)配時(shí);混合算法;平均等待時(shí)間

中圖分類(lèi)號(hào)：TP13????? 文獻(xiàn)標(biāo)識(shí)碼：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

單交叉路口交通信號(hào)控制系統(tǒng)大多采用多時(shí)段定時(shí)控制的方式，根據(jù)路口歷史通行數(shù)據(jù)把一天劃分為多個(gè)時(shí)間段，人為的設(shè)置不同的信號(hào)燈時(shí)間[1]。由于傳統(tǒng)的信號(hào)燈配時(shí)方法無(wú)法適應(yīng)復(fù)雜的交通環(huán)境和實(shí)時(shí)多變的車(chē)流量要求，不少學(xué)者開(kāi)始利用神經(jīng)網(wǎng)絡(luò)、模糊控制、自適應(yīng)控制、智能優(yōu)化算法等研究信號(hào)燈的配時(shí)優(yōu)化方案[2-5]，增強(qiáng)交叉路口的通行效率，使車(chē)輛擁堵情況得到改善 [6]。

Wu等提出了一種以十字路口的交通流量和周?chē)致房诘慕煌髁繛閰?shù)的霧計(jì)算交通燈控制系統(tǒng)[7]，它的主要原理是采用霧計(jì)算平臺(tái)計(jì)算和共享某一路口及相鄰路口的實(shí)時(shí)車(chē)流量情況，來(lái)協(xié)調(diào)多個(gè)路口之間的信號(hào)燈周期。陳丹利用混沌優(yōu)化的遍歷性改進(jìn)遺傳算法[8]，來(lái)提高初始種群的隨機(jī)性和多樣性，然后在變異操作后對(duì)部分種群進(jìn)行混沌搜索，并用該算法對(duì)城市微觀交通仿真系統(tǒng)模型進(jìn)行優(yōu)化。Qu等以路口的通行承載力最大化為目標(biāo)構(gòu)造了綠燈利用率的數(shù)學(xué)模型[9]，而且并提出了一種能夠?qū)崟r(shí)調(diào)整綠燈時(shí)間的自適應(yīng)控制方案。張文泉將模糊控制和按照誤差逆向傳播的BP神經(jīng)網(wǎng)絡(luò)融合，得到一種擁有自學(xué)習(xí)結(jié)構(gòu)的多交叉口信號(hào)協(xié)調(diào)系統(tǒng)[10]。張小雨等綜合考慮車(chē)輛起步延誤、道路的通行能力和車(chē)輛尾氣排放等因素，構(gòu)造多目標(biāo)信號(hào)配時(shí)優(yōu)化模型[11]并采用遺傳算法求最優(yōu)解。

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

1 控制策略

道路交通安全法規(guī)定，駕駛機(jī)動(dòng)車(chē)在路口右轉(zhuǎn)彎不受信號(hào)燈限制，所以這里不考慮右轉(zhuǎn)車(chē)道，單交叉路口的車(chē)流一共分為8個(gè)方向，如圖1所示。因?yàn)閚2和n5、n3和n7、n1和n6、n4和n8的車(chē)流互不干擾，所以只需要設(shè)置4個(gè)方向的綠燈時(shí)間。每個(gè)方向上有兩個(gè)車(chē)道是互不干擾的，取其中車(chē)流量較大的車(chē)道作為該方向上的實(shí)際車(chē)流量。

黃燈一般位于綠末紅初之間，時(shí)間一般為3 s，可以在此時(shí)從視頻檢測(cè)系統(tǒng)獲取各個(gè)方向的車(chē)流量和下一個(gè)分配點(diǎn)之前每輛車(chē)已經(jīng)等待的時(shí)間[12]。例如在方向4的黃燈開(kāi)始時(shí)獲取視頻檢測(cè)系統(tǒng)中的數(shù)據(jù)，那么接下來(lái)第一個(gè)信號(hào)周期的綠燈時(shí)長(zhǎng)分別為t1、t2、t3、t4，第二個(gè)信號(hào)周期的綠燈時(shí)長(zhǎng)分別為t′1、t′2、t′3、t′3，在分配點(diǎn)之前的4個(gè)方向的綠燈時(shí)間分別為t″1、t″2、t″3、t″4。

3.3 差分進(jìn)化和狀態(tài)空間模型遺傳混合算法

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

首先，用DE算法對(duì)初始種群進(jìn)行優(yōu)化，當(dāng)種群迭代Q次后，尋優(yōu)搜索空間被縮小，則進(jìn)入下一階段;用MGABS算法在已被縮小的搜索空間中進(jìn)一步尋優(yōu)迭代，找出目標(biāo)函數(shù)的最優(yōu)解。關(guān)于兩階段混合算法迭代次數(shù)的分配問(wèn)題，經(jīng)過(guò)多次試驗(yàn)總結(jié)，當(dāng)Q=0.8M時(shí)，實(shí)驗(yàn)結(jié)果相比其他迭代方式更接近最優(yōu)值，而且標(biāo)準(zhǔn)差明顯小于其他分配方式。

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

第一階段采用DE算法：

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

Step2 變異和交叉操作：根據(jù)（8）式在種群中隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行向量差分后經(jīng)過(guò)放縮，再加上第三個(gè)個(gè)體，得到變異后的新個(gè)體。將其按（9）式進(jìn)行交叉操作來(lái)產(chǎn)生試驗(yàn)個(gè)體;

Step3 選擇操作：比較試驗(yàn)個(gè)體和上一代個(gè)體，選擇其中更優(yōu)秀的粒子成為新的種群。

Step4 判斷是否滿(mǎn)足進(jìn)入下一階段的條件，若kSymbolcB@Q次則轉(zhuǎn)至Step2，否則轉(zhuǎn)至Step5;

第二階段采用MGABS算法：

Step5按照（12）式構(gòu)造狀態(tài)進(jìn)化矩陣G，將DE算法迭代Q次后的種群作為初始種群X（k），按（11）式進(jìn)行迭代，產(chǎn)生子代群體X（k+1）;

Step6計(jì)算子代群體X（k+1）的個(gè)體適應(yīng)度值。從X（k）和X（k+1）中選擇N個(gè)優(yōu)秀的個(gè)體設(shè)為下一代群體，然后置X（k+1）為X（k）;

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

Step8判斷是否完成M次迭代，若滿(mǎn)足則終止進(jìn)化;否則轉(zhuǎn)至Step5。

4 仿真結(jié)果

4.1 測(cè)試函數(shù)

為了驗(yàn)證提出的差分進(jìn)化和狀態(tài)空間模型混合算法在處理復(fù)雜優(yōu)化問(wèn)題上的尋優(yōu)精度和收斂速度，選取了5個(gè)經(jīng)典標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行尋優(yōu)能力測(cè)試。測(cè)試函數(shù)的表達(dá)式、取值范圍、全局最小值以及函數(shù)特性如下面表1所示。這5個(gè)函數(shù)分為單峰函數(shù)和多峰函數(shù)，單峰函數(shù)的作用是測(cè)試混合算法的收斂精度和收斂速度，而多峰函數(shù)具有多個(gè)的局部極大值，能夠很好的測(cè)試算法的全局搜索能力和跳出局部極值的能力。

該算法的測(cè)試環(huán)境為：采用MATLAB R2018a編程語(yǔ)言，在Intel（R）Celeron（R） CPU 1007@ 1.50 GHz、內(nèi)存4 GB的電腦上運(yùn)行程序。

4.2 測(cè)試結(jié)果分析

為了檢驗(yàn)混合算法的優(yōu)化能力，在仿真實(shí)驗(yàn)中將種群規(guī)模均設(shè)為50，粒子維度設(shè)為20，總迭代次數(shù)設(shè)為200，比較5個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次的平均值、最小值、標(biāo)準(zhǔn)差。DE算法、MGABS算法和該混合算法的性能對(duì)比結(jié)果如表2所示。

4.3 信號(hào)燈配時(shí)優(yōu)化

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

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

5 結(jié) 論

在合理的交通環(huán)境假設(shè)及約束條件下，綜合考慮了分配點(diǎn)之前車(chē)輛已經(jīng)等待的時(shí)間和在當(dāng)前配點(diǎn)后2個(gè)綠燈周期內(nèi)預(yù)計(jì)需要等待的時(shí)間，建立了以車(chē)輛平均等待時(shí)間最小為目標(biāo)的數(shù)學(xué)模型。鑒于DE算法早期能夠快速收斂、在求解復(fù)雜的多變量函數(shù)問(wèn)題上優(yōu)化效果明顯，但迭代后期收斂速度變慢、全局搜索能力差的情況，將DE算法和MGABS算法相結(jié)合，形成一種兩階段的差分進(jìn)化和狀態(tài)空間模型遺傳混合算法。實(shí)驗(yàn)結(jié)果證明，差分和狀態(tài)空間遺傳混合算法能夠?qū)さ阶詈线m的綠燈時(shí)間分配方式，完成提高交叉路口通行效率的目標(biāo)。

參考文獻(xiàn)

[1] 柳長(zhǎng)源，任宇艷，畢曉君.基于改進(jìn)螢火蟲(chóng)算法的區(qū)域交通信號(hào)配時(shí)優(yōu)化[J].控制與決策，2020，3：1-6.

[2] 羅文慧.智慧交通背景下道路交叉口交通流控制模型與算法研究[D].北京：北京交通大學(xué)，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] 劉暢，魏麗英.考慮人均延誤和人均排放的信號(hào)配時(shí)優(yōu)化模型[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2018，50（9）：83-88.

[5] 趙盼明，劉釗，劉玉，等.基于模糊控制的小區(qū)域交叉口群過(guò)飽和狀態(tài)信號(hào)協(xié)調(diào)優(yōu)化[J].交通信息與安全，2018，36（4）：51-59.

[6] 雷洋，黃承鋒.城市交通擁堵治理的研究綜述和建議[J].綜合運(yùn)輸，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] 陳丹.城市交通信號(hào)燈的仿真優(yōu)化研究[D].武漢：武漢理工大學(xué)，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]張文泉.城市區(qū)域交通信號(hào)智能控制算法分析與研究[D].成都：西南交通大學(xué)，2016.

[11]張小雨，邵春福.城鄉(xiāng)結(jié)合部道路交叉口多目標(biāo)信號(hào)配時(shí)優(yōu)化模型[J].系統(tǒng)仿真學(xué)報(bào)，2019，32（04）：709-717.

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

[13]王鼎湘.單交叉口智能交通燈配時(shí)優(yōu)化控制策略[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2015.

[14]張新明，涂強(qiáng)，康強(qiáng)，等.灰狼優(yōu)化與差分進(jìn)化的混合算法及函數(shù)優(yōu)化[J].計(jì)算機(jī)科學(xué)，2017，44（9）：93-98.

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

[16]齊戰(zhàn)，李茂軍，肖雨荷，等.基于改進(jìn)狀態(tài)空間模型遺傳算法的分?jǐn)?shù)階PID控制器優(yōu)化設(shè)計(jì)[J].控制與信息技術(shù)，2019，06：18-23.

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