一種改進(jìn)鯨魚算法及其在短時(shí)交通流預(yù)測中的應(yīng)用研究

胡 松，成 衛(wèi)，李 艾

1(昆明理工大學(xué) 交通工程學(xué)院 ，昆明 650500)

2(玉溪市公安局交通警察支隊(duì)，云南 玉溪 653100)

1 引 言

群智能算法是對(duì)自然環(huán)境中一些生物的群體行為特征進(jìn)行模擬而得出的一類算法，如觀察鳥類捕食方式模擬出的粒子群算法，根據(jù)生物進(jìn)化得到的遺傳算法[1]等在現(xiàn)在的眾多領(lǐng)域如電力調(diào)度、資源配置、計(jì)算機(jī)應(yīng)用、醫(yī)學(xué)分析等有著廣泛應(yīng)用.鯨魚優(yōu)化算法(Whale Optimization Algorithm,WOA)[2]在2016年由澳大利亞學(xué)者M(jìn)irjalili通過對(duì)座頭鯨覓食行為的研究，得到的一種新的群智能算法，WOA主要是模擬鯨魚在捕獵過程中的靠近獵物的行為，從而找到復(fù)雜尋優(yōu)問題的最優(yōu)解.標(biāo)準(zhǔn)WOA具有參數(shù)少，全局收斂性好等優(yōu)點(diǎn)，因此大量學(xué)者開始將該算法用于實(shí)際應(yīng)用當(dāng)中.如D.B.Prakash[3]等將WOA應(yīng)用于徑向網(wǎng)絡(luò)中電容的選址問題，證明了WOA在維持電壓的穩(wěn)定性和優(yōu)化運(yùn)行成本上的優(yōu)越性.Pradeep Jangir[4]等使用WOA訓(xùn)練多層感知器，解決了局部最優(yōu)問題，獲得了較高的尋優(yōu)精度；但是同傳統(tǒng)的群智能算法一樣容易陷入局部極值及收斂速率慢這些問題，學(xué)者們提出了一些改進(jìn)的方法,例如閆旭[5]等將量子算法加入WOA中并用來解決TSP問題;郭振洲[6]等使用自適應(yīng)權(quán)重和柯西變異改進(jìn)WOA.

在以前學(xué)者的研究基礎(chǔ)上，本文針對(duì)WOA前期收斂速度較慢以及容易陷入局部最優(yōu)解的問題，提出一種基于自適應(yīng)權(quán)重和天牛須搜索[7，8](Beetle Antennae Search,BAS)的鯨魚優(yōu)化算法.改進(jìn)的算法通過將鯨魚優(yōu)化算法中的搜索捕食策略使用天牛須搜索策略代替，加快前期的搜索能力和提升搜索精度；同時(shí)在包圍捕食和氣泡網(wǎng)攻擊中引入了自適應(yīng)權(quán)重增強(qiáng)后期的局部搜索能力，通過測試函數(shù)仿真表明，改進(jìn)后的自適應(yīng)天牛須鯨魚混合優(yōu)化算法(ABOA)相較于粒子群算法(PSO)、遺傳算法(GA)以及標(biāo)準(zhǔn)鯨魚優(yōu)化算法(WOA)在收斂速度及收斂精度上有了明顯提升.

