1、系統的有效貝葉斯網絡模型貝葉斯網絡在建立系統性能的概率論模型時是一個方便的工具，其方便性尤其體現在當 需要根據觀測信息提升系統或其組分的穩定性的情況下。在本文中，研究了以最小鏈接集或 者最小割集定義的系統性能的BN結構模型。標準BN結構把系統節點定義為其組成成分或 最小鏈接/割集的子節點，從而會導致收斂結構，這種結構不利于計算，并且可能會嚴重阻 礙BN在實際系統中的應用。本文發展了一套系統化的方法，它所創造的鏈狀BN結構比標 準結構的計算效率高幾個數量級，對于計算存儲量尤為如此。這一構想運用了整數最優算法 以確定最有效的BN結構。一些應用實例論證了所提方法并且量化了獲得的計算優勢。引言工程決策

2、經常涉及對正在演化和具有不確定信息的系統狀態的概率論評估。比如說，在 一次自然災害，比如說影響了一個城市社區的一次地震過后，必須要作出關于派遣救援隊和 視察小組，繼續使用或者關閉設施，修復的優先性以及恢復服務的決定，所有這些都依賴與 對不同的基礎系統運行狀態的評估。這些評估會受到所獲得信息的強烈影響，而這些災后信 息卻具有相當高的不確定性，并且可能會隨著所觀測到的不同系統組分狀態的改變而發生迅 速的演化。另一個例子是對正在惡化的系統的操控，在這里需要依據觀察頻率和程度，以及 維持、修復和更換行為作出一些決定，然而系統未來的性能和需求仍然是不確定的。在這兩 個例子中，需要有一種方法，以更新系統狀

3、態的概率評估，因為信息，通常是不定類型，可 以通過測量、檢查以及其他對系統及其組成的觀察得到。貝葉斯網絡對于分析這類系統，尤其是當需要考慮變化不定的信息而更新系統概率模型 時是一個理想的組織架構。BN是一個包含描述隨機變量的節點和描述節點概率相關性的鏈 接的圖像模型。變量可以描述系統組分的狀態、它們的容量和需求BN為建立組分狀態之 間相關性提供了一個方便的方法，而這在大多數經典的系統可靠性分析方法之中都是相當困 難的。此外，當輸入一個或更多變量，比如說一系列組分的觀察狀態、容量和需求，根據貝 葉斯規則，信息就會通過網絡傳播并且更新其他隨機變量的分布，比如其他組分和系統的狀 態。最后，通過添加決

4、策和實用節點，BN依據最大期望效益的原則，給出一個便于作出決 策的圖表。這篇文章聚焦于發展一套使用BN為系統行為建模的系統化的方法，系統性能以他們的 最小鏈接集或者最小割集的形式定義。這篇文章中描述的方法來源于我們在為受到地震災害 影響的民用基礎設施的行為建模的工作，它尤其重視了災后風險評估和決策制定。對于這樣 的一個應用，有效的計算和近乎實時的對大型系統模型的推斷是很有必要的。此外，相比于 其他方法，比如故障樹、事件樹或者可靠性流程圖等，被考慮的系統更容易用MLS/MCS方 式來刻畫。雖然這篇文章的動機來自這個具體的應用，但是這里描述的方法可以應用于很多 問題。BN曾經被用于系統可靠性分析。

5、這些工作中的一部分以直覺的方式將系統建立為BN 模型。其他的則把故障樹，或者可靠性流程圖作為系統信息的根本來源。一些論文為相對簡 單的系統發展BN，對于這些系統，計算量不是特別關鍵。這項工作區別與先前工作的地方 在于，其定義了一種用于發展一個有效BN結構的系統化處理方式，使得在當MLS或者 MCS是系統信息的根本來源時，用于為復雜系統的可靠性建立模型。這一方法在處理具有 拓撲性質的系統時尤為有用，在這樣的系統里，系統的分解通常是通過MLS或者MCS來 完成的。盡管其他的作者已經使用BN為通過可靠性流程圖拓撲定義的系統建立模型，但卻 沒有做出系統化的嘗試以使得BN結構達到最優化，在處理大型、多狀

6、態系統時尤為如此。 傳統的BN模型在尺寸和密度上都會隨著系統尺寸的增加而迅速增加，所以即便是對于中等 尺寸的系統，計算和存儲的需求都會使得模型變得不可行，特別是在使用具有多狀態節點的 精確推算算法時。考慮到這個缺點，在本文中我們針對二元和多元狀態組分，發展了一套生 成有效BN拓撲的方法。發展了一套離散最優化算法以最小化BN密度，從而可以節約幾個 數量級的計算時間和存儲容量。本文開篇對BN作出簡要的介紹。介紹被限定在對文章的后續內容有意義的幾個方面。 其次，陳述了為具有二元組分的串聯和并聯系統建模的有效貝葉斯網絡構想。這些構想然后 被拓展到具有二元和多元狀態組分的一般性系統。為了自動構建有效貝葉

