信息觀和粒子群算法在城市交通擁堵中的研究

史天亮，王文光

(中鐵工程設計咨詢集團有限公司 太原設計院，山西 太原 030009)

0 引 言

交通擁堵是全國各大城市中一直存在的難點，不僅影響城市整體運營效果，還會引起經濟、文化、環境等一系列社會問題。目前許多城市通過建設高架橋、地下交通或立交橋等硬件設施來解決，這些方法雖能在一定程度上緩解交通擁堵，但實質性問題并沒有解決。找出交通擁堵主要因素才是解決問題的關鍵；同時也為當前的智能交通系統提供了強有力幫助。

導致城市道路交通擁堵的影響因素較多，主要包括道路質量、道路寬度、道路標識、天氣、擁堵時間段、特殊假日等，但這些因素并不是對交通擁堵都有重要影響，有部分因素影響程度較小，有些因素幾乎沒影響，因此存在一些非必要信息，需要進行冗余處理[1]。

粗糙集(rough set)理論作為分析不確定性的有力工具，在數據挖掘、決策分析等領域取得了廣泛應用[2]。在粗糙集理論中，屬性約簡是粗糙集應用中重要組成部分，也是優化數據關鍵流程[3-4]。粗糙集理論已在很多方面得到應用，比如大量數據挖掘、模式識別、疾病預測、機器學習等[5-9]。而在屬性約簡算法中，現主要有3種屬性約簡方法：① 利用可辨識矩陣；② 基于正域(代數觀)；③ 基于信息觀(啟發式信息)。文獻[10]指出：在粗糙集一致決策表中，代數觀和信息觀是等價的；而在不一致決策表中，信息觀約簡包含代數觀。故筆者選擇信息觀下的屬性約簡算法。

粒子群優化算法是一種尋優算法[11]。該算法能解決較為復雜的多峰值問題，并能應用于包括屬性約簡在內的多個方向[12]。但該算法由中使用的粒子在后階段行進過程中表現較為單一，整個群體失去了多元化表現，導致最后算法收斂速度基本趨于最低，最后有可能降為零值，未能持續尋優。為提升算法的找尋最優解方式，使得算法能全局收斂，雷開友等[13]對該算法進行了優化。

筆者結合信息觀層面知識，利用信息觀下的屬性約簡算法確定了交通擁堵的核心因素，并結合改進粒子群算法進行選擇；最后基于某市1 000條交通數據進行相關實驗。實驗結果表明：該算法能對解決城市交通擁堵問題提供幫助。

1 信息觀和改進粒子群算法理論

1.1 信息觀理論

1.1.1 定義1

給定實數空間上的非空有限集合[4]為U={u1,u2,…,un}，δ>0，對于U上任意對象ui，定義其δ鄰域為：δ(ui)={u|Δ(u,ui)≤δ}；?u1,u2,u3∈RN；其中：距離函數Δ滿足：

1)Δ(u1,u2)≥0，Δ(u1,u2)=0，當前僅當u1=u2，

2)Δ(u1,u2)=Δ(u2,u1)，?u1,u2∈RN；

3)Δ(u1,u3)≤Δ(u1,u2)+Δ(u2,u3)

1.1.2 定義2

給定一個鄰域決策系統，在樣本X的鄰域中，與樣本決策值不相等的鄰域稱為不一致鄰域。用數學表達式來表示：給定一個鄰域決策系統為NDT=〈U,C,D〉，其中C為條件屬性集，D為決策屬性；樣本X的不一致鄰域為：?xi∈δC(x)，且xi?δD(x)，即δC(x)-δD(x)，記為δC-D(x)。

1.1.3 定義3

給定鄰域決策系統為NDT=〈U,C,D〉，其條件熵E(D|C)可表達為式(1)：

E(D|C)=E(C,D)-E(C)

(1)

1.1.4 定義4

給定鄰域決策系統為NDT=〈U,C,D〉，B?C，對?a∈C-B，a相對于B的重要度定義如式(2)：

sig(a,B,D)=E(D|B)-E(D|B∪{A})

(2)

1.1.5 定理1

設B?C，若E(D|B)=E(D|C)，且不存在屬性A?B，使E(D|A)=E(D|B)，則稱屬性B為屬性C相對于決策D的一個約簡。

1.2 粒子群算法理論

