基于蚁群聚类的路面识别分析方法

刘庆华，翟刘佳，江燕燕，张利敏

(江苏科技大学计算机科学与工程学院，江苏镇江212003)

随着城市建设的飞速发展，作为市政基础设施的城市道路来讲，其使用性能每时每刻与城市的社会经济发展、人民生活都有着不可分割的依存关系.对其进行有效管理和维护成为一个庞大复杂的系统工程.而对道路的路面状况正确、及时作出评价，对保持交通畅通、确保交通安全、减少交通事故、充分发挥道路设施功能和效益等具有十分重要的现实意义［1］.

公路路面是一个复杂的动态系统，受温度、水及车辆载荷等因素的影响，路面的状况不断发生变化.文中通过改进蚁群优化算法，模仿蚂蚁寻找食物的方式来构造分类规则［2］，并将蚁群算法应用于路面识别分析中，取得了理想的效果.

1 蚁群优化

1.1 基本原理

蚁群优化(ant colony optimization，ACO)算法［3－4］是由意大利学者Dorigo M，Colorni A，Manizzo V等在90年代初模拟蚂蚁觅食的原理，设计出的一种群集智能算法.科学家们发现，蚂蚁有能力在没有任何提示下找到从巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择.经研究发现，其根本原因是蚂蚁在寻找食物源时，在其走过的路上释放一种特殊的分泌物——信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.路径越短，信息素的浓度越高.后来的蚂蚁根据路径上的信息素的浓度选择路径.信息素浓度越大，该路径被选择的概率就越高;被选中的概率越高，该路径上留下的信息素浓度越大，如此形成了一个良性的正反馈，如图1所示.最终蚁群选择的必定是一条从食物所在地到蚁巢的最优路径，并且在路径选择过程中，同路径上可以被不同的蚂蚁同时选中.应用ACO解决复杂的组合优化问题包括蚂蚁按照概率选路和信息素更新两个步骤.

图1 蚁群算法路径选择的正循环Fig.1 Path choice cycle chart of ant colony algorithm

t时刻，位于城市i的蚂蚁根据各条可选路径上的信息素浓度进行选择，下一步选择到达城市j的概率为

式中:τij为边(i，j)上的信息素为从城市i转移到城市j的启发式因子;allowedk为蚂蚁k下一步被允许访问的城市集合.

蚂蚁完成一次循环，各路径上的信息素要根据式(2)进行更新.

式中:τij为t时刻i，j间的信息素浓度;ρ为信息素的挥发程度.

1.2 基本蚁群聚类算法

蚁群聚类算法(ant colony clustering algorithm，ACCA)是基于蚁群优化算法衍生出的一类数据挖掘算法.基于蚁群聚类算法的路面分析系统，将数据实例视为不同属性的蚂蚁，聚类中心视为蚂蚁所要寻找的食物源，数据聚类过程即是蚂蚁寻找食物源的过程［5］.

1.3 算法分析

设待聚类的数据集

X={Xi=(xi1，xi2，…，xim)，i=1，2，…，n}，

则算法基本过程如下:

1)初始化，包括聚类算法参数初始化和数据实例标准化.标准化的目的是使所有第j个特征值都变成与平均值的标准偏差，消除由于度量不同对聚类结果产生的影响［6］.标准化后的x′ij可表示为:

2)根据实例，加权欧式距离［7］为:

各路径上的信息素为:

式中:r为聚类半径.

3)Xi归并到Xj的概率为:

4)判断pij≥p0是否成立，若成立，Xi归并到Xj邻域.

5)该类的聚类中心为:

6)各个聚类的偏离误差为:

7)整体的误差为:

8)判断程序终止条件，若达到规定的最大迭代次数，则停止，并输出聚类个数和聚类中心，否则转步骤2)继续迭代.

2 应用实例

2.1 蚁群聚类的路面识别系统

基于蚁群聚类的路面识别系统结构框图(图2)，主要由数据采集、数据预处理、蚁群聚类3个模块组成.

