基于相空間重構的GQPSO-WNN短時交通流預測

唐 瑞 陳慶春 類先富

1(西南交通大學信息科學與技術學院 四川 成都 611756)2(廣州大學機械與電氣工程學院 廣東 廣州 510006)

0 引 言

智能交通系統(tǒng)(ITS)的發(fā)展是減少城市污染、緩解交通擁堵以及避免交通事故發(fā)生的關鍵。短時交通流的預測模型是指預測時間不超過15 min，通過得到的交通流歷史數(shù)據(jù)選擇適當?shù)念A測模型，在t時刻在線實時地預測出時刻的交通流數(shù)據(jù)。短期交通預測模型的實際應用之一是根據(jù)實時交通信息幫助旅客選擇t+Δt出行路線或提前計劃出行。它還可以幫助制定主動的交通管理策略，改善交通擁塞。

傳統(tǒng)的交通流預測精度已經(jīng)無法滿足需求[1]，在過去的幾十年中，交通短期變量預測得到了發(fā)展和改進。預測方法可以分為兩類：統(tǒng)計算法類，如非參數(shù)回歸模型、卡爾曼濾波等；人工智能類，如BP神經(jīng)網(wǎng)絡和WNN等[2-3]；其中，WNN模型是最常用的短期交通預測模型。盡管WNN模型易于構建，并取得了讓人滿意的預測效果。但是人工智能網(wǎng)絡預測模型存在著許多缺點，比如：早熟收斂或無法收斂、求解精度不高等，所以許多研究者引入了粒子群等優(yōu)化算法來對這些智能網(wǎng)絡算法進行改進[4]。粒子群優(yōu)化算法收斂速度快，在尋求函數(shù)最優(yōu)解方面有很大優(yōu)勢，能改善神經(jīng)網(wǎng)絡收斂速度慢、訓練誤差過大的問題。但是，標準粒子群算法存在一些缺點，如搜索空間有限、容易早熟、容易陷入局部優(yōu)化[5]。對應的，本文采用全局收斂的量子粒子群算法在粒子后期搜索中改善收斂性能問題，由于量子粒子群算法沒有交叉和變異過程，難以搜索到全局最優(yōu)點，因此采用遺傳算法進行改進。結合這兩種算法，可以提高捕獲交通流數(shù)據(jù)中的線性和非線性模式的可能性，并提高預測性能。為了使提出的預測模型更加可靠，還需要對交通流時間序列數(shù)據(jù)進行重構，分析序列內(nèi)部的混沌特性，驗證其可預測性[6]。

1 相空間重構

交通流時間序列是一組看似無規(guī)律、隨機性的序列，這樣的序列是否具有可預測性是后續(xù)預測模型建立的前提。1980年Packard[8]和Takens[9]提出了相空間重構理論(phase space reconstruction theory)，其主要目的在于恢復時間序列的混沌吸引子，其原理是選擇合適的延遲時間τ和嵌入維數(shù)m，采用混沌理論的相空間重構技術可以將低維時間序列映射到高維相空間里并保持微分同胚。設x={xi|i=1,2,…,N}為給定的交通流時間序列，選擇適當?shù)膮?shù)重構相空間得到[10]：

X=[xi,xi+τ,…,xi+(m-1)τ]Ti=1,2,…,M

(1)

式中：X是維數(shù)為M×m的軌線矩陣，相點個數(shù)為M=N-(m-1)τ。

1.1 C-C方法

1999年，H.S.Kim等[11]提出C-C方法，該方法認為嵌入維數(shù)m不依賴于延遲時間τd而依賴于延遲時間窗口τw，通過計算公式τw=(m-1)τd可以得出嵌入維數(shù)m的值。對于時間序列x={xi|i=1,2,…,N}，定義關聯(lián)積分為以下公式[7]：

(2)

式中：r>0為尺度，dij=‖Xi-Xj‖，Xi為根據(jù)給出延遲時間τ和嵌入維數(shù)m的值重構相空間的點。若x<0，則θ(x)>0；若x≥0，則θ(x)=1。將時間序列{xi}分解t個不重疊的時間序列，采用分塊平均策略：

(3)

令N→∞時，有：

(4)

對于獨立同分布的時間序列，那么m、t是固定的，當N趨近于無窮時，則對所有的r均有S(m,r,τ)恒等于0。但是實際序列是有限的且可能存在相關的元素，所以S(m,r,τ)≠0，關于半徑r的最大偏差：

ΔS(m,τ)=max{S(m,rj,τ)}-min{S(m,rj,τ)}

(5)

m=2,3,4,5;j=1,2,3,4

Brock等[12]根據(jù)數(shù)學統(tǒng)計結果表明，選取合適的N，計算出時間序列的標準差σ，三個統(tǒng)計量的計算公式：

(6)

(7)

(8)

式中：rj=jσ/2,j=1,2,3,4。

圖1 C-C方法計算交通流數(shù)據(jù)表示圖

1.2 Lyapunov指數(shù)計算

Lyapunov指數(shù)是刻畫相空間中兩條初始值十分靠近的軌道，隨著時間推移呈指數(shù)形式的平均發(fā)散率[13]，若最大Lyapunov指數(shù)大于0，則可以認為系統(tǒng)是混沌的。

