人工蜂群算法詳解

人工蜂群算法（ArtificialBeeColony，ABC）

人工蜂群算法詳解蜂群算法簡介人工蜂群算法是模仿蜜蜂行為提出的一種優(yōu)化方法，是集群智能思想的一個具體應用。主要特點是不需要了解問題的特殊信息，只需要對問題進行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來，有著較快的收斂速度。為了解決多變量函數(shù)優(yōu)化問題，Karaboga在2005年提出了人工蜂群算法ABC模型（artificialbeecolonyalgorithm）。

人工蜂群算法詳解一、蜜蜂采蜜機理蜜蜂是一種群居昆蟲，雖然單個昆蟲的行為極其簡單，但是由單個簡單的個體所組成的群體卻表現(xiàn)出極其復雜的行為。真實的蜜蜂種群能夠在任何環(huán)境下，以極高的效率從食物源（花朵）中采集花蜜；同時，它們能適應環(huán)境的改變。人工蜂群算法詳解蜂群產(chǎn)生群體智慧的最小搜索模型包含基本的三個組成要素：食物源、被雇傭的蜜蜂（employedforagers）和未被雇傭的蜜蜂（unemployedforagers）；兩種最為基本的行為模型：為食物源招募（recruit）蜜蜂和放棄（abandon）某個食物源。一、蜜蜂采蜜機理(1)食物源：食物源的價值由多方面的因素決定，如：它離蜂巢的遠近，包含花蜜的豐富程度和獲得花蜜的難易程度。使用單一的參數(shù)，食物源的“收益率”（profitability），來代表以上各個因素。

(2)被雇用的蜜蜂：也稱引領蜂（Leader），其與所采集的食物源一一對應。引領蜂儲存有某一個食物源的相關信息（相對于蜂巢的距離、方向、食物源的豐富程度等）并且將這些信息以一定的概率與其他蜜蜂分享。人工蜂群算法詳解(3)未被雇用的蜜蜂：其主要任務是尋找和開采食物源。有兩種未被雇用的蜜蜂：偵查蜂（Scouter）和跟隨蜂（Follower）。偵察蜂搜索蜂巢附近的新食物源；跟隨蜂等在蜂巢里面并通過與引領蜂分享相關信息找到食物源。一般情況下，偵察蜂的平均數(shù)目是蜂群的5%-20%。一、蜜蜂采蜜機理（4）舞蹈區(qū)：在群體智慧的形成過程中，蜜蜂間交換信息是最為重要的一環(huán)。舞蹈區(qū)是蜂巢中最為重要的信息交換地。蜜蜂的舞蹈叫做搖擺舞。食物源的信息在舞蹈區(qū)通過搖擺舞的形式與其他蜜蜂共享，引領蜂通過搖擺舞的持續(xù)時間等來表現(xiàn)食物源的收益率，故跟隨蜂可以觀察到大量的舞蹈并依據(jù)收益率來選擇到哪個食物源采蜜。收益率與食物源被選擇的可能性成正比。因而，蜜蜂被招募到某一個食物源的概率與食物源的收益率成正比。人工蜂群算法詳解初始時刻，蜜蜂以偵察蜂的身份搜索。其搜索可以由系統(tǒng)提供的先驗知識決定，也可以完全隨機。經(jīng)過一輪偵查后，若蜜蜂找到食物源，蜜蜂利用它本身的存儲能力記錄位置信息并開始采蜜。此時，蜜蜂將成為“被雇用者”。蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜然后將有如下選擇：

(1)放棄食物源而成為非雇傭蜂。

(2)跳搖擺舞為所對應的食物源招募更多的蜜蜂，然后回到食物源采蜜。

(3)繼續(xù)在同一個食物源采蜜而不進行招募。對于非雇傭蜂有如下選擇：

(1)轉變成為偵察蜂并搜索蜂巢附近的食物源。其搜索可以由先驗知識決定，也可以完全隨機。

(2)在觀察完搖擺舞后被雇用成為跟隨蜂，開始搜索對應食物源鄰域并采蜜。

