基于適應(yīng)度分組的多策略人工蜂群算法

周新宇 胡建成 吳艷林 鐘茂生 王明文

在科學(xué)研究和工程應(yīng)用中，很多實(shí)際問題可轉(zhuǎn)化為優(yōu)化問題進(jìn)行求解，但其中大部分問題都是高度復(fù)雜的，通常有非凸、多峰、強(qiáng)約束等特點(diǎn)，致使一些經(jīng)典的最優(yōu)化方法往往難以求解[1-2].近年來，一些基于進(jìn)化優(yōu)化的方法表現(xiàn)出良好的求解性能，它們對(duì)優(yōu)化問題的數(shù)學(xué)性質(zhì)要求不高，甚至可作為一類黑盒優(yōu)化工具直接使用.在這類方法中，進(jìn)化算法是核心，它通過模擬自然界中的生物進(jìn)化行為實(shí)現(xiàn)尋優(yōu).作為一類算法，進(jìn)化算法包含多種不同的算法范例，常見的有：遺傳算法(Genetic Algorithm, GA)[3]、粒子群優(yōu)化算法(Particle Swarm Optimiza-tion, PSO)[4]、差分進(jìn)化算法(Differential Evolution, DE)[5]、人工蜂群算法(Artificial Bee Colony, ABC)[6]等.

ABC模擬自然界中蜂群的智能采蜜行為，通過不同種類蜜蜂的分工協(xié)作尋找含量最多的蜜源地，即找到優(yōu)化問題的最優(yōu)解.相比GA、PSO、DE，ABC的性能相當(dāng)，具有競爭力[7]，并且結(jié)構(gòu)簡單、控制參數(shù)較少.近年來，ABC受到相關(guān)領(lǐng)域中眾多研究人員的密切關(guān)注，相繼提出很多關(guān)于ABC的算法改進(jìn)和應(yīng)用方面的研究工作.目前，ABC已成功應(yīng)用于求解多種不同的實(shí)際優(yōu)化問題，包括：流水車間調(diào)度問題[8]、服務(wù)計(jì)算優(yōu)化問題[9]、投資組合優(yōu)化問題[10]、人群疏散路徑規(guī)劃問題[11]、特征選擇問題[12]、圖像分割問題[13]、網(wǎng)絡(luò)負(fù)載均衡問題[14]等.

然而，ABC在求解復(fù)雜優(yōu)化問題時(shí)，性能受到嚴(yán)重挑戰(zhàn)，主要表現(xiàn)為求解精度不高、收斂速度較慢.為此，研究人員提出很多相關(guān)改進(jìn)策略，并指出導(dǎo)致ABC性能受限的一個(gè)主要原因是其解搜索方程的勘探能力過強(qiáng)，而開采能力不足.這些相關(guān)改進(jìn)策略可大致分為兩類：1)如何利用種群中的最優(yōu)個(gè)體或精英個(gè)體設(shè)計(jì)新的解搜索方程.Zhu等[15]提出GABC(Gbest-Guided ABC, GABC)，在解搜索方程中把種群的最優(yōu)個(gè)體Gbest添加為引導(dǎo)項(xiàng).周新宇等[16]提出鄰域搜索的ABC，在環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)中選擇最優(yōu)個(gè)體進(jìn)行開采，利用鄰域信息引導(dǎo)算法搜索.Cui等[17]設(shè)計(jì)基于精英個(gè)體引導(dǎo)的解搜索方程，把具有較好適應(yīng)度的若干個(gè)體視為精英個(gè)體，再從中任選一個(gè)精英個(gè)體作為解搜索方程的目標(biāo)個(gè)體.2)如何利用不同的解搜索方程設(shè)計(jì)多策略機(jī)制.Wang等[18]提出多策略集成的改進(jìn)ABC，采用3種不同的解搜索方程,用于構(gòu)建策略候選池，在初始化階段為個(gè)體隨機(jī)分配一種解搜索方程，再根據(jù)子代個(gè)體質(zhì)量動(dòng)態(tài)選擇不同的解搜索方程.Xiang等[19]提出ABCG，在雇傭蜂階段引入引力模型，選擇引力最大的鄰域個(gè)體生成后代個(gè)體，而在觀察蜂階段采用隨機(jī)引導(dǎo)方式、反向?qū)W習(xí)、重新初始化三種策略.Chen等[20]將3種解搜索方程集成到ABC中，提出自適應(yīng)多策略機(jī)制，每個(gè)個(gè)體可自適應(yīng)地選擇其中的一種策略.

