一種改進(jìn)灰狼算法優(yōu)化LSSVM的交通流量預(yù)測(cè)

戴麗珍，付 濤，楊 剛，楊 輝，徐芳萍

(華東交通大學(xué) 電氣與自動(dòng)化工程學(xué)院，南昌 330013) (江西省先進(jìn)控制與優(yōu)化重點(diǎn)實(shí)驗(yàn)室，南昌 330013)

1 引 言

智能交通系統(tǒng)[1]的一個(gè)關(guān)鍵部分—交通流預(yù)測(cè)，在信號(hào)燈控制、交通擁堵疏導(dǎo)、駕駛路線引導(dǎo)等方面均發(fā)揮著重要作用.高效、準(zhǔn)確的交通流預(yù)測(cè)可以保障ITS的準(zhǔn)確運(yùn)行，也為交通管控部門提供決策依據(jù).隨著全球ITS技術(shù)的飛速發(fā)展，交通流預(yù)測(cè)技術(shù)的研究成為一個(gè)熱點(diǎn)問(wèn)題.

研究表明，城市路面交通網(wǎng)中某一時(shí)間點(diǎn)的交通流量與前幾個(gè)時(shí)間點(diǎn)的交通流量有映射關(guān)系，并且交通流量具有周期性[2].為了提高交通流量預(yù)測(cè)的準(zhǔn)確性，常采用時(shí)間序列技術(shù)和回歸模型等[3-9]方法.由于交通流有不確定性、復(fù)雜性和非線性等特點(diǎn)，導(dǎo)致其精確預(yù)測(cè)存在一定的難度.隨著優(yōu)化算法的發(fā)展，基于神經(jīng)網(wǎng)絡(luò)和群體智能優(yōu)化的方法也被廣泛應(yīng)用于交通流量的預(yù)測(cè).Chan[10]等人提出了一種基于粒子群優(yōu)化算法的短時(shí)交通流預(yù)測(cè)方法，提高了預(yù)測(cè)的穩(wěn)定性和可靠性.王凡[11]等人提出了一種基于AOSVR的交通流預(yù)測(cè)及參數(shù)選擇的方法.Li[12]等人提出基于了粒子群優(yōu)化混沌BP神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流預(yù)測(cè).Xu[13]等人提出了利用分類和回歸樹(shù)進(jìn)行短期交通量預(yù)測(cè).楊凡[14]等人研究了一種混合神經(jīng)網(wǎng)絡(luò)挖掘模型方法用于交通流預(yù)測(cè).以上方法均在某種程度上提升了交通流的預(yù)測(cè)精度，但由于構(gòu)建模型的差異，性能優(yōu)劣無(wú)法判定.可以明確的是：基于群體優(yōu)化的預(yù)測(cè)技術(shù)已被應(yīng)用于交通流量預(yù)測(cè)，以提高預(yù)測(cè)模型的準(zhǔn)確性.

