用递归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-)，女，山东临沂人，硕士，从事人工智能研究.