Python — 人工蜂群演算法(Artificial Bee Colony, ABC)求解最佳化問題

Published in

學習漂流瓶 Drift Bottle

8 min readMay 20, 2021

人工蜂群演算法（Artificial Bee Colony, ABC）是由 Karaboga於2005年提出的全局優化演算法，主要來源自蜂群採蜜的行為，是屬於群體智能算法的其中一種。

人工蜂群演算法（以下通稱ABC）是一種全局優化演算法，來源自蜂群採蜜的行為，蜜蜂根據各自所擔任的腳色分別進行不同的活动，訊息會在蜂群間共享和交流，進而找到問題的最佳解。優點為穩定性高、控制參數較少、較易理解，缺點則為存在著過早收斂的疑慮。筆者會在下文解析ABC的原理，並在最後附上代碼。

在本文你將會學會以下技巧:
1.培養分析問題的能力。
3.以python實現簡單的演算法。
4.透過演算法解決最佳化問題。

原理分析

ABC是由雇佣蜂（employed bees）和非雇佣蜂（unemployed bees）所組成，其中非雇佣蜂又是由觀察蜂（on-looker bees）和偵查蜂（scout bees）組成。主要目的是為尋找花蜜量最大的蜜源（fitness）。

雇佣蜂（employed bees）：與特定的蜜源相聯繫(該蜜源枯竭之后雇佣蜂轉變成偵查蜂)
觀察蜂（on-looker bees）：觀察雇佣蜂傳遞的信息並依據其選擇其中一蜜源
偵查蜂（scout bees）：由食物源枯竭的雇佣蜂生成，随機查找蜜源

每個雇佣蜂會對應一個確定的蜜源（fitness），在迭代過程中對蜜源的臨域進行搜索，根据蜜源的豐富程度（fitness大小），採用輪盤法（Roulette Wheel Selection）的方式雇佣跟随蜂採蜜（搜索新蜜源）。

輪盤法(Roulette Wheel Selection)
為一種回放式隨機取樣法，將一輪盤分成N個部分，根據fitness決定其盤面面積大小，fitness越大面積就越大，故在隨機取樣中被選到的機會就會越大。

生成Trial表，代表著搜索次數的限制。

如果蜜源多次更新都没有改變（Trial達到更新上限），意味著蜜源枯竭，則放棄此蜜源，雇佣蜂則轉為偵查蜂随機搜索新蜜源（Trial歸0）。

觀察蜂在蜂巢內等待偵查蜂的食物來源收集，並從有潛在豐富的蜜源中選擇一個蜜源來採蜜。

以下正文開始～

最佳化問題

此次求解最佳化問題為Rastrigin function，為最佳化常用的測試函數，其最佳解為 f(0,0,…,0) = 0，公式如下：

設定參數

D、 N：維度以及組數，藉由此生成Food Source。
ub、lb：區域上下界。
Ub、 Lb：全域上下界。
limit：試驗上限，用以決定是否放棄該蜜源。
max_iter：迭代次數。

初始化蜜源

初始化雇佣蜂和觀察蜂數量、蜜源位置、蜜源搜索次數上限。

在此設定(D、N)為(5、10)，(Ub、Lb)為(5、-5)，(ub、lb)為(5、-5)，limit為D*N， max_iter則為10000。

Minimum: 72.15093

其中蜜源豐富程度(fitness)是根據以下公式決定

#Fitness function
def fitness_machine(num):
    fitness = 1/(1+num) if num >= 0 else 1+abs(num)
    return fitness

雇佣蜂階段 (Employed Bee Phase)

雇佣蜂會根據以下公式更新蜜源位置，保存當前最佳蜜源，紀錄蜜源不好的次數（Trial + 1），根據所選擇的概率方法選擇採蜜的蜜源。

針對每一組數(1~5)隨機選擇一值(公式中為X)，其後根據所選的值所在的column隨機選擇一值為其更新的partner(公式中為Xp)，其中 ϕ 為-1~1間的亂數，將以上數字帶入Xnew公式中求出新的值，並Xnew暫時替代原先選取的值X，求出新的f(x)和fitness，藉由和原fitness比較，決定是否留下新的值以及試驗次數(Trial)是否需要加 1。

決定Xnew和Trial的規範整理

因本文示範範例為“求解最小化問題”，故在寫code時需讓演算法永遠保留最小的值，所以針對fitness公式來說：

f(x)越小，代表fitness越大；f(x)越大，代表其fitness就越小
故為了只保留最小值，若生成的f(x)沒有比較小，則保留原值，trial必須加1，反之若是生成的f(x)有比較小，則將其替換且trial保持不變。

雇佣蜂階段結果

Minimum: 70.11839

觀察蜂階段(On-looker Bee Phase)

觀察蜂根據輪盤法(Roulette Wheel Selection)選擇一個蜜源，在該蜜源附近更新此蜜源。

此階段更新蜜源位置的公式和雇佣蜂階段的公式相同。

建立Probability list

透過上述第一階段結束的fitness求出各別的機率p值，並建立一機率列表。

針對每一組數依序生成一0~1之間的亂數 r，透過和其組數對應的機率p比大小，若是 r 比 p 小，則進行到觀察蜂階段，若沒有則保持不變，且Trial增加1；由上述可知，若是fitness的機率p越大，則可能需替換的機率就會越大。

觀察蜂階段

其步驟和雇佣蜂階段大致一樣，首先針對需替換的組隨機選擇一值(公式中為X)，其後根據所選的值所在的column隨機選擇一值為其更新的partner(公式中為Xp)，其中 ϕ 為-1~1間的亂數，將以上數字帶入Xnew公式中求出新的值，並Xnew暫時替代原先選取的值X，求出新的f(x)和fitness，藉由和原fitness比較，決定是否留下新的值以及試驗次數(Trial)是否需要加 1。

以下為判斷是否需要進入觀察蜂階段，會應用到上述提及的Probability_list和Onlooker_update_fs_step2函式。

for i in range(N):
    if random.uniform(0,1) < Probability_list[i]:
        onlooker_out = Onlooker_update_fs_step2(i,fs_step2)
        fs_step2_2 = onlooker_out[0]
        fv_afe = onlooker_out[1]
    else:
        fs_step2_2 = fs_step2
        fv_afe[i] += 1

觀察蜂階段結果

Best Value: 70.11839 (此為每次迭代中須記錄的最佳值)

偵察蜂階段(Scout Bee Phase)

偵察蜂判斷每個蜜源是否到達試驗上限，若達到則放棄該蜜源，並生成一蜜源代替。

這部分需要針對各組的Trial值(試驗次數)判斷是否有超過limit上限，若是有則隨機生成全域範圍內的一組全新的Food Source，因這部分只需做簡單的判斷即可，所以就不以gists呈現。

#Scout bee phase
for j in range(N):
    if fv_afe[j] > limit:
        for i in range(D):
            fs_step2[j][i] = random.uniform(-5,5)
            fv_afe[j] = 0

迭代結束，輸出最佳蜜源位置。

將以上流程丟入完整的迭代過程

D、N = (5,10)
limit = 50
max_iter = 10000

迭代完後最佳解為：

將結果視覺化，紅線為歷代迭代的最佳解：

若是將max_iter調整為500，可看出其實很早就開始收斂了。

若是將(D、N)設定為(2、10)，會發現max_iter不管設定多大，都不太可能迭代出最佳解，原因是試驗上限limit會受到D和N的影響，兩者是成正比的關係，其意義為因為limit過小，所以最小值需要時常被替換；但因為Trial的增加速度過快，同時其他組解也還未迭代出最小值，使其一直無法收斂。