2.3　群智能算法模式综述

典型的群智能优化算法主要有微粒群优化算法^[24-26]、蚁群优化算法^{[18-20，27-28]}、人工蜂群算法^[16，29]、细菌觅食算法^[30]、萤火虫算法^[31]等。这些算法虽然优化原理各不相同，但具有许多相同特征，对不同智能优化算法的理解对推进算法研究有着重要的启发作用。

2.3.1　微粒群优化算法

微粒群优化算法，或称为粒子群算法，是一种模拟鸟群社会行为规律而提出的群智能优化方法。微粒群优化算法最早由Eberhart和Kennedy在1995年共同提出^[24-26]，其最初主要意图是模拟鸟群的优雅而不可预测的行为，以发现统御鸟群同步飞行的模式，以及在最优形式重组时突然改变方向的模式。Eberhart和Kennedy在1995年的IEEE International Conference on Neural Networks和The Sixth International Symposium on Micromachine and Human Science上分别发表了Particle Swarm Optimization和A New Optimizer Using Particle Swarm Theory的论文，标志着微粒群优化算法的诞生。该算法简单有效，易于实现，适合科学研究和工程应用，受到越来越多的研究者的重视。

在微粒群优化算法中，粒子在超维空间中飞行。搜索空间内粒子位置的改变是基于个体模仿其他粒子成功的社会心理倾向，群内粒子的改变因此受其邻居的经验或知识影响，一个粒子的搜索行为因此受群中其他粒子的影响。社会行为的建模就是搜索过程中粒子随机地返回之前的搜索过程中发现的搜索空间中的成功区域。粒子群中的个体有一个基本行为：仿效邻域个体的成功和它们自己的成功。从这个基本行为显现出来的集体行为就是在一个高维搜索空间中发现最优区域。一个PSO算法维护一群粒子，其中每个粒子表示一个潜在的解。粒子在一个多维搜索空间中飞行，而每个粒子的位置根据它自身的经验及其邻居的经验来调整。驱动优化过程的是速度向量，速度向量反映了粒子的经验知识和粒子邻域的社会交换信息。粒子的经验知识通常被叫作“认知部分”，它与粒子离它从开始到搜索过的最佳位置的距离成正比。社会交换信息被叫作“速度方程的社会部分”。^[32]

生物群体内个体之间的相互作用产生的群智能，往往能够给某些问题的求解提供有效的方法。鸟群在寻找食物的过程中，个体之间存在信息交流和共享，每个成员可以从其他成员的搜索经验中获益，并调整自身的搜索行为。当食物源分布状态不可预测时，这种个体之间的协作所产生的优势是巨大的。基于信息交流和共享的个体间协作正是微粒群算法进行优化搜索的基础。在微粒群优化算法中，将优化问题的搜索空间类比作鸟类的飞行空间，并将每只鸟抽象为一个没有质量的微粒，微粒的位置表示问题的候选解，所需要找到的最优解相当于要搜索的食物。微粒群优化算法还为每个微粒设置了类似于鸟类运动行为的简化规则，从而能够使整个微粒群的运动表现出和鸟类觅食类似的特征，进而可以用于解决优化问题。

基本微粒群优化算法的具体实现步骤如下：

步骤1　随机初始化群体中各微粒的位置和速度。

步骤2　评价群体中所有微粒的适应度值。

步骤3　对每个微粒，将其当前适应度值和其历史最优位置所对应的适应度值进行比较。如果当前的适应度值更优，那么利用当前位置更新其历史最优位置。

步骤4　对每个微粒，将其历史最优适应度值和群体内或其邻域内所经过的最优位置的适应度值进行比较。若更好，则将其作为当前群体内或其邻域内的最优位置。

步骤5　更新每个微粒的速度和位置。

步骤6　若没有达到终止条件，则返回步骤2。

目前，微粒群优化算法已经被广泛用于函数优化、神经网络训练、组合优化、模糊系统控制等领域。^[33-38]比较有潜力的应用领域包括多目标优化、系统设计、模式识别、车间作业调度、机器人路径规划、时频分析和图像处理等。

2.3.2　蚁群优化算法