上述兩類策略可有效提高ABC性能，并為設(shè)計(jì)新的策略提供有益借鑒,但這些工作還存在一定的局限性：1)雖然利用精英個(gè)體引導(dǎo)搜索可加快算法的收斂速度，但未考慮種群中占多數(shù)的非精英個(gè)體，在一定程度上容易導(dǎo)致種群陷入局部最優(yōu)；2)大部分的多策略機(jī)制是以算法的歷史經(jīng)驗(yàn)選擇策略，即把以往迭代的策略成功率作為后續(xù)策略選擇的概率，但當(dāng)問題的適應(yīng)度地形非常崎嶇時(shí)，這種歷史經(jīng)驗(yàn)往往不準(zhǔn)確.因此，本文提出基于適應(yīng)度分組的多策略ABC算法(Multi-strategy ABC Based on Fitness Grouping, MABC-FG).一方面，在利用精英個(gè)體引導(dǎo)搜索的同時(shí)，考慮種群中占多數(shù)的非精英個(gè)體，設(shè)計(jì)4種精英個(gè)體與非精英個(gè)體結(jié)合的解搜索方程；另一方面，從個(gè)體層次出發(fā)選擇策略，根據(jù)適應(yīng)度對(duì)種群進(jìn)行分組，為不同分組的個(gè)體分配具備不同搜索能力的解搜索方程，使不同個(gè)體產(chǎn)生不同的搜索行為，平衡算法的勘探能力和開采能力，達(dá)到有效提高ABC性能的目的.為了驗(yàn)證本文算法性能，在CEC2013 (2013 IEEE Congress on Evolutionary Computation)、CEC2015 (2015 IEEE Congress on Evolu- tionary Computation)測(cè)試集及調(diào)頻聲波合成問題上進(jìn)行實(shí)驗(yàn)，結(jié)果表明本文算法性能較優(yōu).

1 經(jīng)典人工蜂群算法

經(jīng)典ABC[21]是根據(jù)蜜蜂尋找蜜源的搜索過程提出的一種進(jìn)化算法.在算法中有3種蜜蜂：雇傭蜂、觀察蜂、偵察蜂，這3種蜜蜂相互分工和合作，尋找更好的蜜源.首先，雇傭蜂負(fù)責(zé)在蜜源周圍搜索新的蜜源，并且完成搜索后將蜜源位置、蜜量等信息分享給觀察蜂.然后，觀察蜂根據(jù)雇傭蜂分享的信息按照一定的概率選擇某一個(gè)蜜源繼續(xù)進(jìn)行開采，如果該蜜源的蜜量越多，被選擇的概率越高.最后，如果某一蜜源連續(xù)limit次仍未更新，該蜜源就會(huì)被拋棄，偵察蜂負(fù)責(zé)重新隨機(jī)搜索一個(gè)新的蜜源代替被拋棄的蜜源.值得注意的是，雇傭蜂的數(shù)目、觀察蜂的數(shù)目和蜜源的數(shù)目是相同的，偵察蜂只有一只，蜜源對(duì)應(yīng)優(yōu)化問題的候選解，蜜源的蜜量對(duì)應(yīng)優(yōu)化問題的適應(yīng)度值.

經(jīng)典ABC采用隨機(jī)初始化種群開始迭代搜索，設(shè)蜜源的規(guī)模為SN，其中，蜜源

Xi=(xi,1,xi,2,…,xi,D)

表示一個(gè)候選解，第i個(gè)蜜源的第j個(gè)維度

(1)

1)雇傭蜂階段.在該階段，每只雇傭蜂在對(duì)應(yīng)的蜜源Xi處，根據(jù)

vi,j=xi,j+φi,j(xi,j-xr,j)

產(chǎn)生一個(gè)新的蜜源Vi=(vi,1,vi,2,…,vi,D)，其中，Xr表示種群中隨機(jī)選擇的一個(gè)蜜源，r=1,2,…,SN，滿足i≠r,φi,j表示[-1,1]內(nèi)均勻分布的隨機(jī)數(shù).依據(jù)貪婪選擇機(jī)制，當(dāng)候選蜜源Vi的蜜量更多，即適應(yīng)度值更優(yōu)，替換蜜源Xi.

2)觀察蜂階段.所有雇傭蜂完成搜索后，觀察蜂根據(jù)收到的信息，選擇一個(gè)蜜源繼續(xù)進(jìn)行開采.第i個(gè)蜜源被選擇的概率為：

(2)

其中，fiti表示第i個(gè)蜜源的適應(yīng)度，

(3)

fi表示第i個(gè)解的目標(biāo)函數(shù)值.適應(yīng)度越高的蜜源被選擇的概率越大.

3)偵察蜂階段.在上面兩個(gè)階段完成之后，如果某一蜜源連續(xù)limit次開采仍未更新，說明該蜜源已被開采耗盡.在這種情況下，該蜜源將被舍棄，并根據(jù)式(1)產(chǎn)生一個(gè)新的蜜源替換它.

2 基于適應(yīng)度分組的多策略人工蜂群算法

2.1 適應(yīng)度分組機(jī)制

從多策略集成的ABC的相關(guān)研究中，本文發(fā)現(xiàn)這些算法通常對(duì)種群中的每個(gè)個(gè)體都一視同仁，但是從個(gè)體層次上看，個(gè)體之間存在優(yōu)劣差異，這種差異可根據(jù)適應(yīng)度值衡量，這種差異也可粗略地在適應(yīng)度地形的位置分布上得到體現(xiàn).一般而言，較好的個(gè)體可能離局部最優(yōu)解或全局最優(yōu)解更近，而較差的個(gè)體可能離局部最優(yōu)解或全局最優(yōu)解更遠(yuǎn).因此，較好的個(gè)體更適合進(jìn)行開采，而對(duì)于較差的個(gè)體應(yīng)更注重勘探.因此，本文從個(gè)體層次出發(fā)，在設(shè)計(jì)多策略機(jī)制時(shí)，根據(jù)適應(yīng)度將種群分成3個(gè)具有不同特性的組.具體地，本文按照個(gè)體的適應(yīng)度對(duì)種群排序，適應(yīng)度最好的個(gè)體排在第一位，適應(yīng)度最差的個(gè)體排在最后一位.將種群中前三分之一的個(gè)體劃分到A組，三分之一到三分之二的個(gè)體劃分到B組，最后三分之一的個(gè)體劃分到C組.此過程如圖1所示.

