遺傳算法優(yōu)化支持向量機的城市交通狀態(tài)識別

李巧茹，郝恩強，陳 亮，范忠國，楊文偉

(1.河北工業(yè)大學(xué) 土木與交通學(xué)院，天津 300401；2.河北工業(yè)大學(xué) 智慧基礎(chǔ)設(shè)施研究院，天津 300401)

0 引 言

城市交通狀態(tài)識別不僅是現(xiàn)代智能交通系統(tǒng)(intelligent transport system, ITS)的重要內(nèi)容之一，同時也是城市交通規(guī)劃、設(shè)計和交通組織的重要依據(jù)。

交通狀態(tài)識別具有主觀模糊性，因此選取合理高效的算法判斷交通狀態(tài)是實現(xiàn)交通識別的關(guān)鍵。現(xiàn)有算法主要有：數(shù)理統(tǒng)計算法、聚類分析算法、模式識別算法。針對數(shù)理統(tǒng)計算法，A.R.COOK等[1]通過比較交通參數(shù)的實際觀測值和雙指數(shù)平滑法(DES)獲得的預(yù)測值判斷交通狀態(tài)；B.N.PERSAUD等[2]提出了基于突變理論的McMaster算法，實現(xiàn)對交通擁堵類別的準(zhǔn)確分類；M.LEVIN等[3]通過貝葉斯算法計算占有率變化的條件概率，實現(xiàn)交通狀態(tài)的自動檢測。針對聚類分析算法，任其亮等[4]通過建立交通參數(shù)之間的模糊相似性與樣本之間歐式距離的映射關(guān)系，構(gòu)建了基于遺傳動態(tài)模糊聚類的交通狀態(tài)判定方法；張亮亮等[5]考慮交通流參數(shù)在交通狀態(tài)劃分過程中作用的不同，提出了一種基于參數(shù)權(quán)重模糊聚類的交通狀態(tài)識別方法；黃艷國等[6]提出了一種基于模糊C均值聚類的城市道路交通狀態(tài)識別方法。針對模式識別算法，最具代表的算法為神經(jīng)網(wǎng)絡(luò)(neural network，NNet)算法和支持向量機算法，巫威眺等[7]提出了一種基于BP神經(jīng)網(wǎng)絡(luò)的交通狀態(tài)判別算法，該算法在實測數(shù)據(jù)驗證下具有較高的精確度和較好的收斂性；C.CORTES等[8]首次提出支持向量機模型，其在非線性和高維模式識別中也表現(xiàn)出許多優(yōu)勢；于榮等[9]利用支持向量機對道路交通狀態(tài)進行分類；廖瑞輝等[10]針對擁擠預(yù)警信息的隨機性和模糊性特點，利用支持向量機對交通狀態(tài)進行判別，在預(yù)警系統(tǒng)取得成功。

綜合分析現(xiàn)階段國內(nèi)外交通狀態(tài)識別研究現(xiàn)狀，數(shù)理統(tǒng)計算法、聚類分析算法以及模式識別算法已成為交通狀態(tài)識別的重要手段。數(shù)理統(tǒng)計算法使用簡便，但存在交通狀態(tài)識別誤報率高，實用性不強等缺點。聚類分析算法適用于交通狀態(tài)識別的模糊性特征，但易于陷入局部最優(yōu)以及對初始參數(shù)較為敏感，處理海量數(shù)據(jù)時存在一定弊端。神經(jīng)網(wǎng)絡(luò)模型簡單，在處理并行數(shù)據(jù)方面具有天然優(yōu)勢，具備強大的非線性映射及反饋學(xué)習(xí)能力，但其易產(chǎn)生過擬合現(xiàn)象，在實際應(yīng)用中效果并不理想。支持向量機具有嚴(yán)格的理論基礎(chǔ)和數(shù)學(xué)基礎(chǔ)，可避免局部最小問題，克服了神經(jīng)網(wǎng)絡(luò)算法過擬合的缺陷，且小樣本學(xué)習(xí)具有較強的泛化能力。然而，支持向量機的分類性能對參數(shù)選擇比較敏感，實際應(yīng)用中存在依靠經(jīng)驗或試算方法確定參數(shù)的局限性，這在一定程度上限制了模型的泛化能力。吐松江·卡日等[11]提出了一種基于支持向量機和遺傳算法的電力變壓器故障診斷方法，該方法能準(zhǔn)確、有效診斷變壓器故障。

