多策略改進哈里斯鷹算法的交通信號配時優(yōu)化

宿夢夢，趙曉蕾，趙洪鑾，鄒 煒，李曉君

(1.山東建筑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山東 濟南 250101；2.山東建筑大學(xué) 建筑城規(guī)學(xué)院，山東 濟南 250101)

0 引 言

城市的快速發(fā)展加上人口的增長，導(dǎo)致道路上的車輛呈指數(shù)形式增長，這加劇了本就不堪重負(fù)的交通擁堵問題，而交叉口是發(fā)生交通擁堵的主要地段，因此，對交叉口進行合理的優(yōu)化設(shè)計是提高道路通行能力的重要手段。對交叉口進行優(yōu)化的方案有很多，其中城市道路擴建這種昂貴又短視的解決方案不再適用，一種有效的道路資源分配方法是交通信號燈的時間安排[1]。合理的信號配時方案可以有效緩解交通擁堵[2]，因此做好交叉口的信號配時安排至關(guān)重要[3]。

國內(nèi)外學(xué)者在交叉口信號配時上做了很多研究，甘楊杰[4]采用整體優(yōu)化的思想，以機動車延誤、非機動車延誤、行人延誤、停車次數(shù)和通行能力這五項指標(biāo)作為目標(biāo)函數(shù)，通過遺傳算法對其進行求解并通過VISSIM仿真軟件進行驗證，但是并沒有對算法進行改進。羅文慧[5]根據(jù)車輛延誤、停車次數(shù)和通行能力構(gòu)建多目標(biāo)模型，通過改進的蜻蜓算法對模型進行求解，但是并未考慮到尾氣排放。牟海維等[6]從交通效益和環(huán)保角度出發(fā)，在改進的Webster模型的基礎(chǔ)上加入尾氣排放指標(biāo)，利用改進的粒子群算法對目標(biāo)函數(shù)求解最佳周期，但是低峰時段的通行能力并未得到改善。柳長源等[7]在傳統(tǒng)螢火蟲算法的基礎(chǔ)上加入一種驅(qū)散機制和變異操作，建立以區(qū)域總延誤最小為目標(biāo)的配時模型進行優(yōu)化，但是只考慮車輛延誤這一指標(biāo)不能很好地反映交叉口的交通情況。

綜上所述，大部分學(xué)者都是通過建立目標(biāo)函數(shù)，使用元啟發(fā)式算法進行求解或通過仿真軟件得出結(jié)果。與其他元啟發(fā)式算法相比，HHO算法是一種快速、強大、高性能的算法，具有很強的競爭力，并且通過加入混沌映射、柯西函數(shù)和隨機噪聲干擾，可以增加HHO算法的種群多樣性，提高算法的尋優(yōu)精度和收斂速度。因此，該文在Webster模型的基礎(chǔ)上考慮環(huán)保因素，構(gòu)建以平均延誤、停車率、通行能力和尾氣排放為指標(biāo)的信號配時模型，使用改進后的HHO算法對模型求解，獲得綜合效益最高的信號配時方案。

1 交通信號配時問題

交叉口信號配時的目標(biāo)是獲得最大的通行能力、最小的車輛延誤、最短的排隊長度、最少的停車次數(shù)、最少的尾氣排放等。其中通行能力、車輛延誤和停車次數(shù)是評價交叉口交通情況的重要指標(biāo)，而隨著環(huán)保形勢的日益嚴(yán)峻，尾氣排放也是必須要考慮的指標(biāo)，因此，該文取車輛延誤、通行能力、停車次數(shù)、尾氣排放為目標(biāo)進行模型構(gòu)建。

1.1 機動車平均延誤模型

機動車平均延誤是指機動車通過交叉口的額外平均消耗時間，該文采用Webster延誤模型計算機動車平均延誤，公式如下[8]：

(1)

(2)

式中，Di是第i相位車輛通過交叉口的延誤時間；C是最佳信號周期時長；λi是綠信比，第i相位的有效綠燈時間與信號周期比值，λi=gi/C；yi是第i相位的流量比；qi是第i相位的實際到達的當(dāng)前交通量；D是交叉口的平均延誤時間。

