基于改進LSSVM的短時交通流量預測

婁婉秋

（四川大學計算機學院，成都 610065）

基于改進LSSVM的短時交通流量預測

婁婉秋

（四川大學計算機學院，成都 610065）

為提高短時交通流量預測的準確性，提出一種基于改進LSSVM的短時交通流量預測模型。針對傳統混合蛙跳算法（SFLA）容易陷入局部最優的問題，提出基于新局部更新策略的改進混合蛙跳算法（ISFLA）,在此基礎上將其與最小二乘支持向量機（LSSVM）相結合，通過采用該算法優化LSSVM的關鍵參數，從而提高LSSVM的預測能力。結合實例，對模型和算法進行仿真分析，證明模型的可行性和算法的有效性。

短時交通流量預測；最小二乘支持向量機；改進蛙跳算法；參數選擇；智能優化算法

0 引言

排序是計算機程序設計中一項基本的操作，在實際應用中，有很多情況下需要對數據按照某種方式進行排序后才能達到某種要求，因此，學習和研究各種排序方法是計算機工作者的重要課題之一。

對交通流量進行精確的預測是緩解交通堵塞現象的重要基礎，也是實現智能交通系統的一個核心部分。交通流量預測是指基于當前和過去的交通流量信息，使用合適的預測模型對未來的交通流量進行預測。其中短時交通流量預測是指時間范圍在30分鐘內的預測。由于短時交通流量具有隨機性、不確定性和突發性，對短時交通流量進行有效準確預測是智能交通管理領域的一個難題。

針對短時交通流量預測，國內外學者提出了許多預測方法。一類是傳統的數學方法，例如卡爾曼濾波方法[1]、自回歸滑動平均方法[2]。這些方法實現簡單，對于緩慢變化的交通流量預測效果較佳；缺點則是無法反映交通流中的不確定性和非線性，難以對短時交通流量進行精確預測。針對這個問題，學者們提出了另外一類基于人工智能的方法，例如神經網絡方法[3]和支持向量機方法[4]。神經網絡模型雖然在描述非線性系統中有杰出的性能，但是過于強調學習誤差，這會導致過擬合，并且，由于神經網絡方法基于經驗風險最小化原則，導致在處理小樣本數據時效果不佳。而支持向量機克服了神經網絡模型的上述固有缺點[5]，其中，最小二乘支持向量機（LSSVM），對標準支持向量機進行了改進，廣泛應用于短時交通流量預測中[6]。該算法的預測結果與其相關參數的選取密切相關。不合適的參數選擇會導致LSSVM預測能力下降。目前已經采用遺傳算法、粒子群算法、網格搜索算法[7～8]等對LSSVM的相關參數進行優化。然而這些算法有容易陷入局部最優值，初始參數設置過多等缺點。

混合蛙跳算法（Shuffled Frog Leaping Algorithm, SFLA）是2003年Muzaffar Eusuff和Kevin Lansey提出的一種新型群體智能優化算法，可以用于解決許多復雜的如非線性、多維的優化問題[9]。該算法結合了粒子群算法（PSO）和模因算法（MA）的優點，并且具有容易理解、設置參數少、計算速度快以及全局搜索尋優能力較佳的特點。

跟大多數智能優化算法一樣，SFLA算法也易陷入局部最優值。針對這個問題，本文首先對SFLA算法進行了改進，通過提出新的局部個體更新策略在一定程度上使算法跳出局部最優，獲得更優的優化結果。在此基礎上，提出改進混合蛙跳算法優化最小二乘支持向量機的短時交通流量預測模型（ISFLA-LSSVM），通過優化LSSVM中影響其預測能力的正則化參數γ和核參數σ，以提高短時交通流量的預測精度。并通過仿真實驗驗證了ISFLA-LSSVM的有效性。

1 方法介紹

對于給定的訓練數據樣本集，D=｛（x1，y1），…，（xk，yk），…，（xn，yn）｝，xk∈R，yk∈R，其中xi是時間序列樣本的輸入，yi是相應的輸出，n是訓練樣本數目。通過非線性函數?（x），LSSVM方法把樣本空間映射到高維特征空間中進行回歸，回歸函數如下所示：

其中w是權重，b是偏差值，f（x）表示預測值。根據結構風險最小化原則，LSSVM的回歸問題可以表示為如下所示的優化問題：

其中ei是誤差變量，表示實際值與預測值之間的誤差，γ是正則化參數，用于平衡模型的訓練誤差和復雜度。為了解決上述優化問題，建立拉格朗日函數：

