基于动态分级和邻域反向学习的改进粒子群算法

任燕芝

(西安电子科技大学 数学与统计学院， 陕西 西安 710126)

智能优化算法是建立在生物智能或物理现象基础之上，通过模拟某些自然现象或过程来求解复杂优化问题的一种方法[1]. 常见的智能算法有： 粒子群算法(particle swarm optimization, PSO)[2]、人工蜂群算法(artificial bee colony, ABC)[3]、人群搜索算法(seeker optimization algorithm, SOA)[4]、蝙蝠算法(bat algorithm, BA)[5]、布谷鸟算法(cuckoo search ,CS)[6]等,这些算法为解决传统优化算法难以处理的问题提供了切实可行的方案.

粒子群算法(PSO)是由美国的KENNEDY等[2]基于鸟群飞行觅食的行为提出的一种有效的全局寻优算法. 与其他智能算法相比，PSO算法操作简单，具有记忆全局极值和个体极值的功能，能根据当前的搜索情况动态地调整搜索策略，在较少的迭代次数内找到最优解. PSO算法已被广泛应用于函数优化、数据挖掘、神经网络训练等领域. 但PSO算法存在易早熟收敛、易陷入局部最优等缺点，为此，专家学者们提出了许多改进措施. 文献[7]提出由种群多样性引导的粒子群算法(ARPSO)，该算法在迭代过程中，通过种群多样性的大小判断粒子处于吸引还是排斥阶段.当种群多样性下降到最小阈值时，采用种群增加机制，此为吸引阶段；当种群多样性增加到最大阈值时，采用精英选择机制，此为排斥阶段. 但粒子的种群多样性往往处于二者之间，因此改进算法的效果不太明显，而且该算法需要在每一次迭代中计算种群的多样性，增加了算法的复杂度. 2013年，WANG等[8]提出了基于邻域搜索的粒子群算法(DNSPSO),以一定的概率从父代种群和子代种群中随机选择粒子作为试验个体，采用贪婪策略更新粒子，然后通过邻居搜索策略使粒子之间实现信息交互，此算法对复杂问题的优化有较好的寻优效果.

目前，大多数改进PSO算法所提出的改进策略是作用在整个种群上的，由自然环境对生物的选择可知，同一环境下，不同生物对环境的适应度不同，进化速度和方式也不同；不同环境下，同一生物的进化方向也有不同. 为此，本文提出一种基于动态分级和邻域反向学习的改进粒子群算法. 在算法中，根据函数评价次数和每次迭代时粒子的适应度值将种群中的粒子动态地划分成3个等级，并分别对不同等级内的粒子执行不同的扰动策略，使得粒子在增强种群多样性的同时保持向全局最优方向进化，在此基础上，采取新的粒子位置更新方式，提高粒子的寻优能力. 另外，为了加快算法的收敛速度，平衡种群的局部开采和全局探测能力，引入了动态邻域反向点来构建全局搜索策略. 仿真结果表明，该算法在求解不同类型测试函数时均取得了较好的实验效果.

1 PSO算法

在粒子群算法中，每个粒子代表寻优空间中一个潜在的解，对应一个由适应度函数决定的适应度值，粒子根据本身找到的最优解和整个种群当前找到的最优解进行更新迭代，直到找到全局最优解为止.

假设在D维的可行解空间，初始化N个粒子x=(x1,x2,…,xN),其中第i个粒子表示为xi=(xi1,xi2,…,xiD),代表第i个粒子在搜索空间的位置，第i个粒子的速度定义为vi=(vi1,vi2,…,viD). 在每次迭代中计算各粒子的适应度值，确定t时刻第i个粒子迄今为止搜索到的最优位置，即个体极值pbesti=(pbesti1,pbesti2,…，pbestiD)，以及整个种群迄今为止搜索到的最优位置，即全局极值gbest=(gbest1,gbest2,…,gbestD).

vij(t+1)=vij(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestj(t)-xij(t))，

(1)

xi(t+1)=xi(t)+vi(t+1)，

(2)

其中，c1和c2(非负常数)为学习因子,控制粒子向个体极值和全局极值学习能力的大小；r1,r2为[0,1]内的随机数；t为迭代次数. 在迭代过程中，根据式(1)和式(2)更新粒子的速度和位置.

1998年，EBERHART等对式(1)进行了改进，形成了目前通用的粒子群算法速度更新公式：

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestj(t)-xij(t))，