小數(shù)組方法[14]是混沌理論里計算最大Lyapunov指數(shù)普遍適應的方法，跟Jacobian方法、P-范數(shù)法等比起來，該算法具有計算量不大、相對易操作、對小數(shù)據(jù)組比較可靠、求解精度較高的優(yōu)點。

使用小數(shù)組方法求解Lyapunov指數(shù)的步驟如下[11]：

Step1對時間序列進行FFT變換，求出平均周期P；

Step2根據(jù)計算得到的m和τ，重構相空間矩陣{Xj=j=1,2,…,M}；

Step3找出給定軌跡上的每個點相隔最近的點，即:

d(0)=min‖Xj-X′j‖ |j-j′|>P

(9)

Step4尋找相空間軌跡矩陣里Xj最近點經(jīng)過i個時間點后的距離：

dj(i)=min‖Xj+i-X′j+1‖

(10)

Step5求出所有的lndj(i)平均y(i)，q為當dj(i)≠0時的值，即：

(11)

如圖2所示，對交通流時間序列數(shù)據(jù)進行仿真實驗求得的最大Lyapunov指數(shù)，即為最小二乘法擬合后的曲線斜率λ。從圖中可以看出，λ是大于0的，根據(jù)定理說明交通流時間序列是混沌的，可以進行短期預測。

圖2 小數(shù)量法求得交通流最大Lyapunov指數(shù)

2 小波神經(jīng)網(wǎng)絡(WNN)模型

如圖3所示，WNN是三層架構，包括輸入層、隱藏層(其中小波函數(shù)用作激活函數(shù))和輸出層(其是隱藏層的加權輸出的線性求和)[5]。

圖3 小波神經(jīng)網(wǎng)絡拓撲結構

圖3中xi是輸入?yún)?shù)，yk是輸出參數(shù)。wij和wjk是神經(jīng)網(wǎng)絡的權值。

(12)

本文采用的小波基函數(shù)為Morlet母小波基函數(shù)，因為它在[-1,0]以及[0,1]上是單調(diào)的，數(shù)學公式為:

y=cos(1.75x)e-x2/2

(13)

WNN的輸出網(wǎng)絡層計算公式為:

(14)

式中：wik為隱含層到輸出層權值；h(i)為第i個隱含層節(jié)點的輸出；l為隱含層節(jié)點數(shù)；m為輸出層節(jié)點。

傳統(tǒng)的小波神經(jīng)網(wǎng)絡采用的是梯度下降法來調(diào)整參數(shù)，網(wǎng)絡權值、伸縮因子、平移因子這些參數(shù)的初值選取一般采用試探法給定[15]，可能會造成求解過程中陷入局部最優(yōu)和產(chǎn)生振蕩的不良效果，網(wǎng)絡訓練誤差也達不到設定的要求，因此本文采用粒子群優(yōu)化算法對其進行改進。

3 量子粒子群優(yōu)化算法

3.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)[16]是一種利用速度向量Vi和位置向量Xi模擬社會有機體的自然演變過程。算法里面的每個粒子相當于一種當前問題的候選解決方案，這些粒子將四處移動以搜索最佳值，每個粒子記錄其最佳先前位置(給出最佳適應值的位置)為gbesti，稱為個體最佳位置。在每次迭代中，每個粒子與整個種群中的其他粒子競爭最佳位置zbest的最佳粒子(在種群中具有最佳適應值)，稱為全局最佳位置。然后使用這些信息來調(diào)整自己的速度和位置，從而實現(xiàn)解決方案領域的個性化優(yōu)化。粒子的更新公式如下：

(15)

(16)

式中:ω為慣性權重；k為當前的迭代次數(shù)；Vid為粒子速度；c1和c2為加速度因子；r1和r2為分布于[0,1]之間的隨機數(shù)。粒子群算法雖然在魯棒性、求解精度上有明顯優(yōu)勢，但是粒子由于隨機性不高容易陷入局部最優(yōu)。

3.2 量子粒子群算法

Sun等提出的QPSO算法，這是一種基于PSO和量子模型的新算法。在經(jīng)典粒子群優(yōu)化算法中，通過位置矢量Xi和Vi速度矢量來描述粒子飛行軌跡。但是在CPSO系統(tǒng)中，粒子的動力學行為是廣泛發(fā)散形式，即不能同時確定Xi和Vi的精確值。由于粒子會因為速度的原因使得搜索空間限制在某個區(qū)域，于是QPSO算法采用波函數(shù)表示粒子的運動狀態(tài)。量子粒子群算法的更新方程為:

（一）基本建設投資管理缺乏科學有效的分工決策機制?；窘ㄔO項目由投資主管部門進行立項、可行性研究、初步設計和概算審批，其主要考慮項目需求，往往忽略財政可承受能力評估，容易出現(xiàn)超越現(xiàn)有財力或者雖然確定了籌資渠道但是無法落實的情況，綁架財政不斷擴大支出。同時，現(xiàn)行決策制度也缺乏硬約束，有的前期論證流于形式，“邊設計、邊報批、邊施工”，時常出現(xiàn)“預算超概算，決算超預算”的情況。整個鏈條不同環(huán)節(jié)沒有形成合力，不同的部門之間溝通不暢，影響科學決策。

