粒子群优化

粒子群优化（Particle Swarm Optimization, PSO），又称粒子群算法、微粒群算法，是由 J. Kennedy 和 R. C. Eberhart 等^[1]于1995年开发的一种演化计算技术，来源于对一个简化社会模型的模拟。其中“群（swarm）”来源于微粒群符合 M. M. Millonas 在开发应用于人工生命（artificial life）的模型时所提出的群体智能的5个基本原则。“粒子（particle）”是一个折衷的选择，因为既需要将群体中的成员描述为没有质量、没有体积的，同时也需要描述它的速度和加速状态。

PSO 算法最初是为了图形化地模拟鸟群优美而不可预测的运动。而通过对动物社会行为的观察，发现在群体中对信息的社会共享提供一个演化的优势，并以此作为开发算法的基础^[1]。通过加入近邻的速度匹配、并考虑了多维搜索和根据距离的加速，形成了 PSO 的最初版本。之后引入了惯性权重w来更好的控制开发（exploitation）和探索（exploration），形成了标准版本。为了提高粒群算法的性能和实用性，中山大学、（英国）格拉斯哥大学等又开发了自适应（Adaptive PSO）版本^[2]和离散（discrete）版本^[3]。

PSO 算法属于一种万能启发式算法，能够在没有得知太多问题信息的情况下，有效的搜索具有庞大解空间的问题并找到候选解，但同时不保证其找到的最佳解为真实的最佳解。

算法原理

PSO 算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是 D 维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第 i 个微粒表示为 X_i =(x_i1, x_i2, …, x_iD) ，它经历过的最好位置（有最好的适应值）记为 P_i = (p_i1, p_i2, …, p_iD)，也称为 pbest。在群体所有微粒经历过的最好位置的索引号用符号 g 表示，即 P_g，也称为 gbest 。微粒 i 的速度用 V_i = (v_i1, v_i2, …, v_iD) 表示。对每一代，它的第 d+1 维（1 ≤ d+1 ≤ D）根据如下方程进行变化：

       v_id+1 = w∙v_id+c₁∙rand()∙(p_id-x_id)+c₂∙Rand()∙(p_gd-x_id)        (1a)
       x_id+1 = x_id+v_id+1				              (1b)

其中w为惯性权重（inertia weight），c₁和c₂为加速常数（acceleration constants），rand() 和 Rand() 为两个在[0,1]范围里变化的随机值。

此外，微粒的速度 Vi 被一个最大速度 V_max 所限制。如果当前对微粒的加速导致它的在某维的速度 v_id 超过该维的最大速度 v_max,d，则该维的速度被限制为该维最大速度 v_max,d。

对公式（1a），第一部分为微粒先前行为的惯性，第二部分为“认知（cognition）”部分，表示微粒本身的思考；第三部分为“社会（social）”部分，表示微粒间的信息共享与相互合作。

“认知”部分可以由 Thorndike 的效应法则（law of effect）所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被激励着去减小误差。

“社会”部分可以由 Bandura 的替代强化（vicarious reinforcement）所解释。根据该理论的预期，当观察者观察到一个模型在加强某一行为时，将增加它实行该行为的几率。即微粒本身的认知将被其它微粒所模仿。

PSO 算法使用如下心理学假设：在寻求一致的认知过程中，个体往往记住自身的信念，并同时考虑同事们的信念。当其察觉同事的信念较好的时候，将进行适应性地调整。

标准 PSO 的算法流程如下：

初始化一群微粒（群体规模为 m ），包括随机的位置和速度；
评价每个微粒的适应度；
对每个微粒，将它的适应值和它经历过的最好位置 pbest 的作比较，如果较好，则将其作为当前的最好位置pbest；
对每个微粒，将它的适应值和全局所经历最好位置 gbest 的作比较，如果较好，则重新设置gbest的索引号；
根据方程（1）变化微粒的速度和位置；
如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数 G_max ），回到（2）。

算法参数

PSO 参数包括：群体规模 m ，惯性权重 w ，加速常数 c₁ 和 c₂ ，最大速度 V_max，最大代数 G_max。

V_max 决定在当前位置与最好位置之间的区域的分辨率（或精度）。如果 V_max 太高，微粒可能会飞过好解，如果 V_max 太小，微粒不能进行足够的探索，导致陷入局部优值。该限制有三个目的：防止计算溢出；实现人工学习和态度转变；决定问题空间搜索的粒度。

惯性权重w使微粒保持运动的惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。

加速常数 c1 和 c2 代表将每个微粒推向 pbest 和 gbest 位置的统计加速项的权重。低的值允许微粒在被拉回来之前可以在目标区域外徘徊，而高的值导致微粒突然的冲向或者越过目标区域。

如果没有后两部分，即 c₁ = c₂ = 0，微粒将一直以当前的速度飞行，直到到达边界。由于它只能搜索有限的区域，将很难找到好的解。

如果没有第一部分，即 w = 0，则速度只取决于微粒当前的位置和它们历史最好位置 pbest 和 gbest ，速度本身没有记忆性。假设一个微粒位于全局最好位置，它将保持静止。而其它微粒则飞向它本身最好位置 pbest 和全局最好位置 gbest 的加权中心。在这种条件下，微粒群将统计的收缩到当前的全局最好位置，更像一个局部算法。

在加上第一部分后，微粒有扩展搜索空间的趋势，即第一部分有全局搜索的能力。这也使得w的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。