粒子群優化算法(particle swarm optimization, PSO)基于群智能算法思想，該算法中的群包括很多個體粒子(鳥)，將它們初始化成每個解，鳥在飛行過程中都有方向和速度，對應到粒子中也就存在著方向和速度，且要計算每個解所對應的適應度值，找到當前狀態下最優解位置，然后其他粒子開始跟隨此解進行新一輪搜尋。

設數據的空間為d維，種群內個體數量為N。第i個粒子位置表示為xi=(xi1,xi2,xi3,…,xiD)；第i個粒子“飛行”在之前狀態下最優位置為Pi=(pi1,pi2,pi3,…,piD)，其中第g個粒子在之前狀態最優位置Pg為所有Pi(i=1, 2,…,g, …,n)中最好的；第i個粒子的速度為Vi=(vi1,vi2,vi3,…,viD)。每個粒子速度和位置都如下變化，如式(3)、(4)：

vid(t+1)=w×vid(t)+c1×rand( )×[pid(t)-xid(t)]+c2×rand( )×[pgd(t)-xid(t)]

(3)

xid(t+1)=xid(t)+vid(t+1)

(4)

式中：1≤i≤n，1≤d≤D；c1、c2分別為正常數，稱為加速因子；rand( )為(0, 1)之間的隨機數；w為慣性因子，w的大小決定對解空間的搜尋范圍；w×vid(t)為“慣性部分”，體現出粒子運動狀態的情況；c1×rand( )×[pid(t)-xid(t)]為“認知部分”，表示粒子自身行為狀態，通過相關行為獲得經驗的過程；c2×rand( )×[pgd(t)-xid(t)]為“社會部分”，表示粒子與其他“兄弟姐妹”間的交互共享，互相之間傳遞好的經驗；其中第d維的位置變化區間為(-Xmax,d,Xmax,d)，速度變化區間為(-Vmax,d,Vmax,d)。

1.3 改進粒子群算法理論

粒子群算法是一種基于群體的具有全局尋優能力的優化工具。粒子在搜索時可能會趨于不變狀態，群體會變的處于單一性，算法收斂速度逐漸變慢，可能會無法找到最優解。因此筆者對該算法進行改進。

1.3.1 最優“搜尋”點

根據粒子群算法，速度矢量如式(5)：

Vi(t+1)=ωVit+c1r1(pbit-xit)+c2r2(gbt-xit)

(5)

式中：xi=(xi1,xi2,…,xin)為當前粒子位置；vi為粒子速度；pbi為截止當目前的個體最優解；gb為粒子群體截止當目前的全局最優解；ω為權重系數；t為截止當目前的迭代次數；r1∈(0, 1)，r2∈(0, 1)；當pbi=gb時，粒子朝同一方向進行選擇，令該點為最優“搜尋”點。

RSPSO算法中吸引子的計算如式(6)：

pi, j(t)=φi, j(t)×pbi, j(t)+[1-φi, j(t)]×gbj(t)

(6)

可知φi,j(t)粒子全局最優值和局部最優值相等，且知道是在(0, 1)上均勻分布的無關隨機數。基于此，最優“搜尋”點的可表示如式(7)：

(7)

根據每次迭代結果，得到本次迭代“搜尋”點，該點作為具體屬性選取結果，運用式(1)計算出條件熵。每次迭代得到條件熵的值需適用度函數進行判斷，得到最大子即為最優解。

1.3.2 適應度函數

適應度函數如式(8)：

(8)

式中：Fitness(K)為適應度函數，表示粒子P中為“1”的個數與適應度關系；q為條件屬性總數；s(K)為條件屬性總數；E(D/m)為關于m(選擇的條件屬性)的條件熵；E(D/C)為條件屬性集下C的條件熵。

2 道路擁堵數據信息表準備

筆者選取某交通管理部門獲取的某路段1 000組數據作為實驗對象，從中總結出導致影響城市道路交通擁堵的因素，并將這些因素作為條件屬性集，而最終形成城市道路交通擁堵類型作為決策屬性集。

2.1 城市交通流分析

