基于GA- FCM 和SVM 的城市快速路交通狀態(tài)判別方法研究

王崢

（蘇州科技大學(xué)，江蘇 蘇州212200）

1 概述

準(zhǔn)確劃分城市快速路交通狀態(tài)能為交通信息發(fā)布與服務(wù)水平評價提供重要依據(jù)，國內(nèi)外學(xué)者提出了許多有效的交通狀態(tài)判別方法，其中機(jī)器學(xué)習(xí)算法因其強(qiáng)大的性能得到廣泛關(guān)注。

聚類分析方法能夠在沒有任何先驗標(biāo)簽數(shù)據(jù)的基礎(chǔ)上對交通流數(shù)據(jù)進(jìn)行分類。董紅召等[1]對交通流數(shù)據(jù)進(jìn)行模糊聚類，定量分析交通路網(wǎng)的狀態(tài)，在此基礎(chǔ)上分析路網(wǎng)密度，對城市道路狀態(tài)進(jìn)行實(shí)時判別。錢超等[2]應(yīng)用FCM算法將交通狀態(tài)劃分為四個類別，并利用蒙特卡洛模擬法對聚類精度進(jìn)行評價。楊慶芳等[3]以高速公路收費(fèi)依據(jù)為基礎(chǔ)建立FCM算法模型判別交通狀態(tài)。

經(jīng)典有監(jiān)督學(xué)習(xí)算法支持向量機(jī)（SVM）和人工神經(jīng)網(wǎng)絡(luò)（ANN）也被廣泛運(yùn)用到交通狀態(tài)判別當(dāng)中。于榮，王國祥等[4]對比了SVM三種核函數(shù)在交通狀態(tài)分類中的優(yōu)劣性，并提出在數(shù)據(jù)預(yù)處理時歸一化的必要性。李清泉，高德荃等[5]結(jié)合模糊理論和SVM建立了模糊SVM模型用于交通狀態(tài)分類。董春嬌，邵春福等[6]建立了一種基于優(yōu)化SVM的城市快速路交通狀態(tài)判別方法。李曉斌，徐建閩等[7]利用RBF 神經(jīng)網(wǎng)絡(luò)建立了交通狀態(tài)判別模型。巫威眺，靳文舟等[8]提出了基于BP 神經(jīng)網(wǎng)絡(luò)的交通狀態(tài)判別模型。

上述文獻(xiàn)為城市快速路交通狀態(tài)判別提供了理論基礎(chǔ)，但大部分的文獻(xiàn)都只是單純使用聚類或者分類，入手角度單一，由于數(shù)據(jù)量大且參數(shù)維度高，如果不對參數(shù)進(jìn)行預(yù)處理就容易造成運(yùn)算量大程序運(yùn)行時間過長或分類結(jié)果不精準(zhǔn)等情況，因此本文運(yùn)用先聚類后分類的策略，構(gòu)建了基于GA-FCM的交通狀態(tài)聚類模型，先對大量數(shù)據(jù)進(jìn)行聚類預(yù)處理后，再使用SVM進(jìn)行交通狀態(tài)分類使之更容易找到分類邊界，提高數(shù)據(jù)處理效率和分類準(zhǔn)確度。

2 基于GA-FCM 和SVM 的判別方法

2.1 模糊C 均值算法和遺傳算法存在的問題

FCM采用梯度下降法尋找最優(yōu)解，這種計算方法收斂速度快，但存在著對初始化敏感與容易陷入局部最優(yōu)解等問題。上述缺點(diǎn)導(dǎo)致模糊C 均值應(yīng)用于交通流狀態(tài)劃分時可能無法給出正確的聚類結(jié)果。

