人工蜂群算法詳解-ppt課件(PPT 22頁(yè))

1、人工蜂群算法（Artificial Bee Colony，ABC） 第1頁(yè)，共22頁(yè)。蜂群算法簡(jiǎn)介人工蜂群算法是模仿蜜蜂行為提出的一種優(yōu)化方法，是集群智能思想的一個(gè)具體應(yīng)用。主要特點(diǎn)是不需要了解問(wèn)題的特殊信息，只需要對(duì)問(wèn)題進(jìn)行優(yōu)劣的比較，通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來(lái)，有著較快的收斂速度。為了解決多變量函數(shù)優(yōu)化問(wèn)題，Karaboga在2005年提出了人工蜂群算法ABC模型（artificial bee colony algorithm）。 第2頁(yè)，共22頁(yè)。一 、蜜蜂采蜜機(jī)理蜜蜂是一種群居昆蟲(chóng)，雖然單個(gè)昆蟲(chóng)的行為極其簡(jiǎn)單，但是由單個(gè)簡(jiǎn)單的個(gè)體所組成的群體卻表現(xiàn)

2、出極其復(fù)雜的行為。真實(shí)的蜜蜂種群能夠在任何環(huán)境下，以極高的效率從食物源（花朵）中采集花蜜；同時(shí)，它們能適應(yīng)環(huán)境的改變。第3頁(yè)，共22頁(yè)。蜂群產(chǎn)生群體智慧的最小搜索模型包含基本的三個(gè)組成要素：食物源、被雇傭的蜜蜂（employed foragers）和未被雇傭的蜜蜂（unemployed foragers）；兩種最為基本的行為模型：為食物源招募（recruit）蜜蜂和放棄（abandon）某個(gè)食物源。 一 、蜜蜂采蜜機(jī)理(1)食物源：食物源的價(jià)值由多方面的因素決定，如：它離蜂巢的遠(yuǎn)近，包含花蜜的豐富程度和獲得花蜜的難易程度。使用單一的參數(shù)，食物源的“收益率”（profitability），來(lái)代表

3、以上各個(gè)因素。 (2)被雇用的蜜蜂：也稱引領(lǐng)蜂（Leader），其與所采集的食物源一一對(duì)應(yīng)。引領(lǐng)蜂儲(chǔ)存有某一個(gè)食物源的相關(guān)信息（相對(duì)于蜂巢的距離、方向、食物源的豐富程度等）并且將這些信息以一定的概率與其他蜜蜂分享。 第4頁(yè)，共22頁(yè)。(3)未被雇用的蜜蜂：其主要任務(wù)是尋找和開(kāi)采食物源。有兩種未被雇用的蜜蜂：偵查蜂（Scouter）和跟隨蜂（Follower）。偵察蜂搜索蜂巢附近的新食物源；跟隨蜂等在蜂巢里面并通過(guò)與引領(lǐng)蜂分享相關(guān)信息找到食物源。一般情況下，偵察蜂的平均數(shù)目是蜂群的5%-20%。一 、蜜蜂采蜜機(jī)理（4）舞蹈區(qū)：在群體智慧的形成過(guò)程中，蜜蜂間交換信息是最為重要的一環(huán)。舞蹈區(qū)是蜂巢中

4、最為重要的信息交換地。蜜蜂的舞蹈叫做搖擺舞。食物源的信息在舞蹈區(qū)通過(guò)搖擺舞的形式與其他蜜蜂共享，引領(lǐng)蜂通過(guò)搖擺舞的持續(xù)時(shí)間等來(lái)表現(xiàn)食物源的收益率，故跟隨蜂可以觀察到大量的舞蹈并依據(jù)收益率來(lái)選擇到哪個(gè)食物源采蜜。收益率與食物源被選擇的可能性成正比。因而，蜜蜂被招募到某一個(gè)食物源的概率與食物源的收益率成正比。第5頁(yè)，共22頁(yè)。初始時(shí)刻，蜜蜂以偵察蜂的身份搜索。其搜索可以由系統(tǒng)提供的先驗(yàn)知識(shí)決定，也可以完全隨機(jī)。經(jīng)過(guò)一輪偵查后，若蜜蜂找到食物源，蜜蜂利用它本身的存儲(chǔ)能力記錄位置信息并開(kāi)始采蜜。此時(shí)，蜜蜂將成為“被雇用者”。蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜然后將有如下選擇： (1)放棄食物源而成為非

