| 【中文题名】 | 求解极小碰集的遗传算法及其相关算法的研究 |
| 【英文题名】 | Research of Genetic Algorithm and Relative Algorithms for Minimal Hitting Sets |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-6 |
| 【中关键词】 | 基于模型的诊断,碰集,遗传算法,等价部件,集合枚举树,对分二叉树 |
| 【英关键词】 | |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
本文首先简单介绍了基于模型诊断的基本思想、诊断过程及一些诊断引擎和系统的相关知识。然后提出了计算极小碰集的一个新方法—EC-GA方法,并与其他方法进行了实验对比,指出我们方法的优点及适用范围。接下来介绍诊断产生过程中其他用于产生所有极小碰集的改进方法SEHS-GA方法和SEHS-EC方法,以及基于对分HS树,介绍BHSGA-tree,BHSEC-tree,BHSSE-tree三种相关改进方法,并通过与其他方法进行理论和实验比较说明了我们方法的优点及适用情形;本文还针对实例关于对分HS树提出的增量诊断算法进行了改正,并依据测量点顺序选择给出一点改进。 |
| 【论文题纲】 |
|
内容提要 |
4-7 |
|
第一章 引言 |
7-10 |
|
1.1 研究背景 |
7-8 |
|
1.1.1 基于模型诊断的简介 |
7-8 |
|
1.1.2 基于模型诊断的步骤 |
8 |
|
1.2 本文主要工作 |
8-10 |
|
第二章 诊断产生之算法：EC-GA |
10-24 |
|
2.1 引言 |
10 |
|
2.2 预备知识 |
10-12 |
|
2.3 算法描述 |
12-19 |
|
2.3.1 遗传算法的基本内容 |
12-15 |
|
2.3.2 等价部件和同构诊断 |
15-17 |
|
2.3.3 EC-GA 算法 |
17-19 |
|
2.4 示例及结果验证 |
19-21 |
|
2.5 与其他算法的比较 |
21-22 |
|
2.6 小结 |
22-24 |
|
第三章遗传算法和等价部件在SE-TREE 及BHS-TREE 结构中的应用 |
24-54 |
|
3.1 引言 |
24 |
|
3.2 集合枚举树（SE-TREE） |
24-26 |
|
3.3 RYMON 的SE-HS 算法 |
26-30 |
|
3.4 SEHS-GA 和SEHS-EC 算法 |
30-34 |
|
3.4.1 SEHS-GA 方法描述 |
30-32 |
|
3.4.2 SEHS-EC 方法描述 |
32-34 |
|
3.5 BHS-TREE 方法 |
34-38 |
|
3.6 BHSGA-TREE 方法和BHSEC-TREE 方法 |
38-46 |
|
3.6.1 BHSGA-tree 方法描述 |
38-40 |
|
3.6.2 BHSEC-tree 方法描述 |
40-43 |
|
3.6.3 BHSSE-tree 方法简介 |
43-46 |
|
3.7 本章方法总结和比较 |
46-51 |
|
3.7.1 本章方法简单总结 |
46-47 |
|
3.7.2 本章方法的比较 |
47-51 |
|
3.8 诊断产生的各种算法的相关讨论 |
51-54 |
|
第四章求解极小碰集的相关优化问题 |
54-58 |
|
4.1 引言 |
54 |
|
4.2 一种增量式计算极小碰集的改进 |
54-56 |
|
4.3 小结 |
56-58 |
|
第五章结论 |
58-59 |
|
参考文献 |
59-62 |
|
摘 要 |
62-65 |
|
ABSTRACT |
65-68 |
|
致谢 |
68-69 |
|
导师及作者简介 |
69 |
|
| 【DOI】 | LunWen.ID:2.2008.388746 |