(3)

其中，w为惯性权重,控制前一速度对当前速度的影响,使其保持运动惯性，有能力搜索新的区域.

2 基于动态分级和邻域反向学习的改进PSO算法(DSNRPSO)

2.1 动态分级扰动策略

在标准PSO算法中，种群中的粒子在每一次迭代时单纯地按照式(2)和式(3)更新，使得种群在收敛时，降低了多样性，导致算法陷入局部最优无法跳出，最优解不被更新的可能性变大，增加了无效搜索次数. 另外，在求解多峰或具有极强跳跃性特点的函数时，当前最优个体的前进方向不一定就是全局最优方向，因此，当种群的多样性降低、算法中的最优个体领导能力下降时，有必要对种群中的最优个体进行扰动. 本文基于函数评价次数和粒子的适应度值动态地将种群中的粒子划分为3个等级，对不同等级中的粒子执行不同的扰动策略. 这种动态分级扰动策略在增加种群多样性的同时，一定程度上也促使了粒子向全局最优进化.

2.1.1 动态分级机制

本文只考虑无约束最小化优化问题，将其目标函数作为算法的适应度函数，在每一次迭代中，根据适应度函数值重新排列粒子，使得当粒子xi的下标从1到N时,适应度值变大，粒子变差，在此基础上根据函数评价次数的变化情况动态地将粒子分为最优、次优、最差3个等级. 在迭代初期，种群中的大部分粒子距离全局最优点较远，因此使最优等级中的粒子占主导地位，有利于加快算法的收敛速度；在迭代中期，粒子接近全局最优点或者局部最优点，需要粒子细致地搜索解空间，以提高算法的收敛精度；在迭代后期，算法可能陷入局部最优，此时，可通过增加随机游走粒子，尽量使算法跳出局部极值的约束. 具体的分级方法如下：

(4)

其中，

(5)

(6)

其中，N为种群规模；t为当前函数评价次数；T为最大函数评价次数. 种群中粒子等级的划分及每个等级内的粒子数随评价次数变化的趋势图如图1所示.

图1 粒子分级示意图Fig. 1 Illustration of the particle classification

2.1.2 扰动机制

最优等级中的粒子xi(i=1,2,…,m)影响种群的进化方向，引导种群向最优解方向进化，故保留当前的最优粒子. 其粒子位置的扰动公式为

xi(t)=xi(t) .

(7)

(8)

其中，pr为选择概率；r3为[0,1]上满足均匀分布的随机数.

最差等级中的粒子xi(i=n,n+1,…,N)对种群寻优的贡献不大，故将其作为游荡者，以增加种群多样性，避免种群中粒子陷入局部最优.其粒子位置的扰动公式为

(9)

其中，

(10)

maxpj=max{pbestij(t)|i=1,2,…,N},

(11)

minpj=min{pbestij(t)|i=1,2,…,N},

(12)

2.2 改进粒子位置的更新方式

在PSO寻优过程中，粒子收敛速度过快是导致算法陷入局部最优的原因之一，因此，为了控制粒子的更新速度，构建了粒子位置的更新公式：

(13)

按此更新方式，粒子在迭代初期，以较快的速度向全局极值方向进化，提高了算法的搜索速度；在迭代后期，粒子以较慢的速度进化，提高了种群的寻优能力，避免粒子更新过快，跳过最优解.

2.3 动态邻域反向学习全局搜索策略

图2 环状拓扑结构和当k=2时粒子xi的邻域Fig. 2 The circle topology and 2-neighborhood

定义假设种群中第i个粒子为xi,i=1,2,…,N，其中N为种群规模.xm和xn为xi邻域中的2个粒子，满足m≠n≠i，则在第t次迭代过程中，xi的动态邻域反向点为

(14)

图3 动态邻域反向点的例子Fig. 3 An example for dynamic neighborhood reverse point

为了进一步提高算法的全局搜索能力，引导种群向全局最优点方向进化，加快算法的收敛速度，结合上述定义的动态邻域反向点和全局极值点构建全局搜索策略：

(15)

gvi=vi,

(16)

2.4 DSNRPSO算法步骤：

步骤1随机初始化种群，设置学习因子c1和c2、惯性权重w、最大函数评价次数T、种群规模N、维数D、邻域半径k、函数评价次数t=0；

