2014，TEVC，A competitive swarm optimizer for large scale optimization（CSO）

PSO 分析（从而引入 CSO）

CSO (competitive swarm optimizer) 算法是在PSO (particle swarm optimization) 算法的基础上改进而来的。PSO算法是一种功能强大、应用广泛的群体智能算法，主要用来解决优化问题。PSO算法包含一个粒子群，粒子群里面的每个粒子均有1个$n$维位置变量和1个$n$维速度变量。在算法的每次迭代过程中，每个粒子的位置变量$X_i$ 和速度变量$V_i$通过以下公式进行更新：

$$\begin{array}{c}{V}_i\left(t+1\right)=\omega V_i\left(t\right)+c_1{R}_1\left(t\right)(pbes{t}_i\left(t\right)?X_i\left(t\right))+c_2{R}_2\left(t\right)(gbest(t)?X_i\left(t\right))\\ \\ \\ X_i\left(t+1\right)=X_i\left(t\right)+V_i\left(t+1\right)\end{array}$$

其中$t$是当前迭代数，$\omega$是惯性权重，$c_1$和$c_2$是加速度系数，$R_1(t)$和$R_2\left(t\right)$是两个向量，向量中每个元索取值范围为$[0,1{]}^n$，$pbes{t}_i(t)$ 是第$i$个粒子的历史最优解，$gbest(t)$是所有粒子的历史最优解。$c_1{R}_1(t)(pbes{t}_i(t)?X_i(t))$为认知部分，$c_2{R}_2(t)(gbest(t)?X_i(t))$为社会部分。

当优化问题存在大量局部最优值和具有高维特点时，传统PSO算法在处理此类问题时会过早收敛，从而导致其优化效果不佳。首先来看 $gbest$ 对算法收敛过程的影响，将上述公式进行变换，可得：

$$V_i\left(t+1\right)=\omega V_i\left(t\right)+{\theta }_1(p_1?X_i\left(t\right))$$

其中，

$${\theta }_1=c_1{R}_1\left(t\right)+c_2{R}_2\left(t\right)$$

$$p_1=\frac{c_1{R}_1\left(t\right)}{c_1{R}_1\left(t\right)+c_2{R}_2\left(t\right)}pbes{t}_i\left(t\right)+\frac{c_2{R}_2\left(t\right)}{c_1{R}_1\left(t\right)+c_2{R}_2\left(t\right)}gbest(t)$$

$p_1$和$X_i$的差决定了粒子群的种群多样性，而$pbes{t}_i$ 和$gbest$的取值多样性决定了$p_1$取值的多样性。由于$gbest$的影响，随着送代过程的继续，粒子逐渐向$gbest$靠拢，这导致$pbes{t}_i$逐渐接近$gbest$,进而导致粒子群的种群多样性大幅降低。$p_1$在很大程度上决定着传统PSO 算法在搜索过程中的勘探能力和开采能力。

为了解决传统PSO算法的过早收敛问题，本文提出了CSO算法。该算法去掉了$pbes{t}_i$和$gbest$两个变量，引入了粒子间的成对竞争机 制。在该机制中，竞争失败的粒子将向竞争胜利的粒子学习，而不是向$pbes{t}_i$和$gbest$学习，这将较好地解决传统PSO算法的过早收敛问
题。

基本理论

CSO 算法的总体思想如图所示。在每一次迭代过程中，随机从粒子群$P(t)$中选择一对粒子进行竞争。竞争成功的粒子直接进入下一次迭代，竞争失败的粒子将向竞争成功的粒子学习并更新自己的位置变量和速度变量。该操作完成后，将这一对粒子从粒子群$P(t)$中剔除， 将竞争成功的粒子和更新后的失败粒子加入到粒子群$P(t+1)$中。当所有粒子从粒子群$P(t)$中移到粒子群$P(t+1)$中后，算法进入下一次迭代。根据上图可知，每一次迭代将会使粒子群$P$中一半的粒子得到更新。

竞争失败的粒子的速度变量和位置变量更新如以下公式所示：

$$\begin{array}{rl}{V}_{l,k}\left(t+1\right)& =R_1\left(k,t\right)V_{l,k}\left(t\right)+R_2\left(k,t\right)(X_{w,k}\left(t\right)?X_{l,k}\left(t\right))+\phi R_3\left(k,t\right)({\bar{X}}_k\left(t\right)?X_{l,k}\left(t\right))\end{array}$$

$$\begin{array}{rl}{X}_{l,k}\left(t+1\right)& =X_{l,k}\left(t\right)+V_{l,k}\left(t+1\right)\end{array}$$

其中，$X_{w,k}(t)$表示第$t$代的第$k$轮竞争中竞争成功粒子的位置，$X_{l,k}(t)$表示第$t$代的第$k$轮竞争中竞争失败粒子的位置，$V_{l,k}(t)$表示第$t$ 代的第$k$轮竞争中竞争失败粒子的速度，$R_1(k,t)$、$R_2(k,t)$、$R_3(k,t)\in [0,1]$分别表示算法第$t$次迭代的第$k$轮竞争中随机生成的向量。

