维适应人工蜂群算法的研究

赵 明,焦剑如,宋晓宇,高怡臣

1(沈阳建筑大学 计算机科学与工程学院,沈阳 110168)

2(沈阳燃气有限公司 技术信息部,沈阳 110005)

0 引 言

群体智能优化算法,通过智能体之间简单的相互作用所产生的智能全局行为使得群体具有求解复杂问题的能力[1],由于其在各种优化问题中比确定性算法性能好、速度快,从而在许多应用学科中非常流行,学者研究出了各种群体智能优化算法[2].其中,人工蜂群(Artificial Bee Colony,ABC)算法是一种建立在蜜蜂自组织型和群体智能基础上的优化算法,是Karaboga受蜜蜂智能采蜜行为的启发于2005年提出的[3],由于其参数简单、易于求解和性能优异等特点[4],在解决诸多实际优化问题中被成功应用,如生产调度、图像分割、路径规划、组合优化、参数选择和连续优化等领域[5-10].

与其他优化算法一样,基本ABC算法也有不足之处,由于其擅长探索而不擅长开发,因此往往收敛速度较慢[11].相关学者从改进维数方面对基本ABC算法进行了研究,例如:Chu等人提出每次对解的所有维进行改进,通过对邻域的全方位探索提高了搜索效率[12];Gao等人发现改进维数直接影响着不同问题的优化效果,并引入参数对不同优化问题的改进维数进行控制,但需要事先基于实验进行测定然后才能进行设置[13];Li等人受差分进化算法的启发,在跟随蜂阶段基于食物源搜索失败的次数设置改进维数,次数越多维数越少,以此增强局部开发能力,对改进维的选择采用随机方式进行,没有采用当前种群进化信息进行指导[14].

以上研究及其成果表明,对不同的问题进行优化时,适用的改进维数会存在差异,而且对改进维的选择也直接影响着算法的性能.因此,为了使ABC算法能够根据不同优化问题以及不同优化阶段,适应地确定需要改进的维数,基于以上启发,本文首先提出一种基于改进维数成功历史档案的适应机制,不再单一的选择几维或者全维进行搜索,而是基于构建的改进维数成功历史档案动态设置,使得算法能够随着具体问题的优化过程适应到适合的改进维数,从而提高解的改进成功率;在此基础上,以一定比例引入到当前最优解的欧式距离信息智能指导跟随蜂对要改进维的选择,使得算法能够根据不同优化问题的不同搜索过程自动适应到有潜能的维进行搜索,从而提升算法性能以加快收敛速度.最后,采用CEC2014基准测试函数集对提出算法的有效性和优越性进行验证分析.

1 基本ABC算法

基本ABC算法是由食物源、雇佣蜂和非雇佣蜂(包括跟随蜂和侦查蜂)3部分组成.一只雇佣蜂对应一个食物源,即二者数量相等,且为种群规模NP的一半,种群的另一半为跟随蜂.雇佣蜂的任务是发现食物源信息并与跟随蜂分享,跟随蜂获取信息后采用轮盘赌选择食物源并对其进行开发.如果某食物源在限定次数后仍未被更新,相应的雇佣蜂变成侦查蜂在蜂巢附近搜索新的食物源代替原来的食物源.整个蜂群的目标就是找到花蜜量最大的食物源.

在初始化阶段,ABC算法使用公式(1)随机对食物源进行初始化.初始化食物源就相当于初始化问题的一个解.食物源数量(也是雇佣蜂数量和跟随蜂数量)用SN表示(SN=NP/2),种群的第i个食物源用Xi表示.Triali代表尝试被搜索改进的次数,limit代表预先设置的食物源尝试被改进的最大次数.

(1)

然后,基于最小优化问题采用公式(2)计算食物源的适应度值.Xi的适应度值用fiti表示,f(Xi)代表优化问题中食物源Xi的目标函数值(根据具体优化问题的优化目标进行计算).

(2)

在雇佣蜂搜索阶段,每个食物源的雇佣蜂均采用公式(3)在其附近进行搜索.

(3)

其中,Vi表示搜索到的新食物源,G表示代数,j表示随机选取的改进维度,Xk表示从种群中随机选取且与Xi不同的食物源,φij是范围为[-1,1]随机实数.

雇佣蜂搜索结束后对原食物源和新食物源进行比较,从中选择更优质的保留并与跟随蜂分享.此时,若食物源Xi更新成功,则Triali值设置为0,否则增1.

在跟随蜂搜索阶段,每个跟随蜂利用轮盘赌选择一个食物源,食物源被选择的概率根据公式(4)计算出来:

(4)

其中,Pi为Xi被选择的概率,与该食物源的适应度值成正相关,食物源越好被选择的概率越大.

