用布尔代数方法计算最小碰集 被引量：38

1

作者 姜云飞 林笠 《计算机学报》 EI CSCD 北大核心 2003年第8期919-924,共6页

在基于模型的诊断中 ,模型一般都是用布尔代数来表示 ,而计算碰集 (hittingsets)则采用HS 树或图 ,这就使得诊断系统采用多种不同的数据结构 ,给编程实现带来了不便 .本文用布尔代数变量表示待诊断系统的部件 ,并给出了用布尔代数直接... 在基于模型的诊断中 ,模型一般都是用布尔代数来表示 ,而计算碰集 (hittingsets)则采用HS 树或图 ,这就使得诊断系统采用多种不同的数据结构 ,给编程实现带来了不便 .本文用布尔代数变量表示待诊断系统的部件 ,并给出了用布尔代数直接计算最小碰集的算法 .数据结构更为简单 ,只需要布尔表达式 ,相当于字符串 ,效率上比其他的一些研究结果也要好 ,同时可克服丢失正确解的问题 。 展开更多

关键词 人工智能 布尔代数方法 计算 最小碰集 模型诊断 最小冲突集

下载PDF 职称材料

用对分HS-树计算最小碰集 被引量：37

2

作者 姜云飞 林笠 《软件学报》 EI CSCD 北大核心 2002年第12期2267-2274,共8页

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出... 在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分HS-树(binary hitting set-树,简称BHS-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于HS-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原BHS-树的基础上增加新的分支即可,这种性质对实际诊断问题是特别有用的.对利用BHS-树的算法从理论上进行了分析和论证,并通过实际编写程序进行了检验. 展开更多

关键词 模型诊断 最小冲突集 最小碰集 对分HS-树 人工智能 推理理论

下载PDF 职称材料

基于模型诊断中用逻辑数组计算最小碰集 被引量：16

3

作者 林笠 《暨南大学学报（自然科学与医学版）》 CAS CSCD 2002年第1期24-27,共4页

在基于模型诊断中 ,冲突集的最小碰集就是诊断目标 .提出用二维逻辑型数组计算冲突集的最小碰集的一种新的算法 .

关键词 逻辑数组 模型诊断 最小冲突集 最小碰集 人工智能 诊断专家系统

下载PDF 职称材料

基于动态极大度的极小碰集求解方法 被引量：17

4

作者 张立明 欧阳丹彤 曾海林 《计算机研究与发展》 EI CSCD 北大核心 2011年第2期209-215,共7页

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,... 在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好. 展开更多

关键词 基于模型的诊断 极小碰集 SE-Tree 动态极大度 向量交集

下载PDF 职称材料

基于BNB-HSSE计算全体碰集的方法 被引量：13

5

作者 陈晓梅 孟晓风 乔仁晓 《仪器仪表学报》 EI CAS CSCD 北大核心 2010年第1期61-67,共7页

在基于模型的故障诊断与测试中,计算全体最小碰集是其关键的步骤.本文将分支定界法BNB与集合枚举法HSSE相结合,提出了一种基于BNB-HSSE计算全体最小碰集的算法.该算法利用分支定界法将问题不断分解成子问题,从而降低待求问题的规模.然... 在基于模型的故障诊断与测试中,计算全体最小碰集是其关键的步骤.本文将分支定界法BNB与集合枚举法HSSE相结合,提出了一种基于BNB-HSSE计算全体最小碰集的算法.该算法利用分支定界法将问题不断分解成子问题,从而降低待求问题的规模.然后针对BNB过程中的子问题,应用HSSE来进行一层集合枚举,从而简化了枚举过程.最后采用仿真进行验证,可得本文方法在集合簇规模较大时显示了较强的计算效率优势,且能够计算全体最小碰集. 展开更多

关键词 基于模型的诊断 最小碰集 分支定界算法 集合枚举

下载PDF 职称材料

用CHS-tree基于集合势的方法计算极小碰集 被引量：10

6

作者 王肖 赵相福 《计算机集成制造系统》 EI CSCD 北大核心 2014年第2期401-406,共6页

在基于模型的故障诊断理论中,为了根据所有冲突部件集计算全体极小碰集,提出基于集合势的方法,每次选择当前集合簇中势最小的集合进行扩展,并借助集合簇中元素出现的频率作为辅助判断,不断将大问题逐渐分解成子问题,然后依次求出不包含... 在基于模型的故障诊断理论中,为了根据所有冲突部件集计算全体极小碰集,提出基于集合势的方法,每次选择当前集合簇中势最小的集合进行扩展,并借助集合簇中元素出现的频率作为辅助判断,不断将大问题逐渐分解成子问题,然后依次求出不包含该扩展集合中各元素的集合簇的所有极小碰集。实验结果表明,CHStree方法生成树的过程较简单,能产生较少的节点,比经典的碰集树方法、二分法和集合枚举法等具有更高的求解效率。在某些情况下,其效率也高于当前效率最高的Boolean方法。 展开更多

关键词 基于模型的诊断 极小冲突集 极小碰集 碰撞树

下载PDF 职称材料

递归建立HS-树计算最小碰集 被引量：9

7

作者 林笠 《微电子学与计算机》 CSCD 北大核心 2002年第2期7-10,共4页

在基于模型的诊断中,广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS-树,HST-树,BHS-树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS-树(Recursivehittingset-树,简记为RHS-树)计算最小碰集的方法,在空间复杂... 在基于模型的诊断中,广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS-树,HST-树,BHS-树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS-树(Recursivehittingset-树,简记为RHS-树)计算最小碰集的方法,在空间复杂性与时间复杂性上能够满足大多数诊断系统中的要求。 展开更多

关键词 模型诊断 最小冲突集 最小碰集 RHS-树 HS-树 算法 人工智能

下载PDF 职称材料

基于DPSO最小碰集算法的掩盖故障识别 被引量：11

8

作者 蒋荣华 田书林 龙兵 《系统工程与电子技术》 EI CSCD 北大核心 2009年第4期997-1000,F0003,共5页

针对可测性分析中掩盖故障识别的难点,提出一种掩盖故障存在性的判定及计算其冲突集方法;并将离散粒子群算法(discrete binary particle swarm optimization,DPSO)用于求解冲突集的最小碰集,实现掩盖故障最小碰集的求解;为克服DPSO易陷... 针对可测性分析中掩盖故障识别的难点,提出一种掩盖故障存在性的判定及计算其冲突集方法;并将离散粒子群算法(discrete binary particle swarm optimization,DPSO)用于求解冲突集的最小碰集,实现掩盖故障最小碰集的求解;为克服DPSO易陷入局部最优的缺点,还比较了惯性权重对DPSO算法性能的影响。实例验证表明:与求解掩盖故障的其他方法相比,惯性权重线性变化的DPSO算法不仅提高了算法效率,而且避免了其他算法求解时容易出现"计算爆炸"的问题,尤其适合于识别大型复杂系统的掩盖故障。 展开更多

关键词 掩盖故障 隐藏故障 冲突集 最小碰集 离散粒子群算法 惯性权重

下载PDF 职称材料

基于最小碰集的多故障诊断算法研究 被引量：11

9

作者 王子玲 许爱强 《兵工学报》 EI CAS CSCD 北大核心 2010年第3期337-342,共6页

目前存在的测试性分析和故障诊断工具基本都是基于单故障假设,不适用于复杂系统。针对这一问题,研究了多故障假设下的序贯测试算法。提出了利用分类HS-树(CHS-树)计算最小碰集(MHS)的算法;以多故障状态集的MHS作为故障状态,生成最优单... 目前存在的测试性分析和故障诊断工具基本都是基于单故障假设,不适用于复杂系统。针对这一问题,研究了多故障假设下的序贯测试算法。提出了利用分类HS-树(CHS-树)计算最小碰集(MHS)的算法;以多故障状态集的MHS作为故障状态,生成最优单故障测试策略;以决策树中各叶节点的MHS为判断依据来决定下一步要执行的测试,最终生成多故障诊断策略。最后给出案例分析,结果表明:计算MHS的算法能够提高诊断策略的生成效率;诊断策略能够有效隔离多故障问题。 展开更多

关键词 系统工程方法论 多故障诊断 最小碰集 分类HS-树 序贯测试

下载PDF 职称材料

基于攻击图及蚁群算法的安全评估 被引量：9

10

作者 金晶 孙东来 陈秀真 《信息安全与通信保密》 2009年第4期79-81,共3页

攻击图是网络安全分析人员常用的分析工具之一,文章重点研究了基于攻击图模型的系统安全分析架构,并结合攻击难度提出了应用蚁群算法,在攻击图中获取最小关键攻击集的优化解。同时,文章将实验结果与贪婪算法进行了比较,证明了蚁群算法... 攻击图是网络安全分析人员常用的分析工具之一,文章重点研究了基于攻击图模型的系统安全分析架构,并结合攻击难度提出了应用蚁群算法,在攻击图中获取最小关键攻击集的优化解。同时,文章将实验结果与贪婪算法进行了比较,证明了蚁群算法在该应用上是一种高效的优化算法。 展开更多

关键词 攻击图 最小关键攻击集 最小碰撞集 蚁群算法

原文传递

一种基于模型的配电网故障诊断搜索算法 被引量：10

11

作者 胡非 刘志刚 +1 位作者 何士玉 杨红梅 《电力自动化设备》 EI CSCD 北大核心 2013年第1期81-84,90,共5页

提出用二进制编码逻辑运算求解最小碰集的算法,该算法将求解最小碰集问题映射到0/1整数规划问题,即首先对系统进行建模仿真,得到最小冲突集簇,然后求出系统的所有候选碰集,对系统中每个元件进行二进制编码,最后采用自底向上的搜索方法,... 提出用二进制编码逻辑运算求解最小碰集的算法,该算法将求解最小碰集问题映射到0/1整数规划问题,即首先对系统进行建模仿真,得到最小冲突集簇,然后求出系统的所有候选碰集,对系统中每个元件进行二进制编码,最后采用自底向上的搜索方法,进行搜索确认,在确认的过程中,使用二进制代码的逻辑"或"运算。将该算法分别从最小冲突集数和最小冲突集簇中所含的总元件数这两方面与其他的最小碰集算法进行比较。实验结果表明,这2种因素对二进制编码算法的时间效率影响较小。最后,以一个实际配电网诊断为例,将所得的最小冲突集簇分别用该算法和其他的最小碰集算法计算,计算结果更加充分地说明了该算法的优越性。 展开更多

关键词 电力系统 配电 故障分析 最小碰集 搜索算法

下载PDF 职称材料

基于BPSO的多故障最小候选集生成技术 被引量：7

12

作者 吕晓明 黄考利 连光耀 《系统工程与电子技术》 EI CSCD 北大核心 2012年第5期961-965,共5页

多故障最小候选集生成是制定多故障诊断策略的首要步骤。利用二进制粒子群优化算法(binaryparticle swarm optimization,BPSO)生成多故障模糊组的最小候选集。首先,利用紧集表示法描述某或节点上的多故障模糊组,其最小候选集即多故障模... 多故障最小候选集生成是制定多故障诊断策略的首要步骤。利用二进制粒子群优化算法(binaryparticle swarm optimization,BPSO)生成多故障模糊组的最小候选集。首先,利用紧集表示法描述某或节点上的多故障模糊组,其最小候选集即多故障模糊组的最小碰集;然后,利用BPSO算法求解多故障模糊组的最小碰集,通过构造个体适应度和群体适应度双函数,解决BPSO算法求解最小碰集的适应性问题,并保证了算法尽可能搜索冲突集的全部碰集;最后,通过某系统实例对算法的有效性进行了验证。事实表明,该方法能有效应用于多故障最小候选集问题的求解。 展开更多

关键词 多故障诊断 最小候选集 紧集表示法 最小碰集 二进制粒子群优化算法

下载PDF 职称材料

求极小碰集的遗传算法 被引量：9

13

作者 张楠 孙吉贵 +1 位作者 赵相福 欧阳丹彤 《广西师范大学学报（自然科学版）》 CAS 北大核心 2006年第4期62-65,共4页

采用改进的遗传算法求解极小碰集问题。在标准遗传算法的基础上,引入了精英策略以提高算法的搜索效率;在进化过程中加入了极小化操作,使得得到的结果都是极小碰集。同时通过实例,验证了极小化操作的有效性。最后,将此算法与其他求极小... 采用改进的遗传算法求解极小碰集问题。在标准遗传算法的基础上,引入了精英策略以提高算法的搜索效率;在进化过程中加入了极小化操作,使得得到的结果都是极小碰集。同时通过实例,验证了极小化操作的有效性。最后,将此算法与其他求极小碰集的算法进行了比较。 展开更多

关键词 极小碰集 遗传算法 精英策略

下载PDF 职称材料

可用于诊断产生的计算碰集的新方法 被引量：6

14

作者 赵相福 欧阳丹彤 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2006年第3期385-390,共6页

提出一种利用与元素相关联的冲突集个数计算碰集的新方法,并结合带有终止节点的集合枚举树SE-tree形式化地表达计算过程,逐步生成所有的极小碰集.由于在SE-tree中添加了终止节点,因而能够较大提高搜索效率.实验结果表明,该算法程序容易... 提出一种利用与元素相关联的冲突集个数计算碰集的新方法,并结合带有终止节点的集合枚举树SE-tree形式化地表达计算过程,逐步生成所有的极小碰集.由于在SE-tree中添加了终止节点,因而能够较大提高搜索效率.实验结果表明,该算法程序容易编制,且效率较好,对于复杂的被诊断对象系统可以满足实时性. 展开更多

关键词 基于模型诊断 冲突集 极小碰集 集合枚举树

下载PDF 职称材料

在基于模型诊断中计算最小碰集算法 被引量：6

15

作者 林笠 《计算机应用研究》 CSCD 北大核心 2002年第9期36-39,共4页

介绍了基于模型诊断中的计算碰集的算法 ,并分析比较了各算法的效率和计算结果。其中的逻辑型数组算法、递归算法、BHS 树算法、布尔代数算法、GA算法均是笔者近年来研究的结果。

关键词 模型诊断 计算 最小碰集算法 人工智能 BHS-树 布尔代数算法 GA算法

下载PDF 职称材料

极小碰集求解中候选解极小性判定方法 被引量：5

16

作者 刘思光 欧阳丹彤 张立明 《软件学报》 EI CSCD 北大核心 2018年第12期3733-3746,共14页

极小碰集问题是人工智能中的重要问题,应用广泛.碰集极小性判定,作为极小碰集求解过程中的关键步骤,效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方... 极小碰集问题是人工智能中的重要问题,应用广泛.碰集极小性判定,作为极小碰集求解过程中的关键步骤,效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题,提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法,剥离了碰集极小性判定耗时与极小碰集簇大小的相关性;通过深入分析增量求解过程中非极小碰集的产生原因,给出了ICC方法的增量判定形式IICC方法,使其可以尽早发现并丢弃非极小候选解,为使用其增量极小碰集求解算法带来额外的剪枝效果,进一步提升算法的效率.实验结果表明:该方法易于实现,可扩展性强,对于当前效率较高的Boolean算法,使用IICC方法后,算法可求解问题的规模和整体效率均有明显提升,效率提升最高达4个数量级以上. 展开更多

关键词 基于模型诊断 极小碰集 碰集极小性判定 预剪枝 增量方法

下载PDF 职称材料

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

17

作者 魏霞 赵相福 黄森 《电子学报》 EI CAS CSCD 北大核心 2023年第5期1334-1340,共7页

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

关键词 基于模型诊断 极小冲突集 极小碰集 增量策略 启发式策略 全增量

下载PDF 职称材料

基于动态极大元素覆盖值的极小碰集求解算法 被引量：5

18

作者 邓召勇 欧阳丹彤 +1 位作者 耿雪娜 刘杰 《计算机研究与发展》 EI CSCD 北大核心 2018年第4期791-801,共11页

在基于模型诊断(model-based diagnosis,MBD)中,因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果,所以利用所有极小冲突集构造极小冲突集合簇,并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖... 在基于模型诊断(model-based diagnosis,MBD)中,因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果,所以利用所有极小冲突集构造极小冲突集合簇,并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖值求解极小碰集的新算法.该算法按照元素的元素覆盖值从大到小的顺序依次处理元素,并在求解碰集的过程中加入启发式策略和剪枝策略,使得搜索空间极大减少;利用邻接链表存储输入的极小冲突集合簇,邻接链表相对于用矩阵作为存储结构有较好的空间开销且通过邻接指向能快速地找到元素可以覆盖的集合簇中的元素;每得到一个碰集便使用极小碰集判定规则进行筛选,因此算法结束时可以产生而且仅产生所有的极小碰集.实验结果表明该算法有较高的计算效率. 展开更多

关键词 基于模型诊断 极小冲突集 极小碰集 动态极大元素覆盖值 启发式策略 剪枝策略

下载PDF 职称材料

基于极小碰集的军事模型组合方法

19

作者 田乃予 浦方韬 +2 位作者 钱诗君 沈驰 潘阳 《信息化研究》 2024年第3期53-58,共6页

面对现代化战争对军事模型与日俱增的新需求,为解决模型组建过程中因依赖人工选择而导致的不良影响,针对军事模型组合这一难点问题,本文提出基于极小碰集的军事模型组合方法。首先,给出模型功能集的定义,并提供应用模型功能需求分解方法... 面对现代化战争对军事模型与日俱增的新需求,为解决模型组建过程中因依赖人工选择而导致的不良影响,针对军事模型组合这一难点问题,本文提出基于极小碰集的军事模型组合方法。首先,给出模型功能集的定义,并提供应用模型功能需求分解方法;其次,通过构建功能-模型集合簇,将军事模型组合问题转化为极小碰集问题进行求解;最后,结合经典的极小碰集算法HS-Tree算法,求解得到满足应用模型所需功能的全部模型组合,为模型研发人员提供客观、全面、准确的模型组合方式,有效降低军事模型组建过程中的人工参与度,提高模型组合效率。 展开更多

关键词 模型组合 极小碰集 军事应用

下载PDF 职称材料

基于多故障假设的诊断策略研究与应用 被引量：6

20

作者 王子玲 许爱强 牛双诚 《工程设计学报》 CSCD 北大核心 2009年第4期281-285,共5页

针对工程中最优单故障序贯测试难以隔离的多故障问题,利用Grunberg等人提出的多故障模糊组的概念,以最优单故障测试策略为基础,构造了一种多故障假设下的序贯测试算法.该算法以多故障状态集的最小碰集作为生成最优单故障策略的故障状态... 针对工程中最优单故障序贯测试难以隔离的多故障问题,利用Grunberg等人提出的多故障模糊组的概念,以最优单故障测试策略为基础,构造了一种多故障假设下的序贯测试算法.该算法以多故障状态集的最小碰集作为生成最优单故障策略的故障状态,生成最优单故障策略;以诊断决策树中各叶节点的多故障状态集为评判标准,确定系统的状态,完成多故障假设下的系统故障诊断;与连续使用单故障策略的方法相比,该方法提高了测试效率.以某型机载电子设备为例给出算例分析,验证了该算法隔离多故障的有效性. 展开更多

关键词 故障诊断 序贯测试 多故障模糊组 最小碰集

下载PDF 职称材料