基于混合算法優化SVM的短時交通流預測

梅 朵，鄭黎黎，劉春曉，王秀芹

(1.渤海大學 信息科學與技術學院，遼寧 錦州 121013 2.吉林大學 交通學院，吉林 長春 130022)

基于混合算法優化SVM的短時交通流預測

梅 朵1，鄭黎黎2，劉春曉1，王秀芹1

(1.渤海大學 信息科學與技術學院，遼寧 錦州 121013 2.吉林大學 交通學院，吉林 長春 130022)

為了提高城市道路短時交通流預測的精度，提出了一種基于混合算法優化支持向量機的短時交通流預測模型。在粒子群算法中引入遺傳算法的交叉和變異因子，對粒子群算法進行改進，然后用改進后的粒子群算法優化支持向量機，得到最優的支持向量機模型，最后實現城市道路的短時交通流預測。以檢測器采集到的長春市路網數據為基礎進行了實例驗證，結果表明，優化支持向量機參數時，遺傳粒子群算法不會陷入局部最優，優化效果更好；與傳統的支持向量機模型、粒子群優化支持向量機模型相比，所提出的混合算法優化支持向量機模型的相對誤差波動較穩定，得到的短時交通流平均預測精度分別提高了3.63%和2.46%，說明所提出模型的短時交通流預測效果更好。

城市交通；短時交通流預測；遺傳算法；粒子群算法；支持向量機

0 引 言

城市道路是人們賴以生存的環境之一，城市道路出行質量直接影響人們的生活質量。實時獲取城市道路的交通流量，準確預測城市道路的未來交通流量，可以提高城市道路交通控制與誘導的效率，緩解城市道路交通擁堵，改善城市道路出行質量。因此，致力于研究高可靠、高精度的短時交通流預測方法，并形成了許多經典的預測模型，包括：基于線性模型的方法，如歷史平均法、線性回歸法、卡爾曼濾波法等[1-3]；基于非線性理論的方法，如K近鄰非參數回歸法、小波分析法、混沌Elman網絡法等；基于知識發現的智能方法，如基于神經網絡的方法、基于支持向量機的方法等[4-5]；基于混合理論的方法，如基于進化算法的神經網絡預測方法、基于進化算法的支持向量機預測方法、基于小波支持向量機的預測方法等[6-8]；基于新興技術的方法，如基于數據融合的預測方法、基于時空分析

的預測方法、基于云模型的預測方法、基于并行計算的預測方法等[9-10]。

這些模型在一定程度上提高了短時交通流的預測精度，然而也存在一定的不足之處，如支持向量機參數優化效果不好導致最終預測模型精度不高，并行計算的預測方法更適于大規模路網，時空分析的方法操作復雜、不易求解，等等。

因此，文中在已有研究成果的基礎上，提出一種基于混合算法優化支持向量機的短時交通流預測方法。以城市小區域路網中的某條路段為研究對象，深入研究粒子群算法，發現其不足之處，利用遺傳算法對其進行改進，并用改進后的粒子群算法優化支持向量機模型，得到最優的短時交通流預測模型，并以長春市城市道路的檢測器數據為基礎對該方法進行驗證。

1 支持向量機

短時交通流預測是一類非線性問題，支持向量機(Support Vector Machine，SVM)是解決這類問題的主要方法[11]。

SVM的基本思想如下：

已知學習樣本T={(x1,y1),…,(xi,yi),…,(xl,yl)}，xi∈Rn表示短時交通預測模型的輸入變量，yi∈R表示短時交通預測模型的輸出預測值，i=1,2,…,l是學習樣本數。引入拉格朗日函數φm(x)=[φ1(x),φ2(2),…,φN(x)]T，將原始的非線性優化問題變成線性優化問題：

(1)

(2)

(3)

經過求解，得到SVM預測模型：

(4)

2 混合算法優化支持向量機

在SVM中，懲罰因子C、不敏感損失因子ε和核函數因子σ對預測輸出值的影響非常大，為了取得更高的預測精確度，必須對它們進行優化。文中采用粒子群算法對SVM的參數進行優化。

粒子群算法(Particle Swarm Optimization，PSO)是一種典型的進化算法，源于對鳥類捕食行為的研究，由于其實現簡單、精度高、收斂速度快等優點，被廣泛應用到各領域[12]。然而，粒子群算法沒有選擇策略，也沒有交叉和變異過程，容易陷入局部最優，因此考慮采用遺傳算法對其進行改進。引入遺傳算法的選擇、交叉算子和變異算子，一方面改善參數優化效果，提高預測精確度；另一方面兩種算法取長補短，避免粒子群算法陷入局部最優，混合算法又具有較快的收斂能力。文中設計的基于混合算法優化支持向量機參數的具體流程如圖1所示。

圖1 遺傳粒子群算法優化支持向量機的具體流程

