蜂群算法基本理論

5.1蜂群算法的概述5.1.1蜂群算法的概念5.1.2蜂群算法的的開展5.1.3蜂群算法的特點5.1.4蜂群算法的分類5.2蜂群算法的根本原理5.2.1基于蜜蜂繁殖行為的蜂群算法5.2.2基于蜜蜂采蜜行為的蜂群算法5.3蜂群算法的應(yīng)用5.4蜂群算法的研究方向第5章蜂群算法根本理論1.5.1蜂群算法概述

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

5.1蜂群算法概述2.5.1.2蜂群算法的開展人工蜂群算法于2005年由土耳其學(xué)者D.Karaboga系統(tǒng)提出。萌芽階段1946年，德國生物學(xué)家K.V.Frisch破譯了蜜蜂采蜜時跳舞所蘊含的信息，并因此獲得1973年諾貝爾生理學(xué)獎。1995年，美國CornellUniversity〔康奈爾大學(xué)〕的T.D.Seeley提出蜂群的自組織模型。2001年，H.A.Abbass提出了蜜蜂婚配優(yōu)化〔MatingOptimization，MBO〕算法，用于解決可滿足性問題。2001年，P.Lucic等針對蜜蜂行為建模，并提出一種基于蜂群采蜜行為的蜜蜂系統(tǒng)〔BeeSystem，BS〕。5.1蜂群算法的概述3.5.1.2蜂群算法的開展開展階段2005年，土耳其埃爾吉耶斯大學(xué)的DervisKaraboga在T.D.Seeley蜂群自組織模型的根底上，系統(tǒng)提出了人工蜂群算法〔ArtificialBeeColony，簡稱ABC〕，并將其應(yīng)用于數(shù)值優(yōu)化領(lǐng)域。2006年又擴展到約束性數(shù)值優(yōu)化領(lǐng)域。此后，國內(nèi)外學(xué)者針對根本蜂群算法提出了多種改進算法，并應(yīng)用于不同領(lǐng)域。目前，蜂群算法的研究還處于不斷探索與改進的階段。5.1蜂群算法的概述4.5.1.3蜂群算法的特點蜂群算法的優(yōu)點①全局性：蜂群算法在搜索過程中不易陷入局部極值點，即使在非連續(xù)和含有噪聲的情況下，也能以較大概率收斂到最優(yōu)解或滿意解，具有很強的容噪能力。②并行性和高效性：蜂群算法具有大范圍全局搜索和并行性等特點，適用于并行計算，因而執(zhí)行效率高。③魯棒性：魯棒性強意味著蜂群算法的搜索以群體為根本單元，不受初始選擇的影響，不因?qū)嵗牟煌懽?；同時對于一個相同問題，在不同的屢次運行中能夠得到相同結(jié)果，在解的質(zhì)量上沒有很大差異。這已被許多數(shù)值所證實。5.1蜂群算法的概述5.④普適性和易擴性：蜂群算法是一種弱方法，它采用自然進化機制來表示復(fù)雜現(xiàn)象，對函數(shù)的形態(tài)無要求，可解決多種優(yōu)化搜索問題。針對不同實例，只需適當調(diào)整算子參數(shù)等，進行很小修改即可適應(yīng)新的問題，程序能夠通用，這是現(xiàn)行的其他大多數(shù)優(yōu)化方法所做不到的。⑤簡明性：蜂群算法的根本思想簡單明了，實現(xiàn)步驟通俗易懂。5.1蜂群算法的概述6.5.1.4蜂群算法的分類按照機理不同，蜂群算法分為兩類：受婚配行為啟發(fā)的蜜蜂婚配優(yōu)化算法，也稱為基于蜜蜂繁殖機理的蜂群算法。受采蜜行為啟發(fā)的蜜蜂采蜜優(yōu)化算法。另外，還有模擬蜂王繁殖行為的蜂王進化算法，模擬蜜蜂躲避障礙物的蜜蜂躲避算法，模擬蜂群任務(wù)分配行為的可用于效勞器動態(tài)分配的分散蜜蜂算法，等等。5.1蜂群算法的概述7.5.2蜂群算法的根本原理5.2.1基于蜜蜂繁殖行為的蜂群算法生物學(xué)機理一個完整的蜂巢一般由一只蜂王、上千的雄蜂、10000~60000工蜂和幼蜂組成。這三種蜂分工明確，各司其職。蜂王是蜂群中唯一具有生殖能力的雌蜂，主要任務(wù)是與不同的雄蜂進行交配與產(chǎn)卵；雄蜂是整個蜂群的父親和警衛(wèi)，主要任務(wù)是和蜂王交配繁殖后代；工蜂主要負責(zé)清潔、哺育、筑巢、守衛(wèi)和采蜜等各項工作。5.2蜂群算法的根本原理8.5.2蜂群算法的根本原理蜂王的求偶過程稱為婚飛。蜂王在空中起舞就標志著婚飛的開始，一群雄蜂追隨其后。蜂王選擇其中一只雄蜂進行空中交配，每次可以與7~20只雄蜂交配，直至納滿精子飛回蜂巢產(chǎn)卵。為了防止近親繁殖，蜂王有時會尋找其他蜂群的雄蜂交配。剛開始交配時，蜂王飛行速度很快，每交配一次，蜂王的飛行速度有所衰減。當蜂王衰弱到一定程度時，那么由成熟且勝任的幼蜂替代，即產(chǎn)生新一代蜂王，此時結(jié)束原蜂王的生命周期。蜂群繁殖進化過程也是蜂王不斷更新的過程，如圖5-1所示。其實，新蜂王的產(chǎn)生類似于進化計算中的一個優(yōu)化過程，蜂王是優(yōu)化過程中待求解問題的最優(yōu)解。9.5.2蜂群算法的根本原理圖5-1蜂群繁殖優(yōu)化過程示意圖10.5.2蜂群算法的基本原理

