趙 越 茹婷婷 袁 越

(1:吉林建筑大學計算機科學與工程學院,長春 130118;2:吉林建筑大學基礎科學部，長春 130118)

0 引言

近年來,生物學家在對蜜蜂進行研究的過程中發(fā)現(xiàn),蜂群采蜜的效率非常高.一個蜂群往往能很快地發(fā)現(xiàn)距離蜂巢一定范圍內(nèi)較優(yōu)質(zhì)的蜜源并由蜂群將其采回.在一個蜂群系統(tǒng)中,由偵察蜂來偵察附近的蜜源.發(fā)現(xiàn)目標之后,偵察蜂會飛回蜂巢附近跳出優(yōu)美的舞姿,其動作幅度與其發(fā)現(xiàn)蜜源的質(zhì)量正相關.該舞姿會吸引一定數(shù)量的蜜蜂采蜜.依據(jù)蜜源的不同質(zhì)量,采蜜蜜蜂分散開來并飛往不同的目標采蜜.相對于偵察過程中所耗費的資源,整個蜂群以較小的代價獲取了最多的食物,這充分體現(xiàn)了群體智慧[1-2].據(jù)此,2005年Karaboga首次提出了人工蜂群算法.該算法的實質(zhì)就是通過仿生的手段來模擬蜂群采蜜的過程,具有較高的靈活性和適應性[3-4].目前該算法已成為群體智能算法領域中一個非常活躍的研究方向,已解決許多工程與技術問題.

1 人工蜂群算法的建模思想

使用人工蜂群算法完成問題建模的過程中,每一個問題的可行解可作為一個蜜源.蜜源能夠提供花蜜的多少即為該可行解優(yōu)劣程度的一個表征.我們假設每一個引領蜂僅對應一個蜜源,當該蜜源的花蜜消耗完畢后,該引領蜂即變?yōu)閭刹旆?由偵察蜂完成新蜜源的搜尋,找到蜜源后偵察蜂又成為一個引領蜂.

人工蜂群算法是一類帶啟發(fā)的Monte Carlo算法,能完成由候選解構成的目標集合通過不斷進化來得到較優(yōu)或最優(yōu)解.算法的進化過程由3個步驟完成,具體如下：① 每只引領蜂附著于一個蜜源,它們之間是一一對應關系.由引領蜂在蜜源鄰域搜索可行解,當發(fā)現(xiàn)更好的蜜源時則更新并依附于新的目標；② 根據(jù)引領蜂提供的蜜源信息,跟隨蜂按照一定的選擇策略依附于一個蜜源,并在該蜜源附近搜索新解.若發(fā)現(xiàn)更好的蜜源則通知引領蜂更改其附著的蜜源.在這樣的方式下,較優(yōu)質(zhì)的蜜源將吸引更多的跟隨蜂到其鄰域完成搜索,能夠增加獲取較優(yōu)解的可能；③ 若對于預先設定的閾值(如進化代數(shù))解的進化過程出現(xiàn)停滯,則引領蜂重新變?yōu)閭刹旆?重新隨機尋找新的蜜源,并以此開始新的搜索過程.

使用這3個步驟,通過合理的設定結束條件或迭代次數(shù),算法能逐漸收斂于最優(yōu)解或較優(yōu)解.

2 人工蜂群算法的框架結構設計

人工蜂群算法能夠以迭代的方式完成解的尋優(yōu)過程.首先在問題的解空間生成M個可行解(蜜源),并將它們與引領蜂建立一一對應的關系，然后完成一輪迭代過程,由每一只引領蜂在其附著蜜源的鄰域內(nèi)尋找一個新的蜜源.如果新蜜源的花蜜儲量(適應度值)高于現(xiàn)有蜜源,那么，引領蜂更新附著狀態(tài),依附于新的蜜源,否則仍舊附著在原先蜜源.在所有引領蜂確認所附著蜜源之后,所有引領蜂將全部蜜源信息發(fā)布給跟隨蜂,由跟隨蜂按照某種選擇原則選取一個蜜源.若以概率的方式選取,假設蜜源k的花蜜儲量為fk,則每一個跟隨蜂選取該蜜源前往的概率pk可表示為:

