多策略混合的花朵授粉算法

姚光磊,熊菊霞,杨国武,郑宏宇

1(广西民族大学 数理与物理学院,南宁 530006)

2(电子科技大学 计算机科学与工程学院,成都 611731)

0 引 言

工业、信息、管理、交通等领域中的大量科学应用难题都能归类为优化问题,或能使用处理优化问题的方法论来处理.优化领域难题历来都是研究者们公认的重点研究课题.虽然成熟的优化理论与方法已在优化问题中得到了广泛的应用,但随着人类生产力的提升以及科学技术的高速发展,现实世界中所面临的优化问题逐渐增多,并且呈现出规模大、高维、非线性、多目标、多约束、不连续、不可微等一系列复杂特征,这使得专家学者们很难从分析问题的数学特性角度运用传统的优化方法来求解问题.即使能用传统的优化方法求解大规模复杂优化问题,也会存在求解效率低等缺陷.于是,探索出高效率、高并行、自适应性、强健的新型智能优化方法来求解大规模高复杂性优化问题,已成为工程应用领域中一项紧迫且长期的研究课题,不仅在理论方向有深层次意义,而且在实际应用具有广泛的前景.

受人类智能、生物群体社会性或自然现象规律的启发,学者们创造了大量智能优化算法,主要囊括5大类:进化类算法、群智能算法、模拟退火算法、禁忌搜索算法、神经网络算法.在过去的几十年中,在智能优化研究中陆续出现了很多新型优化算法,但是没有一种算法是能够满足所有的优化问题,所以一直有大量新的优化算法不断地被提出或者改进.针对复杂问题和工程优化问题,利用群智能的元启发算法解决优化问题有着满意的效果,从经典的遗传算法(GA)、禁忌搜索算法(TS)、免疫算法(IA)、蝙蝠算法(BA)、蚁群优化算法(ACO)等到近些年来提出和拓展的人工电场算法(AEFA)、蝗虫优化算法(GOA)、哈里斯鹰优化算法(HHO)、正余弦优化算法(SCA)等.这些算法可以归结为两大类:基于个体和基于群体的.第1类只生成一种优化解决方案,而第2类会生成多个解决方案并优化.

众所周知,花朵是地球上最普遍、最吸引人的植物之一.通过风、鸟、雨水等介质,花朵能将花粉带到适合生长的地方,这是大自然中无比奇妙的繁衍过程.2012年Yang提出花朵授粉算法(Flower Pollination Algorithm,简记为FPA)[1],用来模仿花朵授粉过程.FPA借鉴了花粉授粉系统的运行过程,是元启发类型算法的一种.此算法效仿了花朵授粉系统的两种机制:异花授粉和自花授粉.FPA具有算法简单、参数少、包容性强、容易实现等优点.因此,FPA已经被应用于诸多现实问题并取得较好的效果,比如:结构优化[2]、 经济分配[3]、背包问题[4]、旅行商问题[5]等.

自FPA被提出以来,国内外诸多学者对其进行了一系列的改进.Chakraborty等人[6]提出了一种混合差分进化的花朵授粉算法(A Hybrid Differential Evolution-Flower Pollination Algorithm,DE-FPA),将差分进化算法与花朵授粉算法相结合,利用差分进化算法增强了全局搜索的能力,实验结果表明改进后的新算法在寻找足够优的解和摆脱局部最优解方面具有更好的能力.Ouadfel S等人[7]将Social spiders optimization与花朵授粉相结合,提升算法寻优能力.Zhou Y等人[8]提出了 基于精英反向学习的花朵授粉算法(Elite Opposition-Based Flower Pollination Algorithm,EOBLFPA),利用种群精英的信息提升算法寻优能力.贺智明等人[9]提出了一种基于动态全局搜索和柯西变异的花授粉算法(Flower Pollination Algorithm Based on Dynamic Global Search and Cauchy Mutation,DCFPA),实验证明该算法有着较好的收敛速度以及收敛精度.肖辉辉等人[10]提出一种基于引力搜索机制的花朵授粉算法,个体在通过优化信息的共享向质量大(最优位置)的个体靠近,且个体间的万有引力牵制莱维飞行的随机游走.李克文等人[11]提出了一种基于混合策略改进的花朵授粉算法(Flower Pollination Algorithm Based on Hybrid Strategy,HSFPA),使用一种自适应的转换概率策略,以动态的方式切换全局搜索与局部搜索,以提升算法各方面性能.

