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

赵相福; 黄森; 童向荣; 欧阳丹彤; 张立明; 章星林

doi:10.12263/DZXB.20211356

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法
- IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking
- 电子学报 2022年50卷第11期页码：2722-2729
- 作者机构：
  
  1.烟台大学计算机与控制工程学院,山东烟台 264005
  2.浙江师范大学计算机系,浙江金华 321000
  3.吉林大学计算机科学与技术学院,吉林长春 130012
- 作者简介：
  
  [ "赵相福男，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;62076108;62072392)
- DOI：10.12263/DZXB.20211356
  中图分类号： TP306
- 收稿：2021-10-08，
  
  修回：2022-01-20，
  
  纸质出版：2022-11-25
- 稿件说明：
移动端阅览
赵相福,黄森,童向荣等.IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J].电子学报,2022,50(11):2722-2729.

ZHAO Xiang-fu,HUANG Sen,TONG Xiang-rong,et al.IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking[J].ACTA ELECTRONICA SINICA,2022,50(11):2722-2729.
赵相福,黄森,童向荣等.IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J].电子学报,2022,50(11):2722-2729. DOI： 10.12263/DZXB.20211356.

ZHAO Xiang-fu,HUANG Sen,TONG Xiang-rong,et al.IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking[J].ACTA ELECTRONICA SINICA,2022,50(11):2722-2729. DOI： 10.12263/DZXB.20211356.

摘要

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

关键词

Keywords

references

REITER R . A theory of diagnosis from first principles [J]. Artificial Intelligence , 1987 , 32 ( 1 ): 57 - 95 .

FRIEDRICH G , STUMPTNER M , WOTAWA F . Model-based diagnosis of hardware designs [J]. Artificial Intelligence , 1999 , 111 ( 1-2 ): 3 - 39 .

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 .

WOTAWA F . A variant of Reiter's hitting-set algorithm [J]. Information Processing Letters , 2001 , 79 ( 1 ): 45 - 51 .

姜云飞 , 林笠 . 用对分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)

姜云飞 , 林笠 . 用布尔代数方法计算最小碰集 [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)

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 .

刘思光 , 欧阳丹彤 , 张立明 . 极小碰集求解中候选解极小性判定方法 [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)

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 .

刘娟 , 欧阳丹彤 , 王艺源 , 等 . 结合特征学习的粒子群求解极小碰集方法 [J]. 电子学报 , 2015 , 43 ( 5 ): 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 ( 5 ): 841 - 845 . (in Chinese)

何嫱君 , 赵相福 , 欧阳丹彤 , 等 . 极小碰集求解算法的性能分析与比较 [J]. 电子学报 , 2019 , 47 ( 5 ): 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 ( 5 ): 1101 - 1110 . (in Chinese)

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

结合问题特征利用SE-Tree反向深度求解冲突集的方法

结合电路结构基于分块的诊断方法