粒子群算法在编码中的应用

Question

问题

我一直在做一些粒子群优化的研究，所以我说我会把它测试一下。

我试图解决的问题是平衡划分问题--或者简单地简化为子集和问题(其中和是所有数字的一半)。

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

​

​

但对于这个问题，我不会说太多的细节。

由于没有粒子群算法试图在线解决子集和问题，所以我转而研究了旅行推销员问题。

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

我看不出这和上面的公式有什么关系。

My Approach

因此，我放弃了公式，并尝试了我自己的方法，子集和问题。

我基本上使用gbest和pbest来确定将特定元素移除或添加到子集的概率。

也就是说，如果我的问题空间是[1,2,3,4,5] (目标是7或8)，而我当前的粒子(子集)有[1,None,3,None,None]，而gbest是[None,2,3,None,None]，那么基于gbest保持3、添加2和消除1的概率更高。

我可以发布代码，但不认为这是必要的，您可以理解(我使用python因此使用None)。

因此，基本上，这在某种程度上起了作用，我找到了不错的解决方案，但在更大的数据集和值上进展非常缓慢。

我的问题

我是否对问题进行编码，并以一种聪明的方式更新粒子“速度”？

是否有一种方法可以确定这是否会正确地收敛？

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

提前谢谢！

Answer 1

编码

是的，你的编码是正确的:你的每个位图(这实际上就是你的5元素列表)是一个粒子。

概念

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

我看到的主要可能性是创造出3x的粒子，但是转移概率都除以3。这仍然不能很好地满足，但是它确实很好地模拟了这个过程。

离散步骤

如果您有一个非常大的图，其中一个高速可以在一个步骤中给您几十个过渡，您可以使用一个更平滑的距离(损失或错误)函数来指导您的模型。对于这么小的东西，在任何两个位置之间只有5个步骤，很难使用这样的概念。

相反，您可以根据与解决方案的估计距离使用错误函数。最简单的方法是从7或8附近减去粒子的总数，更难的是根据这一差异和粒子元素“发挥”来估计距离。

收敛性的证明

是的，有一个方法，但它需要一些功能分析。一般来说，你要证明误差函数在粒子空间上是凸的。换句话说，您必须证明您的错误函数是可靠的距离度量，至少就相对位置而言是如此(即证明较低的误差确实意味着您更接近解决方案)。

创建更新公式

不，这是一个启发式的领域，根据问题空间的形状定义的粒子坐标，误差函数，和运动特性。

额外推荐

您当前允许的转换是“添加”和“删除”元素。其中包括“交换元素”：用一个现职成员换一个缺席成员。这将允许琐碎的错误函数为您定义一个凸空间，您将在很短的时间内收敛。