任丹丹, 陈笑笑, 刘 清
(安徽理工大学数学与大数据学院,安徽 淮南 232001)
粒子群优化算法(Particle Swarm Optimization,PSO)[1]是一种启发式搜索算法,在理论上具有一定的全局搜索能力。由于参数设置简单、适用范围广等优点,PSO算法现已受到众多领域的广泛关注,比如路径规划[2-4],癌症基因检测[5,6]以及电力系统设计[7]等。
PSO算法在处理复杂的多峰函数时,往往不能收敛到全局最优解:易陷入局部最优区域[8,13,14]。为了提升PSO算法对复杂函数的求解能力,徐等[9]在2020年提出基于正态分布权值的改进粒子群方法(NDWPSO)。NDWPSO通过正态分布函数模拟权值函数,提升了算法的精度。2021年,吴等[10]提出一种动态调整惯性权重和学习因子的粒子群优化算法。该算法在种群进化的过程中,自适应调整惯性权重以及学习因子。由于该算法的参数较多,其收敛效果较好,但是参数调节却较为繁琐;2021年,李等[11]提出一种动态自适应参数的粒子群优化算法,在速度进化公式中引入非线性速度衰减因子,提升了粒子群的稳定性;2022年,郭等[12]提出一种多种群并行协作的粒子群算法,该算法将三个使用不同进化策略的子类群体融合为一个混合的粒子种群,提升了算法的收敛精度。这一类基于参数优化的改进方法,重点关注惯性权重、学习因子等参数对寻优结果的影响,改善了算法的收敛性能。
然而,这些方法却极易多次聚集于同一个局部邻域。当粒子群在某个局部最优区域聚集后,增大惯性系数或者其他参数,能够强制粒子群分散到其他区域。在找到适应值更优的解之前,粒子全局最优位置以及历史最优位置都分布在之前聚集的局部最优区域内,在现有策略的指引下,可能会迅速聚集在相同的局部区域内。
为了克服上述问题,提出一种基于聚集检测的改进粒子群优化算法(Aggregation detection based PSO),简记为ADPSO。ADPSO在粒子发生聚集时,主要通过重新初始化粒子历史最优位置,降低全局学习因子,增大历史最优位置学习因子以及为每个粒子增加随机搜索能力来提升改进粒子群的搜索能力。在标准函数上的测试结果表明,改进方法比传统方法具有更好的收敛精度和收敛速度。
设F(X)是待求解的目标函数(默认最优解为最小解),Ω是可行域。正整数n是粒子群的规模,Xi(i=1,2,…,n) 是第i个粒子Pi的位置,正整数D是粒子搜索空间Ω的维度,F(Xi)是粒子Pi的适应度。在粒子群优化算法中,适应度最优的粒子是种群最优粒子,其位置记为Gbest。粒子Pi经历的历史最优位置记为Pi_best。
线性权重粒子群算法(WPSO)
WPSO是一种基于速度线性衰减的改进算法,与PSO[1]相比,具有更好的收敛性能。假设在第k次迭代中,粒子Pi的速度为Vi。WPSO的速度公式:
Vi=WkVi+c1r1(Pi_best-Xi)+c2r2(Gbest-Xi)
(1)
(2)
其中,Vi是D维向量:Vi=(vi,1,vi,2,…,vi,D),iter_max是最大迭代次数,Wk是速度惯性系数,且0 WPSO根据如下公式更新粒子Pi的位置: Xi=Xi+Vi (3) 其中,Xi是一个D维的向量:Xi=(xi,1,xi,2,…,xi,D) 。 公式(1)和(2)说明,线性递减的权值W使得WPSO算法在前期具有较大的速度,全局搜索能力较强;在迭代后期,粒子群具有较强的局部搜索能力。WPSO通过权值W的调节,来平衡粒子群的全局搜索能力和局部搜索能力。 实际上,WPSO还存在一个较为严重的不足:若粒子群聚集于某局部邻域内,则很难跳出该区域。传统的改进方法[3-6]很难阻止粒子再次聚集于该区域。 当WPSO算法发生聚集时,粒子的历史最优位置都在全局最优点Gbest的局部邻域内: Gbest≈Pi_best (4) 其中,i=1,2,…,n。那么,公式(1)将退化为: Vi=WkVi+(c1r1+c2r2)(Gbest-Xi) (5) 公式(4)说明,在粒子群发现适应值更优的解之前,粒子的历史最优位置仍然在之前聚集位置附近。当前的Gbest与全局最优解的位置可能相距甚远,使用公式(5)更新粒子速度,不一定能找到适应值更优的解。 针对这一关键问题,提出一种基于聚集检测的粒子群优化算法,以进一步提升粒子群的搜索能力。 首先,在粒子群发生聚集后,更新每个粒子的历史最优位置。 假设粒子Pi的位置为Xi,且向量Xi的任意分量xi,j(j=1,2,…,D)的取值范围为:xi,j∈[a,b],全局最优位置Gbest的第j个分量记为Gbestj。由于Gbest是目标函数的一个局部最优解,在其δ(δ>0) 邻域内肯定不存在适应值更优的解。因此,在重新初始化历史最优位置时,通过如下概率函数来约束粒子最优位置: P(xi,j)= (6) 从公式(6)可知,所有粒子的历史最优位置以更大的概率落入Gbest的δ邻域之外。 其次,降低全局最优位置的影响力,防止粒子再次聚集在其局部邻域之中:减小全局最优位置的学习因子c2,并适当增大粒子历史最优位置的学习因子c1。 假设,粒子群在第ith次迭代时发生聚集。为了降低全局最优位置Gbest的影响力,可减小学习因子c2,并增大学习因子c1: (7) (8) 最后,增加随机搜索能力,提升收敛速度。按公式(3)更新Xi之后,随机选择向量Xi的一个分量xi,j,进行如下操作: Xitest1=(xi,1,xi,2,…,xi,j+β,…,xi,D) (9) Xitest2=(xi,1,xi,2,…,xi,j-β,…,xi,D) (10) (11) (12) 1)设置基本参数:迭代次数iter_max>0,N>0,D>0;设粒子位置X和飞行速度V为随机值。学习因子恢复速率参数α>0,局部邻域半径δ>0。 2)计算粒子Pi的适应度F(Xi),计算历史最优位置Pi_best,更新全局最优位置Gbest。 3)公式(1-3):更新粒子速度和位置;公式(9-12):在Xi的某一维度上进行线性的折半查找搜索。若粒子群发生聚集,则转4);否则转5)。 4)公式(6):以一定的概率初始化每个粒子的历史最优位置;公式(7-8):c1,c2的取值。 5)若迭代次数达到iter_max或当前最优解符合精度要求,则算法终止;否则,转2)。 实验使用六种常用的标准函数来测试改进算法的收敛速度和收敛精度,并将结果与WPSO[8]、权值正态分布的粒子群算法(NDWPSO)[9]以及吸引排斥粒子群算法(ARPSO)[15]的结果相比,以验证ADPSO算法的有效性。ADPSO的参数设置如下:c1=c2=2.0;wmax=0.9,wmin=0.4;δ=1,α=0.005,β=0.02;若ADPSO发生聚集,则动态调整相关参数。WPSO的c1,c2,wmax以及wmin与ADPSO算法中对应参数的设置一致。其他算法的参数均已调制最优。所有算法的最大迭代次数iter_max=20000,N=20。测试函数如表1所示: 表1 六个测试函数的名称与表达式 六个测试函数均具有全局最小解,记为Xoptimal。本文选择绝对误差作为算法收敛精度的评价标准: error=(|f(Gbest)-f(Xoptimal)|) (13) 表2给出了四种算法在六种测试函数上的收敛精度:十次实验结果的均值。 表2 ADPSO算法与其他三种对比算法的收敛精度对比表。 从表2可知,ADPSO算法在F1,F2,F4,F5以及F6,这五个函数上的收敛精度明显优于其他三种对比算法;在F3上的收敛精度与WPSO和ARPSO算法的收敛精度基本相当。 对于F1,四种算法都能收敛到全局最小解的局部区域,ADPSO算法具有更高的收敛精度。各算法在F2上的收敛精度都有明显的下降:F2函数的波谷区域非常平坦,导致粒子只能缓慢地接近全局最优解。利用了部分梯度信息的ADPSO算法,具有更优的收敛精度。F3和F4是高维多峰函数,在全局最优解的周围分布着大量的局部极优区域,寻优难度很大。ADPSO具有较好的收敛性能:收敛精度明显高于其他三种粒子群优化方法。F5和F6是二维多峰函数,寻优难度同样很大;ADPSO算法的收敛精度都在10-4以内,正常情况下,能够满足实际应用的精度要求。 图1给出四种算法在测试函数上的“最优值-迭代次数”收敛曲线。 (A) 四种算法在F1(X)上的收敛曲线 (B) 四种算法在F2(X)上的收敛曲线 (C) 四种算法在F3(X)上的收敛曲线 (D) 四种算法在F4(X)上的收敛曲线 (F) 四种算法在F6(X)上的收敛曲线 从图1可知,在F1和F4上,ADPSO算法在前2500迭代就可以收敛到误差精度小于102。F2的波谷区域非常平坦,导致传统的ARPSO,WPSO以及NDWPSO,很难搜索到全局最优解。ADPSO算法需要15000次左右的迭代才能找到全局最优解。F3是一个高维且多峰的函数,寻优难度很大。ADPSO大约需要20000次迭代能够收敛到误差精度小于10的区域。其他对比算法的误差精度则在102,与改进算法的收敛精度有较大差距。在F5和F6函数上, ADPSO在前2000次迭代就能收敛到全局最优解附近,具有明显的优势。 本文提出了一种基于聚集检测的改进粒子群优化算法,简称为ADPSO算法。针对当前粒子群算法存在的易早熟、收敛精度不高的问题,ADPSO算法在粒子群发生聚集时,重新初始化每个粒子的历史最优位置、动态调整学习因子并且利用某一维度上的梯度信息,引导粒子搜索潜在的最优解。改进的ADPSO算法能够保持较好的全局搜索能力,并同时具有较好的局部搜索精度。在六个测试函数上的实验结果表明,ADPSO与WPSO,ARPSO以及NDWPSO等算法相比,具有更好的更高的收敛精度和更快的收敛速度,具有更强的实际应用能力。2.1 WPSO算法的关键问题
2.2 改进方法:基于聚集检测的改进粒子群算法(ADPSO)
3.1 参数设置
3.2 收敛精度对比
3.3 收敛速度对比
