基于蟻群聚類的路面識別分析方法

劉慶華，翟劉佳，江燕燕，張利敏

(江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212003)

隨著城市建設(shè)的飛速發(fā)展，作為市政基礎(chǔ)設(shè)施的城市道路來講，其使用性能每時(shí)每刻與城市的社會經(jīng)濟(jì)發(fā)展、人民生活都有著不可分割的依存關(guān)系.對其進(jìn)行有效管理和維護(hù)成為一個(gè)龐大復(fù)雜的系統(tǒng)工程.而對道路的路面狀況正確、及時(shí)作出評價(jià)，對保持交通暢通、確保交通安全、減少交通事故、充分發(fā)揮道路設(shè)施功能和效益等具有十分重要的現(xiàn)實(shí)意義［1］.

公路路面是一個(gè)復(fù)雜的動態(tài)系統(tǒng)，受溫度、水及車輛載荷等因素的影響，路面的狀況不斷發(fā)生變化.文中通過改進(jìn)蟻群優(yōu)化算法，模仿螞蟻尋找食物的方式來構(gòu)造分類規(guī)則［2］，并將蟻群算法應(yīng)用于路面識別分析中，取得了理想的效果.

1 蟻群優(yōu)化

1.1 基本原理

蟻群優(yōu)化(ant colony optimization，ACO)算法［3－4］是由意大利學(xué)者Dorigo M，Colorni A，Manizzo V等在90年代初模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法.科學(xué)家們發(fā)現(xiàn)，螞蟻有能力在沒有任何提示下找到從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇.經(jīng)研究發(fā)現(xiàn)，其根本原因是螞蟻在尋找食物源時(shí)，在其走過的路上釋放一種特殊的分泌物——信息素，后來的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上該物質(zhì)的強(qiáng)度成正比.路徑越短，信息素的濃度越高.后來的螞蟻根據(jù)路徑上的信息素的濃度選擇路徑.信息素濃度越大，該路徑被選擇的概率就越高;被選中的概率越高，該路徑上留下的信息素濃度越大，如此形成了一個(gè)良性的正反饋，如圖1所示.最終蟻群選擇的必定是一條從食物所在地到蟻巢的最優(yōu)路徑，并且在路徑選擇過程中，同路徑上可以被不同的螞蟻同時(shí)選中.應(yīng)用ACO解決復(fù)雜的組合優(yōu)化問題包括螞蟻按照概率選路和信息素更新兩個(gè)步驟.

圖1 蟻群算法路徑選擇的正循環(huán)Fig.1 Path choice cycle chart of ant colony algorithm

t時(shí)刻，位于城市i的螞蟻根據(jù)各條可選路徑上的信息素濃度進(jìn)行選擇，下一步選擇到達(dá)城市j的概率為

式中:τij為邊(i，j)上的信息素為從城市i轉(zhuǎn)移到城市j的啟發(fā)式因子;allowedk為螞蟻k下一步被允許訪問的城市集合.

螞蟻完成一次循環(huán)，各路徑上的信息素要根據(jù)式(2)進(jìn)行更新.

式中:τij為t時(shí)刻i，j間的信息素濃度;ρ為信息素的揮發(fā)程度.

1.2 基本蟻群聚類算法

蟻群聚類算法(ant colony clustering algorithm，ACCA)是基于蟻群優(yōu)化算法衍生出的一類數(shù)據(jù)挖掘算法.基于蟻群聚類算法的路面分析系統(tǒng)，將數(shù)據(jù)實(shí)例視為不同屬性的螞蟻，聚類中心視為螞蟻所要尋找的食物源，數(shù)據(jù)聚類過程即是螞蟻尋找食物源的過程［5］.

1.3 算法分析

設(shè)待聚類的數(shù)據(jù)集

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

則算法基本過程如下:

