多策略混合搜索的人工蜂群算法

宋曉宇，趙 月，趙 明

(沈陽(yáng)建筑大學(xué) 信息與控制工程學(xué)院, 遼寧 沈陽(yáng) 110168)

0 引 言

針對(duì)基本的人工蜂群算法[1,2](artificial bee colony，ABC)收斂速度慢[3]、開(kāi)發(fā)能力[4]不足等問(wèn)題，國(guó)內(nèi)外學(xué)者根據(jù)不同應(yīng)用背景提出不同的改進(jìn)版本。其中部分學(xué)者通過(guò)改進(jìn)搜索策略[5-7]提升ABC性能。而隨著優(yōu)化問(wèn)題的日趨復(fù)雜，單一的搜索策略具有一定的局限性。一些學(xué)者提出具有多個(gè)搜索策略的改進(jìn)算法：Kiran等[8]提出具有5個(gè)策略候選池的ABCVSS算法,并根據(jù)每個(gè)策略成功更新解的次數(shù)選擇搜索策略；Lin等[9]在雇傭蜂階段使用一個(gè)有鄰域最優(yōu)個(gè)體引導(dǎo)的搜索策略，觀察蜂以自適應(yīng)機(jī)制選擇有最優(yōu)解以及精英解引導(dǎo)的兩個(gè)搜索策略，提出ABCLGII算法；Xiang等[10]引入重力模型到ABC算法中，并采用選擇概率分別為95%、3%和2%的3個(gè)搜索策略，提出 ABCG 算法。

為平衡人工蜂群算法的探索與開(kāi)發(fā)能力，本文提出多策略混合搜索的人工蜂群算法。在雇傭蜂階段提出兩個(gè)基于隨機(jī)解搜索的搜索策略用于保持算法的探索能力，并分配不同的混合比例；觀察蜂階段修改兩個(gè)搜索策略，引入精英解[11]作為搜索起點(diǎn)來(lái)提高算法的開(kāi)發(fā)能力，并采用與雇傭蜂相同的混合比例，達(dá)到探索與開(kāi)發(fā)的平衡，從而提升算法的搜索效率。

1 人工蜂群算法

人工蜂群算法是由土耳其大學(xué)的karaboga提出，模擬生物學(xué)中蜜蜂的智能采蜜行為。用于解決多變量函數(shù)優(yōu)化問(wèn)題。ABC算法中包括3種類型的蜜蜂：雇傭蜂，觀察蜂，偵察蜂[12-14]。ABC算法的搜索過(guò)程主要分為以下幾個(gè)階段：

初始化：

首先，隨機(jī)生成初始種群SN，即SN個(gè)具有D維變量的解

xi,j=xmin,j+rand(0,1)(xmax,j-xmin,j)

(1)

式中：i=1，2，…，SN,j=1,2,…,D,xmax和xmin為搜索空間的上界和下界。每個(gè)解xi代表一個(gè)D維向量。

雇傭蜂階段：

雇傭蜂通過(guò)式(2)產(chǎn)生一個(gè)新的候選位置vi,j并檢查新位置的花蜜量。如果新位置優(yōu)于原位置xi,j，則該蜜蜂記住新位置并忘記原位置。即貪婪選擇機(jī)制被用于決定新位置與原位置。所有的雇傭蜂完成搜索過(guò)程后，它們將記憶中的食物源信息通過(guò)舞蹈區(qū)與觀察蜂共享

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

(2)

式中：k,j是隨機(jī)選擇的下標(biāo)，且滿足k∈{1,2，…,SN},j∈{1,2,…,D},k不等于i,φi,j為[-1,1]之間的隨機(jī)數(shù)。

觀察蜂階段：

食物源的適應(yīng)值以及觀察蜂選擇某個(gè)食物源的概率分別為

(3)

(4)

