应用数学译丛进化优化算法:基于仿生和种群的计算机智能方法

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