积分商城

最新搜索： ARINC429 Souce Insight 3.5 Vivo手机原理图 UltraEdit PBOC 导航
您现在的位置是：首页 > 技术资料 > 结合电路结构基于分块的诊断方法
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

结合电路结构基于分块的诊断方法

更新时间：2019-12-24 17:52:21 大小：806K 上传用户：守着阳光1985查看TA发布的资源 标签：电路结构 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

基于模型的诊断问题在人工智能领域内一直备受关注,将诊断问题转换成SAT(Satisfiable)问题成为解决基于模型诊断问题的一个重要方法.基于目前高效诊断方法 LLBRS-Tree(Last-Level Based on Reverse Search-Tree)的研究,本文提出电路分块诊断方法 ACDIAG(Abstract Circuit Diagnosis)方法,对电路进行分块来缩减电路规模,利用LLBRS-Tree方法对分块后抽象电路求得极小块诊断解;提出诊断解拓展方法,结合分块后电路结构特征对每个极小块诊断解进行直接扩展得到极小诊断解,避免对抽象电路还原后才能得到所有解的问题.


部分文件列表

文件名 大小
结合电路结构基于分块的诊断方法.pdf 806K

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
7
Vol． 46 No． 7  
Jul． 2018  
第
期
电
子
学
报
2018  
7
ACTA ELECTRONICA SINICA  
年
月
结合电路结构基于分块的诊断方法  
1，2  
1，2  
1，2  
1，2  
1，2  
， ， ， ，  
欧阳丹彤 刘伯文 刘 梦 张立明 张永刚  
( 1．  
，
吉林大学计算机科学与技术学院 吉林长春  
130012;  
2．  
，
吉林大学符号计算与知识工程教育部重点实验室 吉林长春  
130012)  
:
，
基于模型的诊断问题在人工智能领域内一直备受关注 将诊断问题转换成  
SAT( Satisfiable)  
摘
要
问题成为  
．
解决基于模型诊断问题的一个重要方法 基于目前高效诊断方法  
LLBRS-Tree( Last-Level Based on Reverse Search-Tree)  
，
的研究 本文提出电路分块诊断方法  
ACDIAG( Abstract Circuit Diagnosis)  
， ，  
方法 对电路进行分块来缩减电路规模 利用  
LLBRS-Tree  
; ，  
方法对分块后抽象电路求得极小块诊断解 提出诊断解拓展方法 结合分块后电路结构特征对每个极小  
，
块诊断解进行直接扩展得到极小诊断解 避免对抽象电路还原后才能得到所有解的问题  
．
:
; SAT  
; ;  
问题 枚举树 抽象  
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
基于模型诊断  
:
TP306  
:
A
:
文章编号  
0372-2112 ( 2018) 07-1571-07  
文献标识码  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 07． 005  
电子学报  
A Block-Based Diagnostic Method Combining with the Circuit Structure  
1，2  
1，2  
1，2  
1，2  
1，2  
OUYANG Dan-tong ，LIU Bo-wen ，LIU Meng ，ZHANG Li-ming ，ZHANG Yong-gang  
( 1． College of Computer Science and Technology，Jilin University，Changchun，Jilin 130012，China;  
2． Ministry Education Key Laboratory of Symbolic Computation and Knowledge Engineering，Jilin University，Changchun，Jilin 130012，China)  
Abstract: Model-based diagnosis problem has been attracting much attention in the field of artificial intelligence． It is  
an important technique for solving model-based diagnosis problem by converting diagnosis problem to SAT． Based on the re-  
search of LLBRS-Tree，this paper proposes an ACDIAG method． Firstly，the circuit blocking method is used to block the cir-  
cuit via circuit structure so as to downscale circuit． Then，minimal block diagnoses are acquired on the abstract circuit after  
blocking via LLBRS-Tree． Secondly，diagnosis extending method is given to extend minimal block diagnoses to obtain other  
diagnoses directly via circuit structure． It avoids the drawback that extending diagnoses need to restore the abstract circuit．  
Key words: model-based diagnosis; SAT problem; enumeration tree; abstract  
［6］  
．
，
完备的极小碰集求解方法随问题规模上升  
的方法  
1
引言  
．
复杂度会以指数级增长 目前效率较高的方法主要包  
［7］  
( Model-Based Diagnosis，MBD)  
基于模型的诊断  
问
、
括姜云飞等学者提出的布尔代数方法  
基于并行的  
［8］  
，
题是人工智能领域内的一个重要问题 推动着人工智  
、
碰集算法  
结合特征学习的粒子群求解极小碰集方  
［1］  
［9］  
［10］  
．
MBD ，  
直接求解难度较大 著名学  
能的发展  
早期由于  
de Kleer ，  
提出的冲突集 概念 设计了一  
、
．
等
法
基于连接关系的分布式求解方法  
［2］  
Reiter  
者
结合  
NP  
，
求解极小冲突集以及求解极小碰集都是  
问题  
［3］  
，
个高效的诊断求解方法  
首先求解电路的所有极小  
MBD  
，
随着对  
问题更深入的研究与计算机硬件的发展  
MBD  
， ，  
冲突集 然后对这些极小冲突集求解极小碰集 并证明  
，
许多学者为避免这两步求解过程 对直接求解  
方
［11］  
．
了这些极小碰集是整个电路的所有极小诊断解 国内  
，
SAT  
法进行了研究  
其中将诊断问题转换为  
问题是  
问题是第  
也是人工智能领域内的  
SAT  
［12］  
外许多学者对求解极小冲突集与极小碰集的算法进行  
MBD  
． SAT  
直接求解  
一个被证明的  
一个重要研究问题之一 近年来 在  
，SAT  
问题的重要方法之一  
［4］  
［13］  
．
了研究 早期学者提出使用定理证明器的方法 与归  
NP  
，
完全问题  
［5］  
， ．  
结方法 求解极小冲突集 但是效率较低 随后国内学  
．
，
竞赛的鼓励  
SAT  
者提出了结合枚举树与电路逻辑关系的利用  
求解  
，
SAT  
下
求解技术的发展引人注目 现在的  
求解器  
: 2016-12-29;  
: 2017-09-07; :  
责任编辑 孙瑶  
收稿日期  
修回日期  
:
基金项目 国家自然科学基金  
( No． 61672261，No． 61502199，No． 61402196，No． 61373052) ;  
( No． LY16F020004)  
浙江省自然科学基金  
1572  
2018  
年
电
子
学
报
［14，15］  
．
MBD  
Tree) ，  
中的每个结点 结点中的元件假设为故障并将其  
已经可以较快地处理更大规模的实例  
将
问
SAT  
，
问题进行求解 能够克服诊断问题复杂  
．
余元件都置为正常  
题转换为  
［16］  
，
性不断增加的难题 因而得到众多学者的广泛关注  
．
( 2)  
1
把步骤 中的对应单元子句加入到电路的  
，
近年来 国内外学者开始研究结合结构信息对基  
CNF  
，
中 调用  
SAT CNF  
求解器对电路  
．
进行一致性检测  
SAT ． ，Smith  
求解诊断的方法进行优化 起初  
， ， ．  
若可满足 则该结点是一个诊断解 把此诊断解保存 检  
于
等学者  
SAT  
，
问题 结合电路中自由输入变  
SE-Tree  
，
中 所 有 结 点 后 最 后 得 到 所 有 极 小 诊  
将诊断问题转换成  
测完  
SAT  
， ．  
的搜索空间 提高诊断效率 随  
．
量的结构信息压缩  
断解  
［17］  
，Siddiqi  
后
等学者提出结合统治关系进行抽象的方  
2. 3 LLBRS-Tree  
方法  
在基于反向搜索的有解无解剪枝  
MBD，  
，
对抽象后的电路进行诊断 得到诊断解后  
法求解  
LLBRS-Tree  
方法  
．
对每一个抽象电路还原后分别求解 赵相福等学者提  
， ，  
中 不仅剪掉是诊断解的结点 而且还对不是诊断解的  
［18］  
SAT  
CSSE-Tree  
出了基于枚举树并利用  
求解器的  
方
．
冗余结点也进行剪枝 在下面介绍有解剪枝与无解剪  
［19］  
． Amit Metodi  
Section  
法求解诊断问题  
提出  
概念并结  
．
枝及反向搜索遍历的相关定义  
［20］  
Cone  
，
的作用 从电路结构的角度对基于  
SAT  
的诊断  
3
，
反向搜索 针对一棵枚举树 当枚举树  
合
定义  
，
进行了优化 缩减了诊断问题的求解时间  
．
，
的层数已经给定的情况下 称从枚举树的最后一层向  
，
周建华等对问题结构特征进行了研究 对  
CSSE-  
．
枚举树的根结点搜索的过程为反向搜索  
Tree  
，
方法进行改进 提出了有解空间与无解空间剪枝方  
SAT  
在调用  
求解器来判断当前元件集合是否为诊  
［20］  
( LLBRS-Tree  
) ，  
方法 既结合了枚举树和诊断问题  
，LLBRS-Tree  
法
断解的时候  
先对比较长的组件集合进行求解 使得求解的  
SAT  
方法结合反向搜索遍历方法  
，
的特征 又利用了  
SAT  
，
求解器的特点 是一种求解效率  
，
CNF  
问
． : ，  
较高的方法 该文提出了两个优化策略 第一 利用反向  
，
．
求解时所耗费的时间  
题的规模较小 进而减少  
，
搜索的思想 对部分集合枚举树从底层结点到根结点  
LLBRS-tree  
1
算法步骤如算法 所示  
．
; ，  
进行深度优先搜索 第二 结合非诊断解结点的祖先结  
1
LLBRS-tree  
算法  
算法  
( ) ，  
点 真子集 不是解的思想 进行无解剪枝  
．
LLBRS-Tree  
，
方法充分研究基础上 借鉴  
本文在对  
现有电路抽象方法 结合电路结构提出一种新的分块  
LLBRS-Tree  
step 1.  
step 2.  
step 3.  
step 4.  
step 4a．  
．
生成集合枚举树  
，
， ，  
寻找当前未判断的最左结点 若未找到 跳转  
step 6．  
．
抽象策略 将电路进行分块后利用  
方法先  
求解抽象电路的极小块诊断解 并提出了一种由极小  
块诊断解快速拓展得到原电路所有极小诊断解的方  
SAT  
．
求解器检查结点的一致性  
调用  
若可满足  
该候选解判断其极小性 若极小则删去原诊断解集合中该候  
，
，
，
选解的所有超集 然后该候选解加入诊断解集合  
．
． ，  
法 结合电路结构与电路信号的传递关系 快速拓展得  
step 4b．  
step 5.  
， ，  
使用有解剪枝策略 找到其父结点 跳转  
step 3．  
，
到极小诊断解 避免了对抽象电路还原后才能得到所  
， ， ，  
若不可满足 使用无解剪枝策略 跳过祖先结点 找到下一个  
．
有极小诊断解的问题  
，
要访问的结点 跳转  
step 3．  
step 6.  
．
返回诊断解集合  
2
基于反向搜索的有解无解剪枝方法  
2. 1 MBD  
问题  
3
电路分块诊断方法  
［3］  
1
DS = ( SD，  
诊断系统被定义为三元组  
定义  
COMPS，OBS) ，  
其中  
: SD  
，COMPS  
LLBRS-Tree  
表示系统描述  
表示系  
上一部分介绍了  
方法求解极小诊断基  
算法基础上提出了电路分  
LLBRS-Tree  
，
本思想 本章在  
LLBRS-Tree  
，OBS  
．
表示系统观测集  
统元件集  
［3］  
ACDIAG，  
此方法在  
2
COMPS，  
块诊断方法  
方法基础  
定义  
设 元 件 集 的 一 个 子 集 Δ   
SD  
．
上加入了电路规模缩减方法和诊断解扩展方法 下面  
AB( c)  
c ，  
为 真 表 示 元 件 故 障 如 果  
:
OBS  
∪
∪
ACDIAG  
， 、  
方法的基本思想 相关定义 定理及其证  
{ － AB( c) | c COMPS －  
的 则 Δ 是关于  
}
{
( SD，COMPS，OBS)  
AB( c) | c  
}
∈Δ 是 可 满 足  
的基于一致性诊断  
给出  
明和分析  
3. 1  
∈
Δ ∪  
．
，
．
， '  
称 Δ 是极小一致性诊断 当任意 Δ Δ 不是基于  
电路分块方法  
．
一致性诊断  
2. 2  
电路分块方法结合电路结构特征对电路进行分  
， ．  
块 从而实现缩减求解电路的规模 下面介绍该方法相  
SAT  
结合枚举树调用  
的诊断方法  
．
SAT  
关概念和思想  
使用  
:
求解器和枚举树来求解极小诊断的基本  
4
定义  
基本元件 如果元件输入端个数小于等  
步骤  
［21］  
2，  
称此元件为基本元件  
．
( 1)  
( Set-Enumeration-Tree，SE-  
于
检测集合枚举树  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号