《基于混合进化的子结构发现》PDF下载

  • 购买积分:10 如何计算积分?
  • 作  者:常新功著
  • 出 版 社:北京:国防工业出版社
  • 出版年份:2009
  • ISBN:9787118060669
  • 页数:204 页
图书介绍:本书介绍了使用进化算法进行图学习的一些概念、思想、方法和技术。全书共分七章,其中前三章为基础篇,介绍了图学习的基本概念、基本思想、发生发展历程、应用领域和典型的图学习算法Subdue系统,另外还介绍了进化算法的基本理论、基本思想、典型范式、一般框架、各个组成要素、典型实例和一个基于进化规划的子结构发现算法EPSD。第四、五、六章为算法设计篇,分别介绍了基于混合进化、基于回溯机制、基于带全部实例的个体表示和基于个体协同的四种混合进化子结构发现算法。第七章为应用篇,介绍了子结构发现算法在学科建设、区域经济研究、地震数据分析和反恐数据分析中的四个典型应用。附录中还给出了本书用到的多个图数据集。

第1章 绪论 1

1.1 图学习的目的 1

1.2 图学习的应用领域 4

1.3 子结构发现的研究现状 6

1.3.1 子结构发现所属的研究领域 6

1.3.2 子结构发现的发展历程 8

1.4 本书内容安排 10

1.5 本章小结 12

参考文献 13

第2章 子结构发现与Subdue系统 17

2.1 图的基本概念 17

2.1.1 图与带标签的图 17

2.1.2 度、路径、连通图 19

2.1.3 图同构、子图同构 19

2.2 图匹配 22

2.2.1 精确图匹配 22

2.2.2 不精确图匹配 24

2.3 子结构发现问题描述 27

2.3.1 子结构及实例 27

2.3.2 MDL与子结构的评价 29

2.3.3 子结构的扩展 30

2.3.4 子结构发现的作用和意义 31

2.4 Subdue系统 32

2.4.1 Subdue系统简介 32

2.4.2 Subdue子结构发现算法的伪码描述 33

2.4.3 图数据的组织与表示 34

2.4.4 图概念学习 40

2.4.5 图聚类 43

2.5 本章小结 47

参考文献 48

第3章 进化算法与EPSD进化子结构发现算法 50

3.1 什么是进化算法 50

3.1.1 最优化问题 51

3.1.2 从进化论和遗传变异理论到进化算法 53

3.1.3 进化算法的特点 55

3.2 进化算法的四种典型范式和一般框架 58

3.2.1 遗传算法 58

3.2.2 进化策略 59

3.2.3 进化规划 59

3.2.4 遗传规划 60

3.2.5 进化算法的一般框架 61

3.3 进化算法的各个组成部分及实例 62

3.3.1 表示和编码 62

3.3.2 评价函数 67

3.3.3 种群和多样性 67

3.3.4 选择 68

3.3.5 交叉和变异 70

3.3.6 种群初始化和算法终止条件 73

3.3.7 进化算法运行示例 74

3.4 EPSD进化子结构发现算法 78

3.4.1 个体的表示 78

3.4.2 适应值评价 78

3.4.3 种群初始化 78

3.4.4 变异 79

3.4.5 选择与精英保留 79

3.4.6 EPSD伪码描述 79

3.4.7 实验结果与分析 79

3.5 本章小结 82

参考文献 83

第4章 混合进化算法与混合进化子结构发现 85

4.1 混合进化算法设计 85

4.1.1 什么是混合进化算法 85

4.1.2 爬山算法、梯度下降法和模拟退火算法简介 86

4.1.3 为什么要混合 92

4.1.4 混合进化算法的分类 94

4.1.5 混合进化算法的理论模型 94

4.1.6 局部搜索算法的使用频率和使用强度 97

4.1.7 混合进化计算的发展现状 97

4.2 基于混合进化计算的子结构发现算法 98

4.2.1 染色体的表示 98

4.2.2 种群的初始化 101

4.2.3 适应值函数、选择和精英保留 101

4.2.4 变异 101

4.2.5 交叉 106

4.2.6 算法的伪码描述 109

4.3 实验结果与分析 111

4.3.1 HEASD与EPSD实验结果对比与分析 111

4.3.2 单标签扩展与Subdue扩展性能对比 112

4.3.3 混合算法的有效性验证 113

4.4 本章小结 115

参考文献 116

第5章 基于带状态回溯个体的混合进化子结构发现 120

5.1 子结构查找的单向性 121

5.2 可回溯的混合进化子结构发现算法 124

5.2.1 回溯法的基本原理和机制 124

5.2.2 HEASDBT基本思想 130

5.2.3 染色体的表示 133

5.2.4 种群的初始化 134

5.2.5 适应值、选择和精英保留 134

5.2.6 变异 134

5.2.7 交叉 136

5.2.8 及时去掉种群中没有潜力的个体和重新初始化 138

5.2.9 算法的伪码描述 140

5.3 实验结果与分析 142

5.3.1 HEASDBT与EPSD实验结果对比与分析 142

5.3.2 回溯的有效性验证 144

5.4 本章小结 145

参考文献 146

第6章 基于个体协同的混合进化子结构发现 147

6.1 子结构查找的瓶颈——实例丢失 148

6.2 带全部实例的混合进化子结构发现算法 151

6.2.1 染色体的表示 151

6.2.2 个体的评价 152

6.2.3 HEASDFI的其他组成部分 152

6.2.4 HEASDFI的实验结果与分析 152

6.3 基于个体协同的混合进化子结构发现算法 158

6.3.1 个体协同算子 158

6.3.2 一种新的多样性保持方案 165

6.3.3 算法的伪码表示 167

6.3.4 HEASDCI的实验结果与分析 167

6.4 本章小结 173

参考文献 174

第7章 应用研究 176

7.1 在信息与计算科学学科建设中的应用 176

7.1.1 问题的背景 176

7.1.2 数据的收集与表示 177

7.1.3 调整子结构评价方法以偏置查找 177

7.1.4 挖掘的结果及分析应用 178

7.2 在区域经济研究中的应用 179

7.2.1 引言 179

7.2.2 数据的收集与预处理 179

7.2.3 条件挖掘 183

7.2.4 挖掘的结果及分析 184

7.3 子结构发现在地震数据分析中的应用 185

7.3.1 地震数据库描述 185

7.3.2 地震数据的图表示 185

7.3.3 子结构发现过程及结果 187

7.3.4 判定地震的活动性 188

7.4 子结构发现在反恐中的应用 190

7.4.1 模拟数据集描述 191

7.4.2 学习有威胁的活动模式 191

7.4.3 学习有威胁组织的结构模式 193

7.4.4 学习有威胁组织的通信模式 195

7.5 本章小结 196

参考文献 196

附录一 实验的软硬件环境 198

附录二 实验图数据集 199