孫 群，袁宏俊

（1.安徽電子信息職業(yè)技術(shù)學(xué)院，安徽蚌埠 233030；2.安徽大學(xué)，安徽合肥 230039；3.安徽財經(jīng)大學(xué)，安徽蚌埠 233030）

蟻群和粒子群算法優(yōu)化支持向量機的公交行程時間預(yù)測

孫 群1,2，袁宏俊2,3

（1.安徽電子信息職業(yè)技術(shù)學(xué)院，安徽蚌埠 233030；2.安徽大學(xué)，安徽合肥 230039；3.安徽財經(jīng)大學(xué)，安徽蚌埠 233030）

為精確預(yù)測公交行程時間，提出了基于蟻群和粒子群（ACO+PSO）優(yōu)化最小二乘支持向量機（LS-SVM）的預(yù)測方法。算法通過對LS-SVM的高斯核參數(shù)σ和正則化參數(shù)C進行搜索尋優(yōu)，獲得更為精確的LS-SVM，建立了ACO和PSO優(yōu)化LS-SVM的公交行程時間預(yù)測模型，根據(jù)歷史數(shù)據(jù)進行實例分析，并與LS-SSVM及BP神經(jīng)網(wǎng)絡(luò)進行比較。實驗表明，ACO+PSO模型的預(yù)測精度高、魯棒性及泛化能力強。

蟻群算法；粒子群算法；最小二乘支持向量機；行程時間預(yù)測

0 引言

隨著城市化進程的加快，城市道路交通的擁堵也不斷加劇，導(dǎo)致公交到站時間不確定等問題。因此，準(zhǔn)確的公交行程時間預(yù)測是提高交通資源利用率，緩解交通擁堵的重要手段。因此，研究公交行程時間的預(yù)測方法對于公交車輛時間的合理安排與調(diào)度、公交資源的合理利用及吸引市民選擇公交出行等具有重要的現(xiàn)實意義。

目前，國內(nèi)外學(xué)者已經(jīng)對公交行程時間的預(yù)測模型進行了很多研究：周雪梅[1]等用統(tǒng)計回歸方法對公交車輛的到站時間進行了預(yù)測；楊兆升[2]等用模糊回歸方程研究了公交行程時間；溫惠英[3]利用灰色理論對公交車輛的行程時間進行預(yù)測；于濱[4]建立支持向量機模型研究了公交車輛的行程時間；周文霞[5]等利用卡爾曼濾波算法來預(yù)測公交的行程時間；彭新建，翁小雄[6]利用螢火蟲尋優(yōu)算法結(jié)合BP神經(jīng)網(wǎng)絡(luò)對公交車輛的行程時間進行了預(yù)測；Patnaik和Chien[7]提出基于多變量回歸算法的車輛到站時刻預(yù)測模型；Ranhee Jeong[8]采用神經(jīng)網(wǎng)絡(luò)模型對公交車輛的行程時間進行預(yù)測；Cathey[9]等基于GPS系統(tǒng)對公交車輛到站時間進行了研究。以上各種預(yù)測模型有著各自的缺點，例如：聚類回歸分析中隸屬度的確定受人為因素影響較大；灰色理論預(yù)測對原始數(shù)據(jù)的依賴較強；神經(jīng)網(wǎng)絡(luò)模型收斂速度慢等。且這些方法都沒有很好地解決變量之間多重相關(guān)性的問題。

根據(jù)以上情況，提出粒子群與蟻群混合算法優(yōu)化最小二乘支持向量機的公交行程時間預(yù)測模型，仿真公交行程時間，為了辨別該模型的有效性，與其他模型的結(jié)果進行了比對，結(jié)果突出了該模型的優(yōu)點。

1 LS-SVM算法

LS-SVM回歸算法[10]是SVM算法的一種，它利用等式約束，SVM采用二次規(guī)劃方法，LS-SVM則把最小二乘線性系統(tǒng)作為損失函數(shù)，在求解方面，LS-SVM比SVM需要的計算資源較少，也更加簡便、快速，對求解問題的速度和精度都有一定的提升。

其中K（x，xi）=φ（xi）φ（x）為核函數(shù)。