基本原理Step1：蜂群初始化。首先確定種群的大小，然后分別運用構(gòu)造啟發(fā)式算法NEH和隨機產(chǎn)生兩種方式產(chǎn)生初始種群。初始化完成后，通過比較所有的種群個體，按適應(yīng)度值從大到小排序。排第一位的個體即為蜂王Queen，其余個體為雄蜂集合Drones'set。Step2：蜂王婚飛行為。重復(fù)Step2~Step6若干次，直到產(chǎn)生的子代個體數(shù)達到種群大小。初始化蜂王的受精囊容量（）和飛行速度。蜂王的飛行速度通常通過下式隨機產(chǎn)生11.5.2蜂群算法的根本原理式中，是一個產(chǎn)生隨機數(shù)的函數(shù)，分別是初始給定的蜂王的最大、最小速度。當蜂王的速度降低到以下時那么返回蜂巢。Step3：隨機選擇一個雄峰個體，然后計算其被蜂王選擇的概率。一個雄蜂與蜂王進行交叉的概率的計算公式可為式中，分別是蜂王和雄蜂的目標函數(shù)值。Step4：在〔0，1〕之間隨機產(chǎn)生一個隨機數(shù)R，如果雄峰被選擇的概率大于該隨機數(shù)R，那么將該雄峰的遺傳信息存儲到蜂王的受精囊中，同時將該雄峰從雄蜂集合中刪除。12.5.2蜂群算法的根本原理不管雄峰的基因是否能夠存儲到蜂王的搜精囊中，蜂王的飛行速度都要按照下式降低。然后返回Step5，直到蜂王的飛行速度降低到其最低速度或者其受精囊的容量已滿。式中，，是每次蜂王速度減小的數(shù)量級。Step5：子代產(chǎn)生過程。通過對蜂王以及蜂王所存儲的雄蜂基因個體的交叉過程產(chǎn)生子代種群個體，可采用多種交叉方法來進行交叉，以使子代更好地繼承父代的有效結(jié)構(gòu)。Step6：后代培育過程。產(chǎn)生子代后，由工蜂對子代個體進行培育。13.5.2蜂群算法的根本原理Step7：將新產(chǎn)生的子代種群集合替換原有種群，根據(jù)適應(yīng)度值從大到小排列。Step8：考查算法終止條件，如果滿足，那么終止算法然后輸出所得最優(yōu)解。否那么，返回Step2。14.15.5.2.2基于蜜蜂采蜜行為的蜂群算法生物學(xué)機理一般情況下，大多數(shù)的工蜂都留在蜂巢內(nèi)值“內(nèi)勤〞，只有少數(shù)作為“偵察員〞四處尋找蜜源。一旦發(fā)現(xiàn)了有利的采蜜地點或新的優(yōu)質(zhì)蜜源植物，就會變成采集蜂，飛回蜂巢并用圓舞或搖擺舞告知其他蜜蜂。圓舞或搖擺舞是蜜蜂之間進行信息交流的一種根本形式，傳達了有關(guān)蜂巢周圍蜜源的重要信息〔如蜜源方向及離巢距離等〕。5.2蜂群算法的根本原理16.研究說明，如果偵察蜂找到的蜜源在距蜂巢100米以內(nèi)時，一般以圓舞方式爬行，即在蜂巢上交替性地向左或向右轉(zhuǎn)著小圓圈。如果超過100米，那么改變舞姿，先左右擺動腹部，沿直線蹣跚地爬行一小段距離，然后往一邊兜半個圓圈，再回到起點，繼續(xù)擺動腹部直線蹣跚爬行一小段距離，再向另一邊兜半個圓圈，呈∞字，故稱為8字舞或擺尾舞。在一定時間內(nèi)，蜜蜂跳擺尾舞數(shù)量的多少，表示蜂巢到蜜源距離的遠近；持續(xù)時間的長短反映蜜源且蜜蜂頭部的位置反映了蜜源的位置，還以附在身上的花粉味道告知蜜源的種類。5.2蜂群算法的根本原理17.5.2蜂群算法的基本原理卡爾·馮·弗里希

Karl

Ritter

von

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