遺傳算法（GA）[9]是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法。在函數(shù)求解、參數(shù)尋優(yōu)方面性能強(qiáng)悍，已被廣泛運(yùn)用到各個領(lǐng)域。考慮到FCM可能會陷入局部最優(yōu)，本文憑借遺傳算法優(yōu)秀的全局搜索能力對FCM進(jìn)行優(yōu)化。盡管遺傳算法能夠?qū)崿F(xiàn)全局優(yōu)化，但其本身也存在一定的缺陷。采用二進(jìn)制進(jìn)行染色體的編碼可能會帶來字符串長度、計算精度、運(yùn)算量等一系列問題。

2.2 基于遺傳算法的FCM算法

針對上文的不足，提出一種基于遺傳算法的模糊聚類，采用實(shí)數(shù)進(jìn)行編碼，然后進(jìn)行交叉、變異，最后再結(jié)合FCM 算法進(jìn)行聚類分析。該算法首先使用優(yōu)化的遺傳算法得到全局最優(yōu)解的近似解，然后把近似解作為FCM算法的初始值，最后再用FCM 算法求解得到全局最優(yōu)解[10]。

編碼：采用實(shí)數(shù)（實(shí)值）編碼策略，簡化了編碼過程，提高了算法的收斂速度和全局搜索能力。將C 個聚類中心組成一個染色體，每個聚類中心有S 個特征值，則編碼長度為C*S。染色體的編碼表示形式為：p11p12…pc1pc2…cs。

選擇：

①計算所有個體適應(yīng)度，找出適應(yīng)度最高的個體復(fù)制到下一代；

交叉：采用單點(diǎn)交叉，隨機(jī)產(chǎn)生交叉點(diǎn)并交換兩父體右半部分產(chǎn)生新個體。

變異：在初始交叉概率的基礎(chǔ)上增加了一個權(quán)值ω=1-f/fmax，個體的變異概率為ω*Pm，fmax表示種群中的最大適應(yīng)度，Pm為變異概率。

2.3 基于GA-FCM和SVM建立的交通狀態(tài)判別模型

步驟1：編碼并初始化種群，確定三參數(shù)的上下界，分別在三參數(shù)上下界中生成3 個隨機(jī)數(shù)作為1 個初始聚類中心，本文聚類數(shù)為4，故執(zhí)行4 次生成四個聚類中心。將四個隨機(jī)生成的初始聚類中心按實(shí)數(shù)編碼組成一個染色體。

步驟2：確定種群規(guī)模，對種群中按步驟一操作生成的染色體進(jìn)行適應(yīng)度評價后進(jìn)行選擇、交叉、變異生成新種群，滿足終止條件后結(jié)束遺傳算法。

步驟3：將遺傳算法得到的聚類中心矩陣作為FCM的初始值帶入FCM計算。并輸出最終的聚類中心。

步驟4：將聚類過后的4 類數(shù)據(jù)分別打上標(biāo)簽，劃分測試集和訓(xùn)練集，選擇SVM核函數(shù)和確定參數(shù)值后進(jìn)行訓(xùn)練。

步驟5：分別使用網(wǎng)格搜索法、粒子群算法、遺傳算法對SVM參數(shù)值進(jìn)行優(yōu)化，確定最優(yōu)參數(shù)組后使用測試集對模型進(jìn)行測試。

3 模型驗證

本文選取上海市某城市快速路路段檢測器提供的2017 年8 月19 日24 小時的交通路參數(shù)（流量、速度、占有率），采集間隔時間為1 分鐘，共1440 組。

3.1 聚類結(jié)果

根據(jù)交通流運(yùn)行特性并參考中國道路服務(wù)四個等級，采用基于改進(jìn)遺傳算法的模糊聚類將交通狀態(tài)劃分為四類。

算法基本參數(shù)：種群數(shù)量n=50，最大進(jìn)化代數(shù)T=100，遺傳概率Pc=0.7，變異概率pm=0.1，聚類中心數(shù)目n=4，模糊系數(shù)m=2，最大迭代次數(shù)100，類內(nèi)距離ε=1*10-5。

4 種交通狀態(tài)的聚類中心矩陣：