5、雇傭蜂。 (2)跳搖擺舞為所對(duì)應(yīng)的食物源招募更多的蜜蜂，然后回到食物源采蜜。 (3)繼續(xù)在同一個(gè)食物源采蜜而不進(jìn)行招募。 對(duì)于非雇傭蜂有如下選擇： (1)轉(zhuǎn)變成為偵察蜂并搜索蜂巢附近的食物源。其搜索可以由先驗(yàn)知識(shí)決定，也可以完全隨機(jī)。 (2)在觀察完搖擺舞后被雇用成為跟隨蜂，開(kāi)始搜索對(duì)應(yīng)食物源鄰域并采蜜。 二、蜜蜂采蜜過(guò)程第6頁(yè)，共22頁(yè)。三、ABC算法原理在基本ABC算法中，人工蜂群包含3種個(gè)體：雇傭蜂、觀察蜂和偵查蜂。每個(gè)雇傭蜂對(duì)應(yīng)一個(gè)確定的食物源（解向量）并在迭代中對(duì)蜜源的鄰域進(jìn)行搜索。根據(jù)蜜源豐富程度（適應(yīng)值的大?。┎捎幂啽P賭的方式雇傭觀察蜂采蜜（搜索新蜜源）如果蜜源多次更新沒(méi)有改進(jìn)，

6、則放棄該蜜源，雇傭蜂轉(zhuǎn)為偵查蜂隨機(jī)搜索新蜜源。 第7頁(yè)，共22頁(yè)。1.蜜源初始化初始化時(shí)，隨機(jī)生成SN個(gè)可行解（等于雇傭蜂的數(shù)量）并計(jì)算適應(yīng)度函數(shù)值。隨機(jī)產(chǎn)生可行解的公式如下： (1) 式中，xi(i=1, 2, . . . , SN)為D維向量，D為優(yōu)化參數(shù)的個(gè)數(shù)，j 1, 2, , D。2. 新蜜源的更新搜索公式蜜蜂記錄自己到目前為止的最優(yōu)值，并在當(dāng)前蜜源鄰域內(nèi)展開(kāi)搜索，基本ABC在蜜源附近搜索新蜜源的公式為: （2） 式中，j 1, 2, , D ，k 1, 2, , SN ，k為隨機(jī)生成且ki，ik 為 - 1, 1之間的隨機(jī)數(shù)。第8頁(yè)，共22頁(yè)。3. 觀察蜂選擇雇傭蜂的概率 式中，f

7、it(xi)為第i個(gè)解的適應(yīng)值對(duì)應(yīng)蜜源的豐富程度。蜜源越豐富，被觀察蜂選擇的概率越大。4. 偵察蜂的產(chǎn)生 為防止算法陷入局部最優(yōu)，當(dāng)某蜜源迭代limit次沒(méi)有改進(jìn)時(shí)，便放棄該蜜源, 并且將該蜜源記錄在禁忌表中,同時(shí)該蜜源對(duì)應(yīng)的雇用蜂轉(zhuǎn)變?yōu)閭刹旆浒词?1)隨機(jī)產(chǎn)生一個(gè)新的位置代替原蜜源。第9頁(yè)，共22頁(yè)。四、基本ABC算法的流程1: 根據(jù)式(1)初始化種群解xi，i =1,SN2: 計(jì)算種群中各個(gè)蜜蜂的適應(yīng)值3: cycle = 14: repeat5: 雇傭蜂根據(jù)(2)產(chǎn)生新的解vi 并計(jì)算適應(yīng)值6: 雇傭蜂根據(jù)貪心策略選擇蜜源7: 根據(jù)(3)式計(jì)算選擇蜜源xi的概率Pi 8: 觀察蜂根據(jù)概率

