一种基于Petri网模型求解故障树最小割集的算法

Petri网作为一种动态的图形化建模工具,可用于表达系统的逻辑关系和描述系统的动态行为,文中利用Petri网的这一特点对故障树进行建模,并在此基础上提出了一种新的求解故障树最小割集的算法,最后以实例说明了这一求解过程.该算法与以往方法相比,提高了执行效率,且可同时得到最小路集,为系统的可靠性分析工作提供了一种新的途径.     

故障树最小割集技术在软件测试中的应用

笔者提出将故障树分析技术应用在软件测试中,通过分析软件系统结构,以软件程序的各子模块为事件建立软件故障模型并对模型进行定性分析,利用最小割集算法分析模块重要性次序,找出软件关键模块和故障组合模块,将分析结果应用于软件测试,提高软件测试针对性,发现软件潜在缺陷,降低产品失效风险,以达到提高软件可靠性的目的。     

基于故障树最小割集的故障诊断方法研究

利用故障树分析原理，对基于故障树最小割集的诊断方法进行了研究。在给出故障树顶事件和底事件概率描述的基础上，计算了故障树最小割集的重要度，并在量级上进行了分析比较，为系统的故障源搜寻提供了具体有效的测试步骤。并给出了应用实例。     

基于最小割集的安全性测试用例的动态生成

利用故障树的原理和方法,对基于故障树最小割集的安全性测试用例动态生成进行了研究.首先阐述了故障树和故障树最小割集的概念及数学描述,然后给出了故障树最小割集的生成算法,最后在此基础上提出了基于故障树最小割集的动态生成安全性测试用例的算法.     

基于故障树最小割集和最小路集的诊断方法研究

利用故障树的原理和方法,对基于故障树最小割集和最小路集的诊断方法进行了研究。首先给出了故障树最小割集和最小路集的数学描述,在此基础上开发了基于故障树最小割集和最小路集的诊断推理策略,最后提出了测点配置和优化的方法。     

一种求解最小割集问题的新思路

最小割集问题与最大流问题本质上是同一个问题，由于后者的实用性更强，人们对它投入的关注与研究也就更多，实际中，多通过最大流问题来求最小割集问题。本文首先介绍了最大流、最小割集的相关概念，然后，从实际应用出发，提出了一种用最大流求流图最小割集的新算法，而后证明了该算法的正确性，并举例说明了这种算法思想在其它方面的应用。     

基于Petri网的系统最小割集求解

针对以往用Petri网求系统最小割集广泛采用分析库所的方法,证明了通过分析模型的变迁能够减少运算量,提出了组成系统最小割集的变迁序列的组合算法,并通过状态方程求取最小割集,最后通过实例验证了算法的正确性和简便性.     

由不交化矩阵求最小割集的改进算法

利用早期不交化法求解最小割集是目前进行故障树定性分析的一种有效方法。但不交化最小割集矩阵行数随着故障树规模的大小呈指数增长,对于数万乃至数百万行的不交化矩阵求解最小割集的过程就会慢得让人无法接受。通过对原算法的分析和改进,采用静态指针法建立动态数组,避免了原算法最耗时间的对不交化矩阵的排序运算。通过与原算法的对比分析,结果验证了本算法的有效性。     

求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

A simple method to derive minimal cut sets for a non-coherent fault tree

Minimal cut sets (or prime implicants: minimal combinations of basic event conditions leading to system failure) are important information for reliability/safety analysis and design. To obtain minimal cut sets for general non-coherent fault trees, including negative basic events or multi-valued basic events, a special procedure such as the consensus rule must be applied to the results obtained by logical operations for coherent fault trees, which will require more steps and time. This paper proposes a simple method for a non-coherent fault tree, whose top event is represented as an AND combination of monotonic sub-trees. A "monotonic" sub-tree means that it does not have both positive and negative representations for each basic event. It is proven that minimal cut sets can be obtained by a conventional method for coherent fault trees. An illustrative example of a simple event tree analysis shows the detail and characteristics of the proposed method.     

故障树分析中底事件排序问题的研究