二、蜜蜂采蜜過程人工蜂群算法詳解三、ABC算法原理在基本ABC算法中，人工蜂群包含3種個體：雇傭蜂、觀察蜂和偵查蜂。每個雇傭蜂對應一個確定的食物源（解向量）并在迭代中對蜜源的鄰域進行搜索。根據(jù)蜜源豐富程度（適應值的大?。┎捎幂啽P賭的方式雇傭觀察蜂采蜜（搜索新蜜源）如果蜜源多次更新沒有改進，則放棄該蜜源，雇傭蜂轉為偵查蜂隨機搜索新蜜源。

蜂群采蜜行為待求解問題食物源位置可行解食物源質量適應度采蜜速度收斂速度食物源質量最大值（最大收益度）最優(yōu)解人工蜂群算法詳解1.蜜源初始化初始化時，隨機生成SN個可行解（等于雇傭蜂的數(shù)量）并計算適應度函數(shù)值。隨機產(chǎn)生可行解的公式如下：

(1)

式中，xi(i=1,2,...,SN)為D維向量，D為優(yōu)化參數(shù)的個數(shù)，j∈{1,2,…,D}。2.新蜜源的更新搜索公式蜜蜂記錄自己到目前為止的最優(yōu)值，并在當前蜜源鄰域內(nèi)展開搜索，基本ABC在蜜源附近搜索新蜜源的公式為:

（2）

式中，j∈{1,2,…,D}，k∈{1,2,…,SN}，k為隨機生成且k≠i，φik

為[-1,1]之間的隨機數(shù)。人工蜂群算法詳解3.觀察蜂選擇雇傭蜂的概率式中，fit(xi)為第i個解的適應值對應蜜源的豐富程度。蜜源越豐富，被觀察蜂選擇的概率越大。4.偵察蜂的產(chǎn)生

為防止算法陷入局部最優(yōu)，當某蜜源迭代limit次沒有改進時，便放棄該蜜源,并且將該蜜源記錄在禁忌表中,同時該蜜源對應的雇用蜂轉變?yōu)閭刹旆浒词?1)隨機產(chǎn)生一個新的位置代替原蜜源。人工蜂群算法詳解四、基本ABC算法的流程1:根據(jù)式(1)初始化種群解xi，i=1,…,SN2:計算種群中各個蜜蜂的適應值3:cycle=14:repeat5:雇傭蜂根據(jù)(2)產(chǎn)生新的解vi

并計算適應值6:雇傭蜂根據(jù)貪心策略選擇蜜源7:根據(jù)(3)式計算選擇蜜源xi的概率Pi

8:觀察蜂根據(jù)概率Pi選擇蜜源xi，根據(jù)(2)式在該蜜源附近產(chǎn)生新的蜜源vi

，并計算新蜜源vi的適應值9:觀察蜂根據(jù)貪心策略選擇蜜源10:決定是否存在需要放棄的蜜源，如果存在，根據(jù)(1)式隨機產(chǎn)生一個蜜源替代它11:記錄最優(yōu)解12:cycle=cycle+113:untilcycle=MCN人工蜂群算法詳解

所有城市的任一種排列即是問題的一個解，解空間由若干解構成，因此初始化解空間就是隨機產(chǎn)生多個不同的城市序列。以n個城市為例，從1到n對其進行編號，那么完成一次旅行的路徑就用1到n的一個排列組合來表示。在人工蜂群算法中，每一個引領蜂或者跟隨蜂的位置就對應一個路徑的組合，食物源的豐富程度對應這條路徑的長度，用適應度函數(shù)值來描述食物源的豐富程度，也就是說，適應度函數(shù)值越小的引領蜂或者跟隨蜂所在的位置，所代表的路徑也最優(yōu)。五、人工蜂群算法解TSP的實現(xiàn)人工蜂群算法詳解算法實現(xiàn)TSP問題與蜂群采蜜行為對應關系人工蜂群算法詳解更新策略

實現(xiàn)TSP問題的算法中存在兩級因子,即引領因子及轉移因子.引領因子是指通過上一級引領路徑直接確定的城市之間引領強度的大?。晦D移因子是指蜜蜂從城市i到城市j的轉移強度,與引領因子及更新策略有關,而轉移因子歸一化后,又可以求出相應兩個城市的轉移概率算法實現(xiàn)人工蜂群算法詳解下一步選擇的城市可以表示為：

