基于局部远亲差分增强的扰动粒子群优化算法

王永贵，胡彩云，李 鑫

(辽宁工程技术大学软件学院，辽宁葫芦岛125105)

(*通信作者电子邮箱1581280425@qq．com)

0 引言

粒子群优化(Particle Swarm Optimization，PSO)算法是根据鸟类觅食、人类认知等社会行为提出的具有记忆功能的群智能进化算法，于1995年由Kennedy等［1］首次提出。该算法具有形式简洁、调参灵活、收敛快速等特点，受到学者广泛关注。目前PSO算法在多信道无线网络、煤与瓦斯的测量、焊接机器人路径规划等复杂优化实例中得到大量应用［2－4］。

PSO算法仅根据个体与群体经验调整自身状态，因此，个体间缺乏联系，易逐渐丧失种群多样性，陷入局部极值，对全局最优解［5］搜索能力弱，在复杂多峰问题中早熟收敛问题尤为突出。为此学者们提出多种改进措施［6－7］:Li等［8］为避免粒子因单一学习模式使特定粒子缺乏智能，从而陷入局部极值，因此引入自学习粒子群优化(Self Learning PSO，SLPSO)算法，为每个粒子提供4种不同策略应对搜索空间中不同情况;van Zyl等［9］提出一种粒子群初始化策略解决高维问题，使粒子的搜索空间为一个子空间，而不是整个搜索空间;Guo等［10］在PSO算法中引入文化算法，群体的优化过程是由信仰与群体两层之间的演化与交流实现;高卫峰等［11］为加速算法跳出局部极值，仅对粒子搜索到的最优解利用人工蜂群算子进行搜索，并提出基于混沌和反学习的初始化学习方法，提高了全局搜索速度;夏学文等［12］为让算法较快逃离局部最优，根据较差粒子及每个粒子的历史较差位置信息指导粒子以较快的飞行速度进行反向学习，提高了算法的求解精度，保证了算法的收敛速度;王东风等［13］根据粒子适应值差异，提出一种对粒子位置进行高斯采样均值的自适应调整策略，增加粒子分布中心的分散度，减缓粒子在中心的聚集趋势，并提出“镜像墙”的越界粒子处理法，大幅提高了算法找到最优解的概率，同时为增加种群多样性，榜样粒子的选择由粒子不同进化时期的不同拓扑结构决定;周伟等［14］在标准粒子群基础上，选取精英粒子种群，构建精英粒子群－进化融合优化机制，并引入模糊高斯学习策略，提高了种群的多样性和寻优能力。

上述改进算法的性能皆有提高，但由于PSO算法本身的随机性，若仅对算法参数改进，搜索中仍具有不确定性且无法避免陷入局部极值;若与其他算法融合，种群的每次迭代都要进行种群重建、计算、比较、寻优，整个过程计算量大，影响算法的执行效率。

为更好地挖掘PSO算法的搜索能力，使算法在收敛速率和收敛精度上都达到理想状态，本文提出一种基于局部远亲差分增强的扰动粒子群优化算法(Perturbation Particle Swarm Optimization algorithm based on Local Far-neighbor Differential Enhancement，LFDE-PPSO)。LFDE-PPSO主要有以下改进:1)为避免随机初始化种群带来的无效解，提出半均匀式初始化种群，使种群既不丧失随机性又能相对均匀地遍布于搜索空间;2)为扩大粒子的搜索空间，增加解的多样性，引入扰动因子对惯性权重、学习因子进行扰动，实现智能搜索;3)为提高全局搜索速度，根据适应度值引入重构概率，选择部分较差个体构建中间种群;4)为避免遗失较差个体中的优秀基因，利用遗传学机理，防止“近亲繁殖”导致的无效操作，引入粒子不相关性，找到差分个体的“远亲”进行差分变异，增加种群多样性。

1 基本理论

1．1 粒子群优化算法

在PSO算法中，待优化问题的潜在解可看成N维搜索空间中的一个点，即为“粒子”。粒子在N维空间中搜索，则第i个粒子的速度及位置更新如下:

表1 基本PSO算法参数说明Tab．1 Basic PSO algorithm parameter description

1．2 差分进化算法

差分进化(Differential Evolution，DE)算法［15］是一种高效智能全局搜索算法，通过个体间差分、交叉、变异产生新个体，增加种群多样性，具备自学习、自组织、自适应和全局搜索能力强等特点。DE算法主要操作如下:

1)变异操作。

2)交叉操作。

2 局部远亲差分增强的扰动粒子群算法

2．1 半均匀式初始化

为避免随机初始化种群导致粒子初始化位置过于集中，不利于粒子的全局搜索，故采用半均匀式初始化种群，使种群既相对均匀地分布在整个搜索空间，又能保持种群的随机性、多样性。半均匀式初始化种群为:

其中:NP 为种群规模，i为第 i个个体，i=(1，2，…，NP/2);t为N维变量中第t个变量;t为第0代种群第i个粒子的第t个变量初始值。

2．2 扰动因子

在PSO算法的影响因子中，惯性权重ω是前一代粒子速度对当前粒子速度的影响系数，平衡全局与局部搜索。自我学习因子c1与社会学习因子c2影响系统张力，因而许多学者对影响因子进行了不同的改进:文献［5］采用了线性递减策略;文献［16］采用了非线性惯性权重递减策略;文献［17］提出了同步、异步的线性变换策略;文献［18］中在学习因子中融入惯性权重的影响因素实现异步变换;文献［19］采用反三角函数变换策略影响学习因子。

研究表明，对影响因子较好的改进方法是递变策略，但固定的变换形式并不利于个体在全局范围内搜索，间接影响种群多样性的保留。受自然界中蝴蝶效应的启发，初始条件下微小的变化能带动整个系统具有长期巨大的连锁反应，任何事物的发展都存在定数和变数。因此，本文引入扰动因子，让PSO算法的惯性权重和学习因子在整体递变的基础上，添加微小的变化，既防止粒子因位置变换引起速度较大的变动，又能保障影响因子在递变的趋势上，实现扰动，从而扩大解的搜索空间，使位置和速度呈现浮动式变换搜索，增加解的可能性。

本文扰动因子使用正余弦函数进行策略变换，因其函数值在［－1，1］变动，能够保障影响因子实现小范围内跳动。惯性权重、学习因子变换策略为:

其中:k为迭代次数;kmax为最大迭代次数;rand()为(0．9，1)的随机数;αk、βk分别为正余弦扰动因子;ωk是种群k次迭代的惯性权重;ωmax、ωmin是惯性权重可取到的最大值和最小值;c1，k、c2，k为 k次迭代过程中的自我学习因子、社会学习因子;c1s、c1e为自我学习因子的初始与最终值;c2s、c2e为社会学习因子的初始与最终值。

扰动策略在算法初期，能够使ω、c1取较大值，使粒子拥有较快的递减速率，促进粒子进行局部搜索，加快粒子向全局最优聚拢，并使粒子对自身具备较强的思考能力，鼓励粒子靠近曾发现的最优位置;算法后期ω递减速率降低，c2取值较大，促进粒子间进行信息共享，帮助粒子在局部搜索的过程中实现精细搜索，引导粒子逼近全局最优位置，保持搜索精度与速度之间的平衡。

2．3 局部远亲差分增强

PSO算法的整个寻优过程仅由个体和社会的历史最优位置迭代驱动，其所有操作都仅针对优秀个体，容易忽略群体中其他粒子信息，特别是较差个体，而较差个体与优秀个体中的优秀基因往往相差甚远，这就导致搜索过程中对种群多样性影响较大的优秀基因逐渐丢失，使种群易陷入局部极值而无法跳脱。为使中间种群中较差个体的优秀基因得以延续，本文根据遗传学“远亲繁殖，杂交出优势”，引入了粒子不相关性，由粒子不相关性计算选择概率，利用选择概率找出“远亲”进行杂交繁殖，有效保障优秀基因的传承，使种群在搜索过程中保持活力，避免算法陷入局部极值。