智能交通系統(tǒng)被認(rèn)為是緩解道路擁堵，加強(qiáng)交通安全，促進(jìn)節(jié)能減排的有效方法之一，可以幫助出行者帶來實(shí)時(shí)有效的交通信息從而在交通路徑選擇上作出更有效的判斷，緩解城市交通壓力，提高出行者的出行效率.隨著海量的交通數(shù)據(jù)被人們獲取，短時(shí)交通流的預(yù)測也變得越來越可靠，對(duì)智能交通系統(tǒng)的幫助也日益增大.在交通流預(yù)測上前人已經(jīng)有了大量的研究，錢偉[9]使用相空間重構(gòu)優(yōu)化Kalman濾波進(jìn)行短時(shí)交通流預(yù)測，解決了Kalman濾波模型時(shí)間滯后性的問題；Kumar[10]把季節(jié)性的影響結(jié)合進(jìn)了車流的變化中，提出了一種基于季節(jié)的SARIMA模型，將原本的ARIMA模型進(jìn)行預(yù)測時(shí)的適用范圍進(jìn)行了擴(kuò)大；Wu[11]等使用改進(jìn)K-近鄰預(yù)測模型對(duì)短時(shí)交通流作出了預(yù)測，并在不同時(shí)間點(diǎn)和條件下驗(yàn)證了其預(yù)測的適用性.傅貴等[12]引入核函數(shù)，把屬于非線性回歸的短時(shí)交通流預(yù)測問題轉(zhuǎn)化為Hilbert空間中的線性回歸問題，建立了基于SVMR的短時(shí)交通流預(yù)測模型.LSSVM是SVM的改進(jìn)，可以有效地對(duì)處理非線性數(shù)據(jù)，并且其訓(xùn)練時(shí)間短，適用性強(qiáng).王賀[13]等使用聚類經(jīng)驗(yàn)?zāi)B(tài)分解和LSSVM組合進(jìn)行短時(shí)風(fēng)能預(yù)測；Liu[14]等使用改進(jìn)的GSA算法優(yōu)化LSSVM構(gòu)建汽輪機(jī)熱耗率預(yù)測模型，并證明了其有效性；Sun[15]等使用LSSVM進(jìn)行了PM2.5濃度預(yù)測.LSSVM進(jìn)行回歸預(yù)測時(shí)主要依賴參數(shù)選擇，直接影響模型的性能.前人已有使用粒子群算法，遺傳算法等進(jìn)行參數(shù)尋優(yōu)[16,17]，并取得了較好的效果.文中采用改進(jìn)的WOA算法將LSSVM中的兩個(gè)參數(shù)(核函數(shù)參數(shù)和懲罰系數(shù))進(jìn)行自動(dòng)搜索確定,得到了一種ABOA-LSSVM短期交通流預(yù)測模型，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證其有效性.

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

鯨魚優(yōu)化算法具有原理簡單、操作簡易，易于實(shí)現(xiàn)，需調(diào)整的參數(shù)少及魯棒性強(qiáng)等特點(diǎn).在函數(shù)優(yōu)化方面，WOA算法在求解精度和穩(wěn)定性上要明顯優(yōu)于粒子群(PSO)、差分進(jìn)(DE)和引力搜索(GSA)等算法.通過模擬座頭鯨的捕食獵物的過程中的一系列行為，從而獲得優(yōu)化的數(shù)學(xué)模型，從而完成的算法.該算法主要包含有3個(gè)階段：包圍獵物(encircling prey)、氣泡網(wǎng)攻擊(bubble-net attacking)、搜尋獵物(search for prey)3種方式.下面是3種方式的簡單介紹.

2.1 包圍獵物階段

在鯨魚捕食開始時(shí)，算法假設(shè)當(dāng)前的最優(yōu)捕食個(gè)體的位置是最佳捕食位置，然后剩余個(gè)體朝著最有位置靠攏，其數(shù)學(xué)模型表示為:

(1)

(2)

式中:A和C為系數(shù)向量;X*(t)為當(dāng)前最佳個(gè)體位置，X(t)表示當(dāng)前個(gè)體位置，t表示迭代次數(shù).系數(shù)向量A和C用來控制鯨魚的游走方式，計(jì)算公式如下:

(3)

(4)

2.2 氣泡網(wǎng)攻擊階段

在WOA算法中，群體中個(gè)體的位置更新方式是根據(jù)生成使得隨機(jī)數(shù)的取值來在螺旋式位置更新和縮小包圍范圍(shrinking en-circling mechanism)這兩種更新方式中選取.

1)收縮包圍 即減少式(3)中的a值.在這個(gè)過程中，A在區(qū)間[-a，a]內(nèi)進(jìn)行取值，如果這個(gè)區(qū)間范圍發(fā)生改變，那么a的值也會(huì)隨之發(fā)生變化，若A在區(qū)間[-1，1]內(nèi)進(jìn)行取值，則鯨魚的游動(dòng)位置將處于當(dāng)前位置和獵物位置中間某個(gè)位置，這種方式體現(xiàn)出了鯨魚個(gè)體的局部搜索能力.包圍過程根據(jù)式(1)進(jìn)行更新.