綜上所述，本研究基于聚類分析算法，獲取先驗分類數(shù)據(jù)，并嘗試采用遺傳算法優(yōu)化支持向量機參數(shù)模型，確定SVM最優(yōu)參數(shù)組合，建立基于GA-SVM的城市交通狀態(tài)識別模型，并在MATLAB平臺下進行驗證分析。

1 支持向量機

1.1 支持向量機分類理論

支持向量機是一種基于VC維理論和結(jié)構(gòu)風(fēng)險最小原理的模式識別算法，可根據(jù)有限樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折中，進而實現(xiàn)模型推廣能力的最優(yōu)化。支持向量機在線性可分情況下，最優(yōu)分類超平面定義的分類決策函數(shù)為：

f(x)=sgn[(w·x)+b]

(1)

(2)

(3)

(4)

(5)

(6)

已有成果表明，目前應(yīng)用較多的支持向量機核函數(shù)包括多項式核函數(shù)、徑向基(RBF)核函數(shù)和Sigmod核函數(shù)3種，且在城市交通狀態(tài)識別方面均有較好的應(yīng)用效果。其中，徑向基(RBF)核函數(shù)不僅能實現(xiàn)非線性映射，且參數(shù)較少，易于優(yōu)化。因此選取徑向基(RBF)核函數(shù)進行參數(shù)尋優(yōu)。

1.2 支持向量機參數(shù)對其性能的影響

在支持向量機分類方法中，關(guān)鍵參數(shù)主要為懲罰系數(shù)C和核函數(shù)參數(shù)σ，其選擇效果直接影響支持向量機的性能。

1)懲罰系數(shù)C影響模型的復(fù)雜度和訓(xùn)練誤差。當(dāng)C取值偏小時，樣本數(shù)據(jù)中超出不敏感帶的樣本懲罰也偏小，同時訓(xùn)練精確度降低，系統(tǒng)推廣能力變差，出現(xiàn)“欠學(xué)習(xí)”現(xiàn)象；當(dāng)C取值偏大時，則易出現(xiàn)“過學(xué)習(xí)”現(xiàn)象。

2)核函數(shù)參數(shù)σ主要反映訓(xùn)練樣本數(shù)據(jù)的范圍特性，直接影響支持向量機模型的學(xué)習(xí)能力。當(dāng)σ取值偏小時易出現(xiàn)“欠學(xué)習(xí)”現(xiàn)象，當(dāng)σ取值偏大時易出現(xiàn)“過學(xué)習(xí)”現(xiàn)象。

由此可見，合理確定上述參數(shù)值能夠有效降低支持向量機的訓(xùn)練誤差，提高其學(xué)習(xí)能力。

2 GA-SVM交通狀態(tài)識別模型

城市交通狀態(tài)識別具有高度復(fù)雜性和主觀模糊性等特點，雖然SVM模型在城市交通狀態(tài)識別方面具有較好的應(yīng)用效果，但在參數(shù)選擇上依然存在依靠經(jīng)驗或者反復(fù)試驗確定參數(shù)的局限性，影響SVM的推廣能力。針對SVM模型中存在的問題，建立基于遺傳算法優(yōu)化支持向量機參數(shù)的城市交通狀態(tài)識別模型。該模型分為3個部分，即城市道路交通狀態(tài)分類理論和方法、遺傳算法優(yōu)化SVM參數(shù)、城市交通狀態(tài)識別的GA-SVM模型。算法流程圖如圖1。

2.1 城市道路交通狀態(tài)分類理論和方法

描述道路交通流整體特性主要有車流量、平均速度、占有率等參數(shù)指標(biāo)。不同時段，城市道路交通流在這些參數(shù)下表現(xiàn)出不同的交通特性，據(jù)此建立三維指標(biāo)評價體系，指標(biāo)定義如下[12]：

1)車流量(pcu/h)：單車道2 min內(nèi)各車型車輛數(shù)目之和，計算公式為：

(7)

式中：ni1為第1 min通過的第i類車的車輛數(shù)；ni2為第2 min通過的第i類車的車輛數(shù)；wi為第i類車輛的折算系數(shù)。

2)平均速度(mile/h)：單車道2 min內(nèi)所有機動車的平均速度，計算公式為：

(8)