早在1亿年以前蚂蚁就已在地球上出现，蚂蚁群体所呈现的复杂行为给人类带来了启发，很多研究涌现出来，以便更好地理解这些行为。受这些研究与观察的启示，Marco Dorigo首次提出蚂蚁觅食行为的算法模型。^{[18-20，27-28]}从那时起，针对蚂蚁算法的研究取得了长足发展，涌现出一批相关算法和应用。关于种类众多的蚁群的觅食行为，研究表明初始的觅食行为是一个随机的混沌模式；当发现食物后，行为路径逐渐变得有组织，越来越多的蚂蚁会经过相同的路径。当一只蚂蚁发现食物后，它将食物拖回巢穴并沿路留下信息素。觅食的蚂蚁通过不同路径上信息素的浓度来选择路径。当越来越多的蚂蚁选择同一特定路径时，该路径就因聚集越来越多的信息素而更具有吸引力，从而吸引更多的蚂蚁选择该路径。这种自动催化导致的协作行为形成一种正反馈机制，使最优觅食路径被越来越多的蚂蚁选择。^[31-33]

Dorigo 1992年在其博士论文中提出该算法。1996年，Dorigo等发表了Ant system：optimization by a colony of cooperating agents一文，奠定了蚁群优化算法的基础。其提出蚂蚁系统、蚁群系统、最大—最小蚂蚁系统、蚂蚁-Q、快速蚂蚁系统、蚂蚁禁忌表算法、蚂蚁排名系统、近似不确定性树搜索等蚁群优化元启发式算法。蚁群优化算法通过其内在的搜索机制，已经成功应用于许多组合优化问题的求解中。因为算法仿真中使用的是“人工蚂蚁”的概念，因此有时也被称为“人工蚂蚁系统”。

基本蚁群优化算法的实现步骤可简单描述为：

步骤1　蚂蚁群体初始化，设置参数。

步骤2　对蚁群进行评价。

步骤3　利用状态转移规则生成新的蚁群。

步骤4　修改信息素浓度，根据信息素更新方程。

步骤5　如果不满足算法停止条件，返回步骤2；否则，继续步骤6。

步骤6　输出当前的最优解。

蚁群算法在经典的旅行商问题和二次分配问题上取得成效以后，已逐步在其他优化问题中取得了成功，如车辆调度问题、图着色问题、工件排序问题、超大规模集成电路设计和通信网络中的负载平衡问题等。这种来自自然界的现代启发式优化算法已经在很多方面表现出很好的优化性能，其求解问题的领域在不断扩大。^[6，39]

2.3.3　人工蜂群算法

蚂蚁并不是唯一让人类见识其群体智慧的昆虫。康奈尔大学的生物学家托马斯·西利（Thomas Seeley）长期以来观察蜜蜂奇特的决策能力——一个蜂房里的工蜂达50000只之多，蜜蜂是如何统一分歧，为蜂群谋得最大利益的？西利发现蜜蜂做出决策的依据是“集思广益”“各抒己见”，用一种有效的机制使选择最优化。这让西利大为惊讶。他把从蜜蜂身上学到的决策方法运用到一些会议上，让与会者考虑所有的可能性，提出各自的想法或意见，然后通过投票决定。

蜜蜂是一种社会化昆虫群体，蜜蜂个体可以担任不同角色，能够完成生育后代、照顾后代、觅食和御敌等工作，并且能够自发地在这些角色之间进行转换。人们利用蜜蜂完成不同工作的机理，提出了不同模型，并将其应用到找寻最优目标函数值、组合优化问题、水资源利用等方面。

通过蜂群的采蜜过程，发现蜜蜂可以通过气味、摇摆舞等多种信息交流方式，使整个蜂群协调完成收获花粉的工作。这种方式使蜂群成为具有自组织性、自我适应性及强鲁棒性的群体。Seeley最先提出了蜂群的自组织模拟模型。受蜂群采蜜过程启发提出的人工蜂群优化算法正是建立在蜜蜂自组织模型和群智能基础上的一种非数值优化计算方法。D. Karaboga在2005年成功地将该优化算法应用到函数的数值优化问题上，并提出了比较系统的人工蜂群算法^[29，40]（artifical bee colony algorithm，简记为ABC）。人工蜂群算法简单，鲁棒性强，在非限制性数值优化函数上有着比常见的启发式算法更加优越的性能。2006年，D. Karaboga和B. Basturk^[41]又进一步将ABC理论应用到限制性数值优化问题的解决上，并取得了比较好的测试效果。来源于蜂群采蜜行为的优化算法结合某些邻域搜索算法也被应用于如车间作业调度问题、函数优化问题等。

人工蜂群算法在具体应用中有各种变形，但是算法的框架基本类似，主要步骤可以描述为：

步骤1　随机产生一组解作为初始解组。

步骤2　求当前解所对应的目标值。

步骤3　形成新的解（当停止条件不满足时）。

步骤4　指派蜜蜂去那些选定的花朵处（最好的e个点处指派更多的蜜蜂）并计算相应的目标值。

步骤5　从每个花朵处选择最合适的蜜蜂。

步骤6　指派剩下的蜜蜂进行随机搜索并计算它们对应的目标值。

