基于不平衡权重和分布更新规则的粒子群算法∗

李克文 陈振文

（中国石油大学（华东）计算机与通信工程学院 青岛 266000）

1 引言

许多控制和决策问题可以转化为优化问题，随着技术的发展，工程实践中遇到的许多问题变得越来越复杂，而一些传统的计算方法往往需要优化函数连续、可微等条件，由于传统计算方法的局限性，许多元启发式算法被设计成求解困难优化问题的满意近似解。

在元启发式优化算法的研究中，群体智能算法是最活跃的领域之一，一些著名的群体智能算法也因此被提出，其中粒子群优化算法是通过受鸟类或鱼类的社会行为启发，由Kennedy，J等在1995年提出的［1］。与其他群体智能算法相比，由于其概念简单，易于理解和实现，在解决许多现实世界问题方面具有良好的性能而受到广泛研究和关注［2］，许多的变体也因此被提出，例如为了防止粒子的早熟收敛，文献［3～4］提出了粒子群算法的一种变体，在更新粒子当前位置的同时，粒子的速度会受到种群gBest、个体pBest、和随机选择其他粒子pBest 的影响；文献［5］提出了对种群的全局最优解gBest进行扰动以减缓种群多样性的丧失；文献［6］根据粒子性能和距离最优位置的远近来确定每一维的惯性权重值，提出了一种新的基于稳定性自适应惯性权重的粒子群优化算法；文献［7］将粒子分为不同的角色以完成不同的搜索分工并且根据距离最优值的远近来动态调整加速系数和惯性权重的大小，以此来改善种群的进化速度；文献［8］在粒子群算法中引入了社会学习机制，利用粒子群的全局最优粒子和其它更优的粒子来引导粒子的飞行；文献［9～10］通过将种群分为多群并利用种群之间的信息交换来平衡算法的探索能力和开发能力；文献［11］提出了一种基于交叉操作的粒子群算法，在保持很好差异性的同时通过对每个粒子的个体最优位置进行交叉，构造出有效的引导样本，进而利用这些高质量的样本来指导粒子群的进化；文献［12］利用粒子的当前位置Xi，个体最有位置pBest 和全局最优位置gBest三者的均值和方差基于正态分布来构造新解，以此改善了种群的早熟收敛、停滞现象。此外还有粒子群优化算法与其他群智能算法的结合，例如文献［13］结合了遗传算法和粒子群算法并将其用在了聚类上；文献［14～18］混合了粒子群算法和人工蜂群算法，利用各自的优势来提高混合算法的性能；文献［19］混合了粒子群算法和烟花算法并将其用在了全局优化上；文献［20～21］结合了粒子群算法和萤火虫算法等。

在这些粒子群算法中大多数都是基于粒子的最优值与当前位置的差值来更新位置的，这种基于差值的更新规则使得种群在迭代后期大多数的粒子都聚集在同一搜索范围内，此时算法很难再产生跳出这一局部范围的新解，因此种群出现停滞行为。本文在基于分布更新规则的基础上引入了不平衡权重策略和局部搜索的方式，在改善了种群停滞现象的同时加快了算法的收敛速度。理论分析和实验结果表明，本文算法有较好的综合性能。

2 基于不平衡权重和分布更新规则的粒子群算法

2.1 标准粒子群算法

粒子群优化算法是一种基于种群的全局优化算法，在标准粒子群算法中，粒子群由N 个粒子组成，粒子搜索的过程被形象化为解的寻优过程，每个粒子位置表示D维搜索空间中的一个可行解，解的质量由目标函数值或适应度函数值来评估。每个粒子用pBest 记录自己曾经寻优过的最优位置，gBest 表示目前种群寻找到的最优位置，每个粒子在现有速度Vi的基础上根据自己的位置Xi、pBest和gBest 来更新速度值，然后粒子利用更新后的速度值来更新自己的位置。

标准粒子群算法的主要步骤如下。

初始化：初始化各种参数，如最大迭代次数IterMax，惯性权重值ω，学习因子C1和C2等；利用式（1）在D 维空间内随机生成N 个解，Xi=(，…，)表示第i个解的位置。

其 中i = 1， 2， … ， SN ，j = 1， 2， …， D ，是第j 维位置的下界值，为第j 维位置的上界值，rand 是［0，1］内均匀分布的随机数，(0)表示第0代第i个解的第j维。

利用式（2）初始化粒子的速度。

分别利用式（3）和式（4）初始化pBest 和gBest，在初始化阶段，pBest 为第0 代时的粒子值，gBest 为所有粒子中的最优值。

其中i = 1， 2，… ， N ，j = 1， 2， … ， D，f（Xi）表示第i 个粒子的目标函数值，以寻优最小值为例，argmin（）函数返回具有最小目标函数值粒子的位置Xi给gBest。

以后每代粒子的速度和位置分别按照式（5）和式（6）进行更新。

其中ω为粒子的惯性权重，表示粒子具有一定保持原来速度的能力，C1、C2为学习因子，分别表示粒子对自我和对群体的认知程度。

在完成位置更新后，粒子利用式（7）来对pBest进行更新，种群利用式（8）来对gBest进行更新。

种群中的所有粒子都跟随着种群的个体最优和全局最优来调整速度进而更新自己的位置，通过权重ω来控制粒子惯性的大小，通过学习因子C1和C2来控制对自我认知和对社会认知的比例。在利用式（1）～（4）初始化粒子后，种群就利用式（5）～（8）迭代运行，直到满足终止条件为止。

2.2 基于不平衡权重和分布更新规则的粒子群算法

在标准粒子群算法中粒子位置是基于pBest、gBest 与当前位置的差值而产生的，所有个体都追随个体最优值pBest 和全局最优值gBest 而去，这种产生新解的方式使得种群多样性下降较快而标准粒子群算法又缺少跳出局部最优解的能力，因此在种群进化到一定代数时，种群易出现进化停滞不前的现象，当粒子位置Xi和个体最优pBest、全局最优gBest 距离较近时，这种基于差值生成新解的方式将很难再产生新解。基于此文献［12］提出了一种新的更新机制，利用Xi、pBest和gBest三者的均值和方差基于正态分布来产生新解，以此改善了种群的停滞现象；而本文则在此基础上依据Xi、pBest 和gBest 三者的适应度值采用不平衡权重的策略来生成均值和方差进而基于正态分布产生新解，以此加快种群的进化速度；另外，在包含所有粒子的种群完成一次全局搜索后，种群依据每个粒子的适应度值采用轮盘赌选择的方式再进行一次局部搜索，以使得较优的粒子得到更多的进化次数，所提算法的具体内容如下。

在本文提出的算法中，增加了计算粒子适应度值和轮盘赌机制选择的步骤，如式（9）和式（10）所示。

其中fi表示第i 个解的目标函数值，fiti表示第i个解的适应度值，abs（）是绝对值函数。

其中Pi表示第i个粒子被选择的概率。

粒子的位置更新方式更改为如下：

其中m 为粒子位置Xi、pBest 和gBest 三者依据适应度比计算出来的均值，计算如式（12）、（13）所示；s 为三者的标准差计算如式（14）所示，Z 的计算方式如式（15）所示。

其中r1、r2是属于［0，1］内均匀分布的随机数。

在种群进行一次全局搜索后：即种群中的每个粒子都进行了一次位置更新。种群利用式（9）和式（10）得到的选择概率逐个可重复的选出要进化的粒子再进行位置更新，粒子被选择的概率和适应度值成正比，搜索的次数往往为粒子的数目N。相比较全局搜索而言，这是一种和粒子质量相关的局部搜索，适应度较大的粒子可以得到更多的进化机会。改进后算法的详细步骤如下。

步骤1：初始化阶段

初始化各种参数，利用式（1）、式（2）、式（3）和式（4）分别初始化粒子的初始位置、初始速度、初始个体最优解pBest以及种群最优解gBest。

步骤2：全局搜索阶段

每个粒子利用式（11）更新自己的位置。

步骤3：最优值更新阶段

利用式（7）和式（8）更新粒子的个体最优解pBest和种群的全局最优解gBest。

步骤4：局部搜索阶段

利用式（10）产生的选择概率随机选择一个粒子，使其利用式（11）更新自己的位置，然后同样利用式（7）进行个体最优解pBesti的更新；另外，若其优于全局最优解gBest 则对gBest 进行更新。本步骤迭代进行N次。

步骤5：判断是否满足终止条件

如果满足终止条件，则输出最优值和最优解并退出，否则返回步骤2。

