进化优化算法 基于仿生和种群的计算机智能方法
作者： （美）丹·西蒙著；陈曦译
出版时间：2018年版
内容简介
　　进化算法是一种人工智能.自然界中观察到的诸如自然选择、物种迁移、鸟群、人类文化、和蚁群等优化过程启发新太阳城开发出进化算法.本书讨论进化优化算法的理论、历史、数学和编程.主要包括遗传算法、遗传规划、蚁群优化、粒子群优化、差分进化、基于生物地理学优化以及其他多种算法.以一种直观但理论上严谨的方式介绍进化算法，同时重视算法的实施.仔细讨论了较新的进化算法，包括反向学习、人工鱼群、细菌觅食以及其他多种算法.每章都配有练习题，教师可以在线获得习题答案.借助简单的例子帮助读者直观理解理论.从作者的网页上可以得到主要的源代码.介绍分析进化算法的数学技巧，包括马尔可夫建模和动态系统建模.本书适合作为高年级本科生和研究生的教材， 对工程和计算机科学领域的研究人员也大有裨益.
目录
致谢 .17

缩写 .19

第一篇进化优化引论 1

第 1章绪论 3

1.1术语 3

1.2又一本关于进化算法的书 5

1.3先修课程 .5

1.4家庭作业 .6

1.5符号 6

1.6本书的大纲 8

1.7基于本书的课程 .8

第 2章优化 10

2.1无约束优化 10

2.2约束优化 . 13

2.3多目标优化 14

2.4多峰优化 . 15

2.5组合优化 . 16

2.6爬山法 18

2.6.1有偏优化算法 21

2.6.2蒙特卡罗仿真的重要性 21

2.7智能 22

2.7.1自适应 22

2.7.2随机性 22

2.7.3交流 . 23

2.7.4反馈 . 23

2.7.5探索与开发 . 24

2.8总结 24

习题 . 25

4目录

第二篇经典进化算法 29

第 3章遗传算法 31

3.1遗传学的历史 32

3.1.1查尔斯·达尔文 32

3.1.2格雷戈尔·孟德尔 . 33

3.2遗传学 34

3.3遗传算法的历史 . 36

3.4一个简单的二进制遗传算法 38

3.4.1用于机器人设计的遗传算法 38

3.4.2选择与交叉 . 39

3.4.3变异 . 42

3.4.4遗传算法的总结 42

3.4.5遗传算法的参数调试及其例子 43

3.5简单的连续遗传算法 47

3.6总结 50

习题 . 51

第 4章遗传算法的数学模型 . 53

4.1图式理论 . 54

4.2马尔可夫链 57

4.3进化算法的马尔可夫模型的符号 61

4.4遗传算法的马尔可夫模型 64

4.4.1选择 . 64

4.4.2变异 . 65

4.4.3交叉 . 66

4.5遗传算法的动态系统模型 69

4.5.1选择 . 69

4.5.2变异 . 71

4.5.3交叉 . 73

4.6总结 77

习题 . 78

第 5章进化规划 80

5.1连续进化规划 80

5.2有限状态机优化 . 83

5.3离散进化规划 86

5.4囚徒困境 . 87

目录 5

5.5人工蚂蚁问题 90

5.6总结 93

习题 . 94

第 6章进化策略 96

6.1 (1+1)进化策略 97

6.2 1/5规则:推导 . 100

6.3 (μ + 1)进化策略 103

6.4 (μ + λ)和 (μ, λ)进化策略 105

6.5自身自适应进化策略 107

6.6总结 112

习题 . 112

第 7章遗传规划 114

7.1 LISP:遗传规划的语言 115

7.2遗传规划的基础 . 120

7.2.1适应度的度量 120

7.2.2终止准则 121

7.2.3终止集合 121

7.2.4函数集合 122

7.2.5初始化 123

7.2.6遗传规划的参数 125

7.3最短时间控制的遗传规划 127

