陳政 張明

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212000）

1 引言

人工蜂群算法［1］（Artificial Bee Colony）是一種屬于啟發(fā)類型的群智能算法，Karaboga在2005年首次提出［2］，其是模仿蜜蜂采蜜機(jī)制，用于最優(yōu)解的搜索，人工蜂群算法在求解過(guò)程中，可以不需要與問(wèn)題相關(guān)的梯度信息，算法具有控制參數(shù)少，易于實(shí)現(xiàn)等優(yōu)勢(shì)，受到越來(lái)越多的關(guān)注，已被應(yīng)用于數(shù)據(jù)挖掘、圖像處理、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。但同時(shí)，在當(dāng)復(fù)雜的優(yōu)化問(wèn)題需要處理的時(shí)候，蜂群算法也存在很多問(wèn)題，例如：收斂速度較慢、容易陷入局部最優(yōu)等。為此，不少學(xué)者研究出了許多關(guān)于ABC算法的改進(jìn)方法［3］。包括，雇傭蜂采取全局最優(yōu)引導(dǎo)的策略，而且隨著實(shí)驗(yàn)次數(shù)，引導(dǎo)程度相應(yīng)減小，從而平衡全局和局部的搜索能力；提出在ABC算法中引入反饋機(jī)制，直接搜索最優(yōu)解最有可能的位置，提高搜索效率［4］；Alam等在ABC算法中提出了，自適應(yīng)步長(zhǎng)機(jī)制，改進(jìn)了算法性能；Aderhold等研究種群規(guī)模和蜜源位置更新公式在算法性能中的重要性，設(shè)計(jì)了兩種ABC算法［5］。

針對(duì)上述問(wèn)題，本文提出了一種對(duì)比機(jī)制，即當(dāng)種群初始化時(shí)，由于初始化的參數(shù)多而復(fù)雜，通過(guò)采取設(shè)置對(duì)比的方式［6］，可以在保證種群多樣性的前提下提高初始解的質(zhì)量；同時(shí)，在蜜蜂搜索到各自的蜜源時(shí)，利用引入算法因子的方式，通過(guò)增加可以根據(jù)進(jìn)化過(guò)程動(dòng)態(tài)變化的因子來(lái)平衡蜂群算法的局部搜索和全局搜索能力，從而提高算法效率以及提升算法精度［7］。最后，根據(jù)仿真實(shí)驗(yàn)和測(cè)試函數(shù)的數(shù)據(jù)對(duì)算法進(jìn)行評(píng)測(cè)。

2 基本蜂群算法

人工蜂群算法，是一種較新的，屬于一類智能優(yōu)化算法，基于模擬蜜蜂的采蜜過(guò)程提出，主要三個(gè)組成部分進(jìn)行組成：食物源和雇傭蜂以及非雇傭蜂［8］。

食物源：代表蜜源。食物源下就是待求優(yōu)化問(wèn)題的可行解，是需要處理的基本對(duì)象［9］。食物源的好壞是通過(guò)蜜源大小評(píng)價(jià)的，即可行解的好壞是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)的。

雇傭蜂：又稱引領(lǐng)蜂，和食物源相對(duì)應(yīng)，一個(gè)食物源就有一個(gè)引領(lǐng)蜂相對(duì)應(yīng)，兩者的個(gè)數(shù)相等［10］；它的任務(wù)包括：發(fā)現(xiàn)食物源信息，一定概率的情況下與跟隨蜂分享信息；概率的計(jì)算通過(guò)人工蜂群算法中的選擇策略，通常根據(jù)適應(yīng)度值以輪盤賭的方法計(jì)算。

非雇傭蜂：包含跟隨蜂與偵査蜂。跟隨蜂根據(jù)引領(lǐng)蜂提供的相關(guān)信息在蜂巢的招募區(qū)內(nèi)選擇食物源［11］，而偵查蜂則在蜂巢附近尋找新的食物源。在人工蜂群算法中，跟隨蜂根據(jù)引領(lǐng)蜂傳遞的食物源信息，在此附近搜索新的食物源。若一個(gè)食物源在經(jīng)過(guò)很多次后仍未被更新，則此引領(lǐng)蜂自動(dòng)成為偵査蜂，尋找新的食物源代替舊的食物源［12］。

蜜蜂搜索操作由式（1）實(shí)現(xiàn)。

其中vij代表食物源位置，φij是［-1，1］中的隨機(jī)數(shù)，xij代表食物源第j維，xkj代表隨機(jī)選擇的不同于i的食物源的第j維位置［13］。式中，fiti為第i個(gè)食物源的收益率，隨著收益率越大，相應(yīng)的食物源被選擇的概率也越大。

0，1內(nèi)均勻分布的隨機(jī)數(shù)；LB和UB分別為問(wèn)題解分量取值的下界和上界。故xi為某個(gè)食物源［14］。

同時(shí)，新解會(huì)根據(jù)下面式子計(jì)算適應(yīng)度：

具體過(guò)程如圖1所示。

圖1 基本算法流程圖

3 改進(jìn)的蜂群算法

本文針對(duì)收斂速度不快、會(huì)極大發(fā)生局部最優(yōu)等問(wèn)題，提出了在種群初始化和個(gè)體搜索方面改進(jìn)之處。

3.1 對(duì)比機(jī)制

