集群智能算法综述

秦小林，罗 刚，李文博，张国华

（1.中国科学院成都计算机应用研究所，成都 610041；2.中国科学院大学，北京 100049；3.中国航天科工飞航技术研究院磁悬浮与电磁推进技术总体部，北京 100074）

1 引 言

针对工程技术领域中复杂的优化问题，众多学者选择从自然界的现实模型中寻求解决方法，由此开启了自然启发式计算（Nature-inspired computation）的研究。在过去几十年里，自然启发式计算是最受研究者关注的人工智能研究分支之一，平均每年有数百个优秀的新算法提出，且这一增长趋势仍在继续。这些算法在适应性、自学习能力、鲁棒性及高效性等方面都有很好的表现。自然启发式计算中有一类关注简单行为个体组成的集群通过自组织完成复杂任务的工作，称作集群智能(Swarm Zntelligence)，如图1。

图1 集群智能与人工智能的关系Fig.1 The relationship between Swarm Intelligence and Artificial Intelligence

1993年，Dario等研究了移动机器人系统，并提出了集群智能的概念[1]，指出简单的有序系统即可产生非平凡的智能行为。Kordon[2]将集群智能定义为基于无中心、自组织群体行为的智能计算技术。而Bonabeau[3]为群体智能给出了更简单的定义，即由简单的个体组成的群体所产生的集体智慧。一个典型的集群智能系统由若干个可以相互通信的、只能完成简单行为的代理（agent）组成，这些代理没有控制中心，行为简单，但往往可以通过相互之间的简单交互完成十分复杂的任务，整体上表现出智能。集群智能系统表现出智能的现象常称为“涌现”[4]。集群智能发挥了集群的所有优势，自组织、无中心控制、高鲁棒性、灵活且低消耗，面对大规模的复杂问题时仍能给出最优解。

最早的集群智能算法包括如蚁群优化算法[4]（Ant Colony Optimization, ACO）和粒子群优化算法[5]（Particle Swarm Optimization, PSO）等都受到了广泛的关注和应用，在很多领域都大获成功，如经典的旅行商问题等。它们普遍具有结构简单、参数少、实现容易等特点。如今已广泛应用于函数优化、多目标优化、求解整数约束和混合整数约束优化、神经网络训练、信号处理、路由算法等实际问题，实践结果证明了这些算法的可行性和高效性[6]。这些年来，学界对解决复杂计算任务的集群智能算法研究呈爆炸趋势增长，如图2所示。

图2 集群智能算法文章趋势（数据来自Scopus）Fig.2 Tendency of Swarm Intelligence algorithm articles (data from Scopus)

上述研究大多与优化问题相关，主要集中在健康卫生、社交网络、交通运输、能源气候、工业4.0等领域，都取得了很好的效果[7-11]。除了应用研究，针对集群智能算法本身性质的理论研究也同样引人关注。集群的简单交互如何涌现出智能；面对同一个问题，不同的集群智能算法却表现千差万别，如何从理论上分析这种区别；问题的建模方法与算法求解效率关系；算法搜索的精度和广度的平衡等。某些问题已取得了一些喜人的进展，然而更多的理论研究则收效甚微，仍极具挑战性。

本文接下来安排如下：第2节简单回顾最重要的两个集群智能算法——粒子群优化算法和蚁群优化算法；第3节介绍部分集群智能表现优异的应用场景；第4节讨论集群智能的理论研究及发展方向；第5节为总结。

2 集群智能算法介绍

2.1 粒子群算法

1995年，社会心理学家Kennedy与电气工程师Eberhart受鸟群或鱼群觅食行为的启发，进而提出了粒子群优化算法用于解决日益复杂的优化问题[5]。他们将族群中的个体（粒子）当作给定优化问题的一个解，粒子在解空间中按照某种策略移动或游走，试图找到问题的最优解。粒子群优化中粒子的移动策略参考的是鸟群觅食行为，并非完全漫无目的地在区域内“碰运气”，而是会向群体分享自己的知识，并参考种群中最好的经验和自己记忆中最好的地点，综合决定下一步去寻找食物的位置。粒子群优化中这两个参考因素分别是种群最优（gbest）及个体最优（pbest），粒子根据这两个因素来更新自己的移动速度向量。假设待解决问题在D维搜索空间，在t时间下群体中的第i个粒子的当前位置由D维向量来表示，其速度由另一个D维向量表示，第i个粒子访问过的最优解位置用表示，群体中最优粒子的索引为“g”，则在每次搜索迭代中，第i个粒子的速度和位置分别由下式进行更新：

