蚁群和粒子群算法优化支持向量机的公交行程时间预测

孙 群，袁宏俊

（1.安徽电子信息职业技术学院，安徽蚌埠 233030；2.安徽大学，安徽合肥 230039；3.安徽财经大学，安徽蚌埠 233030）

蚁群和粒子群算法优化支持向量机的公交行程时间预测

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

（1.安徽电子信息职业技术学院，安徽蚌埠 233030；2.安徽大学，安徽合肥 230039；3.安徽财经大学，安徽蚌埠 233030）

为精确预测公交行程时间，提出了基于蚁群和粒子群（ACO+PSO）优化最小二乘支持向量机（LS-SVM）的预测方法。算法通过对LS-SVM的高斯核参数σ和正则化参数C进行搜索寻优，获得更为精确的LS-SVM，建立了ACO和PSO优化LS-SVM的公交行程时间预测模型，根据历史数据进行实例分析，并与LS-SSVM及BP神经网络进行比较。实验表明，ACO+PSO模型的预测精度高、鲁棒性及泛化能力强。

蚁群算法；粒子群算法；最小二乘支持向量机；行程时间预测

0 引言

随着城市化进程的加快，城市道路交通的拥堵也不断加剧，导致公交到站时间不确定等问题。因此，准确的公交行程时间预测是提高交通资源利用率，缓解交通拥堵的重要手段。因此，研究公交行程时间的预测方法对于公交车辆时间的合理安排与调度、公交资源的合理利用及吸引市民选择公交出行等具有重要的现实意义。

目前，国内外学者已经对公交行程时间的预测模型进行了很多研究：周雪梅[1]等用统计回归方法对公交车辆的到站时间进行了预测；杨兆升[2]等用模糊回归方程研究了公交行程时间；温惠英[3]利用灰色理论对公交车辆的行程时间进行预测；于滨[4]建立支持向量机模型研究了公交车辆的行程时间；周文霞[5]等利用卡尔曼滤波算法来预测公交的行程时间；彭新建，翁小雄[6]利用萤火虫寻优算法结合BP神经网络对公交车辆的行程时间进行了预测；Patnaik和Chien[7]提出基于多变量回归算法的车辆到站时刻预测模型；Ranhee Jeong[8]采用神经网络模型对公交车辆的行程时间进行预测；Cathey[9]等基于GPS系统对公交车辆到站时间进行了研究。以上各种预测模型有着各自的缺点，例如：聚类回归分析中隶属度的确定受人为因素影响较大；灰色理论预测对原始数据的依赖较强；神经网络模型收敛速度慢等。且这些方法都没有很好地解决变量之间多重相关性的问题。

根据以上情况，提出粒子群与蚁群混合算法优化最小二乘支持向量机的公交行程时间预测模型，仿真公交行程时间，为了辨别该模型的有效性，与其他模型的结果进行了比对，结果突出了该模型的优点。

1 LS-SVM算法

LS-SVM回归算法[10]是SVM算法的一种，它利用等式约束，SVM采用二次规划方法，LS-SVM则把最小二乘线性系统作为损失函数，在求解方面，LS-SVM比SVM需要的计算资源较少，也更加简便、快速，对求解问题的速度和精度都有一定的提升。

其中K（x，xi）=φ（xi）φ（x）为核函数。

2 粒子群蚁群算法

2.1 蚁群算法

1992年，Marco Dorigo在他的博士论文中首次提出蚁群算法[11]（Ant Colony Optimization，ACO），此算法又称为蚂蚁算法，是一种模拟寻找优化路径的进化算法，该算法性质优良。

算法开始时，将m只蚂蚁分别放在起点处，蚂蚁按照不同路径寻找最优参数，蚂蚁完成每次循环后在路径上释放信息素，遍历完成后，根据下式对每条路径上的信息量大小进行调整：

其中，Q为蚂蚁循环释放出的信息，Lk为第k只蚂蚁本次经过路径的总长度。

2.2 粒子群算法

Kennedy和Eberhari在1995年受生物界鸟群觅食的启发提出了粒子群算法[12]（Particle Swarm Optimization，PSO），PSO是寻找最优解的一种方法。

粒子群算法的思想是：在初始位置的若干个粒子（或鸟），都有到目前为止自己的个体最优解pi,b，整个粒子群有群体的最优解gb，所有粒子追随当前的最优粒子在解空间中搜索，通过多次迭代找到最优解。每个粒子的速度和位置根据下面式子进行调整：

其中φ（k）为惯性函数，α1、α2为加速常数，γ1i，γ2i为［0，1］区间内均匀分布的随机数。

ACO优化PSO算法的思想如下：将ACO的重要参数值赋给PSO中的粒子位置坐标，通过粒子位置寻优后反馈到ACO中，避免了ACO中参数选取盲目性的问题。

3 基于蚁群和粒子群（ACO+PSO）优化的LS-SVM公交行程时间预测模型

3.1 蚁群粒子群对LS-SVM的参数优化

利用蚁群粒子群算法优化LS-SVM[13]。首先，给LS-SVM一组参数值，训练LS-SVM模型；其次，选择使目标值最优的参数再进行训练，最终得到满意的LS-SVM模型。蚁群粒子群算法优化LS-SVM的流程如图1所示。

首先，由蚁群算法中的信息素挥发度ρ、期望值启发式因子β、信息素强度Q表示粒子群算法中粒子的位置坐标：xi={Q，β，ρ}，随机产生粒子的初速度vi={vQ，vβ，vρ}。

图1 ACO+PSO优化LS-SVM的流程图

粒子位置初始化后，由蚁群算法进行迭代，进而判断粒子位置的优劣，更新粒子的速度和位置：

