基于貝葉斯網(wǎng)絡(luò)推理的道路網(wǎng)絡(luò)級聯(lián)失效仿真

劉新全

（廣西師范學(xué)院 a.北部灣環(huán)境演變與資源利用教育部重點(diǎn)實(shí)驗(yàn)室；b.廣西地表過程與智能模擬重點(diǎn)實(shí)驗(yàn)室；c.物流管理與工程學(xué)院，南寧530001）

基于貝葉斯網(wǎng)絡(luò)推理的道路網(wǎng)絡(luò)級聯(lián)失效仿真

劉新全*a,b,c

（廣西師范學(xué)院 a.北部灣環(huán)境演變與資源利用教育部重點(diǎn)實(shí)驗(yàn)室；b.廣西地表過程與智能模擬重點(diǎn)實(shí)驗(yàn)室；c.物流管理與工程學(xué)院，南寧530001）

針對道路網(wǎng)絡(luò)級聯(lián)失效與其它復(fù)雜網(wǎng)絡(luò)相比具有的特殊性，基于貝葉斯網(wǎng)絡(luò)推理，融合駕駛者出行先驗(yàn)及出行信息，研究了道路網(wǎng)絡(luò)級聯(lián)失效的演變機(jī)理及演變過程.編制MATLAB程序生成基于道路網(wǎng)絡(luò)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，根據(jù)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)MATLAB程序，學(xué)習(xí)了駕駛者感知路段屬性變化；給出了仿真算法，仿真了貝葉斯網(wǎng)絡(luò)推理中不同出行先驗(yàn)權(quán)重，以及出行信息量對道路網(wǎng)絡(luò)屬性及級聯(lián)失效的影響.結(jié)果表明，貝葉斯網(wǎng)絡(luò)推理可以較好地反映駕駛者出行路段選擇對道路網(wǎng)絡(luò)級聯(lián)失效的定量影響，為研究道路網(wǎng)絡(luò)級聯(lián)失效提供了新的研究思路和方法.

交通工程；級聯(lián)失效；貝葉斯網(wǎng)絡(luò)推理；道路網(wǎng)絡(luò)；仿真

1 引言

級聯(lián)失效的產(chǎn)生源自于網(wǎng)絡(luò)中一個(gè)或者少數(shù)幾個(gè)節(jié)點(diǎn)或者邊，受自身或外部環(huán)境影響發(fā)生故障或失效，并且這種故障或失效會引起其它節(jié)點(diǎn)或邊發(fā)生故障或失效，從而可能產(chǎn)生連鎖反應(yīng)，最終導(dǎo)致大部分的節(jié)點(diǎn)或者邊失效，這種現(xiàn)象被稱為級聯(lián)失效[1].城市道路網(wǎng)絡(luò)級聯(lián)失效影響道路網(wǎng)絡(luò)穩(wěn)定性，對城市居民出行及社會經(jīng)濟(jì)發(fā)展產(chǎn)生較大影響.當(dāng)前已有學(xué)者對交通網(wǎng)絡(luò)級聯(lián)失效的產(chǎn)生機(jī)理，以及影響規(guī)律等進(jìn)行了建模和仿真研究，提出了新的方法，并取得了較好的結(jié)果[2].相關(guān)研究為分析城市道路網(wǎng)絡(luò)級聯(lián)失效問題提供了理論和方法基礎(chǔ).通過對現(xiàn)有文獻(xiàn)的深入剖析發(fā)現(xiàn)，對級聯(lián)失效理論的研究最初源于對電力網(wǎng)絡(luò)、互聯(lián)網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)級聯(lián)效應(yīng)的研究[3]，在這些網(wǎng)絡(luò)中，流動的介質(zhì)為電流和信息等；而城市道路網(wǎng)絡(luò)中負(fù)載的產(chǎn)生是由于車輛的行駛，車輛的駕駛者是具有思考和推理能力的人，明顯區(qū)別于電力網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)等網(wǎng)絡(luò)中的負(fù)載，因此道路網(wǎng)絡(luò)級聯(lián)失效的產(chǎn)生和演變具有更強(qiáng)的復(fù)雜性.現(xiàn)實(shí)道路網(wǎng)絡(luò)中駕駛者多次駕駛出行形成出行經(jīng)驗(yàn)，在下次出行過程中會根據(jù)經(jīng)驗(yàn)和實(shí)際道路狀況進(jìn)行路徑選擇，這種選擇影響著道路網(wǎng)絡(luò)中路段負(fù)載的分布，影響級聯(lián)失效的演變路徑；另外，道路網(wǎng)絡(luò)中突發(fā)事件的產(chǎn)生也會造成路段屬性的改變，駕駛者對這種屬性改變的理解不同，也會產(chǎn)生不同的駕駛選擇行為，從而增加了道路網(wǎng)絡(luò)中路段負(fù)載變化的復(fù)雜性.因此研究城市道路網(wǎng)絡(luò)級聯(lián)失效，需要考慮駕駛者的出行經(jīng)驗(yàn)、突發(fā)事件、路段屬性等的影響.貝葉斯網(wǎng)絡(luò)推理是表示和處理不確定性知識比較理想的模型之一[4],駕駛者出行前以出行經(jīng)驗(yàn)為基礎(chǔ)，借助出行信息更新路段屬性的行為，可以看作是駕駛者對路段屬性的一種推理過程，這與貝葉斯網(wǎng)絡(luò)推理中貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)和參數(shù)學(xué)習(xí)的過程是一致的.