原始的粒子群优化算法的流程如下：创建一个大小为S的D维群体，并初始化速度向量；for t=1 to 最大迭代次数 do for i=1 to S do应用速度更新等式（1）；应用位置更新等式（2）；计算位置更新后的适应度值；如果需要，更新pbest和gbest的历史信息；end如果gbest满足问题需求，则终止算法；end

其中：i=1,2,…,S为粒子索引，S是群体大小，ω是惯性权重；c1和c2为加速系数，用于调整粒子向全局最优及自身最优运动的最大步长，也可称为学习因子，表示粒子“自我学习”和“社会学习”的能力；r1和r2是满足均匀分布(0,1)的随机数。可以看到，速度更新时考虑了三部分的内容：第一部分是自身运动的惯性，记录自己原本的运动方向，其目的是防止粒子剧烈地改变方向；第二部分是认知或自我部分，通过这一项，粒子的当前位置会向其自己的最好位置移动，这样在整个搜索过程中，粒子会记住自己的最佳位置，从而避免自己四处游荡；第三部分是社交部分，负责通过群体共享信息，为保证粒子向群体中最优的个体移动，即每个个体向群体中的其他个体学习。

公式（1）与公式（2）描述的是粒子群优化算法的原始形式，其在多个数据集上都取得了十分不错的效果，但是算法本身还存在诸多问题。例如，粒子群算法易陷入局部最优；算法的收敛速度会逐渐变得缓慢；算法的参数选择随机，需要经过多次调整才能取得好的效果。针对这些问题，众学者提出了很多改进方案，例如Clerc等[12]在粒子群优化算法中引入压缩因子用于控制算法收敛；Bergh等[13]将搜索空间按维度进行分割，分别使用粒子群优化算法得到最优解后合并成完整的解；除算法本身的改进外，还有很多研究者将粒子群优化算法与其他算法结合，提出性能更优的混合算法[14-15]。

2.2 蚁群优化算法

蚁群优化算法模仿蚂蚁的合作行为来解决复杂的组合优化问题[4]。蚂蚁是一种高度社会化的生物，它们觅食时可快速越过障碍物，找到蚁巢与食物之间的最短路径。如图3，蚁群觅食过程中，如果蚁巢到食物源已存在最短路径，则蚂蚁会按此路径搬运食物；当前路径如被障碍物阻隔，需要寻找新的路径，蚁群会按照所有可能的方向出发寻找新的路径，最后的路径就是最优路径。Dorigo等[4]经过研究后将这一过程分为路径构建与信息素更新两步，进而提出了蚁群优化算法。初始化时，蚂蚁会漫无目的地按照随机选取的方向搜索食物，并在搜索过程中释放信息素；沿途的信息素会随时间挥发，因此较短的路径相比于较长的路径会残留更多的信息素；后续的蚂蚁根据信息素的指引选择路径，因此会有更多的蚂蚁选择信息素残留较多也就是较短的路径。这些蚂蚁在搜索过程中同样也会释放信息素，使较短的路径又会累计更多信息素进而吸引更多蚂蚁。这样的正反馈机制下，最终蚁群会找到最短路径也就是问题的最优解。蚁群优化算法用于搜索最优路径在旅行商问题上取得了非常好的效果。因其分布式并行、强鲁棒性、易与其他算法结合等特点受到学界的广泛关注，并针对性地提出了很多的改进算法和混合算法，用于无线网络、作业调度、路径规划、数据挖掘等领域。

图3 蚁群觅食图例Fig.3 Figure of ant colony foraging