虽然花朵授粉算法(FPA)在解决较为简单的问题时能够取得不错的结果,但在求解一些较复杂的问题时却表现得不尽人意.因此,本文在FPA算法的基础上,从多个角度添加不同的改进策略,提出多策略混合的花朵授粉算法(MFPA),使其在解决多特征、复杂问题上具有收敛速度快、收敛精度高等优点,为处理复杂问题提供一种新思路.多策略主要包括自适应的控制策略、改进的全局搜索策略、改进的局部搜索策略、基于梯度信息的精英扰动策略、特征选择策略.自适应控制策略能够很好地把控两种花朵授粉过程,使其达到平衡.特征选择策略能够将复杂问题分成一系列较简单的问题,先求解简单问题,最后再将简单问题的解融合在一起,以此提升算法各方面的性能.

1 花朵授粉算法(FPA)

FPA借鉴了花粉授粉系统的运行过程,是元启发类型算法的一种.自然界中的有花(被子)植物约为地球上植物物种的百分之八十.授粉过程是地球最自然、最有意义的活动之一.授粉过程需要将花粉从某个花卉转移到另一个花卉上,从而能够进行繁殖,迁移过程一般有以下方式:非生物因素(花粉由风进行转移)和生物因素(花粉由昆虫等动物转移).前者类型花粉来源具有随机性强、距离远的特点,称为全局授粉(异花授粉)过程.后者类型的花粉通常来自自身所属的花卉或者自身所属植株的花卉,属于局部授粉(自花授粉)过程.

在FPA算法中,将花卉、花粉、植株视为等价的概念,将花粉看成一个可行解,将自花和异花授粉过程视作为寻找最优解的过程.该过程主要由以下面3个部分组成:

1)全局搜索利用莱维飞行效仿异花授粉;

2)局部搜索效仿自花授粉;

3)转化概率p控制异花授粉过程和自花授粉过程转换.

异花授粉过程能够进行大范围的传播,更新公式为:

(1)

(2)

(3)

σv=1

(4)

自花授粉过程主要以风等因素进行传播,传播范围小,更新公式为:

(5)

2 多策略混合的花朵授粉策略

2.1 自适应控制策略

FPA算法通过控制因子p选择全局搜索与局部搜索.FPA为每一个个体赋予控制因子,能提高每一个个体的自主性,但是FPA采用固定的控制因子p,让种群不能有效地朝着首要目标前进,不符合动物群体的社会属性.受到文献[11]的启发,可以比较当前个体与种群最优个体信息,自适应地调整控制因子.控制因子p过大或者过小,会导致算法陷入全局搜索或者局部搜索策略,导致算法稳定性变差.本文提出的控制概率模型如下:

(6)

由公式(6)易知:当R>0.5时,p(t)由1～0随迭代线性递减.随着迭代,算法探索主体由全局搜索向局部搜索转变.由函数cos(x)在[0,π/2]的变化曲线得知,p(t)中期变化速率快,使种群探索方式能够快速完成从全局到局部方式的切换.当R<0.5时,p(t)受到自身到最优个体的距离影响,距离越小p(t)越大,以全局搜索为主,在算法后期可以缓解种群堆积、陷入局部最优的现象.

2.2 改进的全局搜索策略

全局搜索的目的是提高算法的收敛速度,维护种群多态性.分析FPA算法得知:莱维飞行和最优个体信息为种群迭代在全局授粉过程提供动力与方向.利用莱维飞行的随机性,能够很大程度保持种群多样性,增强问题空间的挖掘能力,最优个体能够为种群更新提供方向.FPA算法始终以当前个体为基准最优个体提供方向进行更新.本文提出的改进的全局搜索策略添加反向过程:以最优个体为基准,当前个体为其提供方向,使用自适应控制策略给出的控制因子来控制选择全局更新策略,具体公式为:

(7)

A=2a·r1-a