1)数据采集模块.首先加速度传感器采集系统原始数据，因此该模块是整个路面识别系统的基础.加速度传感器采集到的实时数据通过单片机进行最初的预处理，再通过蓝牙无线传输方式存储于上位机.每组数据均为三维数组，记录的分别是X，Y，Z轴3个方向的力矩.由于课题的需要，只对Z轴振动信号进行分析，对于前进力与侧向力未进行数据处理.

图2 基于蚁群聚类的路面识别系统结构框图Fig.2 Pavement recognition architecture of ant clustering

2)数据预处理模块.数据预处理的目的是将采集到的属性值进行分割过滤.在数据采集过程中，难免会出现数据的串行跳变或系统断电等内外因素的干扰，所以通过数据的预处理将数据属性标准化，格式统一化;然后将合理的数据进行特征提取;文中主要从采集数据中提取有效值、峰值、标准差等3个时域特征，作为数据属性进行聚类.

3)蚁群聚类模块.结合蚁群聚类算法的原型，设计了一种检测路面不平度的蚁群聚类模块.该模块包含了蚁群聚类所需要的一些功能及参数，主要有:各参数的设置、目标函数的计算、聚类中心的计算、蚂蚁解的构造等.通过该模块实现路面模式的分级.

2.2 算法的实现

将原始信号直接输入蚁群聚类系统，会因输入数据维数过高增加聚类系统的负担，并且可能引入干扰信息降低整体性能，因此，对原始数据进行特征提取并进行特征选择是路面识别的重要环节.特征选择的任务是从构造的初始特征集中选择一个优化子集，提高蚁群聚类系统路面识别的正确率，减少特征提取过程中的运算量.通过各种数据分析技术可以从采集信号中提取出大量的特征，不同的特征选择对聚类结果影响很大［8］.

汽车内部结构的复杂性，导致了汽车行驶过程中安装在车身的传感器振动响应的复杂性，其特征提取涉及消除波动、降低噪声等方面.文中根据汽车振动信号特点，通过消除波动、降低噪点，求取所构造特征集的特征值，得到包含各种路面状态完备信息的特征向量.

图3 蚁群聚类算法流程Fig.3 Flow chart of ant colony algorithm

蚁群聚类算法具有离散性和并行性特点，它对于数据的特征聚类非常适用.然而当路面数据量较大时，蚁群聚类在系统循环过程中对数据的搜索时间较长，计算量也随之加大.为了克服这一问题，将初始聚类中心作为蚂蚁的初始食物源加以引导，减少蚂蚁行走的盲目性，以达到降低计算量、加快聚类的目的.蚁群聚类算法实现的基本流程如图3.

2.3 实验及结果分析

文中使用蚁群聚类算法对真实采集的各种路面数据进行聚类分析，达到识别路面状态的目的.使用项目组自主开发的道路载荷谱采集系统［9］采集数据，利用某型加速度传感器采集不同路面状态下的振动数据.车载人数为4人，车速保持在40km/h，采样频率为500 Hz.采集数据经预处理后提取平均值、峰值、均方差等3个时域特征作为数据属性进行分类.每种路面状态类型有100个数据样本，其中50个作为训练样本，用于分类器，另外50个用于测试分类器.

用蚁群算法进行路面识别判断的主要步骤和过程如下:

1)设置蚂蚁个数R=100，将初始解cid设置为空集，设置循环次数NCmax=10，阈值q=0.9，局部寻优阈值pls=0.1，信息素的蒸发率rho=0.1;

2)随机构造若干初始聚类中心，设置聚类中心个数k=4，并计算100只蚂蚁产生的聚类评价函数J，得到Jmax=3.92;

3)根据J值选取较优的10个解，进行局部搜索，以获得更优的解;

4)根据更优的解更新信息素，进入下一轮循环，直到满足终止条件，终止条件为达到一定的聚类效果;

5)根据信息素浓度矩阵进行分类，计算平均聚类中心，建立分类器.

将3种路面状态信号输入基于蚁群聚类算法的分类器，迭代完成后的识别结果如表1，迭代完成后各组信息素矩阵中信息素数值大小代表机器蚂蚁将信号归为该类路面的概率大小，即信号属于信息素数值最大的一类.其他3种状态信号的识别效果相同，但每次识别中训练样本的信息素矩阵数值可能不同，此处不逐一列举.实验共选择每类路面300组样本数据进行实验，此处选择5项指标，识别结果如表2.