跟随蜂选择食物源后,采用公式(3)对其进行改进搜索,并于搜索后在原食物源和新食物源之间进行贪婪选择,同时设置相应食物源的Triali值.

最后是侦查蜂搜索阶段,将食物源中最大的Triali值与limit进行比较,如果达到则表明此食物源在设定的搜索次数内没有变得更好,那么这个食物源会被放弃,其雇佣蜂变成侦查蜂并根据公式(1)随机生成一个新的食物源.

基本ABC算法的终止条件有两个:找到可接受解或达到最大函数评价次(maxFEs).

2 维适应的人工蜂群算法

2.1 搜索方程设计

雇佣蜂阶段采用的搜索方程如公式(5)所示:

(5)

其中,Xr1、Xr2、Xr3从种群中随机选取的3个不同食物源,且均与Xi不同,φij是范围为[-1,1]随机实数.

从公式(5)可以看出,雇佣蜂是围绕随机选择的且与当前食物源不同的食物源进行改进搜索,并基于另外两个随机选择的不同食物源与其的差向量进行引导.由于式中采用了3个不同的食物源组合进行搜索,可以充分利用当前种群的多样性信息,使其具有更好的搜索能力.

跟随蜂阶段采用的搜索方程如公式(6)所示:

(6)

其中,Xk是通过轮盘赌选取的食物源,所以选中好解的概率大,Xr1、Xr2是随机选取的两个不同食物源,且均Xk与不同,φij是范围为[-1,1]随机实数.

从公式(6)可以看出,跟随蜂围绕着轮盘赌选取的食物源进行搜索,利用两个随机选择且不同的食物源的差向量进行扰动.算法迭代搜索初期,Xr1和Xr2的差异较大,此时搜索步长(搜索步长由第2项的差值决定)也较大,侧重于探索;到了算法迭代搜索后期,两者之间的差异很小,此时搜索步长也很小,侧重于开发.因此,跟随蜂可以利用搜索步长的动态变换实现求解过程逐步由探索转为开发.

2.2 改进维数的适应机制

相关研究发现,不同的优化问题适用的改进维数有所不同,而且,随着算法搜索过程的进行,其搜索重点应由探索转向开发,因而不同的搜索阶段适用的改进维数也会发生变化.因此,引入了基于成功历史档案的维数适应机制,通过建立改进维数的成功历史档案,记录当前优化过程中成功对食物源进行改进的维数信息,在此基础上利用高斯分布设置下一代人工蜂搜索时改进的维数,保证改进维数对不同问题的适应性,同时保持适度随机性.

成功历史档案的应用过程如下:在算法初始化阶段,创建维数成功历史档案succ_arch,其规模为H,用于存储人工蜂每代更新食物源时使用的维数比例DNR的加权均值,档案中每个项目的初值均设置为0.5.每代人工蜂搜索时,累计本代成功更新食物源的次数success,并采用success_DNR记录本代每次成功更新食物源时的所有维数比例.当下一代人工蜂对食物源进行改进时,随机在成功历史档案里选择一个值,并基于该值利用高斯分布生成本次更新使用的维数比例DNRi,此外,若本次成功更新,将DNRi保存到本代的success_DNR中,并将本次食物源改进的程度记录到sigma_fi中.每代人工蜂搜索结束后,采用公式(7)计算本代成功改进时的维数比例加权均值DNRG,并用其替代成功历史档案中index位置的值,初始时index=0,以后index=(index+1)modH,从而实现档案项目的实时依次更新.

(7)

从公式(7)可以看出,使用食物源改进程度作为权值进行均值计算,能够突出改进程度大的食物源更新时使用的维数信息,因而可以达到更好的指导作用.

同时,在利用成功改进维数历史信息的基础上,确保具有一定随机性和适应性,人工蜂在确定改进维数时首先从成功历史档案的H个值中随机选取一个记作muDNR,然后利用如公式(8)所示的高斯分布产生本次搜索的维数比例值DNRi.

DNRi=gaussrand(muDNR,0.2)

(8)

公式(8)中,高斯分布参数设置为0.2,目的是使得产生的值较为集中的分布在muDNR附近,以充分利用成功信息保证改进解的成功率.

2.3 维选择的适度指导机制

在确定改进维数比例的基础上,雇佣蜂阶段对于改进维的选择全部随机进行,来保证算法的探索能力.同时,为了提高开发能力以便加快收敛速度,跟随蜂阶段将改进的维分为两个相等的部分,一半随机进行维的选择,另一半则按所选个体与当前最优解的欧式距离进行选择,即利用当前最优解的信息对维选择进行指导.

