人工蜂群算法的研究綜述

鮑韋韋，劉 婷，鄒 康，張立毅，王金海

(1.天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津 300387;2.天津大學(xué)電子信息工程學(xué)院，天津 300072;3.天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134)

群體智能(Swarm Intelligence)是指具有簡單智能的個體通過相互協(xié)作和組織表現(xiàn)出群體智能行為的特性，具有天然的分布式和自組織特征［1］，在沒有集中控制且不提供全局模型的前提下表現(xiàn)出了明顯的優(yōu)勢。雖然目前針對群體智能的研究還處于初級階段，且存在許多困難，但群體智能的研究代表了計算機研究發(fā)展的一個重要方向。

2005 年Karaboga D［2］成功地將蜜蜂采蜜原理應(yīng)用于函數(shù)的數(shù)值優(yōu)化，并提出比較系統(tǒng)的人工蜂群算法(Artificial Bee Colony Algorithm，簡稱ABC算法)。目前，關(guān)于ABC算法研究與應(yīng)用還處于初級階段，但由于其控制參數(shù)少、易于實現(xiàn)、計算簡潔、魯棒性強等特點［3］，已成為群體智能領(lǐng)域的研究熱點之一，被越來越多的學(xué)者所關(guān)注。

1 基本ABC算法的基本原理

ABC算法模擬蜂群采蜜過程，通過不同角色蜜蜂間的交流、轉(zhuǎn)換和協(xié)作來實現(xiàn)群體智能。人工蜂群中有三種角色:引領(lǐng)蜂、跟隨蜂和偵察蜂。假設(shè)有SN個食物源，每個食物源xi=|xij|(i=1，2，…，SN，j=1，2，…，D)是一個D 維向量，設(shè)置蜜蜂總的循環(huán)搜索次數(shù)為MCN。引領(lǐng)蜂首先對相應(yīng)的食物源進(jìn)行一次鄰域搜索，再采用貪婪原則選擇食物源，即如果新搜索到的食物源的收益度(即花蜜數(shù)量)優(yōu)于以前的，則用新食物源位置代替舊食物源位置，否則保持舊食物源位置不變。所有引領(lǐng)蜂完成搜索之后，回到舞蹈區(qū)把食物源信息通過跳搖擺舞傳達(dá)給跟隨蜂。跟隨蜂根據(jù)得到的信息按照概率選擇食物源。收益度越高的食物源，被選擇的概率越大。跟隨蜂選中食物源后，也進(jìn)行一次鄰域搜索，并保留收益度較高的食物源。ABC算法就是通過如此重復(fù)搜索，最終來找到收益度最高的食物源。

ABC算法在求解優(yōu)化問題時，食物源的位置代表優(yōu)化問題的可行解，食物源的收益度代表優(yōu)化問題的適應(yīng)度值，人工蜂群搜索最大收益度食物源的過程代表尋找最優(yōu)解的過程，最大收益度食物源代表優(yōu)化問題的最優(yōu)解。

初始化時，通過式(1)隨機產(chǎn)生SN個解。

其中，(xij)max和(xij)min是xij的上、下限;rand為(0，1)之間的一個隨機數(shù)。

引領(lǐng)蜂和跟隨蜂依據(jù)式(2)進(jìn)行解的更新

其中，vij代表在xij附近產(chǎn)生的一個新解，k∈{1，2，…，SN}，k和j 都是隨機選取，k是i 鄰域的一個解，所以k 不能等于i;rij∈［－1，1］是隨機數(shù)，它控制xij鄰域的生成范圍。

跟隨蜂對解的選擇是通過觀察引領(lǐng)蜂的搖擺舞來判斷解的適應(yīng)度值，并依據(jù)選擇概率大小來選擇跟隨哪個引領(lǐng)蜂。適應(yīng)度值fiti和選擇概率pi計算公式如下:

其中，fi是第i個解的目標(biāo)函數(shù)值。

在ABC算法中，還有一個控制參數(shù)limit，用來記錄某個解被更新的次數(shù)。假定某個解連續(xù)limit 次循環(huán)之后沒有得到改善，表明這個解陷入局部最優(yōu)，就要被放棄。假設(shè)被放棄的解是xi，通過式(1)隨機產(chǎn)生一個新解來代替原來解xi。

