检索结果-南通市图书馆

计算机研究与发展 2018年第11期55卷 2386-2394页

作者：徐旖旎欧阳丹彤刘梦张立明张永刚吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障... 详细信息

基于模型诊断(model-based diagnosis)是人工智能领域中的重要研究方向,而基于极小冲突求诊断是求解诊断问题的经典方法,因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究,结合CSRDSE极小冲突集求解算法,提出结合故障输出结构特征的极小冲突求解算法MCSSFFO:首先对CSRDSE算法的剪枝规则进行了改进,避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问;其次,提出故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;最后,提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝,减少了调用SAT求解器的次数.实验结果表明:与CSRDSE算法相比,MCS-SFFO算法求解效率明显提升.

关键词：基于模型诊断极小冲突集集合枚举树 SAT求解器故障输出无关元件

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

结合剪枝规则和故障输出的极小冲突求解方法

结合剪枝规则和故障输出的极小冲突求解方法

引用

作者：徐旖旎吉林大学

学位级别：硕士

基于模型诊断作为一个新兴的智能故障诊断技术,对人工智能领域的发展起到了至关重要的作用。如今,基于模型诊断的应用越来越广泛,如电子电路,医疗问题,通讯网络,航空航天等领域的故障诊断都应用了基于模型诊断的相关算法。基于模型诊断... 详细信息

基于模型诊断作为一个新兴的智能故障诊断技术,对人工智能领域的发展起到了至关重要的作用。如今,基于模型诊断的应用越来越广泛,如电子电路,医疗问题,通讯网络,航空航天等领域的故障诊断都应用了基于模型诊断的相关算法。基于模型诊断的主要思想是:根据待诊断系统元件逻辑、元件间的连接关系、系统的输入观测推断待诊断系统正常情况下预期的输出行为,若预期输出与实际输出不同,说明待诊断系统产生了故障,利用逻辑推理决定出哪些元件产生故障才能解释预期行为与观测行为间的差别,这些引发系统故障的元件集合就是诊断。基于模型诊断的求解步骤是,首先求出诊断系统的所有极小冲突集,其次求解极小冲突集合簇的极小碰集,即为诊断解。因此,计算极小冲突集是基于模型诊断求解过程的重要一步,提高极小冲突求解算法的效率将很大程度上提高基于模型诊断的求解效率。随着SAT求解器效率的提高,将极小冲突求解问题转化成SAT求解问题已逐步成为求解极小冲突的主流方法之一。CSRDSE方法是使用SAT求解器求极小冲突方法中效率较高的一个方法。CSDRSE方法根据冲突集的特点提出了三条剪枝规则,在反向深度遍历SE-Tree时,根据剪枝规则,对非冲突集的真子集和冲突集的严格超集进行剪枝,从而降低了使用SAT求解器的次数,提高了极小冲突的求解效率。本文对CSRDSE方法的剪枝规则做出改进,提出了CSRDSE2方法。在CSRDSE方法中提出,在遍历SE-Tree时,若访问到非冲突集的叶节点,则跳转到下一个叶节点。而CSRDSE2方法提出了非冲突集叶节点的子叶节点不是冲突集。因此,在访问到非冲突集叶节点时,应跳过该叶节点的子叶节点,直接转至以该叶节点的同层兄弟节点为根的分支子树的最左节点进行判断。CSRDSE2方法减少了访问节点的次数,同时也减少了对非冲突集合簇进行子集检测的次数。实验结果表明,与CSRDSE相比,CSRDSE2方法求解极小冲突的效率有所提升。在CSRDSE2方法基础上,本文提出了结合故障输出的极小冲突求解方法MCS-SFFO。MCS-SFFO方法首先提出了故障输出无关元件集与故障输出相关元件集等相关概念,并根据系统描述和观测给出求解故障输出无关元件集的方法;其次提出非冲突集定理,即故障输出无关元件集的子集不是冲突集,并根据非冲突集定理,在反向深度遍历SE-Tree时,对故障输出无关元件集的子集进行剪枝,从而减少调用SAT求解器的次数。实验结果表明,与CSRDSE2方法相比,MCS-SFFO方法求解效率明显提升。