(1)

從式(1)可以看出,好的蜜源能夠吸引的跟隨蜂一定較多.當每只跟隨蜂確定自己的蜜源之后,便開始在該蜜源的鄰域進行搜索,以期找到更好的蜜源.當蜜源k的所有跟隨蜂對鄰域搜索結束后,選取適應度最高的蜜源作為蜜源k的新位置,即找到一個更優(yōu)解.若蜜源k在迭代步數(shù)內(nèi)仍未取得更優(yōu)解,則視為迭代已陷入局部最優(yōu),此時引領蜂轉化為偵察蜂,拋棄此蜜源并在可行解空間內(nèi)隨機生成新的解作為新的蜜源,重新開始迭代過程.

人工蜂群算法的框架結構設計如下.

算法開始

(1) 算法初始化:

① 設置參數(shù)M，MAXGen，MAXHny，HnyIteri=0(i=1，…，M)；

/*MAXGen代表最大迭代代數(shù),MAXHny代表每個蜜源迭代代數(shù)限制*/

② Form=1 toMdo /*初始種群數(shù)量為M*/

隨機生成蜜源Hm(0);

(2) 算法迭代:

Foriter=1 toMAXGendo

① 對于引領蜂:

Fori=1 toMdo

{將每一個引領蜂附著于一個蜜源之上(兩者一一對應),并計算該蜜源的適應度;

搜索鄰域蜜源并計算其適應度;

取前述適應度高的蜜源,并更新;}

② 對于跟隨蜂:

Forj=1 toMdo

{依據(jù)所有蜜源的適應度值,以概率的方式選擇一個蜜源前往;

在該蜜源的鄰域搜索得到新蜜源,并計算其適應度;

將前述適應度高的蜜源保存;}

③ 偵察蜂尋找新蜜源的過程:

對于所有蜜源:

Fori=1 toMdo

{IfHi(iter)=Hi(iter-1) thenHnyIteri=HnyIter+1;

IfHnyIteri=MAXHnythen

{舍棄蜜源,原先附著其上的引領蜂變?yōu)閭刹旆?

在可行解空間隨機生成蜜源,偵察蜂再次變?yōu)橐I蜂并附著其上;

HnyIteri=0;}

}

④ 記錄下目標適應度值最高的蜜源(最優(yōu)解);

iter=iter+1;

}

(3) 結果輸出:返回所得的最優(yōu)解(適應度最高的蜜源).

3 實驗結果分析

現(xiàn)以多維背包問題為例,在OR-Library實驗室提供的測試數(shù)據(jù)集上選取測試實例,使用VC++ 6.0對人工蜂群算法編程實現(xiàn),每個實例運行10次,結果如表1所示.

表1 人工蜂群算法應用于多維背包問題結果分析

4 結語

實踐表明,人工蜂群算法是一種較優(yōu)秀的群體智能算法.盡管產(chǎn)生時間較晚,算法的很多方面(如引導信息素、信息素擴散機制、最優(yōu)種群大小等)尚需進一步研究,但其性能仍可與現(xiàn)有許多群體智能算法相媲美,如蟻群算法、粒子群算法等.人工蜂群算法現(xiàn)已成為人工智能領域的一個研究熱點問題.隨著各項研究的不斷深入,人工蜂群算法一定能夠更多的解決更多實際問題.

參 考 文 獻

[1] 石俊萍,李必云.改進蜂群算法的旅行商問題仿真[J].計算機工程與設計,2013(4):1420-1423.

[2] 劉 勇,馬 良.函數(shù)優(yōu)化的蜂群算法[J].控制與決策,2012(6):886-889.

[3] 丁海軍,李峰磊.蜂群算法在TSP問題上的應用及參數(shù)改進[J].中國科技信息,2008(3):241-242.

[4] 王 輝.改進的蜂群算法[J].計算機工程與設計,2011(11):3869-3872.