粒子群算法^[1]是由Eberhart和Kennedy于1995年提出的一种全局搜索算法，同时它也是一种模拟自然界的生物活动以及群体智能的随机搜索算法. 算法是作者通过对鸟群觅食活动的规律性的观察，将社会心理学上的个体认知经验、社会经验、种群智慧等思想融合到组织性和规律性很强的群体行为中，进而转变为优化问题求解过程中可行解迭代时向局部最优和全局最优靠拢，最终产生优化问题的全局最优解. 但由于粒子群优化算法是一种有针对性的随机的启发式算法，在解决复杂优化问题时，对全局最优粒子进行粒子靠拢和追逐，最终粒子会趋向统一化而缺少多样性，每次求解的结果可能不同，也有可能找不到全局最优解. 该算法存在容易在局部最优点停止、进化后期收敛速度慢、鲁棒性差等缺陷^[2]. 针对以上问题，本文就远离最差解的思想在粒子群算法中引入2个因子：全局最差解和局部最差解，并分别测试全局最差解和局部最差解对粒子群优化算法的影响.

1 标准粒子群算法及其改进 1.1 标准粒子群算法

在可行解空间随机产生一群粒子，每个粒子都无质量和体积信息，将每个粒子作为可行解空间中的一个可行解，适应度函数即为目标函数. 迭代过程中，每个粒子都在可行解空间中进行位置变化，粒子的位置更新由粒子的速度确定. 通常粒子将追逐当前的最优粒子而运动，并经过逐代更新搜索，最后得到全局最优解. 每次迭代过程中，粒子都将向2个最优值靠拢：一个是粒子本身历史的最优解，即局部最优解；另一个是整个粒子群群体当前找到的最优解，即全局最优解.

假设种群规模popsize为n的粒子群在d维的搜索空间中按照一定的速度进行飞行. 粒子i在t时刻的状态设置如下.

粒子的位置：

$\begin{array}{*{20}{l}}{{{X}_i}(t) = ({{x}_{i1}}(t),{{x}_{i2}}(t), \cdot \cdot \cdot ,{{x}_{id}}(t)),}\\[6pt]{{{x}_{id}}(t) \in [{L_d},{U_d}],}\end{array}$

其中，L_d为搜索空间的下限，U_d为搜索空间的上限；

粒子的速度：

$\begin{array}{l}{{v}_i}(t) = ({{v}_{i1}},{{v}_{i2}}, \cdot \cdot \cdot ,{{v}_{id}}),\\[6pt]{{v}_{id}}(t) \in [{{v}_{\min }},{{v}_{\max }}],\end{array}$

其中，v_min为最小速度，v_max为最大速度；

个体最优位置：

${{P}_{{\rm{best}}}}_i(t) = ({{p}_{i1}}(t),{p}{}_{i2}(t), \cdot \cdot \cdot ,{{p}_{id}}(t));$

全局最优值位置：

${{G}_{{\rm{best}}}}(t) = ({{p}_{g1}}(t),{{p}_{g2}}(t), \cdot \cdot \cdot ,{{p}_{gd}}(t)),$

其中， $1 \leqslant i \leqslant {\rm{popsize}}$ ，popsize为粒子群群体粒子总数.

那么粒子在t+1时刻的位置更新公式如下：

$\begin{split}& {{v}_{id}}(t + 1) = w \times {{v}_{id}}(t) + {c_1} \times {r_1} \times ({{P}_{{\rm{best}}}}_i(t) - \\& \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; {{x}_{id}}(t)) +{c_1} \times {r_2} \times ({{G}_{{\rm{best}}}}(t) - {{x}_{id}}(t)),\\& {{x}_{id}}(t + 1) = {{x}_{id}}(t) + {{v}_{id}}(t + 1),\end{split}$

(1)

式（1）中，r₁、r₂均为在（0, 1）区间均匀分布的随机数；c₁、c₂为学习因子，一般取2.

1.2 已有的粒子群改进算法

