人工蜂群算法及應(yīng)用新探

趙 越 茹婷婷 袁 越

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

0 引言

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

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

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

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

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

2 人工蜂群算法的框架結(jié)構(gòu)設(shè)計(jì)

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

(1)

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

人工蜂群算法的框架結(jié)構(gòu)設(shè)計(jì)如下.

算法開始

(1) 算法初始化:

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

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

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

隨機(jī)生成蜜源Hm(0);

(2) 算法迭代:

Foriter=1 toMAXGendo

① 對(duì)于引領(lǐng)蜂:

Fori=1 toMdo

{將每一個(gè)引領(lǐng)蜂附著于一個(gè)蜜源之上(兩者一一對(duì)應(yīng)),并計(jì)算該蜜源的適應(yīng)度;

搜索鄰域蜜源并計(jì)算其適應(yīng)度;

取前述適應(yīng)度高的蜜源,并更新;}

② 對(duì)于跟隨蜂:

Forj=1 toMdo

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

在該蜜源的鄰域搜索得到新蜜源,并計(jì)算其適應(yīng)度;

將前述適應(yīng)度高的蜜源保存;}

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

對(duì)于所有蜜源:

Fori=1 toMdo

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

IfHnyIteri=MAXHnythen

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

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

HnyIteri=0;}

}

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

iter=iter+1;

}

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

3 實(shí)驗(yàn)結(jié)果分析

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

表1 人工蜂群算法應(yīng)用于多維背包問題結(jié)果分析

4 結(jié)語

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

參 考 文 獻(xiàn)

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

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

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

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