Logistic型混合自适应分数阶达尔文粒子群优化算法
2017-11-01荣兵，陈华
荣 兵，陈 华
(中国石油大学(华东)理学院, 山东 青岛 266580)
Logistic型混合自适应分数阶达尔文粒子群优化算法
荣 兵，陈 华
(中国石油大学(华东)理学院, 山东 青岛 266580)
针对传统的粒子群优化算法中存在的问题及分数阶达尔文微粒群优化(FDPSO)算法收敛速度慢，收敛精度不高的问题，改进其算法中分数阶速度更新策略，同时引入Logistic型混合分数阶自适应动态调整策略，得到一种改进的自适应分数阶达尔文粒子群优化(LFDPSO)算法，并通过相应理论分析，证明了该算法在给定条件下的收敛性，并由6个经典函数的数值测验表明，Logistic型混合自适应分数阶达尔文粒子群(LFDPSO)算法在收敛精度和收敛速度上得到了有效改善与提高，粒子在局部最优时的逃逸能力、全局寻优及智能搜索能力显著增强。
分数阶；粒子群；达尔文；自适应；速度更新；收敛速度
0 引言
粒子群优化(PSO，partical swarm optimization)算法是近年来快速发展的一种智能全局寻优方法[1]。这种方法有它不可取代的寻优特点，在优化组合[2]、多目标联合搜索[3]、任务分配[4]、聚类分析[5]、神经网络[6]等众多领域得到了比较广泛的使用。PSO算法在使用中存在着一些不尽人意的地方，如在寻优的开始阶段，算法的收敛速度较快，而在全局寻优的后期，单纯的粒子群算法容易陷入早熟，进而影响粒子群算法寻优的精度，这也是群智能优化算法的一种通病。
最近几年，为了改进粒子群算法的不足之处，诸多学者做了较为深刻的探索，Jason等[7]提出达尔文粒子群优化(DPSO，Darwinian partical swarm optimization)算法，将生态环境中的自然选择的策略引入到粒子群算法之中。分数阶微积分理论(FOC，fractional ordercalculus) 作为一种快速发展的、非常重要且有用的数学工具在自然科学利于如水文建模，神经网络等领域取得的成果越来越明显[8-9]，Pires等[10]提出了分数阶粒子群优化(FPSO)算法，将分数阶微积分的相关知识引入到粒子群优化算法中，进而，通过改进其速度导数的阶数来控制FPSO算法的收敛效率。由Pires等所研究的FPSO算法中得到启示，Micael等[11]提出了一种分数阶达尔文粒子群(FDPSO，fractional order Darwinian partical swarm optimization)算法，将分数阶这一数学工具同达尔文粒子群优化算法结合起来，集中起两者的优点，较大程度上提高了收敛速度及收敛精度，实验结果也表明，较之传统的其它粒子群优化算法，该算法其在计算精度和收敛速度上均表现不俗。
本文为了进一步提高其收敛的精度及速度，改进了FDPSO算法的分数阶更新公式，但算法在后期任然存在多样性渐失，收敛速度减慢，精度降低，且算法容易陷入局部最优。陈华等[12]提出了基于logistic模型之上的一种动态加速因子的自适应微粒群优化(APSO，adaptive partical swarm optimization)算法，该算法能够有效地提高相应算法的收敛速度及收敛精度，尤其是在提高收敛速度方面，有着较好的效果，主要通过把这种logistic型的动态调整策略运用到FDPSO算法之中形成Logistic FDPSO算法，在下文中简称LFDPSO，且考虑到此模型在算法后期面临的易陷入局部最优的问题，提出了一种混合的自适应动态调整策略，在后期通过粒子群中粒子本身的状态信息来对分数阶进行调整，使其具有逃逸局部最优的能力，提高其算法的收敛速度和收敛精度。
1 分数阶达尔文粒子群(FDPSO)算法改进
1.1 PSO算法基本原理
在一个有N个粒子所构成的D维目标搜索空间的粒子群中， 用Xi=(xi1,xi2,…，xiD)表示第i个粒子的位置向量，用Vi=(vi1,vi2,…,viD)表示第i个粒子的速度向量。对应的粒子的速度和位置更新公式如下：
vid(t+1)=ωvid(t)+c1r1d(pid(t)-xid(t))+
c2r2d(pgd(t)-xid(t))
(1)
xid(t+1)=xid(t)+vid(t+1)
(2)
在式(1)中，i=1,2,…N;d=1,2,…，D；ω是惯性系数，c1、c2是加速系数；r1d、r2d是[0,1]之间的随机数；pid是第i个粒子本身找到的历史最优位置，即局部最优值点；pgd是该粒子群找到的群体中的最优位置，即全局最优值点。粒子群中每个粒子可以根据式(1)和式(2)进行迭代，最终使得算法逼近全局最优值处。
1.2 DPSO算法基本原理
DPSO基本思想是粒子群中每个粒子可以通过找到更好的适应值来获得增加自己的存活寿命的机会，同时可以通过增加新的种群粒子来提高全局寻优过程的后期搜索的速度。如果粒子存活的时间越长，则它产生后代的概率也就越大，而且后代中保存了一些适应值比较好的粒子。在粒子群中，粒子的寿命是否会缩短取决于它在目标搜索过程中有没有找到更好的适应值位置，相应的，如果没能找到延长寿命的较好的适应值，粒子群中那些较差性能的粒子可能就会被删除，当粒子群中粒子的数量减少到一定值时，该粒子群淘汰。
(3)
其中:Nkill为在粒子适应值没有任何改善的一段时间内粒子群中被删除的粒子的数目。
在该算法的实现过程中，若要产生一个新的粒子群，必须保证粒子群中没有粒子被删除，并且所存在的最大粒子群数量不能超过给定的最大值。综合上述所有要求，该算法创建新的粒子群概率仅仅为：
p=f/Ns
(4)
其中:f为[0, 1]之间的随机数，Ns为粒子群数目。
1.3 FDPSO算法中分数阶速度更新策略的改进
根据文献[13-16]，可以得出对传统导数的极限定义为：
(5)
把这个定义扩展到任意的实数α就得到了Grunwald-Letnikov分数阶导数的定义：
(6)
即α阶Grunwald-Letnikov分数阶导数。整理得另一种表达式的形式为：
(7)
式(7)，离散时间的实现表达式可以被定义为：
(8)
其中:T为采样周期，r为截断阶数。
假定式(1)的惯性权重ω=1以及采样周期T=1，由文献[17]我们可以得到下面的表达式：
aDtαvid(t+ 1) =c1r1d(pid(t)-xid(t))+
c2r2d(pgd(t)-xid(t))
(9)
随着迭代次数的增加，当代粒子群中的粒子与最初几代的关系逐渐淡化，在本文中我们取r=4，即我们只保留前4代的速度向量，并取T=1，由式(7)和式(8)，可以得到：
aDtαvid(t+ 1) =vid(t+ 1)-αvid(t) +
(10)
再由式(9)和式(10)，得改进的速度更新策略如下：
c1r1d(pid(t)-xid(t))+c2r2d(pgd(t)-xid(t))
(11)
其形式不同于文献[11，17]等论文中的分数阶速度更新策略：
c2r2d(pgd(t)-xid(t))
(12)
虽然形式相似，但数值实验结果表明无论在收敛精度还是收敛速度上均有较明显的改善。
2 Logistic型混合分数阶自适应动态调整策略的引入
传统的调整分数阶α的方法是在[0.5,0.8]之间线性减小，具体策略为：
(13)
其中:t为当前的迭代步数，nger为总的迭代步数。
这种方法采取的是对分数阶的线性减少，在算法的后期，算法陷入局部最优的可能性会变大，为了更好地避免算法的早熟问题的出现，本文提出一种基于logistic模型之上的混合调整分数阶α的自适应策略。根据粒子最优位置15步没有发生较好变化的前后将算法分为前后两个阶段，在每一阶段采取不同的分数阶α自适应调整策略。
在算法的第一阶段，分数阶α调整策略在算法过程中，为避免其早熟,α值在第一阶段初期应较大，并且α值减小的速度应较大些，能加快算法的收敛速度；在第一阶段后期，α值减小的速度应趋缓,易搜索局部最优值，使算法趋于稳定。设α的最小值和最大值分别为αmax和αmin，若迭代开始时α的衰减率为a，随着迭代次数的增加而衰减率减小，当α减小到最小值αmin时，α停止减小，即衰减率为零。因此，α的变化规律符合logistic模型[18-19]，即：
(14)
对式(14)使用分离变量法来求解，可得到相应缩放因子α的动态调整公式：
(15)
可以通过调整a值来调整加速因子α的下降速度。给定的初始衰减率a值越大些，α在算法前期的下降速度就越快写，反之，c1的下降速度则比较慢。当t=0时，α=αmax，而当t→+∞时，比较容易证明α=αmin。
在算法的第二阶段，分数阶α值比较小，为了有效避免其早熟现象的发生概率及增大粒子的拓展搜索空间的能力，我们采取一种根据粒子的状态和最优粒子的轨迹信息进行动态调整，具体方法如下：
1)求出粒子群中每个粒子与其他粒子之间距离的和。
(16)
2)参照式(14)求出最优粒子与其它粒子的距离之和dgbest。
3)计算分数阶α的阶数。
(17)
Logistic型混合自适应粒子群优化算法(LFDPSO)算法流程如下：
(1)初始化
a)随机生成所有粒子的速度和位置向量；
b)pi=Xi，i=1，2…,n；
c)将arg{minf(Xi)}赋给gbest其中f(·)为适应值函数；
(2)终止条件判断
a)如果终止条件已经达到，gbest即为最优解；
b)否则执行步骤3；
(3)循环i从1到n
a) 判断粒子处于第几阶段，根据(15)及(17)更新α；
b) 根据式(11)和式(2)更新Vi和Xi；
c) 计算第i个粒子的适应值；
d)如果粒子群变得更好则奖励粒子群：产生后代粒子、延长粒子寿命；
e)否则惩罚粒子群：销毁粒子群、缩短其寿命；
f)如果f(Xi)优于f(pi)，则pi=Xi；
(4)结束循环
(5)更新gbest=arg{minf(pi)}
(6)返回步骤2。
3 LFDPSO算法的收敛性分析
(18)
由式(2)xt+1=xt+vt+1得到vt=xt-xt-1，进一步得到：
(19)
整理得出递推公式：
(20)
式(20)可以用下面的矩阵乘积的形式表示：
上面矩阵的特征多项式为：
(21)
该特征多项式的一个根为λ1=1.0，设其他的特征根分别为λ2，λ3，λ4，λ5，λ6，则式(20)的当前关系式为：
(22)
其中:k1,k2,k3,k4,k5,k6均是常数。
下证xt的收敛性，即：
(23)
当λ>1时，特征多项式中(λ-1)恒正，如果此时另一部分，此处我们记为f(λ)恒正则证毕，当λ<1时，特征多项式中(λ-1)恒负，此时f(λ)如果恒负则证毕，由前面的条件容易求出f(λ)当λ=1时大于0，当λ=-1时小于0，对f(λ)求导得：
f′(λ)=5λ4-4λ3(1+α-φ1-φ2)+3λ2[α+
(24)
由前面的条件容易求出当|λ|>1时f′(λ)恒大于0，故当λ>1时f(λ)>f(1)>0，当λ<1时f(λ)
4 数值实验及结果分析
为了验证Logistic型混合自适应粒子群优化(LFDPSO)算法的较之传统的分数阶粒子群优化(FO-PSO)算法，达尔文粒子群优化(DPSO)算法，分数阶达尔文粒子群(FDPSO)算法的性能，选取该6个典型的实验函数进行测试，它们是在群智能优化算法中被广泛采用的测试函数(求最小值)，即Sphere、Rosenbrock、DeJong F4、Rastrigin、Griewank和Ackley函数[20]，其表达式为：
Sphere函数:
(25)
其中:xi∈[-50，50]，i={1,2,…,D}，f(x*)=0.0。
Rosenbrock函数:
(26)
其中:xi∈[-100，100]，i={1,2,…,D}，f(x*)=0.0。
DeJong F4函数:
(27)
其中:xi∈[-20，20]，i={1,2,…,D}，f(x*)=0.0。
Rastrigin函数:
(28)
其中:xi∈[-5.12，5.12]，i={1,2,…,D}，f(x*)=0.0。
Griewank函数:
(29)
其中:xi∈[-600，600]，i={1,2,…,D}，f(x*)=0.0。
Ackley函数:
(30)
其中:xi∈[-32，32]，i={1,2,…,D}，f(x*)=0.0。
这6个函数中前3个为单峰函数，后三个为多峰函数，它们的全局最优值为f(x*)=0.0。本章试验中的算法均选取相同参数r1d、r2d∈[0.3,0.6]，ω=1，c1=1.5，c2=1.5，其中除LFDPSO算法外的分数阶α采取的是线性减小，具体策略如式(12)。
其数值实验结果如图1所示，通过对比可以得到在迭代步数相同的情况下(本文为迭代200步)，改进后的LFDPSO算法其最终收敛精度明显高于分数阶粒子群优化(FO-PSO)算法，达尔文粒子群优化(DPSO)算法，分数阶达尔文粒子群(FDPSO)算法，在收敛速度方面，尤其在迭代后期收敛的速度的改善较为明显，且有比较知道算法在后期具备了逃逸局部最优的能力，全局收敛能力及智能搜索能力加强。
图 LFDPSO算法在不同的测试函数上的性能比较
5 结束语
分数阶导数的应用对于改进粒子群算法来说具有非常重要的意义，使得粒子群算法中局部和全局速度特点更容易被算法理解，换句话说，即为粒子群算法更加智能化。
本文通过改进FDPSO算法中分数阶速度更新策略，将分数阶更好的融入到PSO算法中来，充分利用了粒子群在寻优过程中的历史信息，并采取了Logistic型混合的分数阶自适应动态调整策略，使得再改善收敛精度及收敛速度的基础上，提高了粒子扩展搜索空间的能力，通过实验验证，LFDPSO算法达到了较好的效果，但是在求解某些多峰函数的时候结果仍有陷入局部最优的情况，在陷入局部最优时，粒子如何逃逸仍然是下面一段时期的工作重点，在下一步工作中，将惯性权重因子及加速因子的调整策略与我们的方法结合，寻找效果更好的方法，并将其应用到电磁计算如随钻侧井的参数反演问题中，加快问题求解速度及提高问题的精度。
[1] Kennedy J, Eberhart R. Particle swarm optimization [A]. Proc IEEE International Conf on Neural Networks[C]. 1995:1942-1948.
[2] Chen W N, Zhang. A novel set-based particle swarm optimization method for discrete optimization problem[J]. IEEE Transactions on Evolutionary Computation, 2010, 14 (2): 278-300.
[3] Zhang T, Hu T S, Zheng Y, et al. An improved particle swarm optimization for solving believed mulitiobjective programming problem[J]. Journal of Applied Mathematics, 2012, 2(4): 1-13.
[4] Ho S Y, Lin H S, Liauh W H, et al. OPSO: Orthogonal particle swarm optimization and its application to task assignment problems[J]. IEEE Transactions on Systems, Man, Cybernetics A: Systems, Humans, 2008, 38(2):288-298.
[5] Nie F, Tu T, Pan M, et al. K-Harmonic means data clusteing with PSO Algorithm[M]. Springer Berlin Heidelberg, 2012:67-73.
[6] Varshney S, Srivastava L, Pandit M. Parameter tuning of statcom using particle swarm optimization based neural network[J]. Intelligent and Soft Computing, 2012, 130(3): 813-824.
[7] Tillett J, Rao T, Sahin F, et al. Darwinian particle swarm optimization[A]. Indian International Conference on Artificial Intelligence[C]. 2005:1474-1487.
[8] Gutierrez R E, Rosario J M, Machado J T. Fractional order calculus: basic concepts and engineering applications[J]. Mathematical Proble- ms in Engineering,2010, 2010:1-19
[9] Machado J A T, Jesus I S, Barbosa R, et al. Application of fractional calculus in engineering[J]. Dynamics, Games and Science I, Springer Proceedings in Mathematics, 2011, 1: 619-629.
[10] Pires J A, Moura P B, Oliveir A M, et al. Particle swarm optimization with fractional-order velocity[J]. Nonlinear Dynamics, 2010, 61(1-2): 295-301.
[11] Couceiro M S, Rocha R P, Fonseca F N M, et al.Introducing the fractional - order Darwinian PSO[J]. Signal, Image and Video Processing, 2012,6(3):343-350.
[12] 陈华,范宜仁,等.一种动态加速因子的自适应微粒群优化算法[J].中国石油大学学报,2010, 34(6): 173-176.
[13] Podlubny I. Fractional differential equations[M]. San Diego: Academic Iess, 1999.
[14] Lshehawey E, Elbarbary E F, et al.On the solution of the endolymph equation using fractional calculus[J]. Appl. Math. Comput., 2001, 124(3): 337-341.
[15] Camargo R F, Chiacchio A O, Oliveira E C. Differentiation to fractional orders and the fractional telegraph equation [J]. Math.Phys., 2008,49(3): 033-505.
[16] Diethelm K. The analysis of fractional differential equations[M]. Berlin:Springcr-Vd:lag, 2010.
[17] Pires E J S, Machado J A T, Oliveira P B M, Cunha, et al. Particle swarm optimization with fractional-order velocity[J]. Nonlinear Dyn,2010,61(1/2): 295-301.
[18] Munkres J R. Topology [M]. 2nd ed. London: Prentice-Hall Inc, 2000.
[19] Guez-Lopez J S R, Romaguera S. The relationship between the Vietoris topology and the Hausdorff quasiuniformity[J]. Topology and Its Applications, 2002, 124: 451-464.
[20] 郭 通,兰巨龙,李玉峰,等.自适应的分数阶达尔文粒子群优化算法[J].通信学报, 2014, 35(4): 130-140.
Logistic-model Hybrid Adaptive Fractional Order Darwinian Partical Swarm Optimization Algorithm
Rong Bing， Chen Hua
(College of Science, China University of Petroleum (East China), Qingdao 266580, China)
Aiming at the problems existing in the traditional particle swarm optimization algorithm and the problems existing in convergence speed and precision of fractional order Darwin particle swarm optimization (FDPSO) algorithm, improved the fractional order velocity update strategy of the algorithm, at the same time introduce dynamic logistic model hybrid adaptive strategy of the fractional order to form LFDPSO algorithm, through theoretical analysis and prove the convergence of the iterative algorithm under given conditions, and the experiments by six classical test functions show that the LFDPSO algorithm on the convergence accuracy and convergence speed has been further improved and enhanced, the escape ability of particles in local optimum, global optimization and intelligent search ability have achieved effective improvement.
fractional order; particle swarm; Darwinian; adaptive; speed-update; convergence rate
2017-02-23；
2017-03-14。
国家自然科学基金(41474100)；山东省自然科学基金(ZR2013DM015)。
荣 兵(1991- )，男，山东滨州人，硕士研究生，主要从事应用数学(群智能优化算法、并行算法) 方向的研究。
1671-4598(2017)08-0221-05
10.16526/j.cnki.11-4762/tp.2017.08.057
TP3
A
陈 华(1972- )，男，山东聊城人，硕士生导师，副教授，主要从事数学领域方向的研究。
