当前位置：首页 > news >正文

粒子群优化

news 2026/3/27 4:50:08

原文：towardsdatascience.com/particle-swarm-optimization-b869231c57fe

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/f40eef1690bc8cb84e9abd82280e7db3.png

由 James Wainscoat 在 Unsplash 拍摄的照片

无论我们处理的是机器学习、运筹学还是其他数值领域，我们都必须完成的共同任务是优化函数。根据领域不同，一些常用的方法应运而生：

在机器学习中，当训练神经网络时，我们通常使用梯度下降法。这是因为我们处理的是可微分的函数（至少在几乎所有的点上都是可微分的 – 见 ReLU）。
在运筹学中，我们经常处理可以用线性（或凸）规划解决的线性（或凸）优化问题。

如果我们能应用这些方法，那总是很棒的。然而，对于优化一般函数，即所谓的黑盒优化，我们必须求助于其他技术。其中特别有趣的一种是所谓的粒子群优化，在这篇文章中，我将向你展示它是如何工作的以及如何实现它。

注意，这些算法并不总是给出最佳解，因为它们是高度随机和启发式算法。尽管如此，它仍然是你工具箱中的一个很好的技术，当你遇到难以优化的函数时，你应该尝试使用它！

在 1995 年，Kennedy 和 Eberhart 在他们同名的论文中介绍了粒子群优化。作者从社会生物学中找到了类比，提出集体运动，如鸟群，可以让每个成员从整个群体的经验中受益。我们将在下一部分看到这意味着什么。

让我们假设你想最小化一个二维变量的函数，例如，f(x,y) = _x_² + _y_²。当然，我们知道解是 (0, 0)，值为 0，我们的算法也应该找到这个解。如果我们连这一点都做不到，我们就知道我们完全做错了。

静态粒子

我们首先随机初始化大量潜在解，即二维点 (xᵢ,yᵢ)，其中i= 1, …,N。这些点被称为粒子（鸟类），点的集合是群体（鸟群）。对于每个粒子 (xᵢ,yᵢ)，我们可以计算函数值f(xᵢ,yᵢ)。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/09bf6773d3b821de1b4ff6de4a465f27.png

中间的红色十字是我们要尝试找到的最小值。在白色中，你可以看到 100 个随机点。图片由作者提供。

我们可以在这里停止，并输出具有最低f值的粒子。这将是一个随机搜索，在低维度中可能有效，但在高维度中通常效果较差。

推动它们！

但我们不想就此止步！相反，我们通过给每个粒子一个随机的轻微推动来启动一个动态系统。粒子应该直线飞行，就像在无重力的外太空一样。我们可以检查几个时间步长内所有粒子的位置，然后报告我们见过的最低的f值。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5db955afe2034620fff2c8d9aa5f47b4.png

每个粒子都会在某个方向上受到推动。它们将永远跟随这个方向。图片由作者提供。

这基本上是一个随机搜索，但我们稍微改变一下随机点，这样它们就可以四处飞翔，为我们提供更广泛的搜索空间。你可以这样实现：

deff(x):# function to minimizereturnx[0]**2+x[1]**2defeasy_push(dimension,swarm_size,n_steps):x=np.random.normal(loc=0,scale=3,size=(dimension,swarm_size))# initial swarmv=np.random.normal(loc=0,scale=1,size=(dimension,swarm_size))# initial velocities (directions)best_position=x[:,[f(x).argmin()]]best_value=f(x).min()forstepinrange(n_steps):x=x+v# update positions according to the push directionnew_candidate=f(x).min()ifnew_candidate<best_value:best_value=new_candidate best_position=x[:,[f(x).argmin()]]returnbest_positionprint(easy_push(dimension=2,swarm_size=100,n_steps=100))# use function

在矩阵x中，每一列是粒子的位置。同样，其他矩阵v的每一列代表具有相同索引的相应粒子的方向向量。代码高度向量化，因此性能更好。否则，我们不得不在群体中的所有粒子上写一个 for 循环。

虽然这比随机搜索要好一些，但粒子仍然相当愚蠢——它们只沿直线移动，我们只能希望其中之一能接近最小值。

所以到目前为止，还没有形成群体。只是一群自私的鸟直线飞行，做它们的事情。

添加吸引力

粒子群优化有很多变体，但在每个变体中，粒子都变得更聪明一些：

它们获得了一种记忆：每个粒子都知道迄今为止它找到的最佳位置。
它们意识到群体：每个粒子都知道迄今为止任何粒子找到的最佳位置。

现在，高级思想是粒子不仅直线飞行，而且朝向

它们已知的最著名的位置——局部最佳位置——，但还
群体最著名的地点——全局最佳位置。

你可以通过在每一步改变方向来实现这个想法。在代码中，之前的方向v在循环的每次迭代中保持不变。我们只设置一次，然后更新x = x + v。现在，我们想更新v，例如使用以下公式：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/11558b1640aae5412bdd55ad452ef21c.png

方向改变公式。图片由作者提供。

用话来说：下一时间步的方向由三个组成部分组成：

一个缩放（通常是更短，即，0 <w< 1）的旧方向，
一个认知方向，指向每个粒子迄今为止找到的局部最佳解，以及
一个社会方向，指向整个群体迄今为止找到的全局最佳解。

这意味着每个粒子会随着时间的推移而减速，移动到它曾经见过的最佳解，同时也移动到群体曾经见过的最佳解。

你也可以这样表达：每个粒子被它自己曾经见过的最佳位置吸引，同时也被全局最佳位置吸引。最终，我们的粒子将表现出这样的行为：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/339a3ffbf0aefe5b382e6f5511a62e19.png

粒子移动到它们自己已知最佳位置，同时也移动到群体已知最佳位置。图片由作者提供。

这里是优化二维中更困难的Rastrigin 函数的另一个动画：

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/037bd864e22cec2f3f059f2bae02ad4b.png

图片由作者提供。

这个函数有许多局部最小值，这是训练神经网络时常见的问题。尽管如此，我们的简单算法在这里似乎效果很好。一些粒子卡在了错误的局部最小值中，但许多粒子也聚集在中间的全局最小值周围，这对于得到好的结果已经足够了。

实现

这看起来很复杂，但如果已经理解了自私的鸟类的代码，代码本身也很简单。下面是代码：

defsimple_pso(dimension,swarm_size,n_steps,w,c_cognitive,c_social):x=np.random.normal(loc=0,scale=3,size=(dimension,swarm_size))v=np.random.normal(loc=0,scale=1,size=(dimension,swarm_size))best_position_particle=x# in the beginning, the best position known for each article is its initial positionforstepinrange(n_steps):best_value_particle=f(best_position_particle)# the corresponding function values for the best known positionsbest_position_global=x[:,[best_value_particle.argmin()]]# global best position that attracts all particlesr=np.random.random(2)# this is new, see belowx=x+v# same as beforev=w*v+c_cognitive*r[0]*(best_position_particle-x)+c_social*r[1]*(best_position_global-x)# the direction change formulaimprovement=f(x)<=best_value_particle best_position_particle[:,improvement]=x[:,improvement]# update each particle's locally best solutionbest_position_global=x[:,[best_value_particle.argmin()]]returnbest_position_globalprint(simple_pso(dimension=2,swarm_size=100,n_steps=100,w=0.8,c_cognitive=0.1,c_social=0.1))