基于集群智能的高速公路交通狀態(tài)識別算法

曾朝暉，王江鋒*，教欣萍，熊慧媛，龔希志,2

(1.北京交通大學 交通運輸學院 綜合交通運輸大數(shù)據(jù)應用技術交通運輸行業(yè)重點實驗室，北京 100044; 2.河南省交通規(guī)劃設計研究院股份有限公司，河南 鄭州450000)

借助物聯(lián)網(wǎng)、大數(shù)據(jù)、人工智能等新一代信息技術，構建以車路協(xié)同為核心的智慧高速，將實現(xiàn)出行服務品質(zhì)化、管理科學化和運行高效化。其中智慧高速的精準管控能力對出行服務和科學管理至關重要，而基于群智感知網(wǎng)絡可實時感知路網(wǎng)交通信息，基于交通信息的交通狀態(tài)識別將有效提升智慧高速的服務水平。

傳統(tǒng)的高速公路交通狀態(tài)識別算法多借助傳感器采集的流量、占有率、速度等交通參數(shù)數(shù)據(jù)，基于不同交通狀態(tài)下交通參數(shù)具有的差異性規(guī)律展開研究，例如經(jīng)典的加州算法、McMaster算法。針對固定檢測器不方便使用的局限，研究人員引入浮動車數(shù)據(jù)進行交通狀態(tài)識別，降低誤警率[1-2]。鄔群勇等[3]利用公交車和出租車軌跡數(shù)據(jù)，提出一種交通狀態(tài)精細劃分和識別算法，能有效地識別道路局部位置的交通狀態(tài)。曹潔等[4]引入信息熵理論提出一種基于飽和度、平均排隊長度、平均行程速度、時間占有率等指標加權的識別算法，用于提高算法聚類性能和對交通狀態(tài)的識別率。

上述研究多利用傳統(tǒng)方法依據(jù)交通參數(shù)差異性規(guī)律對識別算法進行研究，在實時性和識別率上存在局限性。國內(nèi)外研究學者開始將神經(jīng)網(wǎng)絡、模式識別等人工智能技術引入到交通狀態(tài)識別算法設計中，提升算法的識別率。Luo等[5]改進了一種多類支持向量機算法用于模式識別，能夠智能判斷三種交通狀態(tài)。高林等[6]利用隨機森林算法用于交通狀態(tài)判別，并以實測數(shù)據(jù)對模型進行了驗證，判別正確率達到80%以上。常麗君等[7]研究了一種基于模擬退火算法改進的模糊C均值聚類算法(fuzzy C-means algorithm，F(xiàn)CM)與概率神經(jīng)網(wǎng)絡(PNN)結合的短時交通流狀態(tài)判別方法，提高城市道路交通狀態(tài)判別的正確性與穩(wěn)定性。李巧茹等[8]利用遺傳算法全局搜索優(yōu)勢對支持向量機的關鍵參數(shù)——懲罰系數(shù)和核函數(shù)參數(shù)σ進行優(yōu)化，建立基于遺傳算法優(yōu)化支持向量機的城市交通狀態(tài)識別模型，識別精度提高3.75%。Zhang等[9]將交通狀態(tài)識別問題轉(zhuǎn)化為圖像搜索問題，采用半監(jiān)督哈希算法，基于局部標簽信息實現(xiàn)圖像搜索獲得交通狀態(tài)。

基于傳統(tǒng)人工智能技術的交通狀態(tài)識別算法多借助諸如支持向量機為代表的線性分類器，不足以體現(xiàn)出交通參數(shù)個體所蘊含的交通狀態(tài)群體特征。集群智能通過眾多無智能個體相互之間合作，表現(xiàn)出高度結構化的群體組織行為方式，使得無智能個體通過集群行為具有的組織性、協(xié)調(diào)性等智能行為，完成無智能個體難以完成的復雜任務。借鑒集群智能優(yōu)點，本文提出一種基于集群智能的高速公路交通狀態(tài)識別算法，既體現(xiàn)不同交通狀態(tài)下交通參數(shù)個體差異性特征，又體現(xiàn)交通參數(shù)個體差異性所呈現(xiàn)的交通流狀態(tài)群體特征。將基于反向?qū)W習策略的鯨魚優(yōu)化算法(opposition-based learning whale optimization algorithm，OWOA)與FCM算法相結合，利用反向?qū)W習策略增強種群的多樣性，克服了FCM算法容易陷入局部最優(yōu)的缺點，從而提高了全局搜索能力，使得基于OWOA和FCM算法混合的高速公路交通狀態(tài)識別算法(OWOA-FCM，簡稱OWF)相較于FCM算法在高速公路交通狀態(tài)識別研究方面的泛化能力更好。該算法可用于研判高速公路交通運行態(tài)勢，為高速公路交通管理部門制定有效的管控策略奠定基礎，進而有助于提高路網(wǎng)的運行效率。