2.1粒子編碼與譯碼

為了解決支持向量機的參數優化問題，粒子編碼是關鍵。針對支持向量機參數優化問題的特點，在粒子編碼過程中，根據參數的取值范圍，采用二進制編碼方式[13]。此時，第i代粒子p(i)可表示為：

p(i)={Cn1,…,Cni,ε1i,…,εni,σni,…,σni}

(5)

其中，Cni、εni和σni分別為懲罰因子、敏感損失因子和核函數因子的位串。

在短時交通流預測中，C、ε和σ的取值范圍分別為[0.1,150]、[0.01,0.5]和[0.01,10]，所以C、ε和σ的位串長度均為8。

粒子解碼的公式如下：

(6)

其中，Xj表示優化參數；xj表示優化參數位串的第j位。

2.2適應度函數

適應度函數影響支持向量機參數優化的效果，選擇均方根誤差函數作為適應度函數，即：

(7)

2.3粒子速度和位置的更新

根據粒子適應度函數可以得到每一個粒子的個體最優解和全局最優解，然后分別采用式(8)和式(9)對粒子速度和位置進行更新。

(8)

xi+1=xi+?i+1

(9)

2.4遺傳算法改進粒子群算法

為了彌補粒子群算法容易陷入局部收斂的缺陷，引入遺傳算法(Genetic Algorithm，GA)的選擇、交叉算子和變異算子，盡量保留父代個體的優秀基因，并保持種群的多樣性[14]。

粒子群算法的繁殖過程是一種全部粒子與最優粒子的配對過程，這樣容易造成粒子聚集，因此引入遺傳算法的選擇運算，避免粒子過分聚集，陷入局部最優。選擇運算采用輪盤賭方法，被選擇的個體再進行下一步的交叉和變異運算。以自適應的交叉和變異概論函數控制交叉和變異運算。

自適應交叉和變異函數分別為：

(10)

(11)

3 基于混合算法優化支持向量機的短時交通流預測

基于混合算法優化支持向量機的短時交通流預測方法的具體步驟為：

(1)學習樣本的預處理，得到各路段的歷史交通流量時間數據序列；

(2)用混合算法優化SVM參數，得到最優的SVM短時交通流預測模型；

(3)預測并輸出結果。

3.1學習樣本的預處理

對交通流時間數據序列進行歸一化處理。

y=

(12)

其中，x為原始交通流時間數據序列；j為歸一化處理后的交通流時間數據序列。

3.2評價指標選取

選取的評價指標，即平均相對誤差、相對誤差、最大相對誤差、均方根誤差分別如下：

(13)

(14)

(15)

(16)

4 實例驗證

實驗的數據來源是檢測器采集的長春市路網的實測流量數據，數據采集時間是2010年7月某周周一到周五的早7:00到晚7:00，采集時間間隔為5 min，共采集720組數據。以某路段為預測路段，將各路段周一到周四的流量數據作為學習樣本，預測路段周五的數據為預測樣本，對其進行短時交通流預測。實驗軟件環境是MATLAB7.0.1，通過編程設計了傳統SVM、GPSO-SVM、PSO-SVM三組實驗，分別用三種預測方法進行短時交通流預測，并將預測效果進行對比。

4.1支持向量機參數優化

設置GPSO模型和PSO模型的種群規模為30,最大迭代次數為100，傳統SVM、PSO-SVM和GPSO-SVM得到的SVM參數優化結果如表1所示。

表1 支持向量機的參數優化結果

4.2實驗結果與分析

預測結果分別如圖2～4所示。

圖2 傳統SVM的預測結果

圖3 PSO-SVM的預測結果

圖4 GPSO-SVM的預測結果

對比圖2～4發現，與傳統SVM和PSO-SVM相比，GPSO-SVM預測方法的預測結果和實際值擬合效果更好，預測結果更加接近于實際值。

三種預測方法的預測結果相對誤差如圖5所示。

由圖5發現，即使在交通流變化很大的情況下，GPSO-SVM模型預測結果的相對誤差曲線波動情況也比較穩定，原因是引入了遺傳算法的選擇算子及自適應交叉和變異函數，使粒子群不至于陷入聚集狀態，導致局部收斂，從而得到更優的預測結果。

圖5 GPSO-SVM的相對誤差

對比其他三個評價指標可以發現：傳統SVM和PSO-SVM的預測結果平均相對誤差分別為10.49%和9.32%，而文中提出的GPSO-SVM預測方法所得的預測結果平均預測誤差為6.86%。此外，用遺傳算法改進后的GPSO-SVM預測方法得到的預測結果最大相對誤差為10.9%，均方根誤差為0.070 1，均小于傳統SVM和PSO-SVM，說明GPSO-SVM預測方法的預測誤差波動范圍較小，預測精度更高，短時交通流預測效果更好。

