基于人工魚(yú)群算法的交通信號(hào)燈配時(shí)優(yōu)化模型

吳嘯宇，李慧慧，林娟娟，房 新

(南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094)

交叉口擁堵一直是困擾城市交通的重要難題之一。為了解決該難題，合理的信號(hào)配時(shí)是十分重要的。Webster算法作為信號(hào)方案設(shè)計(jì)中最常用的算法，雖然簡(jiǎn)單易計(jì)算，但是該算法僅適用于非飽和流量的交叉口信號(hào)優(yōu)化[1]，而在城市交叉口中高峰時(shí)期往往會(huì)出現(xiàn)過(guò)飽和現(xiàn)象和嚴(yán)重的交通擁堵問(wèn)題。因此，針對(duì)這些交叉口的信號(hào)優(yōu)化，則需要去研究計(jì)算機(jī)技術(shù)和智能化算法求解信號(hào)配時(shí)優(yōu)化問(wèn)題。

為解決上述問(wèn)題，很多學(xué)者都提出了采用非線性規(guī)劃模型、多目標(biāo)控制模型及延誤模型等來(lái)改善交叉口運(yùn)行現(xiàn)狀[2-4]。文獻(xiàn)[2]提出一種以車輛排隊(duì)長(zhǎng)度以及交叉口延誤作為優(yōu)化目標(biāo)的自適應(yīng)交通信號(hào)控制方法，并結(jié)合物聯(lián)網(wǎng)實(shí)現(xiàn)動(dòng)態(tài)控制。文獻(xiàn)[3]將多交叉口的延誤指標(biāo)聯(lián)系起來(lái)，尋找延誤最低的信號(hào)時(shí)序策略。文獻(xiàn)[4]考慮了行人過(guò)街條件下的交叉口的車輛停車次數(shù)及交通事故因素，并根據(jù)其影響建立了雙階段信號(hào)優(yōu)化模型來(lái)提高交叉口通行效率和安全性。由此可見(jiàn)，在交叉口優(yōu)化研究中車輛延誤和停車次數(shù)是相當(dāng)重要的評(píng)價(jià)指標(biāo)。在構(gòu)建數(shù)學(xué)模型后，選取良好的求解算法同樣非常重要，在交叉口問(wèn)題中算法求解將更看重時(shí)效性和收斂效率。目前，求解交叉口問(wèn)題的算法研究有很多，比較成熟的有遺傳算法、蟻群算法、量子退火算法、禁忌搜素算法等[5-7]。但遺傳算法優(yōu)化過(guò)程過(guò)于復(fù)雜，在有限時(shí)間內(nèi)不易找到全局最優(yōu)解[5];蟻群算法同樣尋優(yōu)較慢，效率較低[5];量子退火算法則更適合解決局部最優(yōu)問(wèn)題[6];禁忌搜素算法更偏向于解決非飽和流條件下信號(hào)控制優(yōu)化問(wèn)題[7]。本文發(fā)現(xiàn)人工魚(yú)群算法具有對(duì)參數(shù)數(shù)值要求較低且尋優(yōu)能力較強(qiáng)的特點(diǎn)[8]，這與具有動(dòng)態(tài)性、隨機(jī)性的交叉口優(yōu)化問(wèn)題有著較高的契合性，且目前對(duì)人工魚(yú)群算法在交叉口問(wèn)題中應(yīng)用的研究較少?；诖耍疚膶⑷斯~(yú)群算法與信號(hào)控制優(yōu)化相結(jié)合，建立優(yōu)化模型并針對(duì)算法的不足進(jìn)行改進(jìn)，以優(yōu)化交叉口的通行現(xiàn)狀。

1 交通信號(hào)燈配時(shí)優(yōu)化模型

在交叉路口信號(hào)控制中，車輛延誤和停車次數(shù)兩個(gè)指標(biāo)對(duì)交叉口通行狀態(tài)具有較大影響，在本文中將以這兩個(gè)參數(shù)構(gòu)建過(guò)飽和交叉口函數(shù)優(yōu)化模型，所用到的參數(shù)表達(dá)含義如表1所示。

表1 數(shù)學(xué)模型參數(shù)含義

1.1 優(yōu)化參數(shù)的函數(shù)關(guān)系式

在目標(biāo)函數(shù)方面，本文選取并分析了車輛延誤和停車次數(shù)這兩個(gè)主要優(yōu)化目標(biāo)參數(shù)。

1.1.1 平均延誤的函數(shù)關(guān)系式

