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

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

基于混合算法優(yōu)化SVM的短時(shí)交通流預(yù)測(cè)

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

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

為了提高城市道路短時(shí)交通流預(yù)測(cè)的精度，提出了一種基于混合算法優(yōu)化支持向量機(jī)的短時(shí)交通流預(yù)測(cè)模型。在粒子群算法中引入遺傳算法的交叉和變異因子，對(duì)粒子群算法進(jìn)行改進(jìn)，然后用改進(jìn)后的粒子群算法優(yōu)化支持向量機(jī)，得到最優(yōu)的支持向量機(jī)模型，最后實(shí)現(xiàn)城市道路的短時(shí)交通流預(yù)測(cè)。以檢測(cè)器采集到的長(zhǎng)春市路網(wǎng)數(shù)據(jù)為基礎(chǔ)進(jìn)行了實(shí)例驗(yàn)證，結(jié)果表明，優(yōu)化支持向量機(jī)參數(shù)時(shí)，遺傳粒子群算法不會(huì)陷入局部最優(yōu)，優(yōu)化效果更好；與傳統(tǒng)的支持向量機(jī)模型、粒子群優(yōu)化支持向量機(jī)模型相比，所提出的混合算法優(yōu)化支持向量機(jī)模型的相對(duì)誤差波動(dòng)較穩(wěn)定，得到的短時(shí)交通流平均預(yù)測(cè)精度分別提高了3.63%和2.46%，說(shuō)明所提出模型的短時(shí)交通流預(yù)測(cè)效果更好。

城市交通；短時(shí)交通流預(yù)測(cè)；遺傳算法；粒子群算法；支持向量機(jī)

0 引 言

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

的預(yù)測(cè)方法、基于云模型的預(yù)測(cè)方法、基于并行計(jì)算的預(yù)測(cè)方法等[9-10]。

這些模型在一定程度上提高了短時(shí)交通流的預(yù)測(cè)精度，然而也存在一定的不足之處，如支持向量機(jī)參數(shù)優(yōu)化效果不好導(dǎo)致最終預(yù)測(cè)模型精度不高，并行計(jì)算的預(yù)測(cè)方法更適于大規(guī)模路網(wǎng)，時(shí)空分析的方法操作復(fù)雜、不易求解，等等。

因此，文中在已有研究成果的基礎(chǔ)上，提出一種基于混合算法優(yōu)化支持向量機(jī)的短時(shí)交通流預(yù)測(cè)方法。以城市小區(qū)域路網(wǎng)中的某條路段為研究對(duì)象，深入研究粒子群算法，發(fā)現(xiàn)其不足之處，利用遺傳算法對(duì)其進(jìn)行改進(jìn)，并用改進(jìn)后的粒子群算法優(yōu)化支持向量機(jī)模型，得到最優(yōu)的短時(shí)交通流預(yù)測(cè)模型，并以長(zhǎng)春市城市道路的檢測(cè)器數(shù)據(jù)為基礎(chǔ)對(duì)該方法進(jìn)行驗(yàn)證。

1 支持向量機(jī)

短時(shí)交通流預(yù)測(cè)是一類非線性問(wèn)題，支持向量機(jī)(Support Vector Machine，SVM)是解決這類問(wèn)題的主要方法[11]。

SVM的基本思想如下：

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

(1)

(2)

(3)

經(jīng)過(guò)求解，得到SVM預(yù)測(cè)模型：

(4)

2 混合算法優(yōu)化支持向量機(jī)

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

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

圖1 遺傳粒子群算法優(yōu)化支持向量機(jī)的具體流程

2.1粒子編碼與譯碼

為了解決支持向量機(jī)的參數(shù)優(yōu)化問(wèn)題，粒子編碼是關(guān)鍵。針對(duì)支持向量機(jī)參數(shù)優(yōu)化問(wèn)題的特點(diǎn)，在粒子編碼過(guò)程中，根據(jù)參數(shù)的取值范圍，采用二進(jìn)制編碼方式[13]。此時(shí)，第i代粒子p(i)可表示為：

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

(5)

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

在短時(shí)交通流預(yù)測(cè)中，C、ε和σ的取值范圍分別為[0.1,150]、[0.01,0.5]和[0.01,10]，所以C、ε和σ的位串長(zhǎng)度均為8。