7.4遗传规划的膨胀 . 132

7.5演化实体而非计算机程序 133

7.6遗传规划的数学分析 135

7.6.1定义和记号 . 135

7.6.2选择和交叉 . 136

7.6.3变异和最后结果 139

7.7总结 140

习题 . 142

第 8章遗传算法的变种 145

8.1初始化 145

8.2收敛准则 . 146

8.3用格雷编码表示问题 148

8.4精英 150

8.5稳态与代际算法 . 152

6目录

8.6种群多样性 153

8.6.1重复个体 154

8.6.2基于小生境和基于物种的重组 154

8.6.3小生境 156

8.7选择方案 . 160

8.7.1随机遍历采样 160

8.7.2超比例选择 . 162

8.7.3 Sigma缩放 . 162

8.7.4基于排名选择 164

8.7.5线性排名 164

8.7.6锦标赛选择 . 166

8.7.7种马进化算法 167

8.8重组 168

8.8.1单点交叉 (二进制或连续进化算法) 169

8.8.2多点交叉 (二进制或连续进化算法) 169

8.8.3分段交叉 (二进制或连续进化算法) 169

8.8.4均匀交叉 (二进制或连续进化算法) 170

8.8.5多父代交叉 (二进制或连续进化算法) . 170

8.8.6全局均匀交叉 (二进制或连续进化算法) 171

8.8.7洗牌交叉 (二进制或连续进化算法) 171

8.8.8平交叉和算术交叉 (连续进化算法) 171

8.8.9混合交叉 (连续进化算法) 172

8.8.10线性交叉 (连续进化算法) 172

8.8.11模拟二进制交叉 (连续进化算法) 172

8.8.12小结 . 173

8.9变异 173

8.9.1以 xi(k)为中心的均匀变异 173

8.9.2以搜索域的中央为中心的均匀变异 174

8.9.3以 xi(k)为中心的高斯变异 174

8.9.4以搜索域的中央为中心的高斯变异 174

8.10总结 174

习题 . 175

第三篇较新的进化算法 179

第 9章模拟退火 181

9.1自然退火 . 181

9.2简单的模拟退火算法 183

目录 7

9.3冷却调度 . 184

9.3.1线性冷却 184

9.3.2指数冷却 185

9.3.3逆冷却 185

9.3.4对数冷却 187

9.3.5逆线性冷却 . 188

9.3.6依赖于维数的冷却 . 190

9.4实施的问题 192

9.4.1候选解的生成 192

9.4.2重新初始化 . 193

9.4.3记录最好的候选解 . 193

9.5总结 193

习题 . 194

第 10章蚁群优化 196

10.1信息素模型 198

10.2蚂蚁系统 . 200

10.3连续优化 . 204

10.4其他蚂蚁系统 . 207

10.4.1最大最小蚂蚁系统 207

10.4.2蚁群系统 . 208

10.4.3更多的蚂蚁系统 . 211

10.5理论结果 . 212

10.6总结 212

习题 . 213

第 11章粒子群优化 215

11.1基本粒子群优化算法 . 216

11.2速度限制 . 219

11.3惯性权重与压缩系数 . 220

11.3.1惯性权重 . 220

11.3.2压缩系数 . 222

11.3.3粒子群优化的稳定性 . 223

11.4全局速度更新 . 226

11.5完全知情的粒子群 229

11.6从错误中学习 . 231

11.7总结 234

习题 . 234

8目录

第 12章差分进化 237

12.1基本差分进化算法 237

12.2差分进化的变种 . 239

12.2.1试验向量 . 240

12.2.2变异向量 . 242

12.2.3比例因子的调整 . 245

12.3离散优化 . 246

12.3.1混合整数差分进化 247

12.3.2离散差分进化 . 248

12.4差分进化与遗传算法 . 248

12.5总结 250

习题 . 250

第 13章分布估计算法 . 252