(17)

(18)

(19)

式中：M為粒子種群數(shù)，φ1=rand()，φ2=1-φ1，u=rand()；mbesti為迭代t次后所有粒子的最佳位置平均值，β為收縮-擴張系數(shù)，為了保證算法的收斂性，一般使用1.0～5.0線性下降策略[15]:

β=βmax-(βmax-βmin)t/tmax

(20)

3.3 GQPSO

QPSO是一種進化算法，在其全局搜索能力、相對快速的收斂性方面大大優(yōu)于PSO[17]，但是也存在缺陷，隨著迭代次數(shù)的增加，QPSO的收斂性能將逐漸趨于緩慢，尋優(yōu)能力會下降，并且可能在局部極小值中周旋。采用遺傳算法里的交叉變異操作，可以改進量子粒子群算法里隨著迭代次數(shù)增加而生成的新的個體過于單一的問題。在GQPSO算法中，個體不再只是根據(jù)群體里的最優(yōu)位置信息交換群體知識，而是從具有較好適應度的個體隨機選擇需要學習的對象。GQPSO算法步驟如下：

1) 通過適應度函數(shù)計算粒子的適應度值，對群體的局部最佳gbesti和全局最佳zbest分別進行更新。

2) 對雜交池numpool進行初始化，利用公式seed1=floor(rand()×numpool)+1計算出需要進行雜交操作的粒子。

3) 計算雜交后產(chǎn)生的新粒子的適應度的值，若優(yōu)于父代適應度的值，則用子代的位置替代父代的位置。

4) 初始化變異范圍大小，計算出需要進行變異操作的粒子seed2=floor(rand()×mutationpool)+1。

5) 更新變異后的子代粒子的位置，計算適應度的值，若優(yōu)于父代適應度的值，則代替父代位置。

6) 重復上述步驟1)至5)，直到滿足誤差終止條件。

4 實驗分析

為驗證GQPSO-WNN算法的有效性，本文采用了PeMs(http://pems.dot.ca.gov/)能力度量系統(tǒng)上采集的2016年12月5號到7號美國加州快速路網(wǎng)I110-N號線圈檢測的采樣間隔為5 min的實時交通流量數(shù)據(jù)，共864條數(shù)據(jù)，將最后230條數(shù)據(jù)作為測試樣本進行仿真實驗。

由于采集到的數(shù)據(jù)可能存在噪聲，所以首先對數(shù)據(jù)進行了降噪和歸一化處理，根據(jù)C-C算法確定的時間延遲τ和嵌入維數(shù)m(參見圖1)重構相空間，計算得到Lyapunov指數(shù)大于0(參見圖2)，證明該交通流序列具有混沌特性，設置小波神經(jīng)網(wǎng)絡各個參數(shù)，網(wǎng)絡的輸入層應該等于嵌入維數(shù)，故輸入層為6，輸出層為1，隱含層數(shù)7，隨機初始化50個粒子。本文采用以下模型評價指標：

式中：Yp(t)是第t時的預測值，Yr(t)是第t時的實際值。圖4-圖8給出了WNN模型，PSO-WNN模型以及GQPSO-WNN模型對實際交通流的預測結果和誤差對比圖，同時分別比較了PSO-WNN模型和GQPSO-WNN模型的收斂性。

圖4 WNN預測結果對比曲線和絕對誤差

圖5 PSO-WNN預測結果對比曲線和絕對誤差

圖6 GQPSO-WNN預測結果對比曲線和絕對誤差

圖7 PSO-WNN適應度值迭代曲線

圖8 GQPSO-WNN適應度值迭代曲線

從圖6和圖8可以看出，GAQPSO-WNN算法模型預測結果曲線更加貼合真實交通流曲線，算法在迭代次數(shù)不超過10次時，適應度值就已經(jīng)下降到0.2以下，迭代到接近20次時GAQPSO-WNN預測模型的曲線幾乎收斂。由此可見，該算法相較于PSO-WNN算法收斂性較好，預測準確度也更高。

將預測模型多次試驗取平均值得到結果如表1所示。綜合對比BP、WNN和PSO-WNN等算法的評估指標結果，經(jīng)過混合優(yōu)化后的GQPSO-WNN短時交通流預測模型的均方誤差比PSO-WNN模型低56%左右，擬合度也明顯高于WNN模型和PSO-WNN模型。

表1 各類模型交通預測性能對比

5 結 語

本文在建立預測模型之前，利用最大Lyapunov指數(shù)分析交通流的預測性質(zhì)。在現(xiàn)有的短時交通流智能預測模型基礎上，提出基于相空間的GQPSO-WNN的混合預測模型，該方法結合了GA和QPSO的優(yōu)點，優(yōu)化小波神經(jīng)網(wǎng)絡參數(shù)值選取。實驗結果表明，與以往研究中的模型相比，所提模型的收斂速度和預測精確度均可以達到理想水平，有望應用于未來的實際交通領域中。