(8)

a随迭代公式从2～0线性递减,r1满足正态分布N(0,1)的随机数.

从公式(7)可以看出:在算法前期p(t)较大时,种群更新以第1个式子为主,使得种群能够较快地探索最优个体的邻域,加速了算法收敛速度.到算法后期p(t)较小时,则会增加以第2个公式更新的个体,在莱维随机数的控制下,能够很大程度地保持种群的多样性.r1∈N(0,1)理论上可以取到任何实数,使得eA∈(0,+∞),从而全局搜索能够布满整个问题空间.

2.3 改进的局部搜索策略

FPA算法的局部搜索策略是以当前个体为基础,以两个随机个体向量差值为方向及随机权重为步长进行更新.该策略具有一定的盲目性和随机性.为了降低该策略的随机性,本文利用梯度信息与种群最优个体信息为种群提供探索方向.但是,梯度信息存在两个主要缺点:1)在平坦区域,梯度过小导致个体陷入停滞;2)在较为陡峭的位置,梯度较大,从而导致个体跳出局部最优解的探索区域,降低算法精度.

为了缓解梯度更新带来的两种不利情况,将梯度向量归一化并使用群体最优个体为个体更新提供信息.具体公式如下:

(9)

其中eαlcos(2πl)为旋转因子使得种群以螺旋路径靠近最优个体,α为对数螺旋形状的常量系数,l为[-1,1]中均匀分布随机数,Grad为当前个体的梯度信息.采用权重系数ω来平衡两种信息的影响程度.

梯度下降法在机器学习中广泛使用,通过文献[12-14]以及函数始终沿着梯度方向变化最快的原理,不难得出运用梯度下降法的合理性.对于局部搜索策略的第2部分进行简要的证明:

(10)

命题1.给定一元非常数连续函数f(x),定义域为D,x0是f(x)一个极小值点,则必存在一个x0邻域U(x0)使得函数有唯一极小值且x∈U(x0)时f(x)的函数值随着|x-x0|的增大而增大,即:

对于极小值点y0=f(x0),∃U(x0,δ0)∈D,对于∀x1,x2∈U(x0,δ0),满足x1≠x2≠x0且(x1-x)(x2-x)>0当|x1-x0|>|x2-x0|时,有f(x1)≥f(x2).

证明:(反证法)设任意x0的邻域U(x0,δ),有不同于极值y0=f(x0)的极值y1=f(x1),存在ε>0有|x0-x1|<δ使得|y0-y1|>ε,根据δ的任意性知,与f(x)连续性矛盾.所以存在x0的邻域U(x0,δ0)使得存在唯一的极小值.

又根据极小值定义,易知在邻域U(x0,δ0)上使得f(x)的函数值随着|x-x0|的增大而非严格增大.

命题2.f(x0)为f(x)极小值,U(x0,δ)为x0的一个邻域且满足命题1,设xn,xbest∈U(x0,δ),存在一数列{an}an=xn,an+1=xn+1,其中xn+1由公式(10)得出,则数列{an}为收敛数列并且收敛于x0.

证明:eαlcos(2πl)levy的定义区间为[-c,c],c足够大.xn,xbest∈U(x0,δ)有两种情况:1)(xn-x0)(xbest-x0)>0;2)(xn-x0)(xbest-x0)<0.

第1种情况为xn,xbest均在x0的左侧(右侧),根据命题1有|xn-x0|>|xbest-x0|,令xn+1=xn+k(xbest-xn),其中k=eαlcos(2πl)·levy,则当0f(xn+1)>f(x0),又因为(0,x0-xn/xbest-xn)∈[-c,c].所以公式(10)能够产生一单调递减数列有界数列{f(xn)}收敛于f(x0),又由f(x)连续性得xn收敛于x0.

第2种情况,不妨设xnf(xn+1)≥f(x0),因为(0,1)∈[-c,c],所以有{f(xn)}收敛与f(x0),又由f(x)连续性得xn收敛于x0,xn>x0,同理可证.