其中αi表示拉格朗日算子。分別對w、b、e、α求偏微分并設置為零，有：

從上述方程組中消去w和e后，可以得到：

式中y=［y1；…yi；…yn］，Ii=［1；…1］，α=［α1；…；αn］，k（xi，xj）=?（xi）?（xj）T，所求的擬合函數為：

本文中采用的核函數為徑向基函數，k（xi，xj）=exp（-‖xi-xj‖2/δ2），其中σ表示核函數的寬度。選定核函數后，需要選擇合適的正則化參數γ和核參數σ。這兩個參數會影響LSSVM的學習能力和泛化性能。本研究采用改進蛙跳算法對上述兩個參數進行優化，以提高短時交通流量的預測精度。

2 ISFLA-LSSVM的交通流量預測

2.1 傳統SFLA算法

SFLA算法是模仿青蛙群體尋找食物的過程而提出的一種新型智能優化算法。該算法包括兩個核心過程：青蛙子群間的全局信息交換過程以及子群內部的局部更新過程[10]。

（1）子群間全局信息交換

①參數初始化：隨機產生L只青蛙組成初始青蛙群體G={X1，X2，…，XL}，每一只青蛙個體X表示所求問題的一個可行解，即如下所示：X=（x1，x2，…，xd），其中d表示青蛙個體的維數。

②計算種群中所有青蛙個體X的適應度值f（X）并按適應度值大小進行降序排序。將排序后的整個青蛙群體分為m個子群，每個子群有n只青蛙，其中m和n滿足L=m×n。分群規則如下所示：第一只青蛙屬于第一個子群，第二只青蛙屬于第二個子群，依次分配直到第n只青蛙屬于第n個子群，然后循環使第n+1只青蛙又屬于第一個子群，直到所有的青蛙都分配完畢。對于青蛙群體，我們用Gb表示全局具有最大適應度值的解。對于每一個子群，我們分別用Zb和Zw表示具有最大適應度值和最小適應度值的解。

③子群內部局部迭代搜索：根據②中的搜索過程對每一個子群中擁有最小適應度值的青蛙個體位置進行更新。

④將每個子群中的所有青蛙個體全部混合為一個新群體并按適應度值大小重新進行降序排序。

⑤算法結束條件判斷：判斷迭代次數t是否達到規定的最大值，如果未達到，返回到步驟②中，否則輸出最優解。

（2）子群內部局部更新

子群內部局部更新主要是對每個子群中適應度值最小的青蛙個體位置更新。

①k表示子群內部迭代次數，初始值設為0；

②對k進行加1操作，然后根據適應度值大小得到該子群中適應度值最大和最小的青蛙個體。

③對子群中具有最小適應度值的青蛙個體進行更新，更新策略如下所示：

其中rand（ ）函數產生一個范圍在0～1之間的隨機數，S表示青蛙個體的移動步長，Dmax表示青蛙允許移動的最大距離。

④根據更新結果調整對應的更新方式

如果上述過程能夠產生一個更優解，即能夠產生一個適應度值更大的個體，那么用新位置的青蛙取代原來該子群中擁有最小適應度值的青蛙個體，否則，用Gb代替Fb，即步長公式變為：

對最差個體重復上述更新過程。如果仍然不能產生一個更優解，那么隨機產生一只青蛙代替該子群中適應度值最小的青蛙個體。

⑤子群局部更新結束條件判斷

若迭代次數k滿足最大值，返回執行（1）中的步驟③，否則返回執行（2）中的步驟③。

2.2 改進SFLA算法

基本蛙跳算法的局部更新過程即基于最優青蛙個體影響最差青蛙個體的方式去更新子群中的最差個體。該過程首先基于各子群內部適應度值最大和最小的青蛙個體對適應度值最小的青蛙個體進行更新，如果產生的新個體不是更優解，即適應度值更大，那么我們重新基于群體適應度最大值對位置最差的青蛙個體進行更新，如果產生的新個體仍然不是最優解，那么我們隨機產生一個新個體代替原來子群內部適應度值最小的個體。

在此基礎上，本文對傳統混合蛙跳算法進行了如下兩點改進：

（1）首先考慮在局部更新的過程中，同時基于子群內部以及整個種群適應度值最大個體去更新各子群內部適應度值最小個體，從而避免陷入局部最優，并且，通過這樣的改進還可以減少算法的運行時間。即使用一種新的步長計算公式：

