内嵌区域震荡搜索的粒子群优化算法

汤继涛，戴月明

TANG Jitao,DAIYueming

江南大学 物联网工程学院，江苏 无锡 214122

School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China

1 引言

粒子群优化算法（Particle Swarm Optimization，PSO）是一种基于种群搜索策略的全局优化进化算法。它源于鸟群和鱼群群体觅食运动行为研究结果的启发，于1995年由Kennedy和Eberhart共同提出[1]。算法的原理是：每个粒子都有初始位置和速度，都是解空间中的可行解。系统首先初始化为一群随机粒子，然后粒子通过追随个体最优解和群体最优解来完成优化。算法收敛速度较快，涉及参数较少，实现简单，具有较强的全局优化能力。PSO算法作为一种并行优化算法，可以用于解决大量非线性、不可微和多峰值的复杂问题优化，并已广泛应用于函数优化、神经网络训练、模式分类和模糊控制等领域[2-4]。PSO中每个粒子具有记忆功能，能够在迭代中记忆自己进化过程中的最优位置，并结合自身学习能力和社会学习的能力，协同其他粒子追随种群最优粒子，所有粒子都是向着最优解的方向飞去。由于粒子后期在行进的过程中趋于同一化，群体的多样性逐渐丧失，致使后期算法的收敛速度明显变慢，甚至处于停滞状态，出现早熟现象。

为克服算法过早陷入局部最优，保证全局收敛，提升算法的寻优能力，不少学者做了大量的工作，对算法进行了改进[5-7]。改进的粒子群算法大多引入了变异操作，当粒子趋于局部收敛时或算法后期使粒子产生变异，跳出局部收敛位置，从而达到全局收敛的效果。本文结合PSO强大的全局寻优能力，以粒子群中每个粒子的收敛吸引子为中心，引入区域震荡搜索因子，使粒子在吸引子的周围区域震荡搜索寻求全局最优值，避免算法陷入早熟。这有效提升了算法的收敛精度和速度。通过实验结果进行了验证。

2 标准粒子群优化算法（SPSO）

粒子群算法是在1995年由美国社会心理学家Kennedy和电气工程师Eberhart共同提出的，其基本思想起源于他们早期对鸟类群体行为研究结果，并利用了生物学家Frank Heppner的生物群体模型而形成的。粒子群优化算法是一种基于群体的具有全局寻优能力的优化工具。它通过迭代搜寻最优值，系统初始化为一组最优解，而粒子（潜在的解）在解空间追随最优的粒子进行搜索。假设在一个D维的目标搜索空间中，有N个粒子组成一个群体，其中第i个粒子表示一个D维的向量 xi，i=1，2，…，N ，即第i个粒子在D维的搜索空间中的位置是xi；第i个粒子的飞行速度也是一个D维的向量，记为vi，i=1，2，…，N。每个粒子的位置就是一个潜在的解，将xi代入一个目标函数就可以计算出其适应度值，根据适应度值的大小衡量xi的优劣。记第i个粒子迄今为止搜索到的最优位置为 pbi，i=1，2，…，N，整个粒子群迄今为止搜索到的最优位置为gb。

每个粒子的当前最好位置由以下公式决定：

而粒子群优化算法采用下列公式对粒子进行动态调整：

其中，i=1，2，…，N；公式中，t为当前的迭代次数；w为惯性权重因子，用来控制种群长时间不陷入早熟；自身学习c1和社会学习因子c2是非负常数；r1和r2是介于[0，1]之间的随机数。迭代终止条件根据具体问题一般选为最大迭代次数或粒子群迄今为止搜索到的最优位置满足预定最小适应阈值。

3 区域震荡的粒子群优化算法（RSPSO）

M.Clerc通过代数和数学分析方法，对PSO算法中粒子收敛行为进行了分析[8]，研究表明，粒子i的收敛过程是以点 pi=(pi1，pi2，…，piD)为吸引子，其坐标为：

或者

实际上，当 c1=c2时，φi，j(t)本身就是一个区间（0，1）上均匀分布的随机数，即 φi，j(t)～U(0，1)。因此在实际计算过程中可以直接由随机数发生器产生，这时公式（4）（5）就可以合并起来写成：

在区域震荡搜索的粒子群优化算法中，将采用这个公式。在收敛过程中，随着速度的减小，粒子i不断接近 pi点，最后跌落到 pi点。因此在整个过程中，在 pi点存在某种形式的吸引力吸引着粒子，最后促使整个种群保持聚集性。

本文在确立粒子群中每个粒子的吸引子的基础上，计算出每个粒子当前所处位置和该粒子吸引子的距离Δi，j(t)。

Δi，j(t)的大小是粒子群收敛程度的反映。 Δi，j(t)的值越小代表着在吸引子的作用下粒子越靠近吸引子，种群的聚集性就越强；相反，Δi，j(t)的值越大代表着粒子还没有及时靠近吸引子，种群相对比较发散，种群的聚集性相对较弱。在算法初期，Δi，j(t)的值相对比较大，在后期由于迭代种群趋向同一化，Δi，j(t)的值就会变小，粒子i会不断靠近吸引子 pi点，最终收敛到 pi点。

