进化优化算法：基于仿生和种群的计算机智能方法

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