1.2 停車次數(shù)模型

停車次數(shù)是指車輛受信號燈影響在交叉口產(chǎn)生的平均停車次數(shù)，平均停車次數(shù)模型計算公式為[9]：

(3)

(4)

式中，Hi是第i相位的平均停車次數(shù)；gi是第i相位有效綠燈時間；H是交叉口的平均停車次數(shù)。

1.3 通行能力模型

通行能力是指車輛以正常速度連續(xù)不斷通過交叉口，一小時內(nèi)的最大車流量，通行能力模型計算公式為[10]：

(5)

(6)

式中，Qi是第i相位的車輛通行能力；sij是第i相位第j個進口道的飽和流率；Q是交叉口的車輛通行能力。

1.4 尾氣排放模型

車輛在行駛過程中會排放尾氣，尾氣的增加會加劇環(huán)境污染，尾氣控制是必須要考慮的問題。車輛在行駛過程中的加減速都會增加尾氣的排放，而車輛在交叉口會頻繁加減速。車輛在交叉口的尾氣排放模型計算公式為[11]：

(7)

式中，Ei是第i相位的車輛尾氣排放；e是單位怠速排放因子，取5g/(pch·h)。

1.5 目標(biāo)函數(shù)的構(gòu)建

該文從交叉口的實際情況出發(fā)，建立以車輛延誤、停車次數(shù)、通行能力和尾氣排放為指標(biāo)的信號配時模型。但是這四個指標(biāo)之間關(guān)系復(fù)雜，需要找出一個最佳的信號周期和各相位有效綠燈時間，使車輛延誤、停車次數(shù)和尾氣排放達到最小值，通行能力達到最大值，需要給這四項指標(biāo)分配不同的權(quán)值，將其換算成同一標(biāo)準(zhǔn)下進行計算，最后求解目標(biāo)函數(shù)的最小值，模型計算公式如下：

(8)

(9)

2 HHO算法及其改進思想

HHO算法是由Heidari等人[12]在2019年提出的一種新型群智能算法，它是一種快速、強大且高性能的優(yōu)化算法，該算法模仿了哈里斯鷹在自然界中搜索和追逐獵物的方式，與其他啟發(fā)式算法相比，該算法具有很強的競爭力。但傳統(tǒng)的HHO算法存在收斂速度慢、尋優(yōu)精度低、易陷入局部最優(yōu)等不足，所以很多學(xué)者提出了不同的改進策略對傳統(tǒng)的HHO算法進行了改進。劉小龍等[13]通過設(shè)置方形鄰域拓?fù)浣Y(jié)構(gòu)和隨機數(shù)來跳出局部最優(yōu)。朱誠等[14]將細菌覓食算法的趨化校正機制引入來提高尋優(yōu)精確度，并將生物運動時的能量消耗規(guī)律融入能量因子E來平衡算法的探索與開發(fā)階段。陳功等[15]提出一種融合互利共生和透鏡成像反向?qū)W習(xí)的HHO算法，算法的收斂速度更快、尋優(yōu)精度更高。Sihwail R等[16]通過引入精英反向?qū)W習(xí)機制和三種搜索策略提高算法的全局搜索能力，避免陷入局部最優(yōu)。Li C Y等[17]通過提出一種基于對數(shù)螺旋和對立學(xué)習(xí)的探索策略來提高算法的探索能力。

針對傳統(tǒng)HHO算法存在的問題，從三個方面對算法進行了改進。首先，在算法迭代前進行混沌初始化產(chǎn)生初始種群，使個體均勻分布在解空間，提高算法的搜索能力；其次，用柯西函數(shù)控制萊維飛行的步長，實現(xiàn)平滑過渡，提高算法的尋優(yōu)精度；最后，在迭代后期加入隨機噪聲干擾，提高變異能力和收斂速度。

2.1 HHO算法基本思想

HHO算法包括全局探索階段和局部開發(fā)階段,每個階段的具體描述如下。