局部远亲差分增强策略首先利用重构概率根据轮盘赌选择适应度值低的个体重新构建中间种群;然后，在中间种群中随机选择差分个体，根据粒子的不相关性计算其余个体的选择概率，利用选择概率，从中间种群中找出两个与差分个体基因差异较大的临时个体进行差分变异，保留适应度值高的个体基因进入下一代种群。

1)重构概率。

为了使算法每次的搜索结果都能有效反馈给种群，让种群根据寻优结果进行相应的变换，实现自适应调整，因此，本文引入重构概率，即根据粒子的适应度值求出粒子被选中重新构建中间种群的概率。

其中:i=1，2，…，NP，NP为种群规模。式(11)表明当粒子适应度值越低，对应重构概率越大，即粒子被选择构成中间种群的可能性越大。

2)粒子不相关性。

其中:t=(1，2，…，n)，t为n维向量中具体的一维。式(12)表明，若个体间变量值差异性较大，则不相关性越大。

3)选择概率。

3 算法流程

步骤1 初始化 PSO 算法参数，(ωmin，ωmax) =(0．4，0．9)，(c1s，c1e)=(2．5，0．5)，(c2s，c2e)=(0．5，2．5)，种群规模NP，每维变量的上下界范围，粒子的最大飞行速度Vmax;最大迭代次数 kmax，变异算子 F=0．5，交叉概率 CR=0．9;

步骤2 由式(5)半均匀式初始化种群;

步骤4 FOR i=1，2，…，NP，计算个体适应度值与轮盘赌构建规模为(NP/3)的中间种群;

步骤11 若k≥kmax，则输出粒子所在位置的适应度值，否则重复步骤3～11。

4 实验及结果分析

为确保实验的公平性，本文所有实验均在Inter Core i5-2450M CPU 2．5 GHz，12 GB内存的机器上实现，软件运行的环境是Matlab 2014b。种群规模NP=30，变量维度N=30，最大迭代次数kmax=1000，每个测试函数单独运行30次，可接受误差为 0．1。

4．1 测试函数及评价标准

为验证扰动策略和局部远亲差分增强策略的可行性，本文选取了2个经典单峰函数与3个复杂多峰函数进行验证。函数的搜索空间与理论最优值如表2所示。其中函数1是带噪声的四次方缓动函数，最优值随随机分布数而改变，较难寻优;函数2是单峰非凸、较难极小化的典型病态二次函数，其最优值与多变量相关，搜寻难度较大;函数3、4、5都是旋转、不可分离的可变维三角多峰函数，具有大量局部最优点，算法在求解过程中容易逼近局部最优，难以寻到全局极值。

为评定算法性能，本文选用以下评价准则［19］:

1)成功率(SuccR):将适应度函数最终解达到误差允许范围内视为有效解，成功率为有效解次数占总执行次数的比例，用来衡量算法的鲁棒性;

2)平均最优值(MeanBst):算法30次独立运行结束后所得适应度函数的平均最优值，该指标可衡量算法的寻优质量;

3)最终适应度值(FinalBst):函数最终收敛时的最优值;

4)平均运行时间(MeanT/s):算法独立运行30次平均执行时间，是对算法寻优时效性的衡量;

5)稳定性(Stab):算法独立运行30次，所得精度标准差。

表2 测试函数信息Tab．2 Information of test functions

4．2 单项改进措施有效性验证

为验证LFDE-PPSO各个改进措施的有效性，先分别对单项改进措施进行验证。

1)扰动策略。为验证扰动策略PPSO(Perturbation PSO)可使粒子在搜索过程中有效降低粒子陷入局部极值的可能。这里将PPSO与基本PSO算法进行对比，采用测试函数f1、f5进行验证。结果如图1所示。

图1 函数收敛特性曲线Fig．1 Function convergence characteristic curves