除了粒子群优化算法与蚁群优化算法外，集群智能领域还有很多非常优秀的优化算法。文献[16]提出了一种模拟蜜蜂觅食行为的人工蜂群优化（Artificial Bee Colony，ABC）算法，ABC算法中除了蜜蜂的基础选择机制与蜜蜂间的简单交互外，还引入了一些局部与全局搜索机制，在人工神经网络训练、组合优化、电力系统优化、系统和工程设计等多个领域得到广泛应用；蜘蛛猴优化[17]灵感来自蜘蛛猴在觅食过程中的裂变融合社会(Fission-Fusion Social)结构，巧妙地描述了群体智能最重要的两个基本概念：自组织和分工；还有其他的集群智能算法，如细菌算法、布谷鸟搜索、萤火虫算法、蝙蝠算法、细菌觅食优化、烟花算法等都在很多领域取得了良好效果。在此，我们总结了一些经典的集群智能算法，如表1所示。

表1 主要集群智能算法Table 1 Main Swarm Intelligence algorithms

3 集群智能应用

集群智能作为优化算法，涉及的应用领域极其广泛。本部分仅选取近年来的部分热门领域作简单介绍。需要了解的是不同的集群智能算法面对不同的应用问题有不同的性能表现，如粒子群优化算法在分布式资源管理、定位、资源分配、最大化/最小化、全局优化自适应学习等领域表现优异，而蚁群优化算法则擅长网络分析、旅行商问题、路由算法、聚类问题、博弈论等。

Ad Hoc网络是集群智能算法尤其是蚁群优化算法应用最成功的领域之一。我们知道，集群智能的一个非常重要的特性就是无中心、自组织，这是Ad Hoc网络区别于传统网络最鲜明的特点，因此集群智能算法在Ad Hoc网络中得到了极为广泛的应用。以路由协议为例，自20世纪90年代开始，有大量的基于蚁群优化算法的Ad Hoc路由协议开发出来，包括基本网络通信路由协议，如 AntNet(2018)[58]、ARA[59]、PERA[60]、AntHocNet[61]等，以及满足特定应用需求的路由算法，如ACO-EEAODR[62]、AntHocMMP[63]、POSANT[64]等。

大数据技术与机器学习作为近些年的研究热点，同样有许多集群智能算法的身影。以特征提取过程为例，粒子群优化算法、蚁群优化算法、萤火虫算法、布谷鸟搜索等都取得了很不错的效果，Abdi等[65]于2013年提出的用于红皮病的诊断模型，便是利用基于粒子群优化算法与支持向量机（Support Vector Machine，SVM）的方法作特征提取。Chen等[66]利用蚁群优化算法结合粗糙集理论提取最小特征集，并得到了很好的结果。Huang[67]则结合蚁群优化算法和SVM方法提取小而优的特征集，所提出的基于蚁群优化算法的分类器极大地提高了分类精度。Kadri等[68]提出的基于二进制编码的蚁群优化算法通过消除噪声特征的方法提取最优特征集。

集群智能算法在智能电网中也得到了广泛的应用[69-70]，文献[71]将粒子群优化算法用于分布式发电机系统来减少系统的能量损失，文献[72]应用粒子群算法优化分布式能源系统中的效益成本比，同样粒子群优化算法还用于实现智能电网的需求侧管理系统[73]，类似的工作还有文献[74-75]。这些工作都成功地减少了系统的能源损耗，展现了集群智能算法在能源系统与智能电网领域的应用潜力。集群智能算法同样促进了城市智能交通领域的发展，文献[76]将车辆的燃料损耗加入算法的评估函数中，使用蚁群优化算法做路径规划，在得到最优路径的同时有效地节省了车辆的整体燃料消耗。文献[77-78]使用粒子群优化算法来优化电池使用，以延长电动车辆的电池使用寿命。文献[79]将粒子群优化用于车辆避碰，所提出的PID控制器，不仅可使CCAS实现基本功能，还可实现车辆动态稳定性、行驶舒适性和燃油经济性的改善。粒子群优化在文献[80]中用于交通流量预测，同样的任务，文献[81]则采用了人工神经网络与蚁群优化算法的混合算法。关于智能交通中集群智能算法的应用，更多可参考文献[82-83]，而文献[84]与文献[85-86]分别是应用智能算法解决智慧交通系统的信号灯控制问题与交通拥塞问题的综述性文章。近些年其他的研究热点，如社交网络分析[87-88]、医疗与卫生系统[89-91]、网络空间安全[92-93]、游戏AI[94-95]等同样具有集群智能算法的身影。

4 集群智能理论研究