（2）其次，本文提出了新的青蛙個體更新公式，以更新各子群內最差青蛙個體的位置。新公式如下所示：

設w（k）是一個隨著子群內部迭代次數k的增加而逐漸減少的函數。w（k）=（kmax-k+rand（ ）），由此可知，早期迭代中大的w（k）值可以擴大解空間的搜索范圍，即增加解決方案的多樣性，而后期迭代中小的w（k）值使得算法在局部范圍內搜索更優解，即進一步提高局部搜索的能力。

2.3 ISFLA優化LSSVM的短時交通流量預測模型

本文改進的混合蛙跳算法（ISFLA）優化LSSVM模型中參數的步驟如下所示：

（1）初始化基本參數，如青蛙的數目L，子群數目m，子群內部迭代次數k，全局迭代次數t，最大迭代次數kmax，全局最大迭代次數tmax，青蛙個體允許移動的最大距離Dmax；

（2）每只青蛙個體的位置對應一組LSSVM的正則化參數和核參數（γ，σ），計算所有青蛙的適應度值并記錄全局最優解。我們設置精確度PRE為適應度函數，每個青蛙個體根據適應度函數值進行優劣排序并且分成子群。

（3）對每個子群的適應度值最小的青蛙個體先按公式（10）和（11）進行更新，如果新位置的青蛙個體適應度值大于原來的適應度值，則更新后的青蛙個體替換原來適應度值最小的青蛙，否則仍隨機生成一個新青蛙個體替代原子群中適應度值最小的青蛙個體，重復上述過程，直到滿足子群內部最大迭代次數。

（4）混合所有子群，對所有青蛙個體按適應度值大小進行重新降序排序。

（5）如果終止條件不滿足，返回第（2）步，否則輸出最大的適應度值的青蛙所在的位置，即最優的LSSVM參數對（γ，σ）。

改進蛙跳算法優化LSSVM的步驟示意圖如圖1所示：

圖1 改進蛙跳算法優化LSSVM示意圖

3 仿真結果分析

3.1 數據來源

本文中數據來源于2012年四川省某段高速公路，搜集了從7月15日至22日的每天早9點到晚8點每15分鐘的流量，得到48×8=384個數據。用前7天的數據作為訓練集訓練模型，而后1天的數據作為測試集以驗證模型的預測效果。

顯然當前交通流量與歷史交通流量之間有著明顯的聯系。v（t）表示t時刻的交通流量，v（t-1）表示t-1時刻的交通流量，我們使用當前時刻以及歷史時刻的交通流量來預測下一時刻的交通流量，如下所示：

其中Xi表示系統的輸入，Yi表示系統的輸出。本文中我們設置n為6。

3.2 參數設置

為了驗證ISFLA-LSSVM模型在短時交通流量預測中的有效性，進行了如下三種實驗：（1）采用改進后的混合蛙跳算法（ISFLA）優化后的LSSVM模型進行預測；（2）采用傳統SFLA算法優化后的LSSVM模型進行預測；（3）采用網格搜索算法（GS）優化后的LSSVM模型進行預測。實驗（1）中算法參數設置如下所示：γ的范圍為（0，1000），σ的范圍為（0，100），青蛙數目設置為100，子群數目設置為5，子群內部迭代次數設置為10，總迭代次數設置為20，最大移動步長設置為50。實驗（2）的參數設置與實驗（1）一樣。實驗（3）的參數設置則如下所示：迭代截止誤差為10-3，γ和σ的搜索范圍同上，步長設置為10。

?

3.3 評價指標

為了驗證所提出的模型的有效性和優越性，使用如下指標作為模型預測性能的評價指標：MRE、RMSE和精確度PRE。

其中xk是預測值是實際值。這三個指標反映了模型的誤差和預測能力，RMSE和MRE的值越小，精確度PRE的值越大，表明模型的預測性能越強。

3.4 實驗結果分析

通過ISFLA算法優化LSSVM參數我們可以構造基于ISFLA-LSSVM的短時交通流量預測模型。LSSVM根據改進混合蛙跳算法、蛙跳算法、網格搜索算法找到的最優參數建立的短時交通流量預測模型預測值與實際值示意圖如圖2所示。

圖2 不同方法流量預測示意圖

圖3 ISFLA與SFLA的迭代尋優圖

由圖2可知，三種預測模型中ISFLA-LSSVM的預測值與實際值偏差最小，預測結果最好。

