一種改進的故障樹底事件排序算法

甄維坤,李幫東

(1.94595部隊，山東濰坊261500；2.94563部隊，山東威海264411)

一種改進的故障樹底事件排序算法

甄維坤1,李幫東2

(1.94595部隊，山東濰坊261500；2.94563部隊，山東威海264411)

為了提高大型復雜系統(tǒng)故障樹分析效率，借助二元決策圖(BDD)來優(yōu)化對最小割集的求解。將故障樹轉化為BDD過程中，底事件排序決定了BDD的節(jié)點數(shù)及其結構。一般來講，BDD的節(jié)點數(shù)越少，結構越簡單，求解效率越高。目前沒有一種排序方法能夠將所有故障樹轉化為最小結構的BDD。通過對大量排序規(guī)則所涉及的因素進行分析給出一種改進的底事件排序算法，通過故障樹實例驗證了該算法可以獲得更小的BDD結構，從而提高故障樹分析效率。

故障樹；二元決策圖；底事件；最小割集；排序算法

Abstract：In order to improve the efficiency of fault tree analysis(FTA),the Binary Decision Diagram(BDD)was introduced to optimize the solution of the minimal cut sets.The sequence of the basic events can directly influence the number of the nodes and the size of a BDD.In general,the smaller and simpler the BDD is,the less computation time is required.Through the analy?sis of the factors involved in the existing ordering rules，an improved ordering method of basic events was proposed.Demonstrat?ed by the example,the proposed ordering method is superior to the existing ordering methods in terms of reducing the nodes in the BDD and improving the efficiency of fault tree analysis.

Key words：FTA;BDD;basic events;MCS;ordering method

1 概述

故障樹(FTA)是用于對大型系統(tǒng)可靠性、安全性進行風險分析、評價的一種有效方法。傳統(tǒng)的面向割集的故障樹分析方法[1]計算復雜度高，存在“組合爆炸”問題，并且難以計算機上實現(xiàn)，因而不適用于規(guī)模較大、系統(tǒng)關聯(lián)復雜故障樹。BDD(二元決策圖)方法通過將故障樹轉化為二元決策圖的形式進行分析，通過遍歷BDD求得最小割集，該方法的計算效率高、精確度高和編程實現(xiàn)方便。在將故障樹轉化為BDD的過程中，底事件的排序決定了BDD的節(jié)點數(shù)及其結構，一般來講，BDD的節(jié)點數(shù)越少，其結構越簡單，求解效率越高。到目前為止，沒有一種排序方法能夠將所有故障樹轉化為最小結構的BDD[2]。因此尋求合適底事件的排序方法，減少BDD的結構和規(guī)模是基于BDD的故障樹分析的關鍵。

近些年來，國內外很多學者對底事件的排序問題進行了大量研究，提出了很多排序的規(guī)則和方法，本文針對大量排序規(guī)則所涉及的因素進行分析給出一種改進的底事件排序算法，該算法克服了傳統(tǒng)排序算法的不足，通過具體的故障樹實例驗證了該算法的有效性。

2 現(xiàn)有的底事件排序方法

現(xiàn)有的故障樹底事件的排序方法主要是基于對故障樹進行搜索。按照BDD的構造過程，底事件排序算法主要分為結構式方法[3-5]、加權式方法[6,7]和漸進式方法[8,9]。結構式方法是基于底事件在故障樹結構中的位置，采用橫向或縱向的方式進行排序。加權式方法是通過對底事件進行加權進行排序。漸進式方法是采用動態(tài)的方式對底事件進行排序。下面就現(xiàn)有的主要排序方法進行分析：

1)從上向下、從左至右的方法[2]：該方法根據(jù)故障樹結構從故障樹的頂事件開始，按照從上到下、從左到右的順序選擇底事件進行排序，已排序的事件不重復排序。

2)改進的從上向下、從左至右的方法：該方法在方法(1)基礎上，考慮每層中的重復事件，重復度高的底事件優(yōu)先排序。

3)深度優(yōu)先方法[6]：該方法將故障樹分為若干子樹，從上到下對各子樹依次采用從上到下、從左到右的順序進行排序。

4)改進的深度優(yōu)先方法：該方法在方法(3)基礎上，考慮重復事件，重復度高的底事件優(yōu)先排序。

5)有優(yōu)先權的深度優(yōu)先方法：在方法(3)基礎上，優(yōu)先選擇輸入事件全部為底事件即不包含中間事件的子樹進行排序。