1 OWF交通狀態(tài)識別算法

1.1 高速公路交通狀態(tài)指標

交通狀態(tài)指的是道路網(wǎng)中某一個路段或者某一個區(qū)域交通流整體運行狀況的一種客觀表現(xiàn)，是一個較為模糊的概念。美國《道路通行能力手冊》[10]在考慮了交通參與者(駕駛員和乘客)主觀感受和車輛間運行條件的基礎上，將高速公路交通狀態(tài)從自由流到強制流分為A～F 共6個等級。我國借鑒美國《道路通行能力手冊》，將高速公路服務水平分為四級，如表1所示。依據(jù)每級服務水平所對應的密度值，按照平均車長為4 m，換算成相應的時間占有率。下文中根據(jù)交通量、密度、時間占有率三個參數(shù)對交通狀態(tài)進行聚類分級。

表1 我國高速公路服務水平分級情況Table 1 Classification of highway service level in China

1.2 識別算法原理

OWF算法由OWOA和FCM算法結合而成。OWOA是由WOA和反向?qū)W習策略結合的集群智能優(yōu)化算法，其中WOA則是從初始的交通狀態(tài)聚類中心開始，在迭代次數(shù)內(nèi)尋找到交通狀態(tài)最優(yōu)聚類中心。WOA雖然在收斂精度及速度上有著良好的效果，但是仍然有可能陷入局部最優(yōu)的問題，導致收斂速度慢，收斂精度低。而反向?qū)W習策略能夠擴大搜索區(qū)域增強WOA的全局搜索能力，應用反向?qū)W習策略可優(yōu)化WOA。反向?qū)W習策略初始化種群不同于WOA隨機產(chǎn)生一個初始化種群，使得減少了向最優(yōu)解搜索的距離，因此搜索效率更快。反向?qū)W習策略能夠增強種群多樣性，生成更多的初始交通狀態(tài)聚類中心。FCM算法則是根據(jù)OWOA生成的交通狀態(tài)最優(yōu)聚類中心，更新隸屬度矩陣，得到最終的交通狀態(tài)最優(yōu)聚類中心，即各個交通狀態(tài)等級Si。OWF算法克服了FCM算法容易陷入局部最優(yōu)、求解效率差的缺點，其結構如圖1所示。

圖1 OWF算法結構圖Fig.1 Architecture of the OWF algorithm

1.3 識別算法

OWOA通過反向?qū)W習策略增加初始交通狀態(tài)聚類中心的多樣性，用WOA中鯨魚群在魚群下方吐出螺旋形氣泡包圍魚群的氣幕捕殺方式，搜尋最優(yōu)交通狀態(tài)聚類中心。

1.3.1 反向?qū)W習策略

Tizhoosh[11]提出的反向?qū)W習概念是應用于智能領域的一種機器學習方法，后來因為其良好的探索能力，被廣泛用到提高啟發(fā)式算法的搜索性能中。

若x為區(qū)間[a,b]之間的任意實數(shù)，則與x相對應的反向數(shù)x*為：

x*=a+b-x，

(1)

若X=(x1,x2,…,xD)>為D維空間內(nèi)的一點，且xj為區(qū)間[aj,bj]之間的任意實數(shù)，則與之對應的反向點為：

(2)

當求解最小化問題時，X=(x1,x2,…,xD)>為D維空間內(nèi)的一點，若X的反向解X*的適應度比X的適應度小，則用X*代替X，此過程稱為反向優(yōu)化。當X*的適應度比X的適應度大時，稱X為精英個體，反之稱為普通個體。

若群體中的普通個體Xe=(xe1,xe2,…,xeD)>為D維空間內(nèi)的一點，且xej為區(qū)間[aj,bj]之間的任意實數(shù)，則普通個體的反向解為：