跟随蜂选中的食物源Xk在j维距离当前最优解Xbest的欧式距离如公式(9)所示:

Edj(Xk)=|Xkj-Xbest j|

(9)

跟随蜂根据基于成功历史档案和高斯分布生成的本次改进维数比例DNRi确定改进的维数为DNRi×D,然后根据公式(9)计算其选中食物源Xk每一维与当前最优解Xbest的距离,并依据计算结果从大到小的原则选择一半数量的维,另一半从剩下的维中随机选取.

2.4 算法流程和步骤

步骤1.初始化算法参数,包括NP、D、limit、maxFEs和H,采用公式(1)初始化种群X,初始化成功历史存储succ_arch.

步骤2.采用公式(2)计算初始种群中食物源的适应度值.

步骤3.雇佣蜂搜索阶段.每个雇佣蜂根据成功历史档案和公式(8)高斯分布确定改进的维数,并随机选择改进的维,采用公式(5)搜索新食物源,计算新食物源的适应度值,依据贪婪选择策略保留食物源,并设置相应的Trial值.若食物源更新成功,记录改进维数比例以及解改进程度信息.

步骤4.跟随蜂搜索阶段.采用公式(4)计算每个食物源的选择概率,每个跟随蜂采用轮盘赌选择要改进的食物源,根据成功历史档案和公式(8)高斯分布确定改进的维数,其中,一半数量的维根据公式(9)计算每一维到当前最优解的欧式距离从大到小确定,另一半随机选取.然后,跟随蜂采用公式(6)搜索新食物源,计算新食物源的适应度值,依据贪婪选择策略保留食物源,并设置相应的Trial值.若食物源更新成功,记录改进维数比例以及解改进程度信息.

步骤5.成功历史档案更新.采用公式(7)计算本代成功更新解时的加权平均维数比例并更新历史档案.

步骤6.侦查蜂搜索阶段.若某食物源经过限定次数后仍旧未被更新,则该食物源被放弃,该食物源的雇佣蜂变成侦查蜂,采用公式(1)随机初始化一个新的食物源代替该食物源.

步骤7.判断是否满足结束条件,若满足,算法结束;否则重复步骤2～步骤6.

步骤8.输出最优解.

维适应人工蜂群(Dimension-Adaption Artificial Bee Colony,DAABC)算法流程如图1所示.

图1 DAABC算法的流程图Fig.1 Flow chart of DAABC algorithm

2.5 时间复杂度分析

初始化阶段:对种群的初始化,DAABC与基本ABC相同,时间复杂度为O(NP×D);DAABC需要对成功历史档案进行初始化,时间复杂度为O(H),根据本文实验参数设置部分的讨论H设置为D,因此时间复杂度为O(D);对食物源的适应度值的计算,DAABC与基本ABC相同,时间复杂度为O(NP×D).

雇佣蜂搜索阶段:DAABC根据成功历史档案利用高斯分布确定改进的维数,最大改进的维数为D,因此时间复杂度为O(D);利用搜索方程对食物源进行改进搜索时,DAABC一般进行多维搜索,由于最大维数为D,因而时间复杂度为O(NP×D);DAABC需在食物源更新成功时记录改进相关信息,时间复杂度为O(NP).

跟随蜂搜索阶段:对食物源的选择概率进行计算,DAABC与基本ABC相同,时间复杂度为O(NP);DAABC根据成功历史档案确定改进的维数,最大改进维数为D,时间复杂度为O(D);DAABC跟据改进维数对维进行选取时,首先计算各维距离当前最优解的距离并排序,时间复杂度为O(D×log(D)),对要改进的维进行选取时,时间复杂度为O(D);利用搜索方程对食物源进行改进搜索时,DAABC一般进行多维搜索,由于最大维数为D,因而时间复杂度为O(NP×D);DAABC需在食物源更新成功时记录改进相关信息,时间复杂度为O(NP).

侦查蜂搜索阶段:DAABC与基本ABC相同,时间复杂度为O(NP).

通过以上分析可以看出,DAABC与基本ABC相比较,整个算法在各阶段额外增加的时间复杂度量级分别为O(D)、O(NP)、O(D×log(D))和O(NP×D),D通常小于NP,因而整个算法的时间复杂度最大量级仍为O(NP×D),与基本ABC相同.

3 实验结果与分析

3.1 测试函数集以及参数设置

本文采用的CEC2014测试函数集包含30个基准测试函数,搜索空间为[-100,100],其中f1～f3是单峰函数、f4～f16是简单的多峰函数、f17～f22是混合函数、f23～f30是复合函数.表1中列出了每个函数的序号、名称以及取值范围[15].

表1 测试函数集Table 1 Benchmark function set