2)螺旋式位置更新 即鯨魚個(gè)體通過螺旋形的運(yùn)動(dòng)方式靠近群體中的最優(yōu)位置，螺旋式位置更新的數(shù)學(xué)模型表示如下:

(5)

(6)

式中:D′為第i頭鯨魚當(dāng)下位置與當(dāng)前最佳個(gè)體間的間距，參數(shù)b則表示一個(gè)定義對(duì)數(shù)螺旋形狀的常數(shù);l是[-1，1]上的隨機(jī)數(shù).座頭鯨在圍捕獵物時(shí)一邊以螺旋形態(tài)游向獵物一邊縮小包圍圈，以0.5作為臨界值進(jìn)行自身位置的更新.更新位置的公式為:

(7)

式中p為[0,1]區(qū)間上的隨機(jī)數(shù).

2.3 搜索捕食

除使用氣泡網(wǎng)法搜索策略以外，鯨魚個(gè)體還能夠隨機(jī)游走搜索獵物，更新時(shí)依據(jù)系數(shù)A的變換進(jìn)行選擇.式(8)、式(9)表示當(dāng)|A|不小于1時(shí)，鯨魚個(gè)體隨機(jī)向別的鯨魚靠攏，距離值D則隨機(jī)更新，從而擴(kuò)大搜索范圍，使捕食能力提升，這樣WOA就擁有一定程度的全局搜索能力.數(shù)學(xué)模型表示如下:

(8)

(9)

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

本文將WOA與天牛須搜索算法結(jié)合在一起，將WOA的隨機(jī)搜索行為用天牛須搜索來代替，加快算法的前期收斂效率，并保證WOA的遍歷性增強(qiáng)算法的全局搜索能力，避免陷入局部最優(yōu).加上自適應(yīng)權(quán)重使得算法在后期的局部搜索時(shí)提高搜索精度，保證算法后期的收斂精度.

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

WOA實(shí)現(xiàn)局部尋優(yōu)的操作是按照公式(2)和公式(5)進(jìn)行局部搜索的，這時(shí)當(dāng)鯨魚按照公式(2)朝著局部最優(yōu)解逼近時(shí)，這時(shí)只能逼近局部最優(yōu)解，而不能進(jìn)行更好的局部尋優(yōu)，如果當(dāng)鯨魚接近食物的時(shí)候，采用較小的自適應(yīng)權(quán)重改變此時(shí)最優(yōu)的鯨魚的位置，則會(huì)提升WOA的局部尋優(yōu)能力.自適應(yīng)權(quán)值公式如(10)所示；改進(jìn)后的自適應(yīng)更新公式如(11)所示:

(10)

(11)

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

3.2 天牛須搜索策略

天牛須搜索算法(BAS)是2017年由研究人員通過觀察天牛覓食的行為而得到的智能算法,它是根據(jù)天牛左右觸角接受到的食物氣味濃度的差別來決定位置更新的方向，從而到達(dá)食物位置.天牛須搜索算法屬于個(gè)體智能算法，只需要一個(gè)個(gè)體，算法的運(yùn)算速度快,算法個(gè)體的位置定義如式(12)、式(13)所示.

1)天牛的朝向是隨機(jī)的，通過以下公式定義為:

(12)

2)天牛左右須的空間坐標(biāo)按如下所示創(chuàng)建:

(13)

式中：t是算法循環(huán)次數(shù)；d是天牛左右須間的距離.

3)天牛的位置按照以下公式更新:

x(t+1)=x(t)+σtbsign[fr-fl]

(14)

式中，fr和fl表示的是適應(yīng)度；σt表示在第t次更新時(shí)的距離；sign()表示符號(hào)函數(shù).在進(jìn)行尋優(yōu)時(shí)使用δt=αδt-1，其中α為步長因子，通常設(shè)成0.95，這樣可以通過α來逐漸減小更新時(shí)的步長，能大大提升BAS算法的尋優(yōu)能力及收斂速率.