城市交通流再進行劃分時，可依據道路飽和度對城市道路狀況進行分析。假設相鄰兩路口長度為λ，擁有的車道且均為直行車道，利用視頻監控系統，可對實時進入路口、駛離路口的車輛進行目標鎖定。為保證數據準確性，選擇同一時間段內進入路口的車輛作為研究對象。當車輛進入路口后開始計時，當車輛駛離路口后停止計時。分別統計其所用時間并做平均計算，最后將平均行駛時間與規定時間進行除法運算，得出Q值。當90%≤Q≤100%，說明該道路不擁堵；當75%≤Q≤90%，說明該道路輕微擁堵；當60%≤Q≤75%，說明該道路比較擁堵；當Q≤60%，說明該道路嚴重擁堵。

假定設定時間為T，其滿足條件如式(9)：

(9)

式中：Vmin、Vmax分別為正常行駛的最低、最高速度；η為取決于路面狀態的修正系數，根據不同路面狀態進行調整。

2.2 城市交通人流分析

在城市交通擁堵問題中，各大路口人流數量是造成主干道是否擁堵的重要因素之一。人流量較大時，在設定綠燈時間內，行人無法全部同行；當紅燈亮起時，有一部分行人仍處于人行道上，等候車輛無法按時起步，導致排隊車輛長度加長，進而造成該處城市交通擁堵。隨著視頻技術發展，可實現行人個體目標鎖定及人群密度的有效判斷。在行人等候區域利用視頻監控技術，將人流密集程度設為十分密集、比較密集、輕微擁擠和不密集這4種屬性。圖1為各密度屬性示意。

圖1 人流密集程度劃分示意

通過人流密集程度有效劃分，為城市交通決策提供準確的人流數據。表1為影響城市交通擁堵問題的條件屬性，對城市擁堵問題中涉及的眾多擁堵因素進行列舉。

表1 條件屬性

表1中：將11個影響因素作為條件屬性，分別用C1,C2,…,C11表示；通過對原始交通擁堵數據預處理，即數據除噪、離散化、歸一化，最終得到交通擁堵決策表。

C1：0表示早晚高峰時段，1表示非早晚高峰時段；C2：0表示非節假日，1表示節假日；C3：0表示交通流量密度小，1表示交通流量密度大；C4：0表示道路單向為單車道，1表示道路單向為多車道；C5：0表示道路質量差，1表示道路質量一般，2表示道路質量好；C6：0表示道路有施工路段，1表示道路沒有施工路段；C7：0表示道路兩旁停車數多，1表示道路兩旁停車數一般，2表示道路兩旁停車數較少；C8：0表示車輛發生交通事故，1表示車輛未發生交通事故；C9：0表示交通路口指揮差(無信號燈，無指揮)，1表示交通路口指揮一般(無信號燈，有指揮)，2表示交通路口指揮一般(有信號燈，無指揮)，3表示交通路口指揮較好(有信號燈，有指揮)；C10：0表示行人流量大，1表示行人流量一般，2表示行人流量少；C11：0表示行人存在違章情況，1表示行人不存在違章情況。此處考慮的這11個因素是造成交通擁堵的主要原因，其他次要因素被忽略。

假定交通擁堵類型D為決策屬性。D：0表示不擁堵，1表示輕微擁堵，2表示比較擁堵，3表示嚴重擁堵。決策屬性如表2，最終形成決策信息，選取其中10組數據進行展示，如表3。

表2 決策屬性

表3 數據信息(10組)

3 屬性約簡算法

輸入：決策表A，X=?；輸出：A的最優約簡值。

1)首先計算出條件熵E(D/C)；

2)設定Ci為條件屬性集C中的任一屬性(逐一進行選擇)，即Ci∈C，設定R={C-Ci}，判斷E(D/R)是否與E(D/C)相等：若二者相等，則X=X；若二者不相等，則X=X∪Ci；

3)根據得到的屬性核集X，對其他屬性隨機生成數值，將粒子分配種群，并將得到的種群進行二進制離散化，得到標準二進制群體，并得到相應的二進制矩陣；

4)根據此前已提出的適應度函數來計算每個粒子；

5)根據得到的Fitness進行每一代評估，更新pbi和gb；

6)利用此前已提出的公式，計算每個粒子最優“搜尋”點位置，并對粒子進行區域搜索，根據粒子整體情況得到粒子在狀態上得到Fitness最優時的位置；

