差分进化算法

本书介绍了一种实现简单、易于使用、可靠快速的全局优化算法——差分进化算法。主要内容有：差分进化算法的研究动机、主要内容、标准测试、问题域、架构和计算环境、编程以及各种应用。    本书可作为相关专业的教材使用，同时也适合对优化问题感兴趣的所有读者。

肯尼斯·V.普莱斯（Kenneth V.Price） ，1974年于美国伦斯勒理工学院获得物理学学士学位。在迁往旧金山之前，他主要在纽约Teledyne-Gurley Scientific Instrument公司担任主管。现在他居住在加州瓦卡维尔市。1994年，他发表了“遗传退火”算法，并指导Rainer Storn博士攻切比雪夫多项式拟合问题。他提出的“差分变异”被证明是解决切比雪夫问题和其他难题的核心。
赖纳· M.斯托恩（Rainer M.Storn），博士是差分进化算法的发明人之一。目前是IEEE不错会员，罗德施瓦兹公司平台软件研发部总监。曾先后担任西门子公司城市网络研发小组组长、伯利靠前计算机科学研究所博士后、英飞凌公司ADSL项目总监、罗德施瓦兹公司SDR项目总监。因差分进化算法的贡献，Kenneth v.Price和Rainer Storn被授予IEEE计算智能学会“先驱奖”。
约尼·A.兰皮宁（Jouni A.Lampinen），是芬兰瓦萨大学计算机科学学院教授，是差分进化算法的早期重要贡献者。

前言
第1章差分进化的研究动机
1.1参数优化引论
1.1.1引言
1.1.2单点求导型优化
1.1.3单点非求导型的优化及步长问题
1.2局部优化与全局优化对比
1.2.1模拟退火
1.2.2多点求导型方法
1.2.3多点非求导型方法
1.2.4差分进化的第一印象
参考文献
第2章差分进化算法
2.1引言
2.1.1种群结构
2.1.2初始化
2.1.3变异
2.1.4交叉
2.1.5选择
2.1.6初识差分进化算法
2.1.7可视化DE
2.1.8注释
2.2参数表示
2.2.1二进制比特串
2.2.2浮点数
2.2.3浮点约束
2.3初始化
2.3.1初始化边界
2.3.2初始化分布
2.4基向量选择
2.4.1选择基向量索引（r0）
2.4.2一对一基向量选择
2.4.3几种随机基索引选择方法的比较
2.4.4退化向量组合
2.4.5索引值互异
2.4.6测试退化组合的影响：球面函数
2.4.7偏基向量选择方案
2.5差分变异
2.5.1变异缩放因子
2.5.2随机化缩放因子
2.6重组
2.6.1交叉
2.6.2Cr在优化中的作用
2.6.3算术重组
2.6.4相图
2.6.5异或算法
2.7选择
2.7.1生存准则
2.7.2锦标赛选择
2.7.3一对一生存（者）准则
2.7.4局部选择和全局选择的比较
2.7.5置换选择的不变性
2.7.6依赖交叉的选择压力
2.7.7并行性能
2.7.8延伸
2.8终止条件
2.8.1达到目标
2.8.2限制代数
2.8.3统计种群
2.8.4限制时间
2.8.5人工监测
2.8.6特定应用
参考文献
第3章差分进化的标准测试
3.1关于测试
3.2性能评估
3.3几种DE的比较
3.3.1算法
3.3.2测试集
3.3.3相图
3.3.4小结
3.4DE与其他优化算法的比较
3.4.1可比的性能：针对30维函数
3.4.2比较研究：非约束优化
3.4.3其他问题域上的性能比较
3.4.4基于应用的性能比较
3.5总结
参考文献
第4章问题领域
4.1引言
4.2函数及参数量化
4.2.1均匀量化
4.2.2非均匀量化
4.2.3目标函数量化
4.2.4参数量化
4.2.5混合变量
4.3约束优化
4.3.1边界约束
4.3.2不等式约束
4.3.3等式约束
4.4组合问题
4.4.1旅行商问题
4.4.2置换矩阵方法
4.4.3相对位置索引
4.4.4Onwubolu方法
4.4.5邻接矩阵方法
4.4.6总结
4.5设计中心问题
4.5.1发散、自导向性和池化
4.5.2设计中心的计算
4.6多目标优化
4.6.1目标函数加权和
4.6.2Pareto优化
4.6.3Pareto前沿的两个例子
4.6.4优化多目标的适应性DE
4.7动态目标函数
4.7.1稳定优化
4.7.2不稳定优化
参考文献
第5章架构和计算环境
5.1基于多处理器的差分进化算法
5.1.1背景
5.1.2相关工作
5.1.3标准模型的缺点
5.1.4改进的标准模型
5.1.5主处理器
5.2基于资源有限设备的差分进化算法
5.2.1随机数
5.2.2排列数生成器
5.2.3高效的排序
5.2.4内存节省型的差分进化算法
参考文献
第6章计算机编码
6.1差分进化的MATLAB实现——DeMat
6.1.1DeMat的总体结构
6.1.2命名和代码约定
6.1.3数据流程图
6.1.4怎样使用图形
6.2DeWin——Windows下使用C语言的DE
6.2.1DeWin总体的结构
6.2.2命名和代码规范
6.2.3数据流程图
6.2.4怎样使用图形
6.2.5graphics.h的功能
6.3随书光盘上的软件
参考文献
第7章应用
7.1遗传算法和相关技术优化Si—H簇：差分进化的优点分析
7.1.1引言
7.1.2系统模型
7.1.3计算细节
7.1.4结果和讨论
7.1.5总结
参考文献
7.2差分进化在非成像光学设计中的应用
7.2.1引言
7.2.2目标函数
7.2.3逆向工程方法检验
7.2.4更难的问题：扩展源
7.2.5总结
参考文献
7.3工业压缩机供应系统的优化
7.3.1引言
7.3.2测试问题的背景信息
7.3.3系统优化
7.3.4需求概况
7.3.5改进的差分进化及扩展DE的通性
7.3.6数据库中的组件选择
7.3.7交叉方法
7.3.8测试步骤
7.3.9获取100%的确定结果
7.3.10结果
7.3.11总结
参考文献
……
附录

