第5章蜂群算法基本理論

第5章蜂群算法基本理論第一頁(yè)，共27頁(yè)。5.1蜂群算法概述

5.1.1蜂群算法的概念蜂群算法是一種模仿蜜蜂繁殖、采蜜等行為的新興群智能優(yōu)化算法。

5.1蜂群算法概述第二頁(yè)，共27頁(yè)。5.1.2蜂群算法的發(fā)展人工蜂群算法于2005年由土耳其學(xué)者D.Karaboga系統(tǒng)提出。萌芽階段1946年，德國(guó)生物學(xué)家K.V.Frisch破譯了蜜蜂采蜜時(shí)跳舞所蘊(yùn)含的信息，并因此獲得1973年諾貝爾生理學(xué)獎(jiǎng)。1995年，美國(guó)CornellUniversity（康奈爾大學(xué)）的T.D.Seeley提出蜂群的自組織模型。2001年，H.A.Abbass提出了蜜蜂婚配優(yōu)化（MatingOptimization，MBO）算法，用于解決可滿足性問(wèn)題。2001年，P.Lucic等針對(duì)蜜蜂行為建模，并提出一種基于蜂群采蜜行為的蜜蜂系統(tǒng)（BeeSystem，BS）。5.1蜂群算法的概述第三頁(yè)，共27頁(yè)。5.1.2蜂群算法的發(fā)展發(fā)展階段2005年，土耳其埃爾吉耶斯大學(xué)的DervisKaraboga在T.D.Seeley蜂群自組織模型的基礎(chǔ)上，系統(tǒng)提出了人工蜂群算法（ArtificialBeeColony，簡(jiǎn)稱ABC），并將其應(yīng)用于數(shù)值優(yōu)化領(lǐng)域。2006年又?jǐn)U展到約束性數(shù)值優(yōu)化領(lǐng)域。此后，國(guó)內(nèi)外學(xué)者針對(duì)基本蜂群算法提出了多種改進(jìn)算法，并應(yīng)用于不同領(lǐng)域。目前，蜂群算法的研究還處于不斷探索與改進(jìn)的階段。5.1蜂群算法的概述第四頁(yè)，共27頁(yè)。5.1.3蜂群算法的特點(diǎn)

蜂群算法的優(yōu)點(diǎn)①全局性：蜂群算法在搜索過(guò)程中不易陷入局部極值點(diǎn)，即使在非連續(xù)和含有噪聲的情況下，也能以較大概率收斂到最優(yōu)解或滿意解，具有很強(qiáng)的容噪能力。②并行性和高效性：蜂群算法具有大范圍全局搜索和并行性等特點(diǎn)，適用于并行計(jì)算，因而執(zhí)行效率高。③魯棒性：魯棒性強(qiáng)意味著蜂群算法的搜索以群體為基本單元，不受初始選擇的影響，不因?qū)嵗牟煌懽?；同時(shí)對(duì)于一個(gè)相同問(wèn)題，在不同的多次運(yùn)行中能夠得到相同結(jié)果，在解的質(zhì)量上沒(méi)有很大差異。這已被許多數(shù)值所證實(shí)。5.1蜂群算法的概述第五頁(yè)，共27頁(yè)。④普適性和易擴(kuò)性：蜂群算法是一種弱方法，它采用自然進(jìn)化機(jī)制來(lái)表示復(fù)雜現(xiàn)象，對(duì)函數(shù)的形態(tài)無(wú)要求，可解決多種優(yōu)化搜索問(wèn)題。針對(duì)不同實(shí)例，只需適當(dāng)調(diào)整算子參數(shù)等，進(jìn)行很小修改即可適應(yīng)新的問(wèn)題，程序能夠通用，這是現(xiàn)行的其他大多數(shù)優(yōu)化方法所做不到的。⑤簡(jiǎn)明性：蜂群算法的基本思想簡(jiǎn)單明了，實(shí)現(xiàn)步驟通俗易懂。5.1蜂群算法的概述第六頁(yè)，共27頁(yè)。5.1.4蜂群算法的分類按照機(jī)理不同，蜂群算法分為兩類：受婚配行為啟發(fā)的蜜蜂婚配優(yōu)化算法，也稱為基于蜜蜂繁殖機(jī)理的蜂群算法。

受采蜜行為啟發(fā)的蜜蜂采蜜優(yōu)化算法。另外，還有模擬蜂王繁殖行為的蜂王進(jìn)化算法，模擬蜜蜂躲避障礙物的蜜蜂躲避算法，模擬蜂群任務(wù)分配行為的可用于服務(wù)器動(dòng)態(tài)分配的分散蜜蜂算法，等等。5.1蜂群算法的概述第七頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理