命题3.对于极小值点x0=(x1,x2,…xn),y0=f(x0),∃邻域U(x0,δ0)∈D,使得∀xa=(x1,x2,…,xi+c1,…,xn),xb=(x1,x2,…,xi+c2,…,xn)∈U(x0,δ0),i=1,2…,n,满足xa≠xb≠x0,且(xa-x)·(xb-x)>0,|xa-x0|>|xb-x0|时,有f(xa)≥f(xb).存在这样一个邻域使得,任意其中一个分量在固定其他分量情况下满足命题1.

命题4.存在满足命题3的一个邻域,能够通过公式(10)产生一列收敛于x0的数列.

2.4 基于梯度信息的精英扰动策略

由局部搜索公式(9)看出,种群最优个体只能以梯度信息进行更新.为了使最优个体能够充分利用自身信息引入柯西扰动策略[15],这是一种以利用自身信息进行探索的策略,更新公式如下:

X=Xbest+cauchy(0,1)Xbest

(11)

一维标准柯西概率函数定义如下:

(12)

柯西分布函数在越靠近原点处函数值越大,越远离原点处函数值值越小.使用柯西分布产生的随机数cauchy(0,1)∈(-∞,∞)理论上X能够使得可能值为问题空间中的任意一点.但是在计算机上通过有限次数模拟获取到的随机数|rand|>C(C为一个较大常数)的情况极少,所以这种情况下的探索策略能够探索的空间十分有限.所以探索空间的范围主要根据‖Xbest‖的大小而定,当‖Xbest‖取较小值时,其本身引起的的探索范围能够达到较好的水平;当‖Xbest‖较大时,需要采取自适应步长来控制其探索空间.数学模型描述如下:

(13)

又由于柯西分布概率密度函数以轴x=0对称,模拟得出的随机数很可能导致X更新朝着真实解的反方向更新,为了充分利用柯西扰动策略,使用梯度方向作为种群更新方向.修改后的数学模型描述如下:

(14)

其中:

2.5 特征选择策略

在多特征问题中,每个特征对问题的影响可能大不相同,随着问题维数的增加,对于算法而言所需要探索的解空间也急剧增加,而且所有特征同时更新会存在很大的随机性和不可控性.例如,假设X=(x1,x2,…,xn)为特征向量,并且特征分量相互独立,则存在以下问题:设每一个特征分量分别有(n1,n2,…,nn)个极值邻域,最坏情况下通过整体更新需要获取到n1n2,…,nn个空间信息最终找到最优解,而依次找到单个特征的最优解邻域,最坏情况下只需要探索n1+n2,…,+nn个空间信息,极大的减少需要探索的空间,以此提高算法的性能.

控制变量法将多特征复杂问题划分为若干个单特征问题,若只改变其中某一个因素,就研究这个因素对整体的影响,最后自底向上地将多个单特征问题的解融合在一起得到整个问题的解.

序列最小优化算法(Sequential Minimal Optimization,SMO)[16]是一种用于解决支持向量机的优化算法.SMO算法基本思路是每次先任意选取两个变量ai和aj,然后固定ai和aj之外的所有参数,随后求f(x)在ai和aj上的极值,一次反复直至收敛.由此受到启发,本文首次提出特征选择策略,基本思想为:将个体特征分为K个部分,采用本策略时每次会固定第ki部分之外特征,对第ki部分特征进行搜索.特征选择策略算法(FSA)流程如算法 1,其中被选中特征下标向量(Dimselected)定义为被选中的特征位为1,其它特征位为0,I为被选中的特征集合.

根据评估最优值变化情况来判断是否需要使用特征选择策略.当长时间出现最优值变化过小时,则采用特征选择策略;当特征选择算法结束后,评估当前最优解向量的对称性,对称性高时不再采用特征选择策略.

算法1.特征选择算法

输入:未被选择过的特征集合S,需要选择特征的个数k

输出:被选中特征下标(Dimselected).

Dimselected=zeros(dim)

N=min(k,size(S))

WhileN>0 do:

IfS==Ø:

Dimselected=ones(dim)

Else:

I=pop(S)

Indices=argIndices(I)

Dimselected(Indices)=1

2.6 MFPA算法流程