在基于不平衡权重和分布更新规则中，若种群中的粒子收敛于种群的当前最优解gBest，则Xi，pBesti，gBest 位于同一位置上，由此生成的标准差s为0，此时利用式（11）生成的新解与旧解位置相同，无法再产生不同于旧解的新解。为避免此现象的发生，我们设置一个阈值TSD，当s 小于TSD 时，s取值为均值m的一半。

基于正态分布产生新解的方式改善了标准粒子群算法因种群多样性的丧失而导致算法易进化停滞的现象，而不平衡权重的策略进一步使得产生的新解有偏向较优解进化的趋势，另外局部搜索方式的加入使得较优的粒子得到更多的进化机会，也加速了种群的进化。

3 仿真实验分析

为了验证所提算法，如表1 所示，本文选取了具有代表性的10 个基准函数来验证算法的收敛精度和稳定性等性能，其中，sphere 函数、rosenbrock函数、sumSquares 函数、sumPower 函数、quartic 函数为单峰函数，schwefel2.26 函数、rastrigin 函数、ackley函数、griewank函数、levy函数为多峰函数。

为了对比实验本文选取了标准粒子群优化算法SPSO 和PSOd 算法［12］作为对比算法，其中PSOd算法是近来经常被用来比较的优秀算法；标准粒子群优化算法粒子的数量设置为40，惯性权重ω从0.9 随着迭代次数的增加线性递减到0.4，学习因子C1和C2设 置 为1.5；PSOd 的 粒 子 数 目 同 样 设 置 为40；由于本文算法加入了局部搜索且局部搜索的次数为种群粒子的数目，为了公平比较，保证在一次迭代中的函数评估次数也为40，本文算法的粒子数量设置为20；算法的最大迭代次数IterMax 由公式（16）确定：

其中FEperIt 表示种群每进化一代函数的评估次数，D 表示求解问题的维数。除了上述参数外，PSOd和本文算法中的TSD设置为1e-5。

表1 基准函数

3.1 算法的收敛精度和稳定性分析

为了减少算法的随机性影响，每个算法在每个测试函数的30 维上独立运行30 次，然后求其平均值和标准差来分别验证算法的收敛精度和稳定性，结果如表2 所示，最优结果加粗显示，其中uwdPSO表示本文算法。

表2 D=30维时的测试结果

由表2 可知：本文算法在函数f6上的寻有结果略差于PSOd算法但依旧明显优于SPSO算法，另外本文算法的标准差最小，表明了本文算法寻优的稳定性；在函数f1、f4、f5、f7、f8、f9上取得了和PSOd 对等的寻优结果；除此之外，本文算法在函数f2、f3、f10上都取得了明显的最优收敛精度以及最可靠的稳定性；另外，PSOd 算法在函数f10上的寻优结果差于SPSO算法，在其余函数上也都优于SPSO算法。

3.2 算法的收敛速度分析

在函数f1、f4、f5、f7、f8、f9上算法PSOd 都和本文算法uwdPSO 取得了相同的寻优结果，为了进一步对比，我们给出了它们的收敛曲线如图1所示。

图1 部分收敛曲线图

通过图1 可知，在f1、f4、f5、f7、f8、f9函数上本文所提算法的收敛速度要远远快于PSOd 算法，这是因为在搜索过程中，我们依据粒子的适应度值基于不平衡的策略来分配权重以获得均值μ和标准差σ，使得产生的新解有靠近较优解的趋势，加速了种群的进化，另外在进行完全局搜索后，根据个体适应度值依据概率选择要进化的粒子对种群进行局部搜索的方式也提高了算法的收敛速度。

通过对本文所提算法收敛精度、稳定性和收敛速度的分析表明：本文算法具有较好的综合寻优性能。

4 结语

针对标准粒子群算法种群多样性下降较快导致种群进化易出现早熟、停滞现象以及进化速度缓慢等不足，本文提出了一种基于不平衡权重和分布更新规则的粒子群算法。在分布更新规则的基础上引入了不平衡权重策略以使产生的新解有快速朝向较优解进化的趋势，提高了算法的收敛速度；此外，局部搜索机制的加入给予适应度较大的粒子更多进化的机会，也加速了种群的进化。最后在10 个经典基准测试函数上的测优结果表明了本文算法具有较优的收敛精度、可靠的稳定性和较快的收敛速度，是一个优越的寻优算法。