译 者 序

在国际上的计算智能领域内，本书是最新介绍计算群体智能的导论性质的教学与参考书籍之一。本书中从优化计算的角度系统全面地介绍了群体智能中的两个典型范例，即粒子群优化方法和蚁群优化算法，本书不仅介绍了它们的起源、基本模型、模型的收敛行为、基本模型的重要变体，而且还介绍了大量的典型实际问题及其实现。从本书中我们可以全面地了解到目前计算群体智能研究的主要成果，对相关专业的广大教师、研究生和科研工程人员都具有很高的参考价值，故我们决定将本书从英文版翻译成中文出版，希望本书中文版的出版能够吸引我国更多的研究人员认识和使用计算群体智能方法，并进而推动我国科研人员在计算群体智能领域的广泛深入研究。

受对生物体的群体行为研究的启发，我们已经发明了许多群体计算模型。在这些模型中，尽管群体中每个个体都非常简单，但是这些简单个体组成的一个群体却表现出了十分复杂的涌现行为，这些行为已被广大的研究人员成功建模并用于求解大量的复杂实际问题。计算群体智能正是研究这种基于群体行为模型的计算建模和实现的方法。经过近十几年的研究，计算群体智能已经逐渐成为现代计算智能领域的主要研究热点，正日益受到更多人的关注和使用。随着大量新的、更高效的群体行为模型的建立，计算群体智能方法将逐渐在更多的实际问题中被广泛应用并发挥出它应有的价值。

本书的特色是从计算机科学的角度探寻社会性网络结构如何在个体间交换信息，以及个体聚集行为如何形成一个功能强大的有机体。这种基于群体的模型正日益成为计算智能领域的研究热点。本书在简要介绍了基本优化理论和各类优化问题后，概要论述了进化计算方法，详细论述了粒子群优化和蚁群优化算法及其重要变体，证明了这些算法解决实际问题的能力。本书另一个特色是强调这种生物激发系统模型的算法实现，在介绍粒子群优化和蚁群优化的基本行为模型的同时提供了它们的大量变体计算模型及其Java代码实现。本书可以使得新进入本领域的读者以最快的速度认识这些基本模型及其计算能力，并能很快利用所学习到的模型来解决实际问题，从而提高他们对本领域的兴趣和继续探索的热情。同时，本书提供的大量研究实例和丰富、完整的参考文献也为本领域的活跃研究者提供了很有价值的参考，必将成为他们日后研究中不可多得的参考手册。

全书分成四大部分共31章。由谭营教授领导的北京大学计算智能实验室（http://www.cil.pku.edu.cn）的部分教师和研究生共同翻译，它是全体实验室（CIL@PKU）科研人员共同努力的结果。参加初稿翻译的人员有谭营、张军棋、刘坤、周游、肖忠民、朱元春、晁睿、尹致诚等。另外参加材料收集、整理、排版和辅助工作的人员有阮光尘、顾岁成、杨健、张鹏涛、王军等。全书的译文由谭营负责统一术语、格式和一致性检查。在翻译的过程中，对发现的原著中的错误进行了相应的更正，对原著叙述不畅的地方进行了适当的补充和润色。最后，由谭营和邓超对全部译稿进行了认真校对并最终定稿。

感谢Engelbrecht教授对翻译该中文版的大力支持和帮助，尤其是他向John Wiley & Sons出版公司极力推荐。感谢清华大学出版社的编辑们，他们积极引进本书并获得John Wiley & Sons出版公司的出版许可权，从而使得本书中文版能够如此之快地与读者见面。

在本书的翻译过程中，我们尽量力求忠实、准确地把握原著，同时保留原著的写作风格。但由于译者们水平有限，译文中难免存在一些错误和不当之处，敬请广大读者批评指正。有关意见和建议请发送到 ytan@pku.edu.cn，我们将视具体情况予以采纳并更正。

希望这本译著有助于推动我国在计算群体智能方面的深入研究和广泛应用。

谭营于北大中关园, 北京计算群体智能基础译者序原著序

原 著 序

通过研究生物有机体的群体行为，我们人类已经学到了很多东西。这些群体的迷人之处在于，尽管组成群体的个体很简单，但是它们表现出了复杂的集体行为。这些系统的模型已经成功地用于求解不同的复杂实际问题。本书将重点介绍受生物系统研究所激发的两个主要模型，即粒子群优化和蚂蚁算法。尽管存在许多其他的群体系统，例如，描述云中颗粒的微粒系统、人群和人群行为的模型，以及更一般的人类社会行为，本书并不考虑上述系统。即使同是在生物群体系统的范畴内，由于篇幅有限，本书也不会讨论大量有趣的其他生物群体系统的研究成果和计算模型，例如细菌、蜘蛛、蜜蜂、鲨鱼等。本书的重点在群体模型的算法模型，故采用术语 “计算群体智能”。本书是从计算机科学和工程的角度来介绍的，因此，社会模型和理论的讨论已经被限定在最低限度内。

