蜂群算法

摘 要：蜂群算法是一種非數(shù)值優(yōu)化計(jì)算方法，建立在蜜蜂自組織型與群體智能基礎(chǔ)之上，是近幾年比較熱門的智能算法。本文主要介紹了蜂群算法的研究背景、基本原理、要素構(gòu)成、算法流程和優(yōu)缺點(diǎn)等現(xiàn)狀，并對(duì)蜂群算法存在的問(wèn)題進(jìn)行了一些討論，在此基礎(chǔ)上提出了未來(lái)蜂群算法的發(fā)展方向。

關(guān)鍵詞：蜂群算法；人工智能；現(xiàn)狀；發(fā)展方向

中圖分類號(hào)：TP18

蜂群算法（BCA），是一種非數(shù)值優(yōu)化計(jì)算方法，以蜜蜂自組織型與群體智能基礎(chǔ)上建立的。自1995年提出蜂群算法后，該算法引起了學(xué)者們的極大關(guān)注，并已在組合優(yōu)化、網(wǎng)絡(luò)路由、函數(shù)優(yōu)化、機(jī)器人路徑規(guī)劃等領(lǐng)域獲得了廣泛應(yīng)用。

1 基本原理

在自然界中，當(dāng)蜜蜂蜂群發(fā)現(xiàn)優(yōu)良蜜源（或花粉）時(shí)，它們會(huì)以一種跳舞方式傳達(dá)發(fā)現(xiàn)的蜜源信息。這種舞蹈過(guò)程是：蜜蜂初次采集到花粉后，會(huì)在蜂巢上翩然起舞，舞蹈動(dòng)線呈現(xiàn)“8”的字形，蜜蜂首先沿著直線爬行，隨后再轉(zhuǎn)向左，搖擺腹部，舞蹈動(dòng)線的中軸線和地心引力的夾角表示的是蜜源方向和太陽(yáng)夾角，此舞蹈也可稱為“搖擺舞”。蜂群采蜜的集體智能行為由蜜源、采蜜蜂、待工蜂3個(gè)基本部分組成。

此外，蜂群的智能行為有引入搜索蜜源、為蜜源招募、放棄蜜源3種基本的行為模式。假如蜂群發(fā)現(xiàn)有兩個(gè)密源A和B，在蜂巢的等工蜂沒(méi)有收到關(guān)于蜂巢附近蜜源的信息的時(shí)候，它們有兩種選擇：一是在等工蜂根據(jù)觀察到其它蜜蜂的搖擺舞后，它們被招募并開始按照獲得的信息去尋找密源；二是等工蜂可作為偵察蜂，因蜂群內(nèi)部激勵(lì)行為或其他的可能因素，它們自發(fā)地搜尋蜂巢附近的密源。等工蜂若發(fā)現(xiàn)新的蜜源，蜜蜂依靠自身的記憶能力鎖定蜜源地理位置，并迅速開始采蜜。所以，等工蜂變成采蜜蜜蜂，采蜜回到蜂箱后，它們有三種選擇：一是放棄偵察到新蜜源，成為待工的跟隨蜜蜂；二是跳“搖擺舞”招募蜂巢其它等工蜂，然后一起去蜜源采蜜；三是不招募其它的蜜蜂，繼續(xù)去采蜜。

開始，蜂群的蜜蜂都是偵察蜂，沒(méi)有任何先驗(yàn)知識(shí)，當(dāng)它們搜索到蜜源后，即返回蜂巢的舞蹈區(qū)，根據(jù)蜜源收益度的相對(duì)大小，偵察蜂可以轉(zhuǎn)變?yōu)樯鲜鋈魏我环N蜜蜂，轉(zhuǎn)變的原則有三種：一是當(dāng)采集蜜源的收益度很低時(shí)，它再次成為偵察蜂去搜尋附近的蜜源；轉(zhuǎn)變結(jié)果是放棄上次采集的蜜源。二是所采集蜜源的收益度排名小于臨界值時(shí)，例如排名在后50%，它可以在觀察完舞蹈后轉(zhuǎn)變成為跟隨蜜蜂，結(jié)果是前往相應(yīng)的蜜源采蜜。三是所采集蜜源的收益度排名高于臨界值時(shí)，它們轉(zhuǎn)變?yōu)橐I(lǐng)蜂，在舞蹈區(qū)招募更多的蜜蜂，其結(jié)果是帶領(lǐng)招募的蜂群繼續(xù)在同一蜜源采蜜。

2 要素構(gòu)成