关键词：基于模型诊断极小冲突集集合枚举树 SAT求解器故障输出无关元件

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图及树结构的极小不可满足集求解方法

基于图及树结构的极小不可满足集求解方法

引用

作者：高菡吉林大学

学位级别：硕士

命题可满足问题（propositional satisfiability problem,SAT）是人工智能领域的研究热点,也是数理逻辑及计算机研究中的核心问题,对人工智能发展起到了非常重要的推动作用。命题可满足问题擅长将一些艰难的故障求解转化为问题系统中命... 详细信息

命题可满足问题（propositional satisfiability problem,SAT）是人工智能领域的研究热点,也是数理逻辑及计算机研究中的核心问题,对人工智能发展起到了非常重要的推动作用。命题可满足问题擅长将一些艰难的故障求解转化为问题系统中命题公式是否存在可满足赋值的问题,并给出故障识别。极小不可满足集（minimal unsatisfiable subset,MUS）问题是命题可满足问题的扩展问题。在求解极小不可满足解时,通常将不可满足性问题转换为命题可满足问题,利用SAT求解器来给出是否一致可满足的判定。目前求解极小不可满足集效率较高的两种遍历结构为哈斯图和枚举树。哈斯图结构主要是利用图的逻辑结构构建节点之间的联系,适用于广泛的约束关系处理。图结构主要应用于关系规范调试、不一致检测、模型验证等问题中。极小冲突问题是极小不可满足问题在基于模型诊断上的应用,主要采用枚举树结构,利用树的特性对电路系统中元件集的全枚举进行遍历。相对于图结构遍历,树结构遍历求解极小冲突问题节点跳转方便,配合剪枝策略剪去枚举树中不需要遍历的节点使求解效率更快。在基于图结构求解方法中,MARCO方法是目前采用极大化模型求解MUS效率最高的方法,但此方法未对求解空间进行进一步有效剪枝。针对MARCO方法的不足,结合可满足问题求解复杂度低于不可满足问题的特征,提出基于双模型即极大-中间化模型的MARCO-MAM方法求解MUS。此方法对中间模型求解若得到极大可满足子集,则缩减MUS的无解空间,进而缩减未探索空间来提高MUS求解效率;如果中间模型求解得到不可满足集合,则减少了单一MUS的不可满足迭代求解次数。此方法避免了MARCO方法单一极大化模型求解MUS时未有效利用其他优化技术对求解空间进行剪枝的问题。实验结果表明,与MARCO方法相比MARCO-MAM方法效率较高,尤其在大规模问题或较大搜索空间时效率提高更为明显。在基于树结构求解极小冲突集问题中,MCS-SFFO方法以反向深度的方式遍历集合枚举树（Set Enumeration Tree,SE-Tree）,然后针对故障输出无关元件的组合进行剪枝。本文在MCS-SFFO方法的基础上,结合电路的故障逻辑关系提出求解极小冲突集的进一步剪枝方法MCS-FLR,首先提出单元件非冲突集定理,对单元件集合进行剪枝,避免了对无解空间中单元件节点的访问;其次,提出非极小冲突集定理,推证得出故障输出相关元件集的超集都是冲突集,故对有解空间中的非极小解进行剪枝。MCS-FLR方法在MCS-SFFO方法基础上减少了大量有解空间和部分无解空间调用SAT求解器的次数,节省了求解时间。实验结果表明,相比于MCS-SFFO方法,MCS-FLR方法求解效率有显著提高。

关键词：极小不可满足集 SAT求解器哈斯图基于模型诊断集合枚举树故障输出无关元件故障输出相关元件

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：