基于隨機(jī)搜索策略的人工蜂群算法

王志剛，尚旭東

（南京師范大學(xué)泰州學(xué)院 數(shù)學(xué)科學(xué)與應(yīng)用學(xué)院，江蘇 泰州225300）

0 引 言

人工蜂群 （artificial bee colony，ABC）算法［1－4］作為一種隨機(jī)優(yōu)化算法，同其它一些隨機(jī)優(yōu)化算法一樣，其本身存在一些缺陷，如收斂速度較慢、求解復(fù)雜多峰函數(shù)時(shí)容易陷入局部最優(yōu)。為此，專家們分別從不同方面提出了相應(yīng)的策略來改善算法的性能［5－11］。文獻(xiàn) ［5］在ABC算法中利用混沌運(yùn)動(dòng)的隨機(jī)性和遍歷性來提高算法的全局搜索能力；文獻(xiàn) ［6］通過引入Rosenbrock旋轉(zhuǎn)方向的辦法對(duì)引領(lǐng)蜂的搜索策略進(jìn)行改進(jìn)，提高了算法的收斂速度；文獻(xiàn)［7］受粒子群算法的啟發(fā)，給出一個(gè)新的搜索算子來加快算法的收斂速度；文獻(xiàn) ［8］提出一種雙種群差分蜂群算法，將種群中的個(gè)體隨機(jī)分成兩組，每組采用不同的優(yōu)化策略同時(shí)進(jìn)行尋優(yōu)；文獻(xiàn) ［9］通過引入混沌映射提出了帶混沌局部搜索的人工蜂群算法；文獻(xiàn) ［10］采用混沌映射和反向?qū)W習(xí)理論初始化種群，然后引入差分變異搜索機(jī)制和一個(gè)平衡選擇兩種搜索機(jī)制的概率，以提高算法的全局進(jìn)化性能；文獻(xiàn) ［11］在ABC算法的搜索策略中通過引入一個(gè)擾動(dòng)概率參數(shù)和自適應(yīng)尺度因子來對(duì)ABC 算法進(jìn)行改進(jìn)，這些改進(jìn)算法都在一定程度上改善了ABC 算法的性能，但仍存在易陷入局部最優(yōu)的不足。

在前人研究的基礎(chǔ)上，本文提出一種基于隨機(jī)搜索策略的人工蜂群算法。算法在蜂群搜索過程中借鑒差分進(jìn)化算法的交叉操作，并采用隨機(jī)選擇的方式來進(jìn)行搜索，同時(shí)在搜索過程中加入一定的擾動(dòng)來增強(qiáng)種群的多樣性。基于8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果表明，與ABC 算法和其它一些改進(jìn)的ABC算法相比，該算法尋優(yōu)精度高、收斂速度快、魯棒性強(qiáng)。

1 人工蜂群算法

ABC算法中，人工蜂群包含引領(lǐng)蜂、跟隨蜂和偵察蜂3個(gè)部分。人工蜂群算法在求解優(yōu)化問題時(shí)，食物源代表優(yōu)化問題的一個(gè)可能解，蜂群采蜜 （食物源）的過程也就是搜尋優(yōu)化問題最優(yōu)解的過程。食物源的優(yōu)劣取決于優(yōu)化問題的適應(yīng)值 （函數(shù)值），適應(yīng)值高的食物源較優(yōu)。人工蜂群算法中解的個(gè)數(shù) （SN ）等于引領(lǐng)蜂或跟隨蜂的個(gè)數(shù)。用xi＝（xi1，xi2，…，xiD）表示第i個(gè)食物源 （i＝1，2，…，SN，D 為搜索空間的維數(shù)）。人工蜂群搜索食物源的過程如下：①引領(lǐng)蜂對(duì)當(dāng)前食物源進(jìn)行鄰域搜索，產(chǎn)生候選食物源，并通過貪婪選擇較優(yōu)的食物源；②跟隨蜂根據(jù)引領(lǐng)蜂分享的信息選擇一個(gè)食物源，進(jìn)行鄰域搜索產(chǎn)生候選食物源，并通過貪婪選擇較優(yōu)的食物源；③引領(lǐng)蜂放棄食物源，變?yōu)閭刹旆洌㈦S機(jī)搜索新的食物源。

引領(lǐng)蜂和跟隨蜂根據(jù)下式在食物源的鄰域生成一個(gè)候選食物源