圖1 種群劃分示意圖

根據(jù)上述種群劃分過程可得出如下結(jié)論：1)A組中個(gè)體的適應(yīng)度值均優(yōu)于其它兩組中個(gè)體，此時(shí)A組中的個(gè)體很可能離局部最優(yōu)解或全局最優(yōu)解更近，因此A組應(yīng)注重開采；2)C組中個(gè)體的適應(yīng)度值均差于其它兩組中的個(gè)體，相對(duì)而言，C組的個(gè)體很可能離局部最優(yōu)解或全局最優(yōu)解更遠(yuǎn)，因此C組應(yīng)注重勘探；3)B組中個(gè)體的適應(yīng)度值比A組差，但比C組好，因此對(duì)于B組中的個(gè)體而言，應(yīng)注重開采與勘探的平衡.綜合來看，A組注重開采，B組注重開采與勘探的平衡，C組更注重勘探.通過這種劃分方式，不同分組中的個(gè)體可表現(xiàn)出不同的搜索行為，對(duì)于整個(gè)種群而言也能有效平衡勘探與開采.需要注意的是，考慮到觀察蜂是負(fù)責(zé)開采更好蜜源的這一特性，在觀察蜂階段不使用適應(yīng)度分組機(jī)制，而繼續(xù)只使用具有較強(qiáng)開采能力的解搜索方程.為了完成這一目標(biāo)，本文為觀察蜂階段專門設(shè)計(jì)一個(gè)解搜索方程.

為了更直觀地說明各組成員的位置分布特點(diǎn)，以二維的Shekel′s Foxholes函數(shù)為例具體說明.該函數(shù)有24個(gè)局部極值點(diǎn)和1個(gè)全局最優(yōu)點(diǎn)

f(-32,-32)=0.998，

搜索范圍為[-65.536,65.536]2，具體定義可參考文獻(xiàn)[22].此例中種群規(guī)模為30.

圖2分別表示算法第1、5、20代的種群分布圖,圖中△表示A組個(gè)體，▲表示整個(gè)種群的最優(yōu)個(gè)體，○表示B組個(gè)體，*表示C組個(gè)體.由圖可看出，在第1代，3組個(gè)體在搜索空間中隨機(jī)分布.第5代后，算法已找到全局最優(yōu)解，大多數(shù)A組個(gè)體和B組個(gè)體已靠近極值點(diǎn)，C組也聚集在極值點(diǎn)附近.在第20代，A組個(gè)體已全部聚集在全局最優(yōu)點(diǎn)，C組個(gè)體仍分散在各個(gè)極值點(diǎn)，使整個(gè)種群保持較好的勘探能力.

(a)第1代

通過該例可知，A組能快速找到最有潛力的搜索區(qū)域，B組跟隨A組進(jìn)行細(xì)粒度搜索，C組負(fù)責(zé)在全局區(qū)域搜索，這三組相互配合、缺一不可.

2.2 多策略機(jī)制

針對(duì)每個(gè)分組的不同特性，本文引入多策略的思想，為不同分組的個(gè)體設(shè)計(jì)具備不同搜索能力的解搜索方程，具體操作如下.

針對(duì)A組個(gè)體注重開采的特性，設(shè)計(jì)的解搜索方程如下：

vi,j=xi,j+α(xbest,j-xi,j)+α·rand·(xi,j-xr1,j).

(4)

其中:α表示新引入的擾動(dòng)參數(shù)，

MaxFEs表示適應(yīng)度函數(shù)的最大評(píng)價(jià)次數(shù)(Maximum Number of Function Evaluations)，F(xiàn)Es表示已使用的評(píng)價(jià)次數(shù)；Xbest表示全局最優(yōu)個(gè)體，Xr1表示隨機(jī)選擇的一個(gè)個(gè)體，

i∈A,r1=1,2,…,SN，i≠r1≠best；

rand為[0,1]內(nèi)均勻分布的隨機(jī)數(shù)；j=1,2,…,D為隨機(jī)選擇的一個(gè)維度.式(4)的目的是使搜索范圍集中在精英個(gè)體周圍，并且為了防止陷入局部最優(yōu)，在種群中隨機(jī)選擇一個(gè)個(gè)體作為擾動(dòng)個(gè)體，提供一定的多樣性.與此同時(shí)，引入擾動(dòng)參數(shù)α，目的是為了在進(jìn)化過程中動(dòng)態(tài)平衡勘探與開采.在算法初始階段，α值接近于1，此時(shí)個(gè)體的搜索范圍較大，適合進(jìn)行全局搜索，可增加種群多樣性.隨著迭代次數(shù)的增加，搜索范圍會(huì)適當(dāng)減小，有利于加快種群收斂.但注意到，當(dāng)α接近于0時(shí)，會(huì)使Vi接近于Xi，即父代幾乎將全部信息遺傳給子代，不利于種群進(jìn)化.因此，為了保證個(gè)體在算法后期的搜索范圍不至于過小，本文將α的最小值設(shè)置為0.1.