觀察蜂根據(jù)輪盤(pán)賭機(jī)制選擇一個(gè)食物源，像雇傭蜂那樣生成一個(gè)新的位置，然后比較新位置與原位置，擇優(yōu)保留。

偵察蜂階段：

在此階段，如果一個(gè)食物源經(jīng)過(guò)限定的循環(huán)次數(shù)limit后仍沒(méi)有更新，則將該位置放棄。該處的雇傭蜂成為偵查蜂，偵查蜂按式(1)產(chǎn)生新位置。

2 改進(jìn)的人工蜂群算法

眾所周知，基本的人工蜂群算法探索性能好而開(kāi)發(fā)性能弱，這是由于其搜索策略[13]決定的。其次，在雇傭蜂與觀察蜂階段使用同樣的搜索策略，也是制約算法性能的因素。

根據(jù)蜜蜂采蜜的特性，算法在雇傭蜂階段應(yīng)側(cè)重探索能力，使其在整個(gè)種群中探索，從而有大的概率發(fā)現(xiàn)好的區(qū)域。觀察蜂則依據(jù)雇傭蜂分享的已知信息，在一個(gè)較好解附近進(jìn)行開(kāi)發(fā)，從而發(fā)現(xiàn)最優(yōu)解(多峰函數(shù)：全局最優(yōu)解)。

為了提升人工蜂群算法的性能，本文從改進(jìn)搜索策略以及混合搜索方式兩個(gè)方面進(jìn)行改進(jìn)。首先，提出兩個(gè)新的基于高斯分布參數(shù)的搜索策略，用于保持算法的探索能力，并分配不同的混合比例，增加種群多樣性；觀察蜂修改兩個(gè)搜索策略，引入精英解信息，并采用與雇傭蜂相同的混合比例，加快種群收斂。雇傭蜂與觀察蜂的配合，保證算法在保持探索能力的同時(shí)增強(qiáng)開(kāi)發(fā)能力，達(dá)到二者的平衡，進(jìn)而提升算法的搜索效率。

2.1 基于高斯分布的搜索策略

在基本的ABC算法中，雇傭蜂采用式(2)生成候選解，其中，新的候選解是在父代附近產(chǎn)生的。這會(huì)導(dǎo)致算法易于陷入局部最優(yōu)，從而找不到最優(yōu)解。為增強(qiáng)算法的探索能力，Gao提出了CABC

vi,j=xr1,j+φi,j(xr1,j-xr2,j)

(5)

式中：xr1，xr2分別是從種群中隨機(jī)選擇的個(gè)體，互不相等且不等于xi。φi,j是均勻分布產(chǎn)生的[-1,1]之間的隨機(jī)數(shù)。

在式(5)中，用于產(chǎn)生候選解的向量是從種群中隨機(jī)選取的，有較高的隨機(jī)性，因而探索能力較強(qiáng)，對(duì)搜索方向沒(méi)有偏好。

由于式(5)已有非常強(qiáng)的探索性，為更好地平衡探索與開(kāi)發(fā)，本文將參數(shù)φi,j修改為高斯分布N(0,0.4) 產(chǎn)生的隨機(jī)數(shù)。并將修改后的二項(xiàng)式搜索策略命名為CABC1。由于參數(shù)φi,j是高斯分布隨機(jī)數(shù)，相對(duì)于均勻分布隨機(jī)數(shù)，可以提供相對(duì)集中的搜索區(qū)域，加速算法收斂。根據(jù)高斯分布的特性，φi,j有68.3%的概率落在(-0.4，0.4)之間提高開(kāi)發(fā)能力，其余31.7%的概率散落在(-0.4，0.4)外的取值擴(kuò)大搜索范圍，增加種群多樣性。將CABC1用于雇傭蜂階段搜索，可以保證探索能力。然而，因CABC1中產(chǎn)生候選解的個(gè)體是從種群中隨機(jī)選取的，在單峰函數(shù)中可以快速收斂到最優(yōu)解，但是在多峰函數(shù)中，易于陷入局部最優(yōu)。為此，提出另一個(gè)三項(xiàng)式搜索策略CABC2如下