2 粒子群蟻群算法

2.1 蟻群算法

1992年，Marco Dorigo在他的博士論文中首次提出蟻群算法[11]（Ant Colony Optimization，ACO），此算法又稱為螞蟻算法，是一種模擬尋找優(yōu)化路徑的進化算法，該算法性質(zhì)優(yōu)良。

算法開始時，將m只螞蟻分別放在起點處，螞蟻按照不同路徑尋找最優(yōu)參數(shù)，螞蟻完成每次循環(huán)后在路徑上釋放信息素，遍歷完成后，根據(jù)下式對每條路徑上的信息量大小進行調(diào)整：

其中，Q為螞蟻循環(huán)釋放出的信息，Lk為第k只螞蟻本次經(jīng)過路徑的總長度。

2.2 粒子群算法

Kennedy和Eberhari在1995年受生物界鳥群覓食的啟發(fā)提出了粒子群算法[12]（Particle Swarm Optimization，PSO），PSO是尋找最優(yōu)解的一種方法。

粒子群算法的思想是：在初始位置的若干個粒子（或鳥），都有到目前為止自己的個體最優(yōu)解pi,b，整個粒子群有群體的最優(yōu)解gb，所有粒子追隨當(dāng)前的最優(yōu)粒子在解空間中搜索，通過多次迭代找到最優(yōu)解。每個粒子的速度和位置根據(jù)下面式子進行調(diào)整：

其中φ（k）為慣性函數(shù)，α1、α2為加速常數(shù)，γ1i，γ2i為［0，1］區(qū)間內(nèi)均勻分布的隨機數(shù)。

ACO優(yōu)化PSO算法的思想如下：將ACO的重要參數(shù)值賦給PSO中的粒子位置坐標(biāo)，通過粒子位置尋優(yōu)后反饋到ACO中，避免了ACO中參數(shù)選取盲目性的問題。

3 基于蟻群和粒子群（ACO+PSO）優(yōu)化的LS-SVM公交行程時間預(yù)測模型

3.1 蟻群粒子群對LS-SVM的參數(shù)優(yōu)化

利用蟻群粒子群算法優(yōu)化LS-SVM[13]。首先，給LS-SVM一組參數(shù)值，訓(xùn)練LS-SVM模型；其次，選擇使目標(biāo)值最優(yōu)的參數(shù)再進行訓(xùn)練，最終得到滿意的LS-SVM模型。蟻群粒子群算法優(yōu)化LS-SVM的流程如圖1所示。

首先，由蟻群算法中的信息素揮發(fā)度ρ、期望值啟發(fā)式因子β、信息素強度Q表示粒子群算法中粒子的位置坐標(biāo)：xi={Q，β，ρ}，隨機產(chǎn)生粒子的初速度vi={vQ，vβ，vρ}。

圖1 ACO+PSO優(yōu)化LS-SVM的流程圖

粒子位置初始化后，由蟻群算法進行迭代，進而判斷粒子位置的優(yōu)劣，更新粒子的速度和位置：

其中，ω 為慣性權(quán)重；c1，c2為學(xué)習(xí)因子；r1，r2為［0，1］的隨機數(shù)，pbesti與 gbesti為當(dāng)前粒子的個體及全局極值點位置；vi+1為本次迭代后粒子的速度；為粒子在迭代前后所處的位置。

其次，粒子完成一個移步后，再次調(diào)用蟻群算法，如果粒子迭代若干次后不能得到更優(yōu)的解，那么迭代終止，返回全局最優(yōu)解，完成優(yōu)化算法。

最后，將蟻群算法得到的最優(yōu)高斯核參數(shù)σ和正則化參數(shù)C賦值給LS-SVM預(yù)測模型，得出預(yù)測結(jié)果。

3.2 蟻群粒子群（ACO+PSO）優(yōu)化的LS-SVM公交行程時間預(yù)測

為檢驗本模型的準(zhǔn)確性，我們以北京市公交1路為例對模型進行計算。公交1路東起四惠站，西至靛廠新村，共計28個站點，全長27.1km，將全程分為27個子路段。公交1路線如圖2所示。