1)初始化，包括聚類算法參數(shù)初始化和數(shù)據(jù)實(shí)例標(biāo)準(zhǔn)化.標(biāo)準(zhǔn)化的目的是使所有第j個(gè)特征值都變成與平均值的標(biāo)準(zhǔn)偏差，消除由于度量不同對聚類結(jié)果產(chǎn)生的影響［6］.標(biāo)準(zhǔn)化后的x′ij可表示為:

2)根據(jù)實(shí)例，加權(quán)歐式距離［7］為:

各路徑上的信息素為:

式中:r為聚類半徑.

3)Xi歸并到Xj的概率為:

4)判斷pij≥p0是否成立，若成立，Xi歸并到Xj鄰域.

5)該類的聚類中心為:

6)各個(gè)聚類的偏離誤差為:

7)整體的誤差為:

8)判斷程序終止條件，若達(dá)到規(guī)定的最大迭代次數(shù)，則停止，并輸出聚類個(gè)數(shù)和聚類中心，否則轉(zhuǎn)步驟2)繼續(xù)迭代.

2 應(yīng)用實(shí)例

2.1 蟻群聚類的路面識別系統(tǒng)

基于蟻群聚類的路面識別系統(tǒng)結(jié)構(gòu)框圖(圖2)，主要由數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、蟻群聚類3個(gè)模塊組成.

1)數(shù)據(jù)采集模塊.首先加速度傳感器采集系統(tǒng)原始數(shù)據(jù)，因此該模塊是整個(gè)路面識別系統(tǒng)的基礎(chǔ).加速度傳感器采集到的實(shí)時(shí)數(shù)據(jù)通過單片機(jī)進(jìn)行最初的預(yù)處理，再通過藍(lán)牙無線傳輸方式存儲于上位機(jī).每組數(shù)據(jù)均為三維數(shù)組，記錄的分別是X，Y，Z軸3個(gè)方向的力矩.由于課題的需要，只對Z軸振動信號進(jìn)行分析，對于前進(jìn)力與側(cè)向力未進(jìn)行數(shù)據(jù)處理.

圖2 基于蟻群聚類的路面識別系統(tǒng)結(jié)構(gòu)框圖Fig.2 Pavement recognition architecture of ant clustering

2)數(shù)據(jù)預(yù)處理模塊.數(shù)據(jù)預(yù)處理的目的是將采集到的屬性值進(jìn)行分割過濾.在數(shù)據(jù)采集過程中，難免會出現(xiàn)數(shù)據(jù)的串行跳變或系統(tǒng)斷電等內(nèi)外因素的干擾，所以通過數(shù)據(jù)的預(yù)處理將數(shù)據(jù)屬性標(biāo)準(zhǔn)化，格式統(tǒng)一化;然后將合理的數(shù)據(jù)進(jìn)行特征提取;文中主要從采集數(shù)據(jù)中提取有效值、峰值、標(biāo)準(zhǔn)差等3個(gè)時(shí)域特征，作為數(shù)據(jù)屬性進(jìn)行聚類.

3)蟻群聚類模塊.結(jié)合蟻群聚類算法的原型，設(shè)計(jì)了一種檢測路面不平度的蟻群聚類模塊.該模塊包含了蟻群聚類所需要的一些功能及參數(shù)，主要有:各參數(shù)的設(shè)置、目標(biāo)函數(shù)的計(jì)算、聚類中心的計(jì)算、螞蟻解的構(gòu)造等.通過該模塊實(shí)現(xiàn)路面模式的分級.

2.2 算法的實(shí)現(xiàn)

將原始信號直接輸入蟻群聚類系統(tǒng)，會因輸入數(shù)據(jù)維數(shù)過高增加聚類系統(tǒng)的負(fù)擔(dān)，并且可能引入干擾信息降低整體性能，因此，對原始數(shù)據(jù)進(jìn)行特征提取并進(jìn)行特征選擇是路面識別的重要環(huán)節(jié).特征選擇的任務(wù)是從構(gòu)造的初始特征集中選擇一個(gè)優(yōu)化子集，提高蟻群聚類系統(tǒng)路面識別的正確率，減少特征提取過程中的運(yùn)算量.通過各種數(shù)據(jù)分析技術(shù)可以從采集信號中提取出大量的特征，不同的特征選擇對聚類結(jié)果影響很大［8］.

