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

宋曉宇，趙 月，趙 明

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

0 引 言

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

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

1 人工蜂群算法

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

初始化：

首先，隨機生成初始種群SN，即SN個具有D維變量的解

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

(1)

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

雇傭蜂階段：

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

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

(2)

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

觀察蜂階段：

食物源的適應值以及觀察蜂選擇某個食物源的概率分別為

(3)

(4)

觀察蜂根據輪盤賭機制選擇一個食物源，像雇傭蜂那樣生成一個新的位置，然后比較新位置與原位置，擇優保留。

偵察蜂階段：

在此階段，如果一個食物源經過限定的循環次數limit后仍沒有更新，則將該位置放棄。該處的雇傭蜂成為偵查蜂，偵查蜂按式(1)產生新位置。

2 改進的人工蜂群算法

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

根據蜜蜂采蜜的特性，算法在雇傭蜂階段應側重探索能力，使其在整個種群中探索，從而有大的概率發現好的區域。觀察蜂則依據雇傭蜂分享的已知信息，在一個較好解附近進行開發，從而發現最優解(多峰函數：全局最優解)。

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

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

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

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

(5)

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

在式(5)中，用于產生候選解的向量是從種群中隨機選取的，有較高的隨機性，因而探索能力較強，對搜索方向沒有偏好。

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

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

(6)

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

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

2.2 精英解引導的搜索策略

由于真實的蜂群中，觀察蜂需要在雇傭蜂的引導下進行搜索，這就表明觀察蜂需要利用當前搜索信息進行搜索，從而提高算法的開發能力。因此，在觀察蜂階段，對CABC1與CABC2改進如下

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是從精英組(本文中，認為種群中前20%的個體為精英，即4個個體)中隨機選擇的精英解，其它參數與CABC1，CABC2相同。以當前種群中精英解作為搜索起始點，可以促進種群更快地收斂到最優區域，從而增強開發能力。此外，式(7)的二項式保證算法具有一定的探索能力，式(8)的三項式提供了更多的步長與方向的組合，維持種群的多樣性，在增強算法開發能力的同時保證了探索能力。

雖然引入精英解會加快收斂，但同時也會降低探索能力，所以，在雇傭蜂階段采用隨機解，而在觀察蜂階段引入精英解。此外，為降低選擇壓力，給每個解一個均等的開發機會，觀察蜂階段棄用輪盤賭選擇機制，而采用與雇傭蜂相同的食物源選擇方式。

2.3 混合搜索機制

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

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

表1 混合比例測試

2.4 MHABC算法流程

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

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

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

(4)while(FEs

(5)雇傭蜂:

(6)fori=1:SN

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

(8)if(rt<0.6)

(9) 通過CABC1生成一個新的候選解

(10)else

(11) 通過CABC2生成一個新的候選解

(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) 對種群進行排序， 并從中選擇前T=q*SN個解作為精英解

(20)觀察蜂:

(21)fori=1:SN

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

(23)if(rt<0.6)

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

(25)else

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

(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) 更新全局最優解

(35)偵察蜂:

(36)fori=1：SN

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

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

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

(40)endif

(41)endfor

(42)endwhile

2.5 時間復雜度分析

MHABC算法所需時間復雜度與基本的ABC算法相比，在雇傭蜂階段二者相同，MHABC選擇精英解所需時間復雜度為O(q*SN*SN)， 觀察蜂取消輪盤賭選擇機制，時間復雜度為O(SN*D)。 因為q*SN

2.6 高斯分布參數分析

由于高斯分布參數影響著搜索策略的更新效率，為分析不同的φi,j與ψi,j取值對算法性能的影響，本文通過22個標準函數測試集對不同的高斯分布參數取值進行實驗。取值如下：φ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)}。 經過參數的不同組合測試發現：當φi,j取值集中在N(0,0.4) 附近，ψi,j取值集中在N(0,0.3) 附近時，算法取得較好性能。因此，本文設置高斯參數φi,j=N(0,0.4)。ψi,j=N(0,0.3)。 由于篇幅有限實驗數據將不進行展示。

3 實驗與分析

為了測試本文提出算法的性能，本文采用文獻[15]中定義的22個標準函數測試集以及函數可接受值測試其性能，并與其它ABC及ABC變體算法進行對比。這22個函數包括單峰，多峰，可分離，不可分離等特性。其中，f1-f6，f8是單峰連續函數，f7是非連續函數，f9是噪聲函數，f10在高維是多峰函數，f11-f22是多峰函數。如表2所示，D代表問題的維度，函數可接受值代表當一個函數的測試結果小于等于可接受值，即認為這個結果是成功的。

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

表3、表4分別為30，100維的均值與標準差測試結果，表中加粗字體為表現最好的結果。最后一行為平均秩和，其值越小，代表此算法綜合排名越靠前。可以看出，30維除ABCG略優于MHABC，其它算法均劣于MHABC，100維MHABC排名第一。

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

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

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

表2 函數測試集

表3 30維均值與標準差比較結果

表4 100維均值與標準差比較結果

表5 成功率匯總/%

表6 加速比匯總/%

圖1 Sphere函數收斂

圖2 Rosenbrock函數收斂

圖3 Griewank函數收斂

圖4 Alpine函數收斂

4 結束語

為解決人工蜂群算法收斂速度慢，開發能力弱等問題，本文提出一種MHABC算法。在雇傭蜂階段采用兩個基于高斯分布參數的二項式與三項式搜索策略，保證算法有較好的探索能力；觀察蜂階段通過改變搜索起點，使其在精英解的引導下搜索，可以快速收斂到好的區域，增強開發能力。6∶4的混合比例將具有不同特征的搜索策略相結合，可以在進化的不同階段提供合適的策略產生候選解，達到探索與開發能力的平衡。通過22個標準函數測試集的實驗對比結果，提出的算法在搜索精度、穩定性、收斂速度方面都優于ABC算法及其它對比的算法。進一步將考慮自適應方式混合不同的搜索策略。