在解決樣本數(shù)量少、非線性系統(tǒng)以及模式識(shí)別等方面擁有諸多優(yōu)勢(shì)的SVM被Cortes和Vapnik提出，并能將其推廣到線性擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中[15].Suyken為了解決SVM求解二次規(guī)劃問(wèn)題帶來(lái)的訓(xùn)練時(shí)間過(guò)長(zhǎng)等問(wèn)題，提出用求解線性方程組問(wèn)題代替求解二次規(guī)劃問(wèn)題的最小二乘支持向量機(jī)(Least Square SVM，LSSVM)[16].因此，LSSVM也被用于交通流量的預(yù)測(cè)[17，18].最小二乘支持向量機(jī)的性能在很大程度上依賴于它的兩個(gè)核心參數(shù)(懲罰因子γ和核函數(shù)參數(shù)σ).其中，γ是平衡了對(duì)樣本的擬合性能(經(jīng)驗(yàn)風(fēng)險(xiǎn))和測(cè)試樣本的預(yù)測(cè)性能(結(jié)構(gòu)風(fēng)險(xiǎn))，即結(jié)構(gòu)風(fēng)險(xiǎn)隨著γ的增大而上升，經(jīng)驗(yàn)風(fēng)險(xiǎn)卻相反；且γ越大，模型將過(guò)擬合，而γ越小，模型將欠擬合.而σ的情況與γ相反.為了確定這兩個(gè)關(guān)鍵參數(shù)，粒子群優(yōu)化算法PSO、遺傳算法GA、差分進(jìn)化算法DE、人工蜂群算法BA和模擬退火算法SA等多種啟發(fā)式算法已被嘗試[19-23].灰狼優(yōu)化算法(Grey Wolf Optimization，GWO)是模擬狼群的種群地位和捕獵行為的一種新群體智能優(yōu)化算法，常用于模型的參數(shù)優(yōu)化.當(dāng)優(yōu)化目標(biāo)只有一個(gè)峰值時(shí)，GWO算法收斂速度較快；但當(dāng)優(yōu)化目標(biāo)有多個(gè)峰值時(shí)，盡管GWO算法全局搜索性能比PSO和GA等算法高，而易造成局部最優(yōu)(即早熟現(xiàn)象)[24]，從而導(dǎo)致模型陷入欠擬合或過(guò)擬合.由于在GWO算法中，控制距離參數(shù)a與迭代次數(shù)是線性關(guān)系且成反比，忽略了工程應(yīng)用中優(yōu)化問(wèn)題的多樣性，尤其是優(yōu)化目標(biāo)有多個(gè)峰值時(shí)，易陷入早熟.因此，為了實(shí)現(xiàn)交通流的精確預(yù)測(cè)，本文擬研究基于LSSVM的交通流預(yù)測(cè)建模方法，并通過(guò)增加GWO算法的種群多樣性和改進(jìn)GWO算法的控制距離參數(shù)a來(lái)優(yōu)化LSSVM的參數(shù)，提高模型的預(yù)測(cè)精度.

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

最小二乘支持向量機(jī)是對(duì)支持向量機(jī)改進(jìn)得到的(不等式約束問(wèn)題簡(jiǎn)化為等式約束問(wèn)題).考慮數(shù)據(jù)樣本(xt,yt)(t=1,2,…,l)，其中xt∈Rn，yt∈Rn分別為樣本輸入和樣本輸出，l為樣本的數(shù)量.通過(guò)非線性變換，可將樣本輸入x映射到高維空間：

f(x)=wTφ(x)+c

(1)

其中：w為超平面的權(quán)值，c為常數(shù)，φ(·)為空間轉(zhuǎn)換函數(shù).

最小二乘支持向量機(jī)的目標(biāo)函數(shù)定義如下：

(2)

其中：ei為誤差，γ為懲罰因子.

構(gòu)造拉格朗日函數(shù)如下：

(3)

其中：ai為拉格朗日乘子.根據(jù)KKT條件可得：

(4)

求解式(4)，可得LSSVM數(shù)學(xué)模型如下：

(5)

其中：K(·)為模型核函數(shù)，通常采用RBF核函數(shù)，即：

(6)

其中：σ為核函數(shù)參數(shù).

因此LSSVM模型的性能主要取決于γ和σ.

3 基于改進(jìn)GWO的LSSVM模型

(7)

(8)

(9)

A=a(2r1-1)

(10)

C=2r2

(11)

其中：t為當(dāng)前迭代數(shù)；Dp(t)(p=α、β、η)為灰狼與獵物之間的距離；A和C為系數(shù)向量；Xp為當(dāng)前獵物位置；Xl(l=1,2,3)為普通灰狼根據(jù)Xp更新的位置；a為控制距離參數(shù)，為由2-0的線性遞減量；r1和r2為[0 1]隨機(jī)數(shù).

綜上，灰狼優(yōu)化算法的主要步驟如下：

Step 1.參數(shù)初始化.