步骤2计算粒子的适应度值，初始化全局极值gbest和个体极值pbest；

步骤3根据粒子的适应度值对粒子排序，按式(4)～(6)将种群中的粒子进行动态分级，对不同等级粒子按式(7)～(9)对其扰动；

步骤4如果rand

步骤5更新个体极值pbest和全局极值gbest；

步骤6若达到最大函数评价次数，则停止迭代，输出全局极值，否则，t=t+1，转步骤3.

综上所述，基于动态分级和邻域反向学习的改进粒子群算法的流程图如图4所示.

3 数值试验及结果分析

3.1 测试函数及评价标准

为了验证本算法的有效性和可行性，采用4种类型的标准测试函数[14-15]对算法进行仿真： 单峰及简单的多峰函数(f1～f4)、非旋转的多峰函数(f5～f7)、旋转的多峰函数(f8～f10)和高维的漂移函数(f11～f15)，具体如表1所示. 通过统计适应度误差的均值和方差评价算法的优化性能，其中适应度误差值为(f(x)～f(x*))(x和x*分别为算法所获的最优值和理论最优值).

图4 DSNRPSO算法流程图Fig. 4 Flowchart of DSNRPSO

3.2 仿真实验与仿真环境

实验分为4部分： 实验1： 参数敏感性分析. 算法中参数pr和pns分别控制较优等级中粒子的交叉概率和种群中粒子信息交互的能力，本文分别取pr=0.1,0.3,0.5和pns=0.4,0.6,0.8,1.0对标准测试函数进行测试，pr和pns参数有12种组合. 为了简化数据，选取仿真结果相对较优的参数和其对应的实验结果，具体见表2. 实验2： 本文主要提出了3个策略： 分级扰动机制、粒子智能更新行为和邻域反向学习的全局搜索策略. 为了探讨各策略对算法的影响，验证各策略的有效性，将标准的PSO、基于分级扰动机制的PSO(SPSO)、基于分级扰动机制和邻域反向学习的PSO(SNRPSO)和包含所有机制的PSO(DSNRPSO)对简单的单峰和多峰标准测试函数进行仿真实验. 实验3： 将本文提出的算法DSNRPSO与标准的PSO[2]、基于自然选择的PSO(NPSO)[1]、基于邻域搜索增加种群多样性的PSO(DNSPSO)[8]、人群搜索算法(SOA)[4]、布谷鸟算法(CS)[6]的实验结果进行对比. 实验4： 为了分析本文算法对高维测试函数的收敛性和稳定性，将测试函数的维度D设为300，测试函数为f1，f2和f6，给出几种算法在这3个函数上的统计结果并进行比较，评价指标为最优值、最差值、均值和方差.

仿真实验环境： 处理器： Pentium(R) Dual-Core CPU E5800 @3.20 GHz；RAM: 2 GB；系统类型： Win8.1 64位操作系统；语言： Matlab ；版本： R2014a.

3.3 实验参数设定

为了保证比较的公平性，本文在选取相同通用参数的基础上，各进化算法参数采用参考文献中的建议设置，停止准则为函数评价次数达到最大函数评价次数，其中，30维测试函数的最大函数评价次数T=300 000，100维和300维测试函数的最大函数评价次数T=500 000，种群规模N=40，权重因子w=0.729 84，学习因子c1=c2=1.469 18. 除相同的参数外，各优化算法的其他参数设置如下： DNSPSO[8]中邻域半径k=2，参数pr=0.9，pns=0.6；SOA[4]中最大隶属度值umax=0.950 0,最小隶属度值umin=0.011 1，权重最大值wmax=0.9，权重最小值wmin=0.1；CS[6]中被宿主发现的概率pa=0.25. 在每个实验中，6种算法分别进行30次独立实验测试. 实验统计结果见表2～表5，收敛趋势图如图5所示. 其中，黑体数值表示对比算法在相应函数上的寻优效果最好.

3.4 实验结果分析

实验1保持种群多样性和提高算法收敛精度是改进PSO算法的关键，通过对比表2中参数相同pr、不同pns和不同pr、相同pns2种情况下的实验统计结果发现： 参数pr对算法的影响较小，说明采用动态分级机制能够增加种群多样性，参数pns对算法的影响较大，故通过定义邻域反向点构建全局搜索策略可以较好地平衡种群的局部开采和全局探测能力，提高算法的收敛精度，并且当取pr=0.1和pns=0.8时，DSNRPSO算法在测试函数上取得了较好的综合寻优效果.

