张浩然

责任编辑：苏向阳

文章发表于微信公众号【运筹OR帷幄】：优化 | 粒子群算法介绍

编者按：

粒子群算法是计算数学中用于解决最优化的搜索算法，也是最为经典的智能算法之一。应用主要是在工程和计算机科学还有行为管理研究科学里面。通过阅读这篇文章，你将了解粒子群算法的概念，优缺点以及发展方向。

1、简介

粒子群算法(Particle Swarm Optimization,简称PSO)是1995年Eberhart博士和Kennedy博士一起提出的[1]。粒子群算法是通过模拟鸟群捕食行为设计的一种群智能算法。区域内有大大小小不同的食物源，鸟群的任务是找到最大的食物源（全局最优解），鸟群的任务是找到这个食物源。鸟群在整个搜寻的过程中，通过相互传递各自位置的信息，让其他的鸟知道食物源的位置最终，整个鸟群都能聚集在食物源周围，即我们所说的找到了最优解，问题收敛。学者受自然界的启发开发了诸多类似智能算法，如蚁群算法[2]、布谷鸟搜索算法[3]、鱼群算法[4]、捕猎算法等等[5]。有兴趣的读者可以深入了解一下。

2、算法策略

粒子群算法的目标是使所有粒子在多维超体（multi-dimensional hyper-volume）中找到最优解。首先给空间中的所有粒子分配初始随机位置和初始随机速度。然后根据每个粒子的速度、问题空间中已知的最优全局位置和粒子已知的最优位置依次推进每个粒子的位置。随着计算的推移，通过探索和利用搜索空间中已知的有利位置，粒子围绕一个或多个最优点聚集或聚合。该算法设计玄妙之处在于它保留了最优全局位置和粒子已知的最优位置两个信息。后续的实验发现，保留这两个信息对于较快收敛速度以及避免过早陷入局部最优解都具有较好的效果。这也奠定了后续粒子群算法改进方向的基础。

3、算法步骤

基础粒子群算法步骤较为简单。粒子群优化算法是由一组粒子在搜索空间中运动，受其自身的最佳过去位置pbest和整个群或近邻的最佳过去位置gbest的影响。每次迭代粒子i的第d维速度更新公式为:

粒子i的第d维位置更新公式为：

其中

-第k次迭代粒子i飞行速度矢量的第d维分量

-第k次迭代粒子i位置矢量的第d维分量

c1,c2-加速常数，调节学习最大步长

r1,r2-两个随机函数，取值范围[0,1],以增加搜索随机性

w-惯性权重，非负数，调节对解空间的搜索范围

粒子群算法流程图如下：

通过速度更新公式我们可以看出，若需要算法快速收敛，我们需要将加速度常数调大。但是这么做可能会导致算法出现“早熟”。若把惯性权重调大，可增加粒子探测新位置的“积极性”，避免过早陷入局部最优，但也会降低算法的收敛速度。对于有些改进算法，在速度更新公式最后一项会加入一个随机项，来平衡收敛速度与避免“早熟”。并且根据位置更新公式的特点，粒子群算法更适合求解连续优化问题。

4、实例计算

这里，我们选用一个非常经典的测试函数Rastrigin方程作为实例计算，来观察粒子群算法的收敛过程。Rastrigin方程的表达式为：

A=10,xiϵ[−5.12,5.12]。当x为0时，方程值达到最小f(x)=0。

在二维变量下，这个方程是长这个样子的：

我们可以看到，方程具有很强的非凸性（密集恐惧症）。当维数增加时，随机搜索算法很容易陷入某个局部最优解中。我们利用粒子群算法求解了该测试函数。收敛过程如下图所示（为了更好地表现收敛，我们特意加大了随机项系数，使得收敛过程缓慢一些）：

迭代次数1, 5, 10, 20, 50, 和100

这些粒子（蓝点）很快就找到了全局最优解的位置（图中心）。由于有随机项的存在，有些粒子即使在收敛后也不断跳出（不用太在意这些细节）。当然如果读者想避免这种情况，可以将随机项系数设为动态值，即随着迭代次数增加，该值越小。经验表明当随机项系数随迭代次数成指数速度减小时，可增加搜索全局最优解的概率，并提高计算速度。

5、评价标准