7、斯網絡結構，一個 二元整數最優化問題被明確的表述出來。此外，描述了兩個啟發式的改進方案以減小最優化 問題的尺寸。最后列出了論述所提方法及其有效性的幾個例子。貝葉斯網絡簡介一個貝葉斯網絡可以用包括一組描述隨機變量的節點和一組描述概率依賴性的鏈接的 定向非周期性圖表來描述。本文中，我們局限與處理這樣的BN，其中所有的隨機變量都是 離散的；對具有連續性隨機變量的BN感興趣的讀者可以參考Langseth。考慮圖1中的簡單 BN。從X1和X2到X3的定向鏈接表示X3的分布是基于X1和X3定義的。在BN術語中， 隨機變量X3稱為隨機變量X1和X2的子節點，而后者稱為X3的父節點。類似的，X4是 X1的子節

8、點，而X5是X4的子節點。每一個節點與一組彼此獨立且同時明確的狀態相聯系， 與離散隨機變量的結局空間相對應。每個節點都帶有一個條件概率表（CPT），提供了隨機 變量的條件概率函數。根節點沒有父節點，附帶一個邊緣概率表。Fig. r A simple BN.BN中隨機變量的聯合分布以條件分布的乘積形式給出，例如:p（xnx2p.,Xfl）= n 口（珀伊敏招）-（1）其中Pa（Xi）是節點Xi的父集合，p是Xi的CPT，n是BN中隨機變量（節點）的數目。 因此，對于圖1中的BN，聯合概率分布函數為：=f 八，（2）BN在回答當觀察到一個或多個變量時的概率性疑問時很有用處。例如，假設在圖1中 的B

9、N中，X3=x3,X4=x4，需要計算條件分布p（x2|x3,x4）。計算后面的分布時，首先要邊緣化 （2）中的聯合分布，以獲得變量子集的聯合分布：Jp(X2A34)=(為 次5)(3)p(x3tx4) = P(X1，,X5)(4)#1 .也.均要計算的條件分布則為p(x2lx3,x4)=p(x2,x3,x4)/p(x3,x4)。雖然通過這種方法可能獲得更 新的分布，但對非平庸的BN而言這卻不是一個有效的計算方法。一些用于在BN中作出準 確和近似概率推算的有效算法已經被發展起來。這里列出了準確推算算法的一般性原則，以 強調發展有效BN拓撲的必要性。BN的有效性來源于將聯合分布分解成局部條件分布

10、，就像在等式(2)中的例子里一樣。 當對聯合分布求和時，類似于等式(3)和(4)，并沒有利用分解，且計算效率較低。然而，通 過以乘積的形式寫下聯合分布，就有可能根據他們的分布和交換性質，重新安排這些求和和 乘積操作。例如，等式(3)可以寫成：p(X2 g g) =、p (x5|x4)p(x4|x1Jp(x3| Xi tx2 )p(為)P的)=P(X2) Wp (陽 I Xi)P (也 I Xi) P(為)fp (*51 &)(5)求和操作可以被理解成節點的消除。因為計算時從右往左進行的，等式(5)對應于X5的 消除，接著是X1的消除。很明顯，解;5)的第二行比解第一行有效，因為求和是在較小的區

11、 域中進行的。遍及X5的求和只在X4和X5區域中(且在實際上可以被忽略，因為它的結 果是1)。遍及X1的求和是在XI、X2、X3和X4區域中，為此有必要建立一個表(稱為 potential)，表中的條目數量等于這些變量狀態數的乘積。通常情況下，potential的尺寸決定 了推算算法的效率。Potentials，也即推算算法的效率，取決于節點消除的順序。計算上存在著最優消除序列， 所有這些序列都會導致相同的域集，例如在這一過程中產生的potential的域集都是相同的。 與最優消除序列對應的域叫做clique。與這些clique相關的potential的總尺寸能很好的反應 出在貝葉斯網絡中進行

12、推算所需要的計算量，在本文中被用于評估和比較不同BN系統架構 的效率。雖然所有的精確推算算法都旨在尋找最優節點消除順序，但是他們遵循不同的方式。特 別值得一提的是，有些算法旨在為一個具體的推算任務最優化消除，而其他的算法，比如說 交叉樹算法，則具有普適性。利用后者，部分計算可以被重新利用。我們感興趣的是一般性 的推算應用。這些算法中的一部分已經在現有的軟件應用程序中得到了使用，為在復雜貝葉 斯網絡中進行推算帶來了便利。雖然這篇文章集中于提高精確推算算法的計算效率，但是這里所發展的方法對于通過減 小存儲的CPT尺寸的近似算法而言同樣有用。就像Nielsen等談到的，在當BN模型的確定 性部分可以

13、用一個布爾型函數描述時，高級的布爾計算可以用于提高精確算法的運行效率。 這樣一種方法可以用于進一步提高我們通過拓撲最優化得到的BN模型的計算效率。通過貝葉斯網絡為系統性能建立模型考慮一個具有Nc個組分的系統，第i個組分具有ni個離散狀態。系統的不同狀態的個數從而是1 - 。我們把通過組分狀態直接定義系統狀態的BN formulation稱為naiveBN formulation。圖2展示了這樣的一種BN,其中節點Ci定義的是第i個組分的狀態，節點 Ssys定義的是系統的狀態。如果系統有Ns個離散狀態，那么與該系統節點相關聯的CPT 就具有Ns*個條目。雖然這種formulation曾經也被使用