根据已有文献，目前粒子群算法已有的改进一般从以下几个方面进行：

(1) 惯性权重模型：惯性权重w是前一速度的惯性控制量. 一般设置为从0.9线性递减到0.4^[3-5]，即

$w = {w_{\max }} - \frac{{{w_{\max }} - {w_{\min }}}}{{{\rm{ite}}{{\rm{r}}_{\max }}}} \times {\rm{iter,}}$

(2)

其中，w_max为惯性权重最大值，一般经验设为0.9，w_min为惯性权重最小值，一般经验设为0.4；iter_max为迭代最大次数，iter为当前迭代次数.

(2) 学习因子模型：代表了粒子向局部最优点P_best和全局最优点G_best靠拢的加速权重. c₁、c₂一般取2.0，代表着对2个引导方向的同等重视^[6]. 也有一些c₁、c₂不相等的设置，但其范围都在0～4之间，比如将c₁线性减小，c₂线性增大的设置能动态平衡算法的多样性和收敛性^[7-8].

(3) 拓扑结构：不同的拓扑结构会影响算法的全局搜索和局部搜索的能力. Kennedy在进化计算国际会议CEC上发表了文章^[9-10]，提出了例如星型结构、环型结构、齿形结构、金字塔结构、冯·诺依曼结构等等不同的拓扑结构，并且比较了它们在PSO中的性能. 国内的一些学者也提出了一些新的拓扑设计准则, 如菱形十二面的拓扑结构^[11]、层次环形结构的拓扑结构^[12]、基于加权有向的拓扑结构^[13], 并证明了其改进效果.

(4) 与其他算法结合：自粒子群算法提出之后，很多学者就不断地将PSO算法和其他搜索算法或者思想技术相结合，形成了许多PSO算法和其他算法混合的算法的改进版本. 这些算法有些融合了传统进化计算中的算子^[14-15]，例如选择算子、交叉算子、变异算子等，有些直接与其他算法相结合，例如模拟退火算法、免疫算法、差分进化算法、人工鱼群算法等^[16-17].

2 本文改进的粒子群算法

针对标准粒子群优化算法容易陷入局部最优、寻优精度低及后期搜索速度慢等缺陷，本文提出一种基于全局最差解(G_worst)和局部最差解(P_worst)的改进粒子群算法(LWPSO)，并针对同时改进G_worst和P_worst、只改进G_worst、只改进P_worst这3种情况进行仿真实验.

本文算法参数设定：

惯性权重： $w = {w_{\max }} - \displaystyle\frac{{{w_{\max }} - {w_{\min }}}}{{{\rm{ite}}{{\rm{r}}_{\max }}}} \times {\rm{iter}}$ ；

${w_{\max }} = 0.9, \;\; {w_{\min }} = 0.4.$

学习因子：c₁、c₂=2；

粒子更新公式：

$\begin{array}{l}{{v}_{id}}(t + 1) = w {{v}_{id}}(t) + {c_1} {r_1} ({{P}_{{\rm{best}}}}_i(t) - {{x}_{id}}(t)) + \\[6pt]{c_1} {r_2} \times ({{G}_{{\rm{best}}}}(t) - {{x}_{id}}(t)) - {\rm{ }}{r_3} ({{P}_{{\rm{worst}}}}_i(t) - {{x}_{id}}(t)),\\[6pt]{{x}_{id}}(t + 1) = {{x}_{id}}(t) + {{v}_{id}}(t + 1),\end{array}$

(3)

其中，P_worsti(t)为i粒子t时刻局部最差粒子位置，即个体最差位置；r₁、r₂、r₃为均匀分布在0到1之间的随机数；同时改进时加入G_worst的影响，G_worst为全局最差粒子位置.

2.1 算法流程如下 2.2 算法步骤

(1) 按种群规模初始化粒子位置和速度，用目标函数计算粒子的适应度值，将个体的历史最优(P_best)和历史最差(P_worst)设为当前位置，种群中最优个体位置作为当前全局最优(G_best).

