一种改进的故障树底事件排序算法

甄维坤,李帮东

(1.94595部队，山东潍坊261500；2.94563部队，山东威海264411)

一种改进的故障树底事件排序算法

甄维坤1,李帮东2

(1.94595部队，山东潍坊261500；2.94563部队，山东威海264411)

为了提高大型复杂系统故障树分析效率，借助二元决策图(BDD)来优化对最小割集的求解。将故障树转化为BDD过程中，底事件排序决定了BDD的节点数及其结构。一般来讲，BDD的节点数越少，结构越简单，求解效率越高。目前没有一种排序方法能够将所有故障树转化为最小结构的BDD。通过对大量排序规则所涉及的因素进行分析给出一种改进的底事件排序算法，通过故障树实例验证了该算法可以获得更小的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)是用于对大型系统可靠性、安全性进行风险分析、评价的一种有效方法。传统的面向割集的故障树分析方法[1]计算复杂度高，存在“组合爆炸”问题，并且难以计算机上实现，因而不适用于规模较大、系统关联复杂故障树。BDD(二元决策图)方法通过将故障树转化为二元决策图的形式进行分析，通过遍历BDD求得最小割集，该方法的计算效率高、精确度高和编程实现方便。在将故障树转化为BDD的过程中，底事件的排序决定了BDD的节点数及其结构，一般来讲，BDD的节点数越少，其结构越简单，求解效率越高。到目前为止，没有一种排序方法能够将所有故障树转化为最小结构的BDD[2]。因此寻求合适底事件的排序方法，减少BDD的结构和规模是基于BDD的故障树分析的关键。

近些年来，国内外很多学者对底事件的排序问题进行了大量研究，提出了很多排序的规则和方法，本文针对大量排序规则所涉及的因素进行分析给出一种改进的底事件排序算法，该算法克服了传统排序算法的不足，通过具体的故障树实例验证了该算法的有效性。

2 现有的底事件排序方法

现有的故障树底事件的排序方法主要是基于对故障树进行搜索。按照BDD的构造过程，底事件排序算法主要分为结构式方法[3-5]、加权式方法[6,7]和渐进式方法[8,9]。结构式方法是基于底事件在故障树结构中的位置，采用横向或纵向的方式进行排序。加权式方法是通过对底事件进行加权进行排序。渐进式方法是采用动态的方式对底事件进行排序。下面就现有的主要排序方法进行分析：

1)从上向下、从左至右的方法[2]：该方法根据故障树结构从故障树的顶事件开始，按照从上到下、从左到右的顺序选择底事件进行排序，已排序的事件不重复排序。

2)改进的从上向下、从左至右的方法：该方法在方法(1)基础上，考虑每层中的重复事件，重复度高的底事件优先排序。

3)深度优先方法[6]：该方法将故障树分为若干子树，从上到下对各子树依次采用从上到下、从左到右的顺序进行排序。

4)改进的深度优先方法：该方法在方法(3)基础上，考虑重复事件，重复度高的底事件优先排序。

5)有优先权的深度优先方法：在方法(3)基础上，优先选择输入事件全部为底事件即不包含中间事件的子树进行排序。

6)改进的有优先权的深度优先方法：在方法(5)基础上，考虑重复事件，重复度高的底事件优先排序。

7)自顶向下加权的方法：该方法首先设定顶事件的权重为1，下一层子节点平均分配其父节点权重，重复的底事件权重累计，最后按照权重从大到小依次排序。

8)自底向上加权的方法：该方法与方法(7)类似，但顺序不同。它是首先设定每一个底事件权重为1/2，从底向上按照与或逻辑进行计算各门的权重大小，与门权重为其子节点权重相乘，或门权重为其子节点权重相加，根据各子树权重大小选择各子树顺序，最后按照深度优先方法进行排序。

9)结构重要度的方法：该方法是首先计算各底事件的结构重要度，然后根据结构重要度大小进行排序，结构重要度大的优先排序。

10)相邻底事件优先法[8]：该方法先根据故障树结构的特点，确定部分底事件的次序，然后根据底事件之间的邻近关系，确定其他底事件的次序。

11)基于公共事件的方法[9]：该方法引入了公共事件的概念，并基于公共事件采用动态的方式进行排序。

上述现有的各种排序算法可能在特定的故障树结构中会取得比较好的效果，但是各自都有其不足之处，没有哪一种方法对任何结构的故障树都能取得较少的BDD节点数。结构式方法只考虑了底事件在故障树结构中的位置，没有考虑底事件之间的逻辑关系影响，并且同一故障树的不同画法会产生不同的排序结果；加权式方法只考虑到了底事件的权重，同样忽略了底事件之间逻辑关系；渐进式的方法综合了结构式与加权式方法特点，但只考虑了同层底事件之间的相邻关系，并且动态排序方法加大了排序计算的复杂度。

为了改善现有方法，本文综合现有方法中几种影响底事件排序的因素，提出一种改进的底事件排序算法，以获得较好的BDD结构以及相对较少BDD节点数。

3 改进的底事件排序算法

在进行对故障树进行分析之前，应对故障树进行剪枝，除去部分无关事件，简化故障树。改进的底事件排序算法通过分析不同因素对底事件排序的影响，给出排序的优先法则，然后以优先法则为依据通过搜索故障树对底事件进行排序。

3.1 故障树的剪枝

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

具体的故障树剪枝方法为：

①对应于公式(1)和(2)，如果某一逻辑门与其子逻辑门类型相同，则将该子逻辑门除去，并将子逻辑门的子节点提升至它的父门中，使它们成为上层门的子节点，以减少故障树中门的数量。

