如何直观形象地理解粒子群算法？

xiaozongpeng · 发表于 2021-12-1 13:32

求指导，最近我在研究启发式算法关注者
297

被浏览
252,369

关注问题写回答
邀请回答好问题 5
添加评论
分享

<div class="Question-main"><div class="Question-mainColumn"><div id="QuestionAnswers-answers" class="QuestionAnswers-answers" data-zop-feedlistmap="0,0,1,0"><div class="Card AnswersNavWrapper"><div class="ListShortcut"><div class="List">13 个回答

默认排序

<div class="" role="list"><div class="List-item" tabindex="0"><div class="ContentItem AnswerItem" data-za-index="0" data-zop="{&quot;authorName&quot;:&quot;运筹OR帷幄&quot;,&quot;itemId&quot;:666511722,&quot;title&quot;:&quot;如何直观形象地理解粒子群算法？&quot;,&quot;type&quot;:&quot;answer&quot;}" name="666511722" itemProp="acceptedAnswer" itemType="http://schema.org/Answer" itemscope="">运筹OR帷幄
已认证账号

178 人赞同了该回答

<div class="RichContent RichContent--unescapable"><div class="RichContent-inner">粒子群算法是计算数学中用于解决最优化的搜索算法，也是最为经典的智能算法之一。应用主要是在工程和计算机科学还有行为管理研究科学里面。
阅读下面的回答，可以了解到粒子群算法的概念，优缺点以及发展方向。

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库和评价计算方法（<span class="invisible">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&#39;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.
该回答改编自『运筹OR帷幄』原创文章优化 | 粒子群算法介绍
原文作者：张浩然，获得更多信息，欢迎阅读原文

ainatipen · 发表于 2021-12-1 13:38

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

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&#39;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.
该回答改编自『运筹OR帷幄』原创文章优化 | 粒子群算法介绍
原文作者：张浩然，获得更多信息，欢迎阅读原文

xiaozongpeng · 发表于 2021-12-1 13:38

粒子群优化算法（Particle Swarm Optimization，简称PSO）, 是1995年Eberhart博士和Kennedy博士一起提出的，它是源于对鸟群捕食行为的研究。粒子群优化算法的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。
当然这是一种比较正式的说法，对于我们这些数模小白来说肯定希望有一种更加直观形象的解释。
我们不妨假设自己是一只身处鸟群中的鸟，现在要跟随头领去森林里找食物，我们每一只鸟都知道自己离食物的距离，却又不知道食物在哪个方向，
所以，我们在森林里漫无目地的飞着，每隔一段时间，大家会在微信群里共享一次各自与食物的距离。然后鸟A发现自己与食物的距离是5公里，而群里鸟Z距离食物最近，只有50米的距离。鸟A当机立断，在群里说：“我要去那看看！”然后一呼百应，鸟B、鸟C等都往鸟Z方向飞去，在鸟Z的周围寻找食物。
就这样，本来大家都在沿着自己的方向飞，现在都要向鸟Z的位置靠拢，所以大家需要修改自己的飞行速度和方向。但是，当所有鸟儿准备调整自己的飞行轨迹时，鸟H突然想到：虽然现在鸟Z离食物只有50米，但是自己曾经路过点P，那个位置离食物只有40米，所以它不知道自己是应该往点P方向还是往鸟Z的位置飞去。鸟H就把自己的纠结发到了微信群里，然后大家一致决定，还是两者平衡一下，对两个位置进行矢量相加，所以大家共同商量出了速度更新公式

其中，c1和c2被称为社会学习因子和个体学习因子。在速度更新公式之后，鸟儿自然也就知道位置更新公式。
纸上得来终觉浅，绝知此事要躬行。
下面，我们从一个例子来看粒子群算法的具体应用。
已知：

求y的最小值。
首先，我们要确定鸟群在哪片森林里寻找食物，也就是我们在优化问题中所说的可行域，在这里，我们取可行域为

因为鸟群在觅食环节之处可以认为其在森林中是随机分布的，因此我们在初始时刻将50个粒子随机撒入可行域中，然后计算其目标函数值，所有粒子向着目标函数值最小的点移动，我们可以简单画一个算法的基本流程。

第一步，我们设定粒子规模为50个，社会学习因子和个体学习因子为2，最大迭代次数为800。
第二步，在可行域内随机给定粒子位置。

第三步，计算目标函数值，并进行速度和位置更新。

当粒子满足终止条件时，跳出循环输出最优解，在迭代过程中，目标函数是这样变化的

算法在迭代30次后跳出循环，输出最优解为[0.0202，0.0426]，此时目标函数值为

