人工蜂群算法研究綜述

曹金保

（陜西師范大學 計算機科學學院，陜西 西安 710062）

傳統(tǒng)的優(yōu)化算法不適宜解決具有高維或者非線性或其他特殊性質(zhì)的大型問題。群智能算法彌補了傳統(tǒng)優(yōu)化算法的缺陷。在很多困難問題的應用上取得了極其好的效果。群智能屬于計算智能的領域[1]，目前的研究非常活躍[2]。人工蜂群算法一種是新興的群智能算法，它具有較強的全局尋優(yōu)能力，較快的收斂速度和適宜解決多種類型的問題的優(yōu)點。蜂群算法在2010年的太原群智能會議上作為專題討論。國外發(fā)表的這方面的論文數(shù)量增加迅速[3]。目前的研究還處于初期階段，所獲得的研究成果較為分散，算法還有些問題需要解決，對蜂群算法的進一步研究十分必要。通過對其全面系統(tǒng)的總結和評述，能夠有效地促進對這一算法的研究和應用。

1 人工蜂群算法的思想

人工蜂群算法（Artificial Bee Colony algorithm，ABC）[4]是建立在蜜蜂自組織模型和群體智能基礎上的一種非數(shù)值計算優(yōu)化方法。Seeley[5]關注于蜂群社會行為模式，最早提煉出了蜂群自組織結構模型。Karaboga D[6]于2005年系統(tǒng)提出人工蜂群算法這一群智能隨機優(yōu)化算法。

蜂群算法思想的產(chǎn)生是有其生物學基礎的。真實世界中的蜂群由蜂王、工蜂和雄蜂組成[7]。蜂王負責繁殖后代，雄蜂負責與蜂王交配，工蜂負責采集食物、撫育幼蟲、照顧蜂王和抵御外敵入侵。人工蜂群算法主要是從工蜂采集食物的過程中抽象出來的。工蜂先從蜂巢出發(fā)，隨機的在蜂巢周圍尋找蜜源。找到蜜源就會采集蜂蜜回到蜂巢將蜂蜜卸下。然后通過跳“8”字搖擺舞向蜂巢的其他工蜂傳遞信息[8，9]。通過飛行速度、畫的“8”字的大小和畫“8”字的方向來告知其他蜜蜂蜜源的各種信息。之后就會有很多的蜜蜂跟著跳舞的蜜蜂去采蜜。之后其他的蜜蜂會招引更多的蜜蜂去采蜜，整個蜂群就會高效的采集到花蜜。當某個蜜源被采集完工蜂就會自動的去尋找新的蜜源。

基于工蜂采蜜過程提取出來的人工蜂群算法主要是由3個要素和2種最基本的行為模式組成。三要素是食物源、雇傭蜂和未被雇傭蜂。行為模式是放棄某個蜜源和為某個蜜源招募。

食物源由于距離遠近、花蜜量多少等原因，其價值有高有低。一般使用收益度來代表蜜源的所有因素。收益度越高蜜源價值越高，反之則價值越低。解決實際問題建模過程中，蜜源的收益度通常對應于目標函數(shù)值得優(yōu)劣。被雇傭蜂又叫做引領蜂，它們帶有蜜源的各種信息，通過“8”字舞與其他蜜蜂以一定的概率來分享這些信息。未被雇傭蜂有兩種，一種是偵察蜂，另外一種是跟隨蜂。偵察蜂的主要功能是尋找新的蜜源，跟隨蜂的主要功能是跟隨引領蜂去采蜜。

蜂群實現(xiàn)采蜜過程的流程圖如下：

人工蜂群算法滿足Millonas的五項群智能原則[10]和Bonabeau等人的4個群自組織的特征[11]。

五項原則:

1）質(zhì)量原則，蜂群能對蜜源的質(zhì)量作出判斷，可以根據(jù)遠近、蜜量多少等信息來分辨出蜜源的優(yōu)劣。

圖1 人工蜂群算法流程圖Fig.1 Flow chart of ABC

2）鄰近原則，蜂群作出時空計算，即蜂群可以搜索蜜源的鄰域。

3）多樣性原則，蜂群的偵查蜂可以探測新的蜜源，保持蜜源的多樣性。

4）適應性原則，蜂群能根據(jù)蜜源的變化調(diào)整采蜜策略，比如蜂群會放棄某個或者某些蜜源。

5）穩(wěn)定性原則，蜂群的跟隨蜂跟隨著找到較好蜜源的引領蜂采蜜，保證了較好蜜源的穩(wěn)定性，不會輕易被放棄。

自組織的4個特征：

1）正反饋，質(zhì)量好的蜜源能通過引領蜂吸引機制吸引更多的蜜蜂來采蜜。