从图1中可以看出，PPSO在单峰与多峰函数优化上，能够很快进入到全局最优状态，优化精度、速率明显高于基本PSO算法，充分证明扰动策略利于加快速度变换空间，避免粒子局部聚集，推动粒子在全局范围内搜索，有效保持种群的多样性，能够控制局部与全局间的搜索平衡。

2)局部远亲差分增强策略。为验证局部远亲差分增强(Local Far-neighbor Differential Enhancement，LFDE)策略能够增加PSO算法种群多样性，提高算法的收敛速度，帮助粒子逃离局部聚集状态，本文将 LFDE算法与基本PSO算法、DEPSO算法采用测试函数f2、f4进行验证，分别从以下两个方面进行比较:1)稳定性验证，比较3种算法在精度相同时适应度值方差;2)收敛速率验证，比较三种算法在函数评价次数相同时各自的收敛精度。实验结果如表3所示。

从表3可知，LFDE算法与传统PSO算法相比，在达到相同精度时，PSO算法在 f2、f4的 Variance是 LFDE算法的6．56E+02、3．44E+06 倍，在运行 10 000、20 000、30 000 次时，PSO算法在f2的适应度值分别是LFDE算法的1．35E+06、4．36E+05、5．96E+04 倍，在 f4的适应度值分别为8．05E+15、7．00E+15倍。与DEPSO算法相比，DEPSO算法在f2的三次适应度值分别是 LFDE 算法的 2．84E+05、4．08E+04、6．24E+02倍，在f4的适应度值分别为1．61E+12、4．84E+10倍。以上结果表明，LFDE算法与基本PSO、DEPSO算法相比，在收敛速率上明显提高。在稳定性方面，LFDE算法比PSO算法改善明显，但与DEPSO算法相比，没有明显优势，尤其在单峰函数的优化问题上，LFDE算法的适应度值方差是DEPSO算法的1．27倍，而在多峰函数上是DEPSO算法的39．79倍，说明在稳定性方面，LFDE算法在多峰函数的优化问题上仍具有一定优势。从上述实验结果可知，DEPSO算法与LFDE算法都能够维持种群多样性，这是由于DEPSO与LFDE算法都是通过交叉、变异产生新个体;但DEPSO算法每次迭代都通过DE与PSO算法生成两个种群，对这两个种群进行比较，择优选出Pbest与Gbest，因而算法整体计算量庞大，极大地降低了算法的收敛速率。

表3 3种算法多样性、速率比较Tab．3 Diversity and rate comparison of three algorithm

以上两个单项验证实验结果可以得出，本文提出的扰动策略和局部远亲差分增强策略，在算法的收敛速率和种群多样性的维持上都具有明显优势。

4．3 本文算法验证

为进一步验证LFDE-PPSO的优化性能，本文将LFDEPPSO 与标准粒子群算法(Standard PSO，SPSO)［20］，以及对PSO算法改进的混沌粒子群优化算法(Chaos PSO，CPSO)［21］、自调节粒子群优化算法 (Self Regulating PSO，SRPSO)［22］、交错搜索粒子群优化算法 (Crisscross Search PSO，CSPSO)［23］进行比较。表4、5分别为这5种算法对应单峰、多峰测试函数的实验结果，表5中的最后一项是5种算法在5个测试函数的4项评价准则的实验结果平均值。

表4 单峰函数算法性能比较Tab．4 Performance comparison of single-peak function algorithms

表5 多峰函数算法性能比较Tab．5 Performance comparison of multi-peak function algorithms

从表4、5中可知，上述几种算法对f5的优化效果都较为理想，是因为该函数当空间维数超过15维时，函数特性转变，趋向单峰函数，易找到最优值。SPSO算法在f1上的MeanT/s是LFDE-PPSO的11倍;由平均值中的MeanT/s比较可知，LFDE-PPSO分别是 CPSO、SRPSO、CSPSO 算法的23．68%、74．19%、93．7%，算法的执行效率得到极大的改善;在FinalBst上，LFDE-PPSO在平均值中是CPSO算法的99%，虽然SRPSO、CSPSO算法在FinalBst上均能达到函数对应的极值，但在MeanBst的平均值计算结果上，分别是SRPSO、CSPSO算法的4．84%、6．21%，LFDE-PPSO 依旧具有一定的优势。因而，从表4、5的各项验证结果可得出，LFDE-PPSO的寻优精度、速率以及算法的寻优质量明显优于 SPSO、CPSO、SRPSO、CSPSO 算法。