vi,j=xr1,j+φi,j(xr1,j-xr2,j)+ψi,j(xr3,j-xr4,j)

(6)

式中：xr1，xr2，xr3，xr4分別是從種群中隨機(jī)選擇的個(gè)體，互不相等且不等于xi。φi,j是均勻分布產(chǎn)生的隨機(jī)數(shù)且φi,j∈[-1,1]，ψi,j是高斯分布N(0，0.3) 產(chǎn)生的隨機(jī)數(shù)。

在式(6)中，第二項(xiàng)兩個(gè)隨機(jī)解及均勻分布參數(shù)φi,j的使用，保證算法的探索能力。而第三項(xiàng)的引入，提供了步長(zhǎng)組合的更多可能性，增加了逃出局部最優(yōu)的概率。此外，高斯分布參數(shù)ψi,j的使用，調(diào)控xr3與xr4項(xiàng)的步長(zhǎng)，使其有高的概率集中在(-0.3,0.3)之間，小步長(zhǎng)避免錯(cuò)過(guò)最優(yōu)解，同時(shí)，散落在(-0.3,0.3)之外的取值加快收斂。三項(xiàng)式提供了SN(SN-1)(SN-2)(SN-3) 的步長(zhǎng)組合，維持了種群多樣性，對(duì)于步長(zhǎng)方向的選擇提供更多可能性，在一定程度上平衡了算法的探索與開(kāi)發(fā)能力。

2.2 精英解引導(dǎo)的搜索策略

由于真實(shí)的蜂群中，觀察蜂需要在雇傭蜂的引導(dǎo)下進(jìn)行搜索，這就表明觀察蜂需要利用當(dāng)前搜索信息進(jìn)行搜索，從而提高算法的開(kāi)發(fā)能力。因此，在觀察蜂階段，對(duì)CABC1與CABC2改進(jìn)如下

vi,j=xpbest,j+φi,j(xr1,j-xr2,j)

(7)

vi,j=xpbest,j+φi,j(xr1,j-xr2,j)+
ψi,j(xr3,j-xr4,j)

(8)

其中，xpbest是從精英組(本文中，認(rèn)為種群中前20%的個(gè)體為精英，即4個(gè)個(gè)體)中隨機(jī)選擇的精英解，其它參數(shù)與CABC1，CABC2相同。以當(dāng)前種群中精英解作為搜索起始點(diǎn)，可以促進(jìn)種群更快地收斂到最優(yōu)區(qū)域，從而增強(qiáng)開(kāi)發(fā)能力。此外，式(7)的二項(xiàng)式保證算法具有一定的探索能力，式(8)的三項(xiàng)式提供了更多的步長(zhǎng)與方向的組合，維持種群的多樣性，在增強(qiáng)算法開(kāi)發(fā)能力的同時(shí)保證了探索能力。

雖然引入精英解會(huì)加快收斂，但同時(shí)也會(huì)降低探索能力，所以，在雇傭蜂階段采用隨機(jī)解，而在觀察蜂階段引入精英解。此外，為降低選擇壓力，給每個(gè)解一個(gè)均等的開(kāi)發(fā)機(jī)會(huì)，觀察蜂階段棄用輪盤(pán)賭選擇機(jī)制，而采用與雇傭蜂相同的食物源選擇方式。

2.3 混合搜索機(jī)制

隨著對(duì)大量搜索策略的研究，不同的搜索策略在處理不同問(wèn)題或者同一問(wèn)題的不同階段上面展示出不同的特性。因此，一個(gè)混合的方式對(duì)于組合不同特性的搜索策略來(lái)改進(jìn)ABC的性能是有必要的。在本文中，為了確保每個(gè)搜索策略充分發(fā)揮其作用，在雇傭蜂階段與觀察蜂階段均采用混合搜索的方式。

