带随机变异及感知因子的粒子群优化算法

黄懿, 梁放驰, 范成礼, 宋占福

(1.空军工程大学 基础部, 陕西 西安 710051; 2.空军工程大学 防空反导学院, 陕西 西安 710051)

粒子群优化算法(PSO)是一种群体性智能搜索算法[1-3],由Kenney于1995年提出,并因实现容易、精度高、收敛快等优点成为国内外研究的热点。但PSO算法在求解高维多峰问题时容易出现“早熟”现象,不能完全保证求得全局最优[4]。针对此问题,国内外学者提出了许多改进策略[5-15],如调整参数、精英选择和混合算法等,或在前人的基础上增加优化因子。文献[7-9]通过动态和自适应控制惯性权重提高算法的搜索和挖掘能力,但其搜索范围不一定能够覆盖整个空间,依然存在出现局部最优的情况。文献[10]提出了一种无惯性的自适应精英变异策略,加快了算法的收敛过程,扩大了种群搜索范围,但在高维问题求解上还需进一步实验验证。文献[11]根据个体与全局最优粒子间的距离分别对惯性系数ω、学习因子c1和c2求导,给出了3种参数的确定性变化方向,达到参数自适应控制的目的,但对局部最优分散在整个搜索空间,并且与全局最优相距很远的复杂问题求解能力不强。文献[12]在自适应调整惯性权重的量子粒子群优化算法基础上,对粒子位置进行了周期性变异,提高了全局搜索精度,但全局判据仅作为判断优化结果全局性的依据,不会扩大算法搜索范围。文献[13]为解决粒子种群多样性和收敛性的矛盾,引入了动态划分多种群重构粒子作为引导因子,对执行阶段的最优个体实施混合变异,对时变概率实施反向学习或邻域扰动策略,提高算法的开发与勘探能力,但频繁使用该策略反而会降低部分函数的求解精度。文献[14]在前人基础上,提出了一种自适应局部搜索启动策略,提高了算法的收敛速度和精度,但其全局搜索能力有待验证。文献[15-16]分别将混沌云和单纯形与基本粒子群算法相结合,以提高算法的全局搜索能力,多用于多模态复杂问题求解,对目标函数求解问题需要进一步验证。文献[17]提出粒子速度或位置小概率随机变异与自适应逃逸策略相结合,但求解高维多峰等复杂问题时,其收敛速度较慢,需要迭代2 000次以上,才能求出最优值。针对多模态优化问题,文献[18]通过构建集成代理辅助模型,解决了区间多模态粒子群优化计算代价高昂问题,但对多目标多模态的适用性仍需进一步验证。总之,以上算法的改进大多采取参数选择或参数自适应控制策略,或混合其他算法,针对高维复杂问题的求解能力略显不足,不能从根本上克服“早熟”的固有弊端。

基于以上分析,根据粒子群在空间中的搜索和分布特点,通过增加随机变异和感知因子,改进粒子群的速度和位置更新策略,提出带随机变异因子和感知因子的粒子群优化算法(PSORMP),扩大粒子在空间中的搜索范围,有效解决了粒子群因搜索范围不足或粒子过于聚集而陷入局部最优问题。通过典型函数测试、算法对比实验、参数影响分析等仿真实验,验证了PSORMP算法具有很强的快速收敛、全局搜索与精确挖掘能力。

1 基本PSO算法

设一个D维空间中,由N个初始搜索粒子组成一个群落,则第k代第i个粒子的D维向量表示为

(1)

第k代第i个粒子的飞行速度为

(2)

截至k代,第i个粒子经历的最优位置称为个体最优,记为

(3)

截至k代,整个粒子群经历的最优位置称为全局最优,记为

(4)

由此,基本PSO算法粒子的速度和位置更新公式为

(5)

式中:c1和c2为学习因子;r1和r2为[0,1]范围内的随机数。

针对惯性系数ω,采用非线性递减权重策略

(6)