18.巢中的工蜂可以通過“偵察員〞的舞蹈來判別蜜源的方向和距離，以及蜜源質(zhì)量。當舞蹈結(jié)束后，這些偵察員就與巢中的一些同伴一起飛回原先找到的蜜源進行采蜜。如果采集后，該蜜源質(zhì)量仍然很高，它們會回到蜂巢繼續(xù)通過舞蹈招募更多的同伴去采蜜。跟隨采蜜的蜜蜂數(shù)量取決于蜜源質(zhì)量。以這種方式，蜂群就能快速有效地找到高質(zhì)量的蜜源。由此可見，蜜蜂采蜜的群體智能行為是通過不同角色間的交流、轉(zhuǎn)換及協(xié)作來實現(xiàn)的。蜂群實現(xiàn)采蜜行為包括蜜源、采蜜蜂〔即偵察蜂〕與待采蜜蜂〔留在蜂巢中的內(nèi)勤蜂〕三局部。1946年，德國生物學(xué)家K.V.Frisch破譯了蜜蜂采蜜時跳舞所蘊含的信息，并因此獲得1973年諾貝爾生理學(xué)獎。5.2蜂群算法的根本原理19.5.2蜂群算法的根本原理根本原理人工蜂群算法由三局部組成：①食物源：指可獲得食物的位置，其價值取決于多種因素，如距蜂巢的遠近、包含花蜜的豐富程度以及獲取花蜜的難易程度，常用“食物濃度〞來衡量。②采蜜蜂：指已經(jīng)找到食物源的蜜蜂，又稱引領(lǐng)蜂，其與特定食物源相對應(yīng)。③待工蜂：指沒有發(fā)現(xiàn)食物源的蜜蜂，其主要任務(wù)是尋找食物源采蜜，可分為跟隨蜂和偵察蜂兩種。20.5.2蜂群算法的根本原理因此可以將蜜蜂分為三種角色：①引領(lǐng)蜂：也稱為雇傭蜂。在對應(yīng)食物源上采蜜，并通過跳搖擺舞將食物源信息分享給跟隨蜂。②跟隨蜂：在蜂巢內(nèi)等待，通過觀察采蜜歸來的引領(lǐng)蜂的搖擺舞信息選擇優(yōu)秀食物源進行跟隨。③偵察蜂：當某食物源的食物濃度連續(xù)limit次未被更新，說明該食物源陷入局部最優(yōu)，應(yīng)被放棄，與之對應(yīng)的引領(lǐng)蜂成為偵察蜂，開始尋找新的食物源。人工蜂群算法還定義了三種行為模式：搜索食物源，為食物源招募蜜蜂和放棄食物源。招募行為形成算法正反響，而放棄行為導(dǎo)致負反響。21.5.2蜂群算法的根本原理初始時刻，種群由引領(lǐng)蜂和跟隨蜂組成，引領(lǐng)蜂與跟隨蜂數(shù)量相同，都等于食物源數(shù)量。引領(lǐng)蜂首先飛出蜂巢，在對應(yīng)食物源周圍進行鄰域搜索，并利用貪婪原那么進行選擇。回到蜂巢后，引領(lǐng)蜂將食物源信息通過跳搖擺舞的形式傳遞給跟隨蜂，跟隨蜂觀察引領(lǐng)蜂的食物源信息，選擇優(yōu)秀食物源進行跟隨，并再次在其附近進行鄰域搜索和貪婪選擇。假設(shè)跟隨蜂搜索新食物源的食物濃度大于原引領(lǐng)蜂的舊食物源時，新食物源替換舊食物源，同時完成角色互換；反之，保持不變。當某個食物源的食物濃度連續(xù)limit次未被更新，該食物源應(yīng)被放棄，與之對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?，隨機尋找新食物源，找到新食物源后，偵察蜂又成為引領(lǐng)蜂，因此偵察蜂是一種臨時角色，其數(shù)量應(yīng)為1。22.5.2蜂群算法的根本原理人工蜂群算法就是通過不斷地角色轉(zhuǎn)換和執(zhí)行行為模式，最終找到最豐富食物源。在ABC算法中，引領(lǐng)蜂有保持優(yōu)良食物源的作用，具有精英特性；跟隨蜂增加較好食物源對應(yīng)的蜜蜂數(shù)，加快算法的收斂；偵察蜂隨機搜索新食物源，幫助算法跳出局部最優(yōu)。ABC算法的算法流程如圖2-1所示。利用ABC算法求解全局最大化問題時，蜜蜂采蜜與函數(shù)優(yōu)化間的對應(yīng)關(guān)系如表5-1所示。從表5-1可以看出，每個食物源代表優(yōu)化問題的一個可行解，蜜蜂尋找豐富食物源的過程對應(yīng)于優(yōu)化問題搜索優(yōu)秀解的過程，食物源的食物濃度對應(yīng)于解的質(zhì)量，即適應(yīng)度值，采蜜過程對應(yīng)于計算適應(yīng)度值的過程。23.5.2蜂群算法的根本原理24.5.3蜂群算法的應(yīng)用5.3蜂群算法的應(yīng)用目前，ABC算法的應(yīng)用研究已經(jīng)從最初的函數(shù)優(yōu)化領(lǐng)域開展到神經(jīng)網(wǎng)絡(luò)訓(xùn)練、圖像處理、無線通信、數(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)