时空众包环境下时效均衡改进粒子群优化算法

黄素叶

闽西职业技术学院，福建 龙岩 364021

时效均衡粒子群优化算法是一种基于生物种群随机搜索的粒子优化算法，根据思想主要是源于鸟类种群的觅食行为规律，时效均衡改进粒子群中每一个粒子通过自己所处的最优值，跟踪并调整前进速度和方向，从而实现种群个体在空间中的寻优[1].国外对于时效均衡改进粒子群优化算法的研究最早可追溯到20世纪初期，由于当时的理论框架较难适应不同应变场,只能够解决单工况问题,到20世纪中期将数值计算方法引入到了粒子群优化算法中，求解了离散粒子结构拓扑的优化问题[2]；国内关于时效均衡改进粒子群优化算法的研究较晚，在近20年到30年才开始研究时效均衡改进粒子群优化算法，同时也成为结构设计优化领域的研究热点[3].

基于自适应动态改变的粒子群优化算法根据粒子的适应度值来调整算法的权重，采用非线性指数递减来提高算法的搜索能力，避免粒子群优化算法出现局部极值的现象，从而提高算法的性能，实验结果表明该算法可以提高收敛速度，但收敛成效和精度较差，超体积指标出现异常值[4]；基于分解和差分进化的粒子群优化算法通过一组向量的产生，确保时效均衡粒子分布的均匀性，采用时效均衡粒子重置策略，确保时效均衡粒子的多样性，实现时效均衡粒子群的优化，实验显示该算法在求解粒子群优化问题方面具有收敛性好的优势，但是算法运行时间较长[5].

基于以上背景，本文在时空众包环境下，设计了时效均衡改进粒子群优化算法，从而提高了时效均衡改进粒子群优化算法的优化效果.

1 时效均衡改进粒子群优化算法设计

1.1 选择粒子群优化参数

时效均衡改进粒子群优化算法的设计需要控制一些参数，如粒子群的规模、学习因子、惯性权重、种群拓扑结构及最大速度等，如何选择粒子群优化参数将对算法的优化效果产生直接影响.

1.1.1 粒子群的惯性权重参数

粒子群惯性权重参数ω可以衡量粒子群优化算法的搜索性能，使算法在整个计算过程中分配合理.粒子群惯性权重的增大,算法的搜索能力会随着增强,而随着粒子群惯性权重的减小,将使算法只在局部具有搜索能力[6].通常粒子群惯性权重参数的优选范围在0～1.4之间是最合适的，但是粒子群惯性权重参数的取值在0.8～1.2之间时，算法的收敛速度会加快.粒子群惯性权重参数设置在0.8～1.2范围时,会提高算法的收敛速度.因此为了使算法在计算初期具有全局搜索能力、计算末期具有局部搜索能力，我们可以在优选惯性权重参数时,将粒子群惯性权重设置为随算法计算的进行而减小.因为算法具有计算代价和效果两个因素,所以我们采取惯性权重线性削减策略，将惯性权重值降到0.4附近，作为粒子群惯性权重的优选参数.

时空众包环境下，时效均衡粒子群优化算法具有很多优点，但是会使粒子群会追随最优粒子飞行，算法迭代计算若干次之后，会使得时效均衡粒子群产生很强的趋同性,导致算法的收敛速度减慢[7].为了克服算法在迭代计算方面的缺点，又考虑到惯性权重参数对算法性能的影响，将惯性权重值设置为0.7，随着迭代计算次数的增加将惯性权重参数递减到0.4，惯性权重参数的变化由式(1)确定：

(1)

式中，mmax表示权重参数质量最大值，mmin表示权重参数最小值，Tmax表示所需最长计算时间.

1.1.2 学习因子c1和c2

惯性权重参数的引入可以提高算法的检索性能，但是学习因子也影响着算法的性能[8].学习因子c1和c2的选择是通过粒子群的运动轨迹，同时必须满足c1+c2≤4.学习因子c1和c2是控制时效均衡粒子向最优个体学习的因子，从而控制向粒子群内的最优点靠近.如果c1=0，则时效均衡粒子不具有自身经验，算法的收敛速度也比较快，但是当算法应用到复杂性较高的问题中时，会使算法极易进入局部最优状态；如果c2=0，说明时效均衡粒子只有自身经验，而没有粒子群共享信息，由于时效均衡粒子个体之间不存在交流，算法得到解的概率很小[9].

学习因子c1和c2两个参数都具有各自调节的功能，但是两个参数的调节是相互脱离的，减弱了算法在计算过程中的统一性，不利于算法的优化检索性能.本文在时空众包环境下，将学习因子选取惯性权重参数的非线性函数：

(2)

粒子群优化算法的优化算法随着学习因子c1和c2的变化而变化，时效均衡粒子的速度也会发生变化，优选学习因子c1和c2参数时，通常选择c1=c2，并将参数的范围设置在0～4之间.

1.1.3 最大速度vmax