6)改進的有優(yōu)先權的深度優(yōu)先方法：在方法(5)基礎上，考慮重復事件，重復度高的底事件優(yōu)先排序。

7)自頂向下加權的方法：該方法首先設定頂事件的權重為1，下一層子節(jié)點平均分配其父節(jié)點權重，重復的底事件權重累計，最后按照權重從大到小依次排序。

8)自底向上加權的方法：該方法與方法(7)類似，但順序不同。它是首先設定每一個底事件權重為1/2，從底向上按照與或邏輯進行計算各門的權重大小，與門權重為其子節(jié)點權重相乘，或門權重為其子節(jié)點權重相加，根據(jù)各子樹權重大小選擇各子樹順序，最后按照深度優(yōu)先方法進行排序。

9)結構重要度的方法：該方法是首先計算各底事件的結構重要度，然后根據(jù)結構重要度大小進行排序，結構重要度大的優(yōu)先排序。

10)相鄰底事件優(yōu)先法[8]：該方法先根據(jù)故障樹結構的特點，確定部分底事件的次序，然后根據(jù)底事件之間的鄰近關系，確定其他底事件的次序。

11)基于公共事件的方法[9]：該方法引入了公共事件的概念，并基于公共事件采用動態(tài)的方式進行排序。

上述現(xiàn)有的各種排序算法可能在特定的故障樹結構中會取得比較好的效果，但是各自都有其不足之處，沒有哪一種方法對任何結構的故障樹都能取得較少的BDD節(jié)點數(shù)。結構式方法只考慮了底事件在故障樹結構中的位置，沒有考慮底事件之間的邏輯關系影響，并且同一故障樹的不同畫法會產生不同的排序結果；加權式方法只考慮到了底事件的權重，同樣忽略了底事件之間邏輯關系；漸進式的方法綜合了結構式與加權式方法特點，但只考慮了同層底事件之間的相鄰關系，并且動態(tài)排序方法加大了排序計算的復雜度。

為了改善現(xiàn)有方法，本文綜合現(xiàn)有方法中幾種影響底事件排序的因素，提出一種改進的底事件排序算法，以獲得較好的BDD結構以及相對較少BDD節(jié)點數(shù)。

3 改進的底事件排序算法

在進行對故障樹進行分析之前，應對故障樹進行剪枝，除去部分無關事件，簡化故障樹。改進的底事件排序算法通過分析不同因素對底事件排序的影響，給出排序的優(yōu)先法則，然后以優(yōu)先法則為依據(jù)通過搜索故障樹對底事件進行排序。

3.1 故障樹的剪枝

故障樹的剪枝基于布爾吸收律，也就是如下公式：

具體的故障樹剪枝方法為：

①對應于公式(1)和(2)，如果某一邏輯門與其子邏輯門類型相同，則將該子邏輯門除去，并將子邏輯門的子節(jié)點提升至它的父門中，使它們成為上層門的子節(jié)點，以減少故障樹中門的數(shù)量。

②對應于公式(3)和(4)，如果某一底事件的兄弟門事件的子節(jié)點中包含該底事件，則將整個兄弟門事件全部除去。

3.2 排序算法的優(yōu)先法則

對底事件進行排序之前，首先通過對已有排序方法的研究，分析不同的排序規(guī)則[10-13]，尋找到影響排序的幾大因素。第一個因素是底事件在故障樹中的層次，層次越高，越靠近頂事件，對頂事件的影響就會越大[14]；第二個因素是底事件的重復度，重復度越高，對頂事件影響會有累積效應，比重復度低的事件影響要大；第三個因素是子樹所包含的底事件的數(shù)目，數(shù)目越少，對頂事件的影響應該越大；第四個因素是相鄰事件，某底事件的相鄰事件會影響到該底事件，文獻[8]已經(jīng)驗證了相鄰事件的影響力。通過對以上四個因素的分析，給出排序的四個優(yōu)先法則：

①優(yōu)先法則一：層次。底事件所在層次越高，其排序優(yōu)先級越高；子樹包含的層次越少，優(yōu)先級越高。

②優(yōu)先法則二：重復度。底事件的重復度越高，排序優(yōu)先級越高。

③優(yōu)先法則三：底事件數(shù)目。子樹包含底事件越少，優(yōu)先級越高。