2.1.1 全局探索階段

在這一階段，提出了HHO的探索機制。在HHO中，哈里斯鷹隨機棲息在某些位置，并根據(jù)兩種策略等待發(fā)現(xiàn)獵物，每一個策略的機會均等。

X(t+1)=

(10)

式中，X(t+1)是下一次迭代中鷹的位置，Xrabbit(t)是當(dāng)前最優(yōu)解的位置，X(t)是鷹的當(dāng)前位置，r1、r2、r3、r4和q是(0,1)內(nèi)的隨機數(shù)，UB和LB分別是種群的上下界，Xrand(t)是從當(dāng)前種群中隨機選擇的個體，Xm(t)是當(dāng)前種群的平均位置。

(11)

2.1.2 過渡階段

HHO算法根據(jù)獵物的逃逸能量，從探索階段轉(zhuǎn)移到開發(fā)階段。在逃跑行為中，計算公式如下：

(12)

式中，E為獵物的逃逸能量，T為最大迭代次數(shù)，E0為能量的初始狀態(tài)，是(-1,1)內(nèi)的隨機數(shù)。

2.1.3 局部開發(fā)階段

在這一階段，哈里斯鷹通過攻擊前一階段檢測到的目標(biāo)獵物進行突襲，而獵物則試圖逃離。用r表示獵物成功逃脫的概率，用參數(shù)E模擬哈里斯鷹的圍攻策略。

Case1：軟圍攻。

當(dāng)r≥0.5且|E|≥0.5時，獵物有足夠的能量，并試圖通過隨機跳躍逃跑，但最終逃跑失敗。哈里斯鷹通過軟圍攻對獵物進行突襲，位置更新公式如下：

X(t+1)=ΔX(t)-E|JXrabbit(t)-X(t)|

(13)

ΔX(t)=Xrabbit(t)-X(t)

(14)

式中，J=2(1-r5)表示獵物在逃逸過程中的隨機跳躍強度。

Case2：硬圍攻。

當(dāng)r≥0.5且|E|<0.5時，獵物精疲力竭，逃逸能量低。哈里斯鷹通過硬圍攻進行突然襲擊，位置更新公式如下：

X(t+1)=Xrabbit(t)-E|ΔX(t)|

(15)

Case3：以漸進式快速俯沖進行軟圍攻。

當(dāng)r<0.5且|E|≥0.5時，獵物有足夠的能量成功逃脫，哈里斯鷹在襲擊之前仍然進行軟圍攻，實施兩種策略，當(dāng)?shù)谝粋€策略無效時，執(zhí)行第二個策略。

Y=Xrabbit(t)-E|JXrabbit(t)-X(t)|

(16)

Z=Y+S×LF(D)

(17)

式中，D是問題的維數(shù)，S是D維的隨機向量，LF是levy飛行函數(shù)，計算公式如下：

(18)

式中，β是設(shè)置為1.5的默認(rèn)常量，因此，該階段位置更新的最終策略如下：

(19)

Case4：以漸進式快速俯沖進行硬圍攻。

當(dāng)r<0.5且|E|<0.5時，獵物沒有足夠的能量逃跑，因此，在襲擊并捕殺獵物之前會進行一次硬圍攻，哈里斯鷹試圖縮短與獵物的平均位置距離，位置更新策略如下：

(20)

Y=Xrabbit(t)-E|JXrabbit(t)-Xm(t)|

(21)

Z=Y+S×LF(D)

(22)

2.2 混沌初始化

初始化種群是否均勻分布在解空間中，是影響算法收斂速度和尋優(yōu)精度的一個重要因素[18]?；煦缱兞烤哂辛己玫谋闅v性和隨機性，在保證種群多樣性的同時還能提高算法的全局搜索能力?；煦绯跏蓟脑砭褪腔煦缭恚愃坪?yīng)，在初始階段很小的差異經(jīng)過迭代后可能會產(chǎn)生巨大的差別。利用這一特性，在初始化階段生成混沌序列，經(jīng)過若干次迭代之后就可遍布解空間。為了使初始哈里斯鷹種群均勻分布在解空間中，該文采用Logistic混沌映射初始化種群，Logistic混沌映射公式如下：