(3)

式中k為區(qū)間[0,1]間的隨機數(shù)，aj和bj分別為動態(tài)搜索的下界和上界。

用動態(tài)邊界代替固定邊界提升搜索質(zhì)量，上述[aj,bj]稱為固定邊界，則相應的動態(tài)邊界[daj,dbj]為：

(4)

1.3.2 WOA

(1)包圍獵物階段

在包圍獵物階段，鯨魚分頭搜尋獵物，當有鯨魚發(fā)現(xiàn)獵物時向其他鯨魚發(fā)送信號，其他鯨魚收到信號后游向發(fā)射信號的鯨魚，從而包圍獵物。包圍獵物階段其他鯨魚更新自己位置的表達式如式(5)所示：

Y(t+1)=Y*(t)-α|β·Y*(t)-Y(t)|,

(5)

式中：Y*表示距離獵物最近的鯨魚位置；Y表示當前鯨魚位置；t表示當前迭代次數(shù)；α、β表示搜索系數(shù)，其定義如式(6)～(7)所示：

α=2τ·rτ-τ，

(6)

β=2rc，

(7)

式中：rτ表示隨機向量，0≤rτ≤1；rc表示隨機向量，0≤rc≤1?？梢钥闯鏊阉飨禂?shù)α在[-τ,τ]范圍內(nèi)變化。τ在迭代過程中由2線性下降至0，計算公式如式(8)所示：

τ=2-2t/tmax，

(8)

式中tmax表示最大迭代次數(shù)。

(2)氣幕攻擊階段

在氣幕攻擊階段，鯨魚有兩種攻擊方式，一種是鯨魚個體螺旋前進吐出氣泡包圍獵物，另一種是鯨魚根據(jù)氣幕收縮形成獵物包圍圈。假設鯨魚在兩種方式間隨機切換，切換概率是0.5，則鯨魚更新位置表達式如式(9)所示：

(9)

式中：σ表示限定螺旋形狀的常數(shù)；l表示隨機數(shù)，-1≤l≤1；p表示切換概率。

(3)搜尋獵物階段

除了上述方法外，鯨魚也可以隨機選擇其余鯨魚的位置來搜尋獵物，鯨魚更新位置表達式如式(10)所示：

Y(t+1)=Y(t)-α|β·Yr(t)-Y(t)|，

(10)

式中Yr表示隨機鯨魚個體位置。

總結上述三個階段，得到結論：當p≥0.5時采用螺旋前進方式；當p<0.5時，采用包圍獵物方式，包圍獵物時根據(jù)|α|判斷更新位置方式，當|α|≥1時，通過式(10)更新鯨魚位置；當|α|<1時，通過式(5)更新鯨魚位置。

1.3.3 FCM算法

FCM算法將輸入的交通量、速度、占有率作為n個3維樣本xi(i=1,2,…,n)>分為4類，每類具有相同的標簽[12]，將OWOA得到的交通狀態(tài)聚類中心集作為FCM算法的初始聚類中心集：

(11)

式中：uji表示樣本xi屬于類j的程度；U為uji構成的c×n隸屬度矩陣；V為vj構成的d×c類中心矩陣；m∈(1，+∞)是一個加權模糊指數(shù)，反映控制隸屬度在各類之間共享的程度；dji=‖xi-vj‖表示樣本點xi到類中心vj的歐氏距離。

綜合以上各式，反向?qū)W習策略得到的初始交通聚類中心傳遞給WOA，而后經(jīng)過WOA優(yōu)化后得到交通狀態(tài)聚類中心作為FCM算法的初始模糊聚類中心Cb。經(jīng)過FCM算法不斷迭代，更新隸屬度矩陣U，得到最終的交通狀態(tài)最優(yōu)聚類中心，即各個交通狀態(tài)等級Si。

1.4 OWF求解算法

OWF求解算法步驟如下，流程框圖如圖2所示。

Step1 設置初始參數(shù)：模糊指數(shù)m、聚類類別數(shù)c、誤差閾值ε、初始化隸屬度矩陣U、種群規(guī)模N、搜索空間維度D、適應度函數(shù)f(x)、迭代次數(shù)t、最大迭代次數(shù)tmax。

