神奇的小蜜蜂

最新 05-25

英國一項最新研究說，在花叢中飛來飛去的小蜜蜂顯示出了輕易破解「旅行商問題」的能力，而這是一個吸引全世界數學家研究多年的大問題，如能理解蜜蜂的解決方式，將有助於人們改善交通規劃和物流等領域的工作。

英國倫敦大學皇家霍洛韋學院等機構研究人員報告說，小蜜蜂顯示出了輕而易舉破解這個問題的能力。他們利用人工控制的假花進行了實驗，結果顯示，不管怎樣改變花的位置，蜜蜂在稍加探索後，很快就可以找到在不同花朵間飛行的最短路徑。

進行研究的奈傑爾·雷恩博士說，蜜蜂每天都要在蜂巢和花朵間飛來飛去，為了采蜜而在不同花朵間飛行是一件很耗精力的事情，因此實際上蜜蜂每天都在解決「旅行商問題」。儘管蜜蜂的大腦只有草籽那麼大，也沒有電腦的幫助，但它已經進化出了一套很好的解決方案，如果能理解蜜蜂怎樣做到這一點，對人類的生產、生活將有很大幫助。

2005年，Karaboga小組為優化代數問題提出了人工蜂群演算法(Artificial Bee Colony Algorithm, 簡稱ABC演算法)是一個由蜂群行為啟發的演算法。

這種演算法主要基於 Tereshko 和Loengarov (2005) 提出的蜂群覓食行為模型。這個模型包含了三種核心元素：僱傭蜂（employed bees），非僱傭蜂（unemployed bees）和食物源（food sources）。前兩者負責搜尋蜂巢附近的富源（rich food sources）。這種模型也定義了兩種指引模式：富源會反饋會積極信號，從而引導更多的蜜蜂來采蜜；貧源（poor food sources）會反饋消極信號，會導致放棄這個食物源。這兩種行為是自組織的和群智能的。

在ABC中，把待求解的問題的解看做是人工食物，食物越充足（rich），表示解的質量越好，然後一群人工蜜蜂會去搜尋富源，從而找到一個相關問題的比較好的解。為了應用ABC，待求解的問題首先要轉化為最優化問題，也就是找到一組參數向量，使得目標函數最小化。人工蜂群就會隨機初始化一些解，然後通過迭代，使用鄰居搜索的策略來向更好的解靠近，並放棄差的解，逐步提高解的質量。

人工蜂群元啟發式演算法

在ABC中，人工蜂群由三種蜜蜂組成：僱傭蜂(employed bees)同特定的食物源相關聯；觀察蜂(onlooker bees)觀察蜂巢內僱傭蜂的舞蹈以決定選擇某個食物源；偵察蜂(scout bees)會隨機的搜索食物。偵察蜂和觀察蜂又叫做未僱傭蜂。演算法初始的時候，所有的食物源會被偵察蜂搜索到，然後，食物源會被僱傭蜂和觀察蜂所開發利用。持續性的開發利用會使得食物源很快被消耗盡，於是消耗盡食物源的僱傭蜂會轉變成為偵察蜂。在ABC中，食物源的位置代表了問題的一個可行解，食物源處的蜂蜜的數量代表了相關問題解的質量。僱傭蜂的數量等於食物源的數量，因為每隻僱傭蜂會關聯到一個且僅一個食物源。

初始化時期

利用偵察蜂初始化所有代表食物源的向量xm，（m=1,...,SN），SN是種群的大小，設定控制參數。由於每個食物源xm都是待優化問題的解向量，因此每個xm都含有n個變數(xmi,i=1,...,n)。這些向量將要被優化，從而使得目標函數最小化。可以利用下式進行初始化：

其中li和ui是參數xmi取值的上下限。

僱傭蜂時期

僱傭蜂會依據其記憶中的食物源的位置進行鄰居搜索，找食物源附近的更好的食物源。當僱傭蜂找到一個食物源之後，會評估其適應值。此處，它們可以採用下述公式來確定鄰居食物源：

其中xli是一個隨機選擇的食物源，i是隨機選擇的一個位置索引，θmi是一個[-a,a]之間的一個隨機數。當產生新的食物源之後，會計算出它的適應值，並且在vm和xm之間應用貪心法做出選擇。

解的適應值，可以通過下式轉化為最小化問題來求解：

其中，fm(xm)是待解問題的目標函數值。

觀察蜂時期

非僱傭蜂由兩部分群體組成：觀察蜂和偵察蜂。僱傭蜂會向在蜂巢中等待的觀察蜂來分享它們獲得的食物源信息。觀察蜂會根據這些信息進行一種隨機的選擇。為此，需要一種基於適應值的選擇方法，比如輪盤賭。fm(xm)被選中的概率Pm可以用下述表達式計算：

當食物源xm被一隻觀察蜂選中後，利用(2)式產生鄰居食物源vm，再計算其適應值。在僱傭蜂時期，在xm和vm之間用貪心法來做出選擇。因此，更多的觀察蜂會選擇富源並反饋回積極信號。

偵察蜂時期

未僱傭蜂隨機搜索食物源，稱為偵察蜂。如果僱傭蜂通過實現給定的嘗試次數之後，仍然未能提高解的質量，則僱傭蜂就變成為偵察蜂，其擁有的解就會被放棄。（嘗試次數是由ABC使用者事先給定的，稱為「limit」或者「放棄閾值」（abandonment criteria））轉換後的偵察蜂開始隨機搜索新的解，比如，如果xm被放棄了，那麼原來擁有xm的僱傭蜂就會利用(1)式來產生新的解。因此那些隨機產生的貧源或者近期形成的貧源就會被放棄，產生消極的信號，以來平衡積極的信號。

ABC演算法總結起來，有以下幾點：

1) 根據蜜蜂的覓食行為而得到；

2) 是全局優化演算法；

3) 為了數值優化而設計；

4) 也可以用來求解組合優化問題；

5) 可以用於有約束的和無約束的優化問題；

6) 只使用了三個參數（種群數量，最大循環次數以及閾值），這些參數是用戶事先確定的；

7) 非常的簡單，具有柔性和魯棒性。

編輯：叨叨徐

智能演算法交流中心