基于排斥作用的改进粒子群算法

杨洪涛 丁烽

（第七一五研究所，杭州，310023）

粒子群优化算法（Particle Swarm Optimization，PSO）是由 Kenedy和Eberhart 于1995年提出的一种基于集体演化的随机搜索优化方法[1]。算法的基本思想是模仿鸟群的觅食特性，是群体中个体之间信息的社会共享和协同进化。PSO在诸多优化领域取得了比较成功的结果，例如函数优化[2]、系统辨识[3]、人工神经网络的训练[4]等。但是PSO容易发生早熟收敛而陷入局部最优和在最优值附近收敛缓慢。学者对于粒子群算法进行了改进：引入动态参数修正策略，对演化方程加入随机扰动策略，而后其他算法进行融合，以及将以上改进相互混合。文献[5]提出了基于自适应观点的惯性权重改进方式。文献[6]考虑前两代位置对速度方程进行改进。文献[7]消除了方程的粒子速度项而使得原来的二阶微分方程简化为一阶微分方程，避免有粒子速度项引起的粒子发散而导致收敛慢、精度低的问题。通过分析我们发现，粒子群算法对于初值的选取十分敏感，当粒子集中于求解区域一端时间，对于另一端的空间的探测能力较弱，这极大的影响了粒子群算法的求解能力，尤其在求解空间较大且较为复杂的情况下。针对这一情况本文提出具有斥力-引力作用的粒子群优化算法，使得粒子在下一步迭代过程中，主动避开已有粒子的探测具有增大粒子的空间拓展能力，降低算法对于初值的依赖性。

1 标准粒子群优化算法

1.1 算法描述

假设在一个D维的空间进行搜索，粒子种群X有n个粒子，表示为(X1,X2,…Xn)，其中第i个粒子表示为一个D维向量Xi=(x1,x2,…xD)T，为搜索空间的一个探索解。根据目标函数即可算出每个粒子当前位置的适应度值。第i个粒子的速度为其个体经验极值为种群的群体经验极值为

在每个迭代过程中，粒子通过自身初始运动速度、自身经验极值和群体经验极值协同决定下一次的运动速度。并更新运动位置以及运动速度

其中，ω为惯性权重；k为当前迭代次数；Vid为粒子的速度；c1和c2是非负常数，称为加速度因子；r1和r是分布于[0,1]区间的随机数。

1.2 算法伪代码

经典粒子群算法的通过迭代更新速度矢量和位移矢量（Algorithm 1:10-11），并通过不断将粒子群当前状态与历史状态的个体最优中和群体最优，使得群体最优值逐步收敛到全局最优值（Algorithm 1: 6-7），伪代码如下

2 改进模型

2.1 模型背景

我们通过对于鸟群觅食过程的分析可以发现，初期阶段，每只鸟由于自身的“好奇心理”都会主动探索无“鸟”区域，并努力避开其他鸟类的探索位置，这种“好奇心理”使得种群更加快速高效全面的探索觅食区域。而随着觅食时间的延续，“好奇心理”逐渐减弱。在觅食后期，鸟群更倾向于回归种群，并在回归过程中继续探索觅食区域。次过程可以抽象为粒子间的吸引排斥作用。由经典的分子力学可知，分子间同时存在吸引作用与排斥作用，这样可以使得每个分子在自己的工作区域内保持振动。我们将经典的斥力作用和引力作用引入模型。

2.2 数学模型构造

将单个个体在初期搜索阶段的排它性表现为对于附近个体的斥力作用，并且要求当两个个体越近时斥力表现越明显。在此基础上，斥力作用应当随着探索时间的延长逐渐减弱并且逐步转化为引力作用。通过公式可以表示为：

其中：c3为某正常数参数；r3是分布于[0,1]区间的随机数；Rn为衰减项，满足n=1时R1=1，当n达到最大迭代次数为第i个粒子和第j个粒子间的距离；为第i个粒子和第j个粒子间的位移差。由于斥力项具有较强的非线性结构，斥力项的影响力强弱依赖于的选取，为了使得粒子群系统能够稳定迭代，在c3选取时应使其远小于c1、c2。

图1 粒子斥力作用图

粒子斥力作用示意图见图1。斥力因素的引入可以使得粒子更快的拓展求解区域，降低由于粒子的聚集状态所导致的局部最优。而后期引力因素将提高粒子群局部搜索能力并提升收敛速度。在此基础上，有别于传统粒子群算法对于初值的敏感性，新的粒子群算法对于初值的选择并不敏感。即便初始粒子选择区域较小，由于互斥效应的影响，粒子群也将向着为空旷区域逐步扩散。

2.3 改进PSO算法

由于互斥效应的引入，粒子迭代公式变为：

2.4 改进算法伪代码

在粒子群算法基础上为使得粒子群在初始阶段能够快速扩张求解区域，我们在经典算法中加入了斥力作用项(Algorithm2, 8)， 并使得斥力在粒子的速度迭代中发挥作用(Algorithm2, 12)。

3 算法仿真

为了比较改进算法的性能，选取了如下8个标准测试函数。

表1 算法性能对比

我们采用经典的 LPOS（Linear Weighted Particle Swarm Optimization） 、QPOS（Quantum Particle Swarm Optimization） 和 IAPOS（Improved Adaptive Swarm Optimization） 作为比较算法，并分别设定搜索算法的维度为10和20做比较，见表1。通过比较我们可以得出改进算法对于高维问题具有较好的收敛性。

4 结束语

传统的粒子群算法由于初值的随机选取使得，当粒子位置初始化比较集中时，粒子对于为探测区域的扩张性较差，而斥力项的引入使得，粒子可以主动拓展为探测区域。仿真结果表明，改进的粒子群算法对于初值的依赖性较低，对于大范围且具有多局部最优值的优化问题具有较好的全局收敛性。本文方法可应用于线性优化、非线性优化等数学经典问题，同时也可应用于信号处理、深度学习等工程问题，具有较好的应用前景。