在種群初始化時(shí)，由于蜂群算法采取方式的隨機(jī)性，雖然在一定程度上體現(xiàn)了種群的多樣性，但不能夠保證初始解的質(zhì)量［15］，對(duì)后面解的搜索易造成效率上的下降。所以，本文提出對(duì)比機(jī)制，即在初始化解的時(shí)候，對(duì)每個(gè)生成的個(gè)體進(jìn)行M次迭代，這樣能夠達(dá)到質(zhì)量更高的種群［16］。

式子中，x'

ij表示個(gè)體前一次通過(guò)式（3）獲得的第j

3.2 算法因子的引入

在蜂群算法中，個(gè)體是通過(guò)搜索，然后根據(jù)共享的信息選擇最優(yōu)解。但在這過(guò)程中，信息量會(huì)不斷減少，所以要考慮到全局優(yōu)化和局部?jī)?yōu)化的作用［17］。因此，本文在優(yōu)化過(guò)程中，引入算法因子，更好的提高了搜索的蜜源質(zhì)量，即進(jìn)一步篩選最優(yōu)解的值，從而提高搜索能力。

其中i為迭代次數(shù)，i∈[0 ，M]，μij是[- 1，1]之間的隨機(jī)數(shù)，γij是[ ]0，E一個(gè)隨機(jī)數(shù)，E是一個(gè)正數(shù)。yj第j維最優(yōu)解的適應(yīng)值。本文通過(guò)引入以上因子，在全局和局部?jī)煞矫妫?8］，都對(duì)搜索能力得到了相應(yīng)的提高，正題優(yōu)化了算法的性能，從而能夠在搜索的不同階段保證算法最優(yōu)解。

3.3 CABC算法步驟

Step2：引領(lǐng)蜂根據(jù)式（1）搜索新蜜源，然后通過(guò)式（6）比較新蜜源，即適應(yīng)度值。

Step3：之后跟隨蜂根據(jù)式（2）的概率選擇策略來(lái)選擇蜜源。

Step4：通過(guò)貪婪機(jī)制選擇更好的蜜源。

Step5：對(duì)于淘汰的蜜源，引領(lǐng)蜂根據(jù)式（3）轉(zhuǎn)換成偵察蜂。

Step6：記錄蜜源位置。

Step7：判斷能否滿足結(jié)束條件，如果滿足終止則輸出最佳解，否則回到Step2，直到達(dá)到limit值。

4 仿真分析

4.1 測(cè)試函數(shù)選擇與分析

本文為便于實(shí)驗(yàn)仿真，采用以下四個(gè)基本函數(shù)進(jìn)行算法性能比較。

表1 測(cè)試函數(shù)

其中Schwefel為連續(xù)單模態(tài)函數(shù)，Rastrigin和Griewank為多模態(tài)非線性全局優(yōu)化函數(shù)［19］，峰形呈現(xiàn)高低起伏的不定跳躍性，具有震蕩性，因此用來(lái)測(cè)試算法的搜索能力；Rosenbrock函數(shù)較為復(fù)雜，用于測(cè)試算法綜合性能［20］。

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

首先實(shí)驗(yàn)設(shè)備為一臺(tái)64位PC機(jī)，算法是通過(guò)Matlab2014a軟件，用M語(yǔ)言實(shí)現(xiàn)。相關(guān)的實(shí)驗(yàn)設(shè)置參數(shù)如下：種群數(shù)大小設(shè)為40，引領(lǐng)蜂個(gè)數(shù)和跟隨蜂個(gè)數(shù)各為20，最大迭代次數(shù)為1000次，判斷是否停滯的limit=100。

同時(shí)，為體現(xiàn)出算法的優(yōu)化性能，每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行10次，記錄平均值、方差。

從圖2的四個(gè)測(cè)試函數(shù)運(yùn)行結(jié)果看，基本ABC算法存在著收斂速度不快、收斂精度會(huì)比較低的問(wèn)題。而改進(jìn)后的CABC算法，Griewank、Schwefel、Rastrigin函數(shù)不僅收斂速度、精度和全局優(yōu)化能力明顯優(yōu)于ABC算法，即使對(duì)于Rosenbrock函數(shù)，CABC算法早期收斂速度快，后期趨于停滯，但整體性能明顯高于ABC算法。并且，由于CABC算法采取了對(duì)比機(jī)制，在運(yùn)行初期階段，CABC初始解精度方面就明顯優(yōu)于ABC算法，而且與最優(yōu)值的差距明顯縮小，所需要的迭代次數(shù)也明顯減少。

圖2 ABC算法和本文CABC算法的收斂曲線對(duì)比

整體而言，從以上的所有實(shí)驗(yàn)分析可以得出結(jié)論，本文算法在性能上更加具有明顯的改進(jìn)效果，說(shuō)明改進(jìn)的算法很好地改善了基本算法的存在會(huì)發(fā)生局部之最優(yōu)的問(wèn)題，也提高了解的精度。

表2 四個(gè)函數(shù)實(shí)驗(yàn)比較結(jié)果

5 結(jié)語(yǔ)

本文提出了一種改進(jìn)的算法，通過(guò)在種群初始化的時(shí)候，加入對(duì)比機(jī)制，改善了解的質(zhì)量，同時(shí)引入算法因子，更好的保證算法的搜索能力，從這兩個(gè)方面解決了原ABC算法易早熟的問(wèn)題，提高了算法的全局搜索能力。由實(shí)驗(yàn)的數(shù)據(jù)對(duì)比也說(shuō)明了提出的算法在尋優(yōu)精度和尋優(yōu)效果上更好于原始算法。在今后的研究工作中，要集中于多目標(biāo)優(yōu)化問(wèn)題和實(shí)際應(yīng)用的研究上，更好地改善蜂群算法。