式中：v1為第1 min的平均速度；v2為第2 min的平均速度；f1為第1 min的流量；f2為第2 min的流量。

3)占有率(%)：單車道2 min內(nèi)車輛在環(huán)形線圈檢測器上的時間比例，計算公式為：

(9)

式中：ft為t時間段內(nèi)的流量；lt為t時間段內(nèi)所有機動車輛的車身長度；vt為t時間段內(nèi)的平均速度；t為時間間隔，此處定義為2 min。

根據(jù)上述三維指標(biāo)，對城市道路交通狀態(tài)數(shù)據(jù)進行聚類分析，得到聚類中心矩陣為：

(10)

該矩陣第1列v1，v2，v4，v4分別代表順暢流、平穩(wěn)流、擁擠流、堵塞流的聚類中心；第2列代表車流量；第3列代表速度；第4列代表占有率。

2.2 遺傳算法優(yōu)化SVM參數(shù)

遺傳算法種群規(guī)模設(shè)定為20，進化代數(shù)設(shè)定為200。保留精英遺傳算法優(yōu)化參數(shù)執(zhí)行過程如下：

1)種群初始化。參數(shù)C和σ分別以n1和n2位二進制進行編碼，則每組參數(shù)為一個基因長度n1+n2的二進制代碼，如圖2。

2)確定適應(yīng)度函數(shù)。根據(jù)種群中個體得到SVM模型的初始參數(shù)值，用樣本數(shù)據(jù)訓(xùn)練SVM模型，然后依據(jù)訓(xùn)練精確度確定個體適應(yīng)度值，如式(11)～式(12)：

f=Ac

(11)

(12)

式中：f為適應(yīng)度函數(shù)；Ac為預(yù)測精確度；N為訓(xùn)練總樣本；Nf為錯誤分類的樣本。

3)選擇操作。采用遺傳算法選擇操作中的輪盤賭法。個體被選中的概率與其適應(yīng)度值的大小成正比，這樣就增加了個體的多樣性，便于執(zhí)行交叉操作和變異操作，如式(13)：

(13)

式中：fi為個體i的適應(yīng)度值。

4)交叉操作。按照一定交叉概率交換配對個體基因，產(chǎn)生新的個體。第1代交叉后自適應(yīng)概率如式(14)：

(14)

式中：G為遺傳代數(shù)；Gmax為最大遺代數(shù)；Pc(1)為第1代交叉概率，此處定義為0.7；Pc(G)為第G代的交叉概率。

5)變異操作。按照一定的變異概率改變選中個體染色體的等位基因，增強種群的多樣性。第1代變異后自適應(yīng)概率如式(15)：

(15)

式中：Pm(1)為第1代變異概率，此處定義為0.01；Pm(G)為第G代的變異概率。

2.3 GA-SVM模型

將上述遺傳算法進化過程中得到的最優(yōu)個體分解為參數(shù)組合C*和σ*，代入SVM模型，得到城市交通狀態(tài)識別的GA-SVM模型。在MATLAB平臺下對GA-SVM模型性能進行測試分析。

3 MATLAB實驗分析

3.1 數(shù)據(jù)采集與處理

岳麓大道為長沙市四橫六縱的重要一環(huán)，承載著連接?xùn)|西城區(qū)的重任。選取長沙市岳麓大道的實驗路段西起澗塘立交橋，東至銀盆嶺大橋，道路線型大致呈直線線形，車道數(shù)為雙向八車道，易于交通數(shù)據(jù)的采集。在車輛出行高峰期和低谷期，呈現(xiàn)多種交通狀態(tài)。因此采集其周一至周五6:00—19:00的流量、速度和占有率數(shù)據(jù)，將城市道路交通狀態(tài)設(shè)定為順暢流、平穩(wěn)流、擁擠流和堵塞流4種類別，進行聚類分析。每一種交通狀態(tài)選用100個樣本，共400組觀測數(shù)據(jù)。取每種狀態(tài)80個樣本作為訓(xùn)練數(shù)據(jù)，20個樣本作為測試數(shù)據(jù)，結(jié)果如圖3、圖4。其中，圖3為交通數(shù)據(jù)的box可視化圖，記錄了樣本數(shù)據(jù)分布情況，交通流參數(shù)屬性正常，不存在異常點；圖4為交通樣本數(shù)據(jù)三維可視化圖，在三維空間內(nèi)呈現(xiàn)出4種交通狀態(tài)，數(shù)據(jù)聚類效果明顯。