为防止Δi，j(t)在种群迭代的过程中逐渐变小，种群丧失多样性，算法陷入局部极值，本文提出了区域震荡的粒子群优化算法。区域震荡算法应用于粒子群粒子的每一维，粒子i的各维区域震荡因子为 Δi，j(t)， 1≤ i≤ N，1≤ j≤ D 。 Δi，j(t)描述的是粒子i当前的 j维度位置和该粒子相应维度的吸引子之间的距离，前面已经讲到，距离的大小反映粒子的聚集程度。粒子震荡搜索的范围是以吸引子为中心，区域震荡因子为半径的搜索区域，即 regioni，j=pi，j± Δi，j。粒子既是受到吸引子的吸引，则粒子震荡搜索的方向即为粒子指向吸引子的方向。粒子搜索的过程中，区域震荡因子线性减小，从而使粒子能够在吸引子周围区域以一定概率寻找到比自身历史极值更佳的值。区域震荡因子线性减少的公式为：

Δi，j(S)为粒子指向吸引子开始的震荡幅度，由于粒子的搜索区域是以吸引子为中心，粒子和吸引子的距离为半径的范围，所以设定为 2Δi，j(t)，Δi，j(E)为粒子指向吸引子结束时的震荡幅度，这里设定为0，RS为粒子最大的震荡次数，k则为当前的粒子震荡次数。

粒子各维每震荡搜索一次，粒子各维的位置则改变一次，粒子各维的位置更新式为：

xi，j(k)记录第k次在吸引子附近震荡搜索的粒子位置，xi，j(t)为粒子震荡搜索前粒子所在的位置。 flag则是来决定粒子震荡的方向，使粒子在每次搜索的过程中都保证粒子是向着吸引子靠近。粒子从第一维度开始搜索，每搜索一次粒子要结合该粒子剩余的还没有震荡搜索的维度位置计算出粒子的适应度值，在完成震荡搜索之后选取适应度值最小的位置，剩下的维度则按照相同的方法实现。当粒子的各个维度都完成设定的粒子区域震荡次数RS后，将各个维度的最佳位置拼接起来计算粒子的适应度值，如果适应度值优于粒子的历史最优极值则取代震荡搜索前粒子的历史最优极值，如果适应度值优于整个种群的全局最优值，则取代震荡搜索前种群的全局最优值成为新的全局最优值。

综上所述，算法的流程描述如下：

步骤1初始化种群及相关参数。种群规模N，每个粒子的维度D，种群的迭代次数Max DT，粒子区域震荡搜索次数RS；根据种群规模和维度随机生成种群，并确定每个粒子的局部最优位置和种群的全局最优位置。

步骤2根据公式（6）计算出每个粒子吸引子 pi的位置。

步骤3根据公式对粒子进行区域震荡搜索。

步骤3.1根据公式（7）计算出粒子每维的区域震荡因子 Δi，j(t)。

步骤3.2根据公式（8）计算出当前震荡次数时的震荡幅度 Δi，j(k)。

步骤3.3粒子的每一维按照公式（9）进行震荡搜索，并结合粒子的其他维度计算出粒子在该维度上最佳适应度值时的位置。

步骤3伪代码描述如下：

步骤4计算经过区域震荡搜索后的粒子适应度值，更新粒子的局部最优位置 pbi，更新全局最优位置gb。

重复计算步骤2至步骤4，直到满足迭代的次数。

4 仿真实验

为了验证RSPSO算法的有效性和正确性，本文采用了表1中的经典测试函数来评价算法的性能，并与标准PSO算法及带有柯西变异的PSO算法[9]的测试结果作比较。

表1 经典测试函数及相关参数

表1中涉及的函数比较全面，有单峰函数(f1～f4)，同时也有多峰函数(f5～f8)。表中除 f6函数以外，其余的函数的理论最优值均为0，函数 f6的理论最优值为－418.982 9n，结合表中的具体维数，该函数的最优值为－12 569.5。算法参数设置为：f1～f3测试函数中，粒子种群规模N=10，f4～f8中，粒子种群规模N=50，粒子的维数和各维搜索范围参见表1，粒子群除 f4外迭代次数Max DT=100，优化 f4迭代次数Max DT=1 000，区域震荡搜索的次数RS=10。选取的几个测试函数分别对三种算法进行测试，为了减少偶然性，每个函数独立运行30次。取30次实验结果的平均最优适应度值和标准方差作为对比结果。