②对应于公式(3)和(4)，如果某一底事件的兄弟门事件的子节点中包含该底事件，则将整个兄弟门事件全部除去。

3.2 排序算法的优先法则

对底事件进行排序之前，首先通过对已有排序方法的研究，分析不同的排序规则[10-13]，寻找到影响排序的几大因素。第一个因素是底事件在故障树中的层次，层次越高，越靠近顶事件，对顶事件的影响就会越大[14]；第二个因素是底事件的重复度，重复度越高，对顶事件影响会有累积效应，比重复度低的事件影响要大；第三个因素是子树所包含的底事件的数目，数目越少，对顶事件的影响应该越大；第四个因素是相邻事件，某底事件的相邻事件会影响到该底事件，文献[8]已经验证了相邻事件的影响力。通过对以上四个因素的分析，给出排序的四个优先法则：

①优先法则一：层次。底事件所在层次越高，其排序优先级越高；子树包含的层次越少，优先级越高。

②优先法则二：重复度。底事件的重复度越高，排序优先级越高。

③优先法则三：底事件数目。子树包含底事件越少，优先级越高。

④优先法则四：相邻底事件。如果底事件或者子树的相邻底事件已排序，则其优先级越高，如果都有已排序的相邻底事件，则相邻底事件排序越靠前，优先级越高。

图1 子树选择判定过程

3.3 算法流程

图2 底事件排序判定过程

根据上面给出的四个优先法则，对故障树依次进行搜索，如果以上法则都无法选择优先级，则按照从左至右的顺序进行排序。在故障树搜索过程中，子树的判定选择过程见图1，首先按照法则一选择包含层次最少的子树；若相同，按照法则三选择底事件数目最少的子树；若相同，按照法则四选择相邻事件已排序且排序考前的子树；若相同，则采用由左至右的顺序进行选择。

底事件的排序判定过程见图2，首先按照优先法则一，所在层次高的底事件优先排序；若相同，按照法则二，重复度高的底事件优先排序；若相同，按照法则四，相邻事件已排序且排序靠前的底事件优先排序；若相同，则采用由左至右的顺序进行排序。

改进的底事件排序算法流程见图3。首先对故障树进行剪枝，然后从最上层开始按照子树判定与底事件判定方法对故障树进行底事件排序，对故障树全部遍历后给出最终的底事件顺序。

图3 改进的底事件排序算法流程图

4 算法应用与比较

为了更好的介绍改进的底事件排序算法的计算过程，我们以某系统故障树(图4)为例来说明具体过程，并通过结果与其他几种排序算法结果进行比较，来验证本算法的优越性。

图4 故障树实例

①故障树剪枝

首先对该故障树进行剪枝。在图4故障树中，底事件e15的兄弟门事件下也存在e15，根据布尔吸收律有G3=e15+(e9×e6×e4×e15)=e15，所以可将G7门及其子事件除去，这样G3下只有e15一个子事件，则可将图中白色部分除去，将e15直接划为G1下的子事件。

②搜索第一层并进行排序

第一层存在底事件，按照底事件判定排序规则，e7，e11，e1处在同一层次，比较其重复度，repeat(e7)=repeat(e11)＞repeat(e1)，此三个底事件都没有已排序的相邻事件，所以e7与e11按照从左到右的顺序排序，得到Index(e7)＞Index(e11)＞Index(e1).

底事件排序完成后，按照子树判定规则选择子树，首先比较G1与G2包含的层次数，layer(G1)=3＞layer(G2)=2，所以选择G1进行搜索。

③搜索G1子树并进行排序

搜索子树G1，第二层中G1含有一个底事件e15，所以e15优先排序；然后对G4搜索，第三层中含有两个底事件e0和e8，他们所在层数相同，比较其重复度也相同，都没有相邻事件已排序，按从左到右的顺序得到Index(e0)＞Index(e8)；继续搜索G8，第四层中G8有四个底事件e14,e4,e5和e11，其中e11已排序，比较其他三个的重复度得到repeat(e4)=2＞repeat(e14)=repeat(e5)=1，所以e4优先排序；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)；继续向下搜索G5与G6子树，按照子树判定选择规则首先选择G5，第三层中G5有底事件e7,e10，其中e7已排序，所以e10排在未排序底事件首位；向上回溯搜索G6，第三层中G6仅有一个未排序事件e13，正常排序。最后得到Index(e3)＞Index(e12)＞Index(e10)＞Index(e13)。

最后继续向上回溯，没有未排序的底事件或者未搜索的子树，排序结束，得到最终的排序结果为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 不同底事件排序方法排序结果及节点数比较

为了说明改进的底事件排序算法的优越性，分别应用本算法和其他几种排序算法对图4中的故障树底事件进行排序，并比较他们转化为BDD后的节点数(见表1)，可以看出本算法得到的BDD节点数是最少的，虽然与相邻事件优先法得到的节点数相同，但是对他们的BDD结构进行比较如图5和图6，明显可以看出本算法得到的BDD结构更加简单。

图5 改进的算法得到的BDD图

图6 相邻事件优先法得到的BDD图

5 结论

故障树分析是装备系统可靠性研究以及故障诊断的重要手段，基于二元决策图的故障树分析方法求解故障树最小割集以及顶事件概率具有良好的计算效率并且易于编程实现，而故障树底事件的排序决定了BDD的节点数及其结构。本文通过分析影响排序的底事件层次、重复度、子树所包含底事件数目、相邻底事件等几大因素，提出一种改进的底事件排序算法，并通过故障树实例分析与比较验证了该方法的有效性和优越性。

[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].系统管理学报,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—)，男，山东青州人，工程师，主要研究方向为装备保障。