3.2 仿真分析

在MATLAB平臺下，利用LIBSVM工具箱對樣本數(shù)據(jù)進行歸一化處理，將數(shù)據(jù)歸一化到[0,1]范圍內(nèi)。其中，圖5為遺傳算法迭代尋優(yōu)過程，設(shè)定遺傳算法種群規(guī)模為20，迭代次數(shù)為200。迭代尋優(yōu)前期，適應(yīng)度曲線隨著迭代次數(shù)的增加，適應(yīng)度逐漸上升；迭代尋優(yōu)后期，適應(yīng)度曲線趨于平穩(wěn)狀態(tài)，最佳適應(yīng)度穩(wěn)定在99.69%，說明在尋優(yōu)過程中支持向量機參數(shù)種群不斷進化，直到滿足訓(xùn)練條件，獲得最優(yōu)參數(shù)C*和σ*。

圖6為SVM測試集實際分類效果和預(yù)測分類效果對比圖，結(jié)合現(xiàn)有研究成果設(shè)定C=2，σ=1，圖中測試樣本總數(shù)為80，準(zhǔn)確預(yù)測樣本數(shù)為76，Ac=95%(76/80)，錯誤預(yù)測的樣本點為3個順暢流樣本點預(yù)測為平穩(wěn)流樣本點，1個擁擠流樣本點預(yù)測為堵塞流樣本點；圖7為GA-SVM測試集實際分類效果和預(yù)測分類效果對比圖，圖中測試樣本總數(shù)為80，最優(yōu)參數(shù)組合C*=0.518 5，σ*=21.067 4，準(zhǔn)確預(yù)測樣本數(shù)為79，Ac=98.75%(79/80)，錯誤預(yù)測的樣本點為1個擁擠流樣本點預(yù)測為堵塞流樣本點。

比較上述結(jié)果，GA-SVM模型和SVM模型均有較好的城市交通狀態(tài)識別效果，其中GA-SVM模型比SVM模型識別精確度提高3.75%，具體結(jié)果如表1。

由表1可知，改進后的模型優(yōu)于基于SVM的交通狀態(tài)識別模型，主要體現(xiàn)在以下3個方面：①參數(shù)選取方法，參數(shù)C和σ的選擇對支持向量分類機的學(xué)習(xí)和推廣能力有很大影響，傳統(tǒng)參數(shù)選取方法計算復(fù)雜，盲目性較強，利用遺傳算法可以在初始化范圍內(nèi)對參數(shù)進行全局、快速搜索；②全局最優(yōu)，遺傳算法具有良好的全局搜索能力，不易陷入局部最優(yōu)，利用遺傳算法對支持向量機關(guān)鍵參數(shù)進行尋優(yōu)，可找到使模型識別精確度更高的參數(shù)，在此基礎(chǔ)上進行城市道路交通狀態(tài)識別，更具科學(xué)性；③識別精確度，由表1可知，在測試集的識別分類中，GA-SVM模型識別精確度更高，更適于實際工程使用。

表1 SVM模型和GA-SVM模型分類結(jié)果比較

4 結(jié) 論

將遺傳算法和支持向量機相結(jié)合應(yīng)用于城市交通狀態(tài)識別研究，得出如下結(jié)論：

1)選取車流量、平均速度和占有率為城市交通狀態(tài)識別的基礎(chǔ)參數(shù)指標(biāo)，通過聚類分析方法，獲取以順暢流、平穩(wěn)流、擁擠流和堵塞流為標(biāo)簽的城市交通狀態(tài)先驗分類數(shù)據(jù)。

2)利用遺傳算法優(yōu)化支持向量機模型的關(guān)鍵參數(shù)——懲罰系數(shù)C和核函數(shù)σ，避免了依靠經(jīng)驗確定參數(shù)方法的盲目性。

3)依托長沙市岳麓大道監(jiān)測數(shù)據(jù)進行城市交通狀態(tài)識別研究，SVM模型和GA-SVM模型預(yù)測精確度分別達到95.00%和98.75%，相較于SVM模型，GA-SVM模型在預(yù)測精確度方面提高3.75%。

4)GA-SVM模型為城市交通狀態(tài)識別研究提供一種新思路，對智能交通系統(tǒng)中路徑誘導(dǎo)和交通控制有一定的實用價值。