④優(yōu)先法則四：相鄰底事件。如果底事件或者子樹的相鄰底事件已排序，則其優(yōu)先級越高，如果都有已排序的相鄰底事件，則相鄰底事件排序越靠前，優(yōu)先級越高。

圖1 子樹選擇判定過程

3.3 算法流程

圖2 底事件排序判定過程

根據(jù)上面給出的四個優(yōu)先法則，對故障樹依次進行搜索，如果以上法則都無法選擇優(yōu)先級，則按照從左至右的順序進行排序。在故障樹搜索過程中，子樹的判定選擇過程見圖1，首先按照法則一選擇包含層次最少的子樹；若相同，按照法則三選擇底事件數(shù)目最少的子樹；若相同，按照法則四選擇相鄰事件已排序且排序考前的子樹；若相同，則采用由左至右的順序進行選擇。

底事件的排序判定過程見圖2，首先按照優(yōu)先法則一，所在層次高的底事件優(yōu)先排序；若相同，按照法則二，重復度高的底事件優(yōu)先排序；若相同，按照法則四，相鄰事件已排序且排序靠前的底事件優(yōu)先排序；若相同，則采用由左至右的順序進行排序。

改進的底事件排序算法流程見圖3。首先對故障樹進行剪枝，然后從最上層開始按照子樹判定與底事件判定方法對故障樹進行底事件排序，對故障樹全部遍歷后給出最終的底事件順序。

圖3 改進的底事件排序算法流程圖

4 算法應用與比較

為了更好的介紹改進的底事件排序算法的計算過程，我們以某系統(tǒng)故障樹(圖4)為例來說明具體過程，并通過結果與其他幾種排序算法結果進行比較，來驗證本算法的優(yōu)越性。

圖4 故障樹實例

①故障樹剪枝

首先對該故障樹進行剪枝。在圖4故障樹中，底事件e15的兄弟門事件下也存在e15，根據(jù)布爾吸收律有G3=e15+(e9×e6×e4×e15)=e15，所以可將G7門及其子事件除去，這樣G3下只有e15一個子事件，則可將圖中白色部分除去，將e15直接劃為G1下的子事件。

②搜索第一層并進行排序

第一層存在底事件，按照底事件判定排序規(guī)則，e7，e11，e1處在同一層次，比較其重復度，repeat(e7)=repeat(e11)＞repeat(e1)，此三個底事件都沒有已排序的相鄰事件，所以e7與e11按照從左到右的順序排序，得到Index(e7)＞Index(e11)＞Index(e1).

底事件排序完成后，按照子樹判定規(guī)則選擇子樹，首先比較G1與G2包含的層次數(shù)，layer(G1)=3＞layer(G2)=2，所以選擇G1進行搜索。

③搜索G1子樹并進行排序

搜索子樹G1，第二層中G1含有一個底事件e15，所以e15優(yōu)先排序；然后對G4搜索，第三層中含有兩個底事件e0和e8，他們所在層數(shù)相同，比較其重復度也相同，都沒有相鄰事件已排序，按從左到右的順序得到Index(e0)＞Index(e8)；繼續(xù)搜索G8，第四層中G8有四個底事件e14,e4,e5和e11，其中e11已排序，比較其他三個的重復度得到repeat(e4)=2＞repeat(e14)=repeat(e5)=1，所以e4優(yōu)先排序；e14有已排序相鄰事件e4，e5有已排序相鄰事件 e11，Index(e11)＞Index(e4),所以得到Index(e5)＞Index(e14).最后，通過對G1搜索得到Index(e15)＞Index(e0)＞Index(e8)＞Index(e4)＞Index(e5)＞Index(e14)。

④搜索G2子樹并進行排序

搜索完G1子樹后，向上回溯到第一層對G2進行搜索排序。第二層中G2含有三個底事件e4,e3,e12，其中e4已排序，e3與e12重復相同，都沒有已排序相鄰事件，按照從左到右的順序得到In?dex(e3)＞Index(e12)；繼續(xù)向下搜索G5與G6子樹，按照子樹判定選擇規(guī)則首先選擇G5，第三層中G5有底事件e7,e10，其中e7已排序，所以e10排在未排序底事件首位；向上回溯搜索G6，第三層中G6僅有一個未排序事件e13，正常排序。最后得到Index(e3)＞Index(e12)＞Index(e10)＞Index(e13)。