因为我们选用的例子为二次型规划，显然最优解为[0，0]，最优值为0。
最后，我们用一个三维动画来展示一下粒子群算法的寻优过程。

源程序可以在公众号”数学建模andMATLAB“中回复粒子群算法，下载哈~

fwalker · 发表于 2021-12-1 13:42

昨天正好写了篇博客，来回答一下 ()
其实觉得学习一种算法最好的方法是实践，安利一下我的博客哈哈，里面有用粒子群算法解决简单函数极值问题: 粒子群算法实践算函数极值
-------------------------------------------------- 我是分割线------------------------------------------------
好啦，正文如下！
粒子群算法是模拟鸟群蜂群的觅食行为的一种算法。
基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。
试着想一下一群鸟在寻找食物，在这个区域中只有一只虫子，所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远，同时它们知道离食物最近的鸟的位置。想一下这时候会发生什么？
鸟A：哈哈哈原来虫子离我最近！
鸟B,C,D：我得赶紧往 A 那里过去看看！同时各只鸟在位置不停变化时候离食物的距离也不断变化，所以一定有过离食物最近的位置，这也是它们的一个参考。
鸟某某：我刚刚的位置好像靠近了食物，我得往那里靠近！综上，影响鸟的运动状态变化有下面两个因素：

离食物最近的鸟的位置
自己之前达到过的离食物最近的位置

而鸟每次的位置变化除了考虑上面两个因素还有一个因素: 惯性！
所以考虑这三个因素，位置变化量 v 的公式如下：

可以预见的是，经过不断的调整，鸟群会向食物方向聚集，达到目标。
这就是粒子群算法的大体思想了！

acecase · 发表于 2021-12-1 13:45

想要直观形象地理解粒子群算法，莫过于理解下面这个图了

这个图是一个粒子群算法结果的可视化图。（算法来自 scikit-opt）
图中，每个粒子自身的历史最优是一个引力源，全局历史最优是第二个引力源。
迭代过程模拟了现实中大量小球的物理规则。
来回震荡寻到最优。

gif动画老是崩掉，再传个视频
（红圈是非线性约束）
代码见于： https://github.com/guofei9987/scikit-opt/blob/master/examples/demo_pso_ani.py
无约束的：
参考文献：
<a href="http://link.zhihu.com/?target=https%3A//github.com/guofei9987/scikit-opt" class=" wrap external" target="_blank" rel="nofollow noreferrer">scikit-opt

kirin77 · 发表于 2021-12-1 13:48

一图胜千言，我这里通过最直观的方式讲一下PSO算法吧。首先，我们要明确，任何优化问题的核心是找到最优值，例如如果我们想要求取二次函数的最小值，那么二次函数谷底的位置就是这个二次函数的最优值。

如果我们采用传统的优化方法（梯度法），对于一个已知解析表达式的二次函数，我们可以求其一阶梯度，并沿着梯度方向反方向移动控制参数，最终就可以达到最优点。

但是很多时候，我们无法知道目标函数的解析表达式（黑盒优化问题），这时候我们就可以采用一些启发式方法去近似梯度方向。例如，我们可以让历史最优点位置 $g_{best}$ 减去当前点位置  ，这样得到的向量  如下图所示。

从图中可以看出，尽管在缺乏解析表达式的情况下，我们无法精确计算目标函数的梯度，但是我们依然可以根据当前点和最佳点的位置关系，模拟出一个近似梯度。利用该近似梯度，我们也可以最终求到最优值。
此外，这里需要指出的是，尽管图中只标明了一个点，但是PSO算法是运行在种群上的。如果整个种群只有一个点的话，这时候的全局最优值和当前值是完全重合的，即 $(g_{best}-x)=0$ 。
讲到这里，对于演化算法领域有所了解的同学可能就会发现，上述过程就是差分演化算法的核心思想，而对于差分演化更新公式 $x'=x+F*(a-b)$ （其中F为学习率，a,b为任意两点），上述过程就是这个公式的一个变体，即 $x'=x+F*(g_{best}-x)$ 。
在这个例子中，我们使用的二次函数是一个凸函数，因此梯度法或者近似梯度均可以求得最优值。但是很多时候我们的目标函数是一个复杂的非凸函数（例如神经网络参数优化），那么这时候上述方法就不再适用，这也就引出了这篇答案的主题-粒子群算法。
对于下面这样一个非凸函数，可以明显发现存在多个局部最小值，而这些最小值会导致传统的梯度法陷入局部最优解。为了解决这个问题，我们引入了更多的梯度方向信息并期待通过结合个体方向信息和种群方向信息，最终实现全局优化。具体来说，粒子群算法引入了三个方向向量，分别为惯性动量  ，个体方向信息  和种群方向信息  ，示例图如下图所示。

