1、第三章人工蜂群算法及其改進3.1介紹在自然界中，群體是由多個為實現(xiàn)一共同目標的個體構(gòu)成，目標可以是抵御捕食者、 建巢穴、保留或繁殖種群、充分利用環(huán)境中的資源等。在群體中為完成目標，存在著任 務選擇機制和分工，個體根據(jù)局部規(guī)則和相鄰個體間的相互作用進行自組織。這些低層 次的交互導致了全局的群體行為。Bonabeau等人1將自組織定義為正反饋、負反饋、 波動和多重交互作用的組合。正反饋促進個體更頻繁地做出有益的行為，或促使其他個 體向適當?shù)男袨榭繑n。螞蟻分泌信息素或蜜蜂跳舞都是正反饋的例子。由于正反饋效應 的存在，當種群趨于飽和時，負反饋機制拋棄了無效的模式。螞蟻信息素的蒸發(fā)或蜜蜂 放棄已耗盡的資

2、源就是負反饋的例子。這種波動帶來了創(chuàng)造力和創(chuàng)新，以探索新的模式。 多重交互是群中相鄰代理之間的通信。自組織和分工使群體適應外部和內(nèi)部的變化。結(jié) 合上述特點的群體智能具有可擴展性、容錯性、適應性、速度快、模塊化、自主性、并 行性等優(yōu)點2。螞蟻、白蟻、蜜蜂、鳥類和魚類群居生活，在沒有監(jiān)督的情況下共同完成一些任務。 這些生物的集體和智能行為啟發(fā)一些研究人員將集體智能應用到解決問題的技術(shù)中。 Dorigo3的蟻群優(yōu)化算法和Kennedy和Eberhart4的粒子群優(yōu)化算法都是群體智能算法 的例子。蜂群具有多種智能行為模式，如巢內(nèi)任務分工、交配、導航、巢址選擇、覓食等5。 蜜蜂通過自組織和分工特性，非常

3、有效地完成覓食任務。被分配到覓食任務的蜜蜂分為 三類:雇傭蜂、觀察蜂和偵察蜂，這與覓食任務中的勞動分工相對應。雇傭蜂負責開采食 物來源，并通過舞蹈招引其他蜜蜂。觀察蜂在蜂房中等待，通過觀看雇傭蜂的舞蹈來選 擇食物來源。偵察蜂尋找未知的新資源。被剝削殆盡的食物來源被雇傭蜂拋棄，此時雇 傭蜂就變成了偵察蜂。將蜜蜂招引到有利的資源中是一種正反饋現(xiàn)象，而放棄枯竭的資 源則是一種負反饋現(xiàn)象。偵察蜂尋找未被發(fā)現(xiàn)的食物來源是一種波動效應，它給現(xiàn)有的 食物來源帶來新的發(fā)現(xiàn)。蜜蜂通過舞蹈進行的交流包含了食物源的位置信息和質(zhì)量信息， 這是自組織的多重交互特性。由Karaboga6設(shè)計的人工蜂群算法(ABC)是一種

4、模擬蜜蜂覓食行為的群體智能算 法，可以成功地用于優(yōu)化無約束和有約束、單目標和多目標以及連續(xù)和組合設(shè)計問題5, 7。本部分將詳細介紹ABC算法及其改進。3.2 ABC算法2005年，Karaboga開發(fā)了一種模擬蜜蜂覓食行為的優(yōu)化算法，并將其稱為人工蜂 群算法(ABC)。該算法使用一群食物源位置，每個食物源都是優(yōu)化問題的可選方案，而 食物源的花蜜量就是該方案的適應度。該算法除了使用蜜蜂執(zhí)行的各種選擇機制外，還 使用一些局部和全局搜索機制，試圖找到一個最優(yōu)解(最有利的食物源)。如前一節(jié)所述，蜜蜂根據(jù)食物來源的選擇類型分為三組，這些類對應于算法的階段。 算法的主要步驟如下：初始化repeat雇傭蜂階

5、段觀察蜂階段記憶當前獲得的最優(yōu)解偵查蜂階段until達到終止標準算法1： ABC算法的主要步驟在初始化階段，使用下式隨機初始化食物源種群：列. = w嚴+ rand(0,1)(町皿-町也)X = Xmin + rand(0,1)(xmax - Xmin)( 1)其中i = 1 SN, j = 1 D，SN是食物源數(shù)量，D是設(shè)計參數(shù)的個數(shù)(即維度)，xmin j和Xmax分別是第j維的下界和上界。j最初的種群是通過雇傭蜂、觀察蜂和偵察蜂的覓食循環(huán)來改善的，覓食循環(huán)將一直 迭代至終止準則滿足。終止準則可以是達到最大評估次數(shù)，也可以是找到一個可接受的 函數(shù)值。在雇傭蜂階段，通過在食物源的領(lǐng)域內(nèi)進行局

6、部搜索來模擬真實覓食行為中的食物 源開采?；A(chǔ)ABC算法的局部搜索由式（2）定義：v = x +?。ㄓ?一x ）（2）ij ij ij ij kj其中，是當前解，k是隨機選擇的鄰域解，%是-1,1之間符合均勻分布的隨機數(shù)。 上式定義的局部搜索中，只改變了當前解中隨機選擇的一個維度（參數(shù)j）。局部搜索 完成后，貪婪選擇當前解和變異解中較好的解保留下來，并丟棄較差解。種群中的每個 食物源都會應用局部搜索和貪婪選擇。在文獻7中提出了在局部搜索ABC時的各種改進。一旦雇傭蜂階段完成，就開始觀察蜂階段開始。在這一階段會搜索食物源的鄰域， 以尋找類似于雇傭蜂階段中的較優(yōu)解一樣。不同的是，搜索不是在每個解附

