融合多种策略的改进粒子群算法①

胡 佳

(中国市政工程中南设计研究总院有限公司,武汉 430010)

粒子群优化算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart[1]提出的模拟鸟群觅食行为的一种群体协作随机优化方法.PSO 算法中每个粒子都代表一个问题的候选解,通过粒子个体的简单行为及群体内的信息交互实现问题求解的智能性.其概念简单、实现容易、鲁棒性强、优化性能好,常用于解决多峰值、非线性等问题,并在函数优化[2]、图像处理[3]、系统辨识[4]、神经网络[5]、有限元模型修正[6]等工程和科学领域得到广泛应用.

虽然PSO 算法优化性能较好,但也存在早熟收敛、容易陷入局部极值、迭代后期收敛速度慢等问题.对此,国内外研究学者从调整算法自身参数、改变粒子学习模式、结合其他优化算法等方向提出诸多改进的方法.吴静等人[7]通过动态调整惯性权重,提高了算法收敛速度及稳定性.张继荣等人[8]提出一种惯性权重余弦调整的PSO 算法,提高了算法的精度.李龙澍等人[9]为平衡粒子的搜索行为提出了一种新的自适应惯性权重混沌PSO 算法,提高算法全局探索能力.谭阳等人[10]改变粒子学习模式,将PSO中指导粒子群进化的全局最优解扩展为由多个精英粒子组成的精英子群,提高了算法跳出局部极值的能力.Liang 等人[11]提出了一种综合学习PSO 算法,在多峰函数上具有较好的优化效果.Jiang 等人[12]将遗传算法中杂交算子引入到PSO 算法中,有效提高了算法的收敛性.Xia 等人[13]在PSO 算法中引入变异算子对人行桥进行模型修正,算法收敛速度和精度得到提高,得到令人满意的修正结果.刘波等人[14]提出了一种混合模拟退火算法的改进PSO 算法,提高了算法收敛到全局最优解的速度和精度.张庭场等人[15]提出一种融合裂变和变异操作的分合群PSO 算法,提高了算法局部收敛能力.这些改进算法大都要么提高了算法的收敛速度和精度,即提高算法局部挖掘能力,要么增强算法跳出局部极值的能力,即提高算法全局探索能力,很难同时兼顾两者.基于以上研究,为有效地兼顾了全局探索与局部挖掘能力,提出了一种融合多种策略的改进粒子群算法(Improved Particle Swarm Optimization Algorithm,IPSO).实验结果表明,IPSO 同其他PSO 算法相比,收敛速度快、求解精度高且容易跳出局部最优解.

1 基本PSO 算法

PSO 算法是一种基于群智能的随机搜索算法,源于对鸟群捕食行为的研究.PSO 算法由一群粒子组成,每个粒子可视为D 维搜索空间中的一个搜索个体,具有自身的位置和速度,并且能够保留迄今为止所找到的最优位置以及所有粒子目前找到的全局最优位置.算法迭代过程中,每个粒子根据个体最优位置和全局最优位置来更新自己的速度和位置,通过目标函数适应度值来评价粒子更新的位置是否更优,从而不断进化来获得新的个体最优和全局最优位置.在标准PSO 算法中,粒子迭代更新公式如下:

式中,xti表示第t次迭代第i个粒子的位置,vti表示第t次迭代第i个粒子的速度,表示第t+1次迭代粒子的速度,表示第t+1次 迭代粒子的位置,pti表示第i个粒子搜索至第t代时历史最优位置,即个体最优,ptg表示搜索至第t代时整个种群历史最优位置,即全局最优,ω是惯性权重,决定前一时刻的速度对下次移动的影响,c1、c2为学习因子,通常取2,r1、r2为[0,1]内随机数,代表扰动因子.

惯性权重 ω对平衡算法的收敛速度和全局搜索能力有着重要的作用.ω取值大有利于全局探索,并增加种群的多样性,而较小的ω则可以提高算法的局部挖掘能力,加快收敛速度.为提高算法的前期全局探索能力和后期局部挖掘能力,本文采用常用的线性递减权重策略[2],如式(3)所示:

其中,t为当前迭代次数,Gmax为最大迭代次数,ωmax为初始惯性权重,通常取0.9,ωmin为最大迭代次数时的惯性权重,通常取0.4.