13.1分布估计算法:基本概念 . 253

13.1.1简单的分布估计算法 . 253

13.1.2统计量的计算 . 253

13.2一阶分布估计算法 254

13.2.1一元边缘分布算法 254

13.2.2紧致遗传算法 . 256

13.2.3基于种群的增量学习 . 259

13.3二阶分布估计算法 261

13.3.1输入聚类互信息最大化 . 261

13.3.2优化与互信息树结合 . 266

13.3.3二元边缘分布算法 271

13.4多元分布估计算法 273

13.4.1扩展紧致遗传算法 273

13.4.2其他多元分布估计算法 . 276

13.5连续分布估计算法 276

13.5.1连续一元边缘分布算法 . 277

13.5.2基于增量学习的连续种群 278

13.6总结 281

习题 . 282

第 14章基于生物地理学的优化 284

14.1生物地理学 285

14.2生物地理学是一个优化过程 . 288

14.3基于生物地理学优化 . 290

14.4 BBO的扩展 293

14.4.1迁移曲线 . 293

目录 9

14.4.2混合迁移 . 294

14.4.3 BBO的其他方法 296

14.4.4 BBO与遗传算法 298

14.5总结 299

习题 . 302

第 15章文化算法 304

15.1合作与竞争 305

15.2文化算法中的信仰空间 . 307

15.3文化进化规划 . 309

15.4自适应文化模型 . 311

15.5总结 316

习题 . 317

第 16章反向学习 318

16.1反向的定义和概念 318

16.1.1反射反向和模反向 319

16.1.2部分反向 . 320

16.1.3 1型反向和 2型反向 . 321

16.1.4准反向和超反向 . 321

16.2反向进化算法 . 322

16.3反向概率 . 326

16.4跳变比 . 329

16.5反向组合优化 . 331

16.6对偶学习 . 333

16.7总结 334

习题 . 335

第 17章其他进化算法 . 337

17.1禁忌搜索 . 337

17.2人工鱼群算法 . 338

17.2.1随机行为 . 339

17.2.2追逐行为 . 340

17.2.3聚集行为 . 340

17.2.4搜索行为 . 340

17.2.5跳跃行为 . 340

17.2.6人工鱼群算法概要 341

17.3群搜索优化器 . 342

17.4混合蛙跳算法 . 344

10目录

17.5萤火虫算法 346

17.6细菌觅食优化 . 347

17.7人工蜂群算法 . 350

17.8引力搜索算法 . 352

17.9和声搜索 . 353

17.10基于教学的优化 355

17.11总结 358

习题 . 359

第四篇优化问题的特殊类型 361

第 18章组合优化 363

18.1旅行商问题 364

18.2旅行商问题的初始化 . 365

18.2.1最近邻初始化 . 365

18.2.2最短边初始化 . 367

18.2.3嵌入初始化 367

18.2.4随机初始化 369

18.3旅行商问题的表示与交叉 369

18.3.1路径表示 . 369

18.3.2邻接表示 . 372

18.3.3顺序表示 . 375

18.3.4矩阵表示 . 376

18.4旅行商问题的变异 379

18.4.1反转 379

18.4.2嵌入 379

18.4.3移位 379

18.4.4互换 380

18.5旅行商问题的进化算法 . 380

18.6图着色问题 384

18.7总结 387

习题 . 387

第 19章约束优化 389

19.1罚函数法 . 390

19.1.1内点法 . 390

19.1.2外点法 . 391

19.2处理约束的常用方法 . 393

19.2.1静态惩罚方法 . 393

目录 11

19.2.2可行点优势 393

19.2.3折中进化算法 . 394

19.2.4协同进化惩罚 . 395

19.2.5动态惩罚方法 . 396

19.2.6自适应惩罚方法 . 397

19.2.7分离遗传算法 . 398

19.2.8自身自适应的适应度描述 398

19.2.9自身自适应罚函数 399

