IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法

doi:10.12263/DZXB.20211356

电子学报

• • 上一篇

IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法

赵相福¹, 黄森², 童向荣¹, 欧阳丹彤³, 张立明³, 章星林²

^1.烟台大学计算机与控制工程学院, 山东烟台 264005
^2.浙江师范大学计算机系, 浙江金华 321000
^3.吉林大学计算机科学与技术学院, 吉林长春 130012

收稿日期:2021-10-08 修回日期:2022-01-20
作者简介:赵相福男， 1981年出生于山东省济宁市.烟台大学教授、研究生导师，研究方向为基于模型的故障诊断、智能诊断推理、区块链等.E-mail：xiangfuzhao@163.com
黄森男，1995年出生于山东省枣庄市.浙江师范大学计算机学院研究生，主要研究方向为基于模型的故障诊断.E-mail：hs_huangs@163.com
童向荣男，1975年出生于山东省烟台市.烟台大学教授、研究生导师，研究方向为计算机科学、智能信息处理、社交网络等.E-mail：xr_tong@163.com
欧阳丹彤女，1968年出生于吉林省长春市.吉林大学教授、博士生导师，研究方向为基于模型的故障诊断、自动推理等.E-mail：ouyd@lu.edu.cn
张立明男，1980年出生于吉林省长春市.吉林大学教授、研究生导师，研究方向为基于模型的故障诊断、自动推理等.E-mail：limingzhang@jlu.edu.cn
章星林女，1997年出生于安徽省安庆市.浙江师范大学计算机学院研究生，研究方向为基于模型的故障诊断.E-mail：xinglinzhang2022@163.com
基金资助:
国家自然科学基金面上项目(61972360)

IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

ZHAO Xiang-fu¹, HUANG Sen², TONG Xiang-rong¹, OUYANG Dan-tong³, ZHANG Li-ming³, ZHANG Xing-lin²

^1.School of Computer and Control Engineering，Yantai University，Yantai，Shandong 264005，China
^2.Department of Computer，Zhejiang Normal University，Jinhua，Zhejiang 321000，China
^3.College of Computer Science and Technology，Jilin University，Changchun，Jilin 130012，China

Received:2021-10-08 Revised:2022-01-20

摘要/Abstract

摘要：

基于模型的诊断推理是人工智能领域的一个重要分支.其中由冲突部件集产生所有极小碰集是基于模型诊断推理的重要一步.根据布尔算法的特征，所有的冲突集可以划分为左右两个子集合簇，且左分支集合簇恰好为右分支集合簇的子集，这为由左分支增量产生右分支极小碰集提供了理论基础；另外，在自底向上增量归并元素的过程中，结合局部独立覆盖策略可以直接增量产生所有的极小碰集，从而避免非极小碰集和相同极小碰集的冗余产生.理论上，右分支解集可由左分支解集增量方法产生，避免了碰集中大量元素的重复计算.大量实验结果表明：本文提出的算法比之前的布尔算法及相关改进算法都具有显著的效率提升，最高可达约5倍.

关键词: 基于模型诊断, 诊断推理, 极小碰集, 布尔算法, 冲突集, 增量方法

Abstract:

Model-based diagnostic reasoning is an important research branch in the field of artificial intelligence. Generating all minimal hitting-sets(MHSs) from conflict sets is a crucial step in the process of model-based diagnostic reasoning. To solve this problem, all conflict sets are divided into left and right parts according to the Boolean algorithm, and the left cluster is just a subset of the right one, which provides a theoretical foundation for incrementally generating the right MHSs from the left ones. In addition, in the process of incrementally merging branch elements from bottom to top, with the help of the local independence cover checking strategy, all MHSs can be directly produced without generating any redundant non-MHSs and duplicated MHSs. Theoretically, the right branch solution can be incrementally generated by the left one. Experimental results show that the efficiency of the proposed algorithm is significantly improved by about five times, compared with the classical algorithm based on Boolean algorithm and its related improved algorithms.

Key words: model-based diagnosis, diagnostic reasoning, minimal hitting-set, Boolean algorithm, conflict sets, incremental method

中图分类号:

TP306

赵相福, 黄森, 童向荣, 欧阳丹彤, 张立明, 章星林. IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J]. 电子学报, DOI: 10.12263/DZXB.20211356.