2 級聯(lián)失效理論

當(dāng)前文獻(xiàn)從不同領(lǐng)域?qū)壜?lián)失效問題進(jìn)行了一定的研究[5,6]，通過建立模型對級聯(lián)失效產(chǎn)生和演變進(jìn)行了仿真[7]，為研究城市道路網(wǎng)絡(luò)級聯(lián)失效問題提供了理論支撐.道路網(wǎng)絡(luò)級聯(lián)失效仿真研究，首先要確定網(wǎng)絡(luò)中每條邊的負(fù)載，往往采用最短路介數(shù)[8]，認(rèn)為經(jīng)過路段的最短路徑越多，該路段上的負(fù)載越高：

式中 La——路段xa上的負(fù)載；

lod（a）——節(jié)點(diǎn)o與d之間經(jīng)過路段xa的最短路徑數(shù)目；

lod——節(jié)點(diǎn)o與d之間所有最短路徑數(shù)目；

Z——節(jié)點(diǎn)集合.

實(shí)際道路網(wǎng)絡(luò)中，由于交通擁堵、流量限制及其它隨機(jī)事件影響，起訖點(diǎn)間最短路徑往往不是出行距離最短的路徑，駕駛者在不確定環(huán)境下的出行更多考慮的是能夠按照預(yù)期及時(shí)到達(dá)目的地，因此，本文考慮出行時(shí)間最短.另外，城市道路網(wǎng)絡(luò)中，每條路段的交通容量是有限的，稱為路段負(fù)載容限，表示為[3]

式中 ζ——“容限系數(shù)”，ζ≥1；

為衡量級聯(lián)失效給道路網(wǎng)絡(luò)帶來的損害程度，使用區(qū)域路網(wǎng)中路段數(shù)目相對大小來衡量：

式中 Ωod——od之間路網(wǎng)的損害程度；

S′——級聯(lián)失效引起的失效路段的數(shù)目；

S——級聯(lián)失效前，道路網(wǎng)絡(luò)中路段的數(shù)目.

3 基于路段的貝葉斯網(wǎng)絡(luò)推理

3.1 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

結(jié)合研究內(nèi)容，定義：xa表示道路網(wǎng)絡(luò)中的路段；X表示所有路段集合，其中 a=1，…，n，xa∈X ；Ta表示路段的屬性值域，；道路網(wǎng)絡(luò)中駕駛者依據(jù)前一路段的屬性值來估計(jì)當(dāng)前路段的屬性值，這種估計(jì)可以使用貝葉斯網(wǎng)絡(luò)描述為變量xa屬性值的變化依賴于直接的父節(jié)點(diǎn)，與其它節(jié)點(diǎn)是條件獨(dú)立的，因此變量xa對應(yīng)的聯(lián)合概率分布表達(dá)式為

式中 ga（xa）——道路網(wǎng)絡(luò)結(jié)構(gòu)中路段xa的所有父路段的集合；

g（xa|ga（xa）——為路段xa的父路段（即前一路段）取某一屬性值的條件概率分布.

3.2 基于路段的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)

定義ga（xa）在集合中取值，那么根據(jù)貝葉斯網(wǎng)絡(luò)模型，路段xa對應(yīng)的條件概率可以表示為

3.3 算法實(shí)現(xiàn)

其次，定義樣本數(shù)據(jù)的數(shù)目為出行信息量（nsamples），將樣本數(shù)據(jù)看作關(guān)于路段的出行信息，Q的邊緣分布密度g（Q）可以表示為