Step 2.初始化種群個(gè)體并計(jì)算函數(shù)目標(biāo)值，選擇最優(yōu)個(gè)體α、β和η.

Step 3.計(jì)算a、A和C的值，按照式(7)計(jì)算種群個(gè)體與最優(yōu)個(gè)體的距離并根據(jù)式(8)-式(9)更新個(gè)體位置.

Step 4.更新最優(yōu)個(gè)體位置.

Step 5.判斷是否達(dá)到要求.如果達(dá)到設(shè)定值，則運(yùn)行結(jié)束，否則轉(zhuǎn)至Step 3繼續(xù)迭代.

GWO算法在尋優(yōu)過(guò)程中能自動(dòng)調(diào)整控制距離參數(shù)a，且自身的參數(shù)具有良好的魯棒性能，能夠較好地平衡算法中種群的全局搜索能力和局部搜索能力[25].因此，控制距離參數(shù)a的設(shè)計(jì)，在一定程度上會(huì)影響到算法的全局搜索能力與局部搜索能力之間的平衡性.通常情況下，控制距離參數(shù)a隨著迭代次數(shù)的增大，從2-0線性遞減.當(dāng)算法處于尋優(yōu)初期時(shí)，搜索步長(zhǎng)較大，全局搜索能力較強(qiáng)，不易陷入局部最優(yōu)，且隨機(jī)參數(shù)r1在一定范圍時(shí)，|A|≥1，表明算法進(jìn)行全局搜索；而當(dāng)算法處于尋優(yōu)后期時(shí)，搜索步長(zhǎng)較小，局部搜索能力較強(qiáng)，易于收斂，且隨機(jī)參數(shù)r1在一定范圍時(shí)，|A|<1，表明算法進(jìn)行局部搜索[26].

4 改進(jìn)灰狼算法優(yōu)化LSSVM交通流預(yù)測(cè)模型

對(duì)于GWO算法而言，探索能力對(duì)于其優(yōu)化性能至關(guān)重要[27].GWO算法容易出現(xiàn)早熟現(xiàn)象，要想避免該現(xiàn)象，通?？刹捎秘S富種群多樣性、自適應(yīng)變異、處理重復(fù)個(gè)體等方法[28].針對(duì)灰狼優(yōu)化算法因種群多樣性低以及控制距離參數(shù)a與迭代次數(shù)是線性關(guān)系且成反比的問(wèn)題，忽略了工程應(yīng)用中優(yōu)化問(wèn)題的多樣性，尤其是優(yōu)化目標(biāo)有多個(gè)峰值時(shí)，存在早熟的缺點(diǎn)，結(jié)合差分進(jìn)化算法和控制距離參數(shù)非線性化提出了改進(jìn)的灰狼優(yōu)化算法.為增加算法種群多樣性進(jìn)行如下改進(jìn)：

1)變異操作：

Di(t)=xα+B(xβ-xη)

(12)

其中：Di(t)為變異個(gè)體位置，xp為當(dāng)前種群中隨機(jī)的3個(gè)個(gè)體位置，B為收縮因子.

2)交叉操作：

(13)

其中：R為交叉概率；yi為新個(gè)體.

3)選擇操作：

(14)

其中：f(·)為評(píng)價(jià)函數(shù).

對(duì)于控制距離參數(shù)a我們作如下改進(jìn)：

a=cos(tπ/(2T))+(1-t/T)1.1

(15)

其中：T為最大迭代次數(shù).

應(yīng)用改進(jìn)灰狼算法優(yōu)化LSSVM模型參數(shù)進(jìn)行交通流預(yù)測(cè)的流程如圖1所示.

綜上，改進(jìn)的灰狼優(yōu)化算法主要步驟如下：

1)構(gòu)建數(shù)據(jù)集(即訓(xùn)練集與測(cè)試集)，并對(duì)數(shù)據(jù)預(yù)處理，得到路段的歷史交通流量數(shù)據(jù)的時(shí)間序列.