式中：vij——生 成 的 候 選 食 物 源，k ∈｛1，2，…，SN｝，j ∈｛1，2，…，D｝，這兩個(gè)數(shù)都是隨機(jī)選取的，但k≠i，rij是［－1，1］上均勻分布的隨機(jī)數(shù)。式 （1）稱為ABC 算法的搜索策略。

跟隨蜂通過如下概率來選擇食物源

式中：fiti——第i個(gè)食物源的適應(yīng)值。在最小化問題中，fiti與優(yōu)化問題目標(biāo)函數(shù)值fi的對(duì)應(yīng)關(guān)系為

在ABC算法中，如果連續(xù)經(jīng)過limit 次循環(huán)之后食物源仍然沒有得到更新，則引領(lǐng)蜂就放棄食物源，轉(zhuǎn)變?yōu)閭刹旆洌聪率诫S機(jī)產(chǎn)生一個(gè)新的食物源

2 基于隨機(jī)搜索策略的人工蜂群算法

在式 （1）中，由于rij是［－1，1］上均勻分布的隨機(jī)數(shù)且xkj為隨機(jī)選取的種群中的個(gè)體的一個(gè)分量，使得該搜索策略具有較好的全局搜索能力，但卻忽略了算法的局部搜索能力，使算法的收斂速度較慢［7］。為此，文獻(xiàn) ［7］提出了一種新的搜索策略來對(duì)式 （1）進(jìn)行改進(jìn)

其中，k，j選取與式 （1）相同，ij 是［－1，1］上均勻分布的隨機(jī)數(shù)，φij 為［0，1.5］之間的隨機(jī)數(shù)，xbest為種群最優(yōu)解。由式 （5）可以看出，由于有最優(yōu)解xbest的引導(dǎo)，上述搜索策略既保證了算法具有較強(qiáng)的全局搜索能力，同時(shí)，在一定程度上也提高了算法的局部搜索能力。為進(jìn)一步提高算法的局部搜索能力，可以將式 （5）變化為

與式 （1）、式 （5）相比，式 （6）由于有種群最優(yōu)解引導(dǎo)種群的搜索軌跡并且僅在最優(yōu)解附近產(chǎn)生新的候選解，從而比式 （1）、式 （5）更能提高算法的局部搜索能力，但容易陷入局部最優(yōu)。

從上面的分析可以看出，式 （1）全局搜索能力較強(qiáng)，但局部搜索能力較弱；而式 （6）局部搜索能力較強(qiáng)，全局搜索能力較弱。眾所周知，全局搜索能力和局部搜索能力對(duì)智能優(yōu)化算法是非常必要的，因此，如何平衡全局搜索能力和局部搜索能力是智能優(yōu)化算法獲得較高性能的關(guān)鍵。在對(duì)式（1）和式（6）兩種搜索策略進(jìn)行分析的基礎(chǔ)上，結(jié)合式（1）全局搜索能力較強(qiáng)的優(yōu)點(diǎn)和式 （6）局部搜索能力較強(qiáng)的優(yōu)點(diǎn)，本文采用不確定的隨機(jī)方式來選擇搜索策略，即

其中，rand 為（0，1）之間均勻分布的隨機(jī)數(shù)，由式 （7）可以看出，上述搜索策略改變了ABC 算法原有搜索策略的固定模式，結(jié)合了式 （1）和式 （6）兩種搜索策略，對(duì)搜索策略進(jìn)行隨機(jī)選擇，增強(qiáng)了算法的大范圍搜索。

同時(shí)，為增加種群多樣性，防止算法陷入局部最優(yōu)，我們對(duì)在搜索過程中進(jìn)行小概率的擾動(dòng)，即當(dāng)隨機(jī)數(shù)滿足一個(gè)小概率時(shí)，則進(jìn)行擾動(dòng)，增強(qiáng)算法跳出局部最優(yōu)的能力。擾動(dòng)方式如下

為將隨機(jī)搜索策略和擾動(dòng)操作進(jìn)行有效結(jié)合，我們?cè)O(shè)置一個(gè)參數(shù)DR（發(fā)生擾動(dòng)是小概率事件，因此DR 取值一般要較大，本文取DR ＝0.9995），對(duì)隨機(jī)搜索策略和擾動(dòng)進(jìn)行隨機(jī)選擇，方式如下：