第三，利用 f（θa|Q）借助前文給出的貝葉斯方法對參數(shù)θa進(jìn)行學(xué)習(xí)，學(xué)習(xí)參數(shù)θ的所有可能取值，即計(jì)算后驗(yàn)分布；后驗(yàn)概率受到先驗(yàn)和信息的雙重影響，定義不同先驗(yàn)權(quán)重（p=priors）表示先驗(yàn)概率對后驗(yàn)概率的影響強(qiáng)度.

第四，根據(jù)參數(shù)學(xué)習(xí)得到的后驗(yàn)分布結(jié)合路段先驗(yàn)，加權(quán)平均得到學(xué)習(xí)后路段屬性，編制路段懲罰算法MATLAB程序，模擬駕駛者的出行路徑選擇.

第五，道路網(wǎng)絡(luò)級聯(lián)失效的演變：駕駛者的出行選擇改變了路段負(fù)載La，受路段負(fù)載容限的影響，部分路段產(chǎn)生失效，失效路段負(fù)載平均分配到相鄰路段，可能造成相鄰路段失效，隨著失效范圍的擴(kuò)散，產(chǎn)生級聯(lián)失效.失效路段負(fù)載重分配（見圖1）做如下定義：

當(dāng)某條路段xa上的負(fù)載超出其負(fù)載容限 ηa時(shí)，該路段失效，xa的額外負(fù)載將由其未失效的最近相鄰路段 xb承擔(dān)， xb≠xa∈X：

式中 L′b——負(fù)載重新分配后路段 xb的負(fù)載；

ΔLa——路段xa失效產(chǎn)生的額外負(fù)載；

Ea——路段xa的入度.

圖1 失效路段負(fù)載重分配Fig.1 The load redistribution of failure road

4 算例模擬

4.1 已知條件

為了便于分析，給定如圖2所示的道路網(wǎng)絡(luò)部分路段，根據(jù)實(shí)驗(yàn)網(wǎng)絡(luò)，編制MATLAB程序生成貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖，如圖3所示.

圖2 實(shí)驗(yàn)道路網(wǎng)絡(luò)Fig.2 Experimental road network

圖3 生成的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.3 Generated Bayesian network structure

給出貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的知識（感知路段平均行程時(shí)間）和先驗(yàn)信息（駕駛者感知的路段行程時(shí)間的可靠性）如表1和表2所示.

表1 駕駛者出行知識Table 1 Travel knowledge of driver

表2 駕駛者先驗(yàn)信息Table 2 Prior information of driver

4.2 算例模擬

根據(jù)駕駛者的先驗(yàn)，運(yùn)用MATLAB7.0編制駕駛者的參數(shù)學(xué)習(xí)程序，在CPU 2.2GHZ，內(nèi)存16G的計(jì)算機(jī)上計(jì)算得出了參數(shù)在不同出行信息量（nsamples）和不同先驗(yàn)權(quán)重(p=priors)下的學(xué)習(xí)結(jié)果，如圖4-圖6所示.

圖4 p=1路段屬性值變化Fig.4 The property values vary of links whenp=1

圖5 p=3路段屬性值變化Fig.5 The property values vary of links whenp=3

圖6 p=5路段屬性值變化Fig.6 The property values vary of links whenp=5

圖4-圖6顯示了不同先驗(yàn)權(quán)重和出行信息量影響下，駕駛者感知的路段屬性與先前知識的區(qū)別.通過比較發(fā)現(xiàn)，當(dāng)駕駛者受先前出行經(jīng)驗(yàn)影響較小即p取較小值時(shí)，隨著出行信息量的增加，對路段屬性的感知在開始階段會有較大波動，即出行信息量的增加會使駕駛者做出與出行知識不同的路段選擇，尤其是在開始和即將結(jié)束路段較為明顯，如 p=1時(shí)屬性值變化較大的路段有x2至x8、以及x15至x18，其余路段屬性值變化較小，這些路段屬性與先前相比出現(xiàn)了較大波動，因此在實(shí)際道路網(wǎng)絡(luò)中應(yīng)加強(qiáng)對這些路段交通流的誘導(dǎo)和管理；而當(dāng)p值較大時(shí)，駕駛者大多根據(jù)以往出行經(jīng)驗(yàn)做出路段選擇，此時(shí)出行信息量雖然增加，但是大多數(shù)路段屬性值的變化較小，反映了駕駛者較相信自己先前出行知識.

根據(jù)級聯(lián)失效模型，以及貝葉斯網(wǎng)絡(luò)推理，模擬道路網(wǎng)絡(luò)在不同先驗(yàn)權(quán)重，以及不同信息量條件下的級聯(lián)失效演變過程，設(shè)定懲罰參數(shù)取值為0.15，得到圖7-圖9.