2）負反饋平衡，蜜源枯竭或者本蜜源質(zhì)量排位靠后，蜜蜂就會放棄蜜源作出負反饋。

3）變動性，偵察蜂通過偵查新的蜜源使得蜂群的采蜜過程具有變動性，不會只局限于初始找到的蜜源，蜜源在動態(tài)變化中。

4）交互性，蜂群個體之間以及蜂群與環(huán)境之間存在著信息的交互，群體可以實現(xiàn)隨環(huán)境的變化而進化。

由于群智能算法具有并行性與分布式，所以對于當今以數(shù)據(jù)庫形式存在的大量數(shù)據(jù)非常適合。不僅理論研究有價值，應用研究更有價值。不僅有學術價值更有解決現(xiàn)實問題價值。

2 收斂性證明

對群智能算法的研究，通常關注于能否穩(wěn)定、快速、高效地獲得最優(yōu)解，對算法的理論分析較少。算法的收斂性是算法最重要的性質(zhì)之一。蜂群算法由于其隨機性使得其收斂性的嚴密證明具有一定的難度。本章將對蜂群算法收斂性的證明[12]進行介紹。

2.1 算法的數(shù)學描述

人工蜂群算法定義了3種蜜蜂：偵察蜂、引領蜂和跟隨蜂。這3種蜜蜂構成了蜜蜂角色集合R。算法中的蜜蜂由3方面描述：第一是蜜蜂當前所在的位置x；第二是蜜蜂搜索過程中的最優(yōu)位置g；第三是蜜蜂的角色r。 蜜蜂B=（x，g，r）。 所有的蜜蜂構成了蜂群空間B可行解的集合是S。適應度函數(shù)是 蜜蜂所有的可能的狀態(tài)的集合構成了蜜蜂的狀態(tài)空間H。蜂群經(jīng)過的所有位置中的最優(yōu)位置就是群體的最優(yōu)位置gbest。 狀態(tài)集合狀態(tài)總量用 φ（H，B）來表示。 若H1，H2∈H，?B∈B 使得 φ（H1，B）=φ（H2，B），則稱H1和H2等價，記作H1≌H2。蜂群的狀態(tài)是我們所關注的重點，而哪個狀態(tài)先發(fā)生那個狀態(tài)后發(fā)生并沒有多大的影響。引入等價關系可以使得證明過程得以進行。

2.2 算法收斂性證明所需的數(shù)學知識

定義1：若有隨機過程{Xn，n∈T}，其中T是離散的隨機序列，離散的狀態(tài)集I是由Xn所有可能取值的全體組成的狀態(tài)空間。假如任意的T和任意的I，條件概率滿足

則稱這個隨機過程為離散時間Markov鏈。式1是Markov鏈無后效性（也叫Markov性）的表達式。

定義Markov鏈的轉移概率為

其中i，j∈I。

定義 2：如果任意的i，j∈I，Markov 鏈{Xn，n∈T}的轉移概率Pi，j（n）都和n無關，就稱 Markov 鏈是齊次的，并記Pi，j（n）為Pi，j。

定義 3：稱pi=P{X0}=i（i∈I）和Pi（n）=P{Xn=i}（i∈I）為Markov鏈的初始概率和絕對概率

定義 4：稱{pi，i∈I}和{pi（n）=P{Xn，i∈I}}是初始分布和絕對分布，也可以記為{pi}和{pi（n）}。

定義5:n步轉移概率為=P{Xm+n=j|Xm=i}，n步轉移矩陣為p（n）=（），其中P

2.3 算法的收斂性證明

蜜蜂從狀態(tài)經(jīng)過一步轉移到B2狀態(tài)這一過程如下式所示：

蜂群的位置轉移概率用下式表示：

搜索過程中的最佳位置g的轉移概率用下式表示：

算子Tp[f]定義如下式：

角色轉換的概率定義如下式：蜜蜂的狀態(tài)轉移概率由下式表示：

蜂群從狀態(tài)Hi一步轉移到狀態(tài)Hj的轉移概率如下式所示：

只需證得蜂群狀態(tài)序列是有限齊次Markov鏈，就可以證明蜂群算法是收斂的。

證明：因為蜂群算法的搜索空間是有限的，任何一個蜂群狀態(tài)下的三要素也都是有限的，所以，蜂群的狀態(tài)空間就是有限的。

