基于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 結束語

通過仿真分析實驗表明，蟻群支持向量機的分類精度明顯提高，達到了預期的效果；在后續的算法改進工作中，為了避免蟻群算法陷入局部最優解，還應該提高算法的自適應能力。交通狀態分類的精度提高，對于當前的交通問題來說起到了非常重要的作用；同時，伴隨著信息科技的快速發展，不僅提供了先進的技術支持，也為車輛行駛提供了一種更好的行車路徑，能夠有效地緩解交通所帶來的壓力，從而使得交通信息的融合也越來越完美。