5.2.1基于蜜蜂繁殖行為的蜂群算法

生物學(xué)機(jī)理

一個(gè)完整的蜂巢一般由一只蜂王、上千的雄蜂、10000~60000工蜂和幼蜂組成。這三種蜂分工明確，各司其職。蜂王是蜂群中唯一具有生殖能力的雌蜂，主要任務(wù)是與不同的雄蜂進(jìn)行交配與產(chǎn)卵；雄蜂是整個(gè)蜂群的父親和警衛(wèi)，主要任務(wù)是和蜂王交配繁殖后代；工蜂主要負(fù)責(zé)清潔、哺育、筑巢、守衛(wèi)和采蜜等各項(xiàng)工作。5.2蜂群算法的基本原理第八頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理蜂王的求偶過(guò)程稱為婚飛。蜂王在空中起舞就標(biāo)志著婚飛的開(kāi)始，一群雄蜂追隨其后。蜂王選擇其中一只雄蜂進(jìn)行空中交配，每次可以與7~20只雄蜂交配，直至納滿精子飛回蜂巢產(chǎn)卵。為了避免近親繁殖，蜂王有時(shí)會(huì)尋找其他蜂群的雄蜂交配。剛開(kāi)始交配時(shí)，蜂王飛行速度很快，每交配一次，蜂王的飛行速度有所衰減。當(dāng)蜂王衰弱到一定程度時(shí)，則由成熟且勝任的幼蜂替代，即產(chǎn)生新一代蜂王，此時(shí)結(jié)束原蜂王的生命周期。蜂群繁殖進(jìn)化過(guò)程也是蜂王不斷更新的過(guò)程，如圖5-1所示。其實(shí)，新蜂王的產(chǎn)生類似于進(jìn)化計(jì)算中的一個(gè)優(yōu)化過(guò)程，蜂王是優(yōu)化過(guò)程中待求解問(wèn)題的最優(yōu)解。第九頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理圖5-1蜂群繁殖優(yōu)化過(guò)程示意圖第十頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理基本原理Step1：蜂群初始化。首先確定種群的大小，然后分別運(yùn)用構(gòu)造啟發(fā)式算法NEH和隨機(jī)產(chǎn)生兩種方式產(chǎn)生初始種群。初始化完成后，通過(guò)比較所有的種群個(gè)體，按適應(yīng)度值從大到小排序。排第一位的個(gè)體即為蜂王Queen，其余個(gè)體為雄蜂集合Drones'set。Step2：蜂王婚飛行為。重復(fù)Step2~Step6若干次，直到產(chǎn)生的子代個(gè)體數(shù)達(dá)到種群大小。初始化蜂王的受精囊容量（）和飛行速度。蜂王的飛行速度通常通過(guò)下式隨機(jī)產(chǎn)生第十一頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理式中，是一個(gè)產(chǎn)生隨機(jī)數(shù)的函數(shù)，分別是初始給定的蜂王的最大、最小速度。當(dāng)蜂王的速度降低到以下時(shí)則返回蜂巢。

Step3：隨機(jī)選擇一個(gè)雄峰個(gè)體，然后計(jì)算其被蜂王選擇的概率。一個(gè)雄蜂與蜂王進(jìn)行交叉的概率的計(jì)算公式可為式中，分別是蜂王和雄蜂的目標(biāo)函數(shù)值。

Step4：在（0，1）之間隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)R，如果雄峰被選擇的概率大于該隨機(jī)數(shù)R，則將該雄峰的遺傳信息存儲(chǔ)到蜂王的受精囊中，同時(shí)將該雄峰從雄蜂集合中刪除。第十二頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理不管雄峰的基因是否能夠存儲(chǔ)到蜂王的搜精囊中，蜂王的飛行速度都要按照下式降低。然后返回Step5，直到蜂王的飛行速度降低到其最低速度或者其受精囊的容量已滿。式中，，是每次蜂王速度減小的數(shù)量級(jí)。Step5：子代產(chǎn)生過(guò)程。通過(guò)對(duì)蜂王以及蜂王所存儲(chǔ)的雄蜂基因個(gè)體的交叉過(guò)程產(chǎn)生子代種群個(gè)體，可采用多種交叉方法來(lái)進(jìn)行交叉，以使子代更好地繼承父代的有效結(jié)構(gòu)。Step6：后代培育過(guò)程。產(chǎn)生子代后，由工蜂對(duì)子代個(gè)體進(jìn)行培育。第十三頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理Step7：將新產(chǎn)生的子代種群集合替換原有種群，根據(jù)適應(yīng)度值從大到小排列。