在平均延誤方面d，計(jì)算主要通過(guò)求隨機(jī)延誤dr和一致性延誤du之和來(lái)作為計(jì)算依據(jù)[9]。隨機(jī)延誤dri和一致性延誤dui的計(jì)算過(guò)程如式(1)和(2)

(1)

(2)

λi=gei/C

(3)

本文所需的平均延誤DI的計(jì)算可以通過(guò)不同信號(hào)相位的平均延誤進(jìn)行加權(quán)計(jì)算所得

di=dui+dri

(4)

(5)

1.1.2 平均停車次數(shù)的函數(shù)關(guān)系式

在平均停車次數(shù)方面為使交叉口正常通行，應(yīng)盡量避免車輛二次停車，爭(zhēng)取一個(gè)周期內(nèi)車輛全放完。平均停車次數(shù)為hi的計(jì)算過(guò)程如式(6)

(6)

本文所需要的車輛平均停車次數(shù)HI的計(jì)算方式同DI，通過(guò)加權(quán)計(jì)算所得

(7)

1.2 交通信號(hào)燈配時(shí)的函數(shù)模型

在構(gòu)建目標(biāo)函數(shù)時(shí)，本文所期望達(dá)到的效果是，平均延誤和平均停車次數(shù)最小，以達(dá)到良好的道路通行狀態(tài)。由上兩者的量綱不同，本文要對(duì)這兩個(gè)參數(shù)進(jìn)行無(wú)量綱化，在此處取β作為轉(zhuǎn)換參數(shù)，將停車次數(shù)轉(zhuǎn)換為時(shí)間單位。同時(shí)本文考慮到這兩個(gè)參數(shù)在不同的交通條件下對(duì)實(shí)際交叉口通行能力具有不同的影響。因此引入加權(quán)系數(shù)α將這兩種參數(shù)指標(biāo)統(tǒng)一起來(lái)進(jìn)行優(yōu)化。α、β值取決于實(shí)際交叉口的交通狀況，本文案例中α值取0.5，β值取C/2。本文基于以上描述建立了交叉口函數(shù)優(yōu)化模型，其目標(biāo)函數(shù)為

f(x)=F(DI，HI)

(8)

minf(x)=minF(DI，HI)=

(9)

除目標(biāo)函數(shù)外，一個(gè)完整的數(shù)學(xué)模型約束條件也是必不可少的。一般情況下，n表示信號(hào)相位數(shù)時(shí)，信號(hào)周期應(yīng)滿足大于等于15*n，且小于等于200s的要求[9]。周期時(shí)間由綠燈時(shí)間和損失時(shí)間L兩部分構(gòu)成。交叉口保持良好的通行狀態(tài)需飽和度xi滿足0.6～0.9，同時(shí)信號(hào)配時(shí)的最小綠燈時(shí)間需滿足行人過(guò)街的要求。所以有式(10)、式(11)、式(12)

15*n≤C≤200

(10)

(11)

0.6≤xi≤0.9

(12)

綜上所述，本文求解信號(hào)配時(shí)最優(yōu)化問(wèn)題所建立的數(shù)學(xué)模型為

(13)

2 基于人工魚(yú)群算法的優(yōu)化模型求解

人工魚(yú)群算法具有收斂效率高、初始數(shù)據(jù)和參數(shù)設(shè)置要求低、整體收斂性好等優(yōu)勢(shì)，主要以魚(yú)基礎(chǔ)生活最多的位置便是營(yíng)養(yǎng)最豐富的地方為基本尋優(yōu)原理，通常算法實(shí)現(xiàn)模型求解主要通過(guò)人為設(shè)置尋食的人工魚(yú)群使其模仿魚(yú)類基本行為來(lái)探尋最優(yōu)解，其核心思想是群體中個(gè)體之間的協(xié)作和信息共享，與粒子群算法類似[10]。本文將對(duì)人工魚(yú)群算法的函數(shù)表達(dá)進(jìn)行部分說(shuō)明，并結(jié)合算法不足進(jìn)行部分改進(jìn)，得出改進(jìn)后的算法流程圖。

2.1 人工魚(yú)群算法的函數(shù)描述