为了再次验证实验结果的准确有效性，选择了一组典型的数据集来进行分析验证.此数据集代表的路面由平整水泥路面、两个减速带以及减速带中间为较颠簸的瓷砖路面组成.对数据进行分割，分别选出100个连续的数据送入蚁群聚类分类器，得到各路段的分类结果(表3).实验结果表明，蚁群聚类用于路面识别效果显著.

表1 3种路面测试样本的信息素浓度表Table 1 Pheromone concentration meter of three pavement samples

表2 3种路面测试样本的实验结果Table 2 Experimental results of three pavement test sample

表3 3种路面不平整度分类的正确率Table 3 Classification accuracy of three kinds of pavements

3 结论

文中将蚁群优化聚类应用到路面识别系统.通过实验分析证实了基于蚁群优化聚类分析路面状况的可靠性.综合实验结果，可以得出如下结论:

1)通过多次实验，蚁群聚类路面识别系统识别水泥路面、瓷砖路面与减速带路面的准确率分别为95.3%，93.6%，93.0%，充分证实了此系统的可靠性.

2)由于蚁群聚类算法是多次迭代的过程，如果程序终止条件设置不当，会导致全局收敛速度很慢且所得解的质量较差.本系统摒弃常见的达到最大迭代次数的终止条件，而在达到一定聚类效果时程序终止，效果明显.

3)路面系统是一个复杂的系统，一段路面可能是各种路面的集合.本文算法对于混合路面的识别率较高.为了避免单一路面状态，算法中加入了聚类中心判断条件，优化了聚类算法.

4)蚁群聚类算法参数选取复杂，对于参数的合理设置至关重要.蚁群聚类是启发式全局收敛算法，文中采用先局部寻优再全局收敛的方法进行识别，因而局部寻优阈值与临时聚类度量的设置对于结果影响较大.算法参数的进一步合理化以及与其他算法融合改进，解决算法自适应差等缺点将是下一步要解决的问题.

References)

［1］ 彭富强.公路养护技术与管理［M］.北京:人民交通出版社，2006.

［2］ 王运林，王晓峰.一种基于变异蚁群算法的分类规则挖掘算法［J］.电脑知识与技术，2009，5(10):2541－2543.

［3］ Dortgo M，Maniezzo V，Colorni A.Ant system:optimization by a colony cooperating agents［C］∥IEEE Trans-actions on Systems，Man，and Cybernetics.USA:IEEE，1996，26(1):29－41.

［4］ 周勇，陈洪亮.蚁群算法的研究现状及其展望［J］.微型电脑应用，2002，18(2):5 －7.

［5］ Crampton J.Specifying and enforcing constraints in rolebased access control［C］∥Proceedings of the8th ACM Symposium on Access Control Models and Technologies.［s.l.］:ACM Press，2003:43 －50.

［6］ Hoshyar R，Jamali S H，Locus C.Ant colony algorithm for finding good interleaving pattern in turbo codes［C］∥IEE Proceedings in Communications.USA:IET，2000，147(5):257－262.

［7］ 郝建东，张伟伟.基于核的图像欧氏距离人脸识别［J］.计算机工程与设计，2011，32(11):3844－3847.Hao Jiandong，Zhang Weiwei.Image euclidean distance based on kernel for face recognition［J］.Computer Engneering and Design，2011，32(11):3844 －3847.(in Chinese)

［8］ 印欣运，何永勇，彭志科，等.小波熵及其在状态趋势分析中的应用［J］.振动工程学报，2004，17(2):165－169.Yin Xinyun，He Yongyong，Peng Zhike，et al.Study on wavelet entropy and its applications in trend analysis［J］.Journal of Vibration Engineering，2004，17(2):165－169.(in Chinese)

［9］ 刘庆华，张为公.基于车轮力传感器的道路载荷谱采集系统设计［J］.江苏大学学报:自然科学版，2011，32(4):390－393.Liu Qinghua，Zhang Weigong.Design of acquisition system for road loading spectra data based on wheel force transducer［J］.Journal of Jiangsu University:Natural Science Edition，2011，32(4):390－393.(in Chinese)