粒子的拓扑结构对PSO性能的影响

Tim Blackwell , and Jim Kennedy. "Impact of communication topology in particle swarm optimization." IEEE Transactions on Evolutionary Computation (2018). DOI: 10.1109/TEVC.2018.2880894

提到PSO，脑海中的第一印象就是下面的速度和个体更新公式：

    (1)

    (2)

其中和分别表示个体的历史最优解和所有个体的历史最优解，也就是全局最优解。

公式(1)和(2)所表示的PSO只是PSO算法的一个版本，很可惜现在只要提起PSO算法，大多数情况下默认就是这个版本。所以大部分文献将PSO的优缺点分别总结为收敛速度快和容易陷入局部最优。但这其实只是这个版本的PSO的优缺点，并不能代表全部PSO算法的优缺点。

看完TEVC上的这篇分析粒子拓扑结构对PSO算法性能的影响之后，让我对PSO算法有了进一步的认识。原来PSO算法中粒子拓扑结构，或者搜索信息的传递机制对其性能有很大的影响。用PSO求解手头遇到的问题时性能并不好的原因可能在于没有根据问题的特性（如多模态/单模态/可分离/不可分离，等等）去选择合适的粒子拓扑结构（或者其他参数），并不能怪罪于PSO本身的性能不够强大。所以下文主要总结了这篇文章的主旨、实验和结论，以备忘。

1. 主旨

这篇文章的内容很多，前半部分主要介绍了PSO算法的概念、粒子拓扑结构（集中式、分布式、动态结构、小生境）等。后半部分主要是实验、分析和总结。总结起来，该文主要讨论了PSO中两种极端的拓扑结构在不同性质的问题上的性能。 这两种结构分别用Pbest和Gbest表示。其中Pbest代表分布式的拓扑结构（ring topology），Gbest代表集中式的拓扑结构，参见下图。

（左）Gbest结构，（右）Pbest结构

表现在公式上，两种结构的主要不同在于，在Gbest结构中，种群的全局最优被用于更新每个粒子的速度，而在Pbest结构中，粒子的邻域最优解被用来更新粒子的速度。所以其实公式（1）和（2）所表示的为PSO的Gbest拓扑结构。Pbest拓扑结构的速度更新公式如下

    （3）

其中表示粒子的邻域最优，而不是全局最优（当邻域为整个种群时，Pbest变为Gbest）。

当然除了Gbest和Pbest结构之外，粒子的拓扑结构还有很多种，只不过这两种结构是集中式和分布式结构的两个极端例子（end-points），所以在文章中作者主要测试了这两个版本的PSO的性能。另外，Pbest本身也有不同的结构，比如可以选择不同的邻域大小，当领域为整个种群时，就变成了Gbest。

2. 实验

作者在实验部分共使用了95个测试函数，总结出了14个不同的问题特性，辨识度比较高的四个特性是：多/单模态和可/不可分离。种群大小和变量个数均为30，独立运行50次，停止准则为150000次评价。使用了三个评价指标，分别是误差(Error)、多样性(Diversity)、后发制人能力(Last Improvement)（评价算法在搜索后期的收敛能力）。实验结果如下表所示。

表1 测试结果

其中Error指标越小表示算法在这个指标上的性能越强，其他两个指标都是越大算法越强。由于测试例子太多，每个函数的详细结果作者列在了附录中（附录有51页那么长），表1是作者高度浓缩后的结果，黑色字体表示算法性能强得很明显（）。从上表可以看出，从Error指标看来，Gbest和Pbest各有所长，但总体来说还是Lbest更强一些（看第一行，Lbest得分49.9，小于Gbest的51.1，且我们可以看到49.9被加粗了，表示强得很明显）。再看多样性指标和后发制人指标，可以明显看出Lbest这边一片黑，表明Lbest搜索区域更广、后发制人能力更强。总结起来Lbest结构的搜索特点是广泛撒网，定点捞鱼。前期猥琐发育，后期强势追击。收敛速度慢，但是收敛性能好，所以更适合求解多模态和不可分离的问题（对比第三行和第四行，以及第五行和第六行 （干一行行一行，一行行，行行行））。而Gbest结构的搜索则是一锤子买卖，很容易陷入局部最优（面对多模态、不可分离等复杂问题时 （干一行不行一行，一行不行，行行不行）），所以在求解可分、单模态等简单问题时，用Gbest拓扑结构能搜得更快，搜得更好。

针对表中的结果，作者的总结道：在本文所用测试集上且停止准则为150000次的情况下，Lbest拓扑结构（的PSO算法）在85%的测试集上表现比Gbest好，如果将停止准则再提高一些，这一数字可以提高到89%。

3. 分析

作者还分析了Pbest中不同的邻域（）大小（）对PSO性能的影响。结果如下：

表2

L2-L16分别表示不同大小的邻域，LME表示最小平均误差(lowest mean error)，G表示Gbest拓扑结构。从上表可以看出，G占的格子个数没有L多（表中的G表示Gbest效果最好，Lk表示L的性能比较好，=表示不相上下），所以还是Lbest拓扑结构的总体性能更好一些。

4. 总结

通过对PSO算法中粒子拓扑结构很长篇幅的实验和分析，作者只为了表达一个想法：将Gbest拓扑结构当作PSO默认拓扑结构的观点是绝对错误的，希望PSO研究者以后在选择拓扑结构时能三思而后行。

5. 感受

受制于正文篇幅的限制，作者将大部分实验结果放在了附录中（附录长达51页），只在正文中放置了几个高度总结性的表格。敬佩作者的严谨（总共使用了84（还是95个已经分不清了）个测试函数）和耐心（在附录中提供了所有测试函数的特性和所有实验的详细结果，提供了84幅结果图）。作者花了这么长的篇幅只是为了提出和证明一个被大多数文章忽略的事实。可敬可佩。