步骤7　当不满足停止条件时，重复步骤3至步骤7。

人工蜂群算法需要设置一定的参数。如侦查蜂的数量（n），n个可被采蜜点中挑选出的点的数量（m），挑选出的m个点中最优点的数量（e），指派去最优的e个点的蜜蜂数量（nep），起始的花朵数量（ngh）。算法开始时将n个侦查蜂随机地放置在搜索区域中。

2.3.4　细菌觅食算法

细菌觅食算法（bacterial foraging optimization，简记为BFO）是由Passino于2000年提出来的一种随机仿生算法^[30]，其生物机理是模拟细菌在觅食过程中所体现出来的智能行为，此算法具有群体智能性和并行搜索等特点。目前，细菌觅食算法已被应用于噪声干扰下的谐波估计问题和PID（proportional integral derivative）控制器的设计、自适应控制、车间作业调度等领域。

细菌觅食算法模拟的是大肠杆菌的觅食行为。^{[10，30，42]}大肠杆菌直径为1μm，长为2μm，在外界控制下，20分钟内即可进行自我繁殖。每个大肠杆菌在其自身的“生物发动机”鞭毛的运动下，每秒可实现100～200圈的转动，按每秒10～20μm的速度进行移动。大肠杆菌觅食过程中的觅食区域主要分为三类：

（1）当大肠杆菌处在中性介质中时，选择性地进行转动和游动。

（2）当大肠杆菌处在食物源丰富的区域时，大肠杆菌会在该区域停留一段时间；待食物消耗殆尽时，继续向着其认为食物源丰富的区域游动，游动时间更长。

（3）当大肠杆菌处在食物缺乏的区域时，其会根据以往的搜索经验，避免向不利区域游动。

按照这种方式，大肠杆菌能找到最丰富的食物源，同时避免营养匮乏。在觅食过程中，大肠杆菌用蛋白质接收器对食物进行感知，其感知非常灵敏，能随着环境的微妙变化迅速改变自身的搜索行为。这是生物界普遍存在的感知和决策系统。总体来说，细菌在外界条件和自身条件的约束下，朝着最有利方向移动，使其单位时间内所获得的能量最大化。

使用细菌觅食算法求解问题的实现步骤可简单描述为：

步骤1　对问题进行编码。

步骤2　设计评价函数Z。

步骤3　群体初始化，确定初始细菌群体S的规模及初始位置P。

步骤4　分三层循环：

内层循环：趋化性操作；

中层循环：复制操作；

外层循环：迁徙操作。

步骤5　输出当前最优解。

2.3.5　萤火虫算法

剑桥大学学者Yang于2008年提出一种新的群智能优化算法——萤火虫算法（firefly algorithm，简记为FA）。^{[11，31，43-45]}该算法的研究灵感来源于自然界中萤火虫通过独特的发光行为吸引周围的伴侣或猎物的现象，这种特有的光信息传递方式导致大批萤火虫聚集在一起。萤火虫算法的两个核心思想是萤火虫的吸引力及其位移。在解空间中萤火虫亮度的大小表示其解品质的好坏，目标函数值愈优则其亮度愈亮。每只萤火虫的进化遵循三个相继环节：亮度比较、萤火虫移动和亮度更新。^[31，43-45]

将萤火虫的发光模式与目标函数联系起来，进而形成一种新的智能计算模式。萤火虫算法主要遵循如下规则。

（1）所有的萤火虫不分雌雄。例如，下个萤火虫可以被其他萤火虫吸引而不管它们的性别。

（2）吸引力与其亮度成正比。对任何两个萤火虫，亮度弱的那个会飞向亮度强的那个。吸引力与亮度随着距离的增加而减弱，如果一个个体没有找到亮度更强的萤火虫，它将随机移动。

（3）萤火虫的亮度由目标函数决定。例如，对于最大化问题，亮度可以定义与目标函数值成正比，也可以用更为复杂的方法定义。

萤火虫算法的主要步骤可描述如下。

步骤1　定义目标函数，初始化群体，随机产生n个萤火虫的初始位置（i=1，2，…，n），设置算法参数。

步骤2　计算每个萤火虫的目标函数值，作为萤火虫的亮度。

步骤3　计算萤火虫的吸引力。

步骤4　比较萤火虫i和萤火虫j的亮度。若萤火虫i的亮度小于萤火虫j的亮度，根据公式移动萤火虫i；若种群中无萤火虫亮度大于萤火虫i，则萤火虫i按概率随机移动。

步骤5　萤火虫亮度更新。

步骤6　如未满足结束条件，则返回步骤3。

步骤7　输出全局最优位置。