針對(duì)B組中的個(gè)體兼顧勘探與開采的特性，解搜索方程如下：

(5)

其中，Xelite1∈A,Xr2=1,2,…,SN,i≠r1≠r2≠elite1，jrand表示隨機(jī)選擇的一個(gè)維度，α表示擾動(dòng)參數(shù)，CR表示控制參數(shù).式(5)中引入A組中的個(gè)體引導(dǎo)搜索.

此外，為了使B組具有更好的全局搜索能力，在種群中隨機(jī)選擇兩個(gè)個(gè)體作為擾動(dòng)項(xiàng)，引入控制參數(shù)CR，使個(gè)體每次迭代以一定的概率更新多個(gè)維度.顯然相對(duì)A組的解搜索方程，該解搜索方程更偏向于勘探.

針對(duì)C組中的個(gè)體注重全局勘探的特性，解搜索方程設(shè)計(jì)如下：

vi,j=xi,j+rand·(xelite1,j-xi,j)+

α·rand·(xelite2,j-xw,j),

(6)

其中，Xelite1∈A,Xelite2∈A,Xw∈C,i≠w≠elite1≠elite2,α表示擾動(dòng)參數(shù)，與式(4)相同.為了更有效地利用劣勢(shì)個(gè)體的信息，C組中每個(gè)個(gè)體每次迭代均會(huì)更新所有維度，同時(shí)為了防止后期收斂過慢，還引入A組中的個(gè)體引導(dǎo)搜索.

ABC中雇傭蜂主要負(fù)責(zé)勘探新的蜜源，觀察蜂負(fù)責(zé)針對(duì)適應(yīng)度較好的蜜源進(jìn)行局部開采，它們具有不同的分工.在經(jīng)典ABC中，這兩個(gè)階段使用同一解搜索方程.在經(jīng)典解搜索方程中，受隨機(jī)選擇的個(gè)體影響，種群在搜索過程中具有很強(qiáng)的隨機(jī)性，影響算法的整體性能.為了克服該缺點(diǎn)，本文在觀察蜂階段設(shè)計(jì)解搜索方程，引入全局最優(yōu)個(gè)體和精英個(gè)體，有利于目標(biāo)個(gè)體移動(dòng)到適應(yīng)度更好的搜索區(qū)域，具體如下：

vi,j=xi,j+rand·(xelite,j-xi,j)+

rand·(xbest,j-xr1,j),

(7)

各個(gè)變量含義同上，需要注意的是

elite≠best≠r1≠i.

為了加強(qiáng)觀察峰階段的局部開采能力，引入全局最優(yōu)個(gè)體和精英個(gè)體作為擾動(dòng)個(gè)體引導(dǎo)搜索，使目標(biāo)個(gè)體向精英個(gè)體和全局最優(yōu)個(gè)體所在區(qū)域移動(dòng)，加強(qiáng)對(duì)適應(yīng)度值較好的區(qū)域進(jìn)行搜索，并且為了防止算法太過于貪婪，引入隨機(jī)個(gè)體，增加一定的多樣性.

總之，在觀察蜂階段，通過全局最優(yōu)個(gè)體、精英個(gè)體和隨機(jī)個(gè)體這3種不同個(gè)體之間的協(xié)同合作，增強(qiáng)算法的局部開采能力，同時(shí)也確保算法具有一定的全局勘探能力.

2.3 算法步驟

本文算法的偽代碼如下.

算法MABC-FG

輸入種群規(guī)模SN，控制參數(shù)limit，

維度控制參數(shù)CR,

適應(yīng)度函數(shù)的最大評(píng)估次數(shù)MaxFEs

輸出全局最優(yōu)個(gè)體Xbest

對(duì)輸入?yún)?shù)進(jìn)行初始化.

由式(1)產(chǎn)生初始種群，計(jì)算每個(gè)個(gè)體的適應(yīng)度值.

令triali=0，F(xiàn)Es=SN.

while (FEs<=MaxFEs) do

//雇傭蜂階段

根據(jù)個(gè)體的適應(yīng)度值將種群劃分為3組.

fori=1 toSNdo

根據(jù)個(gè)體Xi所在的分組，選擇式(4)～式(6)，產(chǎn)生候選個(gè)體Vi.

如果f(Vi)

否則，令triali=triali+1.

end for

FEs=FEs+SN.

//觀察蜂階段

按式(2)和式(3)計(jì)算個(gè)體被選中的概率pi.

fori=1 toSNdo

ifpi>rand(0,1) then

根據(jù)式(7)產(chǎn)生候選個(gè)體Vi.

如果f(Vi)

否則，令triali=triali+1.

end if

end for

FEs=FEs+SN.

//偵察蜂階段

fori=1 toSNdo

iftriali>limitthen

根據(jù)式(1)重新生成Xi，令triali=0.

FEs=FEs+1.

end if

end for

end while

3 實(shí)驗(yàn)及結(jié)果分析

在測(cè)試函數(shù)方面，本文選取2套權(quán)威的測(cè)試函數(shù)：CEC2013測(cè)試集[23]和CEC2015測(cè)試集[24].這兩套測(cè)試函數(shù)都是求解難度較高的測(cè)試集，涵蓋偏移、旋轉(zhuǎn)和復(fù)合等多種復(fù)雜測(cè)試問題，常用于驗(yàn)證優(yōu)化算法的性能.