14、，但是對于一個系統，哪 怕是只具有中等數量組分和組分狀態的系統，CPT的尺寸都會變得相當大以至于BN在計算 上變得很棘手。很明顯，我們需要一種更加有效的BN架構。Fig. 2. Naive BN formulation.作為上述naive方式的一種替代，在這篇文章中我們描述了另外四種BN formulation0 前面兩種利用了最小鏈接集和最小割集，以處理具有二元組分的系統，但是利用了和在naive formulation中相同的收斂結構。可以看出，MCS架構對于具有多元狀態組分的一類系統同 樣是適用的。我們接著又發展了兩種架構，它們對具有二元狀態的系統使用了 MCS/MLS， 但是導致了遠比

15、計算目標有效的多的鏈狀BN拓撲結構。這些架構首先用在串并聯系統上， 然后推廣到一般性的系統。這些有效的MCS架構對于具有多元狀態組分的一類系統同樣是 適用的。使用最小鏈接集和割集的BN系統模型4.1二元組分和系統考慮一個具有二元組分的系統和系統狀態，例如存活/失敗狀態。最小鏈接集(MLS)是組 分的最小集合，其節點存活狀態組成了系統的存活狀態。最小鏈接集BN架構在組分和系統 節點間引入了中間節點，其描述了 MLS的狀態，如圖3所示。Fig. 3. MLS formuhtion.TorresToledano和Sucar用這樣的一種BN架構為系統性能建模，盡管其方法比我們這 里使用的方法缺少規范性

16、和一般性。MLS節點的二元狀態被定義成，只有當它的所有的組 分存活時才處于存活狀態，否則處于失敗狀態。當任意一個MLS節點存活時，系統節點存 活。用Nmls表示系統MLS的數量，NMLSi表示在第i個MLS中組分的數量。第i個MLS 節點的CPT大小是2NMLS,i+i，系統節點cPt的大小是2Nmls+i。很明顯，當MLS數量較大 時，與系統節點關聯的CPT尺寸也會變大。對于MLS節點，當組分數量較大時也會出現類 似的問題。與MLS架構對應的是最小割集BN架構。MCS是組分的最小集合，其節點的失敗組成 了系統的死亡。在這種架構中，系統節點是代表MCS節點的子節點，每一個MCS節點是 代表其組

17、分狀態節點的子節點，如圖4所示。Fig. 4. MCS fbrmulAtig系統節點是所有MCS節點的串聯系統（例如，如果至少有一個MCS節點處于失敗狀 態，那么系統節點就處于失敗狀態），然而每一個MCS都是其父節點的并聯系統（例如， 所有的組分必須處于失敗狀態時，MCS節點才會處于失敗狀態）。類似于MLS架構，處于 這種架構中的CPT會隨著MCS數量的增加，且/或MCS中組分的數量（用NMCSi表示第i 個MCS）的增加而變大。4.2具有多狀態組分的多狀態流系統具有多狀態組分的多狀態流系統可以通過應用最大流最小割理論來建立 MCS BN formulation模型。我們不知道存在允許將MLS

18、架構應該用到多狀態流系統中的一個類似的 定理。考慮一個描述從源節點到漏節點流動的系統，假定其MCS組分是二元的。系統的每一 個組分都具有一個流容量，其取值被離散化成一個特定狀態集合，例如最大容量的0%，25%， 50%，75%和100%。用Capi表示組分i的容量狀態。對于一個具有定向流的分布式組分， 我們考慮割線上從源側到漏側的容量。為每一個MCS指定一個容量值，其數值等于組分容 量之和。最大流最小割線定理指出，從源到漏的最大流容量等于所有MCS中的最小值，例 如系統的瓶頸。這個定理允許將MCS BN架構應用到多狀態問題中，而不需要在當假設組 分是二元時，改變所創建的BN的拓撲性。只需要根據