改進(jìn)算法的主要步驟如下:

步驟1.初始化.設(shè)置鯨魚群的種群大小、鯨魚優(yōu)化算法迭代的次數(shù)以及天牛須算法步長等參數(shù).

步驟2.設(shè)定鯨魚群的迭代次數(shù)t=0，比較初始種群中全部個(gè)體的適應(yīng)度值，將鯨魚群中適應(yīng)度值最好的個(gè)體所代表的狀態(tài)記錄到公告板中，記錄最好的適應(yīng)度值.

步驟3.將迭代次數(shù)加1，對(duì)每一個(gè)個(gè)體下一步的的位置進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)選擇下一步所要執(zhí)行的操作，包括：收縮包圍，螺旋位置更新或者隨機(jī)位置更新.將算法中的隨機(jī)位置更新方式用天牛須搜索算法代替，即將式(9)使用式(14)代替進(jìn)行一次天牛須算法尋優(yōu)，然后則將最優(yōu)適應(yīng)度的值輸出.當(dāng)評(píng)價(jià)完3種行為得到的適應(yīng)度之后，將適應(yīng)度值進(jìn)行比較，從而選取鯨魚個(gè)體的下一步位置.同時(shí)將更新后的鯨魚群中的最好適應(yīng)度與公告板中記錄的最好適應(yīng)度進(jìn)行對(duì)比，及時(shí)更新公告板.

步驟4.判斷混合算法的迭代次數(shù)是否已經(jīng)達(dá)上限，若沒達(dá)到則返回步驟3，如果滿足則選取適應(yīng)度值最好的個(gè)體進(jìn)行輸出.

4 算法的實(shí)例測試與分析

本文通過對(duì)選取的18個(gè)不同類型的基準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)來驗(yàn)證ABOA算法的尋優(yōu)能力.表1-表3給出了18個(gè)基準(zhǔn)測試函數(shù)的詳細(xì)相關(guān)信息.其中，F(xiàn)1-F7選取的是單峰函數(shù)，F(xiàn)8-F12選取的是多峰函數(shù)，F(xiàn)13-F18為固定維函數(shù).函數(shù)仿真實(shí)驗(yàn)結(jié)果與分析

表1 單峰函數(shù)

表2 多峰函數(shù)

表3 固定維函數(shù)

將ABOA算法與PSO算法、GA算法以及WOA算法進(jìn)行對(duì)比試驗(yàn),每種算法進(jìn)行50次實(shí)驗(yàn)，把50次尋優(yōu)的結(jié)果取平均值以及計(jì)算最優(yōu)解的標(biāo)準(zhǔn)差放在表4中(表中部分?jǐn)?shù)據(jù)來自文獻(xiàn)[4,8]).

根據(jù)對(duì)單峰、多峰、固定維函數(shù)的測試比較，從表4可以看出ABOA在函數(shù)F1、F3、F9、F11、F17都收斂到了最小值，而且標(biāo)準(zhǔn)差為0或者接近0；在測試函數(shù)F2、F4、F7、F10迭代結(jié)束后沒有收斂到最優(yōu)解，但是在收斂精度上，穩(wěn)定性上都優(yōu)于其他3種算法；F5的求解精度優(yōu)于GA,PSO算法，相對(duì)WOA算法略差；對(duì)函數(shù)F6的求解精度僅次于PSO算法；對(duì)函數(shù)F14的求解精度僅次于GA算法；對(duì)F15，F(xiàn)16、F18來說和其它3種算法相比，優(yōu)化前后差距不明顯;僅對(duì)F8進(jìn)行優(yōu)化時(shí)結(jié)果相對(duì)較差.整體上來說，ABOA在收斂精度和穩(wěn)定性上都有提升，特別是在單峰和多峰函數(shù)，其全局尋優(yōu)能力明顯較強(qiáng).本文選取了4個(gè)函數(shù)的迭代進(jìn)化圖，來直觀的展示函數(shù)的優(yōu)化效果對(duì)比，可以看出ABOA算法在收斂精度及收斂速率上都占優(yōu)，如圖1～圖4所示.

表4 測試結(jié)果