為了公平起見，本文將各算法中用到的公共參數(shù)進(jìn)行統(tǒng)一設(shè)置，其余參數(shù)均參照相應(yīng)算法的原始文獻(xiàn)設(shè)置.實(shí)驗(yàn)參數(shù)設(shè)置如下：測(cè)試函數(shù)的維度D=30,50，對(duì)應(yīng)的兩套測(cè)試函數(shù)的最大評(píng)價(jià)次數(shù)MaxFEs=10000D.在所有實(shí)驗(yàn)中，每種算法獨(dú)立運(yùn)行30次,給出30次運(yùn)行的平均結(jié)果和標(biāo)準(zhǔn)差.實(shí)驗(yàn)結(jié)果分析采用Wilcoxon秩和檢驗(yàn)和Friedman檢驗(yàn)，顯著性水平均設(shè)置為0.05.

3.1 參數(shù)敏感性分析

在本文提出的多策略機(jī)制中，針對(duì)B組個(gè)體的特性，引入?yún)?shù)CR控制子代個(gè)體可更新維度.一般而言，越小的CR值會(huì)使子代個(gè)體可更新的維度越少，從父代個(gè)體中獲取越多的信息.但越大的CR值會(huì)使子代可更新的維度越多，搜索范圍也會(huì)越大.因此，CR值的選取會(huì)對(duì)算法性能具有一定影響.

本節(jié)選取CR=0.1,0.3,0.5,0.7,0.9這5個(gè)典型值進(jìn)行測(cè)試，均在CEC2015測(cè)試集上進(jìn)行實(shí)驗(yàn)，測(cè)試函數(shù)維度設(shè)置為30.實(shí)驗(yàn)結(jié)果如表1所示，表中黑體數(shù)字表示最優(yōu)值，Best表示最優(yōu)值的數(shù)量，同時(shí)給出Friedman檢驗(yàn)的結(jié)果.

由表1可看到，當(dāng)CR=0.1和CR=0.7時(shí)，算法性能最優(yōu).但是：當(dāng)CR=0.1時(shí)，算法在7個(gè)函數(shù)上取得最優(yōu)值；當(dāng)CR=0.7時(shí)，算法只在3個(gè)函數(shù)上取得最優(yōu)值.可能的原因是，當(dāng)CR=0.1時(shí)，B組中個(gè)體可從父代中繼承更多的維度，而B組中個(gè)體都是適應(yīng)度值相對(duì)較好的個(gè)體，有較好的引導(dǎo)作用，能使算法的性能更優(yōu).綜合考慮下，本文設(shè)置CR=0.1.

表1 CR不同時(shí)本文算法在CEC2015測(cè)試集上的實(shí)驗(yàn)結(jié)果

種群規(guī)模的大小也影響算法性能，種群規(guī)模越大,越適合全局勘探;反之種群規(guī)模越小,越適合局部開采.因此，選擇一個(gè)合適的種群規(guī)模至關(guān)重要.一般而言，不同的改進(jìn)ABC通常會(huì)采用不同的SN，本文選擇SN=20,30,40,50,100這5個(gè)典型值.具體實(shí)驗(yàn)結(jié)果如表2所示，表中黑體數(shù)字表示最優(yōu)值.

由表2可看出，SN=50時(shí)，算法在10個(gè)函數(shù)上取得最優(yōu)且綜合排名也是最優(yōu)，而SN=20和SN=100時(shí)，算法只在1個(gè)函數(shù)和3個(gè)函數(shù)上表現(xiàn)最優(yōu).這是因?yàn)楫?dāng)種群規(guī)模過大時(shí)，算法會(huì)過度偏向于勘探，而種群規(guī)模過小時(shí)，算法會(huì)過度偏向于開采，使算法性能下降.當(dāng)SN=50時(shí)，種群規(guī)模適中，有利于平衡算法的勘探與開采.綜上所述，本文設(shè)置SN=50.

表2 SN不同時(shí)本文算法在CEC2015測(cè)試集上的實(shí)驗(yàn)結(jié)果

參數(shù)limit控制偵察蜂階段的執(zhí)行頻率，limit越大，偵察蜂階段的執(zhí)行頻率越低，種群越容易陷入局部最優(yōu).limit越小，偵察蜂階段的執(zhí)行頻率越高，影響算法的收斂.所以limit取值對(duì)算法性能也會(huì)有一定的影響.與種群規(guī)模SN類似，不同的改進(jìn)ABC通常會(huì)采用不同的limit，本文設(shè)定limit=100,200,SN·D.具體實(shí)驗(yàn)結(jié)果如表3所示，表中黑體數(shù)字表示最優(yōu)值.由表可知，當(dāng)limit=200時(shí)，算法在8個(gè)函數(shù)上取得最優(yōu)，當(dāng)limit=100和limit=SN·D時(shí)，算法分別在7個(gè)函數(shù)和5個(gè)函數(shù)上取得最優(yōu).從結(jié)果上看，當(dāng)limit=100和limit=200時(shí)，算法整體性能相當(dāng)，但是在F06～F15復(fù)雜函數(shù)上，當(dāng)limit=200時(shí)，算法取得7個(gè)最優(yōu)值，而當(dāng)limit=100時(shí)，算法取得5個(gè)最優(yōu)值.這說明當(dāng)limit過小時(shí)，偵察蜂階段執(zhí)行的頻率過高，會(huì)破壞算法已獲得的搜索經(jīng)驗(yàn)算法，降低算法求解復(fù)雜問題的性能.從整體的排名上看，limit=200時(shí)排名第一，說明limit=200使算法的整體性能更優(yōu)，因此，本文設(shè)置limit=200.

