CIMHS：基于优化增量策略求解极小碰集的方法_魏霞.pdf

第 5 期2023 年5 月电子学报ACTA ELECTRONICA SINICAVol.51 No.5May 2023CIMHS：基于优化增量策略求解极小碰集的方法魏霞1，赵相福1，黄森2（1.烟台大学计算机与控制工程学院，山东烟台 264005；2.浙江师范大学计算机系，浙江金华 321000）摘要：在基于模型的诊断推理过程中，极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上，充分考虑它们与新增冲突集中元素的关系，提出一种新型的优化增量策略.在原有极小冲突集簇中，首先通过启发式策略抽取部分集合进行极小化，从而大幅度缩短求解时间；然后通过优化的增量策略快速补全并更新解集，进而提高整体求解效率.为进一步提高算法的效率，提出按冲突集的势从小到大增量排序，利用新型优化的增量策略依次递归计算，并最终求得原始问题集合簇所有解集的全增量算法CIMHS（Complete Increment Minimal Hitting Set）.实验结果表明，在许多情形下，CIMHS算法较其他经典的极小碰集求解算法，可减少1至3个数量级的运行时间.关键词：基于模型诊断；极小冲突集；极小碰集；增量策略；启发式策略；全增量基金项目：国家自然科学基金（No.61972360，No.62072392）中图分类号：TP306文献标识码：A文章编号：0372-2112(2023)05-1334-07电子学报URL:http:/DOI:10.12263/DZXB.20220482CIMHS:A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental StrategyWEI Xia1,ZHAO Xiang-fu1,HUANG Sen2（1.School of Computer and Control Engineering，Yantai University，Yantai，Shandong 264005，China;2.Department of Computer，Zhejiang Normal University，Jinhua，Zhejiang 321000，China）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.Key words:model-based diagnosis;minimal conflict set;minimal hitting set;incremental strategy;heuristic strategy;complete incrementFoundation Item(s):National Natural Science Foundation of China(No.61972360,No.62072392)1引言基于模型的诊断（Model-Based Diagnosis，MBD）作为人工智能领域中基于“深知识”的智能化故障诊断推理技术，克服了传统故障诊断中基于专家经验系统存在的诸多局限性，从而在汽车故障诊断、医疗问题诊断以及配电网故障诊断等领域得到广泛的应用13.求解极小碰集（Minimal Hitting Set，MHS）是 MBD过程中的关键步骤之一4.不幸的是，极小碰集的计算已经被证明是一个NP-Hard问题5.1987年智能诊断专家Reiter结合de Kleer提出的冲突集的概念，首次将极收稿日期：2022-04-29；修回日期：2022-10-15；责任编辑：覃怀银第 5 期魏霞:CIMHS：基于优化增量策略求解极小碰集的方法小 碰 集 算 法 HS-Tree（Hitting Set-Tree）5运 用 到MBD.1989 年，Greiner 等 提 出 HS-DAG（Hitting Set-Directed Acyclic Graph）方法，利用有向无环图结构补全了HS-Tree算法的完备性6.近年来，国内外众多学者对极小碰集求解方法进行了大量研究.姜云飞等提出BHS-Tree（Binary Hitting Set-Tree）方法，生成节点个数较少，并且可以增量求解7.随后，林笠等提出基于布尔代数的Boolean方法，将问题集合簇编码，用布尔代数逻辑知识求解极小碰集，是目前效率最高的算法之一8.但这两种方法在系统规模较大时，碰集极小化需花费大量的时间.Pill等对Boolean方法进行了优化，使用迭代代替了递归，减少空间消耗9.赵相福等提出基于连接关系的增量方法10，求解过程中只需对同一等价类解集进行极小化操作，提高了求解效率.此外，欧阳丹彤等提出近似完备算法11，以牺牲解集完备性换取在可接受的时间内得到部分解集，大幅度提升求解效率.当前碰集极小化方法，由于存在无法去除相同的冗余极小碰集问题，仍然采用子超集检测极小化算法（Sub-Superset Detecting Minimization，SSDM）12.此方法每次调用时均需将新碰集与原碰集簇中碰集逐一进行比较，导致判定效率会随着问题规模的增大而迅速降低.为减少子集检测的比较次数，缩小问题集合簇的规模，本文提出优化增量策略以便补全减少的集合.在增量计算时，根据原冲突集合簇的每一解集与新增集合交集是否为空分成两类，对于交集非空的解集，无需极小化处理；而对于交集为空集的解集，需要与新增集合中元素进行笛卡尔积扩展.在扩展前，先将新增集合中的元素分为独有与公有两类，一部分解集与独有元素进行笛卡尔积扩展后，无需去超集；另一部分与新增冲突集的公有元素进行笛卡尔积扩展后，通过启发式策略，仅选取部分解集进行极小化.为进一步提高极小碰集求解效率，提出全增量CIMHS（Complete Increment Minimal Hitting Set）方法.将冲突集合簇中的冲突集按照集合的势从小到大依次排序，采用优化增量策略依次递归增量冲突集合，不断更新解集簇，从而求得所有极小碰集.2预备知识2.1基于模型的诊断相关定义和概念定义1 系统5.一个基于模型诊断的系统定义为三元组，其中：（1）S（System）为系统描述，是一阶谓词公式的集合，描述了待诊断故障系统的相关信息；（2）C（Component）为系统的组成部件集合，是一个有限的常量集；（3）O（Observation）为观测集，是一阶谓词公式的有限集.定义2 冲突集5.冲突集是系统中C的一个子部件集 c1，c2，cn C，使得SO A（c1），A（c2），A（cn）不一致.其中，使用一阶谓词A表示“反常的（abnormal）”，A（c）为真当且仅当部件c反常，cC.一个冲突集被称为极小冲突集，当且仅当该冲突集的任意真子集都不是冲突集.定义3 碰集5.设冲突集合簇F=S1，S2，Sn，称集合 H 为 F 的一个碰集，如果 H 满足：（1）HSiF；（2）对于任意一个SiF，都有HSi.一个碰集是极小碰集，当且仅当它的任意真子集都不是F的碰集.例1 设冲突集合簇F=a，b ，b，c ，d，e，f ，则它的所有的极小碰集为：a，c，d ，a，c，e ，a，c，f ，b，d ，b，e ，b，f .以集合 b，f 为例，首先，该集合中所有元素均来自集合簇F；其次，集合 b，f 与F中任何集合的交集均非空；因而，集合 b，f 为F的碰集.此外，若删除元素b，则集合 f 与集合 a，b 交集为空，因而不是碰集；若删除元素 f，则集合 b 与集合 d，e，f 交集为空，因而不是碰集.综上，集合 b，f 为F的极小碰集.定义4 集合的势.称集合中系统部件的个数为集合的势，其大小可以用来度量集合的规模大小.2.2增量策略的相关定义和概念定义5 独有元素和公有元素.假设向冲突集合簇F中新增的集合为Ss.称元素e为Ss的独有元素，当且仅当eSseSiFSi.独有元素构成的集合Sp称为Ss的独有元素集.称 元 素 e 为 Ss的 公 有 元 素，当 且 仅 当 eSseSi FSi.公有元素构成的集合 Sc称为 Ss的公有元素集.定义 6 集合 S 与集合 X 的笛卡尔积.SX=e X|eS ，即，将集合S中的每一个元素分别添加至集合X.定义 7 集合 S与集合簇 F的笛卡尔积.SF=e Si|eS，SiF ，即，将集合S中的每一个元素e分别添加至集合簇中的每一个集合中，称为集合与集合簇（或集合簇与集合）的笛卡尔积.定义 8 集合簇 F1与集合簇 F2的笛卡尔积.F1F2=S1S2|S1F1，S2F2，即，将集合簇F1中的每一个集合分别与集合簇F2中的每个集合取并集运算产生的所有集合.例 2 设冲突集合簇 F的解集簇为 H=1，2，3 ，3，4，5 ，5，6，7 ，当向冲突集合簇F中新增冲突集Ss=1，7，8 时，此时Sp=8 ，Sc=1，7 .当集合Sc与解集簇H进行笛卡尔积时，ScH=1，2，3 ，1，3，4，5 ，1，5，6，7 ，1，2，3，7 ，3，4，5，7 ，5，6，7 .1335电子学报2023 年3极小碰集求解算法本节首先介绍基于子超集检测极小化算法和原始增量算法，然后给出优化的增量策略以及全增量方法的算法描述，并通过一个具体实例进行说明，最后对算法的时间复杂度进行了分析.3.1子超集检测极小化算法基于子集