基于引力搜索机制的花卉授粉算法

基于引力搜索机制的花卉授粉算法

引用格式：肖辉辉、万常选、段英明、谭迪林；基于吸引力搜索机制的花授粉算法《自动学报》，2017，43（4）：576-594。英国剑桥大学学者Yang于2012年提出一种新型元启发式群智能优化算法—花朵授粉算法(Flowerpollinationalgorithm,FPA)但是,花朵授粉算法与经典的粒子群算法等群智能算法类似,也存在易陷入局部极值,后期收敛速度慢等不足,尤其对于多局部极值、高维的较复杂优化问题.为此,国内外不少学者对该算法进行了改进:Wang等针对FPA算法的局限性,本文提出基于引力机制的花朵授粉算法(Flowerpollinationalgorithmbasedongravitationalsearch,GSFPA).在GSFPA算法中对基本FPA算法的全局寻优部分进行了改进:利用种群个体间的万有引力和花朵授粉算法本身的莱维飞行两种机制融合来共同更新花朵个体的位置,有效地跳出局部极值,提高全局搜索能力和收敛速度.通过三类共16个基准测试函数、6个复合复杂测试函数、2个工程实例的仿真实验结果,验证了改进算法的有效性和优越性,GSFPA算法相比FPA算法在一定程度上有效地避免了过早收敛,且提高了FPA算法的收敛速度、寻优精度、鲁棒性等性能.1花花植物花授粉算法显花植物的授粉可分为异花授粉及自花授粉两种:异花授粉一般需要传播者,如自然界的鸟、蜜蜂等,能飞行到较远的地方,且其飞行的行为具有莱维飞行特征,即跳跃或飞行的步长服从莱维分布,故异花授粉可以发生在距离较远的随机地方,在FPA算法中模拟这种授粉方式为全局寻优(授粉).另外,自花授粉是植物成熟的花粉颗粒传播到自身的花朵上,在FPA算法中模拟这种授粉方式为局部寻优(授粉).同时,在FPA算法中假设:优化问题中的一个解对应于一朵花的一个花粉配子,每株显花植物只开一朵花,且只有一个花粉配子.花朵授粉算法模拟自然界中显花植物花朵传粉过程,还需假定如下规则规则1.生物异花授粉是指携带其花粉的传播者(鸟、蜜蜂等)通过莱维飞行进行的全局授粉过程;规则2.非生物自花授粉是指植物花朵的自身局部授粉过程;规则3.繁衍概率指花的常性,其值的大小与求解问题的两朵花的相似性成一定的比例关系;规则4.全局授粉和局部授粉之间的转换受转换概率p∈[0,1]控制,因花朵会受到物理位置上的邻近性以及风等其他自然因素影响,在算法中起着重要作用.因此,在花朵授粉算法中,全局授粉(优化)和局部授粉(优化)两部分是花朵个体进化的核心,Yang等其中,X其中,λ=3/2,Γ(λ)是标准的伽马函数,S由式(3)得到:其中,式中的σ其中,ε是[0,1]上服从均匀分布的随机数,x算法1是花朵授粉算法的伪代码,其中,n为花朵的个数,p为转换概率,Niter为最大迭代次数,ε是[0,1]上服从均匀分布的随机数,f算法1.FPA花朵授粉算法中,转换概率p在平衡全局和局部寻优中起着重要作用,文献[10]经过仿真实验验证,当p=0.2时,算法的全局寻优和局部寻优之间的转换达到最佳状态,算法的性能最优.2基于吸引力搜索策略的花卉授粉算法2.1引力搜索算法的描述2009年,伊朗的克曼大学教授EsmatRashedi等根据牛顿万有引力定律提出了引力搜索算法(Gravitationalsearchalgorithm,GSA).该算法概念简单,容易实现且需要调整的参数少,已有学者证明其收敛性优于PSO(Particleswarmoptimization)、GA(Geneticalgorithm)等其他智能算法引力搜索算法中,描述个体的主要属性有位置、惯性质量、主动引力质量和被动引力质量.个体的位置为优化问题的解,函数适应度值由其受到的作用力和质量决定,也就是说惯性质量、主动引力质量和被动引力质量3个属性由适应度函数确定,算法的迭代过程中通过适当调整个体的惯性质量、主动引力质量和被动引力质量来指导个体的进化,直到所有个体都受到最重个体的引力作用而靠近其位置,从而找到最优解(惯性质量最大的个体).根据文献[11],引力搜索算法中先随机生成个体的初始位置和初始速度,假设种群有n个个体,在D维的搜索空间以一定的速度进行移动,则第i个个体的位置为其中,x根据牛顿万有引力定律,在第t时刻的第k维空间上,个体i和个体j的作用力定义为其中,M其中,Niter为最大迭代次数;G另外,R个体i的惯性质量M其中,fitness当求解目标函数最小值问题时:当求解目标函数最大值问题时:根据牛顿运动定律,某时刻个体i在第k维空间上所受的引力是其他所有个体的引力之和:其中,rand根据牛顿第二运动定律,物体运动的加速度与其所受外力的大小成正比,与其质量成反比.因此,在t时刻个体i在k维解空间上的加速度定义如下:最后,在每次迭代过程中,个体的速度和位置更新公式如下:其中,rand2.2利用万有引力机制来促基本花朵授粉算法中的全局授粉(优化)部分中花朵个体是借助于携带其花粉的传播者(鸟、蜜蜂等)通过莱维飞行进行位置更新,花朵个体借助莱维飞行所产生的较大跳跃和不均匀的随机移动步长在一定程度上能避免被局部极值所吸引,花朵授粉算法具有较强全局寻优能力.但是,若随机生成的莱维飞行步长过小则会减慢算法的收敛速度,且也存在使算法陷入局部最优,若步长过大,则容易跳离全局最优值.因此,花朵授粉算法全局授粉(优化)部分的个体位置的更新不能单纯依靠莱维飞行来改变步长,这在一定程度上依然存在陷入局部极值的问题.为此,本文针对该问题在花朵授粉算法的全局授粉(优化)部分引入引力机制,在引力的作用下花朵个体向质量大的个体移动,而质量最大的个体占据着最优位置,个体间的相互引力促进个体进行优化信息的共享,从而引导个体向最优解区域展开搜索.因此,万有引力机制能使花朵利用自身与其他花朵间的万有引力来牵制本身不均匀的随机游走的莱维飞行机制,使花朵受莱维飞行和个体间的引力的双重影响,引导种群向最优解靠近.所有的花朵个体通过万有引力相互吸引,并通过引力使所有的花朵朝惯性质量较大的个体方向移动,惯性质量大的花朵(当前较好个体)比惯性质量小的花朵(当前较差个体)移动缓慢.通过这种引力作用,花朵个体间相互交流、相互协作,保证了算法的开采能力.另外,万有引力的加速度与物体所受外力的方向一致,也就说明加速度的方向与大小直接影响着花朵的移动方向和大小.在花朵授粉算法中,花朵间产生的加速度直接左右着花朵的迭代位置的改变,进而引导算法的全局授粉(优化).因此,花朵授粉算法中的式(1)修改为式(18):其中,a由式(18)可以看出,改进后的花朵位置的更新中既考虑到了花朵授粉算法中本身的莱维飞行机制,又考虑到了种群中个体受到的万有引力的作用.这样,在花朵授粉算法的全局授粉(优化)部分引入引力机制,使花朵个体的位置随迭代进化受莱维飞行和引力两种机制的共同作用:一方面,利用莱维飞行的随机性和不均匀性的跳跃动作使花朵个体跳离局部极值;另一方面,花朵个体间的引力机制使花朵间进行信息共享,朝着质量大(最优解)的花朵移动.2.3gsfpa算法介绍针对花朵授粉算法的局限性,以及花朵授粉算法中所特有的莱维飞行机制和引力搜索算法中的引力机制,本文提出了基于引力搜索机制的花朵授粉算法GSFPA,改进算法中利用引力搜索算法中的引力策略作用于花朵授粉中全局寻优(授粉)部分,与花朵授粉算法本身的莱维飞行机制共同指导种群的迭代优化.GSFPA算法的具体实施步骤如下:步骤1.初始化GSFPA算法的参数:种群数N,转换概率p,最大迭代次数Niter,维数D,万有引力初始系数G步骤2.随机初始化种群的位置,计算每个解的适应度值,并求解出当前的最优值、最优解和最差值;步骤3.根据式(8)计算个体的万有引力系数G步骤4.根据式(10)和式(11)计算惯性质量M步骤5.根据式(14)计算个体i的引力之和F步骤6.根据式(15)计算个体i的加速度a步骤7.若转换概率p>rand,按式(18)对解进行更新,并进行越界处理;步骤8.若转换概率p<rand,按式(5)对解进行更新,并进行越界处理;步骤9.计算步骤7或步骤8的适应度值,并更新全局最优值、全局最优解和全局最差值;步骤10.判断结束条件,若满足,退出程序并输出最优值及最优解,或者,转步骤3.2.4gsfpa算法描述和描述对于一种优秀的群智能优化算法,一方面要求其寻优性能要好,另一方面要求其时间复杂度低.改进算法是否有效、可行,除了性能上有较大的提高,算法的时间复杂度应该比较低,相对于原算法,运行的时间应该不能过长.在群智能优化算法中其运行时间主要用在种群个体的适应度值评估上,即算法找到问题最优解或接近问题最优解所需要进行的迭代次数.假设优化问题函数为f(x),解空间的维数为d,则根据FPA算法的描述和时间复杂度符号O的运算规则,FPA的时间复杂度为:T(FPA)=O(d+f(d)).从GSFPA算法步骤可以看出,步骤3∼步骤6是改进算法增加的步骤,即GSFPA包括计算万有引力系数操作、计算惯性质量、计算引力之和、计算加速度和FPA基本操作,根据上文对这几个操作的详细描述和时间复杂度符号O的运算规则,可以推导出各操作的时间复杂度:T(计算万有引力系数操作)=O(1);T(计算惯性质量)=O(d+f(d));T(计算引力之和)=O(d+f(d));T(计算加速度)=O(d+f(d)).因此,T(GSFPA)=T(FPA)+T(计算万有引力系数操作)+T(计算惯性质量)+T(计算引力之和)+T(计算加速度),化简后可以得到GSFPA算法的时间复杂度亦为O(d+f(d)),与FPA算法的时间复杂度属于同一数量级,说明GSFPA算法的时间复杂度没有很大的提高.3实验模拟与分析3.1试验设计和测试函数为了验证本文算法的正确性和有效性,本节通过对16个包括单峰、多峰、低维、高维的基准测试函数3.2改进算法性能对比分析本节实验的参数设置为:5种算法的种群个数都取n=20,最大迭代次数都为MaxNiter=500,GSFPA和FPA的转换概率p=0.2;DEBA的其他参数设置同参考文献[17];PSO算法中,w=0.9,c1=c2=2;ABC算法中,limit=100;本文算法的G1)类型I:高维单峰函数对比算法ABC、PSO、DEBA、FPA、GSFPA分别对本文的5个高维单峰函数f2)类型II:高维多峰函数表3为第II类测试函数的结果,在该类测试函数中,大量的局部极小点分布在其解空间中,算法对全局最优值的寻找有一定的困难.但从表3中表明,除f3)类型III:低维函数此类测试函数为低维函数,具有强烈震荡的特点,且该类函数的全局最优值被大量的局部最优值所包围,这使得全局极小值很难找到,因此,群智能算法的全局寻优能力通常用此类函数来进行测试.本文用5种算法对此类函数进行寻优能力对比测试,实验仿真结果如表4所示.对于函数f4)5种算法的寻优性能对比分析图为了更直观地对比本文算法与ABC、PSO、FPA和DEBA的寻优性能,突出GSFPA算法的优势.鉴于篇幅有限,给出了3类基准测试函数中每类的部分函数的性能分析图,图2为5种算法适应度值的收敛曲线图(为了方便收敛曲线的显示和观察,对部分函数的目标函数值取以10为底的对数),图3为5种算法全局最优值方差分析对比图,图4为5种算法独立运行50次的最优适应度值比较图.从图2可以看出,对于12个测试函数,GSFPA具有更好的寻优能力,其收敛速度、优化精度明显优于ABC、PSO、DEBA及FPA算法,对于绝大部分函数,GSFPA算法只要迭代几次就能找到理论最优值,尤其对于函数f3.3不同维数下的优化均值限于篇幅,本节选用3个高维多峰测试函数,维数从50∼300维递增50维变化,以其优化均值及其平均变化率为评价指标,测试本文算法GSFPA相对于FPA独立运行50次的性能随函数维数的增加而变化的情况,结果如表5所示,其中,平均变化率=∑((后一次维数的优化均值-前一次维数的优化均值)/前一次维数的优化均值)/5.从表5可以看出,随着维数的增加,GSFPA的优化均值都保持不变,特别是对于函数f图5是这两种算法在不同维数下的优化均值的曲线图.从图5中可以直观地观察到,FPA的优化均值随着维数的增加而单调增加,且增加的幅度较大,而GSFPA的优化均值保持不变.这说明随着维数的增加,GSFPA的优化性能基本不降低,即不会随着复杂高维多极值函数的维数的增大而陷入“维灾难”,相对于FPA更能突出其优势.因此,采用引力策略能使FPA跳出局部最优,在高维的多峰函数的优化中,寻优效果同样要好,进一步验证了本文算法的可行性和有效性.3.4与其他群体智力优化方法的性能比较3.4.1在其他常用算法中的寻优性能比较在实际工程应用中,利用启发式群智能算法对多峰、高维复杂优化问题进行优化时,普遍存在收敛精度低、优化后期收敛速度慢、易陷入局部极小等问题,为了进一步验证本文算法在优化高维单峰、高维多峰函数时的优越性,将GSFPA算法和近期提出的知名群智能算法的寻优能力进行对比.为了比较的公平性,且突出本文算法的寻优性能,本文算法的实验参数条件比参考文献的实验条件更苛刻,本节的具体实验参数设置为:GSFPA算法:种群数N=10,维数D=100,迭代次数都为100;文献[18](Aparticleswarmoptimizationalgorithmwithvariablerandomfunctionandmutation,PSO-RM):种群数N=30,维数D=30,迭代次数都为103.4.2显著性检验pso为了进一步佐证GSFPA算法的优化能力的优势和该算法的可行性,利用其对Liang等提出的CF1∼CF6多峰复杂测试函数表7给出了5种算法在6个测试函数上的寻优实验结果,其中,Wicoxon表示30次结果中应用显著性水平α=0.05的Wilcoxon秩检验的结果,“+,-,≈”分别表示本文算法的优化性能要优于、差于、相当于其他4种算法.从表7可以获知:GSFPA在CF1,CF2,CF6函数上的性能要好于其他4种算法;对于函数CF4,GSFPA的性能跟PSO算法相当,但要优于FPA,ABC,ASFA算法;在函数CF3和CF5上,GSFPA的性能虽然要劣于ABC,但要优于ASFA,FPA;对函数CF3,GSFPA性能与PSO相当,而在函数CF5上,GSFPA要好于PSO.综上所述,GSFPA在多峰复杂函数上的优化能力要优于其他4算法,说明本文把引力搜索机制融入到花朵授粉算法中是可行有效的.4sdfpa算法的应用和结果分析4.1弹簧张力问题的分析为了进一步验证本文算法的有效性和正确性,选用弹簧张力设计问题和压力管设计问题作为工程实例.弹簧张力的结构图如图6所示,该问题是在x该问题的数学模型描述如下:分别利用GSFPA算法和基本花朵授粉算法对上述弹簧张力设计问题进行求解,并