汽車內(nèi)部結(jié)構(gòu)的復(fù)雜性，導(dǎo)致了汽車行駛過程中安裝在車身的傳感器振動響應(yīng)的復(fù)雜性，其特征提取涉及消除波動、降低噪聲等方面.文中根據(jù)汽車振動信號特點(diǎn)，通過消除波動、降低噪點(diǎn)，求取所構(gòu)造特征集的特征值，得到包含各種路面狀態(tài)完備信息的特征向量.

圖3 蟻群聚類算法流程Fig.3 Flow chart of ant colony algorithm

蟻群聚類算法具有離散性和并行性特點(diǎn)，它對于數(shù)據(jù)的特征聚類非常適用.然而當(dāng)路面數(shù)據(jù)量較大時(shí)，蟻群聚類在系統(tǒng)循環(huán)過程中對數(shù)據(jù)的搜索時(shí)間較長，計(jì)算量也隨之加大.為了克服這一問題，將初始聚類中心作為螞蟻的初始食物源加以引導(dǎo)，減少螞蟻行走的盲目性，以達(dá)到降低計(jì)算量、加快聚類的目的.蟻群聚類算法實(shí)現(xiàn)的基本流程如圖3.

2.3 實(shí)驗(yàn)及結(jié)果分析

文中使用蟻群聚類算法對真實(shí)采集的各種路面數(shù)據(jù)進(jìn)行聚類分析，達(dá)到識別路面狀態(tài)的目的.使用項(xiàng)目組自主開發(fā)的道路載荷譜采集系統(tǒng)［9］采集數(shù)據(jù)，利用某型加速度傳感器采集不同路面狀態(tài)下的振動數(shù)據(jù).車載人數(shù)為4人，車速保持在40km/h，采樣頻率為500 Hz.采集數(shù)據(jù)經(jīng)預(yù)處理后提取平均值、峰值、均方差等3個(gè)時(shí)域特征作為數(shù)據(jù)屬性進(jìn)行分類.每種路面狀態(tài)類型有100個(gè)數(shù)據(jù)樣本，其中50個(gè)作為訓(xùn)練樣本，用于分類器，另外50個(gè)用于測試分類器.

用蟻群算法進(jìn)行路面識別判斷的主要步驟和過程如下:

1)設(shè)置螞蟻個(gè)數(shù)R=100，將初始解cid設(shè)置為空集，設(shè)置循環(huán)次數(shù)NCmax=10，閾值q=0.9，局部尋優(yōu)閾值pls=0.1，信息素的蒸發(fā)率rho=0.1;

2)隨機(jī)構(gòu)造若干初始聚類中心，設(shè)置聚類中心個(gè)數(shù)k=4，并計(jì)算100只螞蟻產(chǎn)生的聚類評價(jià)函數(shù)J，得到Jmax=3.92;

3)根據(jù)J值選取較優(yōu)的10個(gè)解，進(jìn)行局部搜索，以獲得更優(yōu)的解;

4)根據(jù)更優(yōu)的解更新信息素，進(jìn)入下一輪循環(huán)，直到滿足終止條件，終止條件為達(dá)到一定的聚類效果;

5)根據(jù)信息素濃度矩陣進(jìn)行分類，計(jì)算平均聚類中心，建立分類器.

將3種路面狀態(tài)信號輸入基于蟻群聚類算法的分類器，迭代完成后的識別結(jié)果如表1，迭代完成后各組信息素矩陣中信息素?cái)?shù)值大小代表機(jī)器螞蟻將信號歸為該類路面的概率大小，即信號屬于信息素?cái)?shù)值最大的一類.其他3種狀態(tài)信號的識別效果相同，但每次識別中訓(xùn)練樣本的信息素矩陣數(shù)值可能不同，此處不逐一列舉.實(shí)驗(yàn)共選擇每類路面300組樣本數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，此處選擇5項(xiàng)指標(biāo)，識別結(jié)果如表2.

