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

孫 煦， 陸化普， 吳 娟，2

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

0 引 言

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

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

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

1 支持向量機的基本原理

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

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

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

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

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

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

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

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

從而得到回歸函數：

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

2 基于蟻群算法的SVM參數優化模型

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

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

圖1 基于蟻群算法的支持向量機參數優化流程圖

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

2.1 目標函數的選擇

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

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

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

2.2 蟻群搜索操作步驟

2.2.1 相關參數的初始化設定

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

2.2.2 節點及路徑的生成

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

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

2.2.3 迭代搜索

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

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

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

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

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

2.2.4 終止準則

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

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

3.1 公路客運量預測

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

3.2 預測結果分析

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

表1 數據及歸一化結果 104人

通過對訓練樣本集進行反復訓練［12］，選擇最優的模型參數，從而分別建立蟻群支持向量機預測模型、BP神經網絡預測模型以及傳統SVM預測模型。

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

圖2 偶數年份客運量數據預測結果比較

圖3 奇數年份客運量數據預測結果比較

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

表2 GA－SVM及傳統SVM、BP神經網絡的預測結果比較

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

4 結束語

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

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

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

［3］ 文培娜，張志勇，羅 彬.基于BP神經網絡的北京物流需求預測及分析［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］ 中國統計出版社.北京市2010年度統計年鑒［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］.電力系統保護與控制，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］.計算機技術與發展，2007，17（9）：95－98.

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