在一次迭代计算过程中，时效均衡粒子的最大移动距离由最大速度vmax决定，算法的搜索能力会随着vmax的增大而增强，只是与此同时容易导致时效均衡粒子最优解的错过；算法的开发能力会随着vmax的值减小而增强，但会使算法极易进入局部最优状态[10].因此，通常采用调整惯性权重的方式来设置最大速度vmax的值.在时空众包环境下，为了提高算法的统一性，一般采用通过对惯性权重参数动态调整学习因子和设置最大速度参数，完成粒子群参数的选择.

1.2 提取时效均衡最优粒子

时效均衡改进粒子群优化算法往往忽略了对粒子个体极值更新的改进，通常采用粒子间的支配关系来提取时效均衡最优粒子个体.时效均衡粒子群在进化过程中，会出现时效均衡粒子的极值得不到更新[11].首先，计算时效均衡粒子群中单个粒子的强度si，单个粒子的适应值fi，时效均衡粒子群中单个粒子的强度si可以根据式(3)计算：

(3)

式中，ni表示时效均衡粒子群中的第i个粒子所支配的粒子个体数，N表示时效均衡粒子群的规模.

在粒子群中，单个粒子的适应值fi是由种群所有支配给它的粒子个体强度来决定的，计算公式为

(4)

式中，si表示粒子个体s与i粒子之间的支配关系.假设fi为第i个粒子个体的适应值，时效均衡粒子群中最优粒子个体的适应值为fm，粒子群整体的平均适应值为favg，则有

ΔF=|fm-favg|

(5)

ΔF的值越小，说明粒子群的收敛性越容易早熟.

令粒子个体的精度为ε，当ΔF>ε时，按照粒子间的支配关系，在粒子个体的当前位置和历史位置中选择比较优秀的一个作为最优位置；当ΔF<ε，就从粒子群的外部档案中选择一个非劣解与当前最优解替换[12].提取时效均衡最优粒子除了考虑粒子个体的选择，还要考虑全局最优粒子的选择，一般通过在粒子群的非劣解集中随机选择一个解的方式作为全局最优粒子.为了提高算法求解的多样性，本文通过动态加权法完成对全局最优粒子的提取[13].按照式(6)计算粒子群中各个粒子的适应度，计算公式为

(6)

式中，ai表示第i个粒子的位置，M表示粒子的最终位置.

本文利用粒子个体之间的支配关系,结合选择个体最优粒子和全局最优粒子的选择要求,完成了时效均衡最优粒子的提取，从而改进粒子个体极值的更新[14]；接下来通过优化时效均衡改进粒子群优化算法设计，来实现时效均衡粒子群的优化.

1.3 优化时效均衡改进粒子群

在一个N维搜索空间中，粒子群优化算法由M个粒子组成的粒子群X={X1，X2，…,XM}，t时刻，第i个粒子的位置表示为Xi(t)=[Xi,1(t),Xi,2(t),…,Xi,N(t)]，i=1,2,…,m，粒子不具有速度向量.粒子个体的最优位置表示为Pi(t)=[Pi,1(t),Pi,2(t),…,Pi,N(t)]，粒子群的全局最好位置表示为G(t)=[G1(t),G2(t),…,GN(t)]，且存在G(t)=Pg(t).时效均衡改进粒子群优化算法流程如图1所示.

图1 时效均衡改进粒子群优化算法流程Fig.1 The flow of improved particle swarm optimization algorithm for time effective equilibrium

根据时效均衡改进粒子群优化算法流程，详细分析了时效均衡改进粒子群优化算法的实现步骤：

Step1：在粒子群中对粒子的具体位置进行初始化；

Step2：计算粒子群的平均最优位置；

Step3：对粒子当前位置的适应值进行计算,对比前一次迭代计算的适应值,如果小于前一次迭代计算的结果，则根据粒子的历史位置更新成为粒子当前所处的位置，即如果存在f[Xi(t+1)]

Step5：比较前一次的迭代计算结果和粒子当前全局最优位置,若粒子当前全局最优位置的值比前一次的迭代计算结果的值更好，则利用粒子群全局最优位置来更新粒子的位置；

Step6：计算粒子每一维的最优位置，得到一个粒子的随机点位置；

Step7：计算粒子所处的最新位置；

Step8：重复Step2～ Step7，直到满足终止条件.

综上所述，在时空众包环境下，通过对粒子群的学习因子、惯性权重、最大速度等参数的选择进行对粒子群优化和对粒子群的个体粒子最优位置和全局最优粒子的选择，完成时效均衡最优粒子的提取；最后通过优化时效均衡改进粒子群优化算法设计，实现了时效均衡粒子群的优化[15].

2 实验对比分析

为了测试时效均衡改进粒子群优化算法在时空众包环境下的应用性能，进行仿真实验，实验采用Matlab设计，对时效均衡改进粒子群的节点覆盖设定为200×200的二维平面，最优子节点数为16，中继传输节点的信息通信覆盖半径为R=1.25，总的节点规模为150，改进持续时间设定为20 min(持续12个采样点)，采样点的时间采样间隔为12 min，最大迭代轮次为2 000，其他参数设定具体如表1所示.