由于不同的混合比例影響算法的搜索效率，本文通過(guò)實(shí)驗(yàn)選取合適的混合比例：采用單峰、多峰、可分離及不可分離的4組不同特性函數(shù)對(duì)不同的混合比例進(jìn)行實(shí)驗(yàn)。混合比例分別采取3∶7，4∶6，5∶5，6∶4，7∶3，8∶2。實(shí)驗(yàn)結(jié)果見(jiàn)表1。在測(cè)試中發(fā)現(xiàn)：比值越大，即二項(xiàng)式搜索策略被分配更多的使用機(jī)會(huì)，算法的收斂速度越快，但同時(shí)在多峰函數(shù)易于陷入局部最優(yōu)，算法不穩(wěn)定；比值越小，即三項(xiàng)式搜索策略被分配更多的使用機(jī)會(huì)，則收斂速度降低，但穩(wěn)定性增加。這是因?yàn)?，二?xiàng)式搜索策略中隨機(jī)選取個(gè)體以及高斯分布的特點(diǎn)，加速種群收斂，但隨著進(jìn)化，個(gè)體之間趨同，種群多樣性降低，易于陷入局部最優(yōu)。而三項(xiàng)式搜索策略可以提供更多的步長(zhǎng)方向的組合，提高跳出局部最優(yōu)的可能性，但代價(jià)是收斂速度降低。在考慮算法的綜合性能前提下，本文設(shè)置混合比例為6∶4。即二項(xiàng)式搜索策略被分配60%的使用機(jī)會(huì)，三項(xiàng)式搜索策略被分配40%的使用機(jī)會(huì)。

表1 混合比例測(cè)試

2.4 MHABC算法流程

(1)參數(shù)初始化，SN=NP/2,limit=SN*D, max_FEs=5000*D, q=0.2

(2)通過(guò)式(1)生成初始種群

(3)評(píng)估種群， 令FEs=SN，trial[i]=0;

(4)while(FEs

(5)雇傭蜂:

(6)fori=1:SN

(7) 隨機(jī)生成[0,1]之間的隨機(jī)數(shù)rt

(8)if(rt<0.6)

(9) 通過(guò)CABC1生成一個(gè)新的候選解

(10)else

(11) 通過(guò)CABC2生成一個(gè)新的候選解

(12)endif

(13) set FEs=FEs+1

(14)iff(vi)

(15)xi=vi,trial[i]=0; if (f(xi)≤Accept) break;

(16)elsetrial[i]=trial[i]+1;

(17)endif

(18)endfor

(19) 對(duì)種群進(jìn)行排序， 并從中選擇前T=q*SN個(gè)解作為精英解

(20)觀察蜂:

(21)fori=1:SN

(22) 隨機(jī)生成[0,1]之間的隨機(jī)數(shù)rt

(23)if(rt<0.6)

(24) 通過(guò)式(7)生成一個(gè)新的候選解

(25)else

(26) 通過(guò)式(8)生成一個(gè)新的候選解

(27)endif

(28) set FEs=FEs+1.

(29)iff(vi)

(30)xi=vi,trial[i]=0; if (f(xi)≤Accept) break;

(31)elsetrial[i]=trial[i]+1;

(32)endif

(33)endfor

(34) 更新全局最優(yōu)解

(35)偵察蜂:

(36)fori=1：SN

(37)if(trial[i]>limit)

(38) 通過(guò)式(1)重置食物源

(39) FEs=FEs+1,trial[i]=0;

(40)endif

(41)endfor

(42)endwhile

2.5 時(shí)間復(fù)雜度分析

MHABC算法所需時(shí)間復(fù)雜度與基本的ABC算法相比，在雇傭蜂階段二者相同，MHABC選擇精英解所需時(shí)間復(fù)雜度為O(q*SN*SN)， 觀察蜂取消輪盤(pán)賭選擇機(jī)制，時(shí)間復(fù)雜度為O(SN*D)。 因?yàn)閝*SN

