进化计算

第一章 生物进化与新达尔文主义 1

1.1 进化论 1

1.2 繁殖 5

1.3 变异 6

1.4 竞争 8

1.5 选择 11

1.6 进化优化受益者 14

1.7 适应与拓扑 19

1.8 总结 25

第二章 遗传算法的起源及搜索策略 26

2.1 遗传算法的起源 26

2.1.1 GA的定义 27

2.1.2 GA应用的例子 30

2.2 求解优化问题的搜索方法与搜索策略 37

2.2.1 搜索方法的分类 37

2.2.2 搜索方法的搜索策略 38

3.1 模式定理 42

3.1.1 模式的定义 42

第三章 遗传算法的基本理论 42

3.1.2 模式定理 43

3.1.3 建筑块假说 47

3.1.4 内在并行性 48

3.2 双臂赌机问题 50

3.2.1 双臂赌机问题及分析 51

3.2.2 模式定理的意义 58

3.2.3 k臂赌机问题的局限性 59

4.1.1 渐近收敛 61

4.1 收敛性的各种定义 61

第四章 遗传算法的收敛性分析 61

4.1.2 概率意义下的收敛 62

4.2 基于压缩映射原理的收敛性分析 62

4.2.1 压缩映射原理 63

4.2.2 cmGA及其收敛性分析 64

4.3 基于有限Markov链的收敛性分析 66

4.3.1 有关有限Markov链的预备知识 67

4.3.2 Markov链分析方法回顾 69

4.3.3 GA的收敛性分析 70

4.4 动力学模型 75

4.4.1 Vose模型 76

4.4.2 Bertoni模型 78

4.5 停止准则 81

第五章 遗传算法的改进 96

5.1 遗传算法的局限性 96

5.2 强方法与弱方法 99

5.3 二进制编码方案与浮点数编码方案 101

5.4 选择压力分析 107

5.4.1 选择算子的修改 108

5.4.2 适值函数的尺度变换 117

5.5 局部微调 119

5.6 动态编码 127

5.6.1 随机平均法 127

5.6.2 Delta编码与动态参数编码 130

5.7 欺骗问题与链接问题 133

5.8 种群规模分析 136

5.8.1 基于初始建筑块数目的种群规模分析 136

5.8.2 基于建筑块决策的种群规模分析 137

5.8.3 基于赌徒输光问题的种群规模分析 147

5.9 建筑块混合与控制图 154

5.10.2 线性假设引人 160

5.10 上位效应 160

5.10.1 上位效应概念 160

5.10.3 上位效应要素 161

第六章 mGA与LLGA 163

6.1 mGA 164

6.1.1 mGA的编码方案 164

6.1.2 mGA的遗传算子 165

6.1.3 mGA的算法流程 168

6.1.4 fmGA 170

6.2 LLGA 177

6.2.1 LLGA的编码方案 178

6.2.2 遗传算子 181

6.2.3 链接度与随机链接度 183

6.2.4 LLGA的算法流程 185

6.2.5 压缩内含子 186

第七章 约束条件的处理 188

7.1 线性约束条件 190

7.1.1 问题的简化 190

7.1.3 遗传算子 191

7.1.2 表示方案 191

7.1.4 初始化种群 194

7.1.5 应用GENOCOP的一个实例 195

7.1.6 GENOCOP的进一步改进 197

7.2 非线性约束条件 200

7.2.1 问题的一般形式 200

7.2.2 GENOCOPⅡ的算法流程 200

7.2.3 应用GENOCOPⅡ的实例 203

7.3 GENOCOPⅢ简介 208

8.1 旅行商(TSP)问题 212

第八章 组合优化问题 212

8.1.1 近邻表示 213

8.1.2 序表示 216

8.1.3 路径表示 218

8.1.4 边表示 224

8.1.5 其他表示方案 227

8.1.6 其他搜索策略 243

8.1.7 算法性能度量 244

8.2 调度问题 245

8.2.1 作业调度问题 246

8.2.2 时间表问题 250

第九章 进化策略和进化规划 252

9.1 进化算法的早期研究 252

9.2 进化策略 258

9.3 进化规划 262

9.4 进化算法的收敛性分析 269

9.4.1 进化算法的描述 270

9.4.2 用有限Markov理论分析进化算法 271

9.4.3 进化算法的收敛速率 274

第十章 进化计算框架 285

10.1 进化算法和遗传算法之间的哲学差别 285

10.2 交叉算子与变异算子的比较 287

10.3 进化计算框架 296

10.3.1 表示法 297

10.3.2 进化算子 298

10.3.3 算法定义 300

10.3.4 gfmGA的形式化定义 302

11.1 遗传机器学习概述 311

第十一章 遗传机器学习 311

11.1.1 遗传机器学习系统的结构 312

11.1.2 匹兹堡方法与密西根方法 314

11.1.3 产生式系统体系结构 316

11.2 机器学习方法一：参数调节 319

11.3 机器学习方法二：改变数据结构 327

11.4 密西根方法：分类器系统 334

11.4.1 分类器系统概述 335

11.4.2 信度分配机制——斗链式算法 338

11.4.3 分类器重组机制——遗传算法 343

11.4.4 分类器的运行 343

11.5 分类器实例 345

11.5.1 ANIMATE分类器系统 345

11.5.2 煤气管道操作分类器系统 349

11.5.3 新型战斗机驾驶规则学习 352

11.6 匹兹堡方法：学习系统 368

11.6.1 学习系统概述 370

11.6.2 规则集合的重组 372

11.7 组织学习方法 374

11.6.3 LS-I的性能 374

11.7.1 组织的增长 375

11.7.2 自主组织学习 384

11.8 囚徒窘境问题 400

11.8.1 Axelrod竞赛 402

11.8.2 Fogel有限状态机 403

第十二章 机器人轨迹规划 419

12.1 机器人系统 419

12.2 机器人仿真模型 422

12.3.1 轨迹规划表示 423

12.3 机器人轨迹规划方法 423

12.3.2 轨迹规划方法 427

12.3.3 Lamarck效应和子目标回报 431

12.4 机器人轨迹规划的应用 436

12.4.1 MR-501特性 436

12.4.2 机器人轨迹规划系统设计 437

12.4.3 机器人规划的性能 443

附录A 有限状态自动机 451

附录B 产生式系统 454

参考文献 460