CIMHS:基于优化增量策略求解极小碰集的方法_魏霞.pdf
《CIMHS:基于优化增量策略求解极小碰集的方法_魏霞.pdf》由会员分享,可在线阅读,更多相关《CIMHS:基于优化增量策略求解极小碰集的方法_魏霞.pdf(7页珍藏版)》请在咨信网上搜索。
1、第 5 期2023 年5 月电子学报ACTA ELECTRONICA SINICAVol.51 No.5May 2023CIMHS:基于优化增量策略求解极小碰集的方法魏霞1,赵相福1,黄森2(1.烟台大学计算机与控制工程学院,山东烟台 264005;2.浙江师范大学计算机系,浙江金华 321000)摘要:在基于模型的诊断推理过程中,极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上,充分考虑它们与新增冲突集中元素的关系,提出一种新型的优化增量策略.在原有极小冲突集簇中,首先通过启发式策略抽取部分集合进行极小化,从而大幅度缩短求解时间;然后通过优化的增量策略快
2、速补全并更新解集,进而提高整体求解效率.为进一步提高算法的效率,提出按冲突集的势从小到大增量排序,利用新型优化的增量策略依次递归计算,并最终求得原始问题集合簇所有解集的全增量算法CIMHS(Complete Increment Minimal Hitting Set).实验结果表明,在许多情形下,CIMHS算法较其他经典的极小碰集求解算法,可减少1至3个数量级的运行时间.关键词:基于模型诊断;极小冲突集;极小碰集;增量策略;启发式策略;全增量基金项目:国家自然科学基金(No.61972360,No.62072392)中图分类号:TP306文献标识码:A文章编号:0372-2112(2023)0
3、5-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.D
4、epartment 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 i
5、s 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 performa
6、nce 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 algori
7、thm 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 se
8、veral 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)作为人工智能领域中基
9、于“深知识”的智能化故障诊断推理技术,克服了传统故障诊断中基于专家经验系统存在的诸多局限性,从而在汽车故障诊断、医疗问题诊断以及配电网故障诊断等领域得到广泛的应用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
10、 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等
11、对Boolean方法进行了优化,使用迭代代替了递归,减少空间消耗9.赵相福等提出基于连接关系的增量方法10,求解过程中只需对同一等价类解集进行极小化操作,提高了求解效率.此外,欧阳丹彤等提出近似完备算法11,以牺牲解集完备性换取在可接受的时间内得到部分解集,大幅度提升求解效率.当前碰集极小化方法,由于存在无法去除相同的冗余极小碰集问题,仍然采用子超集检测极小化算法(Sub-Superset Detecting Minimization,SSDM)12.此方法每次调用时均需将新碰集与原碰集簇中碰集逐一进行比较,导致判定效率会随着问题规模的增大而迅速降低.为减少子集检测的比较次数,缩小问题集合簇的
12、规模,本文提出优化增量策略以便补全减少的集合.在增量计算时,根据原冲突集合簇的每一解集与新增集合交集是否为空分成两类,对于交集非空的解集,无需极小化处理;而对于交集为空集的解集,需要与新增集合中元素进行笛卡尔积扩展.在扩展前,先将新增集合中的元素分为独有与公有两类,一部分解集与独有元素进行笛卡尔积扩展后,无需去超集;另一部分与新增冲突集的公有元素进行笛卡尔积扩展后,通过启发式策略,仅选取部分解集进行极小化.为进一步提高极小碰集求解效率,提出全增量CIMHS(Complete Increment Minimal Hitting Set)方法.将冲突集合簇中的冲突集按照集合的势从小到大依次排序,采
13、用优化增量策略依次递归增量冲突集合,不断更新解集簇,从而求得所有极小碰集.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)为真当
14、且仅当部件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的碰集.此外
15、,若删除元素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 集合
16、 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 ,S
17、c=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子超集检测极小化算法基于子集检测去超集算法主要是对碰集的极小性进行判定.由定义3可知,若碰集H是集合簇F的一个极小碰集,则H的任意真子集均不在F的解集簇中.否则,解集簇中存在真超集.具体过程如算法1所示.3.2原始增量算法原始增
18、量算法在增量求解过程中,无需对新冲突集合簇进行重新求解,只需在原解集簇基础上进行增量更新.将原冲突集合簇的解集根据与新增集合交集是否为空分为两类,对于交集非空的解集无需处理,而交集为空的解集,需要与新增集合中元素进行笛卡尔积扩展.具体过程如算法2所示.例 3 设冲突集合簇 F=1,2,3,3,4,5,5,7 ,新增冲突集Ss=1,4 ,求解所有的极小碰集.Step1:由完备极小碰集算法,可以得到F的所有解集为:3,5 ,3,7 ,1,4,7 ,1,5 ,2,4,7 ,2,5 ,共6个集合.Step2:根据原解集簇中集合与Ss是否有交集,分为O1=1,4,7,1,5,2,4,7 与 O2=3,5
19、,3,7 ,2,5 .Step3:经SsO2,得到碰集簇H=1,3,5 ,1,3,7 ,1,2,5 ,3,4,5 ,3,4,7 ,2,4,5 .Step4:将H与O1归并后输入到算法1,得到部分新解集簇h:1,3,7 ,3,4,5 ,3,4,7 ,2,4,5 .Step5:新冲突集簇的解集簇M=O1h,即:1,4,7 ,1,5 ,2,4,7 ,1,3,7 ,3,4,5 ,3,4,7 ,2,4,5 ,共7个解.3.3优化的增量策略首先,根据新增集合中元素与解集元素的关系,找到新增集合的独有元素集Sp及公有元素集Sc;根据每一解集与新增集合交集是否为空,将解集簇分成M1和M2两部分.显然,对于交集
20、非空的 M1依然保持为极小解;其次,对于交集为空的M2与Sp进行笛卡尔积后,得到的解集也为极小解;此外,M2与Sc=e1,e2,em 进行笛卡尔积后,得到的解集仅需与M1中部分解集进行比较去超集.例如:M2中的各集合S扩展ei后,只需与M1中含有元素ei,且不含有Sc中其他元素的解集进行比较去超集后,得到的解集也为极小解.以上三部分解集进行合并,即为最终解集.命题1 M2中的集合S扩展元素e后,若其不是超集,则为极小解,不可能为其他解集的真子集.证明 反证法.如果S扩展元素e后是其他解集的子集,说明S在扩展前已是其他解集的子集,显然不满足候选解都是极小解的前提.若S扩展后成为超集,其子集必然不
21、会含有e以外的其他共有元素,故只需与含有e的解集进行超集比较.具体实现过程如算法3所示.例4 设冲突集合簇F=1,2,3 ,3,4,5 ,5,6,7 ,新增冲突集Ss=1,7,8 ,求解所有的极小碰集.Step1:F的所有解集为:1,5 ,1,4,6 ,1,4,7 ,算法1子超集检测极小化算法输入:碰集簇H=S1,S2,Sn.输出:极小碰集簇M.1.MMS1;2.For Si in H do3.For Sj in M do4.IF(SjSi)5.break;6.IF(SiSj)7.M.d(Sj);8.MMSi;9.End For10.End For算法2原始增量算法输入:冲突集Ss=e1,e2
22、,em,解集簇E=S1,S2,Sn.输出:极小碰集簇M.1.For Si in E do2.IF(SsSi=3.MMSsSi|SiM,SiSsSi;4.ELSE5.MMSi;6.End For算法3优化增量算法输入:Ss=e1,e2,em,解集簇E=S1,S2,Sn.输出:极小碰集簇M.1.Me=ni=1SiE;2.Sp=e|eSseMe;3.Sc=e|eSseMe;4.For Si in E do5.IF(SsSi=6.MMSpSi;7.MMScSi|SiM,SiSsSi;8.ELSE9.MMSi;10.End For1336第 5 期魏霞:CIMHS:基于优化增量策略求解极小碰集的方法2,
23、4,7 ,3,7 ,2,4,6 ,2,5 ,3,5 ,3,6 ,共9个集合.Step2:O1=1,5 ,1,4,6 ,1,4,7 ,2,4,7 ,3,7 ,O2=2,4,6,3,5,2,5,3,6 .Sp=8,Sc=1,7 .Step3:经 SpO2,可得解集簇 h1=2,4,6,8 ,3,5,8 ,2,5,8 ,3,6,8 .Step4:引入集合簇 h2初始为空.循环将 Sc中的元素与O2进行笛卡尔积运算,首先元素1进行笛卡尔积,得到碰集H=1,2,4,6 ,1,3,5 ,1,2,5 ,1,3,6 .此时,挑选O1中仅含有元素1且不含有元素7的部分解集O1=1,5 ,1,4,6 ,将H和O1
24、归并后输入算法1,即可得到部分新解集簇h.令h2=h2h.循环结束时,转到Step5.Step5:新冲突集合簇的极小碰集簇为:M=h1h2O1,即M=2,4,6,8 ,3,5,8 ,2,5,8 ,3,6,8 ,1,3,6 ,2,5,7 ,1,5 ,1,4,6 ,1,4,7 ,2,4,7 ,3,7 ,共11个解.3.4全增量算法受到前述优化的增量策略启发,本文进而提出一种全增量策略计算极小碰集.在计算极小碰集时,首先将冲突集合簇中的冲突集按照集合的势从小到大排序,挑选势最小冲突集依次进行增量求解.在每次增量过程中,采用算法 3 求解,直至冲突集合簇为空为止.具体的实现过程如算法4所示.例5 设冲
25、突集合簇F=1,2,3 ,2,4 ,1,6 ,求解其所有的极小碰集.Step1:将 F 中的集合按照势从小到大依次排序,即,F0=2,4 ,1,6 ,1,2,3 .Step2:首先设 M为空,Ss=2,4 ,将 M和 Ss作为参数调用算法3,输出得到M=2 ,4 .Step3:接着 Ss=1,6 ,M=2 ,4 ,将 M 和 Ss作为 参 数 调 用 算 法 3,输 出 新 M=1,2,1,4,2,6 ,4,6 .Step4:最后将Ss=1,2,3 与M=1,2 ,1,4 ,2,6 ,4,6 作为参数调用算法 3,输出最终 M=3,4,6 ,1,2 ,1,4 ,2,6 ,共4个解.3.5复杂度
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CIMHS 基于 优化 增量 策略 求解 极小 方法 魏霞
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。