8、Pi選擇蜜源xi，根據(jù)(2)式在該蜜源附近產(chǎn)生新的蜜源vi ，并計(jì)算新蜜源vi的適應(yīng)值9: 觀察蜂根據(jù)貪心策略選擇蜜源10: 決定是否存在需要放棄的蜜源，如果存在，根據(jù)(1)式隨機(jī)產(chǎn)生一個(gè)蜜源替代它11: 記錄最優(yōu)解12: cycle = cycle + 113: until cycle = MCN第10頁(yè)，共22頁(yè)。 所有城市的任一種排列即是問(wèn)題的一個(gè)解，解空間由若干解構(gòu)成，因此初始化解空間就是隨機(jī)產(chǎn)生多個(gè)不同的城市序列。以n個(gè)城市為例，從1到n對(duì)其進(jìn)行編號(hào)，那么完成一次旅行的路徑就用1到n的一個(gè)排列組合來(lái)表示。 在人工蜂群算法中，每一個(gè)引領(lǐng)蜂或者跟隨蜂的位置就對(duì)應(yīng)一個(gè)路徑的組合，食物源的豐

9、富程度對(duì)應(yīng)這條路徑的長(zhǎng)度，用適應(yīng)度函數(shù)值來(lái)描述食物源的豐富程度，也就是說(shuō)，適應(yīng)度函數(shù)值越小的引領(lǐng)蜂或者跟隨蜂所在的位置，所代表的路徑也最優(yōu)。五、人工蜂群算法解TSP的實(shí)現(xiàn)第11頁(yè)，共22頁(yè)。算法實(shí)現(xiàn)TSP問(wèn)題與蜂群采蜜行為對(duì)應(yīng)關(guān)系第12頁(yè)，共22頁(yè)。更新策略 實(shí)現(xiàn)TSP問(wèn)題的算法中存在兩級(jí)因子,即引領(lǐng)因子及轉(zhuǎn)移因子. 引領(lǐng)因子是指通過(guò)上一級(jí)引領(lǐng)路徑直接確定的城市之間引領(lǐng)強(qiáng)度的大??； 轉(zhuǎn)移因子是指蜜蜂從城市i到城市j的轉(zhuǎn)移強(qiáng)度,與引領(lǐng)因子及更新策略有關(guān),而轉(zhuǎn)移因子歸一化后,又可以求出相應(yīng)兩個(gè)城市的轉(zhuǎn)移概率算法實(shí)現(xiàn)第13頁(yè)，共22頁(yè)。下一步選擇的城市可以表示為： Ak=1,2, ,n- Tk其中A

10、k表示蜜蜂k下一步可以選擇的城市,Tk表示以記錄蜜蜂k本代所走過(guò)的城市,Tk隨蜜蜂不斷選擇下一個(gè)城市而做動(dòng)態(tài)調(diào)整.進(jìn)化代數(shù)N每增加一次,各條路徑上的轉(zhuǎn)移因子就要清零一次,保證轉(zhuǎn)移因子沒(méi)有遺留歷史信息,而僅僅是根據(jù)本代路徑信息更新.所有蜜蜂完成一次迭代循環(huán),各路徑上轉(zhuǎn)移因子根據(jù)式(1)(2)(3)作調(diào)整.然后,對(duì)所有路徑長(zhǎng)度排序,得到引領(lǐng)路徑矩陣LR.最后采用2級(jí)更新策略.更新策略算法實(shí)現(xiàn)第14頁(yè)，共22頁(yè)。 第1級(jí):引領(lǐng)因子更新策略引領(lǐng)路徑的選擇有3種方式:取長(zhǎng)度最短的路徑為引領(lǐng)路徑;取長(zhǎng)度前位(或%為引領(lǐng)路徑);上代全部蜜蜂走過(guò)的路徑為引領(lǐng)路徑.更新策略算法實(shí)現(xiàn)第15頁(yè)，共22頁(yè)。更新策略式