Zn+1=Zn×μ×(1-Zn)

(23)

式中，μ為Logistic控制參數(shù)，且μ∈[0,4]，Z∈[0,1]，該文取μ=4。將產(chǎn)生的混沌序列映射到新的解空間中：

X(t+1)=XL+(XU-XL)×Zn+1

(24)

式中，X(t+1)為哈里斯鷹的位置，XU和XL為解空間的上下界，Zn+1為上式中產(chǎn)生的混沌序列。

2.3 柯西自適應(yīng)萊維飛行

萊維飛行是一種幫助算法跳出局部最優(yōu)解的策略[19]，在傳統(tǒng)的HHO算法中萊維飛行采用固定的步長值，在搜索過程中有很大概率出現(xiàn)大步長，這種步長在搜索后期會弱化算法的精確度。因此，文中采用柯西函數(shù)控制萊維飛行的步長，柯西函數(shù)是一種平滑遞減的函數(shù)，將萊維飛行步長從搜索初期的大步長逐漸縮小為后期的小步長，實現(xiàn)平滑過渡。

基于以上分析，將式(9)中的β由固定值1.5改為下式的自適應(yīng)步長：

(25)

2.4 隨機噪聲干擾

在算法搜索后期，哈里斯鷹種群大多數(shù)個體會聚集在一個很小的區(qū)域內(nèi)，這時候個體相似度急劇升高，最優(yōu)解可能經(jīng)過多次迭代都不更新，算法進行無效的搜索，這就弱化了算法的開采能力且浪費計算資源。所以，該文對個體進行隨機白噪聲干擾，增強算法跳出局部最優(yōu)的能力，提高收斂速度。模型如下：

X(t+1)=α×X*(t+1)

(26)

α=(1+0.1×r6)

(27)

式中，X(t+1)為干擾后哈里斯鷹的位置，X*(t+1)為干擾前哈里斯鷹的位置，α是系數(shù)且服從正態(tài)分布，r6是(0,1)內(nèi)的隨機數(shù)。

改進的哈里斯鷹算法(HHOG)，從多方面增強了算法的搜索尋優(yōu)性能，算法流程如圖1所示。

2.5 HHOG算法性能測試

在Matlab R2017b中，測試比較HHOG與HHO算法的性能。設(shè)置種群數(shù)量為30，迭代次數(shù)為100，共有參數(shù)保持一致。該文選取9個不同特點的測試函數(shù)進行算法優(yōu)化的對比實驗，包括3個單峰測試函數(shù)、4個多峰測試函數(shù)和2個固定維度測試函數(shù)，具體信息如表1所示。

為了更直觀展示HHOG算法的尋優(yōu)性能，由測試函數(shù)收斂圖2可知，HHOG算法的收斂精度和收斂速度都遠遠高于傳統(tǒng)的HHO算法。f1～f3是單峰測試函數(shù)，常用來測試算法的收斂能力，由f1～f3的收斂曲線圖可知，HHOG算法的收斂精度明顯提高；f4～f7是多峰測試函數(shù)，最優(yōu)值均為0，由收斂曲線圖可知，HHOG算法的收斂速度明顯提高，且均在50到100之間達到最優(yōu)值，說明HHOG算法具有更高的收斂速度；f8～f9是固定維度測試函數(shù)，由收斂曲線圖可知，在迭代過程中出現(xiàn)了多個拐點，證明改進后的算法更容易跳出局部最優(yōu)解，具有更好的全局搜索能力。

圖1 HHOG算法流程 表1 測試函數(shù)