通過(guò)在上述中對(duì)蜂群算法的基本原理的介紹，可以看出蜂群算法是由3個(gè)基本要素構(gòu)成：（1）蜜源。蜜源代表各種可能的解；蜜源值取決于多種因素，例如能量的大小和集中程度、提取該能量的容易程度、蜜源和蜂巢的接近度。考慮簡(jiǎn)單性，以數(shù)字量“收益度”來(lái)衡量蜜源的特點(diǎn)；（2）采蜜蜂。采蜜蜂與具體的蜜源緊密聯(lián)系，這些蜜源是當(dāng)前正在采集的。采蜜蜂攜帶了具體的蜜源信息，主要信息為蜜源與蜂巢的距離、蜜源的收益度、蜜源方向；采蜜蜂通過(guò)“搖擺舞”和其它蜜蜂分享蜜源信息，按照路徑長(zhǎng)度排序和蜜源的收益度，一定比例的成為引領(lǐng)蜂；（3）待工蜂。當(dāng)采蜜蜂正在采集尋找蜜源時(shí)，按工作性質(zhì)分為跟隨蜂、偵察蜂。跟隨蜂是在蜂巢內(nèi)等待，通過(guò)分享采蜜蜂偵察到的信息，尋找合適的蜜源；偵察蜂是去搜索蜂巢附近的新蜜源。

3 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：（1）多角色分工機(jī)制。蜜蜂按照自己角色采用不同的方法搜索，并根據(jù)所得的解的蜜的質(zhì)量自發(fā)的調(diào)整角色，以適應(yīng)下一次搜索過(guò)程；（2）協(xié)同工作機(jī)制。蜜蜂在選擇路徑時(shí)，依據(jù)角色決定是否選用以前蜜蜂留下的信息和利用信息的方式，能以較大概率找到優(yōu)化問(wèn)題的最優(yōu)解；（3）魯棒性強(qiáng)。使用概率規(guī)則而不是確定性規(guī)則指導(dǎo)搜索，不必指導(dǎo)其它先驗(yàn)的信息，有極好的魯棒性和廣泛的適用性；（4）穩(wěn)健性。即使個(gè)體失敗，整個(gè)群體仍能完成任務(wù)；（5）易于與其它方法相結(jié)合。很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能。

缺點(diǎn)：（1）限于局部最優(yōu)解。從算法解的性質(zhì)而言，蜂群算法是在尋找一個(gè)比較好的局部最優(yōu)解，而不是強(qiáng)求是全局最優(yōu)解；（2）工作過(guò)程的中間停滯問(wèn)題。在算法工作過(guò)程當(dāng)中那個(gè)，迭代到一定次數(shù)后，蜜蜂可能在某個(gè)或某些局部最優(yōu)解的鄰域附近發(fā)生停滯。（3）需要較長(zhǎng)的搜索時(shí)間。雖然計(jì)算機(jī)計(jì)算速度的提高和蜂群算法的優(yōu)化在一定程度上可以緩解這一問(wèn)題，但是對(duì)于大規(guī)模優(yōu)化問(wèn)題，還是很大的障礙。

4 蜂群算法的應(yīng)用

（1）函數(shù)優(yōu)化。函數(shù)優(yōu)化問(wèn)題是對(duì)各種蜂群算法性能評(píng)測(cè)的常用算例，是蜂群算法的經(jīng)典應(yīng)用領(lǐng)域。根據(jù)群峰算法構(gòu)造出各種復(fù)雜形勢(shì)的測(cè)試函數(shù)，優(yōu)化問(wèn)題，用其他優(yōu)化方法比較難求解，而蜂群算法可以方便地得到較好的結(jié)果；（2）組合優(yōu)化。問(wèn)題規(guī)模的擴(kuò)大，組合優(yōu)化問(wèn)題的搜索空間急劇擴(kuò)大。由于用枚舉法在目前的計(jì)算機(jī)上很難或者不可能得到其準(zhǔn)確最優(yōu)解，對(duì)于這類復(fù)雜的問(wèn)題，應(yīng)把精力放在尋求其滿意解上，而蜂群算法則是尋求這種滿意解的最佳工具之一；（3）數(shù)據(jù)挖掘。數(shù)據(jù)挖掘數(shù)據(jù)庫(kù)技術(shù)，即是從大型數(shù)據(jù)庫(kù)中提取先前未知的、隱含的、有潛在應(yīng)用價(jià)值的知識(shí)和規(guī)劃。故此數(shù)據(jù)挖掘可比作是搜索問(wèn)題，數(shù)據(jù)庫(kù)可比作搜索空間，挖掘算法可比作搜索策略。所以，使用蜂群算法在數(shù)據(jù)庫(kù)中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行優(yōu)化從而可挖掘出隱含在數(shù)據(jù)庫(kù)中的規(guī)則；（4）機(jī)器學(xué)習(xí)?；诜淙核惴ǖ臋C(jī)器學(xué)習(xí)具備高級(jí)自適應(yīng)系統(tǒng)所具備的學(xué)習(xí)能力，在很多領(lǐng)域中都得到了應(yīng)用，特別是在分類器系統(tǒng)應(yīng)用更為廣泛；（5）圖像處理和模式識(shí)別。圖像處理和模式識(shí)別是計(jì)算機(jī)應(yīng)用專業(yè)中視覺(jué)方面一個(gè)重要研究領(lǐng)域。在當(dāng)前視覺(jué)應(yīng)用領(lǐng)域主要是在圖像壓縮、圖像恢復(fù)、圖像分割、幾何形狀識(shí)別等方面得到了應(yīng)用。

