使用粒子群优化进行适当编码
Appropriate encoding using Particle Swarm Optimization
问题
我一直在研究粒子群优化，所以我说我会把它付诸实践。
我要解决的问题是平衡分区问题 - 或者简单地简化为子集和问题（其中和是所有数字的一半）。
似乎更新粒子速度的通用公式是
不过这个问题我就不多说了。
由于没有针对子集和问题的在线 PSO 尝试，我转而查看了旅行商问题。
他们更新速度的方法涉及获取一组访问过的城镇，从另一个城镇中减去一个城镇，然后对其进行一些操作。
我发现它与上面的公式没有关系。
我的方法
所以我放弃了公式并尝试了自己的方法来解决子集和问题。
我基本上使用 gbest 和 pbest 来确定将特定元素删除或添加到子集中的概率。
即 - 如果我的问题 space 是 [1,2,3,4,5]（目标是 7 或 8），并且我当前的粒子（子集）有 [1,None,3,None,None] , 而 gbest 是 [None,2,3,None,None] 那么有更高的概率保留 3, 添加 2 和删除 1, 基于 gbest
我可以 post 编码，但认为没有必要，你懂的（我正在使用 python 顺便说一句 - 因此 None）。
基本上，这在一定程度上奏效了，我找到了不错的解决方案，但在处理较大的数据集和值时速度非常慢。
我的问题
我是否以巧妙的方式对问题进行编码并更新粒子 "velocities"？
有没有办法确定这是否会正确收敛？
是否有我可以用来学习如何为特定问题 space 创建收敛 "update" 公式的资源？
非常感谢！
编码
是的，你的编码是正确的：你的每个位图（这实际上是你的 5 元素列表）是一个粒子。
概念
你的方程的概念性问题是因为你的问题 space 是一个离散的点阵图，它不适合立即更新步骤。例如，如果你想通过调整你的学习率来获得更细的粒度，你通常会减少一些小的因素（比如，3）。在这个 space 中，步数只有原来的 1/3 是什么意思？这就是你遇到问题的原因。
我看到的主要可能性是创建 3 倍多的粒子，然后将转换概率全部除以 3。这仍然不能很好地满足，但它确实模拟了这个过程。
离散步骤
如果您有一个非常大的图表，其中高速可以在一步中为您提供数十个转换，您可以使用更平滑的距离（损失或错误）函数来指导您的模型。这么小的东西，任何两个位置之间的距离不超过 5 步，很难用这样的概念来工作。
相反，您使用基于到解决方案的估计距离的误差函数。最简单的方法是用较近的 7 或 8 减去粒子的总数。更难的方法是根据该差异和粒子元素 "in play".
来估计距离
收敛性证明
是的，有办法做到这一点，但它需要一些功能分析。通常，您想证明误差函数在粒子 space 上是凸的。换句话说，你必须证明你的误差函数是一个可靠的距离度量，至少就相对位置而言（即证明较低的误差 does 意味着你是更接近解决方案）。
正在创建更新公式
不，这是一个启发式领域，基于由粒子坐标、误差函数和运动特征定义的问题形状 space。
额外推荐
您当前允许的转换是 "add" 和 "delete" 元素。
包括 "swap elements"：用一名在场成员交换一名缺席成员。这将允许平凡误差函数为您定义一个凸 space，您将在很短的时间内收敛。
问题
我一直在研究粒子群优化，所以我说我会把它付诸实践。
我要解决的问题是平衡分区问题 - 或者简单地简化为子集和问题（其中和是所有数字的一半）。
似乎更新粒子速度的通用公式是
不过这个问题我就不多说了。
由于没有针对子集和问题的在线 PSO 尝试，我转而查看了旅行商问题。
他们更新速度的方法涉及获取一组访问过的城镇，从另一个城镇中减去一个城镇，然后对其进行一些操作。
我发现它与上面的公式没有关系。
我的方法
所以我放弃了公式并尝试了自己的方法来解决子集和问题。
我基本上使用 gbest 和 pbest 来确定将特定元素删除或添加到子集中的概率。
即 - 如果我的问题 space 是 [1,2,3,4,5]（目标是 7 或 8），并且我当前的粒子（子集）有 [1,None,3,None,None] , 而 gbest 是 [None,2,3,None,None] 那么有更高的概率保留 3, 添加 2 和删除 1, 基于 gbest
我可以 post 编码，但认为没有必要，你懂的（我正在使用 python 顺便说一句 - 因此 None）。
基本上，这在一定程度上奏效了，我找到了不错的解决方案，但在处理较大的数据集和值时速度非常慢。
我的问题
我是否以巧妙的方式对问题进行编码并更新粒子 "velocities"？
有没有办法确定这是否会正确收敛？
是否有我可以用来学习如何为特定问题 space 创建收敛 "update" 公式的资源？
非常感谢！
编码
是的，你的编码是正确的：你的每个位图（这实际上是你的 5 元素列表）是一个粒子。
概念
你的方程的概念性问题是因为你的问题 space 是一个离散的点阵图，它不适合立即更新步骤。例如，如果你想通过调整你的学习率来获得更细的粒度，你通常会减少一些小的因素（比如，3）。在这个 space 中，步数只有原来的 1/3 是什么意思？这就是你遇到问题的原因。
我看到的主要可能性是创建 3 倍多的粒子，然后将转换概率全部除以 3。这仍然不能很好地满足，但它确实模拟了这个过程。
离散步骤
如果您有一个非常大的图表，其中高速可以在一步中为您提供数十个转换，您可以使用更平滑的距离（损失或错误）函数来指导您的模型。这么小的东西，任何两个位置之间的距离不超过 5 步，很难用这样的概念来工作。
相反，您使用基于到解决方案的估计距离的误差函数。最简单的方法是用较近的 7 或 8 减去粒子的总数。更难的方法是根据该差异和粒子元素 "in play".
来估计距离收敛性证明
是的，有办法做到这一点，但它需要一些功能分析。通常，您想证明误差函数在粒子 space 上是凸的。换句话说，你必须证明你的误差函数是一个可靠的距离度量，至少就相对位置而言（即证明较低的误差 does 意味着你是更接近解决方案）。
正在创建更新公式
不，这是一个启发式领域，基于由粒子坐标、误差函数和运动特征定义的问题形状 space。
额外推荐
您当前允许的转换是 "add" 和 "delete" 元素。 包括 "swap elements"：用一名在场成员交换一名缺席成员。这将允许平凡误差函数为您定义一个凸 space，您将在很短的时间内收敛。