圖2 北京市公交1路線路圖

本文采集的GPS數(shù)據(jù)涵蓋2015年3月23日至2015年4月10日，每周周一、周二、周五3天，共3周；以及2015年4月13日至2015年4月24日，每周周一、周二、周五3天，共兩周，總共15天的數(shù)據(jù)。將早高峰和上午平峰的數(shù)據(jù)分開，其中早高峰樣本1752個，上午平峰樣本1426個，將處理后的高峰和平峰GPS數(shù)據(jù)中最后一次車的數(shù)據(jù)作為預(yù)測數(shù)據(jù)，其余樣本作為訓(xùn)練數(shù)據(jù)。部分數(shù)據(jù)如表1所示。

表1 本文實驗的部分數(shù)據(jù)

利用Matlab7.0軟件編寫程序，算法的初始參數(shù)確定為：慣性權(quán)重ω=0.5，學(xué)習(xí)因子c1=c2=2，粒子群規(guī)模為200，蟻群為4個，蟻群迭代50次，粒子群迭代2000次程序終止，至迭代結(jié)束時，得到支持向量機的C=6.51，核參數(shù)δ=5.316。

根據(jù)公交行程時間的影響因素，并結(jié)合GPS數(shù)據(jù)，利用LS-SVM、BP網(wǎng)絡(luò)及ACO+PSO的LS-SVM三種模型對公交行程時間進行仿真，得到早高峰和上午平峰各路段行程時間實際值與預(yù)測值對比圖，如圖3和圖4所示。

圖3 早高峰各路段行程時間實際值與預(yù)測值對比圖

圖4 上午平峰各路段行程時間實際值與預(yù)測值對比圖

從圖3和圖4可以看出，三種預(yù)測模型預(yù)測的各路段的行程時間均與實際值變化趨勢相同，但相比單一的LS-SVM模型和BP神經(jīng)網(wǎng)絡(luò)模型，本文所提出的模型的預(yù)測值與實際值更為接近。

為了進一步研究以上幾種模型的精度大小，選擇以下三種誤差指標(biāo)對預(yù)測結(jié)果進行對比評價[14]：

（1）平均絕對誤差（Mean Absolute Error，MAE）：

（2）平均絕對誤差百分比（Mean Absolute Percentage Error，MAPE）：

表2 三種模型的評價指標(biāo)結(jié)果表

從表2可以看出，無論是早高峰還是上午平峰，相比單一的LS-SVM、BP神經(jīng)網(wǎng)絡(luò)模型，文章提出的ACO+PSO優(yōu)化的LS-SVM模型的誤差指標(biāo)較小，具有更好的性能，驗證了模型的有效性。

上午平峰時段三項誤差指標(biāo)值普遍低于早高峰時段，這是因為早高峰時段交通流狀態(tài)更為復(fù)雜，道路上車輛較多，交叉路口人流較大，延誤影響較顯著，導(dǎo)致公交車輛在行程時間的不確定性加強，更加難以預(yù)測。

4 結(jié)論

（3）均方根誤差（Root Mean Square Error，RMSE）：

早高峰和上午平峰預(yù)測值的三種誤差的評價結(jié)果如表2所示。

本文提出了蟻群和粒子群（ACO+PSO）優(yōu)化的LS-SVM的公交行程時間預(yù)測方法。主要結(jié)論為：

（1）將蟻群算法中的ρ、β、Q映射到粒子群算法中，避免了粒子群算法早熟及蟻群算法迭代周期長等問題，保證了全局尋優(yōu)能力。

（2）公交行程時間預(yù)測結(jié)果表明，蟻群粒子群（ACO+PSO）優(yōu)化的LS-SVM公交行程時間預(yù)測模型與LS-SVM和BP神網(wǎng)絡(luò)模型相比，泛化能力更強，預(yù)測精度更高，可以有效實現(xiàn)公交行程時間預(yù)測的目標(biāo)。

［1］周雪梅，楊曉光，王磊.公交車輛行程時間預(yù)測方法研究［J］.交通與計算機，2002，（6）：12-14.

