电子学报

• • 上一篇    

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

赵相福1, 黄森2, 童向荣1, 欧阳丹彤3, 张立明3, 章星林2   

  1. 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-fu1, HUANG Sen2, TONG Xiang-rong1, OUYANG Dan-tong3, ZHANG Li-ming3, ZHANG Xing-lin2   

  1. 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

摘要:

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

中图分类号: