粒子群算法的惯性权重调整策略

粒子群算法的惯性权重调整策略

李丽1 薛冰2 牛奔3

1深圳大学管理学院信管系，广东深圳 （518060）

2深圳大学管理学院信管系，广东深圳 （518060）

3深圳大学管理学院信管系，广东深圳 （518060）

E-mail（小五，Times New Roman）

摘 要：惯性权重是粒子群算法改进的一个重要出发点，通过调整惯性权重可以大大提高算法的性能。本文在介绍粒子群算法原理、流程的基础上，分析了惯性权重在算法寻优过程中的重要作用，然后归纳了运用不同方法对惯性权重的改进，进行了简单的讨论，并对下一步工作进行了展望。

关键词：粒子群算法 惯性权重 改进策略

1 引言

粒子群优化算法（Particle Swarm Optimization，PSO）是1995年由Eberhant和Kennedy在文献[1]中提出的一种基于群体智能、自适应的搜索优化方法。其基本思想源于对鱼类、鸟类等群体社会行为的观察研究。粒子群算法提出以后，由于其算法概念简单、需要调整的参数较少、容易实现和快速收敛能力，已被广泛地用在科学和工程领域，如电力系统优化（文献[31]—[33]）、TSP问题(文献[34])、神经网络训练(文献[35])、函数优化(文献[37]、[38])等。

粒子群算法在应用过程中体现出了很强的寻优能力，但与其他全局优化算法相同，粒子群算法也存在早熟局部收敛和后期震荡现象。针对这些问题，国内外学者经过大量研究工作，提出了多种改进方法，包括参数改进，拓扑结构改进和混合算法等。其中惯性权重是最重要的可调整参数，惯性权重由于其概念简单、容易理解、改进的方法较多、改进的空间较大且容易实现等特点，成为很多学者研究的焦点。通过调整惯性权重的值可以实现全局搜索和局部搜索之间的平衡：较大的权值有利于提高全局搜索能力，而较小的权会提高局部搜索能力。诸多研究者运用线性递减、非线性递减等方法对惯性权重进行调整，实现了算法在不同方面和不同程度上的改进。本文通过对国内外研究人员所提出的调整惯性权重策略进行归纳总结，讨论了各种策略的优缺点，并在此基础上提出了下一步工作方向及需要解决的问题。

2 基本粒子群算法

在粒子群算法中，每个寻优的问题解都被想像成一只“鸟”，也称为一个没有重量和体积的粒子，每个的粒子在n维搜索空间里飞行，并有一个速度决定其飞行的距离与方向，所有粒子都有一个适应值函数来判断其目前位置的好坏，且在飞行过程中，每一个粒子都是具有记忆性的，能记得所搜寻到的最佳位置。

