基于异常概率和位置标记的极小冲突集求解方法研究

发布时间：2020-10-28 09:23

　　 基于模型诊断是人工智能领域的热门研究课题,弥补了传统诊断方法的多种不足。其理论研究成果丰硕,并广泛应用于实际生产中,加快了人工智能的发展速度。通常分两步对其求解:首先,求解给定电路系统的全部极小冲突集;然后,求解全部极小冲突集的全部极小碰集,即为给定电路系统的全部极小诊断解。可满足问题(SAT)是经典的NP问题,其理论研究及技术应用发展成熟。很多问题都可以转化为可满足问题求解。国际上定期举办的SAT问题竞赛,使SAT求解器得到了快速的发展。因此,把极小冲突集求解问题转化为SAT问题是一个很好的研究方向。CSRDSE方法是一种结合SAT问题求解极小冲突集的方法。根据枚举树结构特点及冲突集相关推论,对枚举树中非冲突集的真子集节点及冲突集的真超集节点进行剪枝,减少访问节点数量,加快了问题的求解。本文在深度研究CSRDSE方法的基础上,根据对电路结构的分析,发现每个元件异常时对异常输出的影响程度不同,与电路系统异常输出端相关联的元件对异常输出的影响程度更大,且对异常输出影响较大的元件之间的组合更可能是冲突集。根据上述发现,提出了基于异常概率的极小冲突集求解方法(CSABP)。首先,给出了异常概率的定义,并给出了计算元件异常概率的算法SolveABP;然后,按照元件异常概率由大到小的顺序生成枚举树,能够先遍历对异常输出影响较大的元件构成的节点,以至于尽快的找到冲突集,减少对冲突集超集节点的判断。实验结果表明,与CSRDSE方法相比,CSABP方法提高了问题求解效率。在CSABP方法的基础上,结合枚举树的结构特性和冲突集的子集更可能是极小冲突集的原理发现:将冲突集中的元件在枚举树第一层的节点连同其子树一起向左移动,提前搜索这些子树,有利于提早找到极小冲突集。在判断后续节点时,先将当前访问节点同已找到的冲突集作对比,若是某个冲突集的超集,可免去对该节点进行判断;否则,调用求解器判断该节点的冲突性。基于上述想法,提出了位置标记的概念,用来调整枚举树状态的变化。最后,将异常概率与位置标记方法结合在一起,提出了基于异常概率和位置标记的极小冲突集求解方法(CSABPPM)。实验结果表明,CSABPPM方法减掉了更多的冗余节点,更好的解决了极小冲突集求解问题。
【学位单位】：吉林大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP18
【文章目录】：
摘要
abstract
第1章 绪论
    1.1 研究背景和意义
    1.2 研究现状
    1.3 本文工作
第2章 基本知识
    2.1 基于模型诊断问题
    2.2 可满足问题
    2.3 电路问题转化为SAT问题
    2.4 本章小结
第3章 极小冲突集求解方法介绍
    3.1 基于CSSE-tree的极小冲突集求解方法
        3.1.1 相关推论及概念
        3.1.2 CSSE-tree基本思想
        3.1.3 CSSE-tree方法分析
    3.2 基于CSISE-tree的极小冲突集求解方法
        3.2.1 相关概念
        3.2.2 CSSE-tree基本思想
        3.2.3 CSSE-tree方法分析
    3.3 基于反向深度搜索的极小冲突集求解方法
        3.3.1 相关概念
        3.3.2 CSRDSE基本思想
        3.3.3 CSRDSE方法
        3.3.4 CSRDSE方法分析
    3.4 本章小结
第4章 基于异常概率的极小冲突集求解方法
    4.1 预备知识
    4.2 方法思想
    4.3 方法实现
    4.4 实验结果及分析
    4.5 本章小结
第5章 基于位置标记的极小冲突集求解方法
    5.1 预备知识
    5.2 方法思想
    5.3 方法实现
    5.4 实验结果及分析
    5.5 本章小结
第6章 总结和展望
    6.1 工作总结
    6.2 工作展望
参考文献
作者简介及在学期间所取得的科研成果
致谢

【相似文献】

相关期刊论文 前10条

1 方敏;一种识别最小冲突集的实用方法[J];合肥工业大学学报(自然科学版);1999年01期

2 刘晓平;季浩;石慧;;一种基于最小冲突集的约束冲突消解方法[J];工程图学学报;2010年02期

3 姜云飞,林笠;用对分HS-树计算最小碰集[J];软件学报;2002年12期

4 栾尚敏,戴国忠,陈由迪;基于逻辑的一种诊断方法[J];贵州工业大学学报(自然科学版);2002年04期

5 王艺源;欧阳丹彤;张立明;张永刚;;利用CSP求解极小碰集的方法[J];计算机研究与发展;2015年03期

6 张立明;欧阳丹彤;赵相福;;一种基于ATMS的求解所有极小冲突集的新方法[J];计算机工程与科学;2007年11期

7 栾尚敏,戴国忠;利用结构信息的故障诊断方法[J];计算机学报;2005年05期

8 徐旖旎;欧阳丹彤;刘梦;张立明;张永刚;;结合故障输出结构特征的极小冲突求解算法[J];计算机研究与发展;2018年11期

9 潘理;郑红;刘显明;杨勃;;基于Petri网局部性的极大冲突集枚举算法[J];电子学报;2016年08期

10 刘燕丽;李初民;何琨;;基于优化冲突集提高下界的MAXSAT完备算法[J];计算机学报;2013年10期

相关博士学位论文 前1条

1 邵继业;基于模型的故障诊断方法研究及在航天中的应用[D];哈尔滨工业大学;2009年

相关硕士学位论文 前10条

1 陶娅;基于异常概率和位置标记的极小冲突集求解方法研究[D];吉林大学;2019年

2 刘伯文;结合问题特征的基于模型诊断相关问题研究[D];吉林大学;2018年

3 凡义;基于松弛冲突集改进Max-SAT完备算法[D];华中科技大学;2016年

4 徐俊洁;一种基于模型的故障诊断系统研究与实现[D];大连海事大学;2010年

5 常伟;基于角色的访问控制技术研究与应用[D];南京航空航天大学;2012年

6 何士玉;基于模型诊断的搜索算法研究及其在配电网中的应用[D];西南交通大学;2013年

7 张立明;基于一致性诊断中若干问题研究[D];吉林大学;2009年

8 云帆;求解极小碰集的遗传算法及其相关算法的研究[D];吉林大学;2007年

9 高松;牵引供电系统故障的基于模型诊断方法研究[D];西南交通大学;2015年

10 艾阳;求解极小碰集的ROBDD算法的研究与分析[D];吉林大学;2011年

本文编号：2859898