分類測試函數(shù)維度范圍最優(yōu)值單峰測試函數(shù)f1(x)=∑ni=1x2i30 [-100,100]0f2(x)=∑ni=1xi+∏ni=1xi30 [-10,10]0f3(x)=∑ni=1(∑ij-1xj)230[-100,100]0多峰測試函數(shù)f4(x)=∑ni=1[x2i-10cos(2πxi)+10]30 [-5.12,5.12]0f5(x)=-20exp(-0.21n∑ni=1x2i)-exp(1n∑ni=1cos(2πxi))+20+e30 [-32,32]0f6(x)=14 000∑ni=1x2i-∏ni=1cos(xii)+130 [-600,600]0f7(x)=0.1{sin2(3πx1)+∑ni=1(xi-1)2[1+sin2(3πxi+1)]+(xn-1)2[1+sin2(2πxn)]}+∑ni=1μ(xi,5,100,4)30 [-50,50]0固定維度測試函數(shù)f8(x)=∑11i=1[ai-x1(b2i+bix2)b2i+bix3+x4]24 [-5,5]0.000 3f9(x)=4x21-2.1x41+13x61+x1x2-4x22+4x422[-5,5]-1.031 6

圖2 測試函數(shù)收斂曲線

3 基于HHOG的信號配時應(yīng)用

某十字交叉口由東西向和南北向兩條主干道組成，位于城市內(nèi)重要路段，對交通有重要影響，該交叉口是典型的四相位信號燈控制，如圖3所示。結(jié)合文獻[6]，該路口的車流量數(shù)據(jù)如表2所示。

圖3 交叉口相位示意圖 表2 某交叉口實際交通流量數(shù)據(jù)

進口道車道高峰期通過的車輛數(shù)/(pcu/h)低峰期通過的車輛數(shù)/(pcu/h)北左轉(zhuǎn)236181直行269221西左轉(zhuǎn)150121直行806634南左轉(zhuǎn)10165直行209165東左轉(zhuǎn)211167直行1 037819

該交叉口各個車道的機動車飽和流量為1 912 pcu/h，損失時間L=15，各相位最小綠燈時間為15 s，最大綠燈時間不超過60 s。該文使用HHOG算法對建立的非線性多目標(biāo)函數(shù)進行求解，利用HHOG算法可以分別求得高峰時段的最佳信號周期和低峰時段的最佳信號周期，進而可以求得該配時方案下的四個指標(biāo)，如表3所示。

表3 不同配時方案仿真結(jié)果對比

將文中方案與交叉口當(dāng)前方案、Webster方法和改進的PSO算法進行比對，由表3可知，在交通流量高峰時段，使用文中的配時方案可以使車輛平均延誤降低48%，車輛的通行能力提高34.5%，尾氣排放降低43.7%，停車次數(shù)幾乎不變。在交通流量低峰時段，可以使車輛平均延誤降低24.5%，車輛的通行能力提高33.1%，尾氣排放降低8.9%，停車次數(shù)幾乎不變。為驗證HHOG算法的有效性，繼續(xù)對另一交叉口[20]信號配時問題進行求解，該交叉口交通流量數(shù)據(jù)如表4所示，仿真結(jié)果對比如表5所示。

表4 交叉口流量數(shù)據(jù)

表5 不同配時方案仿真結(jié)果對比

經(jīng)過上述對比可以發(fā)現(xiàn)，所提出的配時方案在交通流量高峰和低峰時段可以有效降低車輛延誤和尾氣排放，提高通行能力。同時可以看出改進后的HHOG算法的優(yōu)化結(jié)果優(yōu)于Webster算法，體現(xiàn)了HHOG算法的優(yōu)越性。

4 結(jié)束語

針對HHO算法存在收斂精度低、易陷入局部最優(yōu)的問題，將混沌映射、柯西函數(shù)和隨機噪聲干擾引入傳統(tǒng)HHO算法中，提高了算法的尋優(yōu)精度和收斂速度。針對交叉口信號配時問題，建立以平均延誤、停車次數(shù)、尾氣排放最小和通行能力最大的配時模型，運用HHOG算法進行求解。實驗結(jié)果表明，HHOG算法能有效改進交叉口信號配時，使平均延誤、尾氣排放和通行能力指標(biāo)明顯改進。下一步可以繼續(xù)考慮非機動車和行人出行等因素，并結(jié)合智能算法進行優(yōu)化，更全面解決交叉口的信號配時問題。