基于集群智能的高速公路交通狀態識別算法

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

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

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

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

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

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

1 OWF交通狀態識別算法

1.1 高速公路交通狀態指標

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

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

1.2 識別算法原理

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

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

1.3 識別算法

OWOA通過反向學習策略增加初始交通狀態聚類中心的多樣性，用WOA中鯨魚群在魚群下方吐出螺旋形氣泡包圍魚群的氣幕捕殺方式，搜尋最優交通狀態聚類中心。

1.3.1 反向學習策略

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

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

x*=a+b-x，

(1)

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

(2)

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

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

(3)

式中k為區間[0,1]間的隨機數，aj和bj分別為動態搜索的下界和上界。

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

(4)

1.3.2 WOA

(1)包圍獵物階段

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

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

(5)

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

α=2τ·rτ-τ，

(6)

β=2rc，

(7)

式中：rτ表示隨機向量，0≤rτ≤1；rc表示隨機向量，0≤rc≤1。可以看出搜索系數α在[-τ,τ]范圍內變化。τ在迭代過程中由2線性下降至0，計算公式如式(8)所示：

τ=2-2t/tmax，

(8)

式中tmax表示最大迭代次數。

(2)氣幕攻擊階段

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

(9)

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

(3)搜尋獵物階段

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

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

(10)

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

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

1.3.3 FCM算法

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

(11)

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

綜合以上各式，反向學習策略得到的初始交通聚類中心傳遞給WOA，而后經過WOA優化后得到交通狀態聚類中心作為FCM算法的初始模糊聚類中心Cb。經過FCM算法不斷迭代，更新隸屬度矩陣U，得到最終的交通狀態最優聚類中心，即各個交通狀態等級Si。

1.4 OWF求解算法

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

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

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

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

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

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

Step7 計算最優個體：選擇所有個體中適應度函數值最小的作為鯨魚群中的最優個體，作為該種群內交通狀態聚類中心的局部最優。

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

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

Step10 若t

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

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

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

2 實證分析

2.1 數據樣本

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

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

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

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

2.2 仿真分析

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

表3 算法參數Table 3 Values of the algorithm parameters

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

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

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

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

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

2.3 性能評價

2.3.1 OWF與FCM算法對比

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

由表5可知，從c1到c3，隨著交通量增多，時間占有率變大，而速度幾乎不變，說明S1到S3的交通狀態是由自由流到高密度穩定交通流過度，而c4較c3交通量減少，速度急劇下降，時間占有率迅速上升，說明S4的交通狀態轉變為過飽和狀態。

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

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

2.3.2 不同樣本量效果對比

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

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

圖7 3 d數據的交通狀態聚類結果Fig.7 Traffic state clustering results for three days

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

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

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

3 結論

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

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