一种基于ATMS的求解所有极小冲突集的新方法

在Reiter算法的基础上,本文提出一种基于ATMS的求解所有极小冲突集的新方法。其中,对每个元件模型最多调用一次就可求出所有的极小冲突集,防止了ATMS的多次调用,因而能够提高效率。本文提出了极小依赖集的概念,并据此对ATMS求得的极小冲突集进行了分类;分析了算法的复杂度,并将新方法与相关工作进行了比较。该算法程序容易编制,而且效率高。

CIMHS:基于优化增量策略求解极小碰集的方法

在基于模型的诊断推理过程中,极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上,充分考虑它们与新增冲突集中元素的关系,提出一种新型的优化增量策略.在原有极小冲突集簇中,首先通过启发式策略抽取部分集合进行极小化,从而大幅度缩短求解时间;然后通过优化的增量策略快速补全并更新解集,进而提高整体求解效率.为进一步提高算法的效率,提出按冲突集的势从小到大增量排序,利用新型优化的增量策略依次递归计算,并最终求得原始问题集合簇所有解集的全增量算法CIMHS(Complete Increment Minimal Hitting Set).实验结果表明,在许多情形下,CIMHS算法较其他经典的极小碰集求解算法,可减少1至3个数量级的运行时间.

基于动态极小势参数矩阵求解极小碰集的方法

在基于模型的故障诊断与测试过程中,求解极小碰集是诊断与测试的一个关键步骤,极大地影响了故障诊断的最终效率。鉴于此,提出一种基于动态极小势的参数矩阵计算极小碰集的新算法JMatrix,利用参数矩阵描述冲突集合簇中元素与集合的关系,每次动态选取当前矩阵中势最小的集合进行分解,将大问题逐步分解成规模更小的子问题,并在碰集求解过程中通过加入剪枝策略和启发式信息,避免了对无解空间的搜索;在对每一个碰集进行极小化时,根据原始冲突集合簇的矩阵特性,可以快速地找到特定元素所在的集合,从而加快极小化的速度。实验结果表明,所提算法JMatrix不但在大量人工测试数据集上较其他经典极小碰集求解算法具有更高的效率,而且在国际基准ISCAS-85电路数据集上仍具有高效稳定的性能。

用CHS-tree基于集合势的方法计算极小碰集

在基于模型的故障诊断理论中,为了根据所有冲突部件集计算全体极小碰集,提出基于集合势的方法,每次选择当前集合簇中势最小的集合进行扩展,并借助集合簇中元素出现的频率作为辅助判断,不断将大问题逐渐分解成子问题,然后依次求出不包含该扩展集合中各元素的集合簇的所有极小碰集。实验结果表明,CHStree方法生成树的过程较简单,能产生较少的节点,比经典的碰集树方法、二分法和集合枚举法等具有更高的求解效率。在某些情况下,其效率也高于当前效率最高的Boolean方法。

基于动态极大元素覆盖值的极小碰集求解算法

在基于模型诊断(model-based diagnosis,MBD)中,因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果,所以利用所有极小冲突集构造极小冲突集合簇,并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖值求解极小碰集的新算法.该算法按照元素的元素覆盖值从大到小的顺序依次处理元素,并在求解碰集的过程中加入启发式策略和剪枝策略,使得搜索空间极大减少;利用邻接链表存储输入的极小冲突集合簇,邻接链表相对于用矩阵作为存储结构有较好的空间开销且通过邻接指向能快速地找到元素可以覆盖的集合簇中的元素;每得到一个碰集便使用极小碰集判定规则进行筛选,因此算法结束时可以产生而且仅产生所有的极小碰集.实验结果表明该算法有较高的计算效率.

结合故障输出结构特征的极小冲突求解算法

基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障输出结构特征的极小冲突求解算法MCSSFFO:首先对CSRDSE算法的剪枝规则进行了改进,避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问;其次,提出故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;最后,提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝,减少了调用SAT求解器的次数.实验结果表明:与CSRDSE算法相比,MCS-SFFO算法求解效率明显提升.

基于ATMS的冲突识别及诊断测量方法

依据General Diagnostic Engine(GDE)思想并基于Assumption-based Truth Mainte-nance System(ATMS)技术实现了一种产生所有极小冲突集的方法,并通过定义负节点和新的规则解决了ATMS在使用时完备性丢失的问题。在此基础上实现了基于粗略概率的简化熵诊断测量方法,并提出了基于动态ε策略的简化熵测量方法及测量后动态更新诊断结果的算法。该方法通过环境的传播进行增量的计算,具有正确性、完备性、一致性、极小化的特点,并减小了测量时产生的诊断代价,具有较强的通用性,易于实现和扩展。

利用结构信息的故障诊断方法

基于模型的故障诊断方法是重要的故障诊断方法之一,该方法主要的问题就是如何求得所有的诊断.该文利用系统的结构信息,给出了求极小冲突集的一个算法,证明了算法的正确性,分析了算法的复杂性;然后介绍了如何由极小冲突求得诊断.其次,还给出了利用结构信息直接求诊断的一个算法,证明了其正确性.最后与相关工作进行了比较.该文给出的算法,对于一些特殊结构的系统可在多项式时间内结束.

基于逻辑的一种诊断方法

基于逻辑的故障诊断方法中一个没有解决好的问题就是如何求得所有极小冲突集。讨论了如何由极小不协调子集求得极小冲突集 ,然后给出了求所有极小不协调子集的一种方法。对如何应用该算法求得所有的极小冲突集 ,给出了求诊断的一个过程 ,最后与相关工作进行了比较。