基于信息微传递机制的粒子群算法

闫 李，李国森，瞿博阳，马佳慧

(中原工学院 电子信息学院，河南 郑州 450007)

0 引 言

为提高粒子群算法(PSO)[1-5]的寻优性能，研究人员提出许多解决方案。张新明等[6]将趋优算子与莱维飞行(levy flight)策略引入粒子群算法，以平衡算法的全局和局部寻优能力。Aydilek[7]融合萤火虫算法提出了萤火虫-粒子群混合算法，以避免早熟收敛。Elsayed等[8]在算法中采用交叉操作和参数自适应机制，以提高解的多样性。袁小平等[9]引入社会学习策略以提升PSO的全局搜索能力，并采用Levy Flight策略使种群摆脱局部最优陷阱。

尽管上述研究在一定程度上提高了标准PSO算法的寻优性能，但PSO算法进化后期收敛速度慢、寻优精度低等不足仍需要进一步深入研究。因此，本文提出基于信息微传递机制的粒子群算法(IMPSO)，该算法具有以下3个方面的特点：①采用信息微传递机制，提高种群的多样性；②引入逃离策略，防止种群陷入局部最优；③设计了一种动态边界化策略，提高算法搜索效率。最后，本文选取具有不同特性的测试函数在6种算法上进行性能对比以验证IMPSO算法的有效性。

1 标准粒子群算法

假设MaxIter表示算法最大迭代次数，种群规模为NP，搜索空间维度为D。第i个粒子的位置表示为xi=(xi1,xi2,…xiD)，其速度表示为vi=(vi1,vi2,…viD),标准PSO算法通过其个体历史最优值pbesti=(pbesti1,pbesti2，…，pbestiD)和全局最优值gbesti=(gbesti1,gbesti2，…，gbestiD)对个体进行迭代更新[10,11]。其位置和速度更新定义如下

(1)

(2)

2 基于信息微传递机制的粒子群算法

2.1 信息微传递机制

标准PSO在整个进化过程中所有粒子个体跟随全局最优解进行搜索，增加了收敛到最优解的速度，同时会导致早熟收敛问题[12]。本文提出信息微传递机制，利用适应度值对种群分组，每一组由若干层组成，逐层传递最优信息实现种群进化。具体步骤如下：

(2)信息逐层传递：在种群进化过程中，第一层粒子集体学习种群全局最优信息gbest，而第n层(n>1)每个粒子分别学习第n-1层相应粒子的个体历史最优信息pbest，有利于减缓信息传播的速度。另外，根据适应度值调整粒子速度的变化大小，个体适应度值越大，产生的速度越小，有利于减缓收敛。反之，产生较大的速度避免局部最优。因此，第一层粒子速度更新如下

(3)

其余层粒子的速度更新如下

(4)

其中，fitness(i)是第i个粒子适应度值。ε为极小的正常数，避免分母为零。另外，引入rand2启发于文献[13]，可以改善算法收敛速度[13]。以图1为例说明信息传递过程，每个粒子给予一个编号。按照式(3)、式(4)，13号粒子将会学习9号粒子的pbest。同理，9号粒子和5号粒子将分别学习5号粒子和1号粒子的pbest，而1号粒子直接学习全局最优gbest。最终实现了13号-9号-5号-1号粒子的信息传递和学习。

图1 信息微传递机制

2.2 逃离策略

(5)

其中，dxi表示第i个粒子与种群中适应度值最差粒子的欧氏距离，Dx表示所有粒子离适应度值最差粒子的最大欧氏距离，计算为Dx=max{dxj|j=1,2,…,NP}，w(t) 表示种群中适应度最差的粒子。一方面，粒子不受全局最优引导，根据最差解产生新的进化方向，避免粒子的趋同性；另一方面，根据与最差粒子的距离自适应更新速度，当距离最差粒子近时，产生较大的速度以远离最差解。

2.3 动态边界化策略

标准粒子群算法在整个搜索空间中寻优，搜索空间不随进化过程而改变，增加了粒子寻优的盲目性和工作量[15]。为了提高寻优速度和搜索效率，本文采用动态边界化策略，每组的边界范围均不相同，主要思想是依据组内最优粒子x产生一个动态搜索边界范围[BL,BU]以防止组内粒子的位置超出界限。假设整个搜索空间边界为[LB,UB]D。在d维，上边界BUd和下边界BLd计算如下

BUd= min(2·rand·xd,UBd)

(6)

BLd=max(rand·xd,LBd)

(7)

其中，UBd和LBd表示搜索边界UB和LB的第d维。从公式可以看出，以获得的最优信息x为中心，产生一个缩小的矩形寻优区域，使得粒子较好地向区域内最优解逼近。通过动态地缩小搜索范围，忽略适应度较大且不相关的区域，达到高效寻优的目的。