实验2种群的多样性影响算法的精度，全局搜索策略影响算法的收敛速度，二者相互制约. 从表3可以看出，SPSO算法对测试函数f2和f4～f7的收敛精度优于PSO算法，而对函数f1和f3的收敛精度劣于PSO算法，说明采用分级机制可以有效增强种群多样性，但降低了算法的收敛速度；SNRPSO算法的仿真结果除函数f2外均优于SPSO算法，说明采用邻域反向学习策略极大地提高了算法的收敛精度和速度，但降低了种群的多样性；为了平衡2种策略对算法的影响，在 SNRPSO算法的基础上，采用粒子智能更新方式的DSNRPSO算法，仿真结果最优，说明采用粒子智能更新方式调节粒子的更新速度有效地平衡了算法的寻优精度和收敛速度.

表1 标准测试函数

表2 不同pr和pns组合对应的DSNRPSO算法在测试函数上的适应度误差的均值

表4 6种算法在标准测试函数上的适应度误差均值和方差

图5 6种算法在标准测试函数上的收敛曲线Fig.5 The convergence curves of six methods on benchmark function

实验3由表4和图5可知，6种算法在对不同类型的测试函数进行寻优时，其收敛速度和精度存在以下差异： 对函数f1和f3，SOA和CS算法陷入局部最优，PSO、NPSO、DNSPSO和DSNRPSO算法收敛性能较好，DSNRPSO算法收敛速度最快；函数f2为连续凹函数，最优点位于平滑、狭长的抛物线山谷，很难求出全局最优点，只有DSNRPSO算法可以得到较好的寻优效果，其他5种算法均陷入局部最优.说明采用动态分级扰动策略可增加种群多样性，显著改善算法的性能；函数f4～f7，f8～f10，有较多的局部极小值点，CS、SOA、PSO和NPSO算法均陷入了局部最优，DNSPSO和DSNRPSO算法寻找到了全局最优点，二者的收敛曲线比较平滑，收敛速度快，DSNRPSO算法解的方差优于DNSPSO算法，说明DSNRPSO算法的稳定性更好；对函数f11，PSO、NPSO算法收敛能力较差，SOA、CS、DNRPSO和DSNRPSO算法的收敛曲线均平滑下移，DNRPSO和DSNRPSO算法出现了小的跳跃，说明后2种算法的寻优能力更强；对函数f12和f13，改进的PSO算法均陷入了局部最优；对函数f14，SOA和CS算法的收敛速度较慢，DNRPSO和DSNRPSO算法的收敛速度较快，但当函数评价次数达到200 000次时，收敛曲线平稳，有可能陷入局部最优；函数f15为复杂的非线性多模态函数，峰形高低起伏不定，并且具有跳跃性，所以很难找到全局最优解，6种算法中，DNRPSO算法的寻优效果最好，DSNRPSO算法次之. 另外，从表4中可以看出，在漂移测试函数上，DSNRPSO、DNRPSO和SOA算法解的方差较大，相较其他算法，这3种算法有可能寻找到较好的全局最优解.

表5 6种算法在D=300上的标准测试函数统计结果

实验4从表5中可以看出，在测试函数f1和f6上，DNSPSO和DSNRPSO算法的收敛精度明显优于PSO、NPSO、SOA和CS，在函数f6上，DSNRPSO算法具有较好的稳定性；对于测试函数f2，虽然DSNRPSO算法的方差较大，但其最优解和均值明显优于其他算法. 表明DSNRPSO算法在求解高维优化问题时同样具有良好的性能.

综上所述，DSNRPSO算法通过引入动态分级扰动机制和全局搜索策略，较好地克服了PSO算法的早熟问题，提高了算法的寻优能力和求解精度.

4 结 论

提出了一种基于动态分级和邻域反向学习的改进粒子群算法，该算法将种群动态地划分成3个等级，针对每个等级中的粒子特点对其执行不同的扰动操作，使粒子在增强种群多样性的同时又保持向全局最优点方向进化，克服了标准PSO算法容易收敛于局部最优造成算法早熟的缺陷. 在此基础上，引入了结合全局极值和动态邻域反向点构建的全局搜索策略，加快了算法的收敛速度. 仿真实验表明，基于动态分级和邻域反向学习的改进粒子群算法，计算精度高、稳定性强.

