如何直观形象地理解粒子群算法？

LiteralliJeff · 发表于 2021-12-1 14:15

粒子群优化算法（ParticleSwarm Optimization，简称PSO）, 是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。我们可以利用一个有关PSO的经典描述来对PSO算法进行一个直观的描述。设想这么一个场景：一群鸟进行觅食，而远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略，也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。PSO就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。

在PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”，而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitness value），可以将其理解为距离“玉米地”的距离。在每次的迭代中，种群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个种群的粒子就会逐步趋于最优解。

具体的题主可以看看这两个博客：
[Algorithm] 群体智能优化算法之粒子群优化算法粒子群优化算法简介 - 火星十一郎 - 博客园

rustum · 发表于 2021-12-1 14:20

想象下现在你在玩这样一个游戏。找寻一个位置，这个位置是最适合居住的。这个时候你会基于自己当前位置做出决策。而决策过程受多种因素的影响，当你没有外界信息的条件下，你只能根据自己当前前进方向，曾经找到最好位置方向，以及团队中伙伴共享过来最好位置方向共同影响你的寻找方向。每个因素都会影响你的决策，只是或多或少而已，表现为每个因素的权重。把这些因素往公式上套就是粒子群算法的更新过程。选择了前进的方向再次评判现在的位置居住的适用性，再做决策，不断反复。
至于改进，比如你可以放多个种群去不同地方搜索，加入种群间平均适应度这个共享信息这个因素做更新，类似于加入全局信息，这个是我自己写的过程中想到的（逃了！

xiaozongpeng · 发表于 2021-12-1 14:26

粒子群优化算法(Particle Swarm Optimization,简称PSO)是通过模拟鸟群捕食行为设计的一种群智能算法。本文介绍算法原理，R代码实现以及R包实现。

粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解。 PSO的优势在于简单容易实现并且没有许多参数的调节，广泛应用于函数优化、神经网络训练等领域。
算法原理

介绍

粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟，粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，并将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解，粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。下面的动图很形象地展示了PSO算法的过程：

公式

PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个极值(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。
速度更新公式
$V_i=\omega\times V_i+c_1\times rand()\times (pbest_i-X_i)+c_2\times rand()\times (gbest-X_i) \\$
其中:
$\omega$ 为惯性因子，数值范围为0到1之间；
$V_i$ 为第i个粒子的速度；
$X_i$ 为第i个粒子的位置；
$c_1$ 和 $c_2$ 为学习因子，通常为2；
$rand()$ 为0到1之间的随机数；
$pbest_i$ 为第i个粒子的历史最优位置；
$gbest$ 为粒子群的历史最优位置。
位置更新公式
$X_i=X_i+V_i \\$
流程图

代码实现

用PSO算法解决一个实际的优化问题：
求解 $z=x^2+y^2$ 在 $x,y\in[-10,10]$ 值域范围内的最小值。

函数定义

# 目标函数（x输入长度为2的向量）
fit <- function(x)sum(x^2)
# 值域
lower <- -10
upper <- 10

图像展示

library(plotly)
# 计算函数值矩阵
z <- apply(expand.grid(x=lower:upper,y=lower:upper),1,fit) %>% matrix(ncol = length(lower:upper))
# 3d展示
plot_ly(x=lower:upper,y=lower:upper,z=z) %>% add_surface()

通过图像可知，该函数是一个“碗状”结构，在值域范围内有且只有一个最小值。

粒子群初始化

# 初始粒子数量
n <- 20
# 速度最大值
vmax <- 2
# 惯性因子
w <- 1
# 学习因子
c1 <- c2 <- 2
# 随机数
r1 <- runif(1)
r2 <- runif(1)
# 适应度变化初始值
gBestDelta <- NULL
# 最佳适应度变化阈值
alpha <- 0.0001
# 粒子群迭代次数
iters <- 1000
# 随机位置矩阵 X
X <- data.frame(x=runif(n,-10,10),y=runif(n,-10,10)) %>% as.matrix()
# 随机速度矩阵 V
V <- data.frame(x=runif(n,-vmax,vmax),y=runif(n,-vmax,vmax)) %>% as.matrix()
# pBest初始设置为X
pBest <- X
# gBest初始设置 gBest=min{pBesti}
gBest <- pBest[which.min(apply(pBest,1,fit)),]

粒子群迭代更新

# 结果向量
fitness <- c()
# 迭代
for(j in 1:iters){
  # 粒子群更新
  for(i in 1:n){
# 粒子速度更新
V[i,] <- w*V[i,]+c1*r1*(pBest[i,]-X[i,])+c2*r2*(gBest-X[i,])
# 粒子速度约束（超过最大速度则设置为最大速度）
V[i,V[i,]>vmax] <- vmax
# 粒子位置更新
X[i,] <- X[i,]+V[i,]
# 粒子pBest更新
if(fit(X[i,]) < fit(pBest[i,])) pBest[i,] <- X[i,]
# 粒子群gBest更新(全局解)
if(fit(pBest[i,]) < fit(gBest)){
   gBestDelta <- abs(fit(gBest)-fit(pBest[i,])) # 粒子群适应度变化量
   gBest <- pBest[i,]
}
  }
  # 存储每次迭代的结果
  fitness[j] <- fit(gBest)
  # 达到阈值条件则结束
  if(!is.null(gBestDelta) & gBestDelta < alpha) break
}

输出结果

从计算结果可知，最优解x和y都非常小，约等于0。同时，从图中可以看出，PSO在迭代几十次后，拟合度下降的非常快，之后几乎不再变化，算法很快找到了全局最优解。
print(gBest)
## x y
## 0.010550688 0.009236431
plot(1:length(fitness),fitness,type=&#34;l&#34;,xlab=&#34;iters&#34;,ylab=&#34;fitness&#34;)

R包实现

R中有第三方包实现PSO算法--pso，同样，用该包实现上述优化问题求解。

安装包

install.packages(&#34;pso&#34;)

psoptim函数

library(pso)
psoptim(par = rep(NA,2),fn = fit,lower = -10,upper = 10)
## $par
## [1] -4.761513e-48  4.881461e-48
##
## $value
## [1] 4.650066e-95
##
## $counts
##  function iteration  restarts
##    12000    1000       0
##
## $convergence
## [1] 2
##
## $message
## [1] &#34;Maximal number of iterations reached&#34;从psoptm函数的计算结果可知，其中par表示计算参数结果，分别约等于0，value表示对于的优化函数值。更多的函数使用说明可以参考官方文档。
<hr/>

TheLudGamer · 发表于 2021-12-1 14:27

粒子群算法，顾名思义是仿生一大堆粒子的整体行为的一种启发式算法，谈到粒子群算法就不得不提到模拟鸟类群集行为的Boid模型
Boid模型

Boids 是涌现行为的一个例子，其描述了鸟群中的个体如何根据周边同伴的位置和速度移动，主要有几个特点

冲突避免: 鸟群在一个有限的空间内飞动，每只鸟有自己独立的移动意志但是却不会影响别的鸟，会自发避免碰撞与争执
速度匹配：个体必须配合鸟群中心的移动速度，包括方向和速率上都必须相互配合
群体中心化：即个体倾向于鸟群中心移动(物以类聚不掉队)，并配合中心向目标方向前进(比如大雁南飞)

粒子群算法的一些假设和前提条件是基于Boid模型的，它的本质是初期粒子可能呈现杂乱无章随机的排布，但是到了最后通过各种因素一定会朝向一个目标收敛，每个粒子可以看成是自变量向量，粒子会不断更新，从而不断更新自变量向量达到搜索解空间的效果，粒子根据自己曾经寻找目标的经验和其他粒子信息共享，绝大部分鸟粒子不断向目标迈进，经过有限次位移迭代，绝大多数粒子就会聚集在一起并达到离目标近在咫尺的地方
核心思想

首先需初始化化各个粒子(鸟)的在空间中的位置和速度，一般采用对称初始化随机分布策略，这样粒子在最开始可以落到搜索空间的任意位置，这样有助于避免陷入某一个局部区域
正如人类在对待解决的问题或待选择的做决策一样，往往会综合自己经验和周围人的行为获取知识两种途径一样，前者主要是根据以往的尝试自身的储备，后者主要是见贤思齐，如此一来就需要群体信息共享和不断更新自身经验，当群体中所有个体都经过这样迭代之后，那么必将会逐渐朝向全局最优的目标迈进(这也是人生哲理之一)
量化自身经验的手段是利用当前的信息估计现在的自己对于达到目标有多大的贡献值(即对于达到目标有多大适应值)，然后不断记住自己最好的位置(自己的局部最优)，所以所有粒子的局部最优就可以找到全局最优，即同步效应，朝着最优的方向移动(每个个体看成是一个解)

量化

将每个个体看成一个粒子，假设D维的搜索空间中有m只鸟，第i只鸟的位置为 $x_i = (x_i^1,x_i^2,...,x_i^D)$ ,每只鸟是一个潜在解，将鸟的位置 $X_i$ 代入待优化的目标函数算出适应值，根据适应值大小衡量优劣，第i只鸟的最好位置记为 $p_i = (p_i^1,p_i^2,...,p_i^D)$ ,整个群体所有粒子经历的最好位置为 $p_s = (p_s^1,p_s^2,...,p_s^D)$ ,粒子速度为 $V_i = (v_i^1,v_i^2,...,v_i^D)$
更新速度和位置(算法核心),更新公式为

$v_i^d = \omega v_i^d + c_1 r_1 (p_i^d - x_i^d) + c_2 r_2(p_g^d - x_i^d) \\$ $x_i^d = x_i^d + \alpha v_i^d \\$

的出现是为了共享信息(是当前迭代情况下所有粒子最优适应度的位置,向强者看齐）， $p_i$ 的出现是为了记住自己的经验

式中是惯性因子，非负数， $c_1,c_2$ 是加速常数，也是非负数， $r_1,r_2$ 是满足[0,1]上均匀分布的随机数， $\alpha$ 是约束因子，目的是控制速度，约束速度

速度是有限制的(可以作为有约束优化的切入点)

$v_i^d \in [-v_{max}^d, v_{max}^d] \\$
当某个粒子更新后的速度超过了最大（小）飞翔速度，则这个时候就规定此时的速度取最大（小）飞翔速度,一般是约束边界

迭代终止条件一般达到预定最大迭代次数或粒子群目前为止搜索到的最优位置满足目标函数的最小容许误差即可

方法步骤

1、初始化粒子群速度和位置，惯性因子，加速常数，最大迭代次数，算法终止的最小误差
2、评价每个粒子的初始适应值，即代入目标函数
3、将初始适应值作为当前粒子的局部最优值(因变量)，且将位置作为当前的局部最优所在的位置(自变量)
4、将所有粒子中的最佳局部最优(初始适应值)作为当前全局最优值，并将其作为当前的全局最优值(最强的那个)，最佳位置最为全局最优的位置
5、代入速度更新关系式，更新粒子的飞行速度，并限幅处理，使其不能超过该粒子最大的粒子飞行速度
6、然后代入位移更新表达式，更新每个粒子的位置
7、对每个粒子比较每个粒子的适应值是否比历史的局部最优值好，如果好的话则当前适应值作为粒子的局部最优值，对应位置作为粒子的局部最优的位置
8、在当前粒子群中找出全局最优值，并将对应的位置作为全局最优的位置
9、重复5~9，直到满足设定的最小误差或达到最大迭代次数
10、输出最优值和位置以及其他粒子的局部最优值和位置

一些参数的选取

1、粒子数m，一般选20~40,粒子数越多搜索范围越大，但是一般30个左右就够了
2、惯性因子越大，粒子飞翔幅度越大，全局最优搜索能力越强，但局部寻优能力较弱，用来控制历史速度对当前速度的影响程度，决定了粒子对当前速度继承的多少，越大表明速度更新的幅度越大，因此更加偏离原先的寻优轨道，较好的策略是惯性因子随着迭代的次数不断减小，这样在后期就利于寻找局部最优解
3、加速常数c1,c2,一般都取2，衡量自身经验与群体经验在运动中的比重
4、最大飞翔速度，可以防止搜索范围毫无意义地扩大发散，防止速度过大直接俯冲过最优目标解，一般根据实际问题讨论

思想进阶

粒子群算法可能会容易有一些问题

粒子容易飞跃局部最优位置，造成局部搜索能力差，精度不高
如果适应度目标函数较为慢收敛，也容易出现粒子抱团，飞行速度为0的情况
较为相信别人的话导致一大堆粒子陷入别人自以为的最优位置里面，而这个所谓的别人一直一览众山小速度近乎不更新，从而得到局部极值的情况

遇到这些问题，第一也是最重要的应该是明白粒子在哪可以有概率跳出局部最优(该信别人多一些还是信自己多一些？是否可以动态调整加速常数？)，第二个是如果问题是有约束优化问题的话采用万能方法罚函数法，将问题转化为对正则系数的优化选取上(拉格朗日乘数法)，变成无约束规划，第三个就是挖掘更多的约束，用最大（小）飞翔速度来限制粒子
较为喜欢该算法所折射出的一些道理，前路漫漫，集众家之长地向强者学习的大背景下也不要忽视自身的经验和所得！还有就是只有自身知识积累到一定高度后才能更有机会地融入更高的圈子！
更多内容，欢迎关注公众号
期待和优秀的您一起互相学习互相帮扶！！！

		自动登录	找回密码
密码			立即注册

如何直观形象地理解粒子群算法？

本帖子中包含更多资源

本帖子中包含更多资源