甄維坤,李幫東

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

一種改進(jìn)的故障樹底事件排序算法

甄維坤1,李幫東2

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

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

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

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

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

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

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

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

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

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

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

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

6)改進(jìn)的有優(yōu)先權(quán)的深度優(yōu)先方法：在方法(5)基礎(chǔ)上，考慮重復(fù)事件，重復(fù)度高的底事件優(yōu)先排序。

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

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

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

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

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

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

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

3 改進(jìn)的底事件排序算法

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

3.1 故障樹的剪枝

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

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

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

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

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

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

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

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

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

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

圖1 子樹選擇判定過程

3.3 算法流程

圖2 底事件排序判定過程

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

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

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

圖3 改進(jìn)的底事件排序算法流程圖

4 算法應(yīng)用與比較

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

圖4 故障樹實(shí)例

①故障樹剪枝

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

②搜索第一層并進(jìn)行排序

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

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

③搜索G1子樹并進(jìn)行排序

搜索子樹G1，第二層中G1含有一個(gè)底事件e15，所以e15優(yōu)先排序；然后對G4搜索，第三層中含有兩個(gè)底事件e0和e8，他們所在層數(shù)相同，比較其重復(fù)度也相同，都沒有相鄰事件已排序，按從左到右的順序得到Index(e0)＞Index(e8)；繼續(xù)搜索G8，第四層中G8有四個(gè)底事件e14,e4,e5和e11，其中e11已排序，比較其他三個(gè)的重復(fù)度得到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子樹并進(jìn)行排序

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

最后繼續(xù)向上回溯，沒有未排序的底事件或者未搜索的子樹，排序結(jié)束，得到最終的排序結(jié)果為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é)果及節(jié)點(diǎn)數(shù)比較

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

圖5 改進(jìn)的算法得到的BDD圖

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

5 結(jié)論

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

[1]郭永基.可靠性工程原理[M].北京：清華大學(xué)出版社,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)管理學(xué)報(bào),2008,17(2)：210～216.

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

[10]胡文軍.故障樹向二元決策圖的轉(zhuǎn)換算法[J].原子能科學(xué)技術(shù),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的轉(zhuǎn)化方法[J].計(jì)算機(jī)工程與應(yīng)用,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—)，男，山東齊河人，碩士，主要研究方向?yàn)檠b備智能故障診斷；李幫東(1984—)，男，山東青州人，工程師，主要研究方向?yàn)檠b備保障。