粒子群优化算法(Particle Swarm Optimization,PSO)

PSO算法对每个粒子的要求

• 所有粒子都在一个D维空间中进行搜索
• 所有粒子都由一个适应函数确定适应值以判断目前位置的好坏
• 每个粒子都有记忆功能，可以记住寻找到的最佳位置
• 每个粒子有一个速度和飞行方向

粒子群优化算法求最优解：(D维空间中，有N个粒子)

• 粒子i的位置：$X_i=(x_{i1},x_{i2},...x_{iD})$，将$X_i$带入适应函数$f(x_i)$求适应值
• 粒子i的速度：$V_i=(v_{i1},v_{i2},...v_{iD})$
• 粒子i自身经历最好的位置：$pbas{t}_i=(p_{i1},p_{i2},...p_{iD})$
• 粒子种群经历过最好的位置：$gbast=(g_1,g_2,...g_D)$
• 在d$(1\le d\le D)$维的位置变化范围限定在$[X_{min,d},X_{max,d}]$内。(保证所有粒子在有限可控范围内进行迭代)
• 速度变化范围限定在$[-V_{max,d},V_{max,d}]$内。（保证粒子速度变化可控）

粒子群算法迭代过程

粒子i的第d维速度跟新公式：
$$V_{id}^k=W{V}_{id}^{k-1}+c_1{r}_1(pbes{t}_{id}-x_{id}^{k-1})+c_2{r}_2(gbes{t}_d-x_{id}^{k-1})$$

$W{V}_{id}^{k-1}$：粒子先前的速度矢量

$c_1{r}_1(pbes{t}_{id}-x_{id}^{k-1})$：本粒子找到的最优解，自我认知部分

$c_2{r}_2(gbes{t}_d-x_{id}^{k-1})$：群体找到的最优解，社会经验部分

粒子i的第d维位置更新公式：

$$x_{id}^k=x_{id}^{k-1}+v_{id}^{k-1}$$

$x_{id}^{k-1}$：之前迭代中的位置信息

$v_{id}^{k-1}$：当前的速度矢量

• $v_{id}^k$：第k次迭代粒子i飞行速度矢量的第d维分量
• $x_{id}^k$：第k次迭代粒子i位置矢量的第d维分量
• $c_1,c_2$：加速度常数，调节学习最大步长
• $r_1,r_2$：两个随机函数，取值范围[0,1],以增加搜索随机性
• w：惯性权重，非负数，调节对解空间的搜索范围。（w值越大，全局搜索能力越强，局部搜索能力越弱）

粒子群优化算法流程图

惯性权重，线性递减权值

主要解决问题：前期粒子群比较分散时，提高全局搜索能力；后期粒子群比较集中时，提高局部收敛精度。至此w不宜为固定常数。
$$W=W_{max}-(W_{max}-W_{min})\times \frac{run}{ru{n}_{max}}$$

• $W_{max}$：最大惯性权重
• $W_{man}$：最小惯性权重
• $run$：当前迭代次数
• $ru{n}_{max}$：本次算法迭代总次数

其中较大的w有较好的全局搜索能力，较小的W有较强的局部收敛能力。次公式完成的任务就是：随着迭代次数的增加，惯性权重W不断减小，从而使得PSO算法在前期具有较强的搜索能力，在后期具有较强的收敛能力。

粒子群算法构成要素

群体大小m

• 当m很小：陷入局部最优解的可能性很大

• 当m很大：虽然PSO效果好，但是效率会变慢，比较冗余

权重因子

惯性因子：W

• 当W=1时，为基本粒子群算法
• 当W=0时，将失去对粒子本身的速度记忆（会造成粒子随机性过重，使得寻优更加困难）

学习因子：$c_1,c_2$

• $c_1{r}_1(pbes{t}_{id}-x_{id}^{k-1})$：当$c_1$=0，无私型粒子群算法（会迅速丧失群体多样性，容易陷入局部最优）
• $c_2{r}_2(gbes{t}_d-x_{id}^{k-1})$：当$c_2$=0，自我认知型粒子群算法（完全没有信息社会共享，导致算法收敛速度过低）

邻域拓扑结构

• 全局粒子群算法，将种群所有粒子都设为邻域
  • 收敛速度快
  • 容易陷入局部最优
• 局部粒子群算法，只将部分粒子设为邻域，邻域随迭代次数线性变大，最后邻域扩展到整个粒子群
  • 收敛速度慢
  • 但是不容易陷入局部最优