参考文献(References)：

[1] 王凌.智能优化算法及其应用[M]. 北京： 清华大学出版社，2001： 1-2.

WANG L.IntelligentOptimizationAlgorithmandItsApplication[M]. Beijing: Tsinghua University Press, 2001： 1-2.

[2] KENNEDYJ, EBERHART R C. Particle swarm optimization[C]//ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks.Piscataway: IEEE，1995: 1942-1948.

[3] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm[J].JournalofGlobalOptimization, 2007, 39(3): 459-47.

[4] 余胜威, 曹中清.基于人群搜索算法的PID控制器参数优化[J].计算机仿真，2014, 31(9): 347-350.

YU S W, CAO Z Q. Optimization parameters of PID controller parameters based on seeker optimization algorithm [J].ComputerSimulation, 2014, 31 (9): 347-350.

[5] YANG X, GANDOMI A H. Bat algorithm: A nove approach for global engineering optimization[J].EngineeringComputations, 2012, 29(5): 464-4.

[6] YANG X S, DEB S. Cuckoo search via levy flights[C]//ProceedingsoftheWorldCongressonNatureandBiologicallyInspiredComputing. Coimbatore: Nature & Biologically Inspired Computing, 2010. DOI: 10.1109 / NABIC. 2009.5393690.

[7] RIGET J, VESTERSTRØM J S. A diversity-guided particle swarm optimizer-the ARPSO[J/OL].ResearchGate. Https: //www.researchgate.net/publication/228582468_a_diversity-guide_particle_swarm_optimizer-the_arpso，[2002-01].

[8] WANG H, SUN H, LI C, et al. Diversity enhanced particle swarm optimization with neighborhood search[J].InformationSciences, 2013, 223(2): 119-135.

[9] KENNEDY J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance[C]//EvolutionaryComputation,1999.CEC99.Proceedingsofthe1999Congresson. Piscataway： IEEE Xplore, 1999: 1931-1938 .

[10] DAS S, ABRAHAM A, CHAKRABORTY U K, et al. Differential evolution using a neighborhood-based mutation operator[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(3): 526-553.

[11] TIZHOOSH H R. Opposition-based learning: A new scheme for machine intelligence[C]//ComputationalIntelligenceforModelling,ControlandAutomation,2005andInternationalConferenceonIntelligentAgents,WebTechnologiesandInternetCommerce,InternationalConferenceon. Washington： IEEE Computer Society, 2005(1): 695-701.

[12] 魏文红, 王甲海, 陶铭,等. 基于泛化反向学习的多目标约束差分进化算法[J].计算机研究与发展, 2016, 53(6): 1410-1421.

WEI W H, WANG J H, TAO M, et al. Multi-objective constrained differential evolution using generalized opposition based learning[J].JournalofComputerResearchandDevelopment, 2016, 53 (6): 1410-1421.

[13] WANG H, WU Z, RAHNAMAYAN S, et al. Enhancing particle swarm optimization using generalized opposition based learning[J].InformationSciences, 2011, 181(20): 4699-4714.

[14] ZHAO S Z, SUGANTHAN P N, DAS S. Self-adaptive differential evolution with modified multi-trajectory search for CEC’2010 large scale optimization[C]//Swarm,Evolutionary,andMemeticComputing. Heidelberg: Springer, 2010: 1-10.

[15] LIAO T, STUTZLE T. Benchmark results for a simple hybrid algorithm on the CEC 2013 benchmark set for real-parameter optimization[J].EvolutionaryComputation, 2013, 2013: 1938-1944.

[16] DANG C T, WU Z, WANG H.A new approach of diversity enhanced particle swarm optimization with neighborhood search and adaptive mutation[C]//NeuralInformationProcessing. Heidelberg: Springer International Publishing, 2014: 143-150.

[17] GAO W F, HUANG L L, LIU S Y, et al. Artificial bee colony algorithm with multiple search strategies[J].AppliedMathematics&Computation, 2015, 271(C): 269-287.

[18] GAO W F, LIU S Y, HUANG L L. Particle swarm optimization with chaotic opposition-based population initialization and stochastic search technique[J].CommunicationsinNonlinearScience&NumericalSimulation, 2012, 17(11): 4316-4327.