19.2.10自适应分离约束处理 . 400

19.2.11行为记忆 401

19.2.12随机排名 402

19.2.13小生境惩罚方法 403

19.3特殊表示与特殊算子 . 403

19.3.1特殊表示 . 404

19.3.2特殊算子 . 405

19.3.3 Genocop 406

19.3.4 Genocop II . 407

19.3.5 Genocop III . 407

19.4约束优化的其他方法 . 409

19.4.1文化算法 . 409

19.4.2多目标优化 409

19.5候选解的排名 . 410

19.5.1最大违反约束排名 410

19.5.2约束次序排名 . 410

19.5.3 ←-水平比较 . 411

19.6处理约束方法的比较 . 412

19.7总结 414

习题 . 416

第 20章多目标优化 418

20.1帕雷托最优性 . 419

20.2多目标优化的目标 423

20.2.1超体积 . 424

20.2.2相对覆盖度 427

20.3基于非帕雷托的进化算法 427

20.3.1集结方法 . 427

20.3.2向量评价遗传算法 429

20.3.3字典排序 . 430

12目录

20.3.4 ←-约束方法 431

20.3.5基于性别的方法 . 431

20.4基于帕雷托进化算法 . 432

20.4.1多目标进化优化器 433

20.4.2基于 ←的多目标进化算法 434

20.4.3非支配排序遗传算法 . 436

20.4.4多目标遗传算法 . 438

20.4.5小生境帕雷托遗传算法 . 439

20.4.6优势帕雷托进化算法 . 440

20.4.7帕雷托归档进化策略 . 445

20.5基于生物地理学的多目标优化 . 446

20.5.1向量评价 BBO 446

20.5.2非支配排序 BBO. 447

20.5.3小生境帕雷托 BBO . 448

20.5.4优势帕雷托 BBO. 449

20.5.5多目标 BBO的仿真 . 450

20.6总结 451

习题 . 452

第 21章昂贵、有噪声与动态适应度函数 . 455

21.1昂贵适应度函数 . 456

21.1.1适应度函数的近似 457

21.1.2近似变换函数 . 465

21.1.3在进化算法中如何使用适应度近似 . 466

21.1.4多重模型 . 468

21.1.5过拟合 . 470

21.1.6近似方法的评价 . 471

21.2动态适应度函数 . 472

21.2.1预测进化算法 . 474

21.2.2迁入方案 . 475

21.2.3基于记忆的方法 . 478

21.2.4动态优化性能的评价 . 479

21.3有噪声适应度函数 479

21.3.1再采样 . 480

21.3.2适应度估计 482

21.3.3卡尔曼进化算法 . 483

21.4总结 485

习题 . 486

目录 13

第五篇附录 .489

附录 A一些实际的建议 491

A.1查错 . 491

A.2进化算法是随机的 . 491

A.3小变化可能会有大影响 492

A.4大变化可能只有小影响 492

A.5种群含有很多信息 . 492

A.6鼓励多样性 . 492

A.7利用问题的信息 493

A.8经常保存结果 493

A.9理解统计显著性 493

A.10善于写作 . 493

A.11强调理论 . 494

A.12强调实践 . 494

附录 B没有免费午餐定理与性能测试 495

B.1没有免费午餐定理 . 495

B.2性能测试 500

B.2.1基于仿真结果的大话 . 500

B.2.2如何报告 (不报告)仿真结果 . 502

B.2.3随机数 . 506

B.2.4 t检验 . 508

B.2.5 F检验 . 512

B.3总结 . 515

附录 C基准优化函数 . 516

C.1无约束基准 . 516

C.1.1 Sphere函数 . 517

C.1.2 Ackley函数 . 517

C.1.3 Ackley测试函数 518

C.1.4 Rosenbrock函数 518

C.1.5 Fletcher函数 . 519

C.1.6 Griewank函数 . 520

C.1.7 Penalty#1函数 . 521