Step2 隨機生成初始種群P，是為初始的隨機交通狀態(tài)聚類中心集，初始化N條鯨魚位置，其中每個鯨魚位置代表一種交通狀態(tài)聚類中心可行解。

Step4 動態(tài)邊界計算：計算精英個體的動態(tài)邊界[daj(t),dbj(t)]。

Step5 根據(jù)式(8)求取動態(tài)邊界的普通個體反向解。

Step6 將Step3以及Step5計算得到的精英反向解匯總，得到種群P1，替換種群P，作為反向?qū)W習策略下的初始交通狀態(tài)聚類中心集。

Step7 計算最優(yōu)個體：選擇所有個體中適應度函數(shù)值最小的作為鯨魚群中的最優(yōu)個體，作為該種群內(nèi)交通狀態(tài)聚類中心的局部最優(yōu)。

Step8 更新個體參數(shù)，包括隨機數(shù)τ、隨機數(shù)l、搜索系數(shù)α、搜索系數(shù)β、切換概率p。

Step9 根據(jù)|α|和切換概率p判斷鯨魚更新位置的方式，更新種群P1，即更新新的交通狀態(tài)聚類中心集，更新全局最優(yōu)個體，是為當前迭代次數(shù)內(nèi)所能尋找到的交通狀態(tài)最優(yōu)聚類中心。

Step10 若t

Step11 更新隸屬度矩陣U，更新模糊聚類中心C，得到新的交通狀態(tài)中心點。

Step12 計算價值函數(shù)，判斷是否收斂：若新一代價值函數(shù)值與上一代價值函數(shù)值的變化量大于誤差閾值，則轉(zhuǎn)回Step11，否則輸出結果為各個交通狀態(tài)等級Si，算法結束。

圖2 OWF算法流程圖Fig.2 Flowchart of the OWF algorithm

2 實證分析

2.1 數(shù)據(jù)樣本

為驗證OWF交通狀態(tài)識別算法的有效性，以盧溝橋路段2016年6月13日—15日進京方向車輛檢測器采集的實際交通流數(shù)據(jù)為研究對象，該路段地理位置如圖3所示。

圖3 路段地理位置圖Fig.3 Geographic location of the studied road section

車輛檢測器得到的數(shù)據(jù)包括檢測器id、時間、車道編號、車流方向(進京方向和出京方向)、交通量、速度、85分位車速以及時間占有率等數(shù)據(jù)。對數(shù)據(jù)進行預處理，進行可異常數(shù)據(jù)識別和修復，使用5 min的采樣間隔，提取交通量、速度和時間占有率三個參數(shù)，數(shù)據(jù)形式如表2所示。

表2 檢測器數(shù)據(jù)形式(id:823080008)Table 2 Data format of the detector(id:823080008)

2.2 仿真分析

以上述數(shù)據(jù)為基礎，應用Matlab程序進行編程，算法的初始參數(shù)值如表3所示。

表3 算法參數(shù)Table 3 Values of the algorithm parameters

為驗證OWF算法的有效性，選取1天(6月13日)樣本量進行分析，得到交通狀態(tài)聚類中心如表4所示，可以發(fā)現(xiàn)算法所得出的4個交通狀態(tài)聚類中心在速度、交通量和時間占有率3個方面都具有很大的差異，且不一樣的類型中間可以發(fā)現(xiàn)較強的規(guī)律，代表了高速公路交通狀態(tài)之間的差異性和演變的規(guī)律性。比如處于第1類劃分結果的時段都具有交通量與占有率較小，平均車速快的特點，此時對應的是高速公路交通流中的自由流狀態(tài)，而第4類劃分結果正好相反，該時段內(nèi)交通量與占有率較大，平均車速小。因此，認為OWF算法得到的交通狀態(tài)聚類中心劃分符合交通流特性。交通狀態(tài)樣本三維可視化效果圖如圖4所示，在三維空間內(nèi)呈現(xiàn)出四種交通狀態(tài)，聚類效果明顯。

表4 OWF算法得到的聚類中心Table 4 Clustering center obtained using the OWF algorithm