表2中的实验结果显示，RSPSO算法相比另外两个算法在平均最优值和标准方差上都有显著的提升，尤其在 f1～f2的函数寻优中，结果提升了100多个数量级，f3也有着很大程度的改善。 f4函数的最小值位于非常狭窄的一个条带上，沿着这一条带，函数变化非常缓慢。从结果来看，RSPSO算法在 f4上虽标准方差有所不及，但平均最优值却得到提升。平均最优值结果的对比中显示出RSPSO算法有着更高的收敛精度，标准方差结果的对比中显示出RSPSO算法有着更高的稳定性。由此可见算法能够有效地摆脱局部极值，避免陷入早熟，有着很强的全局寻优能力。从实验结果来看，算法在单峰连续函数的寻优中，有着很强的全局寻优能力。

表2 算法在 f1～f4上的平均最优值和标准方差

表3中的测试函数变量的维数都是30维，种群规模N=50。 f5～f8为多峰函数，相比单峰函数寻优，多峰函数寻优，算法更易局部收敛，陷入早熟。从实现结果看，RSPSO有效避免了陷入局部极值。 f5的寻优结果得到长足的改善，f6的寻优结果虽不及HPSO但是相比PSO也有着长足的进步，f7和 f8更是达到了Matlab的最小精度值，显示为0。由此可以得出，RSPSO在多峰连续函数中也有着很强的全局寻优效果。

表3 算法在 f5～f8上的平均最优值和标准方差

图1 HPSO算法在 f1和 f3上的进化曲线

图2 RSPSO算法在 f1和 f3上的进化曲线

图3 HPSO算法在 f5和 f7上的进化曲线

HPSO的时间复杂度为O(N×D×Iter max)，其中，N为粒子群规模，D为粒子维数，Iter max为迭代次数。RSPSO提出了区域震荡搜索思想，即粒子在每次迭代的过程中，嵌套搜索周围区域，粒子每震荡搜索一次，其作用就相当于HPSO迭代搜索一次，由于嵌套搜索次数的存在，所以粒子群整体的搜索次数为Max DT×RS，其中：Max DT为RSPSO的迭代次数，RS为嵌套震荡搜索的次数。为保证粒子群搜索次数和时间复杂度与HPSO算法的一致，就不能将RSPSO的迭代次数设置和HPSO算法的一样，否则算法在对比中参数设置就不一致了，故将迭代次数设置为Max DT=Iter max/RS，这样保证了算法对比的公平性。文献[9]中的算法的迭代次数设置为1 000，为保证算法对比中参数一致，本文中算法震荡搜索次数RS=10，故RSPSO算法的迭代次数应设置为1 000/10=100，由于算法的迭代次数不同，故不同算法对同一函数优化的结果不能放在同一张图中显示，本文将结果分开展示。

图4 RSPSO算法在 f5和 f7上的进化曲线

图1 和图2为文献[9]中HPSO和RSPSO算法在 f1和 f3上的进化曲线，图3和图4为两种算法在 f5和 f7上的进化曲线。横坐标为进化次数，纵坐标为粒子适应度值的lg对数。虽然分开显示，但是从图上还是可以很直观地看出，RSPSO算法在单峰和多峰函数的优化效果上，从进化一开始就显示出强大的寻优能力，整体在收敛精度和速度上得到实质性的提升。尤其在 f7的寻优上，寻优结果超出了Matlab最小精度值，显示为0，因为纵坐标为粒子适应度值的lg对数，所以后期曲线无法显示。

5 结束语

RSPSO算法将粒子吸引子位置和区域震荡搜索操作结合，在保证了粒子群强大的全局寻优能力的基础上，增加种群的多样性，有效避免了种群陷入局部极值，产生早熟现象。通过实验验证了算法无论在单峰还是多峰连续函数上都有着突出的寻优效果。RSPSO算法涉及的参数比较少，相比SPSO没有速度向量，实现起来比较简单。将改进的算法应用于实际工程中，在实用中检验RSPSO的性能将是本文下一步研究重点。

[1]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings IEEE International Conference on Neural Networks，1995：1942-1948.

[2]Vasant P，Ganesan T，Elamvazuthi I.An improved PSO approach for solving non-convex optimization problems[C]//2011 9th International Conference on ICT and Knowledge Engineering，2012：80-87.

[3]徐刚，黄先玖.一种粒子群优化的神经网络综合训练算法研究[J].计算机工程与应用，2011，47（11）：37-38.

[4]朱文斌，许晓飞.基于混合粒子群算法的保障资源优化研究[J].计算机工程与应用，2012，48（29）：210-213.

[5]彭力，王茂海.基于前馈扰动的粒子群改进算法[J].控制工程，2012，19（1）：102-105.

[6]姜伟，王宏力，何星，等.基于适应度反馈作用的PSO算法改进[J].计算机工程，2012，38（22）：146-150.

[7]王兴元，张鹏.基于细致化仿生的改进粒子群优化算法[J].系统工程与电子技术，2012，34（7）：1484-1492.

[8]Clerc M，Kennedy J.The particle swarm：explosion，stability，and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6（1）：58-73.

[9]Wang H，Liu Y，Li C H，et al.A hybrid particle swarm algorithm with cauchy mutation[C]//Proceedings of IEEE Swarm Intelligence Symposium，2007：356-360.