圖1 F1迭代圖

圖2 F2迭代圖

圖3 F9迭代圖

圖4 F18迭代圖

5 最小二乘支持向量機(jī)模型

最小二乘支持相機(jī)模型是對(duì)支持向量機(jī)的一種改進(jìn)，通過把SVM不等式約束變?yōu)榈仁郊s束來降低求解二次規(guī)劃問題時(shí)的計(jì)算難度，該模型算法在進(jìn)行非線性問題求解方面十分有效，而短時(shí)交通流預(yù)測就是要在復(fù)雜的交通系統(tǒng)中進(jìn)行非線性求解，因此本文選取LSSVM進(jìn)行短時(shí)交通流預(yù)測，該模型對(duì)短時(shí)交通流進(jìn)行預(yù)測的基本描述如下.給定訓(xùn)練樣本數(shù)據(jù)集:

S={(xi,yi),xi∈Rn,yi∈R},i=1,2,…,l

(15)

式中：xi表示與交通預(yù)測模型的預(yù)測量密切相關(guān)的一些影響因素，如交通流量，道路占有率等，n表示輸入數(shù)據(jù)的維數(shù)；yi為短時(shí)交通流預(yù)測的期望值；l為獲取的歷史樣本個(gè)數(shù).由于道路上的流量是根據(jù)時(shí)間序列變化的，所以當(dāng)前的交通流量與前一段時(shí)間的交通流量存在著關(guān)聯(lián)性.因此，前面一段時(shí)間的流量序列數(shù)據(jù)可以用來預(yù)測未來的交通流.通常把輸入的交通參數(shù)xi與輸出的交通流y二者的非線性關(guān)系轉(zhuǎn)變成φ(x)與y之間的線性關(guān)系,非線性短時(shí)交通流預(yù)測的決策函數(shù)可以定義為:

f(x)=(ω,φ(x))+b

(16)

其中，φ(x)是LSSVM的核函數(shù)，可以將輸入的歷史流量數(shù)據(jù)映射到更高維的空間進(jìn)行求解.b為偏差量，ω為權(quán)值向量.使用LSSVM的優(yōu)化函數(shù)對(duì)目標(biāo)函數(shù)值進(jìn)行優(yōu)化可轉(zhuǎn)化為：

(17)

式中：ei表示真實(shí)值與預(yù)測值二者的擬合誤差,γ為LSSVM模型的懲罰因子，用來控制誤差的懲罰力度大小及調(diào)整模型復(fù)雜度，加上拉格朗日乘子αi并構(gòu)造拉格朗日函數(shù)進(jìn)行求解如下:

(18)

根據(jù)KKT條件得:

(19)

消去ω和ei，并且改寫成矩陣形式為:

(20)

式中：K表示核函數(shù)矩陣；I表示相應(yīng)維數(shù)的單位矩陣.通過LSSVM進(jìn)行預(yù)測的函數(shù)形式如下:

(21)

式中：k(xi,xj)表示訓(xùn)練過程中的核函數(shù)，本文采用高斯(Gauss)徑向基核函數(shù)，其函數(shù)形式如下:

K(xi,xj)=exp(-‖xi-xj‖/2δ2)

(22)

式中：其中δ為核函數(shù)帶寬.在基于徑向基函數(shù)的LSSVM預(yù)測模型中，參數(shù)δ決定了訓(xùn)練樣本數(shù)據(jù)分布特性，而懲罰系數(shù)γ的值能影響訓(xùn)練數(shù)據(jù)的誤差以及模型的泛化能力.在進(jìn)行LSSVM交通流預(yù)測時(shí)，這兩個(gè)參數(shù)的選取不當(dāng)會(huì)導(dǎo)致預(yù)測模型過渡學(xué)習(xí)或者過擬合現(xiàn)象，因此有必要使用智能優(yōu)化算法對(duì)δ和γ的取值進(jìn)行選擇優(yōu)化從而提高模型的預(yù)測性能.

6 ABOA_LSSVM短時(shí)交通流預(yù)測模型的建立

6.1 算法的基本流程

