最適化アルゴリズムを実装していくぞ（人工蜂コロニーアルゴリズム）

はじめに

最適化アルゴリズムの実装シリーズです。
まずは概要を見てください。

コードはgithubにあります。

人工蜂コロニーアルゴリズム

概要

人工蜂コロニーアルゴリズム(Artificial Bee Colony: ABC)は、ミツバチの採餌行動をもとに作られたアルゴリズムです。
ミツバチは花の蜜を餌としており、蜜を採取した後、巣で待機している仲間に自分が取得した蜜の質や方向などの情報を8の字ダンスで伝えます。
待機しているミツバチはこの8の字ダンスの情報を元に取りに行く蜜を決めます。

参考
・進化計算アルゴリズム入門 生物の行動科学から導く最適解

アルゴリズム

ミツバチの採餌行動を、収穫バチ、追従バチ、偵察バチの3つの役割を担うミツバチから定義します。

1. 収穫バチは１つの食糧源に蜜を採取しに行き、また食糧源の近くも探索する
2. 追従バチは収穫バチの情報に基づいて目標の食糧源を決め、蜜を採取する
3. 食糧源の蜜が取りつくされたら偵察バチは新しい食糧源を探す

収穫バチは対応した食糧源を持っており、収穫バチと食糧源の数は同じになります。

• アルゴリズムのフロー

• 用語の対応

問題	人工蜂コロニーアルゴリズム
入力値の配列	食糧原(花)
入力値	食糧原の座標
評価値	食糧原の評価値

• コード内で使う変数の意味

変数名	意味	所感
problem	任意の問題のクラス（問題編を参照）
harvest_bee	収穫バチの数	食糧源の数と同じ
flowers	食糧源の配列
flowers[i]["flower"]	i番目の食糧源
flowers[i]["count"]	i番目の食糧源で採取された蜜の回数
follow_bee	追従バチの数	多いほど評価値の高い周りの探索回数を減らす
visit_max	食糧源で取得できる蜜の上限	多いほどじっくり探索、大きいほど広域を探索

収穫バチフェーズ

収穫バチフェーズでは、まず収穫バチが自分の食糧源の近くを探索します。
探索して見つけた新しい食糧源と今の食糧源を比較し、新しい食糧源が良ければ今の食糧源と置き換え、蜜を取得します。

探索は今の食糧源の座標から新しい座標を作成し、その座標を新しい食糧源とします。
新しい座標 $\vec{y}$ は、別の食糧源lを用いて、今の食糧源の座標の第k成分を以下の数式で変更します。