(2) 按照式(3)进行粒子位置和速度更新，然后计算粒子的适应度值.

(3) 如果该粒子当前的适应度值优于历史最优值，那么历史最优被当前值取代.

(4) 如果该粒子当前的适应度值优于全局最优值，那么全局最优被当前值取代.

(5) 如果该粒子当前的适应度值差于历史最差值，那么历史最差被当前值取代.

(6) 如果满足结束条件，则结束并输出G_best；否则转至(2).

3 仿真实验及分析 3.1 测试函数

测试函数如表1所示.

3.2 测试结果

为了验证本文算法的有效性，和惯性权重w线性改变的粒子群算法^[3]基于上述测试函数进行仿真实验比较. 图2~7中LWPSO是本文算法，PSO是惯性权重w线性减少，c₁、c₂=2的粒子群算法^[3]. popsize取20，维度为30，最大迭代次数为100. 测试采用MATLAB 2013a版本，CPU为E5200，频率2.5 GHz，测试环境Win10下进行，以下为测试结果.

Ackley函数测试结果：粒子更新公式单独改进P_worst和二者同时改进之后效果明显，收敛速度有所提高；而单独改进G_worst的影响反而效果不好或和原有算法差不多.

Griewank函数测试结果：Griewank函数的测试结果都不错，P_worst和G_worst都同时改进的效果比初值相同的PSO效果较好；而单独改进了G_worst虽然最后达到最优，但是不如PSO速度快；单独改进了P_worst的效果很明显，能够更快速的收敛.

Rastrigin函数测试结果：3种改进效果均比较理想，其中同时改进和单独改进P_worst效果最好，收敛速度较快.

Rosenbrock函数测试结果：3种改进之后的收敛速度均有所提高，其中二者同时改进和单独改进P_worst效果更好.

Sphere函数测试结果：二者同时改进和单独改进P_worst之后的收敛速度有所提高，而单独改进G_worst之后的收敛速度有所下降.

Matyas函数测试结果：可以看出PSO有时易陷入局部最优，但3种改进之后的算法均能到达最优值，其中单独改进P_worst的效果最好，收敛速度最快.

综上，单独改进P_worst的LWPSO在各个函数的表现都很出色，收敛速度均有所提高，算法改进的有效性得到验证.

表2为上述2种算法求解对应函数精度对比，算法分别独立运行30次取平均值（最大迭代次数为1 000，维度为30，种群规模20），加粗部分为精度高的算法. 从表2中可以看出，除了Sphere函数的精度2种算法差不多之外，其他函数的求解精度LWPSO均明显优于PSO.

4 结束语

本文针对标准粒子群优化算法容易早熟收敛和易陷入局部最优的缺点，提出一种基于全局最差解(G_worst)和局部最差解(P_worst)的改进粒子群算法，并分别针对同时改进G_worst和P_worst、只改进G_worst、只改进P_worst进行仿真. 实验结果显示：G_worst改进之后的结果则和粒子群算法（本文的粒子群算法指的是惯性权重和学习因子改进之后的粒子群算法）效果差不多，二者同时改进和单独改进P_worst的效果较好，收敛速度和精度有所提高；其中单独改进P_worst的效果最好，在几个测试函数中都得到了体现. 如果把个体最优和全局最优对粒子的影响比喻成向量的形式，P_best和G_best影响之后的向量方向是趋向G_best的. 当粒子群后期，G_best无变化时，P_best等于G_best，这时速度靠拢方向向量为零，粒子前进的方向只有自身惯性，而我们加入了P_worst和G_worst之后的算法显然能够避免这一点. 在算法前期，远离P_worst和G_worst的方向向量相当于在趋向G_best的方向的加速，所以收敛速度较快；算法后期当G_best无变化时，G_worst和P_worst又能够使粒子的前进方向不仅受自身惯性的影响，而且可以继续的寻优，从而找到全局最优.