2020年IEEE TCYB SCI1区TOP，三重存档粒子群算法TAPSO，深度解析+性能实测

1.摘要

本文针对粒子群算法（PSO）中的两大核心问题——如何选择合适的学习范例和设计高效的学习模型，提出了一种三重存档粒子群优化算法（TAPSO）。TAPSO算法通过建立三个不同的存档，分别保存精英粒子、进步最快的获益粒子以及表现突出的范例粒子，实现了更优的范例选择和模型自适应。TAPSO 利用遗传算子从精英与获益粒子中生成新解，并根据范例的适应度为每个粒子动态调整学习模型。同时，优秀范例可被低效粒子反复利用，提升开发能力并节省计算资源。

2.粒子群算法PSO原理

【智能算法】粒子群算法（PSO）原理及实现

3.三重存档粒子群算法TAPSO

TAPSO动机

在实际应用中，利用启发式算法如何保持种群多样性是影响全局搜索能力的关键问题。传统PSO中，粒子在社会学习阶段只向一个范例学习，导致可获得的信息有限，种群容易陷入早熟收敛。现实生活和相关研究表明，向多个范例学习可以获得更多有用知识，提升学习效果。
已有方法通常只根据适应度高低选择多个范例，但这样容易让粒子过度聚集在当前表现最好的区域，增加早熟风险。事实上除了适应度最优，还应关注那些进步最快的粒子，因为它们往往位于值得探索的新区域，有可能接近全局最优解。

基于此，TAPSO算法提出利用适应度和进步幅度两个指标，将表现优秀和进步显著的粒子分别存档。每一代中，从这两个存档各选一个粒子，通过遗传操作生成多样化的学习范例，再结合自适应学习模型进行知识提取。此外，将部分表现突出的范例保存到第三个存档，供其他粒子重复利用，从而提升搜索效率，节省计算资源。
TAPSO 以三重存档和多元学习为核心机制，有效平衡了探索与开发，增强了算法的全局寻优能力。

精英与获益者存档的范例生成

在不失一般性的前提下，本文的目标函数$f$为主，TAPSO中粒子$i$进步率$I_r$定义：
$$Ir({\mathbf{X}}_i^t)=\frac{f({\mathbf{X}}_i^{t-1})-f({\mathbf{X}}_i^t)}{e^{|{\mathbf{X}}_i^{t-1}-{\mathbf{X}}_i^t|}}$$

进步率较高的粒子（获益者）表示该粒子在较短的移动距离内获得了更大的适应度提升。如果粒子的适应度在某一区域发生了显著变化，则该区域可能存在局部最优。

虑到精英和获益者各自具有不同的优势，因此每一代分别用两个外部存档记录。存档$A_e^t$ 和$A_p^t$ 分别保存表现最好的 $M$个精英粒子和进步最快的$M$个获益者粒子,为了充分利用精英和获益者的信息，每一维度的范例都是分别从$A_p^t$和$A_e^t$中选择两个父代，通过常见的遗传算子生成。注意，$A_e^t$和$A_p^t$分别按$f$和$Ir$由小到大、由大到小排序。
$$A_e^t=\left\{{\mathbf{X}}_{i_1}^t,{\mathbf{X}}_{i_2}^t,\dots ,{\mathbf{X}}_{i_M}^t|f\left({\mathbf{X}}_{i_1}^t\right)\le f\left({\mathbf{X}}_{i_2}^t\right)\le \cdots \le f\left({\mathbf{X}}_{i_M}^t\right)\right\}$$
$$A_p^t=\left\{{\mathbf{x}}_{j_1}^t,{\mathbf{x}}_{j_2}^t,...,{\mathbf{x}}_{j_M}^t\right|Ir({\mathbf{x}}_{j_1}^t)\ge Ir({\mathbf{x}}_{j_2}^t)\ge ...\ge Ir({\mathbf{x}}_{j_M}^t)$$

在这种排序下，$f$较小或$Ir$较大的个体被选为父代的概率更高。对于排序后的存档，选择第$k$个个体作为父代的概率如下：
$$p_k=\frac{M-k+1}{{\sum }_{i=1}^{M}i}$$
其中，$M$为存档大小。
当某个粒子同时具备优良适应度和显著进步率时，应将其分别存入精英存档$A_e^t$和获益者存档$A_p^t$。这样可以在范例生成过程中，充分发挥该粒子的双重优势。然而，这也可能导致两个副本在同一次范例生成中被同时选中，从而使交叉操作无实际效果，此时生成的范例仅是该粒子的一个变异体。

学习模型的选择

TAPSO中，每个粒子在每一代都会产生三个潜在范例：历史个体最优（PB）、全局最优（GB）和当前遗传操作产生的新范例（Ei）。根据这三者的适应度高低关系，TAPSO为粒子设计了三种自适应学习模型：

• diffident模型：若Ei的适应度最好，粒子完全依赖Ei，无视自身和其他经验，直接向Ei移动。这种策略有利于局部甚至全局最优解的深度开发，提升算法的收敛能力；
  $$v_{i,j}^t=w\cdot v_{i,j}^{t-1}+r_{1,j}\cdot \left(e_{i,j}-x_{i,j}^{t-1}\right)$$
• mild模型：若GB优于Ei，Ei优于PB，粒子结合Ei和GB，既利用了新范例的多样性和精英特性，又兼顾了全局引导信息，在开发和探索之间取得平衡；
  $$v_{i,j}^t=w\cdot v_{i,j}^{t-1}+r_{1,j}\cdot \left(e_{i,j}-x_{i,j}^{t-1}\right)+r_{2,j}\cdot \left(g{b}_{i,j}-x_{i,j}^{t-1}\right)$$
• confident模型：若粒子自身历史最优优于新范例，粒子只围绕自身历史最优（PB）搜索，无视其他个体。这一策略增强了种群的全局探索能力，避免陷入局部最优。

$${\nu }_{i,j}^t=w\cdot {\nu }_{i,j}^{t-1}+r_{1,j}\cdot \left(p{b}_{i,j}-x_{i,j}^{t-1}\right)$$

杰出范例存档复用

当新生成的范例$E_i$优于全局最优或粒子个体最优时，说明它具有较高的开发价值。为了避免优秀范例因单次未被利用而浪费，TAPSO将这类范例存入杰出范例存档($A_o)$,以便后续被其他粒子复用，从而提升整体搜索效率。
为控制计算开销，$A_o$的容量被设置为与种群规模相同，并通过锦标塞策略动态更新：当存档已满时，随机抽取两解，淘汰较差者，用新的优秀范例替换。这样既能保存高质量解，又兼顾了多样性。在复用环节，TAPSO会定期让种群中表现较差的粒子从$A_o$中获得替换机会。将$A_o$随机分组，每组选出适应度更优者作为优胜者，用于替换种群中的劣质粒子，从而加速全局搜索并节省计算资源。

4.结果展示

5.参考文献

[1] Xia X, Gui L, Yu F, et al. Triple archives particle swarm optimization[J]. IEEE transactions on cybernetics, 2019, 50(12): 4862-4875.

6.代码获取

xx

7.算法辅导·应用定制·读者交流