人工魚(yú)群算法執(zhí)行時(shí)的主要變量有:群規(guī)模N、人工魚(yú)視野Visual、步長(zhǎng)Step、擁擠度因子δ、算法次數(shù)Try_number、個(gè)體狀態(tài)X=(x1，x2，…，xn)、人工魚(yú)個(gè)體i和j的距離dij=|xi-xj|等。人工魚(yú)群算法執(zhí)行的函數(shù)部分包括:人工魚(yú)當(dāng)前狀態(tài)的目標(biāo)濃度Y=f(x)、覓食行為Prey、聚群行為Swarm、追尾行為Follow、隨機(jī)行為Move等[11]。本文中不同的信號(hào)配時(shí)方案對(duì)應(yīng)的便是不同的人工魚(yú)狀態(tài)，求得的便是目標(biāo)函數(shù)最小時(shí)的信號(hào)方案。

2.1.1 覓食行為Prey的函數(shù)關(guān)系式

人工魚(yú)由狀態(tài)Xi于視野內(nèi)選擇并轉(zhuǎn)變?yōu)闋顟B(tài)Xj;計(jì)算兩者的目標(biāo)值Yi、Yj，評(píng)價(jià)時(shí)若Yj優(yōu)于Yi，則將Xi向Xj移動(dòng);否則進(jìn)行循環(huán)尋找。若達(dá)到次數(shù)上限仍未找到，則發(fā)生隨機(jī)行為

Xj=Xi+Visual*Rand

(14)

(15)

2.1.2 聚群行為Swarm的函數(shù)關(guān)系式

Xi在dijδYi，則Xi向Xc移動(dòng)。

(16)

2.1.3 追尾行為Follow的函數(shù)關(guān)系式

Xi在dijδYi，則Xi向Xj移動(dòng)。

(17)

2.1.4 隨機(jī)行為Move的函數(shù)關(guān)系式

人工魚(yú)可以在dij

(18)

2.2 人工魚(yú)群算法的改進(jìn)流程

本文針對(duì)人工魚(yú)群算法存在全局優(yōu)化能力低、容易落入局部最佳的弊端，通過(guò)結(jié)合混沌搜索理論來(lái)提高算法全局尋優(yōu)能力[11]，對(duì)算法改進(jìn)的實(shí)現(xiàn)流程如下。

步驟0假設(shè)一個(gè)優(yōu)化n維變量的問(wèn)題，其中第i維決策變量xi的范圍為xmin，i

(19)

(20)

(21)

由于結(jié)合混沌搜索后，提高了原算法的全局尋優(yōu)能力的同時(shí)也變相的提高了算法的復(fù)雜程度，計(jì)算量大大增加。為了避免算法尋優(yōu)時(shí)間過(guò)長(zhǎng)，本文在引入混沌搜索的基礎(chǔ)上，同時(shí)將決策論中的反饋策略[12]與本文使用的主算法進(jìn)行結(jié)合。本文將反饋概率因子Pfb引入到算法的實(shí)際計(jì)算過(guò)程中。人工魚(yú)的隨機(jī)行為以概率Pfb發(fā)生，人工魚(yú)的反饋行為以概率(1-Pfb)發(fā)生，且在整個(gè)優(yōu)化過(guò)程中概率因子Pfb會(huì)隨著優(yōu)化的進(jìn)行不斷降低，用公式表示便是Pfb=γPfb，其中γ為衰減因子。通過(guò)結(jié)合反饋策略，便可以一定程度上確保在算法運(yùn)行前期，人工魚(yú)可以執(zhí)行更多的隨機(jī)行為，提高算法全局尋優(yōu)能力;在算法運(yùn)行后期，人工魚(yú)便會(huì)執(zhí)行更多的反饋行為，提高算法運(yùn)行的效率。綜上，得到改進(jìn)后算法的執(zhí)行流程見(jiàn)圖1(a)，并為了體現(xiàn)改進(jìn)人工魚(yú)群算法的優(yōu)越性，本文以傳統(tǒng)函數(shù)式(22)的全局極大值為例，在[-500，500]區(qū)間上進(jìn)行求解，對(duì)比改進(jìn)前后結(jié)果發(fā)現(xiàn)改進(jìn)后得到的極大值837.965 8明顯優(yōu)于改進(jìn)前的結(jié)果，且改進(jìn)后算法的收斂效率得到了明顯提高，具體迭代過(guò)程見(jiàn)圖1(b)。

圖1 改進(jìn)后人工魚(yú)群算法性能的驗(yàn)證

(22)

3 案例分析

為使本文論證更加具有現(xiàn)實(shí)意義，本文將采用焦作市塔南路與工業(yè)路交叉口作為實(shí)際案例進(jìn)行建模與優(yōu)化。該交叉口為常規(guī)十字交叉口，在工業(yè)路東西向上為三車道設(shè)計(jì)，分別為左轉(zhuǎn)、直行、直右;在塔南路南北向上為四車道設(shè)計(jì)，分別為左轉(zhuǎn)、直行、直行、直右。