本文在花朵授粉算法(FPA)基础上,为了提升FPA算法的性能,从多个角度对算法进行改进和修正,首次提出混合自适应控制策略[10]、全局搜索策略[17]、局部搜索策略[18]、基于梯度信息的精英扰动策略[19,20]、特征选择策略的多策略混合的花朵授粉算法(MPFA),其算法流程如算法2,其中N、dim、itermax、population分别为种群数量、个体特征维度、最大迭代次数、种群.

算法2.多策略花朵授粉算法

输入:N,dim,itermax.

输出:最优值(Xbest)

initialize:population

Repeatitermax:

If use FSA is ture:

Dimselected=FSA()

For 1 toN:

IfR>p(t) then:

UpdateXiby eq(7)

Else

UpdateXiby eq(9):

UpdateXbestby eq(14):

3 实验设计

3.1 实验条件设置

为了验证本文所提出的MFPA算法的优化性能,将MFPA算法与原始花朵授粉算法(FPA)、融合正余弦和柯西变异算的麻雀搜索算法(Sparrow Search Algorithm Combining Sine-Cosine and Cauchy Mutation,SCSSA)[21]、 基于布朗运动与梯度信息的交替优化算法(Alternately Optimizing Algorithm Based on Brownian Movement and Gradient Information,AOABG)[22]与基于混合策略改进的花朵授粉算法(HSFPA)进行对比分析.仿真实验的算法种群数量设置为50,最大迭代数为500,其中FPA算法转换概率设为0.8,λ=1.5,其他算法的参数由对应的文献进行相应设置.采用9个常用测试函数验证算法效果.测试函数的基本信息如表 1所示,其中n=50.

实验硬件环境为:Inter i7 CPU 2.50GHz、RAM 8.0G、Windows10 操作系统,Matlab R2016a.

各算法均在所有测试函数上独立运行15次,最后取每次测试中的最优值并计算方差.公式(11)中ω=0.5,公式(13)中α1=10,β=mod(‖Xbest-0‖,10)其中mod为求余算法.

3.2 全局搜索性能对比

全局搜索的主要目的是让种群个体找到精确解所在邻域.为了验证本文提出的MFPA算法具有高效的全局搜索性能,利用表 1给出的测试函数Michalewiz,Schwefel,Gramacy分别对MFPA、HSPFS、FPA、SCSSA、AOABG算法进行全局搜索性能比较分析,验证MFPA算法在保持种群多样性及搜索最优解邻域方面的效果.

表1 测试函数Table 1 Test functions

Gramacy函数是多峰对称函数,具有定义域小、真实解邻域小、次要解相差小等特点.Schwefel函数为多峰对称函数,具有定义域大、真实解邻域范围大、次要解相差大等特点.Michalewiz函数为多峰非对称函数,定义域小、真实解邻域小、次要解相差小,能够基本满足一般问题的条件.

SCSSA与AOABG算法采取了分量更新步长倍数不相等的模式,即:Incremental=(k1s1,k2s2,…,knsn),而其余算法采用了分量更新步长倍数相等的模式,Incremental=(ks1,…,ksn),Incremental为解向量更新增量.由测试函数Sphere各算法全局搜索个体分布图 1可以看出:倍数不相同模式下,种群分量几乎充满了整个取值范围,其中AOABG算法混乱程度最高,而SCSSA在算法后期种群会向局部最优解堆积,无法良好的保持种群多样性.而选择倍数相等模式下,测试函数为对称函数时,分量会逐步对称缩小搜索围.

图1 全局搜索分布Fig.1 Global search distribution

由表 2可以看出,各个算法在问题维度较小时都能有效并快速的到达最优解邻域.但是当维度较高时,SCSSA、AOABG、FPA算法几乎不能找到解的邻域,而MFPA、HSFPA算法却能找到最优解邻域.HSFPA算法能够进入到最优解邻域的个体偏多,侧面反映出该算法保持种群多样性的能力不足.但在使用非对称测试函数Michalewiz对5个算法进行测试时都不能找到最优解的邻域.在利用Michalewiz测试时,通过给全局搜索策略添加特征特征选择策略后可以降低全局搜索所需要搜索的维度,各算法均能找到最优解的邻域,从而体现出特征选择策略的有效性.

3.3 搜索精度分析