y^i_j = \left\{
\begin{array}{l}
x_j + rand[-1,1] \times ( x^i_j - x^l_j ) \quad j=k \\
x^i_j \qquad (otherwise)
\end{array}
\right.

ここで $k$ と $l$ はランダムな数で、$rand[-1,1]$ は-1以上、1以下の実数乱数です。
座標の1成分だけを更新することで近くの探索を表現しています。

コードの実装例は以下です。

# 収穫バチフェーズ
for i in range(harvest_bee):
    flower = flowers[i]["flower"]

    # 食糧源の近くを探索
    pos = flower.getArray()
    k = random.randint(0, len(pos)-1)  # 第k成分
    flower2 = flowers[random.randint(0, len(flowers)-1)]["flower"]
    pos2 = flower2.getArray()
    pos[k] += (random.random()*2-1) * (pos[k] - pos2[k])

    # 新しい食糧源
    new_flower = problem.create(pos)

    # 良ければ置き換え
    if new_flower.getScore() > flower.getScore():
        flowers[i]["flower"] = new_flower

        # 最も良い食糧源を記録
        if max_flower.getScore() < new_flower.getScore():
            max_flower = new_flower

    # 蜜の取得回数を増やす
    flowers[i]["count"] += 1

追従バチフェーズ

ランダムに食糧源を選び、蜜の取得回数を+1します。
ランダムといっていますが、選ぶ食糧源は評価値の重みで確率を変動させます。
(遺伝的アルゴリズムのルーレット方式と一緒です)

例えば食糧源の評価値が
1番目：9
2番目：1
とあった場合、1番目が選ばれる確率は90%で、2番目が選ばれる確率は10%になります。

算出方法ですが、単純な累積和による選択方法を実装しています。

まずは全食糧源の評価値の合計を求めるのですが、評価値が負の場合に最小の値を基準にしてしまうと選ばれない問題があります。
ですので、最小値が負の場合は0からの距離を重みとして計算しています。

import random
def selectFlower(flowers):

    # 全個体の評価値を配列に入れる
    weights = [x.getScore() for x in flowers]

    w_min = min(weights)
    if w_min < 0:
        # 最小が負の場合は基準を0→w_min→に変更
        weights = [ w + (-w_min*2) for w in weights]
    
    # 重さの合計で乱数を出す
    r = random.random() * sum(weights)

    # 重さを順番に見ていき、乱数以下ならそのindexが該当
    num = 0
    for i, weights in enumerate(weights):
        num += weight
        if r <= num:
            return flowers[i]
    
    assert False, "ここには来ないはず"

# 追従バチフェーズ
for i in range(follow_bee):
    flower = selectFlower(flowers)
    flower["count"] += 1

偵察バチフェーズ

偵察バチフェーズでは蜜を指定回数(visit_max)取得した食糧源を、新しい食糧源に置き換えます。
これは食糧源近くの探索を打ち切り、まったく別の新しい食糧源を探索する事に相当します。

食糧源付近をじっくり探索したい場合は visit_max を大きく、広範囲を探索したい場合は小さく設定します。

# 偵察バチフェーズ
for i in range(len(flowers)):
    # 一定回数以上の食糧源を置き換える
    if visit_max < flowers[i]["count"]:
        o = problem.create()  # 新しい食糧源
        flowers[i]["count"] = 0
        flowers[i]["flower"] = o
        
        # 最も良い食糧源を記録
        if max_flower.getScore() < o.getScore():
            max_flower = o

コード全体

import math
import random

class ABC():
    def __init__(self, 
        harvest_bee,    # 収穫バチの数
        follow_bee=10,  # 追従バチの数
        visit_max=10    # 食糧源(蜜)の最大取得回数
    ):
        self.harvest_bee = harvest_bee
        self.follow_bee = follow_bee
        self.visit_max = visit_max


    def init(self, problem):
        self.problem = problem

        self.max_flower = None
        self.flowers = []
        for _ in range(self.harvest_bee):

            # 食糧源の取得回数を保存したいので count 変数を追加で作る
            o = problem.create()
            self.flowers.append({
                "flower": o,
                "count": 0
            })

            # 最大の食糧源を保存
            if self.max_flower is None or self.max_flower.getScore() < o.getScore():
                self.max_flower = o

    def step(self):

        # 収穫バチフェーズ
        for i in range(self.harvest_bee):
            flower = self.flowers[i]["flower"]

            # 食糧源の近くを探索
            pos = flower.getArray()
            k = random.randint(0, len(pos)-1)  # 1つの成分をランダムに決める
            flower2 = self.flowers[random.randint(0, len(self.flowers)-1)]["flower"]
            pos2 = flower2.getArray()  # 別食糧源
            pos[k] += (random.random()*2-1) * (pos[k] - pos2[k])

            # 新しい座標の食糧源を作成
            new_flower = self.problem.create(pos)

            # 新しい食糧源がよければ更新する
            if new_flower.getScore() > flower.getScore():
                self.flowers[r]["flower"] = new_flower

                # 最大の食糧源なら保存
                if self.max_flower.getScore() < new_flower.getScore():
                    self.max_flower = new_flower

            # 食糧源の取得回数+1
            self.flowers[r]["count"] += 1

        # 追従バチフェーズ
        for i in range(self.follow_bee):
            # 食糧源の評価値に従ってランダムに選ぶ
            index = self._selectFlower()

            # 食糧源の取得回数+1
            self.flowers[index]["count"] += 1

        # 偵察バチフェーズ
        for i in range(len(self.flowers)):
            # 一定回数以上訪れた食糧源を置き換える
            if self.visit_max < self.flowers[i]["count"]:
                
                # 新しい食糧源を作成
                o = self.problem.create()
                self.flowers[i]["count"] = 0
                self.flowers[i]["flower"] = o

                # 最大の食糧源なら保存
                if self.max_flower.getScore() < o.getScore():
                    self.max_flower = o
    

    def _selectFlower(self):
        # 全食糧源の評価値を配列に入れる
        weights = [x["flower"].getScore() for x in self.flowers]

        w_min = min(weights)
        if w_min < 0:
            # 最小が負の場合は基準を0→w_min→に変更
            weights = [ w + (-w_min*2) for w in weights]
        
        # 重さの合計で乱数を出す
        r = random.random() * sum(weights)

        # 重さを順番に見ていき、乱数以下ならそのindexが該当
        num = 0
        for i, weights in enumerate(weights):
            num += weight
            if r <= num:
                return i
        
        raise ValueError()

ハイパーパラメータ例

各問題に対して optuna でハイパーパラメータを最適化した結果です。
最適化の1回の試行は、探索時間を2秒間として結果を出しています。
これを100回実行し、最適なハイパーパラメータを optuna に探してもらいました。

問題	follow_bee	harvest_bee	visit_max
EightQueen	1	47	84
function_Ackley	1	24	77
function_Griewank	4	24	100
function_Michalewicz	4	32	100
function_Rastrigin	1	50	89
function_Schwefel	6	44	99
function_StyblinskiTang	1	18	96
LifeGame	4	38	10
OneMax	34	37	19
TSP	3	38	94

実際の動きの可視化

1次元は6個体、2次元は20個体で50step実行した結果です。
赤い丸がそのstepでの最高スコアを持っている個体となります。

パラメータは以下で実行しました。

ABC(N, follow_bee=15, visit_max=30)

function_Ackley

• 1次元

• 2次元

function_Rastrigin

• 1次元

• 2次元

function_Schwefel

• 1次元

• 2次元

function_StyblinskiTang

• 1次元

• 2次元

function_XinSheYang

• 1次元

• 2次元

あとがき

近くを探すのと遠くに移動するのを繰り返すので、局所解に陥ることはなさそうです。
追従バチと訪問回数のパラメータを決めるのが難しそうですが、いい感じに調整できればいい結果を残しそうです。