ABCの基本 — 知識ノート

近傍生成#

ABC で新しい候補を作る式はこれひとつ。

v_{i j} = x_{i j} + ϕ_{i j} (x_{i j} - x_{k j})

1 成分しか変えない。 残りの成分は $x_{i}$ のまま。 1 回の試行で変わるのは 1 次元だけになる。

差分を使う。 $x_{i j} - x_{k j}$ は差分進化と同じ発想で、集団が広く散っていれば大きく動き、収束すれば自然に小さく動く。ステップサイズを別に管理しなくてよい。

この「1 成分だけ」が ABC の性格を決めている。探索は慎重になり局所解に落ちにくい一方、 次元が上がるほど収束が遅くなる。 $n$ 次元なら全成分を一巡するのに最低 $n$ 回の試行が要る。

作った $v_{i}$ と元の $x_{i}$ を比べ、良い方だけを残す。悪化は決して受け入れない。焼きなまし法と対照的で、 ABC が局所解から抜け出す役目は Scout Bee に分離されている。

最小化問題では、目的関数値をそのまま確率に使えないので変換する。

{fit}_{i} = {\begin{matrix} \frac{1}{1 + f_{i}} & f_{i} \geq 0 \\ 1 + | f_{i} | & f_{i} < 0 \end{matrix}

これをOnlooker Bee の選択確率に使う。

Dervis Karaboga, Bahriye Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization 39, 2007.（原論文） https://doi.org/10.1007/s10898-007-9149-x
Dervis Karaboga, Bahriye Basturk. On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing 8(1), 2008. https://doi.org/10.1016/j.asoc.2007.05.007
Dervis Karaboga et al. A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review 42, 2014.（総説） https://doi.org/10.1007/s10462-012-9328-0