Kenneth VPrice:献给我的父亲。    Rainer MStorn :献给曾给我支持的父母、我深爱的妻子Marion、我可爱的孩子Maja和Robin.Jouni ALampinen:献给曾与我在乡村和城镇一起愉快生活的、也是我非常要好的朋友——小狗Tonique.前言优化问题广泛存在于科学研究和工程领域中。什么形状的机翼能够提供最大的升力？何种多项式最能拟合给定数据？哪种配置的聚焦透镜组合能够生成最锐利的图像？这些问题是研究人员在工作中经常会碰到的基本问题，毫无疑问，他们需要一种鲁棒性的优化算法去解决这些问题。    一般来说，解决一个难度大的“优化问题”，其问题本身不应很难，如，一个拥有丰富机械理论知识的结构工程师可能不需要具备同样程度的优化知识去修改他的设计。除了易于使用之外，一个全局优化算法应能足够有效地收敛到真实最优解。此外，搜寻解的计算时间不应过长。因此，一个真正有效的全局优化算法应该实现简单、易于使用、可靠快速。    差分进化算法(Differential Evolution，以下简称DE)正是这种方法。自1995年发表以来，DE被誉为一种非常高效的全局优化器。但DE并非万能，它良好的可靠性及鲁棒性需要每个科学家及工程师的智慧。    DE源于遗传退火算法(Genetic Annealing Algorithm)，由Kenneth Price提出并发表在Dr.Dobb′s Journal (DDJ) 1994年10月刊上，这是一本很流行的程序员杂志。遗传退火算法是一种基于种群的组合优化算法，实现了经由阈值的退火准则。遗传退火算法在DDJ上出现后，Ken与Rainer Storn博士(来自西门子当时在加州伯克利大学的国际计算机科学研究所，现就职于德国慕尼黑的R&S公司（Rohde & Schwarz GmbH）一起应用遗传退火算法解决了切比雪夫多项式拟合问题（Chebyshev polynomial fitting problem）。而很多人认为用一种通用的优化算法确定切比雪夫多项式的系数是一项非常困难的任务。    Ken最终用遗传退火算法解决了五维切比雪夫问题，但收敛过程很慢且有效的控制参数很难确定。在此之后，Ken改进了遗传退火算法，使用浮点数替换位串编码并用算术运算替换逻辑运算，然后他发现了DE的基础差分变异操作。综合起来，这些有效的改进形成了一种数值优化的组合算法，即首次迭代DE。为了更好地适应并行计算机体系，Rainer提出创建单独的父代种群和子代种群。不同于遗传退火算法，DE在处理33维切比雪夫多项式多项式系数问题时并不困难。    DE的有效性并不只在切比雪夫多项式中得到了证明，在许多其他函数测试中也有不俗的表现。1995年，Rainer和Ken在ICSI的技术报告TR95012中发表了早期的研究结果：“差分进化：一种用于求解连续空间中全局优化的简单、有效的自适应模式”（Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces）。基于差分进化算法的成功表现，Rainer和Ken参加了1996年5月在日本名古屋市同时举办的首届国际进化算法大赛（ICEO）和IEEE国际进化计算会议。DE算法取得了第三名的佳绩，虽然前两名的算法在竞赛函数测试中得分很高，但这两种算法不够灵活，不能定义为通用的优化算法。排名第一位的算法只适用于可分量的竞赛函数，而排名第二的算法因要计算拉丁方而无法处理大量参数。受此鼓舞，Rainer与Ken于1997年4月在DDJ上又发表了一篇名为Different Evolution—A Simple Evolution Strategy for Fast Optimization的文章，文章深受好评，并将DE介绍给全世界的读者。    前言前言许多研究者阅读了Rainer与Ken在1997年12月发表在The Journal of Global Optimization杂志上的文章Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces， 文章给出了大量DE在各种测试函数中鲁棒性的实验性证据。大约在同一时期，Rainer建立了一个DE的网站(http://www.icsi.berkeley.edu/~storn/code/html)，该网站有DE的详细代码、DE的应用及改进。    Ken参加了于1997年4月在美国印第安纳州的印第安纳波利斯举办的第二届国际进化算法大赛（ICEO），由于种种原因导致竞赛结果未公开，但DE表现优秀。在本次会议中，Ken遇见了David博士，随后邀请他撰写了DE的概要介绍，名为New Ideas in Optimization(1999)。从此以后，Ken专注于精炼DE算法，并进行理论研究来解释算法性能。Rainer致力于在有限资源设备上实现DE，并开发了多种编程语言的软件应用程序。此外Rainer还将DE作为高效工具应用在滤波器设计、中心设计和组合优化问题中。    芬兰的Jouni Lampinen教授(拉彭兰塔理工大学，芬兰，拉彭兰塔)于1998年开始研究DE。除了对DE的理论有所贡献外，他还证明了DE在机械工程应用中的成效，Jouni也针对特别需求的约束多目标优化问题设计了简单高效的DE自适应算法。Jouni还建立了DE的文献目录网站(http://www.lut.fi/~jlampine/debiblio.html)。    就像DE算法一样，本书的目的是使读者对DE便于理解和应用。本书主要讲解了DE的工作原理，及适合于在哪些场合使用。第1章“差分进化的研究动机”，以一个常见的优化问题开始，通过对传统方法优劣的讨论