本文选取了当前国内外ABC改进算法研究中性能先进的算法与提出算法进行对比,包括APABC[16]、DFSABC_elite[17]、ABCLGII[18]、ECABC[19]和ARABC[20].参数设置如表2所示.需要特别说明的是,对比算法的参数设置均为其提出文献的设置,算法公共参数maxFEs均设置为10000×D.

表2 所有ABC算法的参数表Table 2 Parameter table of all ABC algorithms

3.2 实验结果及对比分析

3.2.1 均值与标准差

D=30时,每个算法分别独立运行30次,统计求解获得的最优值的均值和标准差,其结果如表3所示.表3中对每个函数在所有算法中最好的结果进行加粗突出显示.

表3 30维均值和方差实验结果列表Table 3 Experimental results of mean and standard deviation with D=30

从表3中可以看出,与其它5个改进的ABC算法相比,DAABC在30个基准函数测试结果中有15个表现最好,APABC、DFSABC_elite、ABCLGII、ECABC和ARABC分别有3个、6个、5个、4个和1个,从数量上DABC显著高于其他对比算法.另外,对于f1、f4、f5、f9、f10、f11、f12、f13、f14、f16、f24、f25、f27、f28,DAABC虽然略低于其它5个算法中最优均值,但是求解结果具有相同的数量级,说明算法的性能相差不大,只有f2效果稍差.综合来看,DAABC在求解精度和鲁棒性上明显优于其它改进算法.

为了进一步验证DAABC的优越性,对表3中算法求解优化函数的均值数据采用SPSS进行非参数检验,包括Wilcoxon检验和Friedman检验,检验结果如表3后两行所示.利用Wilcoxon检验把5个对比算法与DAABC两两进行非参数检验,检验结果p值均小于0.05,说明它们与DAABC存在显著性差异,即DAABC显著优于这5个算法.利用Friedman对6个算法进行非参数检验,秩排名ARABC>APABC>ECABC>ABCLGII>DFSABC_elite>DAABC,说明DAABC表现最好,并且p值远远小于0.05,说明DAABC与5个对比算法存在显著差异,即DAABC显著优于其它改进算法.

3.2.2 收敛能力

为了进一步检验算法的收敛能力,从DAABC算法并非表现最优的函数中选取12个绘制收敛图,如图2所示,其中横轴表示函数评价次数,纵轴表示最优解以10为底的对数值.

图2 30维时部分函数的收敛图Fig.2 Convergence diagrams of partial functions with D=30

从图2可以看出,即使与其他5个算法相比,DAABC算法在这些函数上并非表现最好,但收敛速度更快或相似,尤其可以看出,在算法搜索最初,DAABC由于没有适应到适合的维数及维,收敛不是最快,但随着搜索的继续,其一直保持着向最优解收敛的能力,不易陷入局部最优.

3.3 参数讨论

本文提出算法在设立成功历史档案时新引入了参数H,因而,为了分析H对性能的影响,为DAABC设置不同大小的H值并分别独立运行30次,均值和标准差的结果如表4所示.

表4 不同大小H的实验结果Table 4 Experimental results of H with different sizes

从表4可以看出,对于7种H参数从D/2～3D范围内的设置,在30个优化函数中除了f6、f8、f10、f11和f29这5个函数外的25个函数上,均值都在相同数量级,说明差异不大.在f6上,只有H=D/2和25表现比其他设置差;在f8、f10和f11上,只有H=3D比其他设置差;在f29上,H=D和H=3D/2比其他设置好.由此可以看出,虽然H=3D在12个函数上获得了最好均值,但与其他设置在相同数量级差距不大,于此同时,其在3个函数上表现明显低于其他设置,说明当H较大时会由于成功历史档案更新不及时而导致性能的不稳定.此外,H较小为D/2或25时,有1个函数因为成功历史档案更新过快表现较差.而在H在D～5D/2范围內时,差距不大,因此综合考虑节省程序使用辅助空间因素,建议H的设置为D.

4 结 论

为了解决基本ABC算法后期精度不高、收敛速度慢的问题,本文提出了一种维适应的人工蜂群算法,通过建立维数成功历史档案使得算法能够随着收敛过程自动适应到合适的改进维数,提高了解改进的成功率,同时在改进维选择中适度采用当前最优解进行指导,使得算法能够自动适应到更有潜能的维进行搜索,增强了收敛能力.在CEC2014基准测试集的实验结果以及相应的Wilcoxon和Friedman统计检验表明,本文提出的算法与当前5个先进的改进ABC算法相比,具有显著优越的求解精度、鲁棒性和收敛能力.下一步研究主要考虑将本文提出的算法应用到实际工程问题中,进一步验证其在处理实际问题的优越性.