基于蟻群優(yōu)化支持向量機模型的公路客運量預測

孫 煦， 陸化普， 吳 娟，2

（1.清華大學 交通研究所，北京 100084；2.軍事交通學院 汽車指揮系，天津 300161）

0 引 言

隨著社會經(jīng)濟的持續(xù)快速發(fā)展，人們的出行也更加頻繁，公路交通運輸?shù)玫搅孙w速的發(fā)展。其中，客運量是衡量公路運輸發(fā)展程度的重要指標，可以反映社會經(jīng)濟發(fā)展現(xiàn)狀和人民生活水平，而科學準確地預測公路客運量及其發(fā)展的趨勢、特點和規(guī)律，是制定公路客運發(fā)展規(guī)劃以及規(guī)劃公路客運站場的重要理論依據(jù)［1］。國內外對公路客運量預測方法的研究經(jīng)歷了一個很長的階段，早期主要是以時間序列法、彈性系數(shù)法、回歸分析法、灰色系統(tǒng)預測法等傳統(tǒng)方法為代表［2］，而這些傳統(tǒng)方法主要是集中在對數(shù)據(jù)本身規(guī)律的回歸和時間趨勢外推的分析上，對客運量生成與影響因素的內在作用機理分析不夠，使得數(shù)據(jù)隱含信息量丟失較大。近年來，人工神經(jīng)網(wǎng)絡被廣泛應用于客運量預測中，它具有識別復雜非線性系統(tǒng)的特性，但是也存在著收斂速度慢、過學習和局部極值等問題［3］，這些問題都影響了其預測精度。

支持向量機（Support Vector Machine，簡稱SVM）是一種在統(tǒng)計學習理論基礎上形成的、以實現(xiàn)結構風險最小化為原則的學習方法［4］。與人工神經(jīng)網(wǎng)絡相比，它克服了神經(jīng)網(wǎng)絡所固有的局部極小點、過學習現(xiàn)象以及結構和類型的選擇過于依賴經(jīng)驗等缺陷。由于其具有模型的自由選擇（參數(shù)、基函數(shù)的位置等）、全局最優(yōu)以及良好的泛化能力等特性，因此在小樣本、高維、非線性預測領域具有很好的應用效果［5］。但是和其他學習算法一樣，支持向量機的性能依賴于學習機的參數(shù)，即訓練參數(shù)的選擇對支持向量機的預測效果有著較大的影響。因此，根據(jù)實際的數(shù)據(jù)模型選擇合適的訓練參數(shù)成為關鍵問題。

本文將蟻群算法與支持向量機結合，提出了基于蟻群的支持向量機參數(shù)優(yōu)選方法，利用蟻群算法優(yōu)化其訓練參數(shù)，得到了優(yōu)化的基于蟻群的支持向量機的公路客運量預測模型。以北京市1978—2009年公路客運量數(shù)據(jù)作為實驗數(shù)據(jù)［6］，實驗結果表明，相比于BP神經(jīng)網(wǎng)絡和傳統(tǒng)的SVM方法，基于蟻群的支持向量機模型的預測精度更高、誤差更小，可以更有效地對公路客運量進行預測。

1 支持向量機的基本原理

支持向量機是建立在統(tǒng)計學習理論和結構風險最小化原則基礎上的機器學習方法。它能夠根據(jù)有限樣本信息，在模型復雜性和學習能力之間尋求最佳折衷［7］，有效地實現(xiàn)對基于小樣本的高維非線性系統(tǒng)精確擬合，同時也避免了人工神經(jīng)網(wǎng)絡等方法存在的陷入局部最優(yōu)解的問題，因此具有較好的推廣性。

支持向量機理論可用于分類問題和回歸問題，公路客運量的預測問題屬于支持向量機的回歸問題。其基本原理是：假設給定的訓練樣本為（xi，yi）（xi∈Rn為出入變量，yi∈Rn為對應輸出值，i＝1，2，…，l），通過一個非線性映射φ將數(shù)據(jù)映射到高維特征空間F，從而將非線性回歸問題轉化為高維特征空間的線性問題，即

其中，φ（x）是將樣本點映射到高維空間的非線性變換；w為權值矢量；b為閾值。

根據(jù)結構風險最小化原則，上述函數(shù)回歸問題就是尋求使風險最小函數(shù)最小的f，即

其中，等式右邊前一項（w·w）表示函數(shù)f（x）的復雜性；后一項表示訓練集上的平均損失；懲罰參數(shù)c則體現(xiàn)了函數(shù)的復雜性和訓練集上平均損失之間的折中關系；ε為引入的不敏感損失函數(shù)，其定義為：