此外，在式 （1）中，引領(lǐng)蜂和跟隨蜂只對(duì)xij作一維鄰域搜索，這導(dǎo)致算法的搜索效率較低，借鑒差分進(jìn)化算法［12］的交叉操作，本文通過引入一個(gè)參數(shù)CR 來控制引領(lǐng)蜂和跟隨蜂對(duì)xij的搜索維數(shù)，具體方式如下

其中，

式中：rij是［－1，1］上均勻分布的隨機(jī)數(shù)，rand 和rand1均為 （0，1）之間均勻分布的隨機(jī)數(shù)，rand（1，D）為［1，D］之間的隨機(jī)整數(shù)。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文算法的性能，選擇8個(gè)典型的測(cè)試函數(shù)用于仿真實(shí)驗(yàn)，對(duì)ABC 算法、文獻(xiàn) ［7］提出的算法 （記為GABC）、采用式 （6）作為搜索策略的ABC 算法 （記為ABCbest）以及本文算法 （記為ABCRSS）進(jìn)行比較和分析。實(shí)驗(yàn)時(shí)，當(dāng)函數(shù)維數(shù)為30時(shí)，4種算法的種群規(guī)模均為SN ＝50，維數(shù)為100時(shí)，種群規(guī)模均為SN ＝100。4種算法中l(wèi)imit ＝100，在ABCRSS 中，對(duì)于f1（x）～f4（x），CR ＝0.9；對(duì)于f5（x）～f8（x），CR ＝0.0005。表1給出了8 個(gè)基準(zhǔn)測(cè)試函數(shù) （f1（x）～f4（x）為單峰函數(shù)；f5（x）～f8（x）為多峰函數(shù)）的表達(dá)式、搜索范圍和理論最優(yōu)值。

表1 經(jīng)典測(cè)試函數(shù)

Best、Worst、Mean和Std分別為算法獨(dú)立實(shí)驗(yàn)10次的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差。Mean反映了在給定的函數(shù)評(píng)價(jià)次數(shù)下算法所能達(dá)到的精度，Std反映了算法的穩(wěn)定性和魯棒性。表2為4種算法對(duì)8個(gè)測(cè)試函數(shù)分別獨(dú)立運(yùn)行10次得到的測(cè)試結(jié)果。圖1～圖8分別給出8個(gè)測(cè)試函數(shù)在30維時(shí)的平均適應(yīng)值收斂曲線。

表2 4種算法的實(shí)驗(yàn)結(jié)果

表2 （續(xù)）

對(duì)于簡(jiǎn)單的單峰函數(shù)f1（x）～f2（x），由表2及圖1和圖2中可知，4種算法的收斂速度都比較快，但本文算法的收斂速度最快，明顯優(yōu)于ABC 算法、GABC 和ABCbest，且計(jì)算精度更高。對(duì)于f3（x），4種算法在進(jìn)化前期收斂速度都很快，在進(jìn)化后期收斂速度明顯減慢，但ABCRSS依然優(yōu)于其它3種算法，且穩(wěn)定性也好于其它3種算法。對(duì)于十分復(fù)雜的非線性函數(shù)f4（x），很多優(yōu)化算法對(duì)此函數(shù)的求解精度都較低，從圖4 中可以看出，ABC 算法、GABC和ABCbest在進(jìn)化后期基本上停止進(jìn)化，而本文算法雖然在進(jìn)化前期收斂速度遜于ABC 算法、GABC 和ABCbest，但在后期卻能持續(xù)進(jìn)化，求解結(jié)果遠(yuǎn)優(yōu)于它們。

圖1 Sphere函數(shù)收斂曲線

圖2 Sum Squares函數(shù)收斂曲線

圖3 Quartic函數(shù)收斂曲線

圖4 Rosenbrock函數(shù)收斂曲線

圖5 Rastrigin函數(shù)收斂曲線

圖6 Griewank函數(shù)收斂曲線