19、組分，MCS或者系統容量水平，增 加與每個BN節點關聯的狀態數量，并用算術表示式而不是布爾邏輯關系去定義節點之間的 關系，就像下圖所描述的那樣。Fig* 5. Equivalent BNs with (a) converging structure and (b) chain structure.SEHE/U &mJ 3N23bm -sop Converging,.Chain Structure4Number of Components (NJNumber of Components (NJFig. 6. Computational demands of system BNs with con

20、verging and chain topologies when components have (a) 2 states and (b) 5 states.圖4中的節點q被修改以用于根據每一個組分的容量水平描述多元狀態。如果組分具 有連續容量狀態，那么可能容量的范圍必須被離散化成幾個小的間隔；在這種情況下，節點 Ci描述的是一個間隔節點。類似的，節點MCSi具有多個狀態，它們所具有的容量值通過 下面的關系式來定義：SmcL f 知Cj w M*系統節點的容量可以通過以下關系獲得：。叩曄= min CapMCS.（7）1日1N枕仁時當Ci是間隔節點時，MCSi和Ssys也是間隔節點。在創建后

21、者的CPT時，這些節點的 間隔必須通過考慮從（6）和（7）式中獲的得可能容量值的整個范圍來選擇。關于間隔節點 的CPT計算的更多細節在Bensi等人的文章中給出。5.有效的BN系統模型5.1.動機在前面章節中描述的MLS和MCS架構都會導致收斂的BN結構。一般而言，節點成 鏈狀排列的BN結構比收斂的BN結構更加有效。正如我們稍后會介紹的，在圖5中的兩個 BN結構表示的是同一個系統。圖5a中是一個類似于前面章節表示的收斂結構，而圖5b表 示的是鏈狀結構。在兩種BN中，組分之間的依賴關系通過引入一個共同需求節點D來體 現。稍后將會在本節中的圖5b中給出構建BN的正式描述。圖6比較了圖5中當系統組分

22、分別具有2個和5個狀態時，收斂和鏈狀結構的BN計算 量，該量以總clique尺寸表示。隨著組分數量的增加，收斂結構的BN計算量呈指數增加， 而鏈狀BN的計算量則呈線性增加。然而，對于二元組分系統，當組分數量小于4時，收斂 結構比鏈狀結構更加有效。因此，當圖5a中系統節點具有3個以上的父節點時（例如，連 續組分），用圖5b中的方式建模會更加有利。與推算關聯的計算量不僅受到系統尺寸和結構的影響，也會受到組分節點的共同父節點 的數量影響。圖7比較了與具有1，2或者3個共同父需求節點二元組分的收斂和鏈狀BN 拓撲結構相關聯的計算量。可以看出，計算量會隨著共同父節點數量的增加而增加。然而， 隨著組分數量

23、的增加，鏈狀結構相比于收斂結構仍顯得有利。同時注意到，隨著共同需求節 點數量的增加，轉折點，即鏈狀結構比收斂結構有利的點，會稍微的上移。對于三個共同需 求節點的情況，當具5個或更多組分時，鏈狀結構更為有效，而對于一個共同需求節點的情 況，當具有4個或者更多組分時更為有效。700500 一-Chain3 Common Demand Modes心N第一 mol Converging 3 Cummun Demand Nodes Converging, 2 Common Demand Nodes- - Chairs 2 Common Demand Medes100Chain. 1 Common Dem

24、and NodesNumber of Components (NJFig. 7. Comparison uf compurational demands associated with converging and chain BN topologies for binary nodes with one or more common parent demand nodes.5.2.具有二元組分的串并聯系統我們現在來描述具有二元組分的系統如何用具有鏈狀拓撲結構的BN來建立模型。定義 存活路徑序列（SPS）為一系列的事件，與一個MLS相對應，在后者中，序列中的最后一 個事件指出是否MLS中所有的

25、組分都處于存活狀態。注意到術語“序列”并不含有任何實 時的含義。串聯系統具有一個MLS，而并聯系統具有Nc個MLS。相應的一個串聯系統具 有一個SPS，而一個并聯系統具有Nc個SPS。SPS由一系列的存活路徑事件（SPE）組成， 每一個存活路徑事件都與一個組分相關聯，描述了序列中直到該事件的序列狀態。在貝葉斯 網絡中，SPE用標記為Esi的節點表示，下標i表示與第i個組分關聯。Esi的狀態被定義成：s.i = 1 if Egi） = 1 Cl g = 1）=0 otherwise（8）其中Espai定義為Esi的父SPE節點的狀態。Esi=1表示節點處于存活狀態而Esi=0表 示失敗狀態（在本

26、文中我們始終使用這種布爾型表述）。因此，對于一個串聯系統，貝葉斯 架構采用圖8a中所示的形式。Fig. 8. BN using SPEs to model performance of (a) series system, (b) parallel system.節點Es1的狀態等于節點C1的狀態。Es2僅當Es1和C2都處于存活狀態時才處于存活狀 態。在這種模式下，EsNc當且僅當EsNc1和CNc都處于存活狀態時才處于存活狀態。因此， EsNc的狀態描述了整個,SPS的狀態(表明是否MLS中的所有組分都處于存活狀態)，從而 也描述了這個串聯系統的狀態。節點Ssys的狀態就等于圖8中EsNc

27、的狀態。并聯系統中每個組分都對應一個SPS。由此得到的貝葉斯網絡見圖8b。系統節點表示 當任意一個節點Esi存活時，系統就存活。類似于naive formulation，與系統節點相關的CPT 大小的指數增加致使該貝葉斯網絡在當組分數量很大時變得難以處理。將失敗路徑序列(FPS)定義為一連串的事件，與一個MCS相對應。序列中的終點事 件表明是否MCS中的所有組分都處于失敗狀態。在一個串聯系統中存在Nc個FPS，每一 個都與一個組分對應。在一個并聯系統中只有一個MCS，因而也只有一個FPS。一個FPS 由一連串FPE組成，其中每個FPE與一個組分關聯，并給出序列直到那個事件的狀態。令 Efi是貝

28、葉斯網絡中表示與節點i關聯的FPE的節點。Efi的狀態被定義為：與E = 0 if E/.pm) o n Q = 0=1 otherwise(9)其中Ef,Pa(定義為Efi的父FPE節點的狀態。對于一個串聯系統，使用FPS的BN架構 采用如圖9a的形式，它,具有我們不想要的收斂結構。對于一個并聯系統，BN架構采取圖 9b所示的鏈狀形式。這些發現表明SPS和FPS架構的結合可能被用于有效的建立一般系統 的模型。這種方法將會在下節中介紹。abFig. 9. BN using FPEs to model performance of (a) series system and (b) parall

29、el system.5.3具有二元組分狀態的一般性系統MLS是其組成成分的串聯系統。因此，采用上述的架構，系統的每一個MLS都可以用 一個SPS描述，從而導致鏈狀BN結構。考慮在圖10a中的范例系統，其具有四個MLS： MLS1=1，7, 8,MLS2=2, 7, 8,MLS3=3,7,8和 MLS4=4, 5, 6, 7, 8。在圖 10b 中， 每個MLS被建立為單獨的一個SPS模型。SPE，Esij在每個SPS中用一個與關聯的組分i和 關聯的MLSj對應的角標編號。JFig- ID. (a) ExjfLipie syscem and (b) efficienr Mis fcuniuhTi

30、ovi with diswna SFSi.具有同一個組分的SPE之間的依賴關系通過一個共同的父節點建模。當任意一個SPS 的終端節點處于存活狀態時，系統節點存活。作為參照，其中的MLS按鏈狀結構排列的BN 架構被稱為有效的MLS BN架構。相似的邏輯構建出一個有效的MCS BN架構。當在貝葉斯網絡中執行推斷時，具有相同組分的SPE和FPE之間的依賴關系會增加計 算量。通過合并出現在多個SPS/FPS中的共同的SPE/FPE，貝葉斯網絡中節點和鏈接的數 量會減少，從而計算量也會減少。在范例系統中，組分7和8出現在所有的SPS里。我們 利用這一發現，并只引入一個與這些組分關聯的SPE的instan

31、ce，得到的BN如圖11a所示。Fig-11. Efficient MLS formulations for the example system with coalesced SPEs associated with components 7 and 8 using (a) a converging structure (b) a chain structure.注意到這種結構也會避免系統節點的收斂結構。它確實可以如此，但是要求有一個收斂的 SPE節點(圖11a中的節點Es7)。像這樣具有多個SPE作為父輩的SPE節點可以用如下的 布爾關系描述：if uEgh = i門G = 1)(10=0

32、 otherwise圖11a中引入的一個值得注意的變化是:每個SPE節點的上標現在代表SPE的instance， 而以前表示MLS的編號。例如，當有多個SPE與共同的組分關聯時，它們就作為SPE的不 同instance被識別出來，并通過這些上標區分。對于這個示例系統，因為每一個組分至于一 個SPE關聯，從而圖11a中的所有上標都是1。在下文中我們丟掉上標，除非有必要特別說 明。注意到圖11a中節點Es7的收斂結構，因為需要用它來代表一個并聯子系統。由于并聯 系統可以用FPE鏈非常理想的描述，從而這個收斂結構可以通過用鏈狀排列的FPE節點代 替與節點1,2,3關聯的SPE節點來改進，從而導致了圖

33、11b中的BN結構。具有SPE作為父節點的FPE的定義遵從原始定義：Ef= O if 切,w =。門E$p堀=0 C G =。(11)=1 otherwise盡管示例系統中的三個BN模型都被稱為是有效的MLS架構，但是事實上它們的效率 卻大不相同。圖10b中BN模型的總clique大小是224，圖11a中是108，圖11b中的值則 是64。這表明當合并在不同SPS中的多個SPE的instance時可以提高計算效率。迄今為止，一個SPS中的SPE(FPS中的FPE)，與一個特定的MLS(MCS)對應，是按 一種隨意選擇的順序排列的。對于復雜系統，在SPS中的SPE的排列可能強烈的影響我們 合并不

34、同SPS中SPE的多重instance的能力。SPE出現的順序可以被優化，以至于在盡可 能多的SPS中的SPE可以被合并。正如早先說明的，這會減少在BN中節點和鏈接的數量。 這個優化問題將在下面描述。簡潔起見，我們只給出了使用SPS的架構；相對的架構同樣 適用于FPS。因為我們的焦點只是在SPE上，從而并沒有考慮組合SPE和FPE的可能性。 這樣的一種組合可以當做是在最優化SPE之后的額外步驟，與圖11b中的例子類似。6.生存路徑事件的最佳序列本節的目標是規范化對一個一般性的系統，尋找SPS中SPE最優排序的問題。令 L(im,jn)=1表示存在從節點Es,im到節點Es,jn的直接連接，L=

35、0表示不存在這樣一個連接， 其中i和j是組分編號，m和n是BN中表示這些SPE節點instance的編號。同樣的，令Cim=1 表示在代表組分i的節點和節點Esim之間存在直接連接，Sim=1表示在Esim和系統節點之 間存在直接連接。在最優化問題中的決策變量是SPE節點之間的連接，L(im,jn)。這種優化 問題的架構假定只使用SPE節點以及系統節點處具有收斂結構。為了進一步增加BN的計 算效率，在系統中或者任意其他節點處的收斂結構可以通過使用FPE而被鏈狀結構取代。采用BN中鏈接數量作為當需要進行推斷時描述計算量的替代物，最優化問題的目標就 是最小化在BN中的鏈接數。這可以用下式來描述:、

36、虬 Nc M NfNc M虬 Njnun(12)EEEsrf = lj=1 m = ln=1(= 1 m = 1 t = 1 m = 1其中NI是任意SPE的instance個數的最大值。我們想要NI盡可能的小，但是它的數 值在求解優化問題之前是未知的。因此，一個迭代程序被用于尋找使得最優化問題存在可行 解的最小Ni。為了確保BN結構能夠以在前面章節中描述的方式，利用SPE來表示系統， 一系列的關于最優化問題的限制被提了出來。第一，每一個SPE節點必須有一個從相應組分節點指向它的鏈接。具體來講，如果節 點Esim存在于BN中(如果決策變量指示存在一個鏈接進入或離開節點Esim時會發生)， 則C

37、im=1 (沒有鏈接進入或離開的節點可以從BN中移除)。從數學上說，這被規范化為一 個對最優化問題的限制，寫成下式：第二，如果Esim存在并沒有其他SPE節點作為子節點，那么它就是SPS中的一個終端 節點。這樣一個節點必須有一個指向系統節點的鏈接，例如Sim=1。這導致對最優化問題的 第二個限制：一些有名的技術可以用于為“如果-那么”這類問題建立模型，正如在前兩個等式中的 那樣，為數值優化問題提出限制條件。第三，存在兩個限制條件控制BN中SPE節點的排列：(a)每一個MLS必須用一個SPS 表示；(b)不嚴格是MLS的SPS不存在。破壞第一條限制會排除一個或者更多的MLS，導 致對系統可靠性的

38、低估。破壞第二條限制會導致包含一個或者更多虛假MLS的BN，從而 會高估系統的可靠性。限制(a)要求每一個MLS被表示為一個SPS，例如，至少一個與MLS中的組分相關的 SPE的permutation必須被連接為一條鏈。令NMLSi表示MLSi中的組分的數量。對于在圖10a 中的示例系統，我們有NmcS1=NmcS2=NmcS3=3,NmCS4=5。令Pi表示permutation的集合，且 沒有替換掉MLSi中組分的序號，定義一.，？，甘作為其第a個成員。 舉例來說，對于圖10a中的系統，我們有P1=p11=(1,7,8),p12=(1,8,7),p13=(8,1,7),p14=(7,1,8

39、),p15=(7,8,1),p16=(8,7,1).其次，令Qi表示置換集，其中NMCSi被從序數集1,.NI中排除出去。并定義 qib=qib1,qib2,.qibNMLSi作為其第b個成員。使用圖10a中的例子，假設NI=2，我們有 Q1=q11=(1,1,1),q12=1：1,2,q13=(1,2,1), q14=(1,2,2),q15=(2,1,1),q16=(2,1,2),q17=(2,2,1),q18=(2,2,2)。注意到 Pi 具有 Nmls個成員， 然而Qi具有NINMLSi個成員。定義集合riab=ri1ab,ri1ab,.riNMLSiab，其結合了 pia和qib的元素

40、。具體來說，riab包 括了 pia中的組分序號，其上標則來源于qib。對于示例系統，r111=11,71,81等。總而言之， 對于這種特殊的MLS，存在48中可能的方法來排列組分序號和instance的上標。簡便起見，我們定義:其中rilab是riab的第l個元素。Xiab=NMLSi-1只當與MLSi中的組分對應的SPE以pia 和qib表示的順序構成SPS時才成立。對于與存在于BN中的第i個MLS關聯的SPS而言，我們對來源于集合riab中的至少一個組分/instance的序號順序具有：Xiab=NMLS1。這個限 制被寫成：ImaxX Nmls.l 1% a = 1,NmlsjLfi

41、=(16)為了最優化算法的方便，這里使用不等號而不是等號。限制(b)要求BN中的每一個SPS都要與一個MLS對應。考慮圖12a中所示的BN分割。令陰影節點上：. 土一 二表示組分/instance序號的一個特定置換，這種置換導致一個有效的SPS。限制(b)必須禁止一個SPE Esj,n，對于任意的n，在任意節點處將SPS 分支，例如成為鏈中任意節點的子節點，除非組分j存在于所有先前組分都在序列中的MLS 中。Fig. 12. BN used to illustrate constraint (b).舉例來說，在圖12a中，Esj,n不能作為Es3,1的子節點存在，除非組分1,2,3和j都同時存

42、在 與MLS中。如果組分1,2,3和j不存在于一個MLS中，那么具有虛線邊緣的錯誤存活路徑就 被引入BN中。與所有有效SPS關聯的限制表示如下：|玲，=阻*1 土廿=0, Vj 1 p%L 一 崩Vi； nY L (17)進一步的，限制(b)必須禁止SPE Esj,n，對于任意n，成為在有效SPS中任一節點的父 節點，除非組分i存在于所有后續組分都在序列中的MLS中。舉例來說，在圖12b中，Esj,n 不能是Es2,1的父節點除非組分2,3,4和j都存在于一個MLS中。對所有有效SPS的第二條限 制采取如下形式：*咨=o,力：j,pp第心LSnvm, * n. L 敏 #(IS)綜合(17)和

43、(18)可以得到限制(b)，表示如下兇5 = Nm成I nE EE E m鑿垣 i m m n = U = % 明 P的#M晝N,wu N+ E EE E卬5涔=o瑚心叩苗一或兒叫4(19)限制(b)以及目標函數(其最小化可以確保在構建需要的SPS中非必須的鏈接不存在與 BN中)，禁止了在BN中形成無效的SPS。有效的MCS架構是有效MLS架構的對應物，后者中FPS鏈依據每一個MCS構建。因 此，對于構建一個FPS架構，與上述等價的優化結構被表述出來，上述的SPE需要被替換 為 FPE。上面描述的整數最優化問題要求考慮組分和instance序號的排列。因此，問題的大小會 隨著組分的數量增加而迅

44、速增加。為了克服這個困難，在本文的稍后章節中會引入一些啟發 式方法。6.1多狀態流系統的延伸(20)因為具有標準的MCS架構，通過應用最大流最小割定理，有效的MCS架構可以被用 于解決多狀態問題。BN的拓撲性不需要和二元狀態問題中使用的拓撲性有所不同，僅僅是 需要增加與每個節點關聯的狀態數量，并使用算術表達式而不是布爾關系去定義CPT。FPE 節點的狀態與容量值相關聯，后者被定義為P%=E %忠 任PE/j+C叩E即指派給節點Efi的容量值等于其父FPE節點容量值與關聯節點容量之和的最小值。因 此，每一個FPE節點的容量可以被認為是描述MCS的總運行容量。節點Ssys的容量代表 了系統的最大運

45、行水平，它是所有MCS中的最小容量，定義為|(21)6.2.實例H (di) Lnim血 nrt.mk lyriE-nn;也)irlTii.iiriil ML &M fmnnjivi miO eet SK kiK&iiiJilird will N) fiFta ihcwnn LCEiwnfflEjiiri la raaiinn .Wdfi.ZHZHZHZHZJ為了闡明采用本文所提出的有效BN結構的計算優勢，我們考慮在圖13a中由10個被 標記的組分組成的系統。在這個例子中，一個源和一個漏被默認的用兩個連接路徑連接起來。 一個連接路徑用一條實線表示，另一條則用短虛線表示。在這種結構下，系統具有三

46、個MLS： 1,2,3,4,5,6,7,8,9.組分10代表一個開關，它可以用于從默認結構轉變到一個用長虛線表 示的可選結構。這會在系統中增加4個連接路徑:1,3,10,1,4,10,2,3,10,2,4,10.因此，總 而言之，系統具有7個MLS,采用本文所提出的最優算法獲得的BN如圖13b所示,其中與 MLS5,6,7,8,9對應的SPS用陰影節點突出出來.圖13c中表示與和每個剩余MLS對應的SPS 相同BN也被類似的強調出來.與這個BN關聯的總大小是184.具有收斂結構的MLS BN的 總大小是5140,而具有naive BN結構的系統的數值為2048.當在MLS BN結構中引入中間節

47、 點以確保沒有節點具有三個以上的父節點時，總的集團大小減到804,但是大體上仍然比用有 效MLS BN拓撲所取得的數值要高.因此，經過最優化處理的BN比其他方案在計算上的有效 性高一個數量級.不僅如此，注意到節點Ssys是其四個父SPS節點的并聯系統.一個小的額外 的計算優勢可以通過將收斂結構修改為鏈狀結構實現，正如在圖11b中展示的那樣.7.有啟發意義的增加正如早先提到的,由于需要考慮到組分序號和instance的所有排列，二元最優化問題在大 小上增長迅速。為了克服這個困難，在本節中我們給出兩種啟發式方法:一種旨在減小需要考 慮的組分數量，另一種旨在減少排列的數量.其他的啟發式方法可以被發展

48、以進一步改善在本 文中描述的最優化算法的性能和可擴展性.7.1使用超組分的方法Der Kiureghian和Song引入了系統多尺度模型的想法，據此基本元素的子集被分組為 “超組分”。對單個的超組分進行分析，結果然后集中到系統層面上。超組分組成了簡單的 子系統，比如沿著系統鏈接以串聯或者并聯方式存在的組分。使用超組分可以減少組分的有 效數量，從而減少它們序號的排列數。它也有助于SPS和FPS的組合。我們再一次考慮在圖10a中的簡單系統。組分C4,C5,C6以串聯形式存在，組分C7和C8 也是這樣.我們分別用兩個超組分SC1和SC2代替這些組分的子集，如圖14所示.系統仍然具 有 4 個 MLS

49、,但是它們的組分數量減少了:1,SC2,2,SC2,3,SC2,SC1,SC2.對圖14的考察發現，組分C1,C2,C3和SC1以并聯方式存在.這些組分接下來被一個單 個的超組分取代，從而得到圖15表示的系統.現在，組分SC2和SC3以串聯方式存在,并可以被另一個超組分取代。從這種確定可以被 分組和被一個超組分取代的組分的一系列流程得到的BN如圖16所示。Fig. 16. BN constructed for system in Fig. IDa using the super component heuristic對于包含少于4個組成成分的超組分，使用了收斂結構.對于包含4個或者更多組成成分

50、 的超組分，則使用鏈狀結構.注意到在超組分中的組分不需要是連續的.舉個例子，在圖17中的系統中，組分1和4可 以被放入一個超組分，因為考慮到MLS和MCS的形成，他們具有相同的影響，似乎他們在物理 上就是以串聯方式存在的.2 、 /Source 1 4 SinkFig. 17. Example system illustrating non-contiguous components that can be combined into a super component我們現在提供一種算法，以用于進行系列性的確認和用超組分取代基本組分，或者用更 高級的超組分取代超組分集。在這個算法中的第一步是

51、構建初始關聯矩陣M0,它包括與每 個MLS(MCS)對應的行和與每個基本組分對應的列.矩陣的元素定義為：JM% = 1if component j is a member of MLS (MCS) i=0 otherwise(22)對于在圖10a中的系統，矩陣M0在圖18的頂部給出.在算法接下來的每一步中，關聯矩 陣將要通過消除與被分入超組分的組分相關的列,及創造一個描述新的超組分的行而得到更 新。令Mp表示算法的第p步關聯矩陣，其元素記為MijP.定義了兩種類型的超組分.A類超組分由若干組組分（或是以前形成的超組分）組成它們總是一起出現在一個MLS中,從不分開出現.在一個基于MLS（MCS）

52、的結構中,A類超組分 與以串聯（并聯）方式存在的組分對應.為了確認算法迭代P次的超組分，我們為每個組分j（或是以前形成的超組分）指定量mj（A,p），定義為：這個量只有當組分總是同時出現在某個MLS且從不分開出現在不同的MLS中時對于 不同的組分才是等價的.舉個例子,對于圖10a中的系統,我們有m1A0=2, m2A0=4,m3A0=8 等。具有相同mjAp的每一個組分集合可以分組以形成A類超組分.矩陣MP必須通過移除 與被分組的組分對應的列及增加代表新的超組分的列而更新到MP+1 .令SCj表示新形成的 超組分.更新的矩陣的新列的元素被定義為：M酬=1 if E k w Cfrp(24)0

53、otherwise其中Cgrpp是被分組以形成新的超組分的組分集合.我們重復這種操作直到A類的所有 超組分形成.對于圖10中的系統，使用一個MLS formulation，兩個A類超組分被確定,更新后 的矩陣M1和M如圖18中間所示.M，ML”Fig- 18. Correspondence uia trices of example system. tefore and after IdentificatiQn and formation of Class A and ass B super components.B類超組分由出現在不同MLS（MCS）中，但是相同其他組分相同集合共享這些MLS

54、的組 分組成。對于一個基于MLS（MCS）的結構，這些與并聯（串聯）排列的組分對應.為了確定算法p 次迭代的超組分，我們為每個成分j指定量mjbp，定義為：啪叫 x（25）我們可以容易的證實具有相同mjBp值的組分（或超組分）滿足上述對于B類超組分的 條件，并可以被這樣分組.作為一個例子,對于圖10a中的系統,我們有m1B2=32.矩陣Mp現在 通過移除與一被分組組分對應的列及增加對應于具有按24式定義的元素的超組分的列而更 新.因為組合的成分來自于不同的MLS（MCS）,這個過程使得矩陣的一些行為0,從而可以被移 除.對于示例系統,這個過程導致了更新的關聯矩陣M3,如圖18底部所示.以上用于

55、尋找和用A類和B類超組分替換普通組分的迭代程序將一直重復下去,直到系 統中不存在剩余的超組分.與最后一次迭代對應的矩陣Mp接著被用于對組分及需要被用于 定義最優化問題的相應的MLS或者MCS進行說明.7.2用于減少排列數量的啟發式方法回想起最優化算法考慮到成分序號和instance的所有排列.第二種啟發式方法的目的在 于丟棄這些集合的若干選定的成員.注意到如果一組組分在所有的MLS中出現，那么就沒有 必要考慮它們序號的排列情況（實際上，這樣一組組分應該被識別出來并組合成一個超組分）. 這里展示的方法識別出現在幾個（但不是全部）MLS中成分，并鎖定了它們的序號出現的順 序，因此移除riab被選定

56、的成員.這種方法可能會導致次優化的BN結構,但是當最優化問題的 尺寸超過所提供的資源處理限度時則是必須的.這種方法應該用在通過識別超組分以減少問 題的大小之后。為了便于解釋這種方法,我們用了一個示例系統來闡明這個過程的每一個步驟考慮到具 有7個MLS的任意一個系統： MLS1=1,2,3,4,MLS2=1,4,5,6,8,MLS3=1,4,7,MLS4=2,3,5,MLS5=1,5,7,MLS6=1,2,9 ,MLS7=7,9.第1步:基于組分序號在不同MLS中出現的次數為其創建一個有序列.我們稱其為O列. 對于示例系統，一個MLS中每個組分出現的次數見下表：ComponentNumber o

57、f appearances in a MLS543上表導致有序列O=1,2,4,5,7,3,9,6,8。這個序列是以指數值為基礎的。第2步：基于序列O重新對MLS中的成分排序.對于示例系統，新的MLS成分序列為：MLS1=1,2,4,3, MLS2=1,4,5,6,8, MLS3=1,4,7, MLS4=2,5,3,MLS5=1,5,7,MLS6=1,2,9,MLS7=7,9第3a步:確定MLS之間的所有成對交叉集合：Mj-j = MLS； nMLSp i = 11）=（i+1）（26）對于示例系統，我們有M1,2=M1,3=M2,3=1,4,M1,6=1,2,M3,5=1,7,M2,5=1,

58、5,M1,4=2,3,M1,5, M2,4, M2,6,M3,6, M3,7, M4,5, M4,6, M5,6, M5,7 和 M6,7 是只包含一個元素的集合,M17=M27=M34=M47=空集。第3b步:定義G作為包含元素個數大于1的特殊集合Mij的集合.對于示例系統統,G=1,4,1,2,1,5,1,7,2,3。這個集合包含同時在兩個或者更多MLS中出現， 且組分序號由第1步排序的組分集合。第4步:繼續為每個MLS指定一個集合，該集合來自G且與MLS的交集具有最大的基 數。令gik是第i個MLS與G的第k個成員，Gk的交集，例如：(27)定義gi為具有最大基數的集合gik:考慮到對集合基數的要求，我們選擇G中第一個出現的集合gi是被指定給第i個MLS 的集合.一旦一個集合從G中被指定給一個MLS,就把它放在一個新集合G中,如果它還沒有 被放在那里的話。定義ncj作為成分j出