基于BDD的故障树分析方法是先将故障树转换为BDD,而后进行分析.在转换的过程中,底事件的排序尤其重要,直接影响到后面的分析.研究了底事件的排序问题,将运用于数字电路的化简方法运用底事件的排序中,实例证明,可使转换后的BDD结点数比采用随机的底事件顺序产生的BDD的结点数减少一半以上,甚至可以减少到最少.     

基于改进连续时间动态系统的模拟SAT求解器

针对布尔可满足性问题的高效求解进行了研究。首先,通过对k-SAT问题和基于耦合常微分方程形式的确定性连续时间动态系统的分析,提出了一种基于时延信息形式的改进连续时间动态系统方程,以保持集中搜索特性;然后,提出了实现该系统方程的三个主要组件即信号动态电路、辅助变量电路和数字验证电路的模拟设计。在信号动态电路的设计中,设计了一种获得更高性能、更小面积和更低功耗的模拟硬件形式;在提出的辅助变量电路和数字验证电路的模拟硬件设计中,实现了避免梯度下降搜索陷入无解和确定给定问题的解是否已经找到的目标;同时提出了降低面积和功耗的可替代辅助变量电路的两种设计方案。仿真实验结果表明,提出的新的模拟SAT求解器不仅是有效的,而且相比于单一软件算法实现的SAT求解器和其他硬件类SAT求解器具有更高的加速性能和更低的功耗。     

改进的最小割集生成算法与联锁系统模型的安全性测试*

为保证铁路联锁模型的安全性,在故障分析法的基础上提出一种新的用Petri网来建立故障树的方法,动态地描述铁路联锁系统的安全性需求,并根据Petri网安全需求模型的可达标志图,提出一种能自动生成最小割集的算法。根据算法生成的最小割集,设计了一个联锁安全检测器,用于检测和控制联锁系统模型处于安全状态。最后用CPN工具对所建立的联锁系统模型进行仿真,仿真结果表明联锁安全检测器能够保证模型的安全性。     

基于故障树分析的软件安全性测试研究

针对软件安全性测试的本质特征在于快速降低由于软件失效而导致系统事故的风险, 结合基于Baye-sian统计理论的测试方法, 建立一套构建安全性测试剖面, 并由此产生测试用例的测试方法。该方法运用故障树分析技术, 对各模块发生故障对系统安全性的影响进行分析, 找出影响较大的关键性模块, 然后利用分析结果构建安全性测试剖面。最后给出了测试停止的标准。通过对例子的分析可知, 本方法在快速降低软件事故风险方面比现有软件测试方法更有效。     

Boolean difference techniques in fault tree analysis

For an electrical, mechanical, or hybrid system described diagramatically as a network of interconnected components, fault tree modeling of system reliability as a function of individual component failure probabilities gives rise to logic expressions obtained from the network connections. Application of the method of Boolean differences in the analysis of such Boolean expressions is discussed, and it is shown that the influence of the status of specific components on the reliability of the total system may be investigated by straightforward algebraic operations on the network failure function.     

Reliability Analysis of Systems Described by Fault Trees with Efficiency

A fault tree model is proposed that describes a structure and functioning of systems with different levels of operation quality. Approximate analytical and statistical methods for evaluation of reliability characteristics of such system are developed. An appropriate software is worked out.     

故障树转化为二元决策树的算法研究

故障树分析法在实施过程中会遇到计算量大的问题,二元决策图是解决这个问题的一种新途径。故障树转化为二元决策图涉及的一个关键问题就是对基本事件的排序,但是基本事件排序是一个NP问题。为了解决这个问题提出了一个将故障树转化为二元决策图的启发式算法,此算法既避免了基本事件排序这个难题,同时又充分考虑了故障树的具体结构,使得到的二元决策图尽量的简单。     

用时序和逻辑规则形成动态故障树的紧缩Markov链

针对枚举底事件的所有时序状态来形成Markov链的弊端,借鉴静态故障树的最小割集(minimum cut set, MCS)思想,考虑形成紧缩的Markov链（即最简顺序割集）。其重要目的是剔除冗余的Markov链,在保证不影响系统失效分析的同时减小状态空间,最大限度地避免陷入组合爆炸的危险。其显著特点在于用时序规则和逻辑规则来描述动态逻辑门。以此为基础,用BDD（binary decision diagram）技术首先形成基于逻辑规则的动态系统的MCS,其次对每个MCS运用时序规则,组合成必要的Mark