最小化（2）式引入非負松弛變量ξi和（i＝l，2，…，l），轉化為等價最優(yōu)化問題：

引入Lagrange乘子αi及，上述優(yōu)化問題轉化為對偶問題：

其中，當αi－非零時對應的訓練樣本為支持向量；K（xi，xj）＝φ（xi）·φ（xj）為核函數(shù)，其作用是不必知道從低維輸入空間到高維特征空間非線性映射φ（x）的具體形式，通過引入核函數(shù)就可得到?jīng)Q策回歸方程［8］。常用的非線性核函數(shù)有徑向基核函數(shù)、多項式核函數(shù)等。鑒于徑向基核函數(shù)構造的SVM具有較強的非線性預測能力，因而本文選擇徑向基核函數(shù)構造支持向量機。

從而得到回歸函數(shù)：

研究表明，支持向量機的預測精度很大程度上受到參數(shù)取值的影響［9］。而傳統(tǒng)的參數(shù)選取基本都是根據(jù)經(jīng)驗反復試驗來選取，選取的時間較長且結果的最優(yōu)性無法保證。為了提高參數(shù)的選取速度和最優(yōu)性，需要采用合適的智能優(yōu)化算法在一定的區(qū)域內搜索各參數(shù)的最優(yōu)組合，從而獲得具有較強預測性能的支持向量機。

2 基于蟻群算法的SVM參數(shù)優(yōu)化模型

蟻群算法是文獻［10］通過模擬蟻群的覓食行為提出的一種新型模擬進化算法。它運用了正反饋、分布式計算和貪婪式啟發(fā)式搜索。該算法適應性強，不用計算目標函數(shù)偏導數(shù)，搜索效率高，尋優(yōu)能力突出，克服了其他智能算法容易陷入局部最優(yōu)的缺點。

鑒于以上優(yōu)點，本文采用蟻群算法建立支持向量機的參數(shù)選擇模型，進行參數(shù)的優(yōu)選。具體來說，就是將SVM的參數(shù)選取看作參數(shù)的組合優(yōu)化，對組合優(yōu)化問題建立目標函數(shù)，采用蟻群優(yōu)化算法來搜索最優(yōu)的目標函數(shù)值，從而找到合適的參數(shù)取值。該模型無需計算梯度等信息，且有較高的全局尋優(yōu)效率。優(yōu)化的流程如圖1所示。

圖1 基于蟻群算法的支持向量機參數(shù)優(yōu)化流程圖

基于蟻群算法的SVM參數(shù)優(yōu)選過程中，由于目標函數(shù)中隱含了各螞蟻所走過的所有節(jié)點的信息以及所建模型當前的準確度，因此蟻群系統(tǒng)是根據(jù)目標函數(shù)值來更新信息素的濃度從而進行反復的搜索尋優(yōu)，所以目標函數(shù)的選擇和蟻群搜索操作的實現(xiàn)是進行參數(shù)優(yōu)選的2個重要步驟。

2.1 目標函數(shù)的選擇

對于支持向量機回歸問題，目的是要逼近系統(tǒng)的非線性模型［11］，因此以均方誤差EMS來描述支持向量機回歸與參考模型間的偏差，即

其中，l為樣本個數(shù)；yi為參考模型的實際值；f（xi）為支持向量機計算的預測值。由此得到蟻群支持向量機模型的目標函數(shù)為：

其中，優(yōu)化變量zi總共為3個，對應于參數(shù)c、σ、ε；［ai，bi］為各個變量zi的定義域；yi為實際值；f（xi）為通過SVM計算出的預測值。目標函數(shù)即是選取最佳的參數(shù)組合，使得訓練樣本集的總誤差最小，而尋參過程就是最小化F。

2.2 蟻群搜索操作步驟

2.2.1 相關參數(shù)的初始化設定

初始化確定蟻群算法的基本參數(shù)，如種群大小m、信息素更新比例因子ρ、信息素啟發(fā)因子α等；確定蟻群搜索操作的終止條件（本文設定最大循環(huán)次數(shù)Nmax作為終止條件）。

2.2.2 節(jié)點及路徑的生成

分別設定c、σ和ε具有相應的有效數(shù)位使得待優(yōu)化變量X（統(tǒng)一代表這3個變量）具有n維分量，即X＝｛x1，x2，…，xn｝，同時將各分量等分成N個節(jié)點，并在xOy平面上表示出N＊n個節(jié)點，用符號 Knot（xi，yi，j）表示一個節(jié)點。xi（i＝1～n）中的N個節(jié)點組成一個層Li，共有n層。