集群智能自诞生以来就广受工业与学术界关注，一个重要的原因是其神秘的运行机制。其在很多问题上都能取得极优秀的结果，但是学界始终不能揭示出这其中的理论基础，这些困惑始终激励着研究者对其进行更深入的研究。这些研究可以总结为三个主要问题：集群智能算法智能行为的产生机制；不同集群智能算法面对同一问题的性能表现不同的原因；在选定场景后，使集群智能算法性能最优的设计方法。这些问题的任何一点进展都是集群智能优化领域的极大突破，吸引研究者的持续投入。

研究者首先想要弄清楚，智能从何而来？已经被学术界所知的是，集群智能这一特性并非所有种群都具有，它只存在于具有社会性特征的群居个体之间进行交互的活动中。研究者普遍从生物界出发研究这一问题，Bonabeau[3]研究了生物蚁群的觅食、运输、分工等行为，并在分析后建模构造了集群智能算法。更普遍的结论是由Kennedy等[96]给出的，他们研究了鸟群的协同运动后认为：集群智能产生于社会交往，文化和认知也是人类社交的结果。

智能产生于交互，那为什么在同一个问题中不同的集群智能算法性能差距如此巨大，即为什么一个集群智能算法在某些问题中要比其他集群智能算法好那么多？这一问题在宏观上可以用“没有免费的午餐（No Free Lunch）”原理解释[97]，它表明了不存在任何一个优化算法可以在所有场景中都优于其他所有的算法。所以研究者转而对算法特性做更深入的研究，首先就是对集群智能比传统算法最大的优势特性——收敛性和计算复杂性的分析。其中最重要的研究之一就是对集群智能算法收敛性的分析，即研究在给定条件下算法能够保证的收敛速度，包括马尔可夫模型、不动点理论、变量分析、动态系统等模型都已用于这方面的研究[98]，如文献[99-100]利用动态系统和 Logistic映射等方法研究了粒子群优化，萤火虫算法中保证算法收敛的参数值的范围；文献[101]则采用马尔可夫链蒙特卡罗方法对集群智能算法内部代理之间的交互建模进而研究其收敛性。

在理解不同算法对同一问题的性能差异后，还需要知道面对特定问题集群智能算法求解性能与问题建模方式之间有什么关系，或者说给定应用场景后如何选择设计策略使集群智能算法的性能最优？有学者引入适应度曲面分析[102]的方法，分析解空间与集群智能算法设计之间的关系，例如文献[103]使用带随机游走的适应度曲面分析方法选择合适的启发式算法用于解决蛋白质结构预测问题。然而，目前这些工作都是针对特定问题，难以用于推广解决更一般的问题。

集群智能算法的搜索效率同样是值得关心的问题，这一问题通常是研究算法搜索的收敛性和多样性的平衡[104-105]。搜索候选解集的多样性通常是算法成功找到最优解的前提，但是多样性的增加会导致收敛性降低并直接影响搜索效率。根据这一原则，目前的研究者主要是根据自己特定的问题需求调节参数[106]实现算法的高效率搜索。

5 结束语

近年来，关于集群智能算法的研究增长迅速，但是这一领域所遗留下的问题同样很多。首先，学术界仍缺乏一个适用于所有算法的收敛性分析框架，虽然研究者提出了很多针对某些经典集群算法，如粒子群优化或蚁群优化算法的收敛性分析方法，但是却很难将之推广到其他算法上。其次，针对特定问题，算法的参数选择如种群大小、学习率等仍然只能依靠经验与实验测试，而没有确定性的理论指导。更重要的是，在集群智能算法性能对比中，还没有一个研究工作是公认的很好的方法，多数研究者在做性能测试时都只能对比给定计算结果所需的迭代次数或给定迭代次数下的计算结果，这样的结果受算法参数和评估函数选取的影响极大，不具有推广价值，还需要找到一个通用可推广的集群智能算法性能评估方法。

未来针对集群智能算法的研究仍然以优化应用为主，但是理论研究所占的比重也将会逐步增加。没有免费的午餐原理告诉我们，没有单一的算法可以被指定为最佳算法，只要它经过足够多的问题的测试，总是会激励研究人员开发新的计算智能算法。

总体而言，目前对集群智能的了解十分有限，任何一项微小的理论成果都是这一领域的巨大突破。虽然困难重重，但是需要相信不管未来如何发展，集群智能算法与集群智能研究都会在各领域扮演更加重要的角色。