01 | ABC的生物背景
蜜蜂是一種群居生物,生物學家研究發現蜜蜂以跳舞的方式來交換蜜源信息。根據分工的不同,蜜蜂被分為三個工種:引領峰、跟隨蜂、偵察蜂。
偵察蜂的職責是偵察蜜源(即蜜蜂的食物),一旦某一個偵察蜂找到蜜源後,實際上它的角色就切換為引領蜂了。
找到蜜源後的引領峰以跳舞的方式向同伴傳遞自己找到食物的信息,這時候一些飢餓的、沒有找到食物的蜜蜂就會沿著引領峰指明的方向去尋找食物,這些相信引領峰傳遞的信息的蜜蜂實際上就是跟隨蜂。這實際上屬於招募蜜蜂的行為。
當引領峰尋找了多次蜜源後,發現再也找不到吃起來更香的蜜源後,引領峰說話的信服力會降低,於是跟隨蜂也逐漸不相信引領峰傳遞的信息。
引領峰痛定思痛,決心轉變角色,做回偵察蜂。直到再次找到高質量的蜜源後,再做回引領峰,然後再帶著大夥吃香的、喝辣的。這實際上屬於放棄蜜源的行為。
02 | ABC的算法策略
通過對ABC生物背景的理解,相信各位猜到蜜源實際上就對應ABC中的解,實際上也就等同於遺傳算法中的個體。ABC的最終目的就是找出最好的「蜜源」,也就是最好的解。
那這些解如何尋找呢?也就是在ABC中如何更新這些解呢?
答案就是通過引領峰、跟隨蜂、偵察蜂這三種蜜蜂來更新最好「蜜源」的位置。這裡需要注意的一點是:引領蜂和跟隨蜂各佔蜂群的一半,數量等於蜜源的數量,且每個蜜源同一時間內只有一隻引領蜂採蜜。
有小夥伴可能會有疑問,偵察蜂怎麼沒有了?
因為偵察蜂與引領峰的角色是相互切換的,所以不是偵察蜂消失了,而是假設當前這一部分蜜蜂全是引領峰。
接下來以一個問題為例,幫助各位快速理解這三種蜜蜂是如何更新蜜源位置的?前面我們已經說過,蜜源實際與問題的解相對應。群智能算法的第一步大多是初始化種群,ABC算法也不例外。只有初始化若干個蜜源後,三種蜜蜂才會尋找蜜源。
假設我們要求解問題的維數為D,則一個解的表現形式為(即一個蜜源的位置為):
第i個蜜源的位置初始化公式如公式(1)所示:
接下來就是重頭戲,三種蜜蜂更新蜜源位置的公式。因為當前蜂群中只有引領蜂和跟隨蜂,所以毫無疑問是引領峰先對蜜源種群位置進行更新。引領峰對第i個蜜源位置更新公式如(2)所示:
式中,d為當前位置更新的維數,
所有的引領蜂完成式(2)的運算後,飛回信息交流區共享蜜源信息。跟隨蜂根據引領蜂分享的蜜源信息,按式(3)計算的概率進行跟隨:
然後,跟隨蜂採用輪盤賭的方法選擇引領蜂,即在[0,1]產生一個均勻分布的隨機數r,如果
搜索過程中,如果蜜源
以最小化的優化問題為例,在ABC 算法中,解的適應度評價依據式(5)計算。
綜上所述,ABC的主要步驟如下:
1)初始化各蜜源
2)為蜜源
3)依據式(5)評價
4) 由式(3)計算引領蜂找到的蜜源被跟隨的概率;
5)跟隨峰採用與引領蜂相同的方式進行搜索,根據貪婪選擇的方法確定保留的蜜源;
6)判斷蜜源
7)偵察蜂根據式(4)隨機產生新蜜源;
8)t=t+1; 判斷算法是否滿足終止條件,若滿足則終止,輸出最優解,否則轉到2)。
秦全德, 程適, 李麗, 等. 人工蜂群算法研究綜述[J]. 2014.03 | MATLAB實例
MATLAB代碼源地址:
https://yarpiz.com/297/ypea114-artificial-bee-colony
代碼中的目標函數如下:
點擊main.m函數運行代碼,結果為
目標函數值隨迭代次數變化曲線如下圖所示:
04 | 參考文獻
1.秦全德, 程適, 李麗, 等. 人工蜂群算法研究綜述[J]. 2014
2.Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
各位小夥伴可在留言板留言,未來我們講解的具體內容由你做主。如果可以的話,可以把希望講解的文獻也在留言板上寫出來。我們已經終於推出粉絲QQ交流群,各位小夥伴趕快加入吧!!!