對(duì)于復(fù)雜的非線性多峰函數(shù)，從表2 可以看出，ABCRSS對(duì)于f7（x）的求解結(jié)果不如ABCbest，而對(duì)于其余3個(gè)函數(shù)，ABCRSS的求解結(jié)果都要優(yōu)于ABC 算法、GABC和ABCbest。由于這4個(gè)函數(shù)本身的特性，ABC 算法因?yàn)榫植克阉髂芰^弱從而使得它的收斂速度較慢，導(dǎo)致算法的計(jì)算精度不高，GABC中由于加入了種群最優(yōu)解的引導(dǎo)，在一定程度上可以提高算法的計(jì)算精度和收斂速度，ABCbest雖然具有很快的收斂速度，但當(dāng)函數(shù)比較復(fù)雜時(shí)卻容易陷入局部最優(yōu) （如函數(shù)f5（x）和f6（x）），而ABCRSS較好地平衡了算法的局部搜索能力和全局搜索能力，同時(shí)通過擾動(dòng)增強(qiáng)了種群的多樣性，使算法能跳出函數(shù)中大量的局部最優(yōu)點(diǎn)陷阱。

圖7 Ackley函數(shù)收斂曲線

圖8 Schwefel’s Problem 2.26函數(shù)收斂曲線

綜上，無論是單峰函數(shù)還是多峰函數(shù)，ABCRSS 比ABC算法、GABC和ABCbest在收斂精度和收斂速度上均有較為顯著的提高，并且隨著函數(shù)維數(shù)的增加，ABCRSS也保持了較好的有效性和穩(wěn)健性。這表明，本文提出的算法可以有效改善ABC 算法在優(yōu)化高維函數(shù)時(shí)收斂速度慢、容易早熟收斂的缺陷。

4 結(jié)束語

針對(duì)人工蜂群算法容易陷入早熟的缺點(diǎn)，提出一種基于隨機(jī)搜索策略的人工蜂群算法，該算法為提高搜索效率，在搜索過程中借鑒了差分進(jìn)化算法的交叉操作，并采用隨機(jī)選擇的方式來進(jìn)行搜索以便平衡算法的局部搜索能力和全局搜索能力，同時(shí)在搜索過程中加入一定的擾動(dòng)來增強(qiáng)種群的多樣性。8個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明該算法全局搜索能力好，收斂速度快，計(jì)算精度高。

［1］Karaboga D，Basturk B.On the performance of artificial bee colony（ABC）algorithm ［J］.Applied Soft Computing，2010，8 （1）：687－697.

［2］Karaboga N.A new design method based on artificial bee colony algorithm for digital IIR filters［J］.Journal of the Franklin Institute，2009，346 （4）：328－348.

［3］Singh A.An artificial bee colony algorithm for the leaf－constrained minimum spanning tree problem ［J］.Applied Soft Computing，2009，9 （2）：625－631.

［4］HU Zhonghua，ZHAO Min.Research on robot path planning based on ABC algorithm ［J］.Electric Welding Machine，2009，39 （4）：93－96 （in Chinese）.［胡中華，趙敏.基于人工蜂群算法的機(jī)器人路徑規(guī)劃 ［J］.電焊機(jī)，2009，39 （4）：93－96.］

［5］Alatas B.Chaotic bee colony algorithms for global numerical optimization ［J］.Expert Systems with Applications，2010，37 （8）：5682－5687.

［6］Kang F，Li JL，Ma ZY.Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions［J］.Information Sciences，2011，181 （16）：3508－3531.

［7］Zhu GP，Kwong S.Gbest－guided artificial bee colony algorithm for numerical function optimization ［J］.Applied Mathematics and Computation，2010，217 （7）：3166－3173.

［8］BAO Li，ZENG Jianchao.A bi－group differential artificial bee colony algorithm ［J］.Control Theory ＆ Applications，2011，28 （2）：266－272 （in Chinese）.［暴勵(lì)，曾建潮.一種雙種群差分 蜂 群 算 法 ［J］.控 制 理 論 與 應(yīng) 用，2011，28 （2）：266－272.］

［9］LUO Jun，LI Yan.Artificial bee colony algorithm with chaotic－search strategy ［J］.Control and Decision，2010，25（12）：1913－1916 （in Chinese）.［羅鈞，李研.具有混沌搜索策略的蜂群優(yōu)化算法 ［J］.控制與決策，2010，25 （12）：1913－1916.］

［10］GAO Weifeng，LIU Sanyang.A modified artificial bee colony algorithm ［J］.Computer ＆ Operations Research，2012，39（3）：687－697.

［11］Akay B，Karaboga D.A modified artificial bee colony algorithm for real－parameter optimization ［J］.Information Sciences，2012，192 （1）：120－142.

［12］Stron R，Price K.Differential evolution：A survey of the state－of－the art［J］.IEEE Transaction on Evolutionary Computation，2011，15 （1）：4－31.