2)利用改進(jìn)灰狼優(yōu)化算法對(duì)LSSVM參數(shù)優(yōu)化(即懲罰因子γ和核函數(shù)參數(shù)σ)，主要步驟如下：

Step 1.參數(shù)初始化.

Step 2.初始化種群并計(jì)算函數(shù)目標(biāo)值，選擇最優(yōu)個(gè)體α、β和η.

Step 3.計(jì)算a、A和C的值，根據(jù)式(7)計(jì)算種群個(gè)體與最優(yōu)個(gè)體的距離并根據(jù)式(8)、式(9)更新個(gè)體位置.

Step 4.由式(12)-式(14)對(duì)當(dāng)前種群執(zhí)行變異、交叉和選擇操作，計(jì)算個(gè)體的目標(biāo)函數(shù)值.

Step 5.更新最優(yōu)個(gè)體位置.

Step 6.判斷是否達(dá)到要求.如果達(dá)到設(shè)定值，則運(yùn)行結(jié)束，否則轉(zhuǎn)至Step 3繼續(xù)迭代.

3)根據(jù)最優(yōu)參數(shù)得到最優(yōu)模型后進(jìn)行交通流量預(yù)測(cè).

由于初始化的種群可能不能滿足要求，這時(shí)候就需要擴(kuò)充種群，而算法采用交叉、變異、選擇操作，為算法種群增加了變異種群，因此，可以極大的改善算法的早熟現(xiàn)象.且通過(guò)對(duì)式(15)所示的控制距離參數(shù)a的非線性化的調(diào)整，與傳統(tǒng)的GWO算法相比，非線性的控制距離參數(shù)a隨著迭代次數(shù)的增加，斜率先遞減后遞增，且比傳統(tǒng)a的斜率小，當(dāng)t在0.8T到0.9T之間，a的斜率開(kāi)始上升，如圖1所示.因此，控制距離參數(shù)的非線性化能夠保證在部分情況下，算法依然處于全局搜索，例如：當(dāng)t=2/T，且隨機(jī)數(shù)r1在一定范圍內(nèi)時(shí)，非線性化a=1.17，而傳統(tǒng)a=1，這時(shí)改進(jìn)GWO參數(shù)|A|≥1，而傳統(tǒng)的GWO參數(shù)|A|<1；而當(dāng)t接近最大迭代次數(shù)時(shí)，a以非線性遞增的衰減速度趨于0且比傳統(tǒng)的a衰減慢，這樣也能保證局部搜索的充分性.

圖1 改進(jìn)灰狼算法優(yōu)化LSSVM流程Fig.1 Improved grey wolf algorithm to optimize LSSVM process

5 仿真實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源與處理

本文采集了4天山東省某路段交通流量數(shù)據(jù)樣本，每隔15分鐘采集一次，共采集384組數(shù)據(jù)樣本.

由于是數(shù)據(jù)驅(qū)動(dòng)建模，首先需要確定模型輸入與輸出.依據(jù)相空間重構(gòu)確定時(shí)間序列的遲滯時(shí)間及鑲嵌維度，并建立數(shù)學(xué)模型：

y(n+k)=[x(n),x(n-t),…,x(n-(d-1)t)]T

(16)

其中：y(·)=x(·)為模型的輸出，x(n)為時(shí)間序列，k為預(yù)測(cè)步長(zhǎng).

因?yàn)槭菍?duì)交通流時(shí)間序列進(jìn)行預(yù)測(cè)，則令k=1，且每15min預(yù)測(cè)一次交通流量.由差分熵可以確定該時(shí)間序列的遲滯時(shí)間t=7，鑲嵌維度d=4.訓(xùn)練和測(cè)試數(shù)據(jù)樣本分別為276組和92組.

5.2 參數(shù)選擇