目前评价（改进）粒子群算法的标准已经非常成熟。业内大牛已经整理出了许多不同维度的标准测试函数。需要从准确率（与最优解的偏差），成功率（计算到最优解的概率），计算速度以及稳定性（均值，中位数，方差）等方面对算法进行考量。IEEE演化计算大会更是提出了一个完整的benchmark库和评价计算方法（
http://www.ntu.edu.sg/home/epnsugan/index_files/cec-benchmarking.htm）。同时每年也会组织演化计算竞赛。有兴趣的读者可以查找一些近些年获奖的论文深入研究一下。

6、改进方向

粒子群算法虽然自提出以来就吸引了大量学者的目光，但粒子群算法也存在诸多弊端，如局部搜索能力差，容易陷入局部极值，搜索精度低等。针对这些问题，粒子群算法有如下三类的改进方向：

第一类改进方法为改变粒子关系的拓扑结构。我们之前说粒子群设计玄妙之处在于它保留了全局最优位置和粒子已知的最优位置两个信息。然而历史最优位置（为方便我们称为位置A）和粒子已知的全局最优位置（为方便我们称为位置B）我们可以稍加改动。最经典的改进为master-slave算法。首先，我们可以将问题分解为诸多的master粒子和slave粒子，根据适应值的不同挑选master粒子。每个master粒子下有不同数量的slave粒子，master粒子1所在区域的位置A1为master和slave所有粒子的历史最优位置。同理，我们可以得到对应的A2和A3等粒子的最优位置，对比不同最优位置的数值，得出全局最优位置B。这种算法的好处是，如果master粒子1所属粒子陷入局部最优或者无法找寻到最优解的情况，master粒子2、master粒子3及其它master粒子所在区域仍继续搜寻，一定程度上保证了解的最优性。

master社区粒子的位置A为master社区和slave社区所有粒子的最优过去位置。而slave社区粒子的位置A仅仅为该slave社区所有粒子的最优过去位置。这样，当划分出多个slave社区时，即使有一个slave社区粒子收敛陷入局部最优，仍能保证master社区粒子有较大的概率跳出这个局部最优位置。

第二类改进方法为引入新的机制。通过引入新的控制粒子的机制来加快收敛速度，并且避免陷入局部最优。这类改进方法的一个例子为捕猎算法。在粒子群算法计算中，当出现收敛趋势时，将会有大量的低速度粒子聚集。这些低速的聚集粒子并不会加速算法收敛也不会探测新的位置增加跳出局部最优的概率。所以我们称这些粒子为“懒惰粒子”。在迭代过程中，这些“懒惰粒子”仍会占用计算量。于是，如果能加入一种删除机制，删除这些“懒惰粒子”并生成出一些活跃的粒子，那么就可以在加快计算速度的同时减少收敛陷入局部最优的概率。这里引入了老鹰捕食兔子的机制，删除老弱病残的“懒惰”兔子，并增加新的“活跃”兔子。

第三类改进方法为耦合其他算法。由于不同的算法有不同的优点，如何将不同算法耦合以克服算法自身缺陷一直是研究的热点。目前进行耦合计算的热点算法有模拟退火，蚁群算法，遗传算法等等。

结语

粒子群算法是一个简洁且强大的优化算法。它可以嵌套非凸模型、逻辑模型、复杂模拟模型、黑箱模型、甚至实际实验来进行优化计算，是一个让人欲罢不能的算法。虽然粒子群算法在诸多领域均有不错表现，如电力系统，生物信息，物流规划等，但对于一些特定问题的求解，粒子群并不能保证解的质量。因此，粒子群算法的发展仍在继续，其研究仍有许多未知领域，如粒子群理论的数学验证等等。期待着各位读者大佬为粒子群算法的发展增砖加瓦。

参考文献：

[1] A new optimizer using particle swarm theory, in: MHS’95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Ieee, 1995, pp. 39-43.

[2] Ant colony optimization: a new meta-heuristic, in: Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), IEEE, 1999, pp. 1470-1477.

[3] Cuckoo search via Lévy flights, in: 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), IEEE, 2009, pp. 210-214.

[4] An optimizing method based on autonomous animats: fish-swarm algorithm, Systems Engineering-Theory & Practice, 22 (2002) 32-38.

[5] A novel particle swarm optimization based on prey–predator relationship, Applied Soft Computing, 68 (2018) 202-218.

相关文章推荐

我们还有其他演化计算介绍文章。欢迎大家阅读。

蓝字标题，即可阅读《【优化】遗传算法介绍》。

其他

【优化】优化理论科普丛书专题征稿之群体智能算法理论

温馨提示

可以在 本公众号后台 回复关键词：“ 捕猎算法源代码 ”获得捕猎算法中文注解matlab源代码，如果觉得有用， 请勿吝啬你的留言和赞哦！~