algorithm - 粒子群优化如何达到最终解决方案？

Question

我明白每个粒子都是特定函数的解，每个粒子和群体都在不断寻找最佳解。如果在第一次迭代后找到了全局最佳值，并且没有将新粒子添加到混合中，那么循环是否应该退出并且找到的第一个全局最佳值是最合适的解决方案？如果是这种情况，是什么让PSO比仅遍历列表更好。

Answer 1

你的术语有点不对劲。简单 PSO 是对一个向量 x 的搜索，它使某个标量目标函数 E(x) 最小化。它通过创建许多候选向量来做到这一点。称他们为 x_i。这些是“粒子”。它们在位置和变化率（也称为速度）上随机初始化，这与移动粒子的概念一致，即使该粒子可能具有多于 3 个维度。

简单的规则描述了位置和速度如何随时间变化。选择规则使得每个粒子 x_i 趋向于随机地向减少 E(x_i) 的方向移动。

这些规则通常涉及跟踪“迄今为止看到的单个最佳 x_i 值”并进行调整，以便所有粒子通常倾向于随机变化的最佳值。因此，这些粒子像嗡嗡作响的蜜蜂一样蜂拥而至，作为一个群体朝着一个共同目标前进，但随着时间的推移，个体蜜蜂会出现许多偏差，从而导致共同目标发生变化。

不幸的是，一些文献将此目标或迄今为止看到的最佳粒子值称为“全局最小值”。在优化中，全局最小值有不同的含义。全局最小值（当存在“关系”时可能有多个）是 x 的值，它在可能的 x 值的整个域中 - 产生E(x)的唯一最小可能值。

PSO 绝不保证找到全局最小值。实际上，您的问题有点荒谬，因为人们通常永远不知道何时找到了全局最小值。你会怎么做？在大多数问题中，您甚至都不知道 E 的梯度（它给出了将 E 取为较小值的方向，即下坡）。这就是您首先使用 PSO 的原因。如果您知道梯度，您几乎可以肯定使用比 PSO 更快地找到答案的数值技术。如果没有梯度，您甚至无法确定是否找到了局部最小值，更不用说全局最小值了。

相反，您通常可以做的最好的事情是“猜测”何时找到局部最小值。为此，您可以让系统运行，同时观察“迄今为止看到的最佳粒子”的更新频率和更新程度。当更改变得不频繁和/或很小时，您就宣布胜利。

另一种说法是，PSO 用于减少 E(x) 总是好的问题，并且“你会得到你能得到的任何东西”，而不管你是否有信心得到最好的东西。例如，您是沃尔玛，任何可以节省/赚更多钱的商店的定位方式都很有趣。

以所有这些为背景，让我们回顾一下您的具体问题：

如果在第一次迭代后找到了全局最佳值，并且没有将新粒子添加到混合中，那么循环是否应该退出并且找到的第一个全局最佳值是最合适的解决方案？

没有答案，因为无法确定是否找到了全球最佳。这群嗡嗡作响的粒子可能会在下一次迭代或从现在开始的十万亿次迭代中找到新的最佳状态。你很少知道。

如果是这种情况，是什么让 PSO 比仅遍历列表更好？

我不完全理解你的意思。PSO 正在模仿成群的生物实体（如虫子和畜群动物）的行为方式。以这种方式，它类似于遗传算法、模拟退火、神经网络和其他使用以下逻辑的解决方案查找器系列：自然，无论是物理的还是生物的，都有已知良好的优化过程。让我们利用它们并尽最大努力在软件中模拟它们。我们正在利用自然比我们自己设计的任何简单迭代做得更好。

Answer 2

只是为了在回答中添加一些内容，您的问题似乎与“我什么时候应该停止我的 PSO？”这个常见问题有关。每个人在启动 swarm 时都会面临一个问题，因为（如上所述）你永远不知道你是否达到了全局最佳解决方案（除了非常具体的目标函数）。

大多数 PSO 实现中已经存在的常用技巧： 1- 仅限制迭代次数，因为处理时间总是有限制的（并且您可以通过自我评估评估所花费的时间来实现不同的方法将迭代次数转换为时间限制目标）。2-当优化的进展开始变得微不足道时停止算法。

Answer 3

给定一个函数，粒子群试图找到将最小化（或有时最大化，取决于问题）该函数值的解（向量）。

如果您碰巧知道解决方案的最小值（假设为了论证，它是 0）并且如果您有幸生成在第一步中为您提供 0 的解决方案，那么您可以退出循环并停止算法。

那就是说；您在初始化时随机生成该解决方案的概率非常小。

在大多数实际情况下，当您想使用 PSO 求解时，您很可能不知道最小值，因此您将无法将其用作停止条件。

粒子群优化，优化过程不是随机初始步骤发生的方式，而是通过以社会和认知组件确定的速度调整初始解决方案而发生的修改。

• 社会组件由当前评估的群体全局最佳解决方案组成
• 认知组件由当前解决方案看到的最佳位置组成。

这种调整将使粒子沿着全局最佳和当前最佳之间的一条线移动 - 希望它们之间有更好的解决方案。

我希望以某种方式回答这个问题