第一步搜集交通流數(shù)據(jù)，對(duì)數(shù)據(jù)做預(yù)處理，再利用ABOA對(duì)LSSVM進(jìn)行參數(shù)尋優(yōu)得到優(yōu)化后的短時(shí)交通流預(yù)測模型，最后依據(jù)最優(yōu)模型，進(jìn)行短時(shí)交通預(yù)測，并輸出預(yù)測結(jié)果，具體步驟如圖5所示.

圖5 ABOA化LSSVM模型的流程框架圖

6.2 算例仿真

為了驗(yàn)證提出的ABOA-LSSVM組合預(yù)測模型的有效性.選取云南省某高速5月7號(hào)-11號(hào)5天的實(shí)際交通流量數(shù)據(jù)(每10分鐘一個(gè))，用歷史數(shù)據(jù)補(bǔ)齊缺失數(shù)據(jù)，然后對(duì)獲取的數(shù)據(jù)使用小波閾值降噪[18]減少異常數(shù)據(jù)對(duì)預(yù)測結(jié)果的干擾，將母小波函數(shù)ψ(x)進(jìn)行變換生成一組基本小波函數(shù):

(23)

式中a為縮放因子，b為平移因子.定義信號(hào)f(x)的連續(xù)小波變換為:

(24)

將處理后的數(shù)據(jù)采用前4天的流量作為訓(xùn)練樣本集，最后一天的流量數(shù)據(jù)作為測試集進(jìn)行，然后分別使用ABOA-LSSVM、WOA-、PSO-LSSVM、LSSVM這4種模型對(duì)流量數(shù)據(jù)進(jìn)行預(yù)測，并與預(yù)測日的實(shí)際流量數(shù)據(jù)進(jìn)行對(duì)比.文中種群大小為20，迭代次數(shù)為50代，ABOA的預(yù)測結(jié)果圖如圖6所示.

圖6 ABOA優(yōu)化LSSVM短時(shí)交通流預(yù)測值與實(shí)際值對(duì)比

6.3 預(yù)測結(jié)果對(duì)比

對(duì)于3種不同算法的預(yù)測結(jié)果，為了體現(xiàn)其有效性，本文通過使用采用均方誤差(MSE)、平均絕對(duì)百分比誤差(MAPE)這兩個(gè)值作為評(píng)價(jià)指標(biāo)，指標(biāo)的表達(dá)式如下所示:

(25)

(26)

本文將不同模型計(jì)算的預(yù)測值和真實(shí)值的均方誤差、平均絕對(duì)百分比誤差結(jié)果放在表5中，由表5本文可以看出使用ABOA-LSSVM模型做短時(shí)交通流預(yù)測預(yù)測結(jié)果上整體優(yōu)于其他幾種模型，說明使用的ABOA-LSSVM模型在進(jìn)行短時(shí)交通流預(yù)測是可行的.

表5 模型誤差

7 結(jié) 論

本文提出了使用自適應(yīng)權(quán)重和天牛須搜索的策略對(duì)鯨魚優(yōu)化算法進(jìn)行了改進(jìn)，在進(jìn)行搜索捕食將鯨魚個(gè)體看做天牛個(gè)體，使用天牛須搜索的策略避免了搜索捕食的隨機(jī)性大大加快了前期的全局搜索速度，同時(shí)使用自適應(yīng)權(quán)重策略使得算法后期的搜索精度.通過對(duì)18個(gè)標(biāo)準(zhǔn)測試函數(shù)的仿真實(shí)驗(yàn)可得改進(jìn)后的算法在收斂精度，穩(wěn)定性及收斂速度上相對(duì)于標(biāo)準(zhǔn)WOA、PSO、GA 3種算法均有著明顯的優(yōu)勢，證明了改進(jìn)策略的有效性.然后將改進(jìn)后的算法結(jié)合LSSVM進(jìn)行短時(shí)交通流預(yù)測，并與標(biāo)準(zhǔn)WOA,PSO優(yōu)化LSSVM以及LSSVM短時(shí)交通流預(yù)測進(jìn)行對(duì)比,結(jié)果表明改進(jìn)后的算法在LSSVM短時(shí)交通流預(yù)測上的有效性.