python - 使用粒子群优化的适当编码

Question

问题

我一直在对粒子群优化进行一些研究，所以我说我会对其进行测试。

我要解决的问题是平衡分区问题 - 或者简单地简化为子集和问题（总和是所有数字的一半）。

似乎更新粒子速度的通用公式是

但我不会为这个问题详细介绍。

由于没有针对子集总和问题的 PSO 在线尝试，我改为查看旅行商问题。

他们是更新速度的方法，包括获取一组访问过的城镇，从另一个中减去一个并对其进行一些操作。

我发现这与上面的公式没有关系。

我的方法

所以我放弃了这个公式并尝试了我自己的方法来解决子集和问题。

我基本上使用gbestandpbest来确定删除或添加特定元素到子集的概率。

即-如果我的问题空间是[1,2,3,4,5]（目标是7或8），并且我当前的粒子（子集）具有[1,None,3,None,None]，并且gbest是，则保留，添加和删除[None,2,3,None,None]的概率更高，基于321gbest

我可以发布代码，但认为没有必要，你明白了（我正在使用 python btw - 因此None）。

所以基本上，这在一定程度上有效，我得到了不错的解决方案，但在更大的数据集和值上它非常慢。

我的问题

我是否以智能的方式对问题进行编码并更新粒子“速度”？

有没有办法确定这是否会正确收敛？

有没有我可以用来学习如何为特定问题空间创建收敛“更新”公式的资源？

提前非常感谢！

Answer 1

编码

是的，您正确地对此进行了编码：您的每个位图（实际上就是您的 5 元素列表）都是一个粒子。

概念

你对方程的概念问题是因为你的问题空间是一个离散的格图，它不能立即用于更新步骤。例如，如果您想通过调整学习率来获得更精细的粒度，您通常会将其减少一些小因素（例如 3）。在这个空间中，仅采取 1/3 大的步数意味着什么？这就是你有问题的原因。

我看到的主要可能性是创建 3 倍多的粒子，然后将过渡概率全部除以 3。这仍然不能很好地满足，但它确实可以很好地模拟这个过程。

离散步骤

如果您有一个非常大的图表，其中高速可以在一个步骤中为您提供数十个转换，您可以利用更平滑的距离（损失或错误）函数来指导您的模型。对于这么小的东西，任何两个位置之间的距离不超过 5 步，很难使用这样的概念。

相反，您可以根据到解的估计距离使用误差函数。最简单的方法是从 7 或 8 中的较近者中减去粒子的总数。更难的是根据该差异和“在场”的粒子元素来估计距离。

收敛证明

是的，有办法做到这一点，但它需要一些功能分析。通常，您希望证明误差函数在粒子空间上是凸的。换句话说，您必须证明您的误差函数是一个可靠的距离度量，至少就相对位置而言（即证明较低的误差确实意味着您更接近解决方案）。

创建更新公式

不，这是一个启发式场，基于由粒子坐标、误差函数和运动特征定义的问题空间的形状。

额外推荐

您当前允许的转换是“添加”和“删除”元素。包括“交换元素”：用一个在场的成员换一个缺席的成员。这将允许微不足道的误差函数为您定义一个凸空间，并且您将在很短的时间内收敛。