Ak={1,2,…,n}-Tk其中Ak表示蜜蜂k下一步可以選擇的城市,Tk表示以記錄蜜蜂k本代所走過的城市,Tk隨蜜蜂不斷選擇下一個城市而做動態(tài)調(diào)整.進化代數(shù)N每增加一次,各條路徑上的轉移因子就要清零一次,保證轉移因子沒有遺留歷史信息,而僅僅是根據(jù)本代路徑信息更新.所有蜜蜂完成一次迭代循環(huán),各路徑上轉移因子根據(jù)式(1)(2)(3)作調(diào)整.然后,對所有路徑長度排序,得到引領路徑矩陣LR.最后采用2級更新策略.更新策略算法實現(xiàn)人工蜂群算法詳解

第1級:引領因子更新策略引領路徑的選擇有3種方式:取長度最短的路徑為引領路徑;取長度前δ位(或δ%為引領路徑);上代全部蜜蜂走過的路徑為引領路徑.更新策略算法實現(xiàn)人工蜂群算法詳解更新策略式中:N為進化代數(shù);LR(N)表示第N代路徑長度排序后得到的引領路徑矩陣;gm表示蜂群中蜜蜂總數(shù);λij表示第k只蜜蜂在第N次迭代循環(huán)中留在路徑ij上的引領因子。算法實現(xiàn)人工蜂群算法詳解更新策略ABC算法提供了3種不同模型,分別為Bcs,Bqs,Bds,它們的差別在于引領因子λkij的計算表達式不同.上述三種模型中,后兩者利用的是局部信息,而前者利用的是整體信息.其中:Q為引領常數(shù);Lk為第k只蜜蜂在本次迭代中所走過路徑的長度;dij表示第i個城市到第j個城市的距離.算法實現(xiàn)人工蜂群算法詳解更新策略第2級:轉移因子動態(tài)更新策略轉移因子更新,人工蜜蜂根據(jù)當前允許選擇的城市及上一代建立的引領路徑矩陣,動態(tài)確定每個待選城市的轉移因子轉移因子動態(tài)更新公式為算法實現(xiàn)人工蜂群算法詳解更新策略

式中:ρkij為第k只蜜蜂從城市i到城市j的轉移因子;γ為除引領蜂走過的路徑外,可選城市的總數(shù);σ為轉移強度;μ為可選城市總數(shù);當可選路徑中不含引領蜂走過的路徑時,轉移因子取σ/μ,其中,當可選路徑中含引領蜂走過的路徑且為引領蜂走過的路徑時,轉移因子等于τij,若選其它路徑,則轉移因子為算法實現(xiàn)人工蜂群算法詳解更新策略蜂群算法的狀態(tài)轉移策略

設蜂群中蜜蜂總數(shù)為gm,偵察蜜蜂數(shù)為sm,跟隨蜜蜂數(shù)fm,則有gm=sm+fm.其中sm取總數(shù)的1/c左右,c為常數(shù),取值小于10,以保證算法收斂.在從城市i轉移到城市j的過程中,引領蜂完全重走上一次的路徑.跟隨蜂和偵察蜂依據(jù)下式計算在第N代第k只蜜蜂節(jié)點轉移的概率.狀態(tài)轉移公式為算法實現(xiàn)人工蜂群算法詳解更新策略

式中對于引領蜂,完全重走上次的路徑,概率等于1.對于跟隨蜂,根據(jù)轉移因子大小依概率選擇路徑,啟發(fā)式因子ηij=1/dij,dij(i,j=1,2,…,n)為城市i和城市j之間的歐式距離;α為表示轉移因子ρij重要程度的參數(shù);β為表示啟發(fā)式因子ηij重要程度的參數(shù);BS,BF,BL分別為偵察蜂、跟隨蜂及引領蜂集合.

對于偵察蜂,t是允許路徑集中,可以選擇城市的總數(shù),構造累加集序列Psum,累加集序列位置代表城市標號,通過計算機產(chǎn)生(0,1)之間的隨機數(shù),并由此確定在Psum的位置,最終確定選擇城市.此外,c可以隨著進化代數(shù)動態(tài)調(diào)整:起初,為了增加解的多樣性,可適當增大c,隨著迭代次數(shù)的增加,為了加速并保證收斂,可適當減小c.算法實現(xiàn)人工蜂群算法詳解更新策略

跟隨蜂根據(jù)轉移因子大小按概率狀態(tài)轉移,保證大部分蜜蜂依上代歷史信息選