式中:f表示粒子实时的目标函数值;favg和fmin分别表示当前粒子群的平均值和最小目标值[19]。

由基本PSO算法的迭代公式可以发现,粒子的寻优方向由粒子群的自身历史最优位置和全局最优位置所决定,因此,如果全局最优位置是解空间的局部最优位置,就很容易导致粒子群陷入局部收敛。许多高维空间求解问题都是复杂多峰函数,如果算法跳出局部最优的能力不足,这些峰值很容易吸引粒子群发生“早熟”现象,算法的可靠性和稳定性难以保证。

2 PSORMP算法

为了使算法更具跳出局部最优能力,根据粒子群的运动特性,提出带随机变异及感知因子的PSO算法,改变粒子的速度和位置更新策略,以提高全局搜索与挖掘能力。

2.1 带随机变异因子的速度更新策略

为扩大粒子的搜索范围,避免粒子群受初始种群的限制,在速度更新公式中增加一个基于粒子自身邻域、个体最优和全局最优的随机变异因子,以提高粒子的运动能力,更新的速度公式为

(9)

(10)

式中:r4为[-0.5,0.5]的随机数(由函数测试得出,具体见本文3.3节);xmax为最大可行变异区间,这里同自变量的取值范围。

(11)

(12)

最后,进行负理想点映射,得映射点xR

xR=xC+α(xC-xF)

(13)

式中,α为负理想点映射系数,一般取α=1.3～0.5递减。

图1 为负理想点时粒子运动过程

图2 为负理想点时粒子运动过程

2.2 带感知因子的位置更新策略

针对算法容易陷入局部最优的不足,本文提出一种带感知因子的位置更新修正策略,使种群粒子尽可能分散于整个搜索空间,提升全局搜索能力。其主要思想为:粒子自身虚拟感知与其他粒子之间的距离,粒子间的距离小于平均距离的粒子,该部分粒子自身触发感知排斥,将自身与其他粒子的距离控制在平均距离之外,从而保持跳出局部搜索。如图3所示,黄色点代表个体最优粒子,红色点代表全局最优粒子,若粒子群出现图3a)表示的情况,个体最优附近粒子群数量比全局最优数量多,且距离较近,容易使结果陷入局部最优。此时,局部紧密粒子存在斥力,触发感知排斥,而经过感知因子调整后,粒子群空间分布如图3b)所示,从而防止陷入局部最优。

图3 感知因子对粒子群修正示意图

为更好地理解该策略,引入以下2个定义。

定义1各维度粒子间的距离定义为

(14)

定义2则各维度的平均距离定义为

(15)

(16)

为简化计算过程和保证种群收敛,令惯性权重系数ω3的递减策略与惯性权重系数ω1相同,采取非线性递减的方式,以达到后期的局部挖掘能力。

2.3 PSORMP算法步骤

根据基本粒子群算法求解过程,结合带随机变异粒子的速度更新策略和带感知因子的位置更新策略,PSORMP算法的寻优步骤为

step1 输入初始化PSORMP算法参数,设置初始种群规模N,粒子维数D,最大迭代次数Tmax,学习因子c1,c2,粒子速度阈值vmin,vmax和粒子各维阈值xmin,xmax;

step2 计算并记录粒子群的位置和速度;

step3 计算粒子的适应度值;

step4.1 利用随机变异粒子的速度更新策略进行速度更新;

step4.2 利用感知因子的位置更新策略进行位置更新;

step6 判断是否满足终止条件t=Tmax,若满足,则转至step7,若不满足,则转至step4;

3 实验与结果分析

3.1 算法的选择与比较