Step8：考查算法終止條件，如果滿足，則終止算法然后輸出所得最優(yōu)解。否則，返回Step2。第十四頁(yè)，共27頁(yè)。第十五頁(yè)，共27頁(yè)。5.2.2基于蜜蜂采蜜行為的蜂群算法

生物學(xué)機(jī)理一般情況下，大多數(shù)的工蜂都留在蜂巢內(nèi)值“內(nèi)勤”，只有少數(shù)作為“偵察員”四處尋找蜜源。一旦發(fā)現(xiàn)了有利的采蜜地點(diǎn)或新的優(yōu)質(zhì)蜜源植物，就會(huì)變成采集蜂，飛回蜂巢并用圓舞或搖擺舞告知其他蜜蜂。圓舞或搖擺舞是蜜蜂之間進(jìn)行信息交流的一種基本形式，傳達(dá)了有關(guān)蜂巢周圍蜜源的重要信息（如蜜源方向及離巢距離等）。5.2蜂群算法的基本原理第十六頁(yè)，共27頁(yè)。研究表明，如果偵察蜂找到的蜜源在距蜂巢100米以內(nèi)時(shí)，一般以圓舞方式爬行，即在蜂巢上交替性地向左或向右轉(zhuǎn)著小圓圈。如果超過(guò)100米，則改變舞姿，先左右擺動(dòng)腹部，沿直線蹣跚地爬行一小段距離，然后往一邊兜半個(gè)圓圈，再回到起點(diǎn)，繼續(xù)擺動(dòng)腹部直線蹣跚爬行一小段距離，再向另一邊兜半個(gè)圓圈，呈∞字，故稱為8字舞或擺尾舞。在一定時(shí)間內(nèi)，蜜蜂跳擺尾舞數(shù)量的多少，表示蜂巢到蜜源距離的遠(yuǎn)近；持續(xù)時(shí)間的長(zhǎng)短反映蜜源且蜜蜂頭部的位置反映了蜜源的位置，還以附在身上的花粉味道告知蜜源的種類。5.2蜂群算法的基本原理第十七頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理卡爾·馮·弗里希

Karl

Ritter

von

Frisch1886.11.20~1982.06.12德國(guó)動(dòng)物學(xué)家，行為生態(tài)學(xué)創(chuàng)始人，出生于奧地利維也納，逝于德國(guó)慕尼黑。1973年獲得諾貝爾生理學(xué)或醫(yī)學(xué)獎(jiǎng)

第十八頁(yè)，共27頁(yè)。巢中的工蜂可以通過(guò)“偵察員”的舞蹈來(lái)判別蜜源的方向和距離，以及蜜源質(zhì)量。當(dāng)舞蹈結(jié)束后，這些偵察員就與巢中的一些同伴一起飛回原先找到的蜜源進(jìn)行采蜜。如果采集后，該蜜源質(zhì)量仍然很高，它們會(huì)回到蜂巢繼續(xù)通過(guò)舞蹈招募更多的同伴去采蜜。跟隨采蜜的蜜蜂數(shù)量取決于蜜源質(zhì)量。以這種方式，蜂群就能快速有效地找到高質(zhì)量的蜜源。由此可見(jiàn)，蜜蜂采蜜的群體智能行為是通過(guò)不同角色間的交流、轉(zhuǎn)換及協(xié)作來(lái)實(shí)現(xiàn)的。蜂群實(shí)現(xiàn)采蜜行為包括蜜源、采蜜蜂（即偵察蜂）與待采蜜蜂（留在蜂巢中的內(nèi)勤蜂）三部分。1946年，德國(guó)生物學(xué)家K.V.Frisch破譯了蜜蜂采蜜時(shí)跳舞所蘊(yùn)含的信息，并因此獲得1973年諾貝爾生理學(xué)獎(jiǎng)。5.2蜂群算法的基本原理第十九頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理基本原理

人工蜂群算法由三部分組成：①食物源：指可獲得食物的位置，其價(jià)值取決于多種因素，如距蜂巢的遠(yuǎn)近、包含花蜜的豐富程度以及獲取花蜜的難易程度，常用“食物濃度”來(lái)衡量。②采蜜蜂：指已經(jīng)找到食物源的蜜蜂，又稱引領(lǐng)蜂，其與特定食物源相對(duì)應(yīng)。③待工蜂：指沒(méi)有發(fā)現(xiàn)食物源的蜜蜂，其主要任務(wù)是尋找食物源采蜜，可分為跟隨蜂和偵察蜂兩種。第二十頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理因此可以將蜜蜂分為三種角色：