首先我们来看一下惯性动量  ，该动量的作用是保留一定的梯度方向惯性，避免卡在局部最优值。实际上动量这个概念不仅仅是粒子群算法中存在，在梯度法中也是存在的。因此，这里我简单介绍一下动量的原理，具体详情可以参考一些梯度法的资料。

这里举了一个简单的例子，从图中可以看出，传统梯度法的方向是指向局部谷底的，这样会导致产生局部最优解。而这时候，如果我们让控制点具有一定的方向惯性，即继承前几步的梯度方向，那么就有可能跳出局部最优。

关于种群方向信息，我们刚刚已经详细阐述过了，其作用是计算近似梯度。但是如果我们观察上图这样一种情况，就会发现种群方向信息实际上会将控制点向左移动到一个局部最优的位置，这显然不是我们所希望的。针对这个问题，刚刚提到的惯性动量可以在一定程度上缓解这个问题。为了进一步缓解这个问题，PSO算法的设计者选择使用个体方向信息  作为辅助梯度方向信息，用以指导控制点  的移动。从图中可以看出，尽管种群方向  指向了错误的当前局部最优方向，个体方向  可以指导控制点  避免卡入局部最优。
综上所述，我们最终将三个方向向量相加，分别采用不同的控制权重 $w_1,w_2,w_3$ ，就得到了PSO的速度公式。
$v=w_1*v_{old}+w_2*(p_{best}-x)+w_3*(g_{best}-x)$
而利用该速度公式（近似梯度信息），我们就可以对控制点  进行更新，从而得到新的控制点 $x'$ ，即 $x'=x+v$ 。

ainatipen · 发表于 2021-12-1 13:54

最近我也一直在琢磨这类算法，我感觉学习算法最好的途径是有个总体认识后看一个简单例子的实现代码，一味的用很形象的解释不能解决心中所有的疑问，毕竟有句话说的好：“纸上得来终觉浅，绝知此事要躬行”，看到一个博客专门有一系列粒子群的文章，还有对应的matlab代码，感觉学起来挺有帮助的：
粒子群算法研究 - niuyongjie的专栏 - CSDN博客
粒子群算法工具箱-CSDN下载
另外还有一个博客有一系列文章是讲此系列所有算法的，什么遗传算法啦、蚁群算法啦，反正就是常听到的那几个，你听过的有了，没听过的也有，感觉也不错的：
智能优化算法 - ZCC的专栏 - CSDN博客

另外再谈一点看法：此类算法都可以求函数极值（或近似的极值），当然最关键的还是为了求解NP问题，所以可以先找一个包括多极值的函数先试着求一下最大（小）值，然后再试着求一下TSP（travelling salesman problem ）问题，到此应该就可以掌握一个算法进而去解决自己的问题了~

RecursiveFrog · 发表于 2021-12-1 14:00

理解粒子群可以从粒子运动的牛顿定律开始：
1。首先把离散粒子群算法对应成连续时间的微分方程。
2。找到里面对应位置二阶导数的项（即加速度），找到对应的力（摩擦力、全局最优的作用力，本个体历史最优的作用力）
这就是粒子群的全部物理意义。
当然，也可以先从简单地更直观的智能优化算法研究起，毕竟单个体的情形要比多个体群体优化要简单容易理解很多，比如先找一个最简单的算法看懂用会作为起点，弄清楚一个再由点及面弄清楚其他一些类似算法，到时候你就是专家了。最简单直观的启发式算法莫过于天牛须搜索算法（BAS），可以以此切入

jquave · 发表于 2021-12-1 14:05

懒人啊～～～
准确来说pso，叫元启发式算法，是一种通用的算法框架。
pso算法是仿真鸟群觅食。也就是说，这是个多解迭代的过程，和模拟退火这种单解迭代的区别就在于此。
pso算法的本身的精华也就在于那两个公式：
速度更新公式
位置更新公式
速度更新的本质是：看别的解有哪些优越的东西值得当前解去学习，将那些优秀的东西提取出来。（1）
位置更新的本质就是：让当前解去学习提取出来的别的解的优秀之处，（2）
让后上（1）（2）的过程迭代，在这过程中，每一只鸟要记录自己的历史最好成绩，另外记录全局最优的那只鸟的位置，不断根据这些比当前解好的部分去微调，直到算法结束。

做pso，难点在于结合那两个公式，建立自己问题独特的数据结构。

franciscochonge · 发表于 2021-12-1 14:13

每一本粒子群算法的书里面，一开始都会举这个例子：PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。

		自动登录	找回密码
密码			立即注册

如何直观形象地理解粒子群算法？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源