(College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
出版日期:
2018-11-01基金资助:
国家自然科学基金项目(61672261,61502199,61402196,61373052,61872159)Algorithm of Computing Minimal Conflict Sets Based on the Structural Feature of Fault Output
Xu Yini, Ouyang Dantong, Liu Meng, Zhang Liming, Zhang Yonggang(吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (jlxuyini@126.com)
Online:
2018-11-01摘要/Abstract
摘要: 基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障输出结构特征的极小冲突求解算法MCS-SFFO:首先对CSRDSE算法的剪枝规则进行了改进,避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问;其次,提出故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;最后,提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝,减少了调用SAT求解器的次数.实验结果表明:与CSRDSE算法相比,MCS-SFFO算法求解效率明显提升.
参考文献
相关文章 9
[1] | 欧阳丹彤, 高菡, 徐旖旎, 张立明. 结合故障逻辑关系的极小冲突集求解方法[J]. 计算机研究与发展, 2020, 57(7): 1472-1480. |
[2] | 田乃予,欧阳丹彤,刘梦,张立明. 基于子集一致性检测的诊断解极小性判定方法[J]. 计算机研究与发展, 2019, 56(7): 1396-1407. |
[3] | 王荣全,欧阳丹彤,王艺源,刘思光,张立明. 结合DOEC极小化策略的SAT求解极小碰集方法[J]. 计算机研究与发展, 2018, 55(6): 1273-1281. |
[4] | 欧阳丹彤,智华云,刘伯文,张立明,张永刚. 基于伪故障度生成枚举树的极小诊断求解方法[J]. 计算机研究与发展, 2018, 55(4): 782-790. |
[5] | 邓召勇,欧阳丹彤,耿雪娜,刘杰. 基于动态极大元素覆盖值的极小碰集求解算法[J]. 计算机研究与发展, 2018, 55(4): 791-801. |
[6] | 欧阳丹彤,周建华,刘伯文,张立明. 基于模型诊断中结合问题特征的新方法[J]. 计算机研究与发展, 2017, 54(3): 502-513. |
[7] | 欧阳丹彤,贾凤雨,刘思光,张立明. 结合互补度的基于扩展规则#SAT问题求解方法[J]. 计算机研究与发展, 2016, 53(7): 1596-1604. |
[8] | 刘思光,欧阳丹彤,王艺源,贾凤雨,张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. |
[9] | 王艺源,欧阳丹彤,张立明,张永刚. 利用CSP求解极小碰集的方法[J]. 计算机研究与发展, 2015, 52(3): 588-595. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3806