設定螞蟻數(shù)m，給每只螞蟻k（k＝1～m）各定義一個具有n個元素的一維數(shù)組Pathk，在Pathk中依次存放第k只螞蟻從L1層開始直至到達Ln層所要經(jīng)過的n個節(jié)點的縱坐標值，可用來表示第k只螞蟻的爬行路徑。

2.2.3 迭代搜索

（1）設定初始時刻t＝0，m只螞蟻都位于起始點處，搜索開始后，根據(jù)（9）式計算每只螞蟻k（k＝1～m）從Li－1層向Li層的轉移概率Pk（xi，yi，j），采 用 賭 輪 法 選 擇 Li層 上 的 某 個 節(jié) 點Knot（xi，yi，j），從而轉移到該節(jié)點，同時將該節(jié)點的縱坐標值存入Pathk的第i個元素中。t時刻的轉移概率Pk（xi，yi，j）計算公式為：

其中，τ（xi，yi，j，t）為t時刻節(jié)點 Knot（xi，yi，j）上遺留的信息量，假設初始時刻各節(jié)點上的信息素相等，信息素增量為零，即τ（xi，yi，j，0）＝γ（γ 為常數(shù)），Δτ（xi，yi，j，t）＝0；η 表 示 由 Knot（xi－1，yi，j）到 Knot（xi，yi，j）的期望程度，與上一次循環(huán)的目標函數(shù)值F有關。

（2）經(jīng)過n個時間單位后，m只螞蟻都從起始點爬到終點，將螞蟻k（k＝1～m）所走過的路徑即數(shù)組Pathk組成一個解X＊，計算出相應的目標函數(shù)值F＊，比較各目標函數(shù)值，確定本次循環(huán)中的最優(yōu)路徑（即對應的目標函數(shù)值最小的路徑），并記錄與其對應的c、σ和ε值。

（3）令t＝t＋n，N＝N＋1，按照（10）式更新此時刻各節(jié)點上的信息量，并將Pathk（k＝1～m）中的所有元素清零。

其中，Q為信息強度，它在一定程度上影響算法的收斂速度；Fk為第k只螞蟻在本次循環(huán)中的目標函數(shù)值，由（8）式計算。

2.2.4 終止準則

本文的終止條件為預設的最大迭代次數(shù)Nmax。若N＜Nmax，且整個蟻群尚未收斂到走同一條路徑，則再次將全部螞蟻置于起始點0并重復操作迭代搜索中的各步驟，直到所有螞蟻全部收斂到一條路；若N＜Nmax，且整個蟻群已收斂到走同一條路徑，則算法結束，輸出最優(yōu)路徑所對應的相應的c、σ和ε。

3 公路客運量預測實例分析

3.1 公路客運量預測

以北京市1978—2009年的公路客運量數(shù)據(jù)為應用實例（2006、2007年的數(shù)據(jù)由于具有特異性，因此剔除掉）。先以其中奇數(shù)年的公路客運量數(shù)據(jù)作為訓練數(shù)據(jù)，形成訓練樣本集，以偶數(shù)年的數(shù)據(jù)作為測試數(shù)據(jù)，形成測試集；再以偶數(shù)年的公路客運量數(shù)據(jù)作為訓練數(shù)據(jù)，形成訓練集，以奇數(shù)年的數(shù)據(jù)作為測試數(shù)據(jù)，形成測試集，從而對模型進行反復訓練。模型的各參數(shù)設置如下：c的取值范圍為（0.01，200），ε的取值范圍為（0，0.8），σ的取值范圍為（0.001，100）；螞蟻種群大小m＝50，最大迭代 Nmax＝500，信息素更新比例因子ρ＝0.7，α＝1，β＝5，Q＝100。

3.2 預測結果分析

數(shù)據(jù)的歸一化結果見表1所列。為了驗證模型的有效性，同時選取了BP神經(jīng)網(wǎng)絡法及使用交叉驗證試算的傳統(tǒng)SVM法對同一實例進行預測。選取以下2個誤差指標作為各種方法預測效果判斷的依據(jù)（yi指樣本提供的實際值，yi＊指根據(jù)模型求得的預測值，n為預測值個數(shù)），即相對誤差ERP和平均絕對百分比誤差EMAP。

表1 數(shù)據(jù)及歸一化結果 104人

通過對訓練樣本集進行反復訓練［12］，選擇最優(yōu)的模型參數(shù)，從而分別建立蟻群支持向量機預測模型、BP神經(jīng)網(wǎng)絡預測模型以及傳統(tǒng)SVM預測模型。