5 蜂群算法存在的局限性

蜂群算法的理論依據(jù)是源于對(duì)生物群落社會(huì)性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，導(dǎo)致了蜂群算法存在一些問(wèn)題：（1）蜂群算法增加了時(shí)間復(fù)雜度。作為全局隨機(jī)搜索算法，能夠以一定的概率避免陷入局部最優(yōu)。然而針對(duì)復(fù)雜空間的全局搜索，無(wú)法避免地增加了時(shí)間復(fù)雜度，耗費(fèi)了大量時(shí)間；（2）蜂群算法的定量計(jì)算依據(jù)少。蜂群算法的數(shù)學(xué)理論基礎(chǔ)相對(duì)薄弱，缺乏具備普遍意義的理論性分析，算法中涉及的各種參數(shù)設(shè)置一直沒(méi)有確切的理論依據(jù)，大多是按照經(jīng)驗(yàn)型方法確定，對(duì)具體問(wèn)題和應(yīng)用環(huán)境依賴性比較大，沒(méi)有辦法像其他智能算法一樣定量計(jì)算；（3）蜂群算法的可靠性有待驗(yàn)證。蜂群算法同其它的自適應(yīng)問(wèn)題處理方法一樣，蜂群算法也不具備絕對(duì)的可信性，處理突發(fā)事件，系統(tǒng)的反應(yīng)是不可測(cè)的，一定程度上增加了應(yīng)用風(fēng)險(xiǎn)；（4）蜂群算法和其它群智能方法與先進(jìn)技術(shù)的融合還不足。

6 研究方向

蜂群算法的思維方法，其在沒(méi)有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題求解方案提供了良好基礎(chǔ)。已研究驗(yàn)證過(guò)的蜂群算法理論及應(yīng)用研究證明蜂群算法是一種能夠解決大多數(shù)優(yōu)化問(wèn)題的新思維方法，且蜂群算法潛在的并行性和分布式特點(diǎn)，其為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)基礎(chǔ)。從理論研究還及應(yīng)用研究的不同角度分析，蜂群算法理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)應(yīng)用價(jià)值的一種理論。

蜂群算法未來(lái)的研究方向：（1）為了更好、更快的找到問(wèn)題的最優(yōu)解，在算法進(jìn)行全局搜索的過(guò)程中，針對(duì)要解決的實(shí)際問(wèn)題，加入局部搜索算法也是很好的思想。利用算法的全局性搜索防止陷入局部最優(yōu)，利用局部搜索來(lái)加快算法的收斂速度，降低時(shí)間復(fù)雜度，在下一步研究中應(yīng)該去解決如何更好地將二者完美的結(jié)合；（2）目前，蜂群算法理論研究現(xiàn)狀是還在基本思想的描述摸索階段，若能夠取得比較大的研究發(fā)現(xiàn)，需要提出一些較為明確的思維方法和嚴(yán)格定義，且還必須總結(jié)出構(gòu)造一些蜂群算法應(yīng)用的規(guī)則，并以此為基礎(chǔ)建立及開發(fā)有實(shí)用價(jià)值的一些基于蜂群理論的算法和方法；（3）加快蜂群算法領(lǐng)域?qū)Ω拍钸M(jìn)行嚴(yán)格定義，使蜂群算法有堅(jiān)實(shí)地科學(xué)性和可信性，當(dāng)處理突發(fā)事件時(shí)候，使系統(tǒng)的反應(yīng)是可測(cè)的，這樣就會(huì)在一定程度上減少其應(yīng)用的風(fēng)險(xiǎn)；（4）蜂群算法還是剛起步，對(duì)她的應(yīng)用還不多，與其它智能算法和先進(jìn)的技術(shù)融合的還不夠好，未來(lái)還有很大的發(fā)展空間，將蜂群算法更多地與啟發(fā)式算法相結(jié)合將會(huì)得到更好的應(yīng)用。

參考文獻(xiàn)：

[1]葛宇，梁靜，王學(xué)平.求解函數(shù)優(yōu)化問(wèn)題的改進(jìn)的人工蜂群算法[J].計(jì)算機(jī)科學(xué)，2013（08）.

作者簡(jiǎn)介：?jiǎn)淌娼?，男，山東淄博人，計(jì)算機(jī)軟件工程（嵌入式）專業(yè)。

作者單位：華東師范大學(xué) 軟件學(xué)院，上海 200062