C.1.8 Penalty#2函数 . 521

C.1.9 Quartic函数 522

C.1.10 Tenth Power函数 . 523

C.1.11 Rastrigin函数 524

14目录

C.1.12 Schwefel二重和函数 . 524

C.1.13 Schwefel最大函数 525

C.1.14 Schwefel绝对值函数 . 526

C.1.15 Schwefel正弦函数 526

C.1.16 Step函数 . 527

C.1.17 Absolute函数 528

C.1.18 Shekel's Foxhole函数 . 528

C.1.19 Michalewicz函数 . 529

C.1.20 Sine Envelope函数 . 530

C.1.21 Eggholder函数 530

C.1.22 Weierstrass函数 . 531

C.2约束基准 531

C.2.1 C01函数 . 532

C.2.2 C02函数 . 532

C.2.3 C03函数 . 533

C.2.4 C04函数 . 533

C.2.5 C05函数 . 533

C.2.6 C06函数 . 534

C.2.7 C07函数 . 534

C.2.8 C08函数 . 534

C.2.9 C09函数 . 535

C.2.10 C10函数 . 535

C.2.11 C11函数 . 535

C.2.12 C12函数 . 535

C.2.13 C13函数 . 536

C.2.14 C14函数 . 536

C.2.15 C15函数 . 537

C.2.16 C16函数 . 537

C.2.17 C17函数 . 537

C.2.18 C18函数 . 538

C.2.19约束基准的总结 538

C.3多目标基准 . 539

C.3.1无约束多目标优化问题 1 539

C.3.2无约束多目标优化问题 2 540

C.3.3无约束多目标优化问题 3 541

C.3.4无约束多目标优化问题 4 541

C.3.5无约束多目标优化问题 5 542

C.3.6无约束多目标优化问题 6 542

C.3.7无约束多目标优化问题 7 543

目录 15

C.3.8无约束多目标优化问题 8 544

C.3.9无约束多目标优化问题 9 544

C.3.10无约束多目标优化问题 10 545

C.4动态基准 545

C.4.1动态基准的完整描述 . 546

C.4.2简化的动态基准描述 . 550

C.5噪声基准 551

C.6旅行商问题 . 551

C.7无偏化搜索空间 553

C.7.1偏差 553

C.7.2旋转矩阵 . 555

参考文献 557

索引 . 601

致谢

进化算法是一个令人着迷的研究领域 ,我涉足其间已有 20年,感谢多年来为我的研究提供资助的每一位人士 : TRW系统集成组的 Hossny El-Sherief, TRW汽车安全系统的 Dorin Dragotoniu, NASA Glenn控制和动力学部门的 Sanjay Garg和 Donald Simon,福特汽车公司的 Dimitar Filev,克利夫兰医学中心的 Brian Davis和 William Smith,国家科学基金和克利夫兰州立大学 .还要感谢和我一起工作 ,在进化算法领域发表论文的学生和同事： Je. Abell, Dawei Du, Mehmet Ergezer, Brent Gardner, Boris Igelnik,Paul Lozovyy, Haiping Ma, Berney Montavon, Mirela Ovreiu,Rick Rarick, Hanz Richter, David Sadey, Sergey Samorezov, Nina Scheidegger, Arpit Shah, Steve Szatmary, George Thomas, Oliver Tiber, Tonvanden Bogert, Arun Venkatesan和 Tim Wilmot.最后 ,我想感谢阅读这些材料的初稿并给我许多有用建议的人士： EmileAarts, Dan Ashlock, Forrest Bennett, Hans-Georg Beyer, Maurice Clerc, Carlos Coello Coello, Kalyanmoy Deb, Gusz Eiben, Jin-KaoHao, Yaochu Jin, Pedro Larranaga, Mahamed Omran, KennethV. Price, Hans-PaulSchwefel, Thomas St¨utzle, Hamid Tizhoosh, Darrell Whitley.还要感谢评审本书最初的出版计划的三位匿名评阅人 .这些评阅人不一定赞同这本书,但他们的建议和评论帮助我提升本书的品质.