任意一個H（k-1），H（k）∈S蜂群的狀態(tài)序列{H（k），k≥0}中，對應的轉移概率P（TH（H（k-1）=Hk））都是由蜜蜂的轉移概率P（TB（Bi）（k-1））=Bi（k）所決定。 而蜜蜂的轉移概率又是由位置轉移概率、最優(yōu)位置轉移概率和角色轉移概率三者決定。這三者又只與x，g，r和全局最優(yōu)解gbest相關。gbest是所有的g 中的最優(yōu)值。P（g（k-1）→g（k））只與P（x（k-1）→x（k））和P（g（k-1））相關，所以說P（g（k-1）→g（k））也只與x，g，r和全局最優(yōu)解gbest相關。P（TH（H（k-1）=Hk））只與蜜蜂狀態(tài)相關，也就是{H（k），k≥0}具有Markov性。蜂群的狀態(tài)空間是離散又有限的，所以是有限 Markov 鏈。 因為P（x（k-1）→x（k））、P（g（k-1）→g（k））和P（r（k-1）→r（k））都與時間無關，所以P（TB（B（k-1））=B（k））也與時間無關，最終P（TH（H（k-1）=Hk））也與時間無關，是齊次的。得證{H（k），k≥0}是有限齊次Markov鏈。

通過證明蜂群的狀態(tài)序列是有限齊次Markov鏈，證明了蜂群算法的收斂性。

3 人工蜂群算法的研究與應用的現(xiàn)狀

國內(nèi)外研究主要從兩方面進行，一是算法的改進，另外一方面是算法的應用。

算法改進的已有研究主要有：何宗耀等將蜂群算法與蟻群算法融合，設計了一種參數(shù)自適應機制。王輝通過調(diào)整信息共享程度和在算法后期減弱食物源對蜂群的影響兩方面對蜂群算法進行了改進。畢曉君等改變輪盤賭選擇模型對蜂群算法進行了改進。韋新丹將模擬退火算法引入改進了蜂群算法跟隨蜂的鄰域搜索過程。王志剛將粒子群與蜂群算法進行了融合。向萬里提出一種輪盤賭反向選擇機制來保持蜂群個體的多樣性。李衛(wèi)華等將蜂群算法與BP神經(jīng)網(wǎng)絡算法融合。畢曉君等提出了一種加速收斂的人工蜂群算法。王輝提出了一種帶有共享因子的人工蜂群算法。暴勵等提出了一種雙種群差分蜂群算法。林小軍等提出了一種云變異人工蜂群算法。羅鈞等用遺傳算法改進了蜂群算法。

算法應用的研究成果主要有：Karaboga D等用ABC解決約束優(yōu)化問題、聚類分析和訓練神經(jīng)網(wǎng)絡。趙良輝等用蜂群算法解決了集聚約束調(diào)度問題。Pulikanti等把ABC和貪婪算法、局域搜索算法結合來求解二次方程漸縮的問題。李林菲等應用ABC算法快速求解邏輯推理問題。Kang等將ABC與單純形法結合來解決逆分析問題。拓守恒用 算法解決高維約束優(yōu)化問題。樊小毛等用ABC解決經(jīng)典的0-1背包問題。趙小強等用ABC算法解決模糊聚類問題。Rao等人用ABC算法來優(yōu)化多工序制粉操作過程的參數(shù)。胡中華等用ABC算法來求解TSP和JSP問題。梁建慧等將ABC算法應用在了圖像分割問題中。肖永豪等將ABC算法應用在圖像邊緣檢測問題中。Hsieh等人將ABC算法應用到股票價格預測問題中。黎竹娟將ABC算法應用到移動機器人路徑規(guī)劃問題中。Karaboga將ABC算法應用到數(shù)字無限脈沖反應過濾器設計問題中。姚婧等將ABC算法用于解決云計算負載平衡問題。Rebreyend等人把ABC與貪婪算法結合來優(yōu)化多處理機調(diào)度問題。Sundar等將ABC算法應用于求解二次的最小生成樹問題。王慧穎等改進了蜂群算法并且應用在了函數(shù)優(yōu)化問題中。Banharnsakun等用最優(yōu)選擇法改進ABC算法并應用于圖像配準問題。任新新等將ABC算法應用于配電網(wǎng)無功優(yōu)化問題上。Bernardino等用ABC算法解決加權環(huán)網(wǎng)負荷的問題。劉敏等將ABC算法應用于無人機航路規(guī)劃與平滑問題當中。Ho等將ABC算法應用于求逆電磁問題。周文越等應用ABC算法解決電力系統(tǒng)保護與控制問題。Omkar等用ABC算法解決多目標復合件設計問題。于君等用ABC算法創(chuàng)造出了一種制作群體動畫的方法。Hetmaniok等用ABC算法解決了逆熱傳導問題。張姣玲用ABC算法解決了非線性方程及方程組的求解問題。呂聰穎等用模糊人工蜂群算法解決了加工中心組成問題。算法應用如此之廣泛，可見其應用前景非常廣闊。