2.6 高斯分布參數(shù)分析

由于高斯分布參數(shù)影響著搜索策略的更新效率，為分析不同的φi,j與ψi,j取值對(duì)算法性能的影響，本文通過(guò)22個(gè)標(biāo)準(zhǔn)函數(shù)測(cè)試集對(duì)不同的高斯分布參數(shù)取值進(jìn)行實(shí)驗(yàn)。取值如下：φi,j,ψi,j∈{N(0,0.1),N(0,0.2),N(0,0.3),N(0,0.4),N(0,0.5),N(0,0.6),N(0,0.7),N(0,0.8),N(0,0.9),N(0,1.0)}。 經(jīng)過(guò)參數(shù)的不同組合測(cè)試發(fā)現(xiàn)：當(dāng)φi,j取值集中在N(0,0.4) 附近，ψi,j取值集中在N(0,0.3) 附近時(shí)，算法取得較好性能。因此，本文設(shè)置高斯參數(shù)φi,j=N(0,0.4)。ψi,j=N(0,0.3)。 由于篇幅有限實(shí)驗(yàn)數(shù)據(jù)將不進(jìn)行展示。

3 實(shí)驗(yàn)與分析

為了測(cè)試本文提出算法的性能，本文采用文獻(xiàn)[15]中定義的22個(gè)標(biāo)準(zhǔn)函數(shù)測(cè)試集以及函數(shù)可接受值測(cè)試其性能，并與其它ABC及ABC變體算法進(jìn)行對(duì)比。這22個(gè)函數(shù)包括單峰，多峰，可分離，不可分離等特性。其中，f1-f6，f8是單峰連續(xù)函數(shù)，f7是非連續(xù)函數(shù)，f9是噪聲函數(shù)，f10在高維是多峰函數(shù)，f11-f22是多峰函數(shù)。如表2所示，D代表問(wèn)題的維度，函數(shù)可接受值代表當(dāng)一個(gè)函數(shù)的測(cè)試結(jié)果小于等于可接受值，即認(rèn)為這個(gè)結(jié)果是成功的。

本文選取4個(gè)算法(ABC，ABCLGII，ABCG，ABCVSS)與MHABC算法在30維與100維進(jìn)行對(duì)比。所有算法均使用VC++6.0軟件，基于Win 10操作系統(tǒng)進(jìn)行實(shí)驗(yàn)。為了公平比較，所有算法均采用其初始文章中設(shè)置的參數(shù)。具體設(shè)置如下：對(duì)于NP，除ABCLGII=100外，其它均為40，對(duì)于limit除ABCG=200外，其它均為SN*D。為公平起見(jiàn)，所有算法設(shè)置相同的停止條件，即最大評(píng)價(jià)次數(shù)為5000*D。每個(gè)算法獨(dú)立運(yùn)行25次，測(cè)試其均值與標(biāo)準(zhǔn)差。

表3、表4分別為30，100維的均值與標(biāo)準(zhǔn)差測(cè)試結(jié)果，表中加粗字體為表現(xiàn)最好的結(jié)果。最后一行為平均秩和，其值越小，代表此算法綜合排名越靠前。可以看出，30維除ABCG略優(yōu)于MHABC，其它算法均劣于MHABC，100維MHABC排名第一。

為了進(jìn)一步測(cè)試算法的穩(wěn)定性及其效率，每個(gè)算法獨(dú)立運(yùn)行50次，在其可接受解下，測(cè)試其成功率(SR)與函數(shù)評(píng)價(jià)次數(shù)(FEs)。為方便比較，有如下定義：成功率SR=達(dá)到可接受解的次數(shù)/總次數(shù)；成功性能SP=FEs/SR； 加速比AR=SP(其它算法)/SP(MHABC)。 可以看出，成功率越高說(shuō)明算法越穩(wěn)定。對(duì)于加速比，是以本文提出的算法作為一個(gè)基準(zhǔn)，當(dāng)AR大于100%時(shí)，說(shuō)明對(duì)于同樣的問(wèn)題，該算法需要比MHABC多付出代價(jià)才可以達(dá)到相同精度的解，即MHABC具有更高的效率；反之，則說(shuō)明該算法更高效。