丹·西蒙 (Dan Simon)

缩写

ABC 人工蜂群

ACM 自适应文化模型

ACO 蚁群优化

ACS 蚁群系统

ADF 自动定义的函数

AFSA 人工鱼群算法

AS 蚂蚁系统

ASCHEA 自适应分离约束处理进化算法

BBO 基于生物地理学的优化

BFOA 细菌觅食优化算法

BMDA 二元边缘分布算法

BOA 贝叶斯优化算法

CA 文化算法

CAEP 受文化算法影响的进化规划

CEC 进化计算大会

cGA 紧致遗传算法

CMA-ES 协方差阵自适应进化策略

CMSA-ES 协方差阵自身自适应进化策略

COMIT 优化与互信息树结合

CX 循环交叉

DACE 计算机实验的设计与分析

DAFHEA 基于动态近似适应度的混合进化算法

DE 差分进化

DEMO 多样性多目标进化优化器

←-MOEA 基于 ←的多目标进化算法

EA 进化算法

EBNA 贝叶斯网络估计算法

ECGA 扩展紧致遗传算法

20 缩写

EDA 分布估计算法

EGNA 高斯网络估计算法

EMNA 多元正态估计算法

EP 进化规划

ES 进化策略

FDA 因子化分布算法

FIPS 完全知情的粒子群

FSM 有限状态机

GA 遗传算法

GP 进化规划

GSA 引力搜索算法

GSO 群搜索优化器

hBOA 分层贝叶斯优化算法

HCwL 学习爬山法

HLGA Hajela-Lin遗传算法

HS 和声搜索

HSI 生境适宜度指数

IDEA 迭代密度估计算法

IDEA 不可行性驱动的进化算法

IUMDA 增量一元边缘分布算法

MMAS 最大最小蚂蚁系统

MMES 多元进化策略

MIMIC 输入聚类的互信息最大化

MOBBO 基于生物地理学的多目标优化

MOEA 多目标进化算法

MOGA 多目标遗传算法

MOP 多目标优化问题

MPM 边缘积模型

N(μ, σ2) 均值为 μ方差为 σ2的正态分布

N(μ, Σ) 均值为 μ协方差为 Σ的多元正态分布

NFL 没有免费午餐

NPBBO 小生境帕雷托基于生物地理学优化

NPGA 小生境帕雷托遗传算法

NPSO 负强化的粒子群优化

NSBBO 非支配排序基于生物地理学优化

NSGA 非支配排序遗传算法

缩写 21

OBBO 反向的基于生物地理学优化

OBL 反向学习

OBX 基于顺序交叉

OX 顺序交叉

PAES 帕雷托归档进化策略

PBIL 基于种群的增量学习

PDF 概率密度函数

PID 比例积分微分

PMBGA 概率建模遗传算法

PMX 部分匹配交叉

PSO 粒子群优化

RMS 均方根

RV 随机变量

SA 模拟退火

SBX 模拟二进制交叉

SAPF 自身自适应罚函数

SCE 混合复杂进化

SEMO 简单多目标进化优化器

SFLA 混合蛙跳算法

SGA 随机梯度上升

SHCLVND 由正态分布向量学习的随机爬山法

SIV 适应度指数变量

SPBBO 优势帕雷托基于生物地理学优化

SPEA 优势帕雷托进化算法

TLBO 基于教学的优化

TS 禁忌搜索

TSP 旅行商问题

U[a, b] 在域 [a, b]上均匀分布的概率密度函数.可为连续的也可为离散的,

根据上下文确定

UMDA 一元边缘分布算法

UMDAG c 连续高斯一元边缘分布算法

VEBBO 向量评价基于生物地理学优化

VEGA 向量评价遗传算法