圖7 p=1時(shí)，Ω與namples關(guān)系Fig.7 The relationship betweenΩandnsampleswhenp=1

圖8 p=3時(shí)，Ω與namples關(guān)系Fig.8 The relationship betweenΩandnsampleswhenp=3

圖9 p=5時(shí)，Ω與namples關(guān)系Fig.9 The relationship betweenΩandnsampleswhenp=5

圖7-圖9反映了不同出行信息量條件下，經(jīng)過貝葉斯網(wǎng)絡(luò)推理后，出行引起的道路網(wǎng)絡(luò)級聯(lián)失效損害程度與只根據(jù)出行知識出行引起的損害程度之間的關(guān)系.在開始階段經(jīng)過兩次迭代后，級聯(lián)失效損害程度較低；p=1時(shí)，經(jīng)過開始出行之后，隨著信息量的增加，駕駛者出行造成級聯(lián)失效損害程度會迅速降低，經(jīng)過兩次迭代之后，nsamples=60引起的網(wǎng)絡(luò)級聯(lián)失效損害程度遠(yuǎn)小于i=1、i=2和nsamples=20、nsamples=40，說明駕駛者出行受到信息量增加的影響，出行選擇更加合理，造成網(wǎng)絡(luò)級聯(lián)失效損害程度更小.

當(dāng)先驗(yàn)權(quán)重p=3時(shí)，經(jīng)過三次迭代之后，隨著信息量的增加，級聯(lián)失效損害程度Ω會降低；但是與p=1時(shí)相比，nsamples=20時(shí)Ω會短時(shí)間內(nèi)迅速增加，經(jīng)過一段平緩變化后繼續(xù)增加，但是增速變緩；nsamples=60時(shí)，雖然信息量增加，但是受到先驗(yàn)權(quán)重的增加，此時(shí)經(jīng)過兩次迭代Ω緩慢增加；因此，整個(gè)迭代過程反映了先驗(yàn)權(quán)重的增加會造成網(wǎng)絡(luò)級聯(lián)失效損害程度的增加，但是增加出行信息量可以有效緩解損害程度.