其中，ω 为惯性权重；c1，c2为学习因子；r1，r2为［0，1］的随机数，pbesti与 gbesti为当前粒子的个体及全局极值点位置；vi+1为本次迭代后粒子的速度；为粒子在迭代前后所处的位置。

其次，粒子完成一个移步后，再次调用蚁群算法，如果粒子迭代若干次后不能得到更优的解，那么迭代终止，返回全局最优解，完成优化算法。

最后，将蚁群算法得到的最优高斯核参数σ和正则化参数C赋值给LS-SVM预测模型，得出预测结果。

3.2 蚁群粒子群（ACO+PSO）优化的LS-SVM公交行程时间预测

为检验本模型的准确性，我们以北京市公交1路为例对模型进行计算。公交1路东起四惠站，西至靛厂新村，共计28个站点，全长27.1km，将全程分为27个子路段。公交1路线如图2所示。

图2 北京市公交1路线路图

本文采集的GPS数据涵盖2015年3月23日至2015年4月10日，每周周一、周二、周五3天，共3周；以及2015年4月13日至2015年4月24日，每周周一、周二、周五3天，共两周，总共15天的数据。将早高峰和上午平峰的数据分开，其中早高峰样本1752个，上午平峰样本1426个，将处理后的高峰和平峰GPS数据中最后一次车的数据作为预测数据，其余样本作为训练数据。部分数据如表1所示。

表1 本文实验的部分数据

利用Matlab7.0软件编写程序，算法的初始参数确定为：惯性权重ω=0.5，学习因子c1=c2=2，粒子群规模为200，蚁群为4个，蚁群迭代50次，粒子群迭代2000次程序终止，至迭代结束时，得到支持向量机的C=6.51，核参数δ=5.316。

根据公交行程时间的影响因素，并结合GPS数据，利用LS-SVM、BP网络及ACO+PSO的LS-SVM三种模型对公交行程时间进行仿真，得到早高峰和上午平峰各路段行程时间实际值与预测值对比图，如图3和图4所示。

图3 早高峰各路段行程时间实际值与预测值对比图

图4 上午平峰各路段行程时间实际值与预测值对比图

从图3和图4可以看出，三种预测模型预测的各路段的行程时间均与实际值变化趋势相同，但相比单一的LS-SVM模型和BP神经网络模型，本文所提出的模型的预测值与实际值更为接近。

为了进一步研究以上几种模型的精度大小，选择以下三种误差指标对预测结果进行对比评价[14]：

（1）平均绝对误差（Mean Absolute Error，MAE）：

（2）平均绝对误差百分比（Mean Absolute Percentage Error，MAPE）：

表2 三种模型的评价指标结果表

从表2可以看出，无论是早高峰还是上午平峰，相比单一的LS-SVM、BP神经网络模型，文章提出的ACO+PSO优化的LS-SVM模型的误差指标较小，具有更好的性能，验证了模型的有效性。

上午平峰时段三项误差指标值普遍低于早高峰时段，这是因为早高峰时段交通流状态更为复杂，道路上车辆较多，交叉路口人流较大，延误影响较显著，导致公交车辆在行程时间的不确定性加强，更加难以预测。

4 结论

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

早高峰和上午平峰预测值的三种误差的评价结果如表2所示。

本文提出了蚁群和粒子群（ACO+PSO）优化的LS-SVM的公交行程时间预测方法。主要结论为：

（1）将蚁群算法中的ρ、β、Q映射到粒子群算法中，避免了粒子群算法早熟及蚁群算法迭代周期长等问题，保证了全局寻优能力。

（2）公交行程时间预测结果表明，蚁群粒子群（ACO+PSO）优化的LS-SVM公交行程时间预测模型与LS-SVM和BP神网络模型相比，泛化能力更强，预测精度更高，可以有效实现公交行程时间预测的目标。

［1］周雪梅，杨晓光，王磊.公交车辆行程时间预测方法研究［J］.交通与计算机，2002，（6）：12-14.

［2］杨兆升，保丽霞，朱国华．基于Fuzzy回归的快速路行程时间预测模型研究［J］.公路交通科技，2004，（3）：78-80.

［3］傅惠，胡刚，徐建闽，等.基于神经网络的城市关联交叉口交通流预测控制方法［J］.中国公路学报，2008，（5）：91-95．

［4］于滨，杨忠振，林剑艺.应用支持向量机预测公交车运行时间 ［J］.系统工程理论与实践，2007，（4）：160-165．

［5］周文霞，徐建闽，刘正东.基于卡尔曼滤波算法的公交车辆行程时间预测［J］.交通标准化，2007，（Z1）：174-177.

［6］彭新建，翁小雄.基于萤火虫算法优化BP神经网络的公交行程时间预测［J］.广西师范大学学报，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］李春祥，丁晓达，叶继红.基于混合蚁群和粒子群优化LSSVM的脉动风速预测［J］.振动与冲击，2016，（21）：131-136.

［11］席先杰.蚁群优化算法在物流配送车辆路径问题中的应用研究［J］.廊坊师范学院学报（自然科学版），2011，（6）：30-35.

［12］王志刚，谭沈阳.求解0-1背包问题的粒子群优化算法［J］.廊坊师范学院学报（自然科学版），2010，（5）：18-19.

［13］付华，于翔，卢万杰.基于蚁群粒子群混合算法与LS-SVM瓦斯涌出量预测［J］.传感技术学报，2016，（3）：373-377.

［14］柏丛，彭仲仁.基于动态模型的公交行程时间预测［J］.计算机工程与应用，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年教育部人文社会科学研究青年基金项目(12YJC630277)；2017年安徽财经大学重点科研基金资助项目 (ACKY1713ZDB)

孙群（1981-），女，硕士，安徽电子信息职业技术学院讲师，研究方向：智能计算与数据分析等。