最后繼續(xù)向上回溯，沒有未排序的底事件或者未搜索的子樹，排序結束，得到最終的排序結果為Index(e7)＞Index(e11)＞Index(e1)＞ Index(e15)＞ Index(e0)＞ Index(e8)＞ Index(e4)＞ Index(e5)＞ In?dex(e14)＞Index(e3)＞Index(e12)＞Index(e10)＞Index(e13)。

表1 不同底事件排序方法排序結果及節(jié)點數(shù)比較

為了說明改進的底事件排序算法的優(yōu)越性，分別應用本算法和其他幾種排序算法對圖4中的故障樹底事件進行排序，并比較他們轉化為BDD后的節(jié)點數(shù)(見表1)，可以看出本算法得到的BDD節(jié)點數(shù)是最少的，雖然與相鄰事件優(yōu)先法得到的節(jié)點數(shù)相同，但是對他們的BDD結構進行比較如圖5和圖6，明顯可以看出本算法得到的BDD結構更加簡單。

圖5 改進的算法得到的BDD圖

圖6 相鄰事件優(yōu)先法得到的BDD圖

5 結論

故障樹分析是裝備系統(tǒng)可靠性研究以及故障診斷的重要手段，基于二元決策圖的故障樹分析方法求解故障樹最小割集以及頂事件概率具有良好的計算效率并且易于編程實現(xiàn)，而故障樹底事件的排序決定了BDD的節(jié)點數(shù)及其結構。本文通過分析影響排序的底事件層次、重復度、子樹所包含底事件數(shù)目、相鄰底事件等幾大因素，提出一種改進的底事件排序算法，并通過故障樹實例分析與比較驗證了該方法的有效性和優(yōu)越性。

[1]郭永基.可靠性工程原理[M].北京：清華大學出版社,2002

[2]R.M.Sinnamon,J.D Andrew.Fault Tree Analysis and Binary Decision Diagrams[C].IEEE PROCEEDINGS Annual RELI?ABILITY and MAINTAINABILITY Symposium,1996：215～222.

[3]Sinnamon R.M.,Andrews J.D.New Approaches to Evaluating Fault Trees[J].Reliability Engineering and System Safety,1997,58：89～96.

[4]Andrews JD,Bartlett LM.Ef fi cient basic event orderings for bi?nary decision diagrams[C].Proceedings Annual Reliability and Maintainability Symposium,1998：61～68.

[5]A.Rauzy.New algorithms for Fault Tree Analysis[J].Reliability Engineering and System Safety,1993,140(3):203～211.

[6]Bartlett LM,Andrews JD.An ordering heuristic to develop the binary decision diagram Based on structural importance[J].Re?liability Engineering and System Safety 2001,72：31～38.

[7]Bartlett LM,Andrews JD.Choosing a heuristic for the“fault tree to binary decision diagram”conversion using neural net?works[J].IEEE Transactionson Reliability 2002,51(3)：344～349.

[8]孫艷,杜素果.一種二元決策圖底事件排序的新方法[J].系統(tǒng)管理學報,2008,17(2)：210～216.

[9]章金偉.基于公共事件的二元決策圖底事件排序方法研究[D].上海交通大學,2008：50-65.

[10]胡文軍.故障樹向二元決策圖的轉換算法[J].原子能科學技術,2010,44(3):289～293.

[11]G.L.Pahuja,R.Singh.Common Cause Failure Analysis of Systems Using BDD[C].XXXII National Systems Conference,NSC 2008,2008：17-19.

[12]段珊,張修如,劉樹錕,等.一種故障樹向BDD的轉化方法[J].計算機工程與應用,2009,45(21)：51～54

[13]Hong-Zhong Huang,Hua Zhang,Yanfeng Li.A New Ordering Method of Basic Events in Fault Tree Analysis[J].Quality and Reliability Engineering International,2011：27(8).

[14]Lu L,Jiang J.Joint failure importance for noncoherent fault trees[J].IEEE Transactions on Reliability 2007,56(3)：435-443.

An Improved Ordering Method of Basic Events in Fault Tree Analysis

ZHEN Wei-kun1，LI Bang-dong2
(1.Unit No.94595 of PLA,Weifang 261500,China;2.Unit No.94563 of PLA,Weihai 264411,China)

TP301

A

1009-3044(2017)24-0017-04

2017-07-05

甄維坤(1986—)，男，山東齊河人，碩士，主要研究方向為裝備智能故障診斷；李幫東(1984—)，男，山東青州人，工程師，主要研究方向為裝備保障。