鮑韋韋,劉 婷,鄒 康,張立毅,王金海
(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)注。
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。
初始解是算法進(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)生可行的初始解。
在基本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ù)拉伸。
基本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)過程中所起的作用。
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é)合,改善算法性能。
由于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)練等。
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.