7)根據6)得到的最優位置更新種群中每個粒子情況，將粒子按照最優化方向策略進行位置更新(通過對種群中每個粒子進行指導性優化搜尋，在搜尋完成后，找到所謂“較優解”)，首先需進行二進制離散化，其次是運用公式將“較優解”進行二進制化，最后進行另外粒子尋優，結束本次迭代，進行下一步操作；

8)判斷是否在沒有達到迭代次數情況下找到最小約簡或已達到迭代次數，然后計算適應度值。若還沒有找到最優約簡且也還沒有達到迭代次數，則跳回3)；若已經達到迭代次數，則前往9)；

9)得到最優解L，輸出該粒子所對應屬性集合，并進行二進制化，最終該二進制屬性集合即為最優約簡結果。

4 實驗仿真

為進一步驗證IVPSO算法有效性，筆者選用4組UCI數據集，分別為：Balance、Lymphography、Tic-Tac-Toe、Post，具體數據描述如表4。實驗環境為：一臺A4 2.5GH處理器4G內存的PC機(其中：n為數據個數；l為屬性個數；k為決策類)。

表4 數據描述

4.1 約簡結果比較

為對約簡效果進行分析，采用表4中的4個數據集進行測試。筆者將所提出的CEPSO算法分別與不同文獻算法進行比較，最終根據約簡后剩余的屬性個數來表示約簡效果。實驗結果如表5和圖2。對比算法分別為PSO算法[14]、GA-PSO算法[15]、EACO算法[16]。

由表5和圖2可看出：與GARS算法、BPSO算法、CABC算法相比，IVPSO算法在數據集上能得到更小的屬性約簡，表明筆者所提出的尋優算法具有良好的全局尋優能力。

表5 約簡結果比較

圖2 各算法對數據集進行屬性約簡

4.2 迭代次數比較

對算法在收斂速度上進行評估及比較，具體方法是將這4種算法在同一數據集執行20次，再求平均值，得出平均迭代次數，實驗結果如表6。通過表6可看出：筆者選用的算法其平均迭代次數最低，證實了該算法在解決此類問題中快速有效性。

表6 迭代次數比較

5 IVPSO在城市交通擁堵中的研究

運用IVPSO算法對交通擁擠數據進行分析。從最終得到結果可知：當前時間、天氣情況、車流量情況、交通事故情況、道路是否施工、道路寬窄情況是造成交通擁堵的主要因素。

為驗證算法有效性和高效性，筆者分別采用PSO算法[14]、GA-PSO算法[15]、EACO算法[16]與文中算法(IVPSO)對數據結果屬性約簡進行評估。最終結果如表7。由表7可知：文中算法約簡率更高，說明IVPSO算法具有較好尋優能力。

表7 約簡結果對比分析

根據各算法得到的結果判斷算法有效性，計算如式(9)：

(10)

式中：t為加權系數；L為各算法最終得到的最優解；C為條件屬性集；D為決策屬性。

圖3為各算法有效性對比分析示意。從圖3可知：文中IVPSO算法有效性分析得到的結果最好，驗證了IVPSO算法的有效性。從最終約簡結果來看：影響交通擁堵核心屬性為：當前時間、天氣情況；而車流量情況、交通事故情況、道路是否施工、道路寬窄情況也是影響交通擁堵的重要因素。

圖3 各算法有效性對比分析

在下上班高峰時間段、雨雪霧天氣時，基本都會發生交通擁堵情況；若在遇到如車流量較大、發生交通事故、道路施工、道路偏窄時，交通會變得更加擁擠。因此人們在出行前首先要確定當前時間是否高峰時段、天氣情況是否為惡劣天氣，從而達到避免出現交通擁堵目的。而道路、交通監管部門針對車流量問題需做好規劃，針對車流量較大、行車壓力較大的道路做好引流；針對出現交通事故道路做到快速發現、快速解決、快速善后；針對正在施工道路提前做好告知，并根據實際情況及時做好預案；針對較窄道路做好規劃，評估是否有擴路可能，或有其他更有效的解決方法。

6 結 語

筆者針對交通擁堵的實際情況，將信息觀相關理論引入到基于粒子群優化的屬性約簡算法中。根據核屬性搜尋最優解，并通過改進粒子群優化算法使得種群中的粒子能較快地找到最優值，獲取影響交通擁堵因素；并驗證了該算法的有效性。