CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy

WEI Xia; ZHAO Xiang-fu; HUANG Sen

doi:10.12263/DZXB.20220482

您当前的位置：

首页 >

文章列表页 >

CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy

PAPERS | 更新时间：2025-12-08

- CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy
- ACTA ELECTRONICA SINICA Vol. 51, Issue 5, Pages: 1334-1340(2023)
- 作者机构：
  
  1.烟台大学计算机与控制工程学院，山东烟台 264005
  2.浙江师范大学计算机系，浙江金华 321000
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(61972360;62072392)
- DOI：10.12263/DZXB.20220482
  CLC： TP306
- Received：29 April 2022，
  
  Revised：2022-10-15，
  
  Published：25 May 2023
- 稿件说明：
移动端阅览
魏霞,赵相福,黄森.CIMHS：基于优化增量策略求解极小碰集的方法[J].电子学报,2023,51(05):1334-1340.

WEI Xia,ZHAO Xiang-fu,HUANG Sen.CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy[J].ACTA ELECTRONICA SINICA,2023,51(05):1334-1340.
魏霞,赵相福,黄森.CIMHS：基于优化增量策略求解极小碰集的方法[J].电子学报,2023,51(05):1334-1340. DOI： 10.12263/DZXB.20220482.

WEI Xia,ZHAO Xiang-fu,HUANG Sen.CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy[J].ACTA ELECTRONICA SINICA,2023,51(05):1334-1340. DOI： 10.12263/DZXB.20220482.

摘要

在基于模型的诊断推理过程中，极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上，充分考虑它们与新增冲突集中元素的关系，提出一种新型的优化增量策略.在原有极小冲突集簇中，首先通过启发式策略抽取部分集合进行极小化，从而大幅度缩短求解时间；然后通过优化的增量策略快速补全并更新解集，进而提高整体求解效率.为进一步提高算法的效率，提出按冲突集的势从小到大增量排序，利用新型优化的增量策略依次递归计算，并最终求得原始问题集合簇所有解集的全增量算法CIMHS（Complete Increment Minimal Hitting Set）.实验结果表明，在许多情形下，CIMHS算法较其他经典的极小碰集求解算法，可减少1至3个数量级的运行时间.

Abstract

In the process of model-based diagnosis

it is a key step to efficiently generate all minimal hitting sets. In this paper

a novel optimization strategy for incremental diagnosis is proposed. When a new conflict set is added

the relationship between the original minimal hitting sets and the newly added conflict set will be explored thoroughly. The time cost can be greatly reduced by joining the corresponding heuristic strategy to select the specific sets in the course of minimality checking. The computing performance can be improved considerably by introducing the optimized incremental strategy to update the final results. Furthermore

in order to obtain the higher efficiency

an algorithm named CIMHS (Complete Increment Minimal Hitting Set) based on optimized incremental strategy is presented. The proposed algorithm processes set incrementally in turn according to the ascending order of the cardinality of set. Experimental results including both on multiple synthetic and benchmark examples show that the proposed CIMHS algorithm is more efficient than many other state-of-the-art methods

with a reduction of several orders of magnitude runtime.

关键词

Keywords

references

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

DE K J , WILLIAMS B C . Diagnosing multiple faults [J]. Artificial Intelligence , 1987 , 32 ( 1 ): 97 - 130 .

ZHAO Xiang-fu , TONG Xiang-rong , OUYANG Dan-tong , et al . TreeMerge: Efficient computation of minimal hitting-sets for conflict sets in a tree structure for model-based fault diagnosis [J]. IEEE Transactions on Reliability , 2021 , 70 ( 4 ): 1596 - 1610 .

何嫱君 , 赵相福 , 欧阳丹彤 , 等 . 极小碰集求解算法的性能分析与比较 [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)

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

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 .

姜云飞 , 林笠 . 用对分HS-树计算最小碰集 [J]. 软件学报 , 2002 , 13 ( 12 ): 2267 - 2274 .

JIANG Yun-fei , LIN Li . Computing the minimal hitting set with binary HS-tree [J]. Journal of Software , 2002 , 13 ( 12 ): 2267 - 2274 . (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(ECAI) . Montpellier, France : IOS Press , 2012 : 648 - 653 .

ZHAO Xiang-fu , OUYANG Dan-tong . Deriving all minimal hitting sets based on join relation [J]. IEEE Transactions on Systems Man Cybernetics: Systems , 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 , 56 ( 7 ): 1396 - 1407 .

TIAN Nai-yu , OUYANG Dan-tong , LIU Meng , et al . A method of minimality-checking of diagnosis based on subset consistency detection [J]. Journal of Computer Research and Development , 2019 , 56 ( 7 ): 1396 - 1407 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

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

A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree

A Block-Based Diagnostic Method Combining with the Circuit Structure

Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics

Related Author

ZHANG Xing-lin

ZHANG Li-ming

ZHAO Xiang-fu

HUANG Sen

TONG Xiang-rong

OUYANG Dan-tong

ZHANG Li-ming

OUYANG Dan-tong

Related Institution

School of Computer and Control Engineering, Yantai University

Department of Computer, Zhejiang Normal University

College of Computer Science and Technology, Jilin University

Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University) Ministry of Education Changchun Jilin China

College of Software, Jilin University

⁰