當(dāng)先驗(yàn)權(quán)重p=5時(shí)，開始兩次迭代階段信息量的變化對Ω的影響是相同的，說明先驗(yàn)權(quán)重較大時(shí)，駕駛者的選擇基本不受信息量影響，但此時(shí)Ω變化較小；當(dāng)nsamples=40時(shí)，經(jīng)過五次迭代，對網(wǎng)絡(luò)造成的破壞大于 nsamples=20和nsamples=60；該過程說明當(dāng)先驗(yàn)權(quán)重較大時(shí)，需要對nsamples進(jìn)行控制，避免提供不適當(dāng)?shù)男畔⒘繉︸{駛者的選擇產(chǎn)生負(fù)面影響，造成網(wǎng)絡(luò)級聯(lián)失效損害程度增加.

5 研究結(jié)論

道路網(wǎng)絡(luò)級聯(lián)失效的機(jī)理和特征與其它復(fù)雜網(wǎng)絡(luò)相比有其特殊性，本文以貝葉斯網(wǎng)絡(luò)推理方法為基礎(chǔ)，對道路網(wǎng)絡(luò)級聯(lián)失效進(jìn)行了研究.研究發(fā)現(xiàn)，基于貝葉斯網(wǎng)絡(luò)推理的道路網(wǎng)絡(luò)級聯(lián)失效演變，并不是一定隨著出行信息量的增加就可以降低網(wǎng)絡(luò)級聯(lián)失效，而是同時(shí)受到先驗(yàn)的影響，兩種因素共同影響著駕駛者的路段選擇，進(jìn)而影響路段負(fù)載的變化；通過算例模擬，并對比不同仿真結(jié)果表明，當(dāng)貝葉斯網(wǎng)絡(luò)推理中先驗(yàn)權(quán)重小于某值時(shí)，隨著出行信息量的增加，道路網(wǎng)絡(luò)級聯(lián)失效損害程度迅速降低；當(dāng)權(quán)重大于某值時(shí)，隨著出行信息量的增加，級聯(lián)失效損害程度出現(xiàn)階段性跳躍變化，文中對這種變化進(jìn)行了詳細(xì)研究.對于現(xiàn)實(shí)道路網(wǎng)絡(luò)來說，如何確定先驗(yàn)權(quán)重值與信息量變化之間臨界值，以及如何利用它們之間的關(guān)系，誘導(dǎo)交通量以降低級聯(lián)失效的產(chǎn)生，將是今后需要研究的一個(gè)問題.

［1］ Cao X B，Cheng H，Du W B，et al.Improving the network robustness against cascading failures by adding links［J］.Chaos，Solitons&Fractals，2013（57）：35-40.

［2］ 尹洪英，權(quán)小峰.交通運(yùn)輸網(wǎng)絡(luò)級聯(lián)失效影響規(guī)律及影響范圍［J］.系統(tǒng)管理學(xué)報(bào)，2013，22（6）：869-875.［YIN H Y，QUAN X F.The cascading influence law and influence scope of a failure in transportation networks［J］.Journal of Systems&Management，2013，22（6）：869-875.］

［3］ Yakup Koc，Martijn Warnier，Piet Van Mieghem，et al. The impact of the topology on cascading failures in a power grid model［J］.Physica A 402，2014：169-179.

［4］ 陸化普，黃海軍.交通規(guī)劃理論研究前沿［M］.清華大學(xué)出版社，2007，4.［LU H P，HUANG H J.Theoretical research frontiers in transportation planning［M］. Tsinghua University Press，2007，4.］

［5］ 張迎新，陳超，徐成濤，等.指揮控制網(wǎng)絡(luò)級聯(lián)失效模型研究［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3245-3248.［ZHANG Y X，CHEN C，XU C T，et al.Research on cascading failures model for command and controlnetworks［J］.Application Research of Computers，2011，28（9）：3245-3248.］

［6］ 李勇，譚躍進(jìn)，吳俊.基于任務(wù)時(shí)間約束的物流保障網(wǎng)絡(luò)級聯(lián)失效抗毀性建模與分析［J］.系統(tǒng)工程，2009，27（5）：7-11.［LI Y，TAN Y J，WU J.Modeling and analysis of cascading invulnerability of logistics support networks based on task-time constraints［J］. Systems Engineering，2009，27（5）：7-11.］

［7］ 謝豐，程蘇琦，陳冬青，等.基于級聯(lián)失效的復(fù)雜網(wǎng)絡(luò)抗毀性［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，51（10）：1252-1257.［XIE F，CHENG S Q，CHEN D Q，et al.Cascade-based attack vulnerability in complex networks［J］.Tsinghua University（Sci&Tech），2011，51（10）；1252-1257.］

［8］ L C Freeman.A set of measures of centrality based upon betweenness［J］.Sociometry，1997，40：35-41.

［9］ 李曉毅，徐兆棣，孫笑微.貝葉斯網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)研究［J］.沈陽農(nóng)業(yè)大學(xué)學(xué)報(bào)，2007，38（1）：125-128.［LI X Y，XU Z D，SUN X W.Study on parameter learning of bayesian network［J］.Journal of Shenyang Agricultural University.2007，38（1）：125-128.］

［10］史忠值.高級人工智能［M］.北京：科學(xué)出版社，2006，9.［SHI Z Z.Advanced artificial intelligence［M］. BeiJing：Science Press，2006，9.］

Cascading Failures Simulation of Road Networks Based on Bayesian Network Inference

LIU Xin-quana,b,c
(a.Key Laboratory of Environment Change and Resources Use in Beibu Gulf；b.Guangxi Key Laboratory of Earth Surface Processes and Intelligent Simulation；c.College of Economics and Management,Guangxi Teachers Education University, Nanning 530001,China)

The characteristics of road networks cascading failures are studied to other complex networks. The evolution of mechanism and process of road networks cascading failures are studied by integrating travel prior experience and travel information based on Bayesian network inference.The Bayesian network structure of road network is generated by MATLAB program.The driver's perception of road properties change is learned based on the MATLAB program of Bayesian network parameter learning.We design the simulation algorithms and simulate the effects of different travel prior experiences and travel information by Bayesian network inference to the road network properties and cascading failures.The results show that Bayesian network inference can better reflect the quantitative impact of link choice on road network cascading failures.The research provides new idea and method for the study of cascading failures.

traffic engineering;cascading failures；Bayesian network inference；road network；simulation

1009-6744（2015）02-0210-06

U491

A

2014-10-16

2015-01-08 錄用日期：2015-03-03

國家自然科學(xué)基金（71462005）；廣西高?？茖W(xué)技術(shù)研究（2013YB145）；廣西哲學(xué)社會科學(xué)規(guī)劃（13FGL010）；北部灣環(huán)境演變與資源利用教育部重點(diǎn)實(shí)驗(yàn)室系統(tǒng)基金（2014BGERLXT17）；高等學(xué)?！皩I(yè)綜合改革試點(diǎn)”（ZG0429）.

劉新全（1979-），男，河北衡水人，副教授，博士，碩士生導(dǎo)師. *通信作者：gxsfxy80@163.com