為了再次驗(yàn)證實(shí)驗(yàn)結(jié)果的準(zhǔn)確有效性，選擇了一組典型的數(shù)據(jù)集來進(jìn)行分析驗(yàn)證.此數(shù)據(jù)集代表的路面由平整水泥路面、兩個(gè)減速帶以及減速帶中間為較顛簸的瓷磚路面組成.對數(shù)據(jù)進(jìn)行分割，分別選出100個(gè)連續(xù)的數(shù)據(jù)送入蟻群聚類分類器，得到各路段的分類結(jié)果(表3).實(shí)驗(yàn)結(jié)果表明，蟻群聚類用于路面識別效果顯著.

表1 3種路面測試樣本的信息素濃度表Table 1 Pheromone concentration meter of three pavement samples

表2 3種路面測試樣本的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of three pavement test sample

表3 3種路面不平整度分類的正確率Table 3 Classification accuracy of three kinds of pavements

3 結(jié)論

文中將蟻群優(yōu)化聚類應(yīng)用到路面識別系統(tǒng).通過實(shí)驗(yàn)分析證實(shí)了基于蟻群優(yōu)化聚類分析路面狀況的可靠性.綜合實(shí)驗(yàn)結(jié)果，可以得出如下結(jié)論:

1)通過多次實(shí)驗(yàn)，蟻群聚類路面識別系統(tǒng)識別水泥路面、瓷磚路面與減速帶路面的準(zhǔn)確率分別為95.3%，93.6%，93.0%，充分證實(shí)了此系統(tǒng)的可靠性.

2)由于蟻群聚類算法是多次迭代的過程，如果程序終止條件設(shè)置不當(dāng)，會導(dǎo)致全局收斂速度很慢且所得解的質(zhì)量較差.本系統(tǒng)摒棄常見的達(dá)到最大迭代次數(shù)的終止條件，而在達(dá)到一定聚類效果時(shí)程序終止，效果明顯.

3)路面系統(tǒng)是一個(gè)復(fù)雜的系統(tǒng)，一段路面可能是各種路面的集合.本文算法對于混合路面的識別率較高.為了避免單一路面狀態(tài)，算法中加入了聚類中心判斷條件，優(yōu)化了聚類算法.

4)蟻群聚類算法參數(shù)選取復(fù)雜，對于參數(shù)的合理設(shè)置至關(guān)重要.蟻群聚類是啟發(fā)式全局收斂算法，文中采用先局部尋優(yōu)再全局收斂的方法進(jìn)行識別，因而局部尋優(yōu)閾值與臨時(shí)聚類度量的設(shè)置對于結(jié)果影響較大.算法參數(shù)的進(jìn)一步合理化以及與其他算法融合改進(jìn)，解決算法自適應(yīng)差等缺點(diǎn)將是下一步要解決的問題.

References)

［1］ 彭富強(qiáng).公路養(yǎng)護(hù)技術(shù)與管理［M］.北京:人民交通出版社，2006.

［2］ 王運(yùn)林，王曉峰.一種基于變異蟻群算法的分類規(guī)則挖掘算法［J］.電腦知識與技術(shù)，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］ 周勇，陳洪亮.蟻群算法的研究現(xiàn)狀及其展望［J］.微型電腦應(yīng)用，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］.計(jì)算機(jī)工程與設(shè)計(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］ 印欣運(yùn)，何永勇，彭志科，等.小波熵及其在狀態(tài)趨勢分析中的應(yīng)用［J］.振動工程學(xué)報(bào)，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］ 劉慶華，張為公.基于車輪力傳感器的道路載荷譜采集系統(tǒng)設(shè)計(jì)［J］.江蘇大學(xué)學(xué)報(bào):自然科學(xué)版，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)