粒子的飞行速度 v影响粒子位置更新的步长.最大飞行速度vmax一般取变量可行域的10%～20%.迭代过程中,粒子的飞行速度将被约束在[−vmax,vmax]的范围内.

2 改进粒子群算法

本文融合了多种策略对基本PSO 进行改进.首先,受达尔文 “优胜劣汰、适者生存”生物进化思想[16]的启发,对种群粒子进行选择,适应度值小的优良种群被保留,其它粒子则被淘汰,具体实施中采取了分组策略和精英策略.按适应度值从小到大排序将种群分为优解组和劣解组,优解组进行遗传交叉操作,劣解组进行变异操作;然后将经过交叉变异后的种群和当前迭代次数下的初始种群按适应度值从小到大进行排序,选出前一半粒子作为更新种群.其次,采取改进粒子学习模式的策略,充分利用了群体信息,保证了种群的多样性,提高了算法全局探索的能力.最后,采取了控制概率的策略,通过引入决策数P,控制进入交叉变异等操作的概率,使算法在迭代初期小概率执行交叉变异等操作,尽量增加种群多样性,保证算法的全局探索的能力;随迭代次数的增加,进入交叉变异等操作的概率逐渐增大,迭代后期的收敛速度显著加快,算法的局部挖掘能力得到增强.通过多种策略的融合,IPSO 算法能有效兼顾全局探索和局部挖掘能力,具有收敛速度快、求解精度高、避开局部最优解的优点.

2.1 分组策略

根据目标函数的适应度值对种群进行分组.首先生成包含N个粒子的初始种群,计算种群内所有粒子目标函数的适应度值fit(xi)并排序,根据排序结果选择适应度值小的前一半粒子作为优解组,其他粒子作为劣解组,优解组粒子进行交叉操作,产生新的优良子代种群,如式(4)所示:

劣解组进行变异操作,通过变异生成优良基因,充分利用每个粒子信息,如式(5)所示:

2.2 精英策略

2.3 改进粒子学习模式

个体除总结自身的实践经验和向最优个体学习外,也学习其他优秀同伴的行为,尤其在进化初期,这种行为在个体的学习中应处于主导地位.为充分利用群体信息,从排序后的种群中选出前1/4 粒子,以这些粒子的均值代替个体最优指导粒子搜索,以保证种群的多样性.对基本PSO 算法中的个体极值 pt按式(6)改进:

其中,m=N/4 (取整),pt1,pt2,···,ptm为适应度值从小到大排序的前1/4 粒子对应的个体极值,改进后的速度更新公式为:

2.4 概率控制

引入一个随机决策数P,P是以迭代次数t为变量构建的函数,在迭代初期取大值,在迭代后期取小值,如式(8)所示:

若rand(0,1)≥P,则进行交叉变异等操作,否则不进行.

2.5 算法流程

对IPSO 算法流程描述如下,图1给出了IPSO 算法流程图.

图1 IPSO 算法流程图

Step 1.设置算法参数;

Step 2.随机初始化种群;

Step 3.计算每个粒子适应度值;

Step 4.判断是否进入交叉变异操作,若rand(0,1)≥P,进入Step 5,否则跳至Step 7;

Step 5.根据适应度值按升序排列粒子,前50%个粒子被定义为优解组,其余为劣解组,优解组进行交叉操作,劣解组进行变异操作,产生新的种群;

Step 6.将经过交叉变异后新产生的种群与当前迭代次数下的初始种群合并形成扩大种群,按适应度值升序排列,选出前一半粒子作为精英种群用于更新迭代;

Step 7.按式(6)更新个体最优,更新全局最优;

Step 8.更新粒子位置和速度;

Step 9.判断是否满足迭代中止标准,若迭代次数达到最大迭代次数Gmax,算法停止;否则跳至Step 3.

3 算法仿真测试

3.1 实验环境及参数设置

实验环境为:Matlab R2014b,CPU为i7-6500U@2.5 GHz,选取基本PSO[1],BreedPSO[12],SimuAPSO[14]三种算法与本文提出的IPSO 算法进行比较.算法参数的设置同原文献相同,对于BreedPSO,杂交概率取0.9,杂交池的大小取0.2;对于SimuAPSO,退火常数取0.5.各优化方法共有参数均保持一致,种群规模取400,最大迭代次数为200,学习因子均取2.

3.2 测试函数

