Top/研究/2012-03-09

/2012-03-09

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

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

ABCでは，収穫蜂の数をとすると追従蜂の数もであり，巣を構成する蜜蜂の総数（コロニーサイズ）はであると考えます．解こうとしている問題の候補解（餌場）の数は収穫蜂の数と同数になります．アルゴリズムの枠組みは図1の通りです．

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

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

解こうとしている最適化問題の解をベクトルとします．ベクトルの番目の成分をと書きます．

収穫蜂フェーズ

収穫蜂フェーズでは各蜂が担当する解を(1)式を用いて更新します（とします）．



ここで，はランダムに選択されます．はランダムに選択された以外のベクトル，は区間中の乱数です．更新後，との適応度を比較します．もしがよりも優れているならば，を新たなとし，試行カウンタも0にリセットします．さもなくば，の試行カウンタを1増やします．対象問題が最小化問題ならば適応度は次の評価関数によって求めます．

追従蜂フェーズ

各解の適応度に基づいた(3)式の確率によって更新する解を決定し，その解を(1)式を用いて更新します．収穫蜂フェーズと異なるのは適応度に基づいて更新する解を決定することだけです．この更新作業を回行います．もちろん適応度に基づく確率で解を選択するため，適応度の高い解は何度も更新作業を受け，低い解は一度も更新作業を受けない場合があります．

偵察蜂フェーズ

予め決められている打ち切り回数まで収穫蜂・追従蜂フェーズで更新作業を受けても改善されなかった解をランダムに生成した解と置換します．は知識利用（exploitation）と探査（exploration）のバランスを取るパラメータです．

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

研究