4 人工蜂群算法與其他算法的對比分析

4.1 人工蜂群算法與其他群智能算法共同點的分析

人工蜂群算法與其他群智能算法有很多的共同點：

1）都是由多個簡單的智能體組成的。智能體與智能體、智能體與環(huán)境之間有交互作用。

2）都是自組織的。他們沒有一個中央控制器，完全靠每個個體的簡單行為模式出現(xiàn)自組織特性。

3）都是不確定的概率型算法。算法的過程以及最終求得的結果，往往是隨機的，只要其保持收斂性，算法就有可能有較大的機會求得全局最優(yōu)解。

4）都具有廣泛的適用性。算法可以廣泛應用于解決各種優(yōu)化問題。對問題的數(shù)學特征和結構特征要求不嚴格。很多時候一個適應度函數(shù)就可以解決問題。

5）都是收斂的有效的算法。

6）都具有并行性。這些算法與算法可以并行，而且算法本身的計算過程中存在著并行性。

4.2 人工蜂群算法與其他重要群智能算法優(yōu)缺點對比分析

人工蜂群算法與其他重要群智能算法優(yōu)缺點對比分析結果如下面的表1所示。

5 結束語

蜂群算法的應用與研究取得了很多的進展，也證明了蜂群算法[13]具有良好的性能。未來的研究仍然有很多的突破口與切入點。

表1 4種群智能算法優(yōu)缺點對比分析表Tab.1 Advantages and disadvantages comparative analysis table for several swarm intelligence algorithm

1）理論方面。由于蜂群算法是一種概率搜索算法，從嚴格的數(shù)學意義上證明蜂群算法的正確性與可靠性相當困難。對其收斂性的證明也可以從不同的角度進行，也不僅僅是Markov理論這一種。參數(shù)選擇、種群分配以及收斂速度等問題，由于其經(jīng)驗性和直覺性，缺乏嚴格的數(shù)學論證。

2）模型方面。蜂群不僅僅只有抽象出來的這幾種行為模式而已，可以從這種思路提出更好的蜂群算法。也可以借鑒其他算法的模型，進行算法的融合操作。

3）應用領域方面。現(xiàn)有的研究大部分是止步于仿真階段，都對現(xiàn)實情況進行了簡化，所以可以更加深入的向實際問題應用靠近。

4）硬件實現(xiàn)方面。可以將蜂群算法用硬件實現(xiàn)，但是產(chǎn)品的魯棒性、可靠性等問題需要深入探索。也可以研制蜂群算法的仿生平臺，訂立產(chǎn)品的技術標準。

[1]Krol D，Drozdzowski M.Use of MaSE methodology for designing a swarm-based multi-agent system[J].Journal of Intelligent and Fuzzy Systems，2010，21（3）:221-231.

[2]Sabat S L，Udgata S K，Abraham A.Artificial bee colony algorithm for small signal model parameter extraction of MESFET[J].Engineering Applications of Artificial Intelligence，2010，23（5）:689-694.

[3]Karaboga D.A survey algorithms simulating bee swarm intelligence[J].Artificial Intelligence Review，2009，31（1-4）:61-85.

[4]Karaboga D，Akay B.A comparative study of Artificial Bee Colony algorithm[J].Applied Mathematics and Computation，2009，214:108-132.

[5]Seeley T D.The wisdom of the hive:the social physiol-ogy of honey bee colonies[M].Boston，Massachusetts，USA:Harvard University Press，1995.

[6]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06.Erciyes University，2005.

[7]Horng M H，Jiang T W.Image vector quantization algorithm via honey bee mating optimization[J].Expert Systems with applications，2011，38（3）:1382-1392.

[8]Camazine S，Deneubourg J L，F(xiàn)ranks N R，et al.Selforganization in biological systems[M].Princeton:Princeton University Pres，2003.

[9]Dereli T，Das G S.A hybrid bee （s） algorithm for solving container loading problems[J].Applied Soft Computing，2011，11（2）:2854-2862.

[10]MillnasM M.Swarms，phase transitions，and collective intelligence[C]//Proc of Artificial LifeⅢConference.New York，Addison-Wesley Publishing Company，1994:417-445.

[11]Bonabeau E，Dorigo M，Theraulaz G.Swarm intelligence:from natural to artificial systems[M].New York:Oxford University Press，1999.

[12]肖永豪.蜂群算法及在圖像處理中的應用研究[D].廣州：華南理工大學，2011.

[13]黃孝倫.蜂群算法在智能交通中的應用研究[J].現(xiàn)代電子技術，2010（14）:134-135，139.

HUANG Xiao-lun.Applied research of bee colony algorithm in intelligent transportation System[J].Modern Electronics Technique，2010（14）:134-135，139.