小鸟搜索

发布时间：2023-06-13 作者：admin 来源：文学

小鸟搜索

2023年3月18日发(作者：工伤认定申请表怎么填)

混沌粒⼦群算法原理_优化粒⼦群算法介绍

张浩然

责任编辑：苏向阳

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

编者按：

粒⼦群算法是计算数学中⽤于解决最优化的搜索算法，也是最为经典的智能算法之⼀。应⽤主要是在⼯程和计算机科学还有⾏为管理研究科

学⾥⾯。通过阅读这篇⽂章，你将了解粒⼦群算法的概念，优缺点以及发展⽅向。

1、简介

粒⼦群算法(ParticleSwarmOptimization,简称PSO)是1995年Eberhart博⼠和Kennedy博⼠⼀起提出的[1]。粒⼦群算法是通过模拟鸟

群捕⾷⾏为设计的⼀种群智能算法。区域内有⼤⼤⼩⼩不同的⾷物源，鸟群的任务是找到最⼤的⾷物源(全局最优解)，鸟群的任务是找到这

个⾷物源。鸟群在整个搜寻的过程中，通过相互传递各⾃位置的信息，让其他的鸟知道⾷物源的位置最终，整个鸟群都能聚集在⾷物源周

围，即我们所说的找到了最优解，问题收敛。学者受⾃然界的启发开发了诸多类似智能算法，如蚁群算法[2]、布⾕鸟搜索算法[3]、鱼群算

法[4]、捕猎算法等等[5]。有兴趣的读者可以深⼊了解⼀下。

2、算法策略

粒⼦群算法的⽬标是使所有粒⼦在多维超体(multi-dimensionalhyper-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、评价标准

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]Anewoptimizerusingparticleswarmtheory,in:MHS'dingsoftheSixthInternationalSymposiumonMicro

MachineandHumanScience,Ieee,1995,pp.39-43.

[2]Antcolonyoptimization:anewmeta-heuristic,in:Proceedingsofthe1999congressonevolutionarycomputation-

CEC99(.99TH8406),IEEE,1999,pp.1470-1477.

[3]CuckoosearchviaLévyflights,in:2009WorldCongressonNature&BiologicallyInspiredComputing(NaBIC),IEEE,

2009,pp.210-214.

[4]Anoptimizingmethodbasedonautonomousanimats:fish-swarmalgorithm,SystemsEngineering-Theory&Practice,22

(2002)32-38.

[5]Anovelparticleswarmoptimizationbasedonprey–predatorrelationship,AppliedSoftComputing,68(2018)202-218.