为进一步验证LFDE-PPSO在收敛精度和稳定性上的性能，分别对LFDE-PPSO与SPSO算法以及综合学习粒子群优化算法(Comprehensive Learning PSO，CLPSO)［24］、全 局 信 息 粒 子 群 算 法 (Fully Informed Particle Swarm，FIPS)［25］和 CPSO 算法进行比较。图2、3分别是算法在30次实验中，进行1 000次迭代的平均收敛特性曲线和标准差波动图，图中横纵坐标分别是收敛精度对数、标准差与迭代次数。

由于SPSO算法无法向局部其他粒子学习，易造成启发式信息和计算资源浪费，陷入局部最优，算法寻优质量较差;CPSO算法利用混沌映射创建初始种群，利用最优解附近混沌搜索结果替代种群中部分粒子，但CPSO算法是当种群陷入局部极值后，混沌搜索策略才开始生效，寻优过程中忽略其他粒子可能含有的先进基因，在多峰问题的求解上效果较差，从图2中可看出，当迭代次数达到500次时，适应度值曲线基本已停止寻优，陷入互补局部极值。CLPSO算法通过选择榜样粒子的学习策略能够改善PSO算法的性能，但该算法对多样性保留的机制过于强健，在复杂多峰优化上较为有效，而单峰问题上的求解效果并不理想，在单峰问题的求解质量上仅优于SPSO算法。FIPS算法利用邻域内所有成员最优加权平均值指导更新，结合周边粒子的信息，该算法在单峰函数优化问题上作用效果尤为明显，但该算法忽略个体差异性，因而在复杂多峰求解问题上效果较弱。从图2所有的函数适应度值曲线中可以看出，对于难以优化的高维函数，尤其是存在多个局部极值的多峰函数，SPSO、CLPSO、FIPS、CPSO算法寻优时易陷入局部最优，且粒子一旦陷入局部极值，则很难跳出，因此很难得到理想的效果，LFDE-PPSO根据粒子适应度值自适应的选择较差粒子重建中间种群，获取较差个体中优秀基因填充现有种群，丰富了种群的多样性。因此，在迭代的初期能够较快地逼近全局最优，在单峰及复杂多峰的问题求解上都能取得优质解。从图3的平均标准差波动趋向图可以明显得出，LFDE-PPSO与SPSO、CLPSO、FIPS、CPSO 算法相比具备较强的稳定性能。

图2 各算法收敛特性曲线对比Fig．2 Convergence characteristic curve comparison of algorithms

图3 各算法标准差波动对比Fig．3 Standard deviation comparison of algorithm

5 结语

本文提出了一种基于局部远亲差分增强的扰动粒子群算法，通过多角度对比仿真实验得出该算法具有以下特点:1)采用扰动策略，使惯性权重与学习因子在迭代过程中动态生成，并加以微小扰动，使粒子在有效位置和速度上实现跳动，扩大搜索范围，平衡全局搜索和精细搜索，促进粒子跳出局部极值;2)对新生种群中较为低质的粒子采用局部远亲差分增强策略，挖掘低质粒子中优秀基因，通过交叉变异保存下来，填充现有种群基因库，进而使种群富有活力，不易陷入局部极值进入早熟状态;3)仅对部分个体进行差分增强操作，避免种群大规模再生，重复计算，算法的收敛速度得到了极大的提升。因此，本文算法在处理较为复杂的优化问题上具有重要的实用价值。接下来，对于受参数影响较大的支持向量机优化问题上，利用LFDE-PPSO自动寻找支持向量机的最优参数，提高向量机的分类准确率与速率是下一步有待研究的问题。