7、近逐一執(zhí)行 的，相反，需要搜索的解是根據(jù)適應度值隨機選擇的，也就是說高質(zhì)量的解將更有可能 被選擇到，這就是ABC算法的正反饋屬性。選擇每個解的概率正比于其適應度值：p = fitnesst（3）1 SN fitness計算出概率值后，采用基于適應度值的選擇機制以較大機會選擇較優(yōu)解，選擇機制 可以是輪盤賭、基于排名、隨機遍歷抽樣、錦標賽等，而在基礎(chǔ)的ABC中采用的是輪 盤賭，這與真實蜂群是類似的，根據(jù)雇傭蜂的跳舞信息，更好的食物源會吸引更多蜜蜂 的注意。一旦概率性的選擇了 SN個解，并在這些解的附近進行局部搜索，然后貪婪搜 索以獲得更優(yōu)的解。在雇傭蜂和觀察蜂階段，如果局部搜索無法再改善解，那么其

8、計數(shù) 器加1，該計數(shù)器保存了這個解在種群中被利用和保留的次數(shù)，因此這類似于現(xiàn)實中蜜 蜂開發(fā)食物源的數(shù)量。在現(xiàn)實中，就像ABC算法中所模擬的那樣，一個食物源的花蜜 在開采結(jié)束時被耗盡，如果一個食物源被充分開采，這個食物源就會被其蜜蜂拋棄。計 數(shù)器用于確定開采的充分性和耗盡性，如果計數(shù)器超過限制，和該計數(shù)器相關(guān)聯(lián)的解被 認為已耗盡，然后被通過式（1）隨機產(chǎn)生的新解替代。對于所有階段，算法包含三個控制參數(shù)：食物源數(shù)量、循環(huán)最大代數(shù)和確定食物源 耗盡的上限。對于實參數(shù)優(yōu)化，對ABC算法的改進提高了其收斂性8。在基礎(chǔ)的ABC算法中， 變異解的生成只是通過改變參數(shù)向量中一維，而在改進的ABC算法中可以改變

9、多維：，x +4 Q -x ）, ifR MRu廣 W， kJotherwise（4）i j其中R是修改率，由（0,1）上的標準正態(tài)分布得到，MR控制擾動的頻率。因此對于每一個維度J，如果滿足R MR，就通過局部搜索產(chǎn)生v，否則v等于x。J J J J在8中，還提出了對的大小的改進。在基礎(chǔ)的ABC算法中是-1,1之間的隨機 數(shù)，而改進后則是由尺度因子限定的區(qū)間l-SF, SF得到，SF是尺度因子，基于Rechenberg的1/5規(guī)則進行自動調(diào)整以實現(xiàn)微調(diào)，即如果成功變異與所有變異的比率小 于1/5，則降低SF，否則增大以加速搜索。參數(shù)定義：CS：食物源數(shù)量，MCN：最大循環(huán)次數(shù)，limit :

10、放棄食物源的最大試驗次數(shù)，即食物源耗盡上限。begin初始化for s=1 to CS do使用式（1）隨機生成解；計算解的適應度值；初始化試驗次數(shù)為0.endcycle=1；while cycleMCN do雇傭蜂階段for s=1 to CS do根據(jù)式（2）隨機生成一個新解；計算新解的適應度值；貪婪選擇if新解適應度由于原有解then用新解替換原有解；else原有解試驗次數(shù)加1；endend根據(jù)式（3）計算觀察蜂選擇概率；觀察蜂階段（注意，此處仍然需要變異CS次，但是較優(yōu)解變異次數(shù)更多for s=1 to CS do根據(jù)上面計算的概率選擇解并按公式（2）產(chǎn)生新解；計算新解的適應度值；貪婪

11、選擇if新解適應度由于原有解then用新解替換原有解；else原有解試驗次數(shù)加1；endend記憶當前獲得的最優(yōu)解;偵查蜂階段找出試驗次數(shù)最大的解，超過limit則根據(jù)式(1)重新初始化；cycle+；endend算法2參考文獻Bonabeau, E., M. Dorigo, and G. Theraulaz, Swarm Intelligence - From Natural to Artificial Systems. Vol. 14. 1999.Kassabalidis, I., et al. Swarm intelligence for routing in communication

12、 networks. in GLOBECOM01. IEEE Global Telecommunications Conference (Cat. No.01CH37270). 2001.Dorigo, M., V. Maniezzo, and A. Colorni, Positive Feedback as a Search Strategy. Tech rep., 91-016, Dip Elettronica, Politecnico di Milano, Italy, 1999.Kennedy, J. and R. Eberhart. Particle swarm optimizati

13、on. in Proceedings of ICNN95 - International Conference on Neural Networks. 1995.Karaboga, D. and B. Akay, A survey: algorithms simulating bee swarm intelligence. Artificial Intelligence Review, 2009.31(1-4): p. 61-85.Karaboga, D., An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report - TR06. Technical Report, Erciyes University, 2005.Karaboga, D., et al., A comprehensive survey: artificial bee colony (ABC) algorithm and