11、中:N為進(jìn)化代數(shù);LR(N)表示第N代路徑長(zhǎng)度排序后得到的引領(lǐng)路徑矩陣;gm表示蜂群中蜜蜂總數(shù);ij表示第k只蜜蜂在第N次迭代循環(huán)中留在路徑ij上的引領(lǐng)因子。算法實(shí)現(xiàn)第16頁(yè)，共22頁(yè)。更新策略 ABC算法提供了3種不同模型,分別為Bcs, Bqs, Bds,它們的差別在于引領(lǐng)因子kij的計(jì)算表達(dá)式不同.上述三種模型中,后兩者利用的是局部信息,而前者利用的是整體信息.其中:Q為引領(lǐng)常數(shù);Lk為第k只蜜蜂在本次迭代中所走過(guò)路徑的長(zhǎng)度;dij表示第i個(gè)城市到第j個(gè)城市的距離.算法實(shí)現(xiàn)第17頁(yè)，共22頁(yè)。更新策略 第2級(jí):轉(zhuǎn)移因子動(dòng)態(tài)更新策略轉(zhuǎn)移因子更新,人工蜜蜂根據(jù)當(dāng)前允許選擇的城市及上一代建立的

12、引領(lǐng)路徑矩陣,動(dòng)態(tài)確定每個(gè)待選城市的轉(zhuǎn)移因子轉(zhuǎn)移因子動(dòng)態(tài)更新公式為算法實(shí)現(xiàn)第18頁(yè)，共22頁(yè)。更新策略 式中:kij為第k只蜜蜂從城市i到城市j的轉(zhuǎn)移因子;為除引領(lǐng)蜂走過(guò)的路徑外,可選城市的總數(shù);為轉(zhuǎn)移強(qiáng)度;為可選城市總數(shù); 當(dāng)可選路徑中不含引領(lǐng)蜂走過(guò)的路徑時(shí),轉(zhuǎn)移因子取/,其中,當(dāng)可選路徑中含引領(lǐng)蜂走過(guò)的路徑且為引領(lǐng)蜂走過(guò)的路徑時(shí),轉(zhuǎn)移因子等于ij,若選其它路徑,則轉(zhuǎn)移因子為算法實(shí)現(xiàn)第19頁(yè)，共22頁(yè)。更新策略蜂群算法的狀態(tài)轉(zhuǎn)移策略 設(shè)蜂群中蜜蜂總數(shù)為gm,偵察蜜蜂數(shù)為sm,跟隨蜜蜂數(shù)fm,則有g(shù)m=sm+ fm.其中sm取總數(shù)的1/c左右,c為常數(shù),取值小于10,以保證算法收斂.在從城市i

13、轉(zhuǎn)移到城市j的過(guò)程中,引領(lǐng)蜂完全重走上一次的路徑.跟隨蜂和偵察蜂依據(jù)下式計(jì)算在第N代第k只蜜蜂節(jié)點(diǎn)轉(zhuǎn)移的概率.狀態(tài)轉(zhuǎn)移公式為算法實(shí)現(xiàn)第20頁(yè)，共22頁(yè)。更新策略 式中對(duì)于引領(lǐng)蜂,完全重走上次的路徑,概率等于1.對(duì)于跟隨蜂,根據(jù)轉(zhuǎn)移因子大小依概率選擇路徑,啟發(fā)式因子ij= 1/ dij,dij(i,j= 1,2, ,n)為城市i和城市j之間的歐式距離;為表示轉(zhuǎn)移因子ij重要程度的參數(shù);為表示啟發(fā)式因子ij重要程度的參數(shù);BS,BF,BL分別為偵察蜂、跟隨蜂及引領(lǐng)蜂集合. 對(duì)于偵察蜂,t是允許路徑集中,可以選擇城市的總數(shù),構(gòu)造累加集序列Psum,累加集序列位置代表城市標(biāo)號(hào),通過(guò)計(jì)算機(jī)產(chǎn)生(0,1)之間的隨機(jī)數(shù),并由此確定在Psum的位置,最終確定選擇城市.此外,c可以隨著進(jìn)化代數(shù)動(dòng)態(tài)調(diào)整:起初,為了增加解的多樣性,可適當(dāng)增大c,隨著迭代次數(shù)的增加,為了加速并保證收斂,可適當(dāng)減小c.算法實(shí)現(xiàn)第21頁(yè)，共22頁(yè)。更新策略 跟隨蜂根據(jù)轉(zhuǎn)移