张渊博,邹德旋,张春韵,杜星瀚
(江苏师范大学电气工程及自动化学院,江苏 徐州 221116)
群智能优化算法[1]是模拟昆虫、兽群、鸟群和鱼群的群体行为,这些群体按照一种合作的方式寻找食物,群体中的每个成员通过学习它自身的经验和其它成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索,从而在解空间内找到最优解。其中粒子群算法结构简单、参数少、容易实现,收敛速度较快。该算法已成功应用于许多领域如图像分割[2]、路径规划[3]、车间调度[4]、系统优化[5]。
尽管粒子群优化算法优势众多,但粒子群算法容易陷入早熟收敛而找不到最优解,存在收敛后期种群多样性较差、速度较慢。因此学者们针对局部收敛、不变性、稳定性、参数设置和拓扑结构进行研究,对粒子群算法改进,并提出了许多算法的变体。文献[6]提出了一种基于粒子群算法的自适应变异差分进化算法,在迭代早期,算法有效地利用改进的DE/rand/1突变策略来探索较好的区域,从而提高逃离局部最优的能力。在进化的后期,利用粒子群算法的变异策略有效地加快了收敛速度。文献[7]采用动态自适应惯性加权因子,并将遗传算法(Genetic Algorithm,GA)[8]相关算子引入粒子群算法中,通过交叉和n点变异算子自适应地选择满足遗传算法选择准则且选择概率随时间变化的粒子群,更新其位置。文献[9]提出全息粒子群算法采用了整体结构和自相似结构。将不同的粒子分为不同的组和级,组内之间粒子进行信息交换,用一组中最好的粒子进行不同级粒子的信息交换。该结构提高了粒子群算法的速度和精度。廖星等[10]运用线性递减惯性权重与正态随机数的随机惯性权重提出了一种自适应惯性权重粒子群优化算法,并引入压缩因子与变学习因子减小惯性权重的影响,最后使用GPU并行的运行算法,加快运行速度。
李龙澍等[11]针对PSO算法易陷入局部极值的缺陷,提出了一种新的自适应惯性权重混沌PSO算法(New Adaptive Inertial Weight Chaotic Particle Swarm Optimizatio, CPSO-NAIW)。该算法首先采用新的权重自适应方法,通过粒子与群体极值位置距离对权重进行调整,使权重的调整与粒子的状态位置状态信息相结合,然后采用基于混沌优化摆脱局部极值的方法,在算法陷入局部极值时,对群体极值进行混沌调整,以使各个粒子在追逐不同群体极值位置进行更新时,可以改变寻优轨迹,提高了算法摆脱局部极值的能力。吴凡等[12]提出一种惯性权重曲线递增策略的改进算法(Curve Increment Particle Swarm Optimization, CIPSO),有效避免早熟问题,在处理“维度灾难”问题上,寻优性能更强,且具备良好的平衡全局与局部寻优性能。以上现有方法都通过自适应权重平衡全局与局部寻优能力,但对于多峰测试函数,算法仍陷入局部最优。
为了使算法在进化前期锁定较好区域,在进化后期提高局部搜索能力,提出一种自适应惯性权重的粒子群优化算法(Stochastic Inertial-Weighted Particle Swarm Optimization, AIWPSO),算法主要是对惯性权重、学习因子进行改进,并加入局部搜索策略。最后通过标准测试函数与其它算法对比,验证了该算法的有效性。
粒子群优化算法是由Kennedy[13]和Eberhart[14]在1995年提出的一种启发式的群体智能算法,是一种无梯度优化算法,其灵感来自于移动生物的社会行为,如鸟群的移动,来达到同样的目标。运动是基于粒子在搜索空间中最佳的位置(即局部最好的位置),以及整个搜索空间中最佳的位置群(即全局最佳)。假设搜索空间有d维(d= 1,2,…D)每个粒子i的位置和速度分别用Vi=(vid,…,viD),Xi=(xid,…,xiD)表示。对于每次迭代或时间步长t,速度被用来更新的下一个位置,每个粒子的计算公式为
vid(t+1)=wvid(t)+c1r1(pgd-xid(t))+c2r2(pid-xid(t))
(1)
xid(t+1)=xid(t)+vid(t+1)
(2)
对于每个粒子i和维数d,通过以上方程(1)式更新粒子的速度vid和(2)式更新粒子的位置xid。在式(1)中,w是动量的权重,它影响到前一个速度对下一个粒子运动的影响程度。群体的最佳位置记为pgd,用常数c1加权,c1为个体学习因子。c2为社会学习因子,对每个粒子pid的最佳位置加权。r1、r2为r(0,1)的均匀随机数样本。
避免速度向量使粒子发散导致后期收敛变慢和低精度问题,胡旺[15]提出一种更简化的粒子群优化算法(Simplified Particle Swarm Optimization, SPSO),舍去速度项,简化为
(3)
本文为了平衡算法的全局搜索与局部搜索能力并加快搜索速度,将惯性权重ω与学习因子(c,c2)和随机数(r1,r2)进行改进,提出一种自适应惯性权重的粒子群优化算法,更新公式为
(4)
(5)
影响因子根据迭代次数来改变个体极值和全局极值对粒子位置的影响。前期受个体极值影响大,使粒子快速找到相对较好的位置,寻优中期,一部分粒子向全局最优值靠近,一部分粒子继续搜寻更好的位置点,迭代次数达到后期时,所有粒子向全局最优值靠近,使粒子得到更好的收敛。
固定的学习因子,在处理复杂问题时,很有可能陷入局部最优解;因此,本文根据惯性权重自适应的更新认知和社交因子,更新公式为
(6)
(7)
其中c＿start和c＿end分别设置为1.5和1。当惯性权重减小时,说明上一代的粒子位置不理想,在更新下一代粒子时应保留粒子少部分的信息,同时应该适量增加认知因子和社交因子,使粒子向自身历史最佳位置和群体历史最佳位置逼近。此学习因子加入余弦函数,能够产生振荡,使粒子更好的寻优。
3.1 自适应惯性权重
惯性权重ω起到了一个平衡全局搜索能力和局部搜索能力的作用恰当的ω值可以提高算法性能,提高寻优能力,减少迭代次数。本文运用双曲线先下降后上升的特性和高斯函数与目标函数值相结合,提出自适应惯性权重,表示为
ω=α(f(x))*β(t)
(8)
(9)
(10)
其中f(x)为粒子的目标函数值;f＿avg为所有粒子的平均目标函数值;δ为方差,a,b为双曲线参数,分别为0.3,50,β取值范围为[0.3,1.042]。目标函数值越小说明粒子适应度越大。当粒子适应度小于平均适应度值时,说明粒子处于较差的位置,惯性权重取得较小值,使下次粒子更新时获得前代粒子较少信息;当粒子适应度值大于平均适应度值时,粒子处于好的位置,惯性权重取得较大值,使下次粒子更新时获得较多前代粒子信息。然后通过双曲线先下降后上升的特性,使粒子寻优前期有很强的全局寻优能力,中期有较强的局部寻优能力,加快收敛,后期增强全局搜索能力,使粒子有能力跳出局部最优,提高寻优精度。
图1为一个粒子随进化次数的惯性权重分布,整体上呈现先下降后上升趋势,进化前期,粒子通过自己的适应度值与所有粒子适应度值的平均值的比值得到自己的惯性权重,使每个粒子搜寻到适合自己的区域;进化中期,惯性权重较小,粒子可以快速达到最优解;进化后期,粒子的惯性权重较大,有利于粒子逃出局部最优。
图1 惯性权重分布
3.2 随机局部搜索
本文为了增加最优解的精确度,引入交叉变异操作,随机生成粒子的方向向量,根据粒子与粒子中心的平均距离,进行随机局部搜索,随机局部搜索的公式为
xcid=rand*xjd+(1-rand)*xkd
(11)
(12)
xni,d=xqi,d+μUi
(13)
(14)
(15)
其中i,j,k分别表示为第i个、第j个、第k个粒子,且i≠j≠k,xcid为交叉后得到新粒子,xqid为突变后的粒子,κ为均匀分布在[-0.01,0.01]之间,ui、li分别为第i个粒子迭代过程中空间中的最大值与最小值,xni,d为逃脱局部最优产生的新粒子,μ为距离中心位置最近的K个粒子的平均距离,Ri(i=1,…,m)为随机生成的方向向量。
算法实现步骤如下:
Step1 设置最大迭代次数、种群数量、初始化种群位置、学习因子;
Step2 计算出每个粒子的适应度值;
Step3 找出个体极值Pbest与全局极值Gbest;
据有关统计表明，项目投入资金的总量为876.459万元，包含783.643万元的营林人工费用以及232.432万元的工程材料费用等。
Step4 根据式(6-10)计算学习因子与惯性权重;
Step5 根据式(11-15)进行随机局部搜索更新出新的粒子;
Step6 通过适应度函数计算两种粒子的适应度值,更新个体极值Pbest和全局极值Gbest。
Step7 判断是否满足终止条件,若满足执行Step8,否则转到Step4。
Step8 输出全局极值Gbest。
算法流程图如图2。
图2 算法流程图
仿真的运行环境的内存为16G,Intel i5-9300H CPU 2.4GHz,Windows 10操作系统,算法采用Matlab R2019b实现。为了验证算法的合理性,分别在30维和100维下运行30次进行实验对比与分析。最后对算法的局部搜索进行验证。
4.1 测试函数
为了检验算法AIWPSO的有效性,本文用16个标准测试函数进行仿真对比,其中f3、f4、f8、f10-f16为单峰测试函数,f1、f2、f5、f6、f7、f9为多峰函数,f7为病态的二次函数,全局极小点被无数的局部极小点所围绕,因此很难找到最优解。本文的测试函数见表1。为了更好统一观测算法搜寻测试函数的最优解。以下测试函数可能在形式上略有变化,但并不影响其测试效果,测试函数的理论解都为0。
表1 测试函数
4.2 参数设置与实验结果分析
设计实验时最重要的环节是合理设置参数和仿真环境,如此才能保证算法比较过程的公平性与公正性。表2为四种算法参数设置。
表2 四种算法参数设置
4.3 实验结果
将本文算法,与近三年新算法CPSO、CISPO和基本粒子群算法PSO在30维下进行仿真对比。算法的实验数据对比结果见表3。
表3 四种算法搜索30维函数结果
从实验结果表中可以看出对于16个测试函数,虽然AIWPSO算法对于f8所搜索的最优解不优,但是四种算法中最优的解,对于其它测试函数AIWPSO算法都能搜寻到很好的解,而且AIWPSO算法搜寻的最优解都比其它三种算法搜寻的解好,并且AIWPSO算法能过搜索到f5、f6、f7、f9的理论解,这主要因为算法有很好的全局搜索能力。但是算法对于多次搜寻f7测试函数的平均解和标准差不优。表中的平均值代表算法的平均优化性能,这也是重要的评价指标,AIWPSO算法不仅最小值搜寻到f5、f6、f9的理论解,而且平均值也为理论解,说明AIWPSO算法对这三个函数有很强的搜索能力。标准差也是衡量算法性能的重要物理量之一。可以从表中看出f1、f4、f5、f6、f9被搜索的方差为0,说明AIWPSO算法搜寻的解很稳定,f8函数的方差较大,是因为此函数带有噪音扰动,导致算法搜寻不稳定。
为了更加直观的观察和反应四种算法的优越性,图3为四种算法分别对函数f1、f3和f4、f8、f10、f16的迭代曲线。从图中可以看出,从算法迭代开始不久AIWPSO就比其它三种算法搜寻的解好,并且不断地找更加准确的解,其它三种算法始终无法在寻优过程中下滑到低于AIWPSO寻优曲线的位置,是由于CPSO产生混沌现象时只有单一的混沌策略,在粒子陷入局部最优时,通过混沌策略,逃出局部最优的能力较弱,粒子会进入另一个局部最优解,减慢了找到更好解的速度。CIPSO的曲线递增策略虽然满足了前期惯性权重较小,加快了搜寻速度,后期惯性权重较大,增加了全局搜索能力,但寻优前期,单一的惯性权重策略,使粒子陷入局部最优,在寻优后期时,粒子跳出局部能力较弱,所以搜寻的解没有AIWPSO的优秀。但对于函数f1、f8平均函数解中CIPSO算法比CPSO逃脱局部最优能力强。
图3 四种算法获得的6个函数平均适应度进化曲线
多数智能算法在低维函数的计算中效果很好,而在高纬函数中效果不佳。为进一步综合评价AIWPSO算法在高维度下算法的性能,本文将四种算法在100维下进行实验,实验结果见表4。由结果可知,AIWPSO算法寻找的最优解并没有明显增大,除了搜寻函数f12、f14、f15的最小值增大了一倍,其它并没有随着维度的增加而使算法降低了寻优的精准度,说明AIWPSO算法能较好的适应解决高维度函数问题。相比较而言,其它三种算法,最优解都有明显增大,发生维度灾难。
表4 四种算法搜索100维函数结果
图4为四种算法在100维下运行30次的平均函数解,可以从图中看出f3、f10的进化曲线,AIWPSO算法随着迭代次数仍平稳的下降,搜寻着最优解,而CPSO、CIPSO算法逃出局部最优能力较差,下降缓慢,而且由于维数的增加,两种算法找到的最优解都有一定量的增大。对于f14进化曲线,AIWPSO算法虽然在52代左右曲线不在下降,但仍搜寻到了较好的解。整体上看,四种算法AIWPSO平均函数解下降的最快,这除了自适应惯性权重的原因外,随机局部搜素影响下,使每代都有机会得到更优的解。
图4 四种算法获得的3个函数平均适应度进化曲线
4.4 局部搜索效果验证
将有局部搜索策略(AIW)和无局部搜索策略(AIW2)两种算法运行10次的平均函数解进行对比见图5。可以看出局部搜索策略十分有效。特别是多峰函数f7、f8尤为明显,分别在28代搜索到理论解和29代搜寻到更好的解。f3为单峰函数,在25代左右逐渐产生效果。由此可以看出,局部搜索策略增强了算法局部的搜索能力,提高了算法的收敛的精度。
图5 两种算法获得的3个函数平均适应度对比曲线
本文针对粒子群优化算法在迭代的后期会出现种群多样性不足,导致陷入局部最优的问题,做出三点改进,首先,提出自适应惯性权重,其次,加入随惯性权重而改变的学习因子,然后,通过交叉变异操作进行随机局部搜索。最后本文通过16个标准测试函数进行仿真,将算法与近三年的两种粒子群算法和标准粒子群算法分别在30维和100维下对比分析,结果表明,AIWPSO算法具有更好的寻优能力。
猜你喜欢 测试函数惯性极值 你真的了解惯性吗中学生数理化·八年级物理人教版(2023年3期)2023-03-21冲破『惯性』 看惯性中学生数理化·八年级物理人教版(2022年3期)2022-03-16极值点带你去“漂移”新世纪智能(数学备考)(2021年10期)2021-12-21极值点偏移拦路，三法可取河北理科教学研究(2020年3期)2021-01-04一类“极值点偏移”问题的解法与反思中学数学杂志(2019年1期)2019-04-03无处不在的惯性中学生数理化·八年级物理人教版(2017年3期)2017-11-09具有收缩因子的自适应鸽群算法用于函数优化问题物联网技术(2017年5期)2017-06-03普遍存在的惯性小学科学(学生版)(2016年1期)2016-10-09借助微分探求连续函数的极值点广东技术师范大学学报(2016年5期)2016-08-22带势函数的双调和不等式组的整体解的不存在性上海理工大学学报(2016年2期)2016-06-02