基于改進(jìn)鯨魚優(yōu)化算法的多目標(biāo)信號(hào)配時(shí)優(yōu)化

吳小龍，胡 松，成 衛(wèi)

（1.昆明阡陌交通工程咨詢有限公司，云南昆明650028；2.昆明理工大學(xué)交通工程學(xué)院，云南 昆明650500）

0 引言

我國(guó)經(jīng)濟(jì)的高速發(fā)展大大刺激了國(guó)民的物質(zhì)需求，私家車出行因?yàn)槠潇`活性和方便性也因此被越來越多的人選擇.由于城市化的推進(jìn)和私家車保有量的快速提高，城市交通問題已成為影響城市經(jīng)濟(jì)發(fā)展的一個(gè)重要因素.我國(guó)的早期交通規(guī)劃化與和現(xiàn)有的通行能力需求并不成正比，城市路網(wǎng)負(fù)荷超標(biāo)嚴(yán)重，導(dǎo)致大量城市出現(xiàn)了擁堵的情況.為了在現(xiàn)有的交通條件下盡可能提升交通效益、減少城市的擁堵狀況，對(duì)交叉口信號(hào)控制進(jìn)行優(yōu)化是最有效的途徑之一.交叉口信號(hào)配時(shí)優(yōu)化要考慮多方面的綜合因素來進(jìn)行交叉口信號(hào)控制方案設(shè)計(jì)以達(dá)到交叉口的交通效益最優(yōu)的目的.在評(píng)價(jià)交叉口通行效益時(shí)通常用停車延誤、停車率、車輛排放、通行能力等指標(biāo)來進(jìn)行.國(guó)內(nèi)外學(xué)者在交叉口配時(shí)優(yōu)化上做出了很多研究：Webster配時(shí)法是以交叉口車輛延誤的估計(jì)為基礎(chǔ)，通過對(duì)周期長(zhǎng)度的優(yōu)化計(jì)算，確定相應(yīng)的一系列配時(shí)參數(shù)的經(jīng)典配時(shí)算法［1］；國(guó)內(nèi)外還開發(fā)了許多有關(guān)信號(hào)控制的軟件系統(tǒng)如Synchro等［2］；文獻(xiàn)［3］針對(duì)交通流的時(shí)變特性，建立了以延誤、排隊(duì)長(zhǎng)度和停車次數(shù)最小為目標(biāo)的交叉口多目標(biāo)信號(hào)配時(shí)優(yōu)化模型，并結(jié)合實(shí)例證明了模型的有效性；文獻(xiàn)［4］使用解析法來構(gòu)建函數(shù)模型，并引入了基于排隊(duì)論的理論模型，結(jié)合人工操作經(jīng)驗(yàn)來完成交叉口的信號(hào)控制，但是該方式在情況復(fù)雜和波動(dòng)性較大的城市交通中適用性不高.近年來，各種啟發(fā)式算法的興起使得交叉口配時(shí)的方法有了新的發(fā)展方向，已經(jīng)有大量將啟發(fā)式算法應(yīng)用于交叉口配時(shí)優(yōu)化的研究：文獻(xiàn)［5］構(gòu)建了車輛和行人總延誤最小的信號(hào)配時(shí)模型，使用遺傳算法尋優(yōu)獲得交通實(shí)體產(chǎn)生的平均交通延誤達(dá)到最小的方案；文獻(xiàn)［6］改善了過飽和條件下的信號(hào)配時(shí)優(yōu)化模型，以延誤最小和通行量最大為目標(biāo)，使用遺傳算法（GA）獲得更優(yōu)的配時(shí)方案；文獻(xiàn)［7］基于TSTM結(jié)合GA算法提出的GATSTM系統(tǒng)能夠通過校準(zhǔn)系統(tǒng)參數(shù)來處理和管理交通網(wǎng)絡(luò)狀況的動(dòng)態(tài)變化；文獻(xiàn)［8］通過使用改進(jìn)的微粒群算法對(duì)構(gòu)建的函數(shù)模型求解，獲得比傳統(tǒng)Webster算法更優(yōu)的配時(shí)方案；文獻(xiàn)［9］將模擬退火算法引入自適應(yīng)控制交叉口中，證明了該方法可以明顯提升交叉口的通行能力.

鯨魚優(yōu)化算法（WOA）作為一種新興的元啟發(fā)式搜索算法，在2016年由澳大利亞的mirjalili等［10］根據(jù)觀察海洋中座頭鯨獨(dú)特的捕食方式提出，算法通過模擬鯨魚一系列的捕食行為實(shí)現(xiàn)目標(biāo)函數(shù)的求解尋優(yōu).WOA算法因其操作簡(jiǎn)單、參數(shù)少而且性能好的特點(diǎn)被大量研究人員所關(guān)注并作出了許多相關(guān)研究.當(dāng)前對(duì)WOA的研究主要集中在應(yīng)用和改進(jìn)兩方面.文獻(xiàn)［11-12］分別通過引入自適應(yīng)權(quán)重和柯西變異以及隨機(jī)自適應(yīng)權(quán)重和模擬退火的策略對(duì)WOA進(jìn)行改進(jìn)，并使用測(cè)試函數(shù)表明了改進(jìn)后算法的優(yōu)越性；文獻(xiàn)［13］對(duì)WOA進(jìn)行改進(jìn)并將其應(yīng)用到充電站選址的項(xiàng)目上，證明了該算法在工程應(yīng)用上的有效性.文獻(xiàn)

［14］使用WOA進(jìn)行水資源的配置優(yōu)化，驗(yàn)證WOA在該領(lǐng)域的適用性.文獻(xiàn)［15］則通過對(duì)WOA進(jìn)行電網(wǎng)無功優(yōu)化調(diào)度，實(shí)例驗(yàn)證了WOA在解決該問題上的魯棒性和有效性.

文章提及的遺傳算法、模擬退火算法和WOA等在進(jìn)行求解時(shí)都存在著傳統(tǒng)啟發(fā)式算法通有的易陷入局部最優(yōu)解、收斂精度低等缺陷.本文首先通過使用自適應(yīng)權(quán)重和levy飛行策略對(duì)WOA進(jìn)行改進(jìn)，提升了WOA的全局尋優(yōu)能力、局部尋優(yōu)能力以及收斂精度，并把改進(jìn)后的算法應(yīng)用到交叉口信號(hào)配時(shí)優(yōu)化中，然后通過構(gòu)造多目標(biāo)尋優(yōu)函數(shù)模型并使用ALWOA對(duì)其進(jìn)行尋優(yōu)求解，獲得綜合通行效益最高的配時(shí)方案.

1 多目標(biāo)信號(hào)配時(shí)優(yōu)化的數(shù)學(xué)模型描述

進(jìn)行交叉口配時(shí)優(yōu)化時(shí)，優(yōu)化效果的評(píng)價(jià)指標(biāo)主要包括延誤時(shí)間、停車次數(shù)、道路通行能力、飽和度、油耗、尾氣排放等.本文選取交叉口的車輛平均延誤、平均停車次數(shù)以及最大通行能力這三個(gè)參數(shù)作為優(yōu)化目標(biāo)，利用加權(quán)的方法將這三個(gè)優(yōu)化目標(biāo)聯(lián)合起來構(gòu)造目標(biāo)函數(shù)并進(jìn)行尋優(yōu)，以獲取交叉口的最大交通效益.

1.1 交叉口平均延誤時(shí)間

車輛延誤由均勻延誤和隨機(jī)延誤組成，本文運(yùn)用韋伯斯特（Webster）提出的延誤時(shí)間的計(jì)算方法來計(jì)算車輛的平均延誤時(shí)間.由Webster延誤計(jì)算公式可得相位i的車輛平均延誤di如下：

式中：第一部分表示均勻延誤，第二部分為隨機(jī)延誤；c表示周期，s；λi是綠信比，表示第i相位有效綠燈時(shí)間與信號(hào)周期的比值；yij為第i相位第j進(jìn)口道的流量比；xij為第i相位第j進(jìn)口道的飽和度；qij為第i相位第j進(jìn)口道的實(shí)際到達(dá)的當(dāng)前交通量，pcu/h.由式（1）可知交叉口的所有車輛的平均延誤表示為：

1.2 交叉口平均停車次數(shù)

進(jìn)入交叉口的車輛在信號(hào)控制的情況下會(huì)產(chǎn)生停車的總次數(shù)如式（3）所示：

式中：hi表示第i相位的車輛平均停車次數(shù).由式（3）可得一個(gè)信號(hào)周期內(nèi)的交叉口的車輛平均停車次數(shù)表示為：

1.3 交叉口通行能力計(jì)算

計(jì)算交叉口通行能力的方法：首先將交叉口各進(jìn)口道劃分為若干車道組，然后計(jì)算各車道組的通行能力，再將各相位的通行能力加起來，最后得到該交叉口一個(gè)周期的通行能力，表達(dá)式如下：

式中：Qi表示第i相位的通行能力，λi為車道組i的飽和流率.

1.4 目標(biāo)函數(shù)

根據(jù)實(shí)際到達(dá)交通量，通過加權(quán)的方式將信號(hào)周期內(nèi)交叉口車輛的平均停車次數(shù)、平均延誤以及交叉口通行能力聯(lián)合轉(zhuǎn)化為交叉口信號(hào)控制優(yōu)化目標(biāo)函數(shù)，以控制周期內(nèi)的有效綠燈時(shí)間作為自變量.考慮到路口交通量的變換，對(duì)模型在設(shè)置權(quán)重時(shí)要根據(jù)實(shí)際交通流率進(jìn)行分配，權(quán)重設(shè)置為ω1=2∣1-Y∣；ω2=1.5∣1-Y∣；ω3=0.5Y（Y為交叉口各相位關(guān)鍵流率比之和），目標(biāo)函數(shù)如下：

約束條件包括以下幾點(diǎn)：

式中：gei為相位i有效綠燈時(shí)間，li為相位i損失時(shí)間，gimin為相位i的最小綠燈時(shí)間，gimax為相位i的最大綠燈時(shí)間，cmin為最小信號(hào)周期長(zhǎng)度，cmax為最大信號(hào)周期長(zhǎng)度.由目標(biāo)函數(shù)構(gòu)成可知，要使目標(biāo)函數(shù)取得最小值，就要求在約束條件下盡可能減小車輛的平均延誤和停車次數(shù)而通行能力則盡量增大.

2 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是一種新興的群智能優(yōu)化算法，鯨魚優(yōu)化算法具有簡(jiǎn)單、調(diào)整參數(shù)少、性能高效的特點(diǎn).算法的主要思路是通過模擬海洋中的座頭鯨的覓食行為得到的，把食物位置作為尋優(yōu)目標(biāo)通過包圍捕食、氣泡網(wǎng)攻擊及隨機(jī)游走等方式獲得最優(yōu)解.

2.1 包圍捕食策略

鯨魚個(gè)體能識(shí)別獵物的位置區(qū)域.由于位置的優(yōu)化設(shè)計(jì)在搜索空間不是預(yù)先確定的，WOA假定當(dāng)前的最佳解決方案是目標(biāo)位置或接近目標(biāo)最優(yōu)個(gè)體位置.在定義了最佳搜索位置之后，個(gè)體開始按照一定的策略朝著當(dāng)前最優(yōu)位置進(jìn)行游動(dòng).此行為表示如下：

2.2 氣泡襲擊階段

描述氣泡網(wǎng)攻擊行為的數(shù)學(xué)模型用如下兩種方式設(shè)計(jì)實(shí)現(xiàn)：

2）螺旋更新位置：此方法首先計(jì)算鯨魚之間的距離，個(gè)體從當(dāng)前位置朝著最優(yōu)個(gè)體位置進(jìn)行螺旋式移動(dòng)，用一個(gè)螺旋方程來模擬鯨魚的螺旋形運(yùn)動(dòng)如下：

2.3 搜尋獵物階段

3 改進(jìn)的鯨魚優(yōu)化算法

為了避免傳統(tǒng)的WOA在求解后期容易陷入局部最優(yōu)導(dǎo)致的算法早熟從而收斂使進(jìn)度不高的問題，本文改進(jìn)WOA的思路從以下兩個(gè)方法入手：一是使用自適應(yīng)權(quán)重方法，使得WOA的局部尋優(yōu)能力得到提升；另一方法是通過引入levy飛行策略對(duì)鯨魚位置進(jìn)行更新，以提升WOA的全局尋優(yōu)能力.

3.1 自適應(yīng)權(quán)重方法

由于WOA的局部搜索實(shí)現(xiàn)方式是以公式（10）和公式（13）進(jìn)行的，當(dāng)個(gè)體以公式（14）的更新方式進(jìn)行局部搜索時(shí)，這種方式只能在局部最優(yōu)解附近徘徊，而不能實(shí)現(xiàn)更好的局部尋優(yōu).慣性權(quán)重是可以用來平衡算法局部搜索能力和全局搜索能力的重要參數(shù).本文使用了一種呈指數(shù)改變的自適應(yīng)權(quán)重方法，算法前期使用較大的權(quán)重實(shí)現(xiàn)較強(qiáng)的全局搜索性能，保證搜索范圍，隨著迭代次數(shù)的增長(zhǎng)，接近最優(yōu)解時(shí)，權(quán)重值呈現(xiàn)指數(shù)減小，使得算法的局部尋優(yōu)能力大大提升.自適應(yīng)權(quán)值公式如（17）所示，改進(jìn)后的位置更新公式如（18）所示：

式中：t表示當(dāng)前迭代次數(shù)，T表示最大迭代次數(shù).

3.2 levy飛行策略

levy飛行這個(gè)概念的正式定義是“步長(zhǎng)具有重尾概率分布的隨機(jī)行走”.我們可以說這是一個(gè)隨機(jī)游動(dòng)，它的特殊性在于它表現(xiàn)出較大的跳躍，因?yàn)檫@個(gè)過程的步長(zhǎng)來自于一個(gè)具有無限方差的分布.與任何隨機(jī)過程一樣，levy飛行起源于擴(kuò)散過程.正因?yàn)槿绱?，它們?cè)陔S機(jī)測(cè)量和隨機(jī)或偽隨機(jī)自然現(xiàn)象的模擬中很有用，特別是表現(xiàn)出一種反常的擴(kuò)散，系統(tǒng)中存在一種“微觀結(jié)構(gòu)”，與混沌理論有關(guān).levy飛行的過程是實(shí)體在進(jìn)行運(yùn)動(dòng)的過程中進(jìn)行大量的小步長(zhǎng)移動(dòng)，同時(shí)還有少量跨越式大步長(zhǎng)移動(dòng)的過程.在Matlab中進(jìn)行模擬levy飛行的二維平面示意圖見圖1.

圖1 Levy飛行二維平面示意圖Fig.1 Two-dimensional diagram of Levy flight

研究發(fā)現(xiàn)許多生物的覓食行為符合levy飛行模式，目前也有大量的研究將其應(yīng)用到一些仿生算法中，并取得了不錯(cuò)的效果.受文獻(xiàn)［16-17］啟發(fā)，本文將levy飛行應(yīng)用于鯨魚的位置更新中，在算法進(jìn)行更新后再進(jìn)行一次levy飛行更新個(gè)體位置，可以實(shí)現(xiàn)跳出局部最優(yōu)解，擴(kuò)大搜索能力的效果.位置更新的方式為：

式中：α是步長(zhǎng)縮放因子，levy（λ）就是隨機(jī)步長(zhǎng)，⊕就是‘·*’運(yùn)算.2009年，Yang X Y［18-19］把levy分布函數(shù)經(jīng)過簡(jiǎn)化和傅立葉變換后得到其冪次形式的概率密度函數(shù)，使用Mantegna方法［20］生成levy分布隨機(jī)步長(zhǎng).levy飛行概率密度函數(shù)及生成隨機(jī)步長(zhǎng)的公式如下：

即進(jìn)行更新時(shí)，levy（λ）使用S表示；進(jìn)行計(jì)算時(shí)，參數(shù)β取值為1.5，α取值為1，u～N（0，σ2），v～N（0，1），σ取值為：

3.3 改進(jìn)WOA的算法流程圖

改進(jìn)WOA通過使用levy飛行策略來跳出局部最優(yōu)解，避免算法早熟.通過加上自適應(yīng)權(quán)重的方式使得鯨魚在進(jìn)行局部尋優(yōu)時(shí)可以提升收斂精度，具體的算法執(zhí)行步驟如圖2所示.

圖2 算法流程圖Fig.2 Algorithm flowchart

4 算例分析

在進(jìn)行多目標(biāo)信號(hào)配時(shí)優(yōu)化時(shí)，本文選取曲靖市某路口作為實(shí)際算例，通過實(shí)地調(diào)研獲得的該路口晚高峰時(shí)的路口各個(gè)方向的交通量以及現(xiàn)有的配時(shí)方案、相位示意圖及該路口的平面渠化圖，見圖3～圖4.通過調(diào)查獲取了該路口的晚高峰小時(shí)交通流量（已轉(zhuǎn)化為標(biāo)準(zhǔn)交通量），實(shí)際數(shù)據(jù)如下表1所示.

圖3 交叉口相位示意圖Fig.3 Phase diagram of intersection

圖4 路口平面示意圖Fig.4 Junction plan

分別使用ALWOA和WOA對(duì)多目標(biāo)配時(shí)優(yōu)化模型進(jìn)行尋優(yōu)求解，模型約束條件設(shè)置為配時(shí)最小信號(hào)周期長(zhǎng)為90 s，最大信號(hào)周期長(zhǎng)為180 s；相位最小有效綠燈時(shí)長(zhǎng)為20 s，最大有效綠燈時(shí)長(zhǎng)為60 s；設(shè)置算法迭代次數(shù)為200，種群個(gè)體數(shù)為50，變量數(shù)為4；通過迭代圖可知，GA和基本W(wǎng)OA過早出現(xiàn)了收斂現(xiàn)象，而使用ALWOA則明顯避免了算法的早熟現(xiàn)象，而且得到的精度更高，改進(jìn)前后算法適應(yīng)度值的收斂曲線分別如圖5所示.

表1 實(shí)際交通流量統(tǒng)計(jì)Tab.2 Actual traffic flow statistics

圖5 算法對(duì)比迭代圖Fig.5 Algorithm comparison iteration diagram

將使用ALWOA進(jìn)行優(yōu)化配時(shí)得到的方案及優(yōu)化目標(biāo)值置于表2中，同時(shí)為了驗(yàn)證本文數(shù)學(xué)模型及算法的有效性，將使用原方案、Webster算法、遺傳算法和標(biāo)準(zhǔn)WOA算法得到的結(jié)果也置于表2中進(jìn)行對(duì)比.

表2 配時(shí)方案及優(yōu)化結(jié)果對(duì)比表Tab.2 Comparison table of timing scheme and optimization results

由表2可以看出使用ALWOA得到的配時(shí)方案與原配時(shí)方案及使用Webster法得到的方案相比有了顯著的提升，與標(biāo)準(zhǔn)WOA算法和遺傳算法相比也有不同程度的提高，結(jié)果充分證明了ALWOA在進(jìn)行交叉口多目標(biāo)信號(hào)配時(shí)優(yōu)化上的有效性.

5 結(jié)語

本文通過引入自適應(yīng)權(quán)重及l(fā)evy飛行的模式對(duì)WOA做出了改進(jìn)，提升了WOA的全局搜索能力和局部尋優(yōu)能力，使得收斂精度提升.然后將其用在交叉口信號(hào)配時(shí)優(yōu)化上，將求解后的結(jié)果與基本的WOA尋優(yōu)得到的結(jié)果進(jìn)行了對(duì)比，結(jié)果顯示使用ALWOA獲得的方案優(yōu)于其余幾種優(yōu)化方法得到的方案，證明了此方法模型的有效性.基于文章只考慮了單點(diǎn)交叉口配時(shí)優(yōu)化的問題，而現(xiàn)實(shí)中的城市道路是多個(gè)交叉口組成的復(fù)雜道路網(wǎng)絡(luò)，接下來考慮如何使用該模型進(jìn)行多交叉口協(xié)調(diào)控制優(yōu)化方面的研究.