用遞歸BDD(二元決策圖)技術分析因果圖*

嚴　曉，王洪春(重慶師范大學數學學院，重慶401331)

用遞歸BDD(二元決策圖)技術分析因果圖*

嚴曉，王洪春＊＊
(重慶師范大學數學學院，重慶401331)

摘要:故障樹是以系統最不希望發生的頂事件為目標，通過分析找出導致頂上事件發生的全部因素;在故障樹分析中，二元決策圖(簡稱BDD)是最有效的方法之一，由于故障樹和因果圖都是用圖形表示因果關系，兩者具有很多相似性，而BDD在故障樹中有廣泛的應用;通過研究表明:在一定條件下，故障樹和因果圖之間可以互相轉化，因此可以分析BDD的原理，并將BDD技術用來分析因果圖。

關鍵詞:故障樹; BDD;因果圖

＊＊通訊作者:王洪春(1967-)，男，四川大竹人，教授，博士，從事人工智能、因果圖和故障診斷研究.E-mail:wanghongchun@swsc.com.cn

故障樹是一種以系統最不希望發生的頂事件為目標，通過對可能導致頂事件發生的中間事件和底事件進行分析，在一般情況下，事件分為兩種狀態，正常或者是故障，在傳統分析故障樹中，一般通過求故障樹的最小割集，對故障樹進行分析，然而對于復雜的故障樹，求最小割集比較困難，為了克服這種缺陷，引入了二元決策圖［1］，把故障樹轉化成二元決策圖進行分析研究，然后自上而下遍歷二元決策圖，能夠得到最小割集，在二元決策圖轉化的過程中，要先對故障樹進行簡化，對簡化后的故障樹的基本事件進行排序［2］，從而對故障樹進行定性和定量分析。而因果圖是從信度網發展起來的，通過事件連接成一個網狀結構來反映事件之間的關系，通過研究表明，在一定條件下因果圖和故障樹之間可以相互轉化，因此BDD也可以用于因果圖中。

1　BDD遞歸法［3］及原理

將故障樹轉化為BDD的方法，最早是由Rauzy提出的，并在轉化過程中提出了一種ite結構(If-then-Else)，它是基于shannon分解提出來的，ite(x，y，z)表示如果x成立，則成立，否則，z成立，數學表達式為ite(x，y，z) = xy+z。

遞歸法的思想轉化:從故障樹最底層的門事件開始，用底事件置換門事件，逐層向上，每置換一步同時按一定規則用ite結構對置換結果進行編碼，如此類推，將所有門事件均用底事件置換編碼，使可得到頂事件的BDD。

將故障樹轉化成BDD，步驟如下:

(1)將復雜故障樹轉化為只含有與、或門的規范樹，如果含有非門，利用德·摩根規則把中間事件的非門去掉，僅使底事件含有與門和或門，以便于處理。

(2)用底事件置換門事件，逐層向上，每置換一步同時按一定規則用ite結構對置換結果進行編碼，如此類推，將所有門事件均用底事件置換編碼，使可得到頂事件的BDD。

(3)求頂事件的BDD［3］，運算規則如下:

假設兩個BDD結構分別為

當i＜j時，(i＞j情況類似)

〈op〉表示邏輯“或”用“+”表示，當〈op〉為“或”操作時:

當〈op〉為“與”操作時:

當i=j時，當〈op〉為“或”操作時:

當〈op〉為“與”操作時:

2　BDD技術分析因果圖

因果圖和故障樹都可以表示系統中的各種關系，在故障樹中表示各系統之間的關系是確定的，而在因果圖中，系統可以表示不確定的因果關系，為了把BDD運用到因果圖中，選取因果圖中確定的因果關系進行分析，類比于故障樹，因果圖中的中間事件相當于故障樹中的頂事件和中間事件，因果圖的基本事件相當于故障樹的底事件。在分析因果圖中，因果圖中的每一個節點事件相應的對應一棵微因果樹，它可以將因果圖分成若干個小的模塊，通過對小模塊進行整合得到因果樹，在對因果樹進行分析。

對比BDD方法在故障樹的應用，將BDD方法應用到因果圖中，步驟如下:

(1)將因果圖轉換成因果樹。因果圖中的每一個節點事件對應一個微型因果樹，將因果圖中多的每個中間事件為頂事件，將所有與頂事件相關的中間事件節點微因果樹化。

(2)將因果圖轉換成因果樹后，形成因果樹頂事件的BDD結構，并對因果樹進行定性和定量分析。

3　算例

在算例中，所用到的因果圖均為確定的關系，對于不確定的因果圖，還有待于研究。算例的因果圖如圖1所示:

圖1　因果圖1

在因果圖1分析中，先將因果圖微因果樹化［4］，在此因果圖中，微因果樹的節點事件分別X1，X2，X3，X4。在對因果圖1進行微因果樹化時，微因果樹的菱形為與節點相鄰的節點事件，圓圈為與節點事件相鄰的基本事件［5］。它的實質實際是將節點事件以樹根的形式呈現出來的過程(圖2、3)。

圖2　因果圖1對應的微因果樹化

圖3　由圖1轉換得到的因果樹

對因果樹進行定性和定量分析，可以得到頂事件的最小割集［6］。

用BDD表示如下(圖4)所示:

頂事件結構的BDD為

圖4　因果樹的二元決策

4　結束語

BDD技術是分析故障的一種有效的手段，與傳統的故障樹相比，它能夠直接對結構函數進行分解，并且快速實現故障的定性和定量分析，在研究中，只研究了BDD在確定因果圖中的應用，而對于不確定的因果圖還有待于進一步研究。

參考文獻:

［1］郎榮玲.故障樹轉化為二元決樹的算法研究［J］.計算機工程與應用，2008，44:108-110

［2］孫艷，杜素果.一種二元決策圖底事件排序的新方法［J］.計算機工程與應用，2008，4(2):210-220

［3］羅航，王厚軍，黃建國，等.用遞歸BDD技術分析故障樹［J］.電子科技大學學報，2011，40(5):726-731

［4］梁新元，王洪春，石慶喜，等.因果圖向故障樹轉換的研究［J］.計算機仿真，2005，22(12):67-70

［5］梁新元，張勤.故障樹向因果圖的轉換的研究［J］.計算機仿真，2005，22(10):144-146

［6］陶勇劍，董德存，任鵬.故障樹分析德爾二元決策法鐵路［J］.計算機應用，2009，18(9):201-210

An Analysis of Causality Diagram by Recursive BDD

YAN Xiao，WANG Hong-chun1
(School of mathematics Sciences，Chongqing normal university，Chongqing 401331，China)

Abstract:Aimed at the most unwilling top event of system，fault tree finds out the all factors that cause the top event through analysis.In fault tree analysis，two binary decision diagrams (BDD) is the most efficient method.As both fault tree and causality diagram can express causation by digraph，there are lots of similarity in common.However，BDDis widely used in Fault tree.The research shows that under certain conditions，fault tree and causality diagram can be transformed into each other.Therefore，causality diagram can be analyzed by BDD on the basis of BDD principle.

Key words:fault tree; BDD; causality diagram

doi:10.16055/j.issn.1672－058X.2015.0008.008

中圖分類號:O141.41

文獻標識碼:A

文章編號:1672－058X(2015) 08－0034－04

收稿日期:2014－10－22;修回日期:2014－12－30.

*基金項目:國家社科基金資助(13BTJ008).

作者簡介:嚴曉(1988-)，女，山東臨沂人，碩士，從事人工智能研究.