表5、表6分別為每個(gè)算法在22個(gè)函數(shù)測(cè)試集下的30，50，100維的成功率與加速比(AR)匯總表。從表5的結(jié)果可以看出，除100維時(shí)，ABCVSS的成功率略高于MHABC，其它算法均不如MHABC，并且，3個(gè)維度的平均成功率排名，MHABC居于第一位。表6是加速比的匯總，ABCVSS的平均AR為119.33%，說(shuō)明對(duì)于同樣的問(wèn)題，ABCVSS需要比MHABC多付出19.33%的函數(shù)評(píng)價(jià)代價(jià)才可以達(dá)到同樣的精度。其它算法的AR也是均高于MHABC，說(shuō)明它們同樣需要比MHABC多付出代價(jià)。通過(guò)成功率與加速比的結(jié)果可以看出，MHABC較之于對(duì)比的算法具有更高的穩(wěn)定性及效率。

為了更直觀地看出每個(gè)算法的收斂速度，圖1～圖4給出4個(gè)函數(shù)在100維時(shí)的收斂過(guò)程，其中，橫坐標(biāo)為函數(shù)評(píng)價(jià)次數(shù)，縱坐標(biāo)為函數(shù)值。從圖中可以看出，對(duì)于單峰函數(shù)(f1)和多峰函數(shù)(f18)，MHABC均具有更快的收斂速度以及能找到精度更高的解；對(duì)于f10，雖然最后求解的精度不是最高，但是通過(guò)斜率可以看出，MHABC有較快的收斂速度；對(duì)于f13，各個(gè)算法均可以找到函數(shù)最優(yōu)值，但是MHABC有更快的收斂速度。精度、成功率與加速比、收斂圖的測(cè)試結(jié)果，說(shuō)明MHABC算法相比于其它算法具有更優(yōu)的性能。

表2 函數(shù)測(cè)試集

表3 30維均值與標(biāo)準(zhǔn)差比較結(jié)果

表4 100維均值與標(biāo)準(zhǔn)差比較結(jié)果

表5 成功率匯總/%

表6 加速比匯總/%

圖1 Sphere函數(shù)收斂

圖2 Rosenbrock函數(shù)收斂

圖3 Griewank函數(shù)收斂

圖4 Alpine函數(shù)收斂

4 結(jié)束語(yǔ)

為解決人工蜂群算法收斂速度慢，開(kāi)發(fā)能力弱等問(wèn)題，本文提出一種MHABC算法。在雇傭蜂階段采用兩個(gè)基于高斯分布參數(shù)的二項(xiàng)式與三項(xiàng)式搜索策略，保證算法有較好的探索能力；觀察蜂階段通過(guò)改變搜索起點(diǎn)，使其在精英解的引導(dǎo)下搜索，可以快速收斂到好的區(qū)域，增強(qiáng)開(kāi)發(fā)能力。6∶4的混合比例將具有不同特征的搜索策略相結(jié)合，可以在進(jìn)化的不同階段提供合適的策略產(chǎn)生候選解，達(dá)到探索與開(kāi)發(fā)能力的平衡。通過(guò)22個(gè)標(biāo)準(zhǔn)函數(shù)測(cè)試集的實(shí)驗(yàn)對(duì)比結(jié)果，提出的算法在搜索精度、穩(wěn)定性、收斂速度方面都優(yōu)于ABC算法及其它對(duì)比的算法。進(jìn)一步將考慮自適應(yīng)方式混合不同的搜索策略。