2.4 实现步骤

步骤1设置算法参数以及初始化种群。

步骤2采用信息微传递机制。依据粒子适应度和种群平均适应值计算划分的组数φ，并将整个种群适应度值按升序排列进行分组分层。如果粒子属于第一层，则按照式(3)更新速度；否则按照式(4)进行更新。

步骤3判断是否采用逃离策略。计算种群平均速度vavg，如果当前粒子的速度小于vavg，则按照式(5)更新粒子速度。

步骤4依据式(2)更新粒子位置。采用动态边界化策略，即根据每组内适应度最优粒子x，通过式(6)、式(7)计算其组内搜索边界。若位置超过该边界，则置为边界值。

步骤5若未达到最大迭代次数MaxIter，则将所有组个体重新组成一个种群，以实现各个组之间信息的交流，并转至步骤2，否则输出结果。

3 实验结果与分析

3.1 实验设置

为了验证本文提出的IMPSO算法的性能，实验选用10个经典测试函数[13,17]。函数表达式和搜索区间见表1。f1～f5是单峰函数；f6～f10是多峰函数，存在多个局部极值。所选测试函数具有不同的优化难度，可以有效评估算法的收敛速度、寻优精度等性能。将IMPSO算法与HSPSO算法[7]、RDPSO算法[8]、ESPSO算法[18]、BLPSO算法[19]、CHPSO算法[20]和基本PSO算法[21]进行对比。IMPSO算法参数设置：学习因子c=2，惯性权重w=0.7298。所有算法的种群大小NP为50，独立实验次数为30。所有实验在Matlab2016b版本下运行，运行环境为Intel Core i3-6100CPU, 3.7 GHz, 4 G内存。

表1 基准测试函数

3.2 实验结果及分析

3.2.1 固定迭代次数的性能分析

实验参数设置如下：所有算法最大迭代次数MaxIter=100，测试函数维度D分别取50和100。采用最优值、平均值、最差值和标准差作为指标进行对比。实验结果见表2。从表2中可以看出，在单峰函数f1～f5中，IMPSO算法的最优值、平均值、最差值都优于其它6种算法，均能收敛到最优解。对于复杂的多峰函数f6～f10，IMPSO算法均成功跳出局部最优，且得到的解精度很高，尤其在函数f6、f8、f10上找到了理论最优值。而其它算法一定程度上陷入了早熟收敛。当函数维度由50维变成100维，IMPSO算法仍可以找到相应函数的最优解。另外，通过对比所有算法在测试函数上的标准差，IMPSO算法得到的标准差明显较小。可以表明，对于单峰函数和多峰函数，IMPSO 在寻优精度和算法稳定性上表现良好，总体上优于比较的算法。可见，采用信息微传递机制可以避免算法过早陷入局部最优，利用逃离策略提高了种群多样性，引入动态边界化策略加快了寻优效率和搜索精度，从而算法得到的结果更接近理论最优值。图2给出算法在维数D=50下的4个测试函数(f1、f3、f5、f7)的收敛曲线。从图1中可以直观地看到，在进化初期，IMPSO算法的曲线下降更快，比其它6种算法显示出更较好的寻优能力，说明IMPSO算法收敛速度更快。在进化中后期，其它6种算法均不同程度的陷入早熟收敛，出现陷入局部最优的现象，而IMPSO算法有效避免了该现象，且快速寻找到最优解，表现出更好的收敛速度和寻优性能。以上结果表明，IMPSO 算法具有更好的收敛速度。因此，IMPSO算法在寻优精度、稳定性和收敛速度方面表现良好。

表2 算法在固定迭代次数下在50维和100维的测试结果

表2(续)

图2 函数进化曲线

3.2.2 固定收敛精度的性能分析

表3 固定精度下的最小、平均和最大收敛代数及成功率对比

4 结束语

针对粒子群算法易陷入局部最优，并导致算法收敛速度慢、寻优精度不高的不足，提出了基于信息微传递机制的粒子群算法(IMPSO)。该算法采用信息微传递机制使整个种群分组分层寻优，增强种群多样性，避免算法早熟；利用逃离策略通过远离最差解促使趋同性的粒子改变飞行方向，提高全局勘探能力，防止陷入局部最优；使用动态边界化策略缩小粒子的搜索区域，增加算法寻优的效率。实验结果表明，IMPSO相比于其它所对比的PSO改进算法，具有更快的收敛速度和更高的寻优精度。下一步工作中，将尝试使用IMPSO算法解决实际工程问题。