粒子解碼的公式如下：

(6)

其中，Xj表示優(yōu)化參數(shù)；xj表示優(yōu)化參數(shù)位串的第j位。

2.2適應(yīng)度函數(shù)

適應(yīng)度函數(shù)影響支持向量機(jī)參數(shù)優(yōu)化的效果，選擇均方根誤差函數(shù)作為適應(yīng)度函數(shù)，即：

(7)

2.3粒子速度和位置的更新

根據(jù)粒子適應(yīng)度函數(shù)可以得到每一個(gè)粒子的個(gè)體最優(yōu)解和全局最優(yōu)解，然后分別采用式(8)和式(9)對(duì)粒子速度和位置進(jìn)行更新。

(8)

xi+1=xi+?i+1

(9)

2.4遺傳算法改進(jìn)粒子群算法

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

粒子群算法的繁殖過(guò)程是一種全部粒子與最優(yōu)粒子的配對(duì)過(guò)程，這樣容易造成粒子聚集，因此引入遺傳算法的選擇運(yùn)算，避免粒子過(guò)分聚集，陷入局部最優(yōu)。選擇運(yùn)算采用輪盤(pán)賭方法，被選擇的個(gè)體再進(jìn)行下一步的交叉和變異運(yùn)算。以自適應(yīng)的交叉和變異概論函數(shù)控制交叉和變異運(yùn)算。

自適應(yīng)交叉和變異函數(shù)分別為：

(10)

(11)

3 基于混合算法優(yōu)化支持向量機(jī)的短時(shí)交通流預(yù)測(cè)

基于混合算法優(yōu)化支持向量機(jī)的短時(shí)交通流預(yù)測(cè)方法的具體步驟為：

(1)學(xué)習(xí)樣本的預(yù)處理，得到各路段的歷史交通流量時(shí)間數(shù)據(jù)序列；

(2)用混合算法優(yōu)化SVM參數(shù)，得到最優(yōu)的SVM短時(shí)交通流預(yù)測(cè)模型；

(3)預(yù)測(cè)并輸出結(jié)果。

3.1學(xué)習(xí)樣本的預(yù)處理

對(duì)交通流時(shí)間數(shù)據(jù)序列進(jìn)行歸一化處理。

y=

(12)

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

3.2評(píng)價(jià)指標(biāo)選取

選取的評(píng)價(jià)指標(biāo)，即平均相對(duì)誤差、相對(duì)誤差、最大相對(duì)誤差、均方根誤差分別如下：

(13)

(14)

(15)

(16)

4 實(shí)例驗(yàn)證

實(shí)驗(yàn)的數(shù)據(jù)來(lái)源是檢測(cè)器采集的長(zhǎng)春市路網(wǎng)的實(shí)測(cè)流量數(shù)據(jù)，數(shù)據(jù)采集時(shí)間是2010年7月某周周一到周五的早7:00到晚7:00，采集時(shí)間間隔為5 min，共采集720組數(shù)據(jù)。以某路段為預(yù)測(cè)路段，將各路段周一到周四的流量數(shù)據(jù)作為學(xué)習(xí)樣本，預(yù)測(cè)路段周五的數(shù)據(jù)為預(yù)測(cè)樣本，對(duì)其進(jìn)行短時(shí)交通流預(yù)測(cè)。實(shí)驗(yàn)軟件環(huán)境是MATLAB7.0.1，通過(guò)編程設(shè)計(jì)了傳統(tǒng)SVM、GPSO-SVM、PSO-SVM三組實(shí)驗(yàn)，分別用三種預(yù)測(cè)方法進(jìn)行短時(shí)交通流預(yù)測(cè)，并將預(yù)測(cè)效果進(jìn)行對(duì)比。

4.1支持向量機(jī)參數(shù)優(yōu)化

設(shè)置GPSO模型和PSO模型的種群規(guī)模為30,最大迭代次數(shù)為100，傳統(tǒng)SVM、PSO-SVM和GPSO-SVM得到的SVM參數(shù)優(yōu)化結(jié)果如表1所示。

表1 支持向量機(jī)的參數(shù)優(yōu)化結(jié)果

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

預(yù)測(cè)結(jié)果分別如圖2～4所示。

圖2 傳統(tǒng)SVM的預(yù)測(cè)結(jié)果