表3 limit不同時(shí)本文算法在CEC2015測(cè)試集上的實(shí)驗(yàn)結(jié)果

3.2 策略有效性驗(yàn)證

相比ABC，本文主要提出兩點(diǎn)改進(jìn)：在雇傭蜂階段采用基于適應(yīng)度分組的多策略機(jī)制；在觀察蜂階段采用基于全局最優(yōu)個(gè)體與精英個(gè)體的解搜索方程.為了分別驗(yàn)證這兩點(diǎn)改進(jìn)之處對(duì)算法性能的影響，設(shè)計(jì)如下對(duì)比算法：1)在ABC的基礎(chǔ)上，僅將基于適應(yīng)度分組的多策略機(jī)制引入雇傭蜂階段，而其它部分與ABC保持相同，該對(duì)比算法記為MABC-FG-1；2)在ABC的基礎(chǔ)上，僅將基于全局最優(yōu)個(gè)體和精英個(gè)體的解搜索方程引入觀察蜂階段，而其它部分與ABC保持相同，該對(duì)比算法記為MABC-FG-2.此外，ABC作為對(duì)比基準(zhǔn)也加入對(duì)比實(shí)驗(yàn).

實(shí)驗(yàn)在CEC 2015測(cè)試集上進(jìn)行，測(cè)試函數(shù)維度設(shè)置為30.結(jié)果如表4所示，表中符號(hào)“+”、“-”、“≈”分別表示MABC-FG優(yōu)于、弱于、相似于對(duì)比算法.由表可看出，MABC-FG-1沒有在一個(gè)函數(shù)上優(yōu)于MABC-FG，這是因?yàn)镸ABC-FG-1的觀察蜂階段仍使用經(jīng)典解搜索方程，不能確保隨機(jī)選擇的個(gè)體好壞，使MABC-FG-1在3個(gè)函數(shù)上弱于MABC-FG.MABC-FG在9個(gè)函數(shù)優(yōu)于MABC-FG-2.由此說明，適應(yīng)度分組機(jī)制能顯著提高種群的搜索效率.注意到MABC-FG-2的總體表現(xiàn)不如ABC，這是由于觀察蜂階段的主要作用是開采精英個(gè)體，而MABC-FG-2的雇傭蜂階段依舊使用經(jīng)典解搜索方程產(chǎn)生候選個(gè)體，隨機(jī)性較強(qiáng)，找到的個(gè)體往往適應(yīng)度不好.

表4 策略有效性驗(yàn)證結(jié)果

總之，MABC-FG的綜合表現(xiàn)優(yōu)于僅有一點(diǎn)改進(jìn)之處的對(duì)比算法，這也說明MABC-FG的兩點(diǎn)改進(jìn)之處是一個(gè)整體、缺一不可.盡管上述實(shí)驗(yàn)可驗(yàn)證本文策略的有效性，但還不足以說明MABC-FG性能較優(yōu).

3.3 實(shí)驗(yàn)結(jié)果對(duì)比

本節(jié)選擇近年來提出的5個(gè)相關(guān)改進(jìn)ABC作為對(duì)比算法:1)LL-ABC[10].基于方向信息和精英機(jī)制的ABC.2)ABCG[19].基于引力模型的ABC.3)iqABC(Improved Quick ABC)[25].4)MGABC[26].基于多精英引導(dǎo)的ABC.5)ECABC[27].基于精英群引導(dǎo)和廣度-深度搜索結(jié)合的ABC.LL-ABC、iqABC、MGABC都涉及對(duì)解搜索方程進(jìn)行改進(jìn)，ECABC、ABCG都融入多策略的思想.

當(dāng)D=30,50時(shí),各算法在CEC2013測(cè)試集上的實(shí)驗(yàn)結(jié)果如表5和表6所示.由表5可看出，當(dāng)D=30時(shí)，MABC-FG在絕大多數(shù)函數(shù)上的性能最優(yōu).從Freidman測(cè)試結(jié)果可看出，MABC-FG的綜合表現(xiàn)排名第一.具體來說，在F01～F05單峰函數(shù)上，MABC-FG在F05上弱于MGABC、ABCG和ECABC，在F01和F02上弱于MGABC.這是因?yàn)镸GABC在偵察蜂階段完成之后，增加一個(gè)對(duì)全局最優(yōu)個(gè)體進(jìn)行鄰域搜索的過程，有效提高算法的開采能力.而MABC-FG利用不同組之間的分工合作進(jìn)行搜索，并未完全依賴于全局最優(yōu)個(gè)體.客觀來說MABC-FG的開采能力稍弱于MGABC.對(duì)于單峰函數(shù)，因?yàn)楹瘮?shù)只有一個(gè)全局最優(yōu)解，適應(yīng)度地形較平滑，使MGABC在該類問題上表現(xiàn)較優(yōu).在F06～F20多峰函數(shù)中，MABC-FG在F07、F09、F12、F13、F15、F20函數(shù)上最優(yōu)，在其余的函數(shù)上也有較優(yōu)性能.在F21～F28組合函數(shù)上，MABC-FG在F23、F24、F25函數(shù)上最優(yōu)，在其余的函數(shù)上也表現(xiàn)不錯(cuò).這是因?yàn)镸ABC-FG中的基于適應(yīng)度分組機(jī)制發(fā)揮重要作用，在該機(jī)制中C組個(gè)體的作用主要是進(jìn)行勘探，可提高算法跳出局部最優(yōu)解的能力，并且A組的個(gè)體專注于開采，有利于提高算法的開采能力.所以在多峰問題和復(fù)雜問題上，MABC-FG具有較優(yōu)性能.總之，MABC-FG在這三種類型的函數(shù)上都具有很強(qiáng)的競爭力.

