致谢 .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 向量评价遗传算法