为验证算法的有效性和优越性,本文选取5种算法进行对比,分别是基本PSO算法和4个基于PSO算法的改进算法,即PSOPC[20]、RPSO[21]、NPSO[22]和RFRPSO[23],其中,①PSOPC算法:为避免生物群在信息共享时存在自私行为导致形成被动群体,从而无法获得全局最优,提出在粒子群中加入一个被动群模型,提高算法粒子运动活力。②RPSO算法:排斥PSO算法利用在粒子间设置几种排斥机制,使种群粒子从被认为个体最佳的位置移开,从而促使粒子探索空间中的新区域,并在后期切换原有探索模式,达到跳出局部最优的可能。③NPSO算法:负粒子优化算法的优化策略是在原有粒子群优化算法的基础上,采取将粒子远离个体和群体负理想解的理念,来达到寻优目的。④RFRPSO算法:带反向预测与斥力因子的PSO算法,其优化策略为降低粒子在运动过程中的惰性,引入反向预测因子以改变粒子速度更新方式,为使粒子分散于搜索空间,引入带斥力的位置修正策略。以上算法的速度更新公式如表1所示。

表1 算法速度更新公式比较

3.2 测试函数的选择与参数设置

为验证算法的稳定性和可行性,本文通过求解7个具有代表性的标准基准函数的最小值问题来验证算法,主要包括Sphere、Quartic、Rosenbrock、Griewank、Ackley、Rastrigrin和Schwefel。其中,Sphere函数除了全局极小值外,还具有D(维度)个局部极小值,对高维粒子求解困难;Quartic函数是存在随机干扰的单峰函数,对算法验证极具代表性;Rosenbrock函数的全局最优位于一个狭窄的抛物线谷中,虽然山谷容易找到,但很难收敛到最小值,是很难求解极小值的典型二次函数;Griewank函数具有很多局部极小值,可验证算法跳出局部最优能力;Ackley函数在二维形式中,呈现出外部平坦,中心下沉的一个深坑状态,并具有众多的局部极小值,对容易产生“早熟”现象的算法求解带来了很大困难;Rastrigrin函数为复杂多峰函数,在求解过程中很容易陷入全局最优附近的局部极小点;如图4所示,Schwefel函数具有均匀随机性,其局部最优分散在整个搜索空间,并且与全局最优相距很远,欺骗性强,算法必须拥有很强的全局搜索能力才能得到全局最优。实验过程中测试函数的相关信息如表2所示。

图4 Schwefel函数的二维图像

表2 测试函数及参数设置

实验过程中,设置初始粒子群规模N=200,最大迭代次数Tmax=1 000,惯性权重系数ωmax=0.9,ωmin=0.5,维数D=30,学习因子c1=c2=2,可接受误差为0.1。实验环境为:AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz,RAM 16.0GB,Windows10操作系统,MATLAB2019a。比较算法的参数根据文献[19-23]的最佳参数而定,如表3所示。

表3 对比算法的参数设置

3.3 测试结果及分析

将每个测试函数独立运行100次,记录每个算法的成功率(S,在规定的可接受误差范围内,成功求解的次数与总运行次数的比值)、平均最优值(Bm,每种算法对每个测试函数独立运行100次后得到的平均最优值,此结果能衡量算法的稳定性)、最终适应值(Bf,表示每种算法对每个测试函数独立运行100次后得到的最优适应值,此结果可以衡量算法的求解精度)、平均运行时间(Tm每个算法对测试函数独立运行100次的平均运行时间)和Adjusted p-value(P,表示本文算法与其他算法对比的显著性差异水平),如表4～10所示,除Adjusted p-value外,最优值用粗体显示,次优值用斜体显示。各类对比算法对7个测试函数的收敛过程如图5所示。

图5 测试函数收敛曲线图

表4 函数f1测试结果对比

表6 函数f3测试结果对比

表7 函数f4测试结果对比

表8 函数f5测试结果对比

表9 函数f6测试结果对比

表10 函数f7测试结果对比