利用3種模型通過訓練奇數(shù)年份的數(shù)據(jù)所得到的偶數(shù)年份客運量的預測結果對比如圖2所示，利用3種模型通過訓練偶數(shù)年份的數(shù)據(jù)所得到的奇數(shù)年份客運量的預測結果對比如圖3所示。

圖2 偶數(shù)年份客運量數(shù)據(jù)預測結果比較

圖3 奇數(shù)年份客運量數(shù)據(jù)預測結果比較

3種方法在2次預測中得到的所有年份的預測值以及與實際值相比較得到的誤差結果見表2所列。

表2 GA－SVM及傳統(tǒng)SVM、BP神經(jīng)網(wǎng)絡的預測結果比較

從表2中可以看出，基于蟻群算法的支持向量機預測模型比傳統(tǒng)SVM和BP神經(jīng)網(wǎng)絡模型效果明顯要好，而傳統(tǒng)SVM模型效果略好于傳統(tǒng)BP神經(jīng)網(wǎng)絡。這是因為SVM方法具有全局最優(yōu)性，不會陷入局部最小點，避免了傳統(tǒng)神經(jīng)網(wǎng)絡方法的缺陷，提高了預測精度。而基于蟻群的支持向量機方法，由于對影響支持向量機預測精度的重要參數(shù)c、ε和σ進行了基于蟻群算法的連續(xù)空間的優(yōu)化搜索，避免了人工進行參數(shù)選擇時需要依賴經(jīng)驗的缺陷，從而明顯提高了預測精度。仿真結果也表明，采用蟻群算法優(yōu)化參數(shù)后的支持向量機模型比傳統(tǒng)支持向量機在預測時具有更高的精度和更強的泛化能力，即利用蟻群算法對支持向量機的參數(shù)進行優(yōu)化搜索的方法是可行有效的。

4 結束語

本文提出了基于蟻群算法支持向量機的公路客運量預測方法。支持向量機以統(tǒng)計學為基礎，在小樣本、高維、非線性預測領域有著很好的應用效果，但其預測效果很大程度上取決于其參數(shù)的選取，因此考慮應用蟻群算法來優(yōu)化支持向量機的訓練參數(shù)，從而得到了基于蟻群算法的支持向量機的公路客運量預測模型；以北京市1978—2009年的公路客運量數(shù)據(jù)作為算例，并與BP神經(jīng)網(wǎng)絡和傳統(tǒng)的SVM預測法相對比，驗證了基于蟻群的支持向量機預測模型擬合程度更強，預測精度更高，是一種可行有效的公路客運量的預測方法。研究結果說明基于蟻群算法進行支持向量機參數(shù)優(yōu)選的方法是有效的，具有一定的實際應用價值。

［1］ 劉 芹.基于最小二乘支持向量機的城市客運量預測模型［J］.交通與計算機，2007，25（5）：50－53.

［2］ 陳 荔，馬榮國.基于支持向量機的都市圈客運量預測模型［J］.交通運輸工程學報，2010，10（6）：75－80.

［3］ 文培娜，張志勇，羅 彬.基于BP神經(jīng)網(wǎng)絡的北京物流需求預測及分析［J］.物流技術，2009（6）：91－93.

［4］ Venkoba R B，Gopalakrishna S J.Hard grove grind ability index prediction using support vector regression［J］.International Journal of Mineral Processing，2009，91（12）：55－59.

［5］ Liu Sheng，Li Yanyan.A novel predictive control and its application on water level system of ship boiler［C］／／International Conference on Innovative Computing，Information and Control，2006：8.

［6］ 中國統(tǒng)計出版社.北京市2010年度統(tǒng)計年鑒［EB／OL］.［2011－03－20］.http：／／www.bjstats.gov.cn／nj／main／2010－tjnj／index.htm.

［7］ 耿 睿，崔德光，徐 冰.應用支持向量機的空中交通流量組合預測模型［J］.清華大學學報：自然科學版，2008，48（7）：1205－1208.

［8］ 魏 俊，周步祥，林 楠，等.基于蟻群支持向量機的短期負荷預測［J］.電力系統(tǒng)保護與控制，2009，37（4）：36－40.

［9］ 曹占輝，李言俊.基于支持向量機和蟻群算法的空間目標分類［J］.航空計算技術，2008，38（3）：15－18.

［10］ Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］.IEEE Transaction on Systems，Man，and Cybernetics：Part B，1996，26（1）：29－41.

［11］ 倪麗萍，倪志偉，李鋒剛，等.基于蟻群算法的SVM模型選擇研究［J］.計算機技術與發(fā)展，2007，17（9）：95－98.

［12］ 張志涌.精通MATLAB 6.5版教程［M］.北京：北京航空航天大學出版社，2003：250－257.