表1為三種預測模型的預測結果對比，從表1我們可以看出，ISFLA-LSSVM模型的MRE和RMSE最小，分別為0.058以及39.60，明顯低于SFLA-LSSVM模型以及GS-LSSVM模型。精確度最高，為94.13。因此，與其他兩種模型相比，本文提出的ISFLA-LSSVM模型是最優的。

表2 不同方法預測結果表

圖3描述了基于改進混合蛙跳算法和傳統混合蛙跳算法優化最小二乘支持向量機在迭代尋優次數為20次時的適應值變化過程。

由圖3可知，與基本混合蛙跳算法相比，本文提出的改進蛙跳算法迭代初期全局搜索能力較強，不易陷入局部最優，迭代后期局部搜索能力較強，收斂效果較優，尋優結果較好。

4 結語

傳統混合蛙跳算法容易陷入局部最優，本文通過對該算法局部更新策略進行修改，提出了改進混合蛙跳算法（ISFLA）。改進后的算法較好地平衡了全局搜索能力和局部更新能力，不易陷入局部最優。并且針對短時交通流量預測中使用最小二乘支持向量機模型時參數難以選擇的問題，本文使用ISFLA算法對其中的參數進行優化，提出了ISFLA-LSSVM短時交通流量預測模型。通過實例證明，與參比模型相比，改進后的預測模型有較高的預測精度，適合應用于短時交通流量預測。

[1] 沈國江，王嘯虎，孔祥杰.短時交通流量智能組合預測模型及應用[J].系統工程理論與實踐，2011，31（3）：561～568

[2] Bidisha Ghosh，Biswajit Basu，Margaret O'Mahony.Multivariate Short-term Traffic Flow Forecasting Using Time-series Analysis[J]. IEEE Transactions on Intelligent Transportation Systems，2009，10（2）：246～254

[3] 董春嬌，邵春福，熊志華，李娟.基于Elman神經網絡的道路網短時交通流預測方法[J].交通運輸系統工程與信息，2010，10（1）：145～151

[4] 姚智勝，邵春福，等.基于主成分分析和支持向量機的道路網短時交通流量預測[J].吉林大學學報（工學版），2008，38（1）：48～52

[5] Huang Xiaolin，Shi Lei，Suykens，Johan A.K.Support Vector Machine Classifier with Pinball Loss[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（5）：984～997

[6] 趙亞萍，張和生等.基于最小二乘支持向量機的交通流量預測模型[J].北京交通大學學報，2011，35（2）：114～117

[7] GAO Junwei，LENG Ziwen，ZHANG Bin.Traffic Flow Forecasting Based on Phase Space Reconstruction and PSO-LSSVM[J].ICIC Express Letters，2014，8（1）：63～70

[8] 陳帥，朱建寧，潘俊，侍洪波.最小二乘支持向量機的參數優化及其應用[J].華東理工大學學報（自然科學版），2008，34（2）：278-～282

[9] ZHU Guangyu，ZHANG Weibo.An Improved Shuffled Frog-leaping Algorithm to Optimize Component Pick-and-Place Sequencing Optimization Problem[J].Expert Systems with Applications，2014，41（15）：6818-6829.

[10] 鄭仕鏈，樓才義，楊小牛.基于改進混合蛙跳算法的認知無線電協作頻譜感知[J].物理學報，2010，59（5）：3611～36

Short-term Traffic Flow Forecasting Based on Improved LSSVM

LOU Wan-qiu
（Department of Computer Science，Sichuan University，Chengdu 610065）

To improve the predicting accuracy,proposes a short-term traffic flow forecasting model which is based on the improved least square support vector machine.Proposes an improved algorithm based on the traditional shuffled frog leaping algorithm,which can let shuffled frog leaping algorithm be not easy to fall into local optima.Uses the ISFLA algorithm to determine the important parameters in LSSVM, which significantly influences the predicting performance in the model.Simulation analysis demonstrates the feasibility of the model and the effectiveness of the algorithm.

Short-Term Traffic Flow Forecasting;Least Square Support Vector Machine;Improved Shuffled Flog Leaping Algorithm;Parameter Selecting;Intelligent Optimization Algorithm

1007-1423（2015）04-0003-06

10.3969/j.issn.1007-1423.2015.04.001

婁婉秋（1991-），女，貴州安順人，研究生，研究方向為智能交通

2015-01-08

2015-01-20

國家自然科學基金（No.11102124）