［2］楊兆升，保麗霞，朱國華．基于Fuzzy回歸的快速路行程時間預(yù)測模型研究［J］.公路交通科技，2004，（3）：78-80.

［3］傅惠，胡剛，徐建閩，等.基于神經(jīng)網(wǎng)絡(luò)的城市關(guān)聯(lián)交叉口交通流預(yù)測控制方法［J］.中國公路學(xué)報，2008，（5）：91-95．

［4］于濱，楊忠振，林劍藝.應(yīng)用支持向量機預(yù)測公交車運行時間 ［J］.系統(tǒng)工程理論與實踐，2007，（4）：160-165．

［5］周文霞，徐建閩，劉正東.基于卡爾曼濾波算法的公交車輛行程時間預(yù)測［J］.交通標(biāo)準(zhǔn)化，2007，（Z1）：174-177.

［6］彭新建，翁小雄.基于螢火蟲算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的公交行程時間預(yù)測［J］.廣西師范大學(xué)學(xué)報，2017，（1）：28-36.

［7］ Chien I J，Ding Y，Wei C.Dynamic Bus Arrival Time Prediction with Artificial Neural Networks ［J］.Journal of Transportation Engineering，2002，128（5）：429-438.

［8］ Jeong R，Rilett L R.Bus arrival time prediction using artificial neural network model ［C］//The International IEEE Conference on Intelligent Transportation Systems，2004.Proceedings.IEEE，2004：988-993.

［9］ Cathey F W，Dailey D J.A prescription for transit arrival/departure prediction using automatic vehicle location data［J］.Transportation Research Part C Emerging Technologies，2003，11（3–4）：241-264.

［10］李春祥，丁曉達，葉繼紅.基于混合蟻群和粒子群優(yōu)化LSSVM的脈動風(fēng)速預(yù)測［J］.振動與沖擊，2016，（21）：131-136.

［11］席先杰.蟻群優(yōu)化算法在物流配送車輛路徑問題中的應(yīng)用研究［J］.廊坊師范學(xué)院學(xué)報（自然科學(xué)版），2011，（6）：30-35.

［12］王志剛，譚沈陽.求解0-1背包問題的粒子群優(yōu)化算法［J］.廊坊師范學(xué)院學(xué)報（自然科學(xué)版），2010，（5）：18-19.

［13］付華，于翔，盧萬杰.基于蟻群粒子群混合算法與LS-SVM瓦斯涌出量預(yù)測［J］.傳感技術(shù)學(xué)報，2016，（3）：373-377.

［14］柏叢，彭仲仁.基于動態(tài)模型的公交行程時間預(yù)測［J］.計算機工程與應(yīng)用，2016，（3）：103-107.

Prediction of Bus Travel Time Based on Support Vector Machines Using Ant Colony Optimization and Particle Swarm Optimization

SUN Qun1,2，YUAN Hong-jun2,3
（1.Anhui Vocational College of Electronics&Information Technology，Bengbu 233030，China;2.Anhui University，Hefei 230039，China;3.Anhui University of Finance&Economics，Bengbu 230030，China）

In order to accurately predict the travel time of the bus，a prediction method based on ant colony and particle swarm optimization （PSO）is proposed to optimize the least squares support vector machine （LS-SVM）.Based on the Gaussian kernel parameters and regularization parameters of LS-SVM，the LS-SVM is obtained by searching the LS-SVM，and the bus travel time prediction model of ACO and PSO optimized LS-SVM is established.The model is analyzed according to the historical data compared with LS-SSVM and BP neural network.Experiments show that the ACO+PSO model has high prediction accuracy，robustness and generalization ability.

ant colony algorithm；particle swarm optimization；least squares support vector machines；travel time prediction

TU311

A

1674-3229（2017）04-0024-04

2017-09-10

2012年教育部人文社會科學(xué)研究青年基金項目(12YJC630277)；2017年安徽財經(jīng)大學(xué)重點科研基金資助項目 (ACKY1713ZDB)

孫群（1981-），女，碩士，安徽電子信息職業(yè)技術(shù)學(xué)院講師，研究方向：智能計算與數(shù)據(jù)分析等。