表1 实验参数设置Tab.1 Experimental parameter setting

根据上述环境和参数设定，进行时效均衡改进粒子群优化试验，分析ε指标值对比结果、超体积指标值对比结果以及算法运行时间对比结果，具体内容如下所述.

2.1 ε指标值对比试验

ε指标是一个用于评价粒子群优化算法收敛性能的指标，可以使用任意两个问题的解来判断算法的收敛性.ε指标值对比实验以测试函数变量个数为自变量，分别采用基于自适应动态改变的粒子群优化算法、基于分解和差分进化的粒子群优化算法及时空众包环境下的粒子群优化算法，对测试函数的求解问题进行优化计算，得到ε指标值对比结果如图2所示.

图2 ε指标值对比结果Fig.2 Comparison results of ε index values

从图2的实验结果可以看出，测试函数变量个数在30个以内时，三种粒子群优化算法的收敛性保持基本一致，而当测试函数变量个数超过30以上时，基于自适应动态改变的粒子群优化算法由于计算过程比较复杂，不能很好地控制求解个数，使得ε指标值变小，导致该算法的收敛性变差；基于分解和差分进化的粒子群优化算法与基于自适应动态改变的粒子群优化算法的收敛性相差不大，测试函数变量个数在70个～100个之间时，ε指标值始终比基于自适应动态改变的粒子群优化算法大0.05，说明该算法的收敛性一般，可以满足求解要求；而时空众包环境下的粒子群优化算法由于优化参数的选择，当测试函数变量个数超过40个时，ε指标值就开始迅速变大，可以求出问题的最优解位置，说明该算法具有较强的收敛性.

2.2 超体积指标值对比试验

超体积指标是指被非支配解集覆盖的目标空间求解区域大小，通常用于评价测试函数的解集质量.超体积指标值对比实验以测试函数变量个数为自变量，分别采用基于自适应动态改变的粒子群优化算法、基于分解和差分进化的粒子群优化算法及时空众包环境下的粒子群优化算法，对测试函数的求解问题进行优化计算，得到超体积指标值对比结果如图3所示.

图3 超体积指标值对比结果Fig.3 Comparison results of super volume index values

从图3的实验结果可以看出，采用基于自适应动态改变的粒子群优化算法来求解测试函数时，当测试函数的变量个数为40个时，超体积指标值出现了异常值，原因可能是算法中没有对参数进行优化，使该算法计算得到的解集质量变差；由于采用基于分解和差分进化的粒子群优化算法缺少对解集最优位置的提取，导致利用该算法求解测试函数时，经常发生求解异常情况，但是由于超体积指标值相对较高，说明该算法计算得到的解集质量良好；而采用时空众包环境下的粒子群优化算法来求解测试函数时，由于该算法不仅优化的参数，还提取了解集的最优位置，使超体积指标值随着测试函数变量的增加而变大，计算得到的解集质量非常好.

2.3 算法运行时间对比试验

算法运行时间对比实验以测试函数变量个数为自变量，分别采用基于自适应动态改变的粒子群优化算法、基于分解和差分进化的粒子群优化算法及时空众包环境下的粒子群优化算法，对测试函数的求解问题进行优化计算，得到算法运行时间对比结果如表2所示.

表2 算法运行时间对比结果Tab.2 Comparison results of algorithm running time

从表2的实验结果可以看出，时空众包环境下的粒子群优化算法的运行时间明显少于其他两种算法，随着测试函数变量数量的增加，其他两种算法的运行时间都超过10 ms，而测试函数变量数量对时空众包环境下的粒子群优化算法的影响较小，说明该算法的参数优化部分,可以通过运行时间的减少,降低算法复杂度.

综合以上实验结果，无论是在收敛性、解集质量还是算法运行时间方面，时空众包环境下的粒子群优化算法的性能明显优于其他两种算法.

3 结束语

时效均衡改进粒子群优化算法的设计需要对微粒群的规模、学习因子、惯性权重、群体拓扑结构和最大速度等几个参数进行控制，微粒群优化参数的选取直接影响着算法的优化效果.原有方法收敛成效和精度较差，超体积指标出现异常值且算法运行时间较长，为此本文提出了时空众包环境下时效均衡改进粒子群优化算法.在时空众包环境下，通过上述提到的参数进行对粒子群优化，且对粒子群的个体粒子最优位置和全局最优粒子进行选择，完成对时效均衡最优粒子的提取；最后通过优化时效均衡改进粒子群优化算法设计，实现了时效均衡粒子群的优化.实验结果显示，时空众包环境下的粒子群优化算法的性能更好.对于未来的工作，可以考虑引入多目标对时效均衡粒子群优化算法进行进一步研究，充分考虑优化算法不同特征，并依据实际开发情况进行全新度量.