①引領(lǐng)蜂：也稱為雇傭蜂。在對(duì)應(yīng)食物源上采蜜，并通過(guò)跳搖擺舞將食物源信息分享給跟隨蜂。

②跟隨蜂：在蜂巢內(nèi)等待，通過(guò)觀察采蜜歸來(lái)的引領(lǐng)蜂的搖擺舞信息選擇優(yōu)秀食物源進(jìn)行跟隨。

③偵察蜂：當(dāng)某食物源的食物濃度連續(xù)limit次未被更新，表明該食物源陷入局部最優(yōu)，應(yīng)被放棄，與之對(duì)應(yīng)的引領(lǐng)蜂成為偵察蜂，開(kāi)始尋找新的食物源。人工蜂群算法還定義了三種行為模式：搜索食物源，為食物源招募蜜蜂和放棄食物源。招募行為形成算法正反饋，而放棄行為導(dǎo)致負(fù)反饋。第二十一頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理初始時(shí)刻，種群由引領(lǐng)蜂和跟隨蜂組成，引領(lǐng)蜂與跟隨蜂數(shù)量相同，都等于食物源數(shù)量。引領(lǐng)蜂首先飛出蜂巢，在對(duì)應(yīng)食物源周圍進(jìn)行鄰域搜索，并利用貪婪原則進(jìn)行選擇?；氐椒涑埠螅I(lǐng)蜂將食物源信息通過(guò)跳搖擺舞的形式傳遞給跟隨蜂，跟隨蜂觀察引領(lǐng)蜂的食物源信息，選擇優(yōu)秀食物源進(jìn)行跟隨，并再次在其附近進(jìn)行鄰域搜索和貪婪選擇。若跟隨蜂搜索新食物源的食物濃度大于原引領(lǐng)蜂的舊食物源時(shí)，新食物源替換舊食物源，同時(shí)完成角色互換；反之，保持不變。當(dāng)某個(gè)食物源的食物濃度連續(xù)limit次未被更新，該食物源應(yīng)被放棄，與之對(duì)應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?，隨機(jī)尋找新食物源，找到新食物源后，偵察蜂又成為引領(lǐng)蜂，因此偵察蜂是一種臨時(shí)角色，其數(shù)量應(yīng)為1。第二十二頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理人工蜂群算法就是通過(guò)不斷地角色轉(zhuǎn)換和執(zhí)行行為模式，最終找到最豐富食物源。在ABC算法中，引領(lǐng)蜂有保持優(yōu)良食物源的作用，具有精英特性；跟隨蜂增加較好食物源對(duì)應(yīng)的蜜蜂數(shù)，加快算法的收斂；偵察蜂隨機(jī)搜索新食物源，幫助算法跳出局部最優(yōu)。ABC算法的算法流程如圖2-1所示。利用ABC算法求解全局最大化問(wèn)題時(shí)，蜜蜂采蜜與函數(shù)優(yōu)化間的對(duì)應(yīng)關(guān)系如表5-1所示。從表5-1可以看出，每個(gè)食物源代表優(yōu)化問(wèn)題的一個(gè)可行解，蜜蜂尋找豐富食物源的過(guò)程對(duì)應(yīng)于優(yōu)化問(wèn)題搜索優(yōu)秀解的過(guò)程，食物源的食物濃度對(duì)應(yīng)于解的質(zhì)量，即適應(yīng)度值，采蜜過(guò)程對(duì)應(yīng)于計(jì)算適應(yīng)度值的過(guò)程。第二十三頁(yè)，共27頁(yè)。5.2蜂群算法的基本原理第二十四頁(yè)，共27頁(yè)。5.3蜂群算法的應(yīng)用5.3蜂群算法的應(yīng)用

目前，ABC算法的應(yīng)用研究已經(jīng)從最初的函數(shù)優(yōu)化領(lǐng)域發(fā)展到神經(jīng)網(wǎng)絡(luò)訓(xùn)練、圖像處理、無(wú)線通信、數(shù)據(jù)挖掘、組合優(yōu)化、電子學(xué)、軟件和控制工程等領(lǐng)域。

5.3.1在神經(jīng)網(wǎng)絡(luò)訓(xùn)練中的應(yīng)用人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練是一種尋找最佳權(quán)矢量集的優(yōu)化過(guò)程。為了克服傳統(tǒng)訓(xùn)練算法收斂速度緩慢且易陷入局部最優(yōu)的缺點(diǎn)，具有較強(qiáng)全局尋優(yōu)能力的各種智能算法，如粒子群、蟻群等都被嘗試用于人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練中。ABC算法在尋找最優(yōu)解方面具有良好的探索和開(kāi)采能力，已被廣泛用于神