基于ACO-SVM的交通状态分类精度研究

运杰伦，郭元术，林欣欣

(长安大学 信息工程学院，陕西 西安 710000)

0 引 言

随着国家在道路交通科技方面的大力发展，车辆和公路的里程数也不断增加，因此也产生了一系列交通问题，其中最显著的就是交通道路的状态识别分类。交通状态问题的分类的准确识别，可以预防拥堵情况的发生，并选择最优化路径行车，减少了在道路上的停滞时间。蚁群算法不仅有鲁棒性、并行分布式计算等优点，而且还可以进行局部最优解的判断。目前的研究发现，支持向量机虽然进行了一些改进，也实现了一些基本的功能，但仍然存在许多问题。与此同时，大量的研究者也通过对算法融合进行各自优化。文中利用蚁群算法的最终寻优，让支持向量分类精度比传统支持向量机效果更明显。

1 蚁群算法

1.1 蚁群算法基本理论

蚁群算法是蚂蚁根据自己留下的分泌物进行最优判断，分泌物成为了蚂蚁接受信息的来源，在它们活动的过程中，随着活动范围的增加，信息分布也就越来越广，因此在蚂蚁的住所和食物周围的信息含量是最多的。蚂蚁能够通过分辨分泌物含量(信息素)的浓度[1-2]来引导自身的前进方向，选择概率越高的地方肯定是分泌物含量越多的地方，引导蚂蚁发现最优路径，然而时间变化也会让分泌物含量逐渐变淡，影响选择路径的优化。

1.2 蚁群算法基本模型

蚁群算法如下：假设有M个地点数量，G=(N,L)，其中，N为顶点数量，L为顶点之间的距离，它们之间的弧线长度用dij表示，(i,j)∈N，蚂蚁的总数量为s。蚂蚁有记住事物的能力，还具有以下特点：

(1)能够依据信息素含量，用转移概率去选取之后要经过的地点位置；

(2)记录所走过的地点位置，在下一个地点的选择中将不考虑这些地点；

(3)每经过一次迭代，相应的信息素需要释放，且经过的地方信息素也要更新；

(4)两个重要的公式为：

·编号为a的蚂蚁经过接下来要走的位置时，选取位置j的转移概率为：

(1)

其中，τij(t)为两个位置连接边的信息素含量，dij为相邻地点之间的距离，Ma为蚂蚁走过的城市，α和β分别为信息素浓度τij(t)和ηij的相互作用程度。ηij是i地点到j地点的期望程度。

·信息素的更新规则表达式：

(2)

(3)

其中，Lk(t)指的是蚂蚁在经过t时刻之后，迭代一次路过所有地点位置再返回起点的路径长度，Q为常数。

算法流程如图1所示。

2 SVM及核函数

支持向量机(support vector machine，SVM)的概念：一种基于VC维和结构风险最小化准则的机器学习方法。与其他机器学习方法相比，SVM具有结构简单、适应性好、训练速度快等优点[3-4]。

2.1 支持向量机理论

如图2所示，圆圈和黑点分别代表两种不同的数据集合，中间的H把两种样本集合分开，并且使得样本边缘的参考平面的H1和H2的分类间隔最大，所以，最优分类面H就是所需要的[5]。

图1 蚁群算法流程

图2 SVM原理

其中

(4)

2.2 核函数

当向量集的维数太低很难划分的时候，常常会把它们映射到相对应的高维空间，但是又使得计算的复杂度增大，所以在这里引出了核函数[5]。

若函数Z(x,y)满足Merce[6-7]条件，则Z(x,y)=φ(x)·φ(y)，其中φ表示某种关系。相对应的高维空间的分类函数如下:

(5)

其中，φ(x)，φ(y)是比x，y维度更高的向量。

3 ACO-SVM算法

ACO-SVM算法流程如图3所示。

图3 ACO-SVM算法流程

SVM参数优化[8-9]如下：

(1)初始化变量。

首先确定每一个参数的取值范围[Cmin，Cmax]、[Ymin，Ymax]，然后将其离散化，并把它N等分：

(6)

初始给定c和δ(蚂蚁的位置坐标)，令离散化后的参数节点初始信息素为T2×N=U，蚂蚁数目记为M，设置最大迭代次数NCmax，NC代表遍历次数[10-11]。

(2)节点的计算概率。

(7)

释放蚂蚁，每只蚂蚁从某一位置开始，按上式计算概率依次选择两个地点位置参数，以选择的参数训练SVM即可得到一个结果。

(3)设实验算法的目标函数为H(X)，X=X(x1,x2,…,xm)，X表示行数为2列数为m的矩阵。

(4)当所有的蚂蚁都选择好参数后，用各个蚂蚁所选参数对SVM进行训练,最后经过多次迭代记录最优的测试结果，达到所期望的效果。

4 仿真分析

4.1 实验环境与参数设置

仿真软件：MATLAB R2010b，使用JAVA语言。

参数设置：种群数量m=10，挥发因子0<ρ=0.8<1，α=2，β=4，迭代次数NCmax=10，其他参数c∈(0,10),δ∈(0,1)。

4.2 仿真实验

取有效交通流参数数据集2 019组[12](数据是河南省郑州市城市道路网所在交通云平台一周之类的)，选取占有率、车流量、超速车辆占比、低车速占比、车辆波动为特征向量。为确保训练集和测试集能够包含不同等级(交通流量大小)的交通状态，根据交通流量的大小和服务水平分类所产生的服务水平的分级，美国《道路通行能力手册》[13]将服务水平分为A至F六级，根据国内的道路交通实际情况，将服务级别分为4级。本实验中，取级别为5级，可以很好地满足所有的交通状态。

因此，在选取的每个集合中把后30个数据作为实验的测试集，则一共有150个数据测试集，把剩余的1 869个数据作为训练集，实验仿真结果如图4所示。

图4 SVM识别结果

图4为基本SVM的识别结果，可看出在150个测试集中，有13个样本分类错误，对于交通状态分类精度为91.33%，说明用SVM识别交通状态模型具备较好的可行性[14]。

图5 ACO-SVM识别结果

经过50次左右的迭代寻优，得到的结果如图5和图6所示，可以看出ACO-SVM模型[15]在分类的精度上有略微的识别增强，但在寻优方面效果还是比较明显的。由图7可知在14代左右时收敛，找到最优解c=6.884，δ=0.731，将分类精度作为蚁群算法的适应度函数值，最终分类精度比基本SVM模型有所提升并达到94.6%。

图6 ACO寻优适应度变化

图7 ACO最优参数变化

5 结束语

通过仿真分析实验表明，蚁群支持向量机的分类精度明显提高，达到了预期的效果；在后续的算法改进工作中，为了避免蚁群算法陷入局部最优解，还应该提高算法的自适应能力。交通状态分类的精度提高，对于当前的交通问题来说起到了非常重要的作用；同时，伴随着信息科技的快速发展，不仅提供了先进的技术支持，也为车辆行驶提供了一种更好的行车路径，能够有效地缓解交通所带来的压力，从而使得交通信息的融合也越来越完美。