群體智能優(yōu)化算法

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

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

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

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

5、段觀察蜂階段記憶當(dāng)前獲得的最優(yōu)解偵查蜂階段until達(dá)到終止標(biāo)準(zhǔn)算法1： ABC算法的主要步驟在初始化階段，使用下式隨機(jī)初始化食物源種群：列. = w嚴(yán)+ 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)將一直 迭代至終止準(zhǔn)則滿足。終止準(zhǔn)則可以是達(dá)到最大評估次數(shù)，也可以是找到一個可接受的 函數(shù)值。在雇傭蜂階段，通過在食物源的領(lǐng)域內(nèi)進(jìn)行局

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

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

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

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

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

11、選擇if新解適應(yīng)度由于原有解then用新解替換原有解；else原有解試驗(yàn)次數(shù)加1；endend記憶當(dāng)前獲得的最優(yōu)解;偵查蜂階段找出試驗(yàn)次數(shù)最大的解，超過limit則根據(jù)式(1)重新初始化；cycle+；endend算法2參考文獻(xiàn)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