第一至四行分別代表擁堵、擁擠、平穩(wěn)、通暢4 種不同的交通狀態(tài)。其中第一類樣本271 個，第二類樣本367 個，第三類樣本378 個，第四類樣本424 個。各類交通狀態(tài)參數(shù)空間分布如圖1 所示。

圖1 交通狀態(tài)聚類結(jié)果圖

算法收斂圖像如圖2 所示。

由于遺傳算法的全局搜索性能優(yōu)秀，經(jīng)過遺傳算法優(yōu)化得到的FCM目標(biāo)函數(shù)初始值已接近FCM目標(biāo)函數(shù)的極值，將此初始值帶入FCM算法求解迭代公式，由圖可以看到FCM算法迭代10 次以內(nèi)已經(jīng)收斂收斂，說明改進(jìn)過的算法收斂能力強(qiáng)，比單純使用FCM效果好。

圖2 GA-FCM 與FCM 算法收斂曲線對比圖

3.2 多分類支持向量機(jī)狀態(tài)判別

利用基于遺傳算法的模糊聚類將1440 組交通流參數(shù)分成了四類，為確保支持向量機(jī)分類的準(zhǔn)確性隨機(jī)抽取40%的標(biāo)簽數(shù)據(jù)作為測試集，60%的標(biāo)簽數(shù)據(jù)作為訓(xùn)練集。

粒子群算法參數(shù)設(shè)定：局部搜索能力和全局搜索能力參數(shù)c1=1.5，c2=1.7，最大進(jìn)化數(shù)量200，最大種群數(shù)量20，速率關(guān)系參數(shù)0.6，速率彈性系數(shù)1，種群彈性系數(shù)1，搜索范圍C∈[0.1，100]，g∈[0.1，100]交叉驗證次數(shù)v=3，C=0.5172，g=0.01 時分類效果最優(yōu)97.7431%。優(yōu)化過程如圖3 所示。

圖3 粒子群算法迭代適應(yīng)度曲線

遺傳算法參數(shù)設(shè)定：最大進(jìn)化代數(shù)T=100，最大種群數(shù)量N=20，交叉概率Pc=0.95，變異概率Pm=0.1，搜索范圍C∈[0，100]，g∈[0，100] 交 叉 驗 證 次 數(shù)v=10，當(dāng)C=0.96292，g=0.0038147 時分類準(zhǔn)確率最優(yōu)為98.6111%。優(yōu)化結(jié)果過程圖4 所示。

通過3 種參數(shù)尋優(yōu)方法比較，最終確定最優(yōu)參數(shù)組合C=0.96292，g=0.0038147。通過選取的最優(yōu)參數(shù)組合對剩余的576 組標(biāo)簽數(shù)據(jù)進(jìn)行測試，準(zhǔn)確率達(dá)98.6111%，共錯誤分類8個樣本，其中第一類誤判2 個樣本，第二類誤判3 個樣本，第三類誤判1 個樣本，第四類分類誤判2 個樣本。

圖4 遺傳算法迭代適應(yīng)度曲線

4 結(jié)論

本文結(jié)合了FCM和SVM的優(yōu)勢，構(gòu)建了基于模糊聚類和支持向量機(jī)的交通狀態(tài)判別模型。首先通過基于改進(jìn)遺傳算法的模糊聚類將交通流參數(shù)劃分成四類，分別代表四種交通狀態(tài)，并將數(shù)據(jù)打上標(biāo)簽；然后劃分測試集和訓(xùn)練集，通過支持向量機(jī)進(jìn)行訓(xùn)練集分類，并使用網(wǎng)格搜索法、粒子群算法、遺傳算法進(jìn)行參數(shù)對尋優(yōu)得到最佳參數(shù)組合，最后將最優(yōu)參數(shù)組合用于測試集，實(shí)驗結(jié)果表明模型性能良好，判別準(zhǔn)確率可達(dá)98.6111%，判別準(zhǔn)確率較高。