5 結束語

文中運用遺傳算法改進粒子群算法，構成一種混合算法。該算法既具備遺傳算法可以得到近乎全局最優解的特點，也具備粒子群算法收斂速度快的優勢。然后用這種混合算法對支持向量機的三個重要參數進行優化，得到最優的短時交通流預測模型，最后設計實驗進行驗證。實驗結果表明，與傳統支持向量機、粒子群優化支持向量機相比，文中方法的預測精度更高，預測效果更好，具有一定的有效性、可行性和優越性。

[1] Smith B L,Williams B M,Oswald R K.Comparison of parametric and nonparametric models for traffic flow forecasting[J].Transportation Research Part C:Emerging Technologies,2002,10(4):303-321.

[2] Williams B M,Hoel L A.Modeling and forecasting vehicular traffic flow as a seasonal ARIMA process:theoretical basis and empirical results[J].Journal of Transportation Engineering,2003,129(6):664-672.

[3] 朱征宇，劉 琳，崔 明.一種結合SVM與卡爾曼濾波的短時交通流預測模型[J].計算機科學，2013，40(10)：248-251.

[4] 楊兆升，王 媛，管 青.基于支持向量機方法的短時交通流量預測方法[J].吉林大學學報:工學版，2006，36(6)：881-884.

[5] Zhu Y,Zhang G, Qiu J. Network traffic prediction based on particle swarm BP neural network[J].Journal of Networks,2013,8(11):2685-2691.

[6] 梅 朵.基于云計算的交通瓶頸控制與誘導協同模型研究[D].長春：吉林大學，2015.

[7] Zhang H,Zhao G,Chen L,et al.Short-term prediction of wind power based on an improved PSO neural network[J].TELKOMNIKA Indonesian Journal of Electrical Engineering,2014,12(7):4973-4980.

[8] 廖榮華，蘭時勇，劉正熙.基于混沌時間序列局域法的短時交通流預測[J].計算機技術與發展，2015，25(1)：1-5.

[9] Min W，Wynter L.Road traffic prediction with spatio-temporal correlations[J].Transportation Research Part C:Emerging Technologies,2011,19(4):606-616.

[10] Yang Zhaosheng,Mei Duo,Yang Qingfang,et al.Research on traffic flow prediction model for large-scale road network based on cloud computing[J].Mathematical Problems in Engineering,2014(5):1-8.

[11] 孫曉雯，孫子文，秦 昉.基于閾值與PSO-SVM的人體跌倒檢測研究[J].計算機工程，2016，42(5)：317-321.

[12] 曾勍煒，徐如海，吳 鍵.基于粒子群優化和支持向量機的電力負荷預測[J].微電子學與計算機，2011，28(1)：147-149.

[13] 張 進，丁 勝，李 波.改進的基于粒子群優化的支持向量機特征選擇和參數聯合優化算法[J].計算機應用，2016，36(5)：1330-1335.

[14] Pourbasheer E，Riahi S，Ganjali M R，et al.Application of Genetic Algorithm-Support Vector Machine (GA-SVM) for prediction of BK-channels activity[J].European Journal of Medicinal Chemistry，2009，44(12)：5023-5028.

AShort-termTrafficFlowPredictionModelBasedonSupportVectorMachineOptimizedbyHybridAlgorithm

MEI Duo1，ZHENG Li-li2，LIU Chun-xiao1，WANG Xiu-qin1

(1.College of Information Science and Technology,Bohai University,Jinzhou 121013,China;2.College of Transportation,Jilin University,Changchun 130022,China)

In order to improve the accuracy of short term traffic flow prediction,a short-term traffic flow forecasting model based on support vector machine optimized by hybrid algorithm is proposed.The crossover and mutation factor of genetic algorithm is introduced to improve particle swarm optimization.And then,the support vector machine is optimized based on the improved particle swarm optimization to obtian the optimal support vector machine model.Finally,the short term traffic flow prediction is realized.It is verified based on the data collected from Changchun City Road Network.The results show that when optimizing the parameters of support vector machine,the genetic particle swarm optimization does not fall into local optimum and gets better effect of optimization.Compared with the model of traditional support vector machine and particle swarm optimized support vector machine,it is more stable and its average prediction accuracy of short term traffic flow is improved by 4.96% and 3.41% respectively,showing the better effect of prediction.

urban traffic;short-term traffic flow prediction;genetic algorithm;particle swarm optimization;support vector machine

2016-11-27

2017-03-03 < class="emphasis_bold">網絡出版時間

時間：2017-07-19

國家青年科學基金(E080701)

梅 朵(1985-)，女，講師，博士，研究方向為云計算、智能交通系統。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1113.088.html

U491.2

A

1673-629X(2017)11-0092-04

10.3969/j.issn.1673-629X.2017.11.020