本书的最初目标是想为两个领域（粒子群优化和蚂蚁算法）提供一个详细的已研究记录，以便作为最新的参考资料。很快我认识到这一目的是不可实现的，因为在这两个领域已经发表了大量的文献（正如书后的大量文献所示，当然它也不是一个所有相关文献的列表），并且本书的篇幅也是有限的。相应地，通过提供一个详细处理每一个领域的基本算法和对最重要的研究途径和方法的总结，我满足于对全局最优解的近似。还有大量的已经计划好的主题也没能被包含进来，例如群体机器人、蚂蚁的自组装行为、其他生物群体的计算模型，以及其他经验研究方法。然而，我相信即使没有这些内容，本书还是可以为读者提供一个关于计算群体智能的详尽且良好的背景知识。

本书致力于帮助初学者更容易地实现粒子群算法和蚂蚁算法，并进而探索这些算法的能力。为了达到这个目的，本书提供了大量的伪码算法。配套网站（http://si.cs.up.ac.za）提供了一个用Java实现的算法的开源库CIlib。在这里，读者也会发现一个仿真器，它用于设定（用XML）和执行本书介绍算法的仿真。可以从网站上找到关于XML说明规范实例。本书还致力于为当前活跃的研究人员提供目前已有研究工作的一个简要总结。因此，本书和配套网站提供的材料对研究生、从业者、新的研究人员和活跃研究人员都是很有用的。

本书分为四部分。第一部分简要综述优化方法，而第二部分概述了进化计算。本书的主要内容是在第三部分和第四部分，分别介绍了粒子群优化和蚁群优化。读者没有必要顺序地阅读这些部分和各部分中的章节。已了解优化和进化计算知识的读者可以跳过前两部分。关于优化和进化计算部分的有关参考资料（在前两部分已经给出），在第三、四部分也提供了充足的参考文献。第三部分和第四部分是相互独立的，读者可以分别阅读。在每一部分中各章节间的依存关系如下，这里给出了每一部分的概要。

本书从第1章开始，定义了有关群体、群体智能、集体智能、涌现和自组织等概念。

第一部分的目的不是要详细论述优化理论，而只是简要介绍在本书后面部分要用到的一些概念。第2章定义了优化中使用的关键术语和概念，例如，全局最优和局部最优的概念。该章给出了最优化条件以及收敛到局部和全局最优的收敛条件，并给出了这些条件的证明。这些条件和证明在第三部分被用来证明粒子群优化算法的收敛性。该章讨论了优化算法的一些基本要素并对优化问题和优化方法进行了分类。然后，又分别介绍了每类优化方法。对每一种优化方法，该章定义了对应的优化问题，列出了问题实例，并可用于评估优化算法的性能。这些问题列表不仅仅是包含了几个问题，而且应该被看成评估算法的起点，而不是作为一个完整的标准。第3章介绍无约束优化。在该章中讨论的优化算法会被应用到本书的后面各章中，并且还介绍了一般局部搜索、集束搜索、禁忌搜索、模拟退火和交替前进(LeapFrog)算法。第4章概述约束优化，列出了处理约束的不同方法，详细讨论了将约束问题转化为无约束问题的罚方法。第5章对求解多个解的优化问题进行了分类。第6章讨论了多目标优化。该章定义了Pareto优化和Pareto前沿知识。第7章讨论了动态变化问题的优化，并定义和说明了动态问题的类型。

在第一部分中，应该最先阅读第2章，可以任意阅读之后各章。在阅读第16章之前应先阅读第5章。在阅读第18章和第25章之前应先阅读第6章。在阅读第1章之前应先阅读第4章。在阅读第19章和第25章之前，应先阅读第7章。在阅读第14章之前，应先阅读第2章。

第二部分简要总结了进化算法。第8章是对进化计算的引言，并且讨论了进化计算的一般概念，如表示、适应度、选择和繁殖。第9章简要讨论了不同的进化计算方法、包括遗传算法、遗传编程、进化规划、进化策略、差分进化和文化算法。协同进化将在第10章讨论。