3.1 案例交叉口現(xiàn)狀分析

本文在把公交車按照規(guī)定折算為標(biāo)準(zhǔn)小汽車后，得到流量分布圖。通過(guò)現(xiàn)場(chǎng)調(diào)查及數(shù)據(jù)發(fā)現(xiàn)高峰期出現(xiàn)了明顯的交通擁堵的問(wèn)題。詳細(xì)的交叉口平峰和高峰小時(shí)流量圖如圖2。

圖2 交叉口平高峰小時(shí)流量圖

3.1.1 飽和流量計(jì)算

具體計(jì)算結(jié)果見(jiàn)表2，表中數(shù)據(jù)顯示塔南路和工業(yè)路的車流較為穩(wěn)定。

表2 交叉口飽和流量數(shù)據(jù)表

3.1.2 信號(hào)配時(shí)現(xiàn)狀

作為配時(shí)優(yōu)化所需的核心，通過(guò)調(diào)查可知該交叉口為五相位控制的交叉口，周期為155 s，右轉(zhuǎn)不受信號(hào)控制。具體的交叉口信號(hào)控制狀況見(jiàn)圖3、圖4。

圖3 交叉口信號(hào)相位圖

圖4 交叉口信號(hào)配時(shí)圖

3.1.3 交叉口沖突點(diǎn)分析

從圖5中明顯看出信號(hào)控制中的第4相位沖突情況比較嚴(yán)重。

圖5 交叉口沖突點(diǎn)分布圖

3.2 交叉口的控制優(yōu)化

根據(jù)以上調(diào)查數(shù)據(jù)，可知該交叉口主要在高峰期間具有明顯的交通擁堵問(wèn)題，且高峰時(shí)交叉口飽和度很可能會(huì)大于0.9導(dǎo)致韋伯斯特配時(shí)法的失效。因此本文將著重從高峰時(shí)段交叉口現(xiàn)狀入手，解決其交叉口通行問(wèn)題。

3.2.1 計(jì)算流量比判斷計(jì)算條件

由于右轉(zhuǎn)不受信號(hào)相位控制，故不作考慮。各方向流量比為工業(yè)路(東直行:0.25、東左轉(zhuǎn):0.009、西直行:0.24、西左轉(zhuǎn):0.133)和塔南路(南直行:0.271、南左轉(zhuǎn):0.13、北直行:0.45、北左轉(zhuǎn):0.125)。由此計(jì)算總的流量比Y。

Y=0.133+0.25+0.13+0.45+0.45=1.413

(23)

從式(23)明顯可知，在本例中1.413>0.9，不滿足Webster算法計(jì)算條件[1]，因此需要使用智能算法進(jìn)行優(yōu)化。從上述現(xiàn)狀分析的交叉口沖突點(diǎn)圖中，可以明顯看出該交叉口第四相位有明顯的交通沖突，因此在優(yōu)化其信號(hào)配時(shí)前應(yīng)先對(duì)其信號(hào)相序進(jìn)行調(diào)整，結(jié)果見(jiàn)圖6。

圖6 調(diào)整后的交叉口信號(hào)相位圖

3.2.2 基于人工魚(yú)群算法的模型求解

實(shí)現(xiàn)方式為使用JAVA語(yǔ)言編寫(xiě)程序，主要包含算法的執(zhí)行、函數(shù)的求解、公告牌的更新、人工魚(yú)的行為描述、判斷算法執(zhí)行結(jié)果是否滿足條件。在改進(jìn)算法方面，應(yīng)用混沌搜索和反饋策略，若人工魚(yú)覓食行為嘗試tryTime次后，可通過(guò)混沌算法移至下一次的位置，同時(shí)引入變量bestfish記錄人工魚(yú)的最優(yōu)狀態(tài)，通過(guò)比選結(jié)果對(duì)其進(jìn)行更新，提高全局優(yōu)化能力[13]。其中主要用到的函數(shù)模塊見(jiàn)表3。

表3 實(shí)現(xiàn)算法的函數(shù)模塊

在使用Java編寫(xiě)人工魚(yú)群算法程序時(shí)需要設(shè)置以下參數(shù)，見(jiàn)表4。

表4 實(shí)現(xiàn)算法設(shè)置的參數(shù)變量

