学位论文 > 优秀研究生学位论文题录展示

求解极小碰集的ROBDD算法的研究与分析

作　者: 艾阳
导　师: 李占山
学　校: 吉林大学
专　业: 计算机软件与理论
关键词: 二元决策图 启发式编序 基于模型的诊断 碰集
分类号: TP181
类　型: 硕士论文
年　份: 2011年
下　载: 33次
引　用: 0次
阅　读: 论文下载
 

内容摘要


基于模型诊断(Model-based diagnosis)是一种智能推理方法,它的出现是为了弥补传统的故障诊断方法的缺点。基于模型诊断已经应用于通信、航天、燃气轮机监控、交通、电子设备等诸多领域。其基本思想是构建待诊断系统的抽象模型,并观测系统的实际行为,当观测行为与系统的预测行为相左时,确认出故障诊断。涉及的四个过程为构建系统模型,冲突鉴别,候选诊断以及诊断。目前MBD的研究重点有以下两种：溯因诊断以及基于一致性诊断,本文中主要讨论的就是基于一致性诊断问题。基于模型诊断中极小碰集的求解问题被证明是NP-complete的。近年来,国内外的研究者不断提出求解碰集的新思想以及优化方法,目的是降低时间的消耗。二元决策图(Binary Decision Diagrams)简称BDD,是于1959年被提出的有根非循环图结构。目前,BDDs在很多领域都有广泛的应用,例如计算机网络、逻辑综合和验证等。Randel在1986年提出BDD中变量顺序对最终生成的BDDs规模有较大的影响的观点。从此以后,很多国内外的研究者针对BDDs变量的顺序排序问题进行了大量并深入的研究。由于最优变量排序问题已经被证明为NP-完全问题,所以目前很多研究者通过对应用领域的研究,设计适当的启发式排序方法,得到较为合理的ROBDD编序方法。适当的编序方法可以缩小BDD的规模,减少BDD算法的运行时间。本文中采用的就是启发式编序相结合的ROBDD求解算法。近年来,已经有国内外学者将OBDDs应用到基于模型诊断问题中,本文也提出运用ROBDDs求解基于模型诊断问题中极小碰集的新思想。把目光聚焦到候选诊断过程(即通过极小冲突集推导出极小碰集的过程)上,提出ROBDD求解极小碰集的方法。这一方法的主要思想为：首先把问题系统构建为析取式方程组的形式,然后根据OBDDs这一数据结构的高压缩性、操作的高效性以及布尔表达式的表示形式等性质,分别应用VCD-Order和FD-Order操作对冲突集簇中的变量进行编序,利用生成的编序序列把冲突集编译成独立ROBDD形式,再进行ROBDDs的与运算,求得系统的碰集。最后进行极小化操作提取极小碰集。本算法不存在类似于某些求解算法由于剪枝而丢失解的现象。因为OBDDs是种高压缩的数据结构,所以占用的空间较少,并且算法容易理解和实现。由于本算法中没有应用随机算法,故可以得到所有的极小碰集,即ROBDD求解算法是完备的。但利用ROBDDs求解碰集需要碰集的极小化操作,才能得到故障系统的极小碰集,这一操作降低了整体算法的效率。我们在本文中提到的两种ROBDDs求解极小碰集的算法,是分别基于变量相关性和基于变量频率来对ROBDDs进行编序约束的。我们通过理论推导,证明了ROBDD方法的有效性以及完备性。通过大量的对比实验,我们可以看到ROBDD算法在随机生成冲突集上有较明显的效率优势。并且通过对基于变量相关性的ROBDD算法和基于频率的ROBDD算法的研究和实验,总结出这两个方法的使用范围。本文提出的两种ROBDDs方法还都有需要改进的地方,以后可以将两种方法相结合提出更为优化的ROBDDs求解碰集的新方法。

全文目录


摘要  4-6
Abstract  6-10
第1章 绪论  10-13
  1.1 研究背景及现状  10-12
    1.1.1 基于模型诊断研究背景与现状  10
    1.1.2 BDD的研究背景与现状  10-12
  1.2 本文的主要工作  12-13
第2章 基于模型诊断与BDD的基础知识  13-23
  2.1 基于模型诊断基础知识  13-16
    2.1.1 基本概念  13-15
    2.1.2 求解极小碰集方法介绍  15-16
  2.2 BDD基础知识  16-23
    2.2.1 BDD的预备知识  16-18
    2.2.2 OBDD的常用操作  18-21
    2.2.3 OBDD的特点  21-23
第3章 基于变量相关性编序的ROBDD求解碰集  23-38
  3.1 算法说明  23-29
  3.2 完备性分析  29-30
  3.3 实验结果  30-37
    3.3.1 随机生成冲突集测试  30-33
    3.3.2 固定冲突集测试  33-37
    3.3.3 实验结果分析  37
  3.4 总结  37-38
第4章 基于频率相关性编序的ROBDD求解碰集  38-45
  4.1 算法说明  38-39
  4.2 实例说明  39-40
  4.3 测试结果  40-44
  4.4 总结  44-45
第5章 结论  45-46
参考文献  46-49
作者简介及在学期间所取得的科研成果  49-50
致谢  50

相似论文

  1. 基于时间自动机的模型验证技术,TP301.1
  2. MBD在配电网故障诊断中的应用研究,TM711
  3. 基于BDD的多阶段任务系统可靠性建模分析,TB114.3
  4. 求解极小碰集的遗传算法的研究与改进,TP18
  5. 基于一致性诊断中若干问题研究,TP18
  6. 基于BDD的碰集与配置求解,TP311.12
  7. 符号化模型检测算法的研究,TP311.52
  8. 一种基于基数的领域特征模型检验方法,TP301
  9. 基于模块化思想的动态故障树分析方法研究,TP18
  10. 多阶段任务系统BDD排序方法研究,TB114.3
  11. 二元决策图的排序优化及故障树转化方法的研究,TP311.5
  12. 基于Windows Mobile5.0平台的故障树分析软件设计与开发,TP311.52
  13. 基于模型检测方法的规划,TP18
  14. 动态故障树分析方法及其实现,TP18
  15. 基于符号模型检测方法的应对规划系统,TP311.52
  16. 基于故障树技术的远程故障诊断专家系统的研究,TP182
  17. 模型检测在模型诊断领域中的应用,TP277
  18. 复杂系统的故障诊断及容错控制研究,O157.5
  19. 基于二元决策图的组合电路测试生成方法研究,TP391.7
  20. 应用Bayesian网处理基于一致性诊断中的不确定性问题的研究,TP183

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化基础理论 > 人工智能理论 > 自动推理、机器学习
© 2012 www.xueweilunwen.com