表5 D=30時(shí)各算法在CEC2013測(cè)試集上的實(shí)驗(yàn)結(jié)果

表6 D=50時(shí)各算法在CEC2013測(cè)試集上的實(shí)驗(yàn)結(jié)果

由表6可看出，當(dāng)D=50時(shí)，MABC-FG綜合表現(xiàn)依舊排名第一，即在絕大多數(shù)函數(shù)上仍保持領(lǐng)先.此外，從Freidman測(cè)試結(jié)果可看出，MGABC綜合性能排名第二.MGABC使用多精英引導(dǎo)機(jī)制，具有較強(qiáng)的開采能力，在高維問題上性能較優(yōu).LL-ABC綜合性能排名第三，這可能是由于方向信息能明確種群個(gè)體每步移動(dòng)的優(yōu)劣，判斷下一步個(gè)體走向，特別在高維問題上表現(xiàn)明顯.

為了進(jìn)一步驗(yàn)證MABC-FG的性能，在CEC2015測(cè)試集上繼續(xù)實(shí)驗(yàn)，當(dāng)D=30,50時(shí)的實(shí)驗(yàn)結(jié)果如表7和表8所示.

表7 D=30時(shí)各算法在CEC2015測(cè)試集上的實(shí)驗(yàn)結(jié)果

表8 D=50時(shí)各算法在CEC2015測(cè)試集上的實(shí)驗(yàn)結(jié)果

由表7可看出，MABC-FG的綜合排名依舊第一，在F01和F02單峰函數(shù)上，MABC-FG在F01函數(shù)上除了與MGABC性能相當(dāng)，優(yōu)于另外四種算法，在F02函數(shù)上,MABC-FG弱于LL-ABC和iqABC.在F03～F05多峰函數(shù)上，MABC-FG的實(shí)驗(yàn)結(jié)果全部優(yōu)于或相似于其它算法.在F06～F15復(fù)雜函數(shù)上,MABC-FG也具有較優(yōu)性能，僅在F14函數(shù)上弱于ABCG、LL-ABC和iqABC.此外，ECABC和MGABC沒有在一個(gè)函數(shù)上優(yōu)于MABC-FG.這是因?yàn)镸ABC-FG是從個(gè)體層面上設(shè)計(jì)多策略機(jī)制，不同分組都具有不同特性，在處理復(fù)雜問題時(shí)，不同分組分工明確、相互合作，提升性能.

由表8可看出，MABC-FG在D=50時(shí)依舊保持領(lǐng)先地位.Friedman檢驗(yàn)結(jié)果中MABC-FG綜合表現(xiàn)排名第一，即隨著問題維度的提升，MABC-FG依然具有較好性能.

由表5～表8的統(tǒng)計(jì)結(jié)果可看出，無論是在單峰函數(shù)上還是多峰函數(shù)上,MABC-FG綜合表現(xiàn)最優(yōu)，尤其在CEC2015測(cè)試集上更明顯.這說明雇傭蜂階段使用的基于適應(yīng)度分組的多策略機(jī)制和在觀察蜂階段設(shè)計(jì)的由全局最優(yōu)個(gè)體和精英個(gè)體引導(dǎo)的解搜索方程相互配合，能明顯提升ABC的性能.

總之，上述實(shí)驗(yàn)驗(yàn)證MABC-FG的性能具有較強(qiáng)的競爭力，原因如下：1)雇傭蜂階段將種群按照適應(yīng)度分為A、B和C組，A組負(fù)責(zé)尋找優(yōu)秀個(gè)體，B組負(fù)責(zé)使種群向精英群體移動(dòng)，C組負(fù)責(zé)全局勘探并逐步向A組移動(dòng)，同時(shí)C組能有效增加種群多樣性，三組分工明確、相互配合，能有效平衡勘探與開采.2)觀察蜂階段使用全局最優(yōu)個(gè)體和精英個(gè)體引導(dǎo)種群搜索，這些個(gè)體由于具有良好的適應(yīng)度，因此其區(qū)域具有很高的開采價(jià)值，在這些區(qū)域搜索能提高搜索效率.

3.4 運(yùn)行時(shí)間對(duì)比