ZHAO Xiang-fu, HUANG Sen, TONG Xiang-rong, OUYANG Dan-tong, ZHANG Li-ming, ZHANG Xing-lin. IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking[J]. Acta Electronica Sinica, DOI: 10.12263/DZXB.20211356.

图/表 3

参考文献 11

1	REITER R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32(1): 57-95.
2	FRIEDRICH G, STUMPTNER M, WOTAWA F. Model-based diagnosis of hardware designs[J]. Artificial Intelligence, 1999, 111(1-2):3-39.
3	GREINER R, SMITH B A, WILKERSON R W. A correction to the algorithm in Reiter's theory of diagnosis[J]. Artificial Intelligence, 1989, 41(1): 79-88.
4	WOTAWA F. A variant of Reiter's hitting-set algorithm[J]. Information Processing Letters, 2001, 79(1): 45-51.
5	姜云飞, 林笠. 用对分HS-树计算最小碰集[J]. 软件学报, 2002, 13(12): 2267-3374.
	JIANG Yun-fei, LIN Li. Computing the minimal hitting set with binary HS-Tree[J]. Journal of Software, 2002, 13(12): 2267-3374. (in Chinese)
6	姜云飞, 林笠. 用布尔代数方法计算最小碰集[J]. 计算机学报, 2003, 26(8): 919-924.
	JIANG Yun-fei, LIN Li. The computation of hitting sets with Boolean formulas[J]. Chinese Journal of Computers, 2003, 26(8): 919-924. (in Chinese)
7	PILL I, QUARITSCH T. Optimizations for the Boolean approach to computing minimal hitting sets[C]//Proceedings of the 20th European Conference on Artificial Intelligence, 2012, 648-653.
8	刘思光, 欧阳丹彤, 张立明. 极小碰集求解中候选解极小性判定方法[J]. 软件学报, 2018, 29(12): 3733-3746.
	LIU Si-guang, OUYANG Dan-tong, ZHANG Li-ming. Minimization of candidate solutions in minimal hitting sets solution[J]. Journal of Software, 2018, 29(12): 3733-3746. (in Chinese)
9	ZHAO Xiang-fu, OUYANG Dan-tong. Deriving all minimal hitting sets based on join relation[J]. IEEE Transactions on Systems Man Cybernetics System, 2015, 45(7): 1063-1076.
10	刘娟, 欧阳丹彤, 王艺源, 等. 结合特征学习的粒子群求解极小碰集方法[J]. 电子学报, 2015, 43(05): 841-845.
	LIU Juan, OUYANG Dan-tong, WANG Yi-yuan, et al. Computing minimal hitting sets with particle swarm optimization combined characteristics learning[J]. Acta Electronica Sinica, 2015, 43(05): 841-845. (in Chinese)
11	何嫱君, 赵相福, 欧阳丹彤, 等. 极小碰集求解算法的性能分析与比较[J]. 电子学报, 2019, 47(05): 1101-1110.
	HE Qiang-jun, ZHAO Xiang-fu, OUYANG Dan-tong, et al. Performance analysis and comparison of algorithms for generating minimal hitting sets[J]. Acta Electronica Sinica, 2019, 47(05): 1101-1110. (in Chinese)

[1]	欧阳丹彤, 刘伯文, 刘梦, 张立明, 张永刚. 结合电路结构基于分块的诊断方法[J]. 电子学报, 2018, 46(7): 1571-1577.
[2]	欧阳丹彤, 刘伯文, 周建华, 张立明. 结合问题特征利用SE-Tree反向深度求解冲突集的方法[J]. 电子学报, 2017, 45(5): 1175-1181.
[3]	潘理, 郑红, 刘显明, 杨勃. 基于Petri网局部性的极大冲突集枚举算法[J]. 电子学报, 2016, 44(8): 1858-1863.
[4]	徐勇, 毋国庆, 袁梦霆. 结合Craig插值分析的软件错误诊断方法[J]. 电子学报, 2016, 44(10): 2514-2521.
[5]	刘娟, 欧阳丹彤, 王艺源, 张立明. 结合特征学习的粒子群求解极小碰集方法[J]. 电子学报, 2015, 43(5): 841-845.
[6]	赵相福;欧阳丹彤;. 使用SAT求解器产生所有极小冲突部件集[J]. 电子学报, 2009, 37(4): 804-810.

IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法

IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 11

相关文章 6

编辑推荐

Metrics