为了验证本文给出的算法MFPA在精度方面的效果,利用表 1中所给的前8个测试函数,将其与HSPFS,FPA,SCSSA,AOABG进行对比,计算不同算法在各测试函数得出的最优值与标准差,测试结果如表3所示.虽然MFPA与HSFPA算法均为改进的FPA算法,但相对于HSFPA算法而言,MFPA算法在Sphere、Stybinski、Tablet上精度都有一定程度的提高,在Tablet函数上方差小,而在Michalewiz上的探索和寻优能力有大幅度提升.AOABG在所有函数上表现得中规中矩.由此可见,本文提出的MFPA算法无论在探索能力与寻优能力都要有一定程度的提升,并且保持着良好的鲁棒性.

表2 全局搜索能力Table 2 Global search capability

表3 算法收敛精度Table 3 Convergence accuracy of algorithms

表4 算法复杂度对比表Table 4 Table of algorithm complexity comparison

3.4 收敛速度分析

为了直观地展示出各算法在收敛速度方面的不同表现,分别绘制出不同算法的收敛曲线,如图 2所示.测试函数的值域较大时则采用对数显示,有些函数值域与定义域均太大则缩小绘图范围.

在BentCigar函数上,算法迭代初期所有算法收敛速度都较慢,MFPA经过一个转折点后就开始快速的下降.在Michalewiz函数中,MFPA算法即使陷入局部最优也能在一定代数后跳出局部最优,下降速率也是最高的.对Sphere、Stybinski函数而言,MFPA收敛速度明显优于其他算法.在Tablet函数中,MFPA算法的收敛速度要稍慢于SCSSA算法,但是最终达到一致的精度.在Schwefel函数中,在算法初期MFPA收敛速度要比HSFPA算法慢,但是到了算法迭代中期则实现了反超.

在Booth&Lee函数中,FPA算法收敛速度要明显高于其他算法,而其他算法无明显差异.在McCormick函数中,MFPA下降速度明显快于其他函数.通过实验结果对比,在低维测试函数上,初始种群的分布对于算法的收敛性能够较大影响.MFPA有着良好的收敛速度,尽管在算法迭代前期在一些情况下收敛速度不足,但在算法迭代中期出现了收敛速度强劲的现象,这也反映出MFPA有着较为优秀的跳出停滞现象的能力.

3.5 算法复杂度分析

在算法执行过程中,时间主要消耗在计算目标函数值和梯度上.假设目标函数计算与梯度计算时间分别设为TF,TG,而其他步骤均为O(1).种群个体向量更新的复杂度为O(1),种群进行全局搜不需要进行梯度计算,则单个个体全局搜索时间复杂度为:O(TF+1).

局部搜索种群个体需要进行梯度计算,因此单个个体局部搜索的时间复杂度为:O(TF+TG+1).全局搜索与局部搜索个体比值为:1-p:p.种群最优个体只进行最优个体扰动策略,其需要计算梯度与目标函数值,算法单次迭代时间复杂度为:O((N-1)×(1-p)(TF+1)+(N+1)p(TF+TG+1)+1(TF+TG+1))=O((N-1)(TF+1)+((N-1)p+1)(TG)).

图2 算法收敛速度Fig.2 Convergence rate of algorithms

所以算法总的时间复杂度为O(Maxiter(N(TF+1)+(N-1)(1-p)(TG))),其中Maxiter为算法最大迭代次数,N为种群数量.其他算法时间复杂度如表 4.

由表 4可知,与其他算法相比,MFPA算法仅多出了求梯度的复杂度,但其总复杂度随种群数量以及迭代次数呈线性增长.

4 总 结

本文提出了一种多策略混合的花朵授粉算法(MFPA),针对于FPA算法跳出局部最优解能力不足提供了新思路.利用水往低处流的思想,为花粉添加了梯度信息,让花粉朝着更好的方向传播.根据自身与最优个体的信息判断下一步该如何更新,让花粉表现出一种“智能”性.通过开展大量仿真实验进行算法性能分析对比,验证了MFPA算法的有效性以及优越性.后续的研究工作将考虑把MFPA算法应用到一些机器学习实际问题中,实现算法的应用示范.