相比ABC，MABC-FG主要是在雇傭蜂階段對(duì)種群中的個(gè)體進(jìn)行排序，會(huì)消耗一定的計(jì)算資源.為了更準(zhǔn)確地評(píng)估MABC-FG的運(yùn)行時(shí)間，本節(jié)給出算法的時(shí)間復(fù)雜度和實(shí)際CPU運(yùn)行時(shí)間.設(shè)種群規(guī)模為SN，問題維度為D，在一次迭代過程中，對(duì)種群個(gè)體進(jìn)行適應(yīng)度排序的時(shí)間復(fù)雜度為O(SN·log(SN)).因?yàn)锳BC的時(shí)間復(fù)雜度為O(SN·D)，所以MABC-FG的整體時(shí)間復(fù)雜度為

O(SN·log(SN)+SN·D).

考慮到D通常情況下會(huì)遠(yuǎn)大于log(SN)，則MABC-FG和ABC的時(shí)間復(fù)雜度均為O(SN·D).

進(jìn)一步分析MABC-FG的運(yùn)行時(shí)間，記錄其在CEC2013測(cè)試集上的實(shí)際CPU運(yùn)行時(shí)間，并與3.3節(jié)的五種算法進(jìn)行對(duì)比.為了確保公平對(duì)比，所有算法均在每個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行30次，以平均CPU運(yùn)行時(shí)間作為最終結(jié)果.

算法運(yùn)行平臺(tái)的配置信息如下：CPU Inter(R)Core i7-10700H,內(nèi)存16 GB,操作系統(tǒng)Microsoft Windows 10 Professional，編程語言Java.

各算法的CPU運(yùn)行時(shí)間如表9所示，表中Avg.為算法在28個(gè)測(cè)試函數(shù)上的總體平均時(shí)間，最后一行為總體平均時(shí)間的排名情況.由表可得，MABC-FG、iqABC、ECABC排在前三位，而LL-ABC、MGABC、ABCG排在后三位.從實(shí)驗(yàn)結(jié)果可知，MABC-FG無論在單峰函數(shù)、多峰函數(shù)、復(fù)雜函數(shù)上運(yùn)行時(shí)間都較短，并且這種優(yōu)勢(shì)在復(fù)雜函數(shù)上更明顯.這是因?yàn)镸ABC-FG并未引入過多的造成額外計(jì)算開銷的操作.綜上可知，MABC-FG在運(yùn)行時(shí)間上同樣也具有競爭力.

表9 D=30時(shí)各算法的CPU運(yùn)行時(shí)間

3.5 在調(diào)頻聲波合成問題上的應(yīng)用

本節(jié)選擇一個(gè)實(shí)際優(yōu)化問題測(cè)試MABC-FG.調(diào)頻(Frequency Modulation, FM)聲波合成在音樂領(lǐng)域中具有重要作用，調(diào)頻合成器是一個(gè)6維高度復(fù)雜的多峰優(yōu)化問題，數(shù)學(xué)表達(dá)式如下：

y(t)=a1sin(ω1tθ+a2sin(ω2tθ+a3sin(ω3tθ)))，

y0(t)=

1.0sin(5.0tθ-1.5sin(4.8)tθ+2.0sin(4.9tθ))，

其中，θ=2π/100，X={a1,ω1,a2,ω2,a3,ω3}為問題的決策向量，ai和ωi的取值范圍為[-6.4,6.35]，i=1,2,3.

該問題優(yōu)化的目標(biāo)是y(t)盡可能接近y0(t)，適應(yīng)度函數(shù)為:

可以看出，函數(shù)的最優(yōu)解f(Xbest)=0.在本次實(shí)驗(yàn)中，D=6，其余的參數(shù)設(shè)置和3.3節(jié)相同，記錄30次運(yùn)行結(jié)果.具體實(shí)驗(yàn)結(jié)果如表10所示，表中黑體數(shù)字表示最優(yōu)值.由表可看到，MABC-FG的平均誤差最小，綜合表現(xiàn)最優(yōu).

表10 D=50時(shí)各算法在FM問題上的實(shí)驗(yàn)結(jié)果

4 結(jié) 束 語

為了克服經(jīng)典ABC僅采用一種解搜索方程和對(duì)所有個(gè)體都一視同仁的缺點(diǎn)，本文提出基于適應(yīng)度分組的多策略人工蜂群算法(MABC-FG).首先，根據(jù)個(gè)體適應(yīng)度的大小將種群分為三組，針對(duì)每組特性，為每組個(gè)體設(shè)計(jì)不同特征的解搜索方程，更好地平衡整個(gè)種群的勘探和開采能力.此外，適應(yīng)度較差的分組還兼有保持種群多樣性的作用，各組之間并非相互獨(dú)立，在勘探或開采的同時(shí)也向更優(yōu)個(gè)體學(xué)習(xí).與此同時(shí)，觀察蜂階段使用全局最優(yōu)個(gè)體和精英個(gè)體引導(dǎo)種群快速向適應(yīng)度值較好的區(qū)域移動(dòng)，確保該區(qū)域被充分開采.為了驗(yàn)證MABC-FG的性能，設(shè)計(jì)5組不同的實(shí)驗(yàn)，驗(yàn)證本文策略的有效性，并通過對(duì)比實(shí)驗(yàn)驗(yàn)證本文算法具有較強(qiáng)的競爭力.今后將考慮把本文算法應(yīng)用于求解更多的實(shí)際優(yōu)化問題，如圖像分割問題等.