本书介绍了一种实现简单、易于使用、可靠快速的全局优化算法——差分进化算法。主要内容有:差分进化算法的研究动机、主要内容、标准测试、问题域、架构和计算环境、编程以及各种应用。 本书可作为相关专业的教材使用,同时也适合对优化问题感兴趣的所有读者。
Kenneth VPrice:献给我的父亲。 Rainer MStorn :献给曾给我支持的父母、我深爱的妻子Marion、我可爱的孩子Maja和Robin.Jouni ALampinen:献给曾与我在乡村和城镇一起愉快生活的、也是我非常要好的朋友——小狗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的技术报告TR95012中发表了早期的研究结果:“差分进化:一种用于求解连续空间中全局优化的简单、有效的自适应模式”(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章“差分进化的研究动机”,以一个常见的优化问题开始,通过对传统方法优劣的讨论进而引出DE算法。对经典的优化可微函数的方法及类似HookeJeeves和NelderMead等传统直接搜索方法进行了讨论。第1章总结了一些较为先进的优化技术,比如模拟退火和进化算法。 第2章“差分进化算法”介绍了DE算法,先概述然后详细讲解。 第3章“差分进化的标准测试”,对比DE与其他EA算法的性能,包括不同版本的DE算法。 第4章“问题领域”,将基本算法扩展到各种优化场景中,包括受约束的、混合变量和多目标优化,以及设计中心问题,因为现实世界中许多问题涉及这些领域,所以这些扩展具有十分重要的意义。 第5章“架构和计算环境”,就如何在并行和串行机器上实现DE给出明确的建议。此外第5章还提出了辅助计算的相关算法。 第6章“计算机编码”提供了在本书附带的光盘中的软件使用说明。 第7章“应用”列举了搜集的12个在不同学科中专家提供的DE的应用。应用涉及用X射线分析进行结构测定、地震再定位、多传感器融合、数字滤波器设计以及一些其他非常复杂的优化问题。附录部分包含本书中所使用的测试函数的描述。 Storn博士要感谢西门子公司,特别是H. Schwartzel教授, YeungCho Yp博士和Jean Schweitzer博士对于DE研究的支持。此外, Lampinen教授还要感谢他所在的DE研究小组的成员,Jani Rnkknen, Junhong Liu和Saku Kukkonen,感谢他们对本书的帮助。作者尤其要感谢第7章中应用DE的研究者们。包括: J.P. Armspach, Institut de Physique Biologique, Université Louis Pasteur,Strasbourg, UMR CNRSULP 7004, Faculté de Médecine, F67085,Strasbourg Cedex, France ; (Sect. 76)Keith D. Bowen, Bede Scientific Incorporated,14 Inverness Drive East,Suite H100, Englewood, CO, USA; (Sect. 710)Nirupam Chakraborti, Department of Metallurgical and Materials Engineering,Indian Institute of Technology, Kharagpur (WB) 721 302,India; (Sect. 71)David Corcoran, Department of Physics,University of Limerick, Ireland;(Sect. 72)Robert W. Derksen, Department of Mechanical and Industrial Engineering University of Manitoba, Canada; (Sect. 73)Drago Dolinar, University of Maribor, Faculty of Electrical Engineering and Computer Science, Smetanova 17, 2000 Maribor, Slovenia; (Sect.79)Steven Doyle, Department of Physics,University of Limerick, Ireland;(Sect. 72)Kay Hameyer, Katholieke Universiteit Leuven, Department E.E. (ESAT),Division ELEN, Kaardinal Mercierlaan 94, B3001 Leuven, Belgium;(Sect. 79)Evan P. Hancox, Department of Mechanical and Industrial Engineering,University of Manitoba, Canada; (Sect. 73)Fabrice Heitz, LSIITMIV, Université Louis Pasteur,Strasbourg, UMR CNRSULP 7005, Poe API, Boulevard Sébastien Brant, F67400 Illkirch,France ; (Sect. 7 6)Rajive Joshi, RealTime Innovations Inc.,155A Moffett Park Dr, Sunnyvale,CA 94089, USA; (Sect. 74)Michal Kvasnika , ERA a.s, Poděbradská 186/56, 180 66 Prague 9, Czech Republic; (Sect. 75)Kevin M. Matney, Bede Scientific Incorporated,14 Inverness Drive East,Suite H100, Englewood, CO, USA; (Sect. 710)Lars Nolle, School of Computing and Mathematics, The Nottingham TrentUniversity, Burton Street, Nottingham, NG1 4BU, UK; (Sect. 712)GuyRené Perrin, LSIITICPS, Université Louis Pasteur,Strasbourg,UMR CNRS CNRSULP 7005, Pole API, Boulevard Sébastien Brant, F67400 Illkirch, France ; (Sect. 7 6)Bohuslav Ru。ek, Geophysical Institute, Academy of Sciences of the Czech Republic, Bo ní II/1401, 141 31 Prague 4, Czech Republic; (Sect.75)Michel Salomon, LSIITICPS, Université Louis Pasteur,Strasbourg, UMR CNRS-ULP 7005, Pole API, Boulevard Sébastien Brant, F-67400 Illkirch,France ; (Sect. 7 6)Arthur C. Sanderson, Rensselaer Polytechnic Institute,110 8th St, Troy,NY 12180, USA; (Sect. 74)Amin Shokrollahi, Laboratoire d’algorithmique Laboratoire de mathématiques algorithmiques, EPFL, I&C-SB, Building PSE-A, 1015Lausanne, Switzerland; (Sect. 77)Rainer M. Storn, Rohde & Schwarz GmbH & Co. KG, Mühldorfstr. 15,81671 München, Germany; (Sects.77 and 78)Gorazd tumberger, University of Maribor, Faculty of Electrical Engineering and Computer Science, Smetanova 17, 2000 Maribor, Slovenia; (Sect. 79)Matthew Wormington, Bede Scientific Incorporated,14 Inverness Drive East, Suite H-100, Englewood, CO, USA; (Sect. 710)Ivan Zelinka, Institute of Information Technologies, Faculty of Technology,Tomas Bata University, Mostni 5139, Zlin, Czech Republic;(Sects. 711 and 712)我们还要感谢为DE成为公开源代码做出贡献的每一个人。尤其要感谢Eric Brasseur向公众提供的头文件plot.h,Makoto Matsumoto和Takuji Nishimura让随机数生成器Mersenne Twister能够免费使用,Lester E. Godwin 编写的C++版本的DE,Feng-Sheng Wang提供的FORTRAN 90版本的DE,Walter Di Carlo将DE移植到Scilab,Jim Van Zandt 和 Arnold Neumaier对MATLAB版本DE的帮助,以及Ivan Zelinka和Daniel Lichtblau提供的Mathematica版本的DE。 对David Corne的不懈支持表示特别感谢,同样要感谢A. E. Eiben以及施普林格出版社的编辑人员,感谢他们对DE的兴趣。此外,我们还要感谢Ingeborg Meyer,因为他的耐心和专业精神使得我们的书得以出版。我们还要感谢Neville Hankins,感谢他细致详细的书稿编辑工作。感谢施普林格出版社的Neville Hankins和Ulrike Stricker帮助我们解决了在这份书稿撰写过程中遇到的各种技术问题。 此外,如果没有许多工程师与科学家的帮助,本书是不可能完成的,DE也不会如此广泛传播。即便他们多得不胜枚举,我们仍要向他们致敬。 最后若没有三位作者家人的理解与支持,本书也无法完成,因此我们要特别感谢他们,感谢他们的宽容与牺牲。 肯尼思V普莱斯(Kenneth V.Price)赖纳M斯托恩(Rainer M.Storn)约尼A兰皮宁(Jouni A.Lampinen )
随手扫一扫~了解多多