如果没有第二部分，即 c₁ = 0，则微粒没有认知能力，也就是“只有社会（social-only）”的模型。在微粒的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容易陷入局部优值点。

如果没有第三部分，即 c₂ = 0，则微粒之间没有社会信息共享，也就是“只有认知（cognition-only）”的模型。因为个体间没有交互，一个规模为m的群体等价于m个单个微粒的运行。因而得到解的几率非常小。

收敛性

收敛性的数学证明帮助了 PSO 的发展和应用^[4]，但此类分析具有很大的局限性^[5]。为 PSO 加入正交学习后，算法的全局收敛、收敛精度及稳健可靠性都得到了提高^[6]。

外部链接

DMOZ Particle Swarm People （页面存档备份，存于互联网档案馆）
PSO源代码链接（页面存档备份，存于互联网档案馆）
Parameter Estimation of a Pressure Swing Adsorption Model for Air Separation Using Multi-objective Optimisation and Support Vector Regression ModelYang Liu 2013
Automatic calibration of a rapid flood spreading model using multiobjective optimisations （页面存档备份，存于互联网档案馆）-Yang Liu 2013
https://web.archive.org/web/20160507233728/http://userweb.eng.gla.ac.uk/yun.li/ga_demo/（格拉斯哥大学的交互式群体演化在线学习课件 EA_demo，可以帮助读者更好地理解进化及粒群算法，允许用户直接在网页上一代一代地手动运行，以看进化算法是怎样一步一步操作的，亦可在背景中批量运行，以观察算法的收敛和个体是否跳出局部最优）

参考文献

^ ^1.0 ^1.1 Kennedy, J.; Eberhart, R. Particle swarm optimization. Neural Networks, 1995. Proceedings., IEEE International Conference on (IEEE). 1995, 4: 1942–1948. ISBN 0-7803-2768-3. doi:10.1109/ICNN.1995.488968.
^ Zhan, Z-H.; Zhang, J.; Li, Y; Chung, H.S-H. Adaptive Particle Swarm Optimization (PDF). IEEE Transactions on Systems, Man, and Cybernetics. 2009, 39 (6): 1362–1381 [2014-02-02]. doi:10.1109/TSMCB.2009.2015956. （原始内容存档 (PDF)于2017-05-17）.
^ Shen, Meie, Zhan, Zhi-Hui, Chen, Wei-Neng, Gong, Yue-Jiao, Zhang, Jun, and Li, Yun. Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks (PDF). IEEE Transactions on Industrial Electronics. 2014, (March): 1362–1381. doi:10.1109/TIE.2014.2314075. （原始内容 (PDF)存档于2014-10-08）.
^ Clerc, M.; Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation. 2002, 6 (1): 58–73. doi:10.1109/4235.985692.
^ Pedersen, M.E.H.; Chipperfield, A.J. Simplifying particle swarm optimization (PDF). Applied Soft Computing. 2010, 10 (2): 618–628 [2014-02-02]. doi:10.1016/j.asoc.2009.08.029. （原始内容 (PDF)存档于2014-01-24）.
^ Zhan, Z-H.; Zhang, J.; Li, Y; Shi, Y-H. Orthogonal Learning Particle Swarm Optimization (PDF). IEEE Transactions on Evolutionary Computation. 2011, 15 (6): 832–847 [2014-02-02]. doi:10.1109/TEVC.2010.2052054. （原始内容存档 (PDF)于2020-08-06）.

[kennedy07ieee-1] 1.0 ^1.1 Kennedy, J.; Eberhart, R. Particle swarm optimization. Neural Networks, 1995. Proceedings., IEEE International Conference on (IEEE). 1995, 4: 1942–1948. ISBN 0-7803-2768-3. doi:10.1109/ICNN.1995.488968.

[zhan09adaptive-2] Zhan, Z-H.; Zhang, J.; Li, Y; Chung, H.S-H. Adaptive Particle Swarm Optimization (PDF). IEEE Transactions on Systems, Man, and Cybernetics. 2009, 39 (6): 1362–1381 [2014-02-02]. doi:10.1109/TSMCB.2009.2015956. （原始内容存档 (PDF)于2017-05-17）.

[sysu14-3] Shen, Meie, Zhan, Zhi-Hui, Chen, Wei-Neng, Gong, Yue-Jiao, Zhang, Jun, and Li, Yun. Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks (PDF). IEEE Transactions on Industrial Electronics. 2014, (March): 1362–1381. doi:10.1109/TIE.2014.2314075. （原始内容 (PDF)存档于2014-10-08）.

[clerc02explosion-4] Clerc, M.; Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation. 2002, 6 (1): 58–73. doi:10.1109/4235.985692.

[pedersen08simplifying-5] Pedersen, M.E.H.; Chipperfield, A.J. Simplifying particle swarm optimization (PDF). Applied Soft Computing. 2010, 10 (2): 618–628 [2014-02-02]. doi:10.1016/j.asoc.2009.08.029. （原始内容 (PDF)存档于2014-01-24）.

[zhan10OLPSO-6] Zhan, Z-H.; Zhang, J.; Li, Y; Shi, Y-H. Orthogonal Learning Particle Swarm Optimization (PDF). IEEE Transactions on Evolutionary Computation. 2011, 15 (6): 832–847 [2014-02-02]. doi:10.1109/TEVC.2010.2052054. （原始内容存档 (PDF)于2020-08-06）.

[1]

[2]

[3]

[4]

[5]

[6]