2 ABC算法的改進(jìn)

2.1 初始解的改進(jìn)

初始解是算法進(jìn)行搜索的起點，基本ABC算法的初始解是隨機生成，如果初始解不夠合理，對算法的性能有很大影響，有必要對初始解的生成方法進(jìn)行改進(jìn)。為了使初始解具有多樣性，均勻分布在搜索空間，丁海軍等［4］提出了小區(qū)間生成法初始化解，保證了初始群體含有較豐富的解，增強了搜索收斂于全局最優(yōu)點的可能。暴勵等［5］采用反向?qū)W習(xí)的方法產(chǎn)生初始解，將有助于效率的提高與解質(zhì)量的改善。羅鈞等［6］利用混沌具有隨機性、遍歷性、初始條件敏感性等特點，提出使用混沌序列初始化解，提高了解的多樣性和搜索的遍歷性。解決約束優(yōu)化問題時，為了確保所有解在ABC算法中的可行性和多樣性，Bolaji A.L 等［7］提出使用回溯算法產(chǎn)生可行的初始解。

2.2 選擇策略的改進(jìn)

在基本ABC算法中，跟隨蜂按輪盤賭方式選擇解，易導(dǎo)致解多樣性的下降，算法過早收斂。搜索最優(yōu)解的過程中，不同階段需要不同的選擇壓力，這樣可以保持解的多樣性和加快最優(yōu)解的收斂速度。為了動態(tài)調(diào)整搜索最優(yōu)解過程中的選擇壓力，丁海軍等［4］在分析現(xiàn)有蜂群算法搜索機制特點的基礎(chǔ)上，將模擬退火算法中的Bolzmann 選擇策略引入到人工蜂群算法中。為了避免適應(yīng)度跨度過大的問題，同時可動態(tài)調(diào)整選擇壓力，步登輝等［8］采用排序選擇方式進(jìn)行指數(shù)拉伸。

2.3 解更新公式的改進(jìn)

基本ABC算法解更新公式中，rij是一個［－1，1］之間的隨機數(shù)，Alam M.S 等［9］提出為rij找到一個合適的縮放因子，使之能夠動態(tài)自適應(yīng)地改變步長，更好地搜索最優(yōu)解。為了克服基本ABC算法本身隨機性大的缺陷，胡珂等［10］利用不同解適應(yīng)度值大小差異來引導(dǎo)優(yōu)化方向。在搜索后期，解非常接近最優(yōu)解甚至在有效位數(shù)內(nèi)都是相同的，因此解更新公式后加上一個攝動因子，通過搜索后期的局部微調(diào)，提高進(jìn)化的收斂速度。基本ABC算法的解更新公式并沒有采用任何對比信息，這很有可能導(dǎo)致算法的局部搜索能力差。王慧穎［11］將全局最優(yōu)解和個體極值的信息引入到引領(lǐng)蜂的搜索模式中進(jìn)一步提高算法的局部搜索能力，而且增加了異步變化學(xué)習(xí)因子，用于調(diào)整蜜蜂自身經(jīng)驗和社會群體經(jīng)驗在整個尋優(yōu)過程中所起的作用。

2.4 與其它算法相結(jié)合

ABC算法由于存在局部收斂問題，在復(fù)雜問題中往往很難得到滿意解。為了解決此不足，可以與其它算法相結(jié)合形成混合算法。

ABC算法是單維更新算法，會導(dǎo)致單維與單維更新之間的矛盾，其主要原因在于解的各維之間單獨更新，缺乏信息交流。El－Abd M［12］將粒子群算法整體更新的思想融入蜂群算法，在蜂群算法的單維更新公式中加入全局信息的影響。步登輝等［9］在單維更新之后加入基于整體更新的試探機制，并且依據(jù)單維更新成功率動態(tài)調(diào)整單維和整體更新的比重。羅鈞等［13］借鑒遺傳算法中組合交叉和變異思想，提出了一種基于遺傳交叉因子的改進(jìn)蜂群優(yōu)化算法，通過采用交叉因子產(chǎn)生出新的解集，增加解的多樣性，跳出局部最優(yōu)，更快搜索到問題的全局最優(yōu)解。禁忌搜索算法的禁忌策略是利用禁忌表存儲已經(jīng)搜索到的局部最優(yōu)解并進(jìn)行標(biāo)記，避免在以后搜索過程中再搜索到這些解，以此來跳出局部最優(yōu)點。羅鈞等［14］借鑒禁忌策略提出了一種具有禁忌策略的蜂群算法。此外，學(xué)者還提出把模擬退火算法、差分進(jìn)化算法等與ABC算法相結(jié)合，改善算法性能。

