人工蜂コロニーアルゴリズム(Artificial Bee Colony algorithm

人工蜂コロニーアルゴリズム(Artificial Bee Colony algorithm:ABC)*1は蜜蜂の採餌行動に基づいた最適化手法の一つです.自然界には採餌を行う蜂として収穫蜂(employed bee),追従蜂(onlooker bee)と偵察蜂(scout bee)が存在すると言われています.ABCではこれらの蜂の行動に基づいた3つのフェーズを条件を満たすまで繰り返すことによって最適化問題を解きます.

ABCでは,収穫蜂の数を&tex($n$,,80%);とすると追従蜂の数も&tex($n$,,80%);であり,巣を構成する蜜蜂の総数(コロニーサイズ)は&tex($2n$,,80%);であると考えます.解こうとしている問題の候補解(餌場)の数は収穫蜂の数と同数になります.アルゴリズムの枠組みは図1の通りです.

ABCの枠組み
図1. ABCアルゴリズムの枠組み

以下,各フェーズについて説明します.

解こうとしている最適化問題の解をベクトル&tex($x_{i}(i=1,\ldots ,n)$,,80%);とします.ベクトル&tex($x_{i}$,,80%);の&tex($j$,,80%);番目の成分を&tex($x_{ij}$,,80%);と書きます.

収穫蜂フェーズ
収穫蜂フェーズでは各蜂が担当する解を(1)式を用いて更新します(&tex($v_{i}=x_{i}$,,80%);とします).

&tex($\begin{eqnarray} v_{ij}=x_{ij}+\phi_{ij}(x_{ij}-x_{kj}) \end{eqnarray} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\not= i,\ \ \ \phi_{ij}\in rand[-1,1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$ ,,更新式);

ここで,&tex($j$,,80%);はランダムに選択されます.&tex($x_{k}$,,80%);はランダムに選択された&tex($x_{i}$,,80%);以外のベクトル,&tex($\phi_{ij}$,,80%);は区間&tex($[-1,1]$,,80%);中の乱数です.更新後,&tex($v_{i}$,,80%);と&tex($x_{i}$,,80%);の適応度を比較します.もし&tex($v_{i}$,,80%);が&tex($x_{i}$,,80%);よりも優れているならば,&tex($v_{i}$,,80%);を新たな&tex($x_{i}$,,80%);とし,試行カウンタも0にリセットします.さもなくば,&tex($x_{i}$,,80%);の試行カウンタを1増やします.対象問題が最小化問題ならば適応度は次の評価関数によって求めます.

&tex($\begin{equation} fit_{i} = \left\{ \begin{array}{ll} \displaystyle\frac{1}{1+f(x_{i})} & \mbox{if } f(x_{i}) \geq 0 \\ 1+abs(f(x_{i})) & \mbox{if } f(x_{i}) < 0 \\ \end{array} \right . \end{equation} \ \ \ \ \ \ \ \ \ \ \ (2)$,,適応度関数);
追従蜂フェーズ
各解の適応度に基づいた(3)式の確率によって更新する解を決定し,その解を(1)式を用いて更新します.収穫蜂フェーズと異なるのは適応度に基づいて更新する解を決定することだけです.この更新作業を&tex($n$,,80%);回行います.もちろん適応度に基づく確率で解を選択するため,適応度の高い解は何度も更新作業を受け,低い解は一度も更新作業を受けない場合があります.

&tex($\begin{equation} p_{i}=\frac{fit_{i}}{\sum_{n}fit_{n}}\end{equation}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$,,選択確率);
偵察蜂フェーズ
予め決められている打ち切り回数&tex($C$,,80%);まで収穫蜂・追従蜂フェーズで更新作業を受けても改善されなかった解をランダムに生成した解と置換します.&tex($C$,,80%);は知識利用(exploitation)と探査(exploration)のバランスを取るパラメータです.

これら3つのフェーズを繰り返すことによって最適化問題を解くことが出来ます.さらに詳しい内容やソースコードのダウンロードはKaraboga等のArtificial Bee Colony (ABC) Algorithm Homepageを参照してください.

研究
 


*1 Karaboga, D.: An idea based on honey bee swarm for numerical optimization, Erciyes University, Kayseri, Turkey, Technical Report-TR06(2005).