从GEATbx中选取4个标准测试函数,测试函数维数取10 维,分别对IPSO 算法和其他改进PSO 算法性能进行了比较.其中f1、f2为单峰函数,f1用于检验算法的收敛速度和精度;f2最优位置是在一个狭长的,抛物线形的扁平山谷内,可认为拥有无数个局部极值,f3、f4为多峰函数,其二维函数图像如图2、图3所示,其局部极值的个数随维数的增加成几何级增加,f2、f3、f4主要用于检验算法跳出局部极值,全局搜索的能力,同时也能检验其收敛速度和精度.f1、f3、f4函数的全局最优均为:当xi=0,(i=1:n),f(x)=0;f2的全局最优为:当xi=1,(i=1:n),f(x)=0.为消除随机性对算法性能带来的影响,对每个测试函数采用不同PSO算法进行100 次独立运算,得到各测试函数迭代完成后的适应度值,以100 次适应度值的均值和方差作为评价指标,均值能最直观反映优化结果的优劣,检验算法的收敛速度和精度,而方差从不确定性量化的角度反映优化结果的稳定性.f1为单峰球函数,xi越接近于0,适应度值越小,优化速度及精度越高,设置成功率来评判优化性能,表1显示了不同优化方法对f1优化的结果.函数f2、f3、f4全局最优附近含有较多局部峰值,若最终的适应度值小于10−5,则认为成功搜索到全局最优解.各种不同优化算法对测试函数f2、f3、f4优化结果如表2所示.图(4)–图(7)分别为几种不同PSO算法在对函数f1～f4寻优时的平均适应度值收敛曲线,能更全面直观展示算法的迭代优化过程.

表1 测试函数f1 优化的结果

图2 Ackley’s Path 二维函数图像

图3 Griewank 二维函数图像

图4 f1 平均适应度值的对数迭代曲线

图5 f2 平均适应度值的对数迭代曲线

图6 f3 平均适应度值的迭代曲线

图7 f4 平均适应度值的迭代曲线

(1)Sphere 球函数:x∈[−5.12,5.12]

(2)Rosenbrock 函数:x∈[−2.048,2.048]

(3)Ackley’s Path 函数:x∈[−1.5,1.5]

(4)Griewank 函数:x∈[−8,8]

3.3 仿真结果分析

从表1和表2可知,IPSO 算法分别对4个测试函数进行100 次计算得到的适应度值均值和方差均小于其他PSO 算法,表明IPSO 算法收敛速度快,搜索精度高,稳定性好.对于测试函数f1,IPSO 算法计算得到适应度值均值为3.03E–25,相比其他PSO 算法,搜索精度显著提高,在最佳目标成功率上,100%达到10−20数量级,优化到10−40以下成功率达到45%,远远优于其他PSO 算法.另外,在相同条件下运行时间,IPSO 算法要比基本PSO 耗时长,与SimuAPSO 相当,比BreedPSO耗时短,从取得的优化效果来看,增加的时间完全可以接受.

图4–图7中平均适应度值收敛曲线显示了IPSO算法下降速度快,达到稳定时迭代次数少,稳定时平均适应度值远低于其他PSO 算法,进一步证实IPSO 算法具有收敛速度快、精度高的特点.从表2可知,IPSO算法在提高收敛速度和精度的同时,跳出局部极值成功搜索到全局最优解的能力显著提升,对于测试函数f2,搜索到全局最优 (1,…,1)附近位置,IPSO 算法成功率达到56%,而其他PSO 算法均小于30%,对于测试函数f3,搜索到全局最优 (0,…,0)附近位置,IPSO 算法成功率高达96%,而其他PSO 算法均小于30%.测试函数f4对比于f3,其局部极值与全局最优位置对应的适应度值相差很小且局部极值数量庞大,因此很难找到全局最优位置,IPSO 算法找到最优解(0,…,0)位置的成功率为90%,而其他PSO 算法均很难找到最优解位置.

4 结论

本文针对PSO 算法容易陷入局部极值及进化后期收敛速度慢、精度低等缺点,提出了一种融合多种策略的改进粒子群算法(IPSO).该算法采取了分组控制、精英选择、改变学习模式、引入概率等策略,通过实验仿真结果证明了IPSO 算法同其他PSO 算法相比,收敛速度快、求解精度高且容易跳出局部最优解.IPSO 算法的全局探索和局部挖掘能力均得到明显提升,较为有效地兼顾了全局与局部寻优.