最終結(jié)果通過(guò)在 Eclipse軟件(設(shè)備為Intel i5-5200U CPU@2.20GHz64位計(jì)算機(jī))下求解出了該交叉口優(yōu)化后的配時(shí)方案。優(yōu)化后總周期為126 s，各相位綠燈時(shí)間為49 s、21 s、27 s、17 s，黃燈時(shí)間為3 s。具體結(jié)果和優(yōu)化后信號(hào)相位見(jiàn)圖7所示。

圖7 優(yōu)化后的交叉口信號(hào)配時(shí)圖

3.2.3 使用VISSIM對(duì)交叉口進(jìn)行仿真評(píng)價(jià)

分別在各進(jìn)口道處設(shè)置檢測(cè)器，其中檢測(cè)器1～3分別測(cè)定西進(jìn)口左直右車輛狀況，4～6分別測(cè)定東進(jìn)口左直右車輛狀況，7～9分別測(cè)定北進(jìn)口左直右車輛狀況，10～12分別測(cè)定南進(jìn)口左直右車輛狀況。本文在VISSIM中分別置入優(yōu)化前后的信號(hào)方案并進(jìn)行仿真實(shí)驗(yàn)，圖8顯示了使用VISSIM進(jìn)行仿真的主要過(guò)程。

圖8 VISSIM仿真過(guò)程

仿真結(jié)束后，本文將采用多次評(píng)價(jià)并求和的方式來(lái)減少實(shí)驗(yàn)誤差并統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果。為了體現(xiàn)本文研究的創(chuàng)新性和算法優(yōu)越性，在仿真部分引入傳統(tǒng)優(yōu)化方法(遺傳算法優(yōu)化信號(hào)配時(shí))進(jìn)行對(duì)比，其中該案例交叉口在不同配時(shí)方案下的總延誤及總停車次數(shù)對(duì)比見(jiàn)表5。

表5 不同配時(shí)方案下的仿真結(jié)果對(duì)比表

不同配時(shí)方案下交叉口的改善情況見(jiàn)圖9，圖中主要將不同位置的平均延誤和平均停車次數(shù)進(jìn)行比較。其中橫坐標(biāo)的數(shù)字1～12對(duì)應(yīng)的分別為VISSIM模型中檢測(cè)器所測(cè)定的位置。

圖9 不同配時(shí)方案下仿真結(jié)果對(duì)比圖

從圖9中可以直觀地看出，本文優(yōu)化方案的結(jié)果明顯比原方案更優(yōu)，在該配時(shí)方案下有效降低了交叉口產(chǎn)生的延誤和停車次數(shù)，改善了路段通行現(xiàn)狀。相較于傳統(tǒng)優(yōu)化方案而言，本文的優(yōu)化方案在多處檢測(cè)器測(cè)定位置下的實(shí)驗(yàn)結(jié)果均優(yōu)于傳統(tǒng)方案，且總延誤和總停車次數(shù)也要更小，這可能是因?yàn)榈螖?shù)50次較少導(dǎo)致遺傳算法未找到更優(yōu)的解。實(shí)驗(yàn)表明，使用人工魚(yú)群算法對(duì)信號(hào)配時(shí)優(yōu)化問(wèn)題進(jìn)行求解，具有研究的實(shí)際意義和算法優(yōu)越性。

4 結(jié)束語(yǔ)

本文主要研究了交叉口信號(hào)優(yōu)化問(wèn)題，通過(guò)使用改進(jìn)的人工魚(yú)群算法進(jìn)行求解優(yōu)化模型，得到更優(yōu)的信號(hào)配時(shí)方案，從而有效地減少了交叉口延誤和停車次數(shù)，改善了目標(biāo)交叉口的交通狀況。在案例分析中，展示了本文研究方向在實(shí)際應(yīng)用中的可行性，并得出了結(jié)論通過(guò)人工魚(yú)群算法改進(jìn)的信號(hào)配時(shí)方案明顯優(yōu)于原方案和傳統(tǒng)優(yōu)化方案，表明了人工魚(yú)群算法改善交叉口交通狀況的研究具有現(xiàn)實(shí)意義和優(yōu)越性。在研究前景方面，未來(lái)可將人工魚(yú)群算法不斷完善使其更加適用于解決不同交通流條件下路網(wǎng)通行能力改善問(wèn)題，實(shí)現(xiàn)實(shí)時(shí)調(diào)整交叉口綠燈時(shí)間，從而使得道路交通系統(tǒng)能便捷、高效、通暢、安全、環(huán)保的運(yùn)行。