第三部分专门论述粒子群优化(PSO)。第11章概述PSO的起源。第1个PSO算法及其基本变体将在第12章详细讨论。讨论的概念包括完整PSO模型、全局最好PSO、局部最好PSO、社会网络结构、速度箝位、惯性权重、收缩系数、不同速度模型、PSO控制参数和性能指标。该章还比较了PSO与进化计算。第13章和第14章总结了粒子和PSO算法的理论研究。第13章讨论和图解了粒子轨迹，并给出了形式化证明以表明一个简化模型可保证收敛到一个稳定点，提供为了保证能收敛到一个稳定状态，选择惯性权重大小和加速度系数值的准则。第14章给出了基本PSO不能保证收敛到局部最小的一个证明，给出了PSO的各种变体，并证明这些变体能收敛到局部极值。第15章总结了大量的PSO算法，它们只用于求得在连续搜索空间上的无约束、静态、单目标优化问题的单个解。算法的分类是基于社会的、混合的、基于子群的、文化基因的（memetic) 、多次启动的和排斥的方法。第16章描述了求解多模优化问题多个解的PSO方法。基于序贯、并行和伪序贯的方法讨论了小生境算法。求解约束优化问题的PSO算法将在第17章讨论。处理约束问题的PSO算法的讨论是基于非可行解的剔除、罚方法、将约束问题转化为等效的无约束问题的方法、修理方法、保留可行解的方法以及Pareto排序方法。第18章讨论了多目标PSO算法。这些算法被分组，并基于聚集、基于准则和基于支配来讨论。该章还论述了多目标问题的性能度量。第19章解释了PSO怎样用于定位和跟踪动态变化环境下的最优点。第20章讨论了二元PSO及其用于求解定义在更一般的离散搜索空间上的问题的适应性。该部分结束于第21章，该章总结了PSO的应用。

在该部分中，应该最先阅读第12章，之后各章可以任意顺序阅读。然而，在阅读第14章之前先阅读第13章对读者是有帮助的。

第四部分介绍蚁群算法(ACO)。第22章是一个引言，讨论了ACO的起源。同时也给出了对其他昆虫研究的总结。不幸的是，由于篇幅的限制，本书没有介绍这些研究工作。第23章重点讨论了蚂蚁觅食行为模型，叙述了第1个ACO算法和ACO的控制参数。第24章描述了ACO算法的框架。第25章先总结了第1个基本ACO算法的大量变体。这些变体分为单个群、连续ACO、多个群和混合方法。业已证明ACO如何用于求解多目标问题和动态变化问题。该章还讨论了ACO算法的并行实现问题。第26章总结了ACO算法的应用，例如排序问题、指派问题、子集问题和分组问题。第27章总结了蚂蚁的集体决策能力，以及如何用人工激发工作对其建模。该章重点讨论了建模觅食蚂蚁的信息素痕迹跟踪行为，并且也讨论了基于层次的模型。第28章给出了ACO算法的形式化收敛证明的简要处理。第29章讨论了蚂蚁的墓地组织行为并且证明了该行为模型如何用于物体聚类。最后总结了不同的蚂蚁聚类算法。最后，第30章讨论了蚂蚁分工行为。

在第四部分中，第29章和第30章可以独立于其他章阅读。在剩余各章中应该最先阅读第23章，之后可以任意阅读其他各章。然而，建议在阅读第27章之前先阅读第25章。

本书末尾给出了大量的参考文献、进阶书籍的列表和所有缩写词和符号。本书尽可能避免对符号的重复命名。然而，当某一个符号的意义被重复定义时，在具体情况下，并不会使读者产生任何误解。

本书的成功出版得到了许多人的集体支持。没有他们的帮助和贡献，本书将永远不会面对读者。首先，要感谢我的母亲Magriet Engelbrecht，她忍受了将所有手稿输入并必须在很短时间内学会使用LATEX；要感谢我的父亲Jan Engelbrecht，他帮助我进行了校对并保证了手稿和打印材料是完全一致的。本书中的部分内容是我指导的博士生和硕士生的研究成果。还要特别感谢Frans van den Bergh、 Ulrich Paquet、 Riaan Brits、 Clive Naicker、 Lona Schoeman、 Mahamed Omran和Edwin Peer。一些人帮助我进行了最后的检查，他们是Leoni Venter、 Linda marshall、 Gary Pampara、 Auralia Edwards, 以及所有帮助校对材料的人们。我真诚地感谢每一个给予过我帮助的人。最后，我要感谢Wiley工作人员的帮助和支持，他们是Wendy Hunter、Mike Shardlow和Kelly Wigfield，还要感谢图形设计员，他为本书设计了一个精彩的封面。

A. P. EngelbrechtPretoria大学, 南非