史天亮，王文光

(中鐵工程設(shè)計(jì)咨詢集團(tuán)有限公司 太原設(shè)計(jì)院，山西 太原 030009)

0 引 言

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

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

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

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

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

1 信息觀和改進(jìn)粒子群算法理論

1.1 信息觀理論

1.1.1 定義1

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

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

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

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

1.1.2 定義2

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

1.1.3 定義3

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

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

(1)

1.1.4 定義4

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

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

(2)

1.1.5 定理1

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

1.2 粒子群算法理論

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

設(shè)數(shù)據(jù)的空間為d維，種群內(nèi)個(gè)體數(shù)量為N。第i個(gè)粒子位置表示為xi=(xi1,xi2,xi3,…,xiD)；第i個(gè)粒子“飛行”在之前狀態(tài)下最優(yōu)位置為Pi=(pi1,pi2,pi3,…,piD)，其中第g個(gè)粒子在之前狀態(tài)最優(yōu)位置Pg為所有Pi(i=1, 2,…,g, …,n)中最好的；第i個(gè)粒子的速度為Vi=(vi1,vi2,vi3,…,viD)。每個(gè)粒子速度和位置都如下變化，如式(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分別為正常數(shù)，稱為加速因子；rand( )為(0, 1)之間的隨機(jī)數(shù)；w為慣性因子，w的大小決定對(duì)解空間的搜尋范圍；w×vid(t)為“慣性部分”，體現(xiàn)出粒子運(yùn)動(dòng)狀態(tài)的情況；c1×rand( )×[pid(t)-xid(t)]為“認(rèn)知部分”，表示粒子自身行為狀態(tài)，通過相關(guān)行為獲得經(jīng)驗(yàn)的過程；c2×rand( )×[pgd(t)-xid(t)]為“社會(huì)部分”，表示粒子與其他“兄弟姐妹”間的交互共享，互相之間傳遞好的經(jīng)驗(yàn)；其中第d維的位置變化區(qū)間為(-Xmax,d,Xmax,d)，速度變化區(qū)間為(-Vmax,d,Vmax,d)。

1.3 改進(jìn)粒子群算法理論

粒子群算法是一種基于群體的具有全局尋優(yōu)能力的優(yōu)化工具。粒子在搜索時(shí)可能會(huì)趨于不變狀態(tài)，群體會(huì)變的處于單一性，算法收斂速度逐漸變慢，可能會(huì)無法找到最優(yōu)解。因此筆者對(duì)該算法進(jìn)行改進(jìn)。

1.3.1 最優(yōu)“搜尋”點(diǎn)

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

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

(5)

式中：xi=(xi1,xi2,…,xin)為當(dāng)前粒子位置；vi為粒子速度；pbi為截止當(dāng)目前的個(gè)體最優(yōu)解；gb為粒子群體截止當(dāng)目前的全局最優(yōu)解；ω為權(quán)重系數(shù)；t為截止當(dāng)目前的迭代次數(shù)；r1∈(0, 1)，r2∈(0, 1)；當(dāng)pbi=gb時(shí)，粒子朝同一方向進(jìn)行選擇，令該點(diǎn)為最優(yōu)“搜尋”點(diǎn)。

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

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

(6)

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

(7)

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

1.3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)如式(8)：

(8)

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

2 道路擁堵數(shù)據(jù)信息表準(zhǔn)備

筆者選取某交通管理部門獲取的某路段1 000組數(shù)據(jù)作為實(shí)驗(yàn)對(duì)象，從中總結(jié)出導(dǎo)致影響城市道路交通擁堵的因素，并將這些因素作為條件屬性集，而最終形成城市道路交通擁堵類型作為決策屬性集。

2.1 城市交通流分析

城市交通流再進(jìn)行劃分時(shí)，可依據(jù)道路飽和度對(duì)城市道路狀況進(jìn)行分析。假設(shè)相鄰兩路口長(zhǎng)度為λ，擁有的車道且均為直行車道，利用視頻監(jiān)控系統(tǒng)，可對(duì)實(shí)時(shí)進(jìn)入路口、駛離路口的車輛進(jìn)行目標(biāo)鎖定。為保證數(shù)據(jù)準(zhǔn)確性，選擇同一時(shí)間段內(nèi)進(jìn)入路口的車輛作為研究對(duì)象。當(dāng)車輛進(jìn)入路口后開始計(jì)時(shí)，當(dāng)車輛駛離路口后停止計(jì)時(shí)。分別統(tǒng)計(jì)其所用時(shí)間并做平均計(jì)算，最后將平均行駛時(shí)間與規(guī)定時(shí)間進(jìn)行除法運(yùn)算，得出Q值。當(dāng)90%≤Q≤100%，說明該道路不擁堵；當(dāng)75%≤Q≤90%，說明該道路輕微擁堵；當(dāng)60%≤Q≤75%，說明該道路比較擁堵；當(dāng)Q≤60%，說明該道路嚴(yán)重?fù)矶隆?/p>

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