圖3 PSO-SVM的預(yù)測(cè)結(jié)果

圖4 GPSO-SVM的預(yù)測(cè)結(jié)果

對(duì)比圖2～4發(fā)現(xiàn)，與傳統(tǒng)SVM和PSO-SVM相比，GPSO-SVM預(yù)測(cè)方法的預(yù)測(cè)結(jié)果和實(shí)際值擬合效果更好，預(yù)測(cè)結(jié)果更加接近于實(shí)際值。

三種預(yù)測(cè)方法的預(yù)測(cè)結(jié)果相對(duì)誤差如圖5所示。

由圖5發(fā)現(xiàn)，即使在交通流變化很大的情況下，GPSO-SVM模型預(yù)測(cè)結(jié)果的相對(duì)誤差曲線波動(dòng)情況也比較穩(wěn)定，原因是引入了遺傳算法的選擇算子及自適應(yīng)交叉和變異函數(shù)，使粒子群不至于陷入聚集狀態(tài)，導(dǎo)致局部收斂，從而得到更優(yōu)的預(yù)測(cè)結(jié)果。

圖5 GPSO-SVM的相對(duì)誤差

對(duì)比其他三個(gè)評(píng)價(jià)指標(biāo)可以發(fā)現(xiàn)：傳統(tǒng)SVM和PSO-SVM的預(yù)測(cè)結(jié)果平均相對(duì)誤差分別為10.49%和9.32%，而文中提出的GPSO-SVM預(yù)測(cè)方法所得的預(yù)測(cè)結(jié)果平均預(yù)測(cè)誤差為6.86%。此外，用遺傳算法改進(jìn)后的GPSO-SVM預(yù)測(cè)方法得到的預(yù)測(cè)結(jié)果最大相對(duì)誤差為10.9%，均方根誤差為0.070 1，均小于傳統(tǒng)SVM和PSO-SVM，說(shuō)明GPSO-SVM預(yù)測(cè)方法的預(yù)測(cè)誤差波動(dòng)范圍較小，預(yù)測(cè)精度更高，短時(shí)交通流預(yù)測(cè)效果更好。

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

文中運(yùn)用遺傳算法改進(jìn)粒子群算法，構(gòu)成一種混合算法。該算法既具備遺傳算法可以得到近乎全局最優(yōu)解的特點(diǎn)，也具備粒子群算法收斂速度快的優(yōu)勢(shì)。然后用這種混合算法對(duì)支持向量機(jī)的三個(gè)重要參數(shù)進(jìn)行優(yōu)化，得到最優(yōu)的短時(shí)交通流預(yù)測(cè)模型，最后設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)支持向量機(jī)、粒子群優(yōu)化支持向量機(jī)相比，文中方法的預(yù)測(cè)精度更高，預(yù)測(cè)效果更好，具有一定的有效性、可行性和優(yōu)越性。

[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] 朱征宇，劉 琳，崔 明.一種結(jié)合SVM與卡爾曼濾波的短時(shí)交通流預(yù)測(cè)模型[J].計(jì)算機(jī)科學(xué)，2013，40(10)：248-251.

[4] 楊兆升，王 媛，管 青.基于支持向量機(jī)方法的短時(shí)交通流量預(yù)測(cè)方法[J].吉林大學(xué)學(xué)報(bào):工學(xué)版，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] 梅 朵.基于云計(jì)算的交通瓶頸控制與誘導(dǎo)協(xié)同模型研究[D].長(zhǎng)春：吉林大學(xué)，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] 廖榮華，蘭時(shí)勇，劉正熙.基于混沌時(shí)間序列局域法的短時(shí)交通流預(yù)測(cè)[J].計(jì)算機(jī)技術(shù)與發(fā)展，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的人體跌倒檢測(cè)研究[J].計(jì)算機(jī)工程，2016，42(5)：317-321.

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

[13] 張 進(jìn)，丁 勝，李 波.改進(jìn)的基于粒子群優(yōu)化的支持向量機(jī)特征選擇和參數(shù)聯(lián)合優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，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">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-19

國(guó)家青年科學(xué)基金(E080701)

梅 朵(1985-)，女，講師，博士，研究方向?yàn)樵朴?jì)算、智能交通系統(tǒng)。

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