因此，在飞行过程中，每一代都能找出两个“极值”：每一个粒子到目前为止的搜寻过程中最优解，代表粒子自身认知水平，称之为个体极值Pbest；所有群体中的最优解，代表社会认知水平，称之为全局极值Gbest。粒子群算法首先初始化一群随机粒子，然后根据两个“极值”通过更新迭代找到最优解，其基本迭代方程如下：

))((()))((())()1(21txprandctxprandctVtVidgdidididid （1）

)1()()1(tVtxtxiii （2）

其中，idv表示粒子i在第d维的速度，n维向量),,()(21iiniixxxtx表示迭代到第t代时粒子i的位置，n维向量),,()(21iniiivvvtv表示粒子i的速度。1c、2c是学习因子，()rand是均匀分布于[0,1]之间的随机数，idp表示个体极值Pbest，gdp表示全局极值Gbest。为了防止)(txi溢出，设置maxv来控制)(tvi的范围：

maxmaxmax)(.................)(.......).........()(VtVVVtVtVtViiii （3）

具体算法流程如下：

(1) 初始化所有微粒(群体规模为N,在允许范围内随机设置微粒的初始位置和速度,并将各微粒的idp设为初始位置,取gdp为idp中的最优值。

(2) 评价每个微粒的适应值,即分别计算每个微粒的目标函数值。

(3) 对于每个微粒,将其适应值与所经历过的最好位置idp的适应值进行比较,若较好,则将其作为当前的最优位置。

(4) 对于每个微粒,将其适应值与群体所经历过的最好位置gdp的适应值进行比较,若较好,则将其作为当前的全局最优位置。

(5) 根据速度和位置更新方程对微粒的速度和位置进行更新。

(6) 如未达到结束条件,通常为足够好的适应值或是达到一个预设的最大迭代代数,则返回第（2）步。

具体算法流程图如下：

是 微粒适度值评价 开 始

微粒群体初始化

计算个体历史最优值和全局最优值

根据速度和位置更新方程更新微粒速度和算法结束 满足终止条件？ 否 3 惯性权重的提出

经过大量的研究试验，为了提高基本粒子群算法的收敛性能和避免算法陷入局部最优，Y.Shi和R.C.Eberhant于1998年在《A modified particle swarm optimizer》（文献[2]）一文中提出了惯性权重这一概念，在进化方程（1）中引入惯性权重因子w，即：

))((()))((())()1(21txprandctxprandctwVtVidgdidididid （4）

等式右边的结构和（1）式一样，第一部分是粒子先前的自身速度，用来保证算法的全局收敛性；第二和第三部分是引起微粒速度变化的社会因素，使算法具有局部搜索能力。所以w起到了一个平衡全局搜索能力和局部搜索能力的作用，w值较大时全局搜索能力强，局部搜索能力弱；w值较小时，反之。恰当的w值可以提高算法性能，提高寻优能力，减少迭代次数。

惯性权重的引入，对粒子群算法的发展起到了很大推动作用，大大拓展了算法改进的空间。但是要达到算法性能最优还存在很多缺陷，因为当w值较大时，有利于全局搜索，虽收敛速度快，但不易得到精确解；w值较小时有利于局部搜索和得到更为精确的解，但收敛速度慢且有时会陷入局部极值。如何寻找合适的w值使之在搜索精度和搜索速度方面起恰当的协调作用，成为很多学者研究的一个新方向，通过几年的发展，已有了不少研究成果。

4 惯性权重调整策略

基于研究各种问题的复杂性和惯性权重在算法迭代过程中所起到的平衡作用，除了固定惯性权重以外，学者们还提出了很多种惯性权重调整策略，主要有线性递减策略、非线性递减策略和自适应调整策略等以下几种：

4.1 线性递减策略

由于在一般的全局优化算法中，总希望前期有较高的全局搜索能力以找到合适的种子，而在后期有较高的开发能力，以加快收敛速度，所以惯性权重的值应该是递减的。其中的线性递减策略主要有以下几种：

4.1.1典型线性递减策略

Y.Shi和R.C.Eberhant在文献[2]还中提到了w应是随着进化线性递减的。这是首次提出的惯性权重递减策略，我们称之为典型线性递减策略，w的计算公式如下：

ttwwwtwmaxminmaxmax)( （5）

其中maxw、minw分别是w的最大值和最小值；t、maxt分别是当前迭代次数和最大迭代次数（全文中符号表示意义相同）。文献[9]试验了将w设置为从 0.9 到 0.4 的线性下降，使得PSO 在开始时探索较大的区域，较快地定位最优解的大致位置，随着w逐渐减小，粒子速度减慢，开始精细的局部搜索。该方法使 PSO 更好地控制全局搜索能力和局部搜索能力，加快了收敛速度，提高了算法的性能。

这种典型的惯性权重线性递减策略在目前是应用最为广泛，但是由于这种策略下，迭代初期全局搜索能力较强，如果在初期搜索不到最好点，那么随着w的减小，局部搜索能力加强，就易陷入局部极值。

4.1.2线性微分递减策略

为了克服典型线性递减策略的局限性，文献[14]中提出了一种线性微分递减策略，惯性权重的计算公式如下：

ttwwdtdwmax2minmax)(2 （6）

22maxminmaxmax)()t(ttwwww （7）

通过对w变化方程及实验结果进行分析，由于在算法进化初期w的减小趋势缓慢，全局搜索能力很强，有利于找到很好的优化种子，在算法进化后期，w的减小趋势加快，因此一旦在前期找到合适的种子，可以使得算法收敛速度加快，在一定程度上减弱了典型线性递减策略的局限性，相应地在算法性能提高上有了很大改善。

4.2非线性递减策略

4.2.1 带阀值的非线性递减策略

惯性权重线性递减策略经过不断改进，已经比原始的惯性策略有了很大改善。但是由于其线性递减的特征，对于很多问题，在迭代过程中，算法一旦进入局部极值点邻域内就很难跳出来，为了克服这种不足，文献[18]在典型线性递减策略的基础上引入了递减指数和迭代阀值0T，提出了一种惯性权重的非线性递减策略，即：

)()11()(minmax0maxwwTtwtw （8）

此时参数集变为{，maxw、minw、0T}，当迭代次数到达0T时，令max)(wtw，并保持到搜索结束，整个迭代过程由于的引入，)(tw随着t的增大而非线性递减，有利于跳出局部极值点。迭代初期w较大，粒子以较大的飞行速度遍布整个搜索空间从而确定最优值的大概范围，随着迭代的进行w非线性减小，大部分粒子的搜索空间逐渐减小，并且集中在最优值的邻域范围内；在迭代末期当达到迭代阀值时，将惯性权重限定为maxw，粒子以近乎不变的飞行速度在最优值邻域范围内找到全局最优解，有利于提高算法的收敛速度，尤其对于低维测试函数，无论在搜索最优值精度、收敛速度还是在稳定性方面都有明显的优势。 4.2.2先增后减策略

针对递减策略中仍然存在的不足，文献[16]提出了一种具有先增后减惯性权重的微粒群算法，w的惯性权重计算方程如下：

15.0...........4.115.00..............4.01W(t)maxmaxmaxmaxtttttttt （9）

文献[16]经过试验研究，这种先增后减的惯性权重，在前期有较快的收敛速度，而后期的局部搜索能力也不错，在一定程度上保持了递减和递增策略的优点，同时克服了一些缺点，相对提高了算法性能。

此外，国内还有人提出了其他的非线性动态递减惯性权重，如文献[19]中提出依据下式来计算惯性权重的方法：

max2/111minmax)()(ttdedwwtw （10）

其中1d，2d为控制因子，目的是为了控制w在maxw和minw之间。经过大量实验证明当2.01d，7.02d时算法的性能会大大提高。

4.3自适应动态改变惯性权重

4.3.1依据早熟收敛程度和适应值进行调整

以上的惯性权重调整策略都是依据迭代次数的递增而递减的，文献[20]提出了一中自适应调整策略，根据群体早熟收敛程度和个体适应值的来确定惯性权重的变化。设粒子ip的适应值为if，最优粒子的适应值是mf粒子群的平均适应值是niifnf1avg1；将优于avgf的适应值求平均得到'avgf； 且定义avgmff'。依据if、'avgf和avgf将群体分为3个子群，分别进行不同的自适应操作。则其惯性权重的调整如下：