(9)

式中：Vmin、Vmax分別為正常行駛的最低、最高速度；η為取決于路面狀態(tài)的修正系數(shù)，根據(jù)不同路面狀態(tài)進(jìn)行調(diào)整。

2.2 城市交通人流分析

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

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

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

表1 條件屬性

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

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

假定交通擁堵類型D為決策屬性。D：0表示不擁堵，1表示輕微擁堵，2表示比較擁堵，3表示嚴(yán)重?fù)矶隆Q策屬性如表2，最終形成決策信息，選取其中10組數(shù)據(jù)進(jìn)行展示，如表3。

表2 決策屬性

表3 數(shù)據(jù)信息(10組)

3 屬性約簡(jiǎn)算法

輸入：決策表A，X=?；輸出：A的最優(yōu)約簡(jiǎn)值。

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

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

3)根據(jù)得到的屬性核集X，對(duì)其他屬性隨機(jī)生成數(shù)值，將粒子分配種群，并將得到的種群進(jìn)行二進(jìn)制離散化，得到標(biāo)準(zhǔn)二進(jìn)制群體，并得到相應(yīng)的二進(jìn)制矩陣；

4)根據(jù)此前已提出的適應(yīng)度函數(shù)來計(jì)算每個(gè)粒子；

5)根據(jù)得到的Fitness進(jìn)行每一代評(píng)估，更新pbi和gb；

6)利用此前已提出的公式，計(jì)算每個(gè)粒子最優(yōu)“搜尋”點(diǎn)位置，并對(duì)粒子進(jìn)行區(qū)域搜索，根據(jù)粒子整體情況得到粒子在狀態(tài)上得到Fitness最優(yōu)時(shí)的位置；

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

8)判斷是否在沒有達(dá)到迭代次數(shù)情況下找到最小約簡(jiǎn)或已達(dá)到迭代次數(shù)，然后計(jì)算適應(yīng)度值。若還沒有找到最優(yōu)約簡(jiǎn)且也還沒有達(dá)到迭代次數(shù)，則跳回3)；若已經(jīng)達(dá)到迭代次數(shù)，則前往9)；

9)得到最優(yōu)解L，輸出該粒子所對(duì)應(yīng)屬性集合，并進(jìn)行二進(jìn)制化，最終該二進(jìn)制屬性集合即為最優(yōu)約簡(jiǎn)結(jié)果。

4 實(shí)驗(yàn)仿真

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

表4 數(shù)據(jù)描述

4.1 約簡(jiǎn)結(jié)果比較

為對(duì)約簡(jiǎn)效果進(jìn)行分析，采用表4中的4個(gè)數(shù)據(jù)集進(jìn)行測(cè)試。筆者將所提出的CEPSO算法分別與不同文獻(xiàn)算法進(jìn)行比較，最終根據(jù)約簡(jiǎn)后剩余的屬性個(gè)數(shù)來表示約簡(jiǎn)效果。實(shí)驗(yàn)結(jié)果如表5和圖2。對(duì)比算法分別為PSO算法[14]、GA-PSO算法[15]、EACO算法[16]。

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

表5 約簡(jiǎn)結(jié)果比較

圖2 各算法對(duì)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)

4.2 迭代次數(shù)比較

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

表6 迭代次數(shù)比較

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

運(yùn)用IVPSO算法對(duì)交通擁擠數(shù)據(jù)進(jìn)行分析。從最終得到結(jié)果可知：當(dāng)前時(shí)間、天氣情況、車流量情況、交通事故情況、道路是否施工、道路寬窄情況是造成交通擁堵的主要因素。

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

表7 約簡(jiǎn)結(jié)果對(duì)比分析

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

(10)

式中：t為加權(quán)系數(shù)；L為各算法最終得到的最優(yōu)解；C為條件屬性集；D為決策屬性。

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

圖3 各算法有效性對(duì)比分析

在下上班高峰時(shí)間段、雨雪霧天氣時(shí)，基本都會(huì)發(fā)生交通擁堵情況；若在遇到如車流量較大、發(fā)生交通事故、道路施工、道路偏窄時(shí)，交通會(huì)變得更加擁擠。因此人們?cè)诔鲂星笆紫纫_定當(dāng)前時(shí)間是否高峰時(shí)段、天氣情況是否為惡劣天氣，從而達(dá)到避免出現(xiàn)交通擁堵目的。而道路、交通監(jiān)管部門針對(duì)車流量問題需做好規(guī)劃，針對(duì)車流量較大、行車壓力較大的道路做好引流；針對(duì)出現(xiàn)交通事故道路做到快速發(fā)現(xiàn)、快速解決、快速善后；針對(duì)正在施工道路提前做好告知，并根據(jù)實(shí)際情況及時(shí)做好預(yù)案；針對(duì)較窄道路做好規(guī)劃，評(píng)估是否有擴(kuò)路可能，或有其他更有效的解決方法。

6 結(jié) 語(yǔ)

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