使用改進(jìn)GWO算法優(yōu)化LSSVM模型參數(shù)前，定義改進(jìn)GWO算法的優(yōu)化目標(biāo)函數(shù)為平均相對(duì)誤差emape，如式(20)所示.改進(jìn)GWO算法可調(diào)參數(shù)設(shè)置如下，種群數(shù)量npop=20，種群參數(shù)上、下界分別為ub=[1000,1000]、lb=[0.01,0.01]，縮放因子B∈(0.3,0.7)，交叉概率為R=0.1，最大迭代次數(shù)T=50等，其他模型同類型參數(shù)均一致.

5.3 實(shí)驗(yàn)結(jié)果分析

對(duì)預(yù)測(cè)結(jié)果采用如下指標(biāo)進(jìn)行評(píng)價(jià)：

最大絕對(duì)誤差：

(17)

歸一化均方根誤差：

(18)

均方差：

(19)

平均相對(duì)誤差：

(20)

為評(píng)價(jià)本文提出方法的優(yōu)勢(shì)，采用GWO-LSSVM、PSO-LSSVM、小波神經(jīng)網(wǎng)絡(luò)和ELM與本文方法對(duì)比，各自獨(dú)立運(yùn)行100次取評(píng)價(jià)指標(biāo)平均值，對(duì)比結(jié)果如表1所示.

表1 模型評(píng)價(jià)指標(biāo)結(jié)果對(duì)比Table 1 Comparison of model evaluation index results

仿真結(jié)果如圖2-圖6所示(其中圖3-圖6圖例一致).對(duì)比分析如下：

圖2 模型平均預(yù)測(cè)值對(duì)比Fig.2 Comparison of model average predictions

1)改進(jìn)GWO-LSSVM模型對(duì)交通流量預(yù)測(cè)與其他算法相比，評(píng)價(jià)指標(biāo)明顯高于其他4種算法.

2)圖3-圖6中GWO-LSSVM的結(jié)果是由于GWO算法在尋優(yōu)過(guò)程中，γ很大，σ很小導(dǎo)致模型出現(xiàn)過(guò)擬合現(xiàn)象，陷入局部最優(yōu).

圖3 最大絕對(duì)誤差Fig.3 Maximum absolute error

圖4 歸一化均方差Fig.4 Normalized mean square error

圖5 均方誤差Fig.5 Mean square error

圖6 平均相對(duì)誤差Fig.6 Mean relative error

3)值得注意的是，與PSO-LSSVM、小波神經(jīng)網(wǎng)絡(luò)相比，雖然本文提出方法性能指標(biāo)發(fā)生5次較大幅度跳躍(可接受范圍)如圖3-圖6，但是泛化性能明顯提升.

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

為提高基于LSSVM的交通流量預(yù)測(cè)精度，本文提出了改進(jìn)灰狼優(yōu)化算法對(duì)LSSVM參數(shù)(懲罰因子γ和核函數(shù)參數(shù)σ)進(jìn)行優(yōu)化.為了提高算法全局搜索能力，避免過(guò)早陷入局部最優(yōu)，設(shè)計(jì)了灰狼優(yōu)化算法內(nèi)部的交叉、變異和選擇操作，并且使得控制參數(shù)a的非線性化，豐富了灰狼優(yōu)化算法中種群的多樣性，提升了算法的搜索性能.仿真結(jié)果顯示，改進(jìn)GWO優(yōu)化LSSVM與GWO-LSSVM相比增強(qiáng)了泛化能力，能夠獲得較高的預(yù)測(cè)精度；與PSO-LSSVM相比，魯棒性和泛化能力均有提升；與小波神經(jīng)網(wǎng)絡(luò)和ELM相比，雖然模型有所差別，但是泛化能力和魯棒性有所提升.此外由于改進(jìn)GWO算法加入了交叉、變異、選擇操作，導(dǎo)致尋優(yōu)時(shí)間較長(zhǎng)，不符合實(shí)時(shí)性要求，因此本文方法通過(guò)歷史數(shù)據(jù)建立模型，獲得模型參數(shù)后預(yù)測(cè)當(dāng)前交通流量.