第一章 绪论 1
1.1 引言 1
1.2 生物进化 2
1.3 遗传算法 3
1.3.1 基础用语 3
1.3.2 标准遗传算法 5
1.4 遗传算法的特点 10
1.4.1 遗传算法和其它传统搜索方法的对比 10
1.4.2 遗传算法和若干搜索方法的亲近关系 13
1.4.3 遗传算法和自律分布系统的亲近关系 14
1.5 遗传算法的研究历史和现状 14
1.5.1 遗传算法的研究概况 14
1.5.2 遗传算法研究的新焦点 21
1.6 遗传算法今后研究的主要课题 23
参考文献 26
第二章 遗传算法的基本原理和方法 28
2.1 模式定理(schemate theorem) 28
2.1.1 模式 29
2.1.2 模式定理 30
2.2 积木块假设 36
2.3 骗问题 41
2.4 隐并行性 48
2.5 性能评估 49
2.6 编码 51
2.6.1 编码问题 51
2.6.2 编码(译码)评估规范和编码原理 52
2.6.3 编码技术 55
2.7 群体设定 67
2.7.1 初始群体设定 67
2.7.2 群体多样性 68
2.8 适应度函数 69
2.8.1 目标函数映射成适应度函数 70
2.8.2 适应度函数定标(scaling) 71
2.8.3 适应度函数的设计对遗传算法的影响 74
2.9 遗传操作 75
2.9.1 选择算子 76
2.9.2 交叉算子(crossover operator) 81
2.9.3 变异算子(mutation operator) 85
2.10 收敛性 88
2.10.1 未成熟收敛 88
2.10.2 有限马尔柯夫链 90
2.10.3 标准遗传算法的收敛性 92
参考文献 98
第三章 遗传算法与组合优化 101
3.1 基于遗传算法的组合优化方法 101
3.1.1 遗传算法的关键参数确定 102
3.1.2 几种流行的选择机制 103
3.1.3 适应度函数的定标 106
3.1.4 二倍体(diploidy)与显性(dominance)技术 107
3.1.5 物种形成(speciation)与小生境(niche)技术 111
3.2 函数优化(functio optimization) 117
3.2.1 问题描述 117
3.2.2 编码与适应度函数 121
3.2.3 基本遗传算法(SGA)的搜索性能 122
3.2.4 基本遗传算法的若干变体形式的搜索性能 127
3.3 背包问题(knapsack problem) 130
3.3.1 问题描述 130
3.3.2 遗传编码 131
3.3.3 适应度函数 131
3.3.4 基于基本遗传算法求解背包问题 132
3.3.5 基本遗传算法的搜索能力 135
3.3.6 基于“与/或”交叉方法求解背包问题 136
3.4 货郎担问题 137
3.4.1 编码与适应度函数 137
3.4.2 交叉策略 138
3.4.3 变异技术 141
3.4.4 选择机制和群体构成 142
3.4.5 混合GA技术 143
3.4.6 基于遗传算法求解TSP的算法实现 143
3.5 混合搜索方法 147
3.5.1 概述 147
3.5.2 启发式搜索法简介 148
3.5.3 混合遗传算法(Hybrid GA) 151
3.5.4 实验与讨论 153
3.6 图的划分问题 158
3.6.1 问题描述 158
3.6.2 编码与适应度函数设计 158
3.6.3 遗传操作 159
3.6.4 实验结果 159
参考文献 161
第四章 遗传算法与机器学习 164
4.1 概述 164
4.2 分类器系统 166
4.2.1 规则与消息 168
4.2.2 桶队算法 171
4.2.3 遗传算法 174
4.3 学习系统LS-1 177
4.3.1 LS-1与CS-1的区别 177
4.3.2 LS-1的工作原理 178
4.4 基于遗传算法的概念学习系统 182
4.4.1 搜索空间的表示 184
4.4.2 遗传操作 186
4.4.3 执行过程 187
4.4.4 非标准操作 188
4.4.5 GABIL系统的自适应性 189
4.5 小结 191
参考文献 192
第五章 遗传算法与并行处理 195
5.1 遗传算法固有的并行性及其并行化的困难 195
5.1.1 源于自然的并行性 195
5.1.2 遗传算法理论中的并行性 196
5.1.3 遗传算法在并行实现上的困难 197
5.2 遗传算法的并行化途径 198
5.2.1 主从式(master-slave)并行化方法 198
5.2.2 粗粒度模型 200
5.2.3 细粒度模型 201
5.3 粗粒度的孤岛模型 202
5.3.1 粗粒度模型的生物学依据 203
5.3.2 粗粒度模型的研究现状 204
5.3.3 孤岛模型在MIMD机器上的实现 205
5.3.4 扩展的分布式遗传算法 211
5.4 细粒度的邻域模型 214
5.4.1 细粒度模型的理论基础 215
5.4.2 细粒度模型的研究现状 216
5.4.3 MIMD上的细粒度模型的实现 217
5.4.4 SIMD上的细粒度模型的实现 220
5.5 粗粒度模型与细粒度模型的性能比较 222
5.6 实现并行遗传算法的一个例子 224
5.6.1 迁入式算法 224
5.6.2 迁出式算法 226
5.6.3 扩散式算法 227
5.7 LCS的并行实现 229
5.7.1 执行系统 230
5.7.2 信用系统中的分配策略 232
5.7.3 遗传算法在LCS中的应用 232
5.7.4 LCS的一个MIMD实现 233
5.7.5 LCS在CM机器上的实现 235
参考文献 237
第六章 神经网络、模糊集理论和进化算法 241
6.1 遗传算法与神经网络 241
6.1.1 神经网络的发展 241
6.1.2 神经网络连接权的进化 245
6.1.3 神经网络结构的进化 250
6.1.4 神经网络学习规则的进化 257
6.2 遗传算法与模糊集理论 258
6.2.1 基于遗传算法的模糊推理规则的优化 259
6.2.2 遗传算法在模糊模式识别中的应用 262
6.3 进化算法 271
6.3.1 引言 271
6.3.2 进化算法的总框架 274
6.3.3 遗传算法 275
6.3.4 进化规划 277
6.3.5 进化策略 279
6.3.6 交叉和变异的关系 282
6.3.7 小结 284
参考文献 285
第七章 遗传算法与人工生命 287
7.1 人工生命的研究内容和方法 287
7.1.1 人工生命及其特征 287
7.1.2 人工生命研究的内容与方法 289
7.2 遗传算法与人工生命进化模型 292
7.3 L系统与形态生成模型 295
7.3.1 L系统与植物形态 295
7.3.2 植物的形态生成模型 296
7.3.3 讨论 303
7.4 博弈型人工生态系统 307
7.4.1 博弈与策略 308
7.4.2 博弈型生态系统 311
7.4.3 生态动力学与自组织化 314
7.5 人工生命与遗传信息处理 318
7.5.1 人类信息世界 319
7.5.2 监视遗传 321
7.5.3 遗传信息处理模型 322
7.5.4 基于遗传信息处理模型的人工生命合成 325
7.5.5 人工生命与人工智能 327
参考文献 332
第八章 遗传算法应用实例 334
8.1 遗传算法在图像恢复中的应用 334
8.1.1 引言 334
8.1.2 图像退化模型 335
8.1.3 遗传算法用于图像恢复 335
8.1.4 遗传算法与贝叶斯方法相结合的图像恢复 340
8.2 遗传算法在图像识别中的应用 345
8.2.1 引言 345
8.2.2 数学模型 347
8.2.3 目标函数形成 348
8.2.4 随机全局优化方法 351
8.2.5 实验结果 352
8.3 遗传算法在控制中的应用 354
8.3.1 操作序列的最优化 355
8.3.2 倒立摆控制 356
8.4 调度问题 358
8.4.1 车间作业调度问题 359
8.4.2 两种解法 359
8.4.3 实验 366
8.5 硬件进化 368
8.5.1 硬件进化的特点 369
8.5.2 硬件进化的学习方法 371
8.5.3 实例 375
参考文献 383
附录A SGA程序 385
附录B TSP程序 397
附录C CLS程序 416