表4～10的实验结果表明:在求解成功率上,PSORMP算法取得5个最高值,2个次高值,平均成功率为97%,明显高于其他算法;在平均最优值上,PSORMP算法得到6个平均最优结果和1个平均次优结果,PSO、RPSO、RFRPSO 3种算法共得到3个平均最优结果和6个次优平均结果,验证了本文算法的寻优能力;在最终适应值上,PSORMP算法得到6个最优结果和1个次优结果,PSO、RPSO、RFRPSO 3种算法共得到5个最优结果和6个次优结果,验证了本文算法的求解精度;在平均运行时间上,PSORMP算法得到5个最优结果,2个次优结果;根据Adjusted p-value,仅在函数f3～f5测试结果中,与RFRPSO算法的对比结果为P>0.05,即没有显著差别,其他测试结果显示本文算法显著优于其他算法,验证了本文算法的优越性和稳定性。从算法的求解精度看,本文算法针对f1,f4～f7共5个函数求得理想的全局最优,对f2,f3函数求得最优值与理想值非常接近,并优于其他算法。分析其主要原因在于依托增加随机变异因子和粒子感知因子后,使粒子群在种群空间中的多样性和聚集性达到了合理分配,从而能够有效求解高维复杂多峰函数,特别是对函数f1,f4～f7,取得了理想全局最优解,并且在成功率和稳定性上也优于其他算法,表现了算法较强的鲁棒性。

本文通过增加随机变异因子和感知因子,动态调整了粒子的散布态势,扩大了搜索空间,调整了粒子聚集时间。从函数的收敛图像可以看出,针对函数f1～f4,各类算法均求得了最优值,根本原因是函数f1和f2本身就是单峰函数,求解最优值相对容易,而函数f3在维度超过15维后,函数特性趋向于单峰,函数f4的全局最优与可达到的局部最优之间有一道狭窄的山谷,求解最优也相对容易,但本文算法在收敛速度和求解精度上相对于其他算法更有优势;函数f5～f7为具有大量局部最优的复杂多峰函数,在求解过程中容易陷入局部最优,但本文算法在收敛速度、求解精度上明显由于其他算法,尤其是相对于PSO、PSOPC、RPSO、NPSO算法,在迭代500次时,本文算法均收敛并取得最优值,而其他算法还未收敛或未求解全局最优值.由此表明,PSORMP算法具有很好的跳出局部最优和快速求解能力。

3.4 算法参数的影响分析

图6 不同r4取值范围Schwefel函数收敛曲线图

3.5 算法复杂性分析

本文引入的随机变异因子和感知因子,是在基本粒子群算法的基础上引入的速度和位置更新策略,需进一步分析PSORMP算法的计算复杂度,以证明算法的优越性。假设T表示最大迭代次数,D表示维度,N表示初始粒子群规模。则随机变异因子的复杂度为Cr1(N)=D×N×T,感知因子的复杂度为Cr2(N)=N×T,基本粒子群算法的复杂度为Cr3(N)=D×N×T。则PSORMP算法复杂度为Cr(N)=D×N×T+N×T+D×N×T≈D×N×T=Cr3(N)。所以,PSORMP算法与基本PSO算法的复杂度在理论上属于同一数量级。

为进一步验证上述结论,采取3.1节和3.2节的参数设置,选用基本PSO算法、PSOPC、RPSO、NPSO、RFRPSO算法及本文算法PSORMP,对7个测试函数在同一初始种群条件下,独立运行100次,记录每个函数平均运行时间Tm,系统运行环境与3.2节相同,最终结果如表11所示。其中最优值加粗表示,次优值用斜体表示。通过给出的结果可以看出,PSORMP算法与其他算法运行时间处于同一数量级,引入的因子没有增加计算的复杂程度。

表11 算法运行时间对比 s

4 结 论

本文为解决高维空间中粒子群算容易产生早熟问题,根据粒子群在空间中的运动规律和散布特点,提出了一种带随机变异因子和动态感知因子的粒子群优化算法,改进了粒子的速度和位置更新策略,有效解决了传统PSO算法在求解高维复杂多峰函数时容易陷入局部最优问题,提高了跳出局部最优能力和收敛速度。并通过测试函数和算法对比,验证了算法的有效性和优越性,适合解决工程应用中高维空间中的复杂函数的优化问题。另外,算法是否适用于动态优化求解及可能存在的问题是未来研究的重点。