為進一步說明算法對交通狀態(tài)劃分的有效性，將實際聚類效果和預測聚類效果進行了對比，如圖5所示。數(shù)據(jù)為288×3矩陣，在全部288個樣本中，準確預測樣本數(shù)為265個，聚類準確率為92%。該圖還能大致看出全天該路段總體的交通狀態(tài)發(fā)展變化規(guī)律，夜間進京方向車輛較多，有一定的擁堵現(xiàn)象，早高峰期間為全天擁堵最嚴重的時間段，之后交通流不斷波動，在自由流和穩(wěn)定流狀態(tài)之間來回波動，進入夜間又開始出現(xiàn)輕微擁堵現(xiàn)象。

圖4 OWF算法聚類效果圖Fig.4 Clustering effect chart of the OWF algorithm

注：橫坐標樣本序列按照時間順序排列，每個樣本點5 min，288個樣本點共1天時間。圖5 高速公路交通流狀態(tài)判別結果Fig.5 Identification result of highway traffic states

2.3 性能評價

2.3.1 OWF與FCM算法對比

FCM算法得到的交通狀態(tài)聚類中心如表5所示，與OWF算法得到的交通狀態(tài)聚類中心是相近的。兩種算法的目標函數(shù)收斂曲線圖如圖6所示，OWF算法得到的目標函數(shù)值雖然經(jīng)過多次迭代后和FCM算法得到的目標函數(shù)值一致，但OWF算法收斂速度更快，這表明OWF算法性能更優(yōu)。

由表5可知，從c1到c3，隨著交通量增多，時間占有率變大，而速度幾乎不變，說明S1到S3的交通狀態(tài)是由自由流到高密度穩(wěn)定交通流過度，而c4較c3交通量減少，速度急劇下降，時間占有率迅速上升，說明S4的交通狀態(tài)轉(zhuǎn)變?yōu)檫^飽和狀態(tài)。

表5 FCM算法得到的聚類中心Table 5 Clustering center obtained using the FCM algorithm

圖6 目標函數(shù)收斂曲線圖Fig.6 Convergence curve of the objective function

2.3.2 不同樣本量效果對比

為進一步研究樣本量多少對狀態(tài)聚類效果的影響，現(xiàn)選取1 d(6月13日)和3 d樣本量(6月13日—15日)分別聚類進行比較分析。由OWF算法得到的3 d樣本量的交通狀態(tài)聚類中心如表6所示。3 d樣本量數(shù)據(jù)對應的聚類效果圖如圖7所示。

表6 3 d樣本量的聚類中心Table 6 Comparison of clustering centers for three days

圖7 3 d數(shù)據(jù)的交通狀態(tài)聚類結果Fig.7 Traffic state clustering results for three days

由圖7可知，相對圖4給出的1 d樣本量數(shù)據(jù)得到的聚類結果，3 d樣本量數(shù)據(jù)得到的聚類效果更明顯一些，樣本數(shù)據(jù)分布規(guī)律基本符合前文所述的交通流參數(shù)關系。

不同樣本量交通狀態(tài)識別率對比如圖8所示，每個箱型分別為該數(shù)據(jù)集的四個階段交通狀態(tài)識別率分布，從最高識別率到最低識別率進行排列。由圖8可得，使用3 d樣本量的交通狀態(tài)整體識別率92.8%與使用1天樣本量的交通狀態(tài)整體識別率92%相近，因此可以認為樣本量增多不會降低OWF算法的整體識別率。

圖8 不同樣本量交通狀態(tài)識別率對比Fig.8 Comparison of traffic state recognition rate with different samples

3 結論

本文將基于反向?qū)W習策略的鯨魚優(yōu)化算法與FCM算法相結合，提出一種基于集群智能的高速公路交通狀態(tài)識別算法，既考慮交通參數(shù)個體特征差異，又考慮個體參數(shù)所蘊含的群體特征差異性。利用反向?qū)W習策略的優(yōu)點擴大搜索范圍且增強全局搜索能力，優(yōu)化交通狀態(tài)初始模糊聚類中心，克服FCM算法易陷入局部最優(yōu)的缺點。以進京高速某路段交通數(shù)據(jù)為基礎，進行實例分析，結果表明，OWF算法在高速公路交通狀態(tài)識別上具有良好的效果，準確率達到92%，且收斂速度較FCM算法更快，同時樣本量增多不會降低OWF算法的整體識別率。

本文研究的路段未考慮匝道口的影響，不受匝道車流匯入及駛出影響，在下一步研究中，將考慮包含匝道路段的交通狀態(tài)識別。