一种基于ZBDD求解大型故障树的基本事件排序方法

刘萍 吴宜灿 李亚洲 王海涛 胡丽琴 张士杰 麻晓敏 聂淼 袁润
中国科学院等离子体物理研究所,安徽合肥230031

文章摘要:如何提高大型故障树分析效率一直是研究人员致力于的一个热点问题。近年提出的基于ZBDD的分析方法是一种比较有效的大型故障树求解方法。本文从ZBDD结构和将故障树转换成ZBDD的特点人手，分析了基本事件的排序对ZBDD结构的影响，并结合BDD基本事件排序的当前研究成果，设计了一种基于ZBDD求解大型故障树基本事件的排序方法，并经过反复测试和比较分析，证明了这个方法的有效性。
文章主题:零压缩二元决策图 概率截断 排序方法 最小割集

文章内容：第27卷2007年第3期9月核科学与工程1.27.3.2007一种基于求解大型故障树的基本事件排序方法刘萍,吴宜灿,李亚洲,王海涛,胡丽琴,张士杰,麻晓敏,聂淼,袁润(中国科学院等离子体物理研究所,安徽合肥230031)摘要:如何提高大型故障树分析效率一直是研究人员致力于的一个热点问题.近年提出的基于的分析方法是一种比较有效的大型故障树求解方法.本文从结构和将故障树转换成的特点人手,分析了基本事件的排序对结构的影响,并结合基本事件排序的当前研究成果,设计了一种基于求解大型故障树基本事件的排序方法,并经过反复测试和比较分析,证明了这个方法的有效性.关键词:零压缩二元决策图;概率截断;排序方法;最小割集中图分类号:61文献标识码:文章编号:0258—0918(2007)03—0282-07--,—,—,—,—,-,—,,(,,.230031.);—.-—..,,..:—;;:收稿日期:2007—05—10;修回日期:2007—08～1作者简介:刘萍(1963),女,江西人,教授,硕士导师,从事概率安全分析软件研发相关工作282大型故障树分析计算量大且割集繁多,需耗费大量的计算时间和内存资源.因此,如何在有限的计算资源内提高分析效率一直是该研究领域的一个难题.尽管在分析流程上可以通过故障树计算前的逻辑化简,模块化等预处理操作一定程度上提高分析效率,但提高大型故障树分析效率的关键还是如何解决最小割集的计算和存储问题[1].故障树最小割集计算的本质是利用布尔规则按一定的树遍历方式进行布尔运算.目前,理论和实践均证明二元决策图(,)是一种能够比较有效地表达和处理布尔函数的数据结构[2].是布尔表达式真值表的压缩编码形式,于2世纪6年代由首次提出[5],并于1993年由.引入到故障树分析领域中且重新构建了完整的故障树分析框架[6].有两个特性:一是它是一种可以通过共享子图方式来压缩的图;二是在上操作的结果可以保留,因此一个操作无需进行两次.这两个特性使得能对布尔表达式进行有效的管理,而且基于可以计算出系统失效的精确概率.尽管如此,的规模仍然是随着故障树的基本事件数目指数增长的[7].对于大规模的故障树特别是核电站的故障树来说,模型中包含成百上千的基本事件,结构仍然需要耗费大量的存储资源,因此方法在处理核电工业这样大规模的复杂故障树时仍然是有困难的..于2005年总结了解决该问题的两种思路[8]:一是使用(—)来求解(-,即最小割集)的算法,即/方法[9;二是设计基本事件排序方法来降低结构的复杂性[1].是.于1992年提出的一种专门用于存储稀疏集合(即集合中元素的数量比全集中元素数量少的多)的数据结构[1.可以省略因为布尔变量置为1时而导致布尔函数的输出为0的节点,从而较大的提高了存储效率,因此可以用相对小的编码大量的割集[1.与不同的是,的中间结果可以进行布尔化简,概率截断和阶数截断等操作.因此可以利用该特性提前舍去不符合要求的割集,从而减小结构的规模,使得大规模故障树的分析成为可能.类似于,使用求解故障树首先也必须为基本事件选择一种排序,然后再将故障树转换为进行计算.而且与相同,结构的规模也是和基本事件排序密切相关的,排序方法直接影响着故障树求解的效率.对于同一棵故障树使用不同的排序方法,获得结果的规模可能相差超过几十倍ⅲ.基于的基本事件排序方法已研究了很多,但是针对的排序方法研究还比较少.根据的特性和大型故障树的特点,设计了一种基于求解大型故障树的基本事件排序方法,并给出了运用此方法的测试结果.1基于故障树分析方法的特点分析的结构和故障树转化为的过程,基于故障树分析方法具有三个显着特点:1)是对割集的直接编码,其左分支决定了割集的数目,右分支决定了割集的阶数.为了使形成的尽量小,则割集中共享基本事件应尽可能的出现在靠近根节点的位置.2)展开过程中可以对中间结果不断进行概率截断,阶数截断和布尔化简,从而减小的中间规模及最后规模,这一特性对于大型故障树求解来说是非常重要的.3)用/方法分析大型故障树的最小割集时,产生的中间节点数目可能会比最后结果的节点数目大得多.如对于163291个门,689个基本事件的某电站的实际故障树模型进行定性分析,若概率截断为1.0×10-1,阶数截断为8,则最小割集数目是8195,采用自顶向下,左边优先的排序方法,可以得到最后的的大小是10222,但在计算过程中产生中间节点数目却是3313222.这对故障树分析的效率影响是非常大的.因此,在研究283的基本事件排序方法时,不仅要考虑结果的规模,而且更要考虑计算过程中产生的中间节点数目.2基于姗的基本事件排序方法根据基于故障树分析方法的特点,并结合经典排序方法的研究成果,本文设计了一种适合的基本事件排序方法:第一步按下列原则调整门的输入:,将基本事件输入放在门的最左边;,对于两个基本事件输入,使用次数多的放在左边;,若使用次数相同,则将发生概率小的基本事件放在左边.第二步采用自顶向下,自左向右的方式遍历故障树,按照遍历到的顺序对故障树的基本事件进行排序.方法分析:1)对"与门"而言,基本事件输入排序靠前,可以获得更小的;而对"或门"而言,无论基本事件输入放在什么位置,其结果都是相同的.如图1的简单故障树,若将基本事件放在左边,基本事件排序为&;&;,对应的如图1所示,只有3个节点;若将基本事件放在右边如图2,基本事件排序为&;&;,对应的有4个节点,如图2所示.()图1"与门"的基本事件放在左边的情形.1-()图2"与门"的基本事件放在右边的情形.2—2)可充分利用的中间结果可以进行截断的特点,在排序时考虑事件的发生概率.284如图3的故障树,它的基本事件排序是&;&;&;,若事件的发生概率是1.0×10～,事件的发生概率是1.0×10.,截断概率为1.0×10一,则在计算顶事件时,第一步,创建(,1,0)并判断的发生概率是否小于截断概率,此时的概率是大于截断概率;要执行第二步,创建(,,)并判断的发生概率是否小于截断概率,此时的概率小于截断概