故障树分析中np问题的处理

故障树分析中np问题的处理

在大型复杂的控制系统中建设的故障树中，基本事件通常超过1000个。这些许多事件不可避免地会重复，这将极大地给决策树的定性和定量分析带来不便。随着故障树规模的增加（np问题），故障树的规模通常可以用下降事件和逻辑门的数量来表示。为了便于定性和定量分析，我们需要对故障树进行全面重新评估，删除故障树中包含的相同重复事件，减少逻辑门的数量，减少故障树的规模，并对故障树进行简化。1fpsd计算的一般算法众所周知,故障树的定性分析首先要求出割集.探测法要把全部n个底事件的所有可能组合送到计算机内的故障树中去探测,能使顶事件发生的就是割集.这种组合2n有种,因此是NP问题.改用上(下)行法求全部割集,它考虑到故障树的具体结构,按逻辑门规则和分配率,自下而上(或自上而下)层层代入和展开.割集数目小于2n,绝对数目还是很大.与、或交叉出现时割集总数还可能迅速增长.其次是把求得的割集最小化,即求最小割集.对于不包含补事件的单调关联故障树,这需要通过布尔吸收运算(A∪(A∩B))=A,对全部的割集进行两两比较,总的比较次数为(1/2)(m-1),m是全部割集个数.对于非单调关联故障树,还要找质蕴涵集,计算量更大.最后就是用最小割集表示故障树,由于这些割集之间一般有相同底事件,因此是相交的,计算顶事件概率的时候项数按最小割集的个数而以指数增长.因此除用近似法估计系统故障概率上下限,限制最小割集阶数或按重要度取近似之外,一般需要把全部最小割集不交化,为此通常用递归算法c1∪c¯1{c2∪c¯2∪[c3∪c¯3(c4∪\c1∪c¯1{c2∪c¯2∪[c3∪c¯3(c4∪\:)]},由里向外逐层按分配率展开,并使之最小化,其计算量类似前面分析,也是很大的.综上所述,FTA实施过程中,在求割集、最小割集、不交化直到计算顶事件概率等基本步骤中的计算量是巨大的.故障树的规模通常可以用底事件和逻辑门数目来表征,FTA的计算量随故障树规模的加大呈指数增长.根据计算复杂性理论(IntractabilityofComputation),用计算机解数学问题时,首先必须把初始数据和必要的说明用二进制数表示,这样输入到计算机所需内存单元的数目(输入长度),就叫做问题的规模,而解题所需求的加、减、乘、除、比较等基本操作的总数,叫做计算量.所谓多项式算法,是对任何规模的问题,计算量T(L)=O(Lk)(k为正的常数),指数算法是指T(L)=O(2KL).后者的计算量随着问题规模的增大呈指数增长,这就是通常所说的“指数爆炸”问题.所以人们把指数算法叫做“坏”算法或“慢”算法,而把多项式算法叫做“好”算法或“快”算法.NP(NondeterministicPolynomial)问题是说在非确定计算机(具有猜测、判断功能的假想计算机)上具有多项式算法的问题.例如图1,最后D0→D1→D5为成功.假想计算机能猜对这一条路,所以计算量只算D0,D2,D5.但是对确定性计算机(现实计算机)来说,似乎只有通过试探所有可能的路径才能保证成功,因此计算量呈指数增长.罗森塔尔(A.Rodenthal)在博士论文中证明一般故障树分析和一般网络可靠度计算是NP困难问题.这里“一般”两个字很重要,就是说特定的故障树或特定的网络可靠度分析可能并不难,但是一般故障树和网络分析是NP困难问题.2错误树的初始不交叉2.1早期不交化原则如前所述,一般故障树分析是NP困难,这个性质是任何人改变不了.不可能设计出普遍使用的“好”算法,但也不是说现有算法都同等程度的“坏”.FTA的要害就是繁,国内外研究者纷纷致力于FTA的简化,显然最有效的简化方法是:不产生最终要消去的项.从这个原则出发,提出了“三早”:早期分解模块,早期进行逻辑简化,早期不交化即:早去复枝,免其烦杂,复枝是指重复事件.重复事件对于FTA有很大的坏作用,重复事件多时使分解模块无能为力,但早期不交化恰恰有利于消除重复事件的影响,是专门对付重复事件的.所以“三早”相结合在大多数情况下可以显著减轻FTA的NP困难.基于上述思想,本文采用了FTA的早期不交化的方法.1)有重复事件的故障树.运用早期不交化运算规则,即经过等幂(x∩x=x)、去补(x∩x¯)=0(x∩x¯)=0运算消除对造成故障树顶事件的发生不起作用的底事件.2)从单调关联故障树运用不交化运算规则求得的不交型故障函数(其中所有逆事件都是为了不交化引入的,单调关联故障树本身原来没有逆事件),取消所有逆事件,再经吸收运算(A∪(A∩B)=A),即得全部最小割集.2.2传统不交化布尔代数运算法1)无论故障树多么复杂,故障树本身的不交化(即早期不交化)都是一种简单的替换,即按照不交化布尔代数运算法则作相应的变换.2)从布尔代数运算来分析,常规途径从布尔显示割集求最小割集必须通过吸收运算.3)早期不交化可以有效的对付重复事件,在重复事件很多时效果显著.2.3基本故障类型,主要有以下几种研究如图2所示的故障树,运用早期不交化原则来对故障树进行布尔代数的简化.T=E1+E2=E3E4+E5D=(A+E6)(C+E7)+(A(D′))D=AC+(B+C)C+AAB+(A(D′))D=AC+BC+C+AB+ABC.Τ=E1+E2=E3E4+E5D=(A+E6)(C+E7)+(A(D′))D=AC+(B+C)C+AAB+(A(D′))D=AC+BC+C+AB+ABC.注:经过早期不交化运算,吸收运算CC=C,AAB=AB,去补运算A(D′)D=Ø.早期不交化后得到故障树如图3所示.3基于模块的识别故障树上面介绍的使用布尔代数简化法对故障树进行早期不交化,随着底事件和门的数目增加计算量将指数地增长,使现代高速计算机也无能为力,因此人们一直在探索其它的故障树简化途径.美国学者罗森撤尔(A.Rosenthal)在深入研究这一问题之后认为,对故障树进行模块分解是对付简化过程中出现NP困难问题的一条出路.因为在大型复杂系统中很多部件(底事件)并不直接相互作用,人们常可把互不相关的部分看成模块分别处理,然后把结果合为一体,即得到整个系统故障树的最小割集.模块概念的数学定义及性质的发现归功于(Z.W.Birnbaum).后来,查特基((P.Chatterjee)提出了识别故障树模块的算法.该算法能找出故障树的全部最大模块,亦能识别不能模块化的故障树.3.1有关模块的概念1底事件的集合对于已经规范化的正规故障树,模块是至少两个底事件,但不是所有底事件的集合.这些底事件向上可以到达同一逻辑门,并且必须通过此门才能到达顶事件,故障树的所有其它底事件向上均不能到达该逻辑门.模块没有来自其余部分的输入,没有与其余部分相重复的事件.2主模块规范化的正规故障树的最大模块是该故障树的一个模块,且没有其它模块包含它.31模块树故障树的模块子树是模块所包含的底事件和向上所经过的各逻辑门包括达到的同一逻辑门构成的原故障树的一个分枝.4模块失败的树把模块子树的顶事件看作为虚构的底事件,这样原来复杂的故障树就变成相对简单的以模块子树为底事件的故障树,称为模块故障树.3.2重复模块分解模块分解法的步骤是:先找出已给出故障树的模块子树并得到模块故障树;然后对每个模块子树进行简化,求得模块子树的最小割集;再对模块子树的最小割集代入模块故障树的最小割集,即得原故障树的最小割集.简言之,模块分解法是将一复杂故障树转化为一系列较简单的故障树,以达到简化分析的目的.另外,若模块子树仍然较复杂的话,则可对模块子树重复上述模块分解步骤.由模块的定义不难发现,故障树中若没有重复事件则可以任意分解模块,以减小规模简化计算.所以对这种故障树的分析不是NP困难问题.重复事件的存在却使问题复杂化了,因为从原则上说有重复事件的地方就不能模块化.为了解决这个困难,用转移事件处理.可以把模块的概念推广一步,把故障树中的重复模块(完全一样但在故障树中重复出现的模块)也分割出来单独处理,而在故障树中用重复的“准底事件”来代替它们,条件是:重复模块对于故障树其余部分和其余模块必须没有重复事件.应用重复模块的概念可以进一步提高模块分解的效率.3.3故障树的最小割集中判断转移符号是为了解决画图重复和故障树太大,一张图纸画不下整棵树的问题.故障树的某一个分支称为故障树的子树,子树可用“转向”符号代替,这个子树将在同标记的“转此”符号处展开.根据这一思想,用转移事件处理复杂故障树,以达到简化故障树分析的目的.如果要处理的故障树比较复杂,可以采用模块化方法简化计算,但是这需要较多模块才有明显的简化效果.采用转移事件来代替一棵子树可以大大简化复杂故障树的分析计算.而且当故障树中出现重复子树时,采用转移事件还可以避免画图重复.转移事件的处理过程:以一个转移事件代替一棵子树,将该转移事件画在子树所在的位置上.故障树的其它部分按正常处理,在初步的分析计算时,该转移事件按基本事件处理,则整棵故障树的最小割集中应该包含转移事件.把包含有转移所事件的故障树文件称为父文件,在其基础上派生一个文件称为派生文件,以该派生文件中的故障树表示转移事件所代表的子树.在派生文件中,底事件及中间事件的序号是以其父文件所在的故障树中的序号为基础的,这样在处理转移事件时就不会出现同序号的问题.当子树建成以后,对其进行计算分析,求出该子树的最小割集及其顶事件的发生概率,并将结果写入相应的数据文件中去,经过这样的处理之后,就可以对整棵故障树进行分析了.在对整棵故障树进行初步的分析之后,其最小割集中包含有转移事件,在进行进一步的分析时,指出转移事件所代表的子树所在文件,其缺省值为该父文件的派生文件.然后,分析该故障树的最小割集,如果某个割集中含有转移事件,则以派生文件中的最小割集来替换该转移事件,直至所有的转移事件都被替换掉.3.4先序遍历树算法模块化产生的故障树是一个子树,它包括的事件不在故障树的其它地方出现,即子树没有来自故障树其它地方的输入.故障树是一个定向的无循环图,节点是底事件或逻辑门.从定义来说,根和底事件就是模块.采用先序遍历树的算法用来寻找故障树的模块,对故障树的节点进行标记.先序遍历树的算法描述:采用先序遍历对图4所示的例子遍历的节点顺序:(Top,g1,b1,g3,b2,b3,g3,g1,g2,g3,g4,b4,b5,g4,g2,Top).可以得知故障树中的每个节点至少被遍历两次:第一次是遍历过程中开始遍历节点,第二次是由节点的右孩子返回;叶子节点只遍历一次.可以得知遍历上图是树边数的线性关系.寻找模块的基本思想:节点是一个模块当且仅当它的任何一个孩子不在第一次访问节点之前被访问并且不在节点第二次被访问后访问.1c1不是模块g3在g1第二次访问后被访问.222g不是模块g3在g2第一次访问之前被访问.3p3是一个模块b2和b3是在g3第一次访问之后和在g3第二次被访问之前被访问.4viitftnode算法描述b4和b5是在g4第一次被访问后和在g4第二次被访问前被访问.为了得知节点的孩子是否是在节点第一次被访问后和在第二次被访问前被访问需要在CFtNode类中定义以下变量和函数.定义对节点的访问在进行模块化分析时是很关键的,在第一次执行PreOrderTraverseFtree()时VisitFtNode()中mnMarkNum,mnFirstVisit,mnSecondVisit,mnLastVisit等参数的数值发生变化,为故障树模块化奠定了基础.如下就是VisitFtNode()函数中参数改变的算法描述:首先所有参数清零:遍历后节点的mnCount变量值如表1所示,表2是mnFirstVisit,mnSecondVisit,mnLastVisit的变量值.进行第二次遍历就需要求出非叶子节点的最小访问值——mnMinVisit和非叶子节点的最大访问值——mnMaxVisit.第二次遍历树算法描述:CFaultTree::SecondTraverseFTree(CFtNode*pft){GetLeftChildNode(*pft);//得到节点的最左的孩子节点;SetMinVisit();//把求得的孩子的mnFirstVisit值赋予节点的mnMinVisit变量;GetLastChildNode(*pft);//得到遍历节点的最后的孩子节点;SetMaxVisit();//把求得的孩子的mnLastVisit值赋予节点的mnMaxVisit变量;判断