3 ABC算法的應(yīng)用

由于ABC算法控制參數(shù)少、易于實現(xiàn)、計算簡潔、收斂速度快、全局搜索能力強等優(yōu)點，在一些領(lǐng)域中得到了很好的應(yīng)用。目前，ABC算法的應(yīng)用可以分為以下幾個方面:連續(xù)函數(shù)優(yōu)化問題、車輛路徑問題、作業(yè)車間調(diào)度問題、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練等。

4 總結(jié)與展望

ABC是一種基于群體智能的新興進(jìn)化算法，目前對其研究尚處于初期階段，已有的研究成果還相當(dāng)分散，許多問題有待于進(jìn)一步研究。未來的研究方向主要有以下幾個方面:ABC算法基礎(chǔ)理論的研究、與其它算法相結(jié)合的混合算法研究、ABC算法應(yīng)用研究等。

［1］E.Bonabeau，M.Dorigo，G.Theraulaz.Swarm Intelligence:Fromnatural to Artificial Systems［M］.New York:Oxford University Press，1999:40－58.

［2］D.Karaboga.An Idea Based on Honey Bee Swarm for Numerical Optimization［R］.Technical Report－ TR06，Erciyes University，2005.

［3］S.Bitam，M.Batouche and E.Talbi.A Survey on Bee Colony Algorithms［C］.2011 IEEE International Symposium on Parallel ＆ Distributed Processing，Workshops and PhdForum，2010:1－8.

［4］丁海軍，馮慶嫻.基于boltzmann 選擇策略的人工蜂群算法［J］.計算機工程與應(yīng)用，2009，45(31):53－55.

［5］暴勵，曾建潮.一種雙種群差分蜂群算法［J］.控制理論與應(yīng)用，2011，28(2):266－272.

［6］羅鈞，李研.具有混沌搜索策略的蜂群優(yōu)化算法［J］.控制與決策，2010，25(12):1913－1916.

［7］A.L.Bolaji，A.T.Khader，M.A.Al－betar et al.An Improved Artificial Bee Colony for Course Timetabling［C］.2011 Sixth International Conference on Bio－ Inspired Computing:Theories Applications.IEEE Press，2011:9－14.

［8］步登輝，李景.基于動態(tài)整體更新和試探機制的蜂群算法［J］.計算機應(yīng)用研究，2011，28(7):2508－2511.

［9］M.S.Alam ，M.W.Kabir and M.M.Islam.Self－adaptation of Mutation Step Size in Artificial Bee Colony Algorithm for Continuous Function Optimization［C］.201013th International Conference on Computer and Information Technology，2010:69－74.

［10］胡珂，李迅波，王振林.改進(jìn)的人工蜂群算法性能［J］.計算機應(yīng)用，2011，31(4):1107－1110.

［11］王慧穎，劉建軍，王全洲.改進(jìn)的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用［J］.計算機工程與應(yīng)用，2011，7(13).

［12］M.El-Abd.A Hybrid ABC-SPSO Algorithm for Cintinuous Function Optimization［C］.2011 IEEE Symposium on Swarm Intelligence，2011:1－6.

［13］羅鈞，樊鵬程.基于遺傳交叉因子的改進(jìn)蜂群優(yōu)化算法［J］.計算機應(yīng)用研究，2009，26(10):3716－3717，3753.

［14］羅鈞，盧嘉江，陳偉民，等.具有禁忌策略的蜂群算法評定圓柱度誤差［J］.重慶大學(xué)學(xué)報，2009，32(12):1482－148.