${\bar{X}}_k\left(t\right)$表示第$t$代的第$k$轮竞争中相关粒子的位置平均值，它分为全局版本和局部版本。

• ${\bar{X}}_k^g(t)$表示$P(t)$中所有粒子的位置平均值，是全局版本。
• ${\bar{X}}_{l,k}^l(t)$表示在竞争失败粒子的预定义邻域内所有粒子的位置平均值，是局部版本。领域控制可以增加粒子群的种群多样性，这可能会提高CSO算法的搜索能力。

---

算法流程

1.3 勘探能力与开采能力分析

粒子群优化算法 PSO 是一种模拟自然界生物群体行为的随机搜索算法，它通过调整粒子的速度和位置来寻找最优解。在这个过程中，粒子需要平衡两种能力：

1. 勘探能力（Exploration Ability）：指粒子在搜索空间中探索新区域的能力，也就是全局寻优能力。勘探能力越强，粒子越容易跳出局部最优解，找到更好的解。
2. 开采能力（Exploitation Ability）：指粒子在搜索空间中开发已知区域的能力，也就是局部寻优能力。开采能力越强，粒子越容易收敛到最优解，提高搜索精度。

粒子群优化算法 PSO 的参数设置和拓扑结构都会影响粒子的勘探能力和开采能力，因此需要根据不同的优化问题进行合理的调整。一般来说，算法在前期需要较强的勘探能力，而在后期需要较强的开采能力，以达到最佳的性能。

首先分析一下CSO算法的勘探能力，将上述公式转换：
$$\begin{array}{rl}& V_i\left(t+1\right)=R_1\left(k,t\right)V_i\left(t\right)+{\theta }_2(p_2?X_i\left(t\right))\end{array}$$

$${\theta }_2=R_2\left(k,t\right)+\phi R_3\left(k,t\right)$$

$$p_2=\frac{R_2\left(k,t\right)}{R_2\left(k,t\right)+\phi R_3\left(k,t\right)}{X}_w\left(t\right)+\frac{\phi R_3\left(k,t\right)}{R_2\left(t\right)+\phi R_3\left(k,t\right)}\bar{X}\left(t\right)$$

CSO算法的种群多样性是高于传统PSO算法的，因为$X_w(t)$和$\bar{X}(t)$的取值更加地多样。下面展示CSO算法的勘探能力是如何高于传统PSO算法的。

首先看图 2，$gbest(t)$陷入了局部最优，在传统PSO算法中，两个被选择的粒子均会向$gbest(t)$靠近，这最终使得算法陷入局部最优的陷阱，导致算法优化结果的不佳。现在去掉向$gbest(t)$更新的方式，所有粒子均只向各自的$pbest(t)$更新，如图 3。从图可以看出，被选择的粒子会跳出局部最优的陷阱，使得算法的勘探能力得到了提升。但是如果$pbest(t)$也陷入了局部最优，如图 4，算法也会陷入局部最优的陷阱，导致算法的勘探能力下降。因此，去掉向$gbest(t)$ 与 $pbest(t)$ 更新的方式，粒子的更新采用成对粒子竞争更新机制，传统PSO算法也就演变为CSO算法。如图 4，由于所有粒子分布在样本空间的不同位置，粒子的更新就变得更加多样化，非常有助于算法脱离局部最优的陷阱，从而使得算法的勘探能力大幅提升。

然后分析一下CSO算法的开采能力。CSO算法的开采阶段是在勘探阶段之后，是在勘探阶段基础上继续小规模地提高算法的优化结果。在传统的PSO算法中，有以下关系：

$$\{\begin{array}{c}f(gbest(t))\le f\left(pbes{t}_w\left(t\right)\right)\le f\left(X_w\left(t\right)\right)\\ f(gbest(t))\le f\left(bes{t}_l\left(t\right)\right)\le f\left(X_l\left(t\right)\right)\end{array}$$

随着迭代过程的继续，t 越来越大，有：

$$\{\begin{array}{l}pbes{t}_w\left(t\right)\approx gbest(t)\\ pbes{t}_l\left(t\right)\approx gbest(t)\end{array}$$

然后令：

其中$p_1^{\prime }$是$p_1$的数学期望，$p_2^{\prime }$是$p_2$在$\phi =0$的数学期望。可以得到：
$$\Delta F_2\left(t\right)\le \Delta F_1\left(t\right)$$

与传统PSO算法相比，CSO算法有更好的能力开发与最优粒子相接近的粒子，也就是其开发能力更好，即局部搜索能力更强。此证明过程主要与其勘探过程结合来看。

References

Cheng R, Jin Y. A competitive swarm optimizer for large scale optimization[J]. IEEE transactions on cybernetics, 2014, 45(2): 191-204.

标准 CSO

竞争粒子群（CSO）算法