Artificial Bee Colony Algorithm

3.5.1 Artificial Bee Colony Algorithm の概要

Artificial Bee Colony Algorithm（ABC）［27］［31］は，2005年にDervis Karabogaにより 開発された，連続値最適化問題を対象とする多点探索型メタヒューリスティクスである。

ABCは蜜蜂の採餌行動のメカニズムに基づいており，働き蜂，傍観蜂，斥候蜂により機能 を分担した探索を行う。ABCの探索性能はメタヒューリスティクスの中でも比較的高いこ とが示されており，更なる改良が目指されている［43］［53］。

3.5.2 Artificial Bee Colony Algorithm のアルゴリズム

ABCでは，働き蜂，傍観蜂，斥候蜂がそれぞれ異なる操作を行う。近傍の生成と探索点 の更新は，主に働き蜂と傍観蜂が行う。働き蜂の探索では，全ての探索点が探索を行う。

傍観蜂の探索では，ルーレット選択で選ばれた探索点が探索を行う。斥候蜂の探索では，

停滞回数が規定回数Limit ≥ 0 (m_o,Limit ∈Z)よりも上回った場合のみ，ランダムに更新

第3章 メタヒューリスティクスの探索構造の解析 44

する。

ABCの更新式を式(3.15)，式(3.16)，式(3.17)に示す。

ˆxⁱ_n =

 xⁱ_λ+ϕⁱu^random_λ , n= λ

xⁱ_n, otherwise (3.15)

vⁱ = 

xˆⁱ−xⁱ, f (ˆxⁱ)< f (xⁱ)

0, otherwise (3.16)

xⁱ := xⁱ+vⁱ (3.17)

ただし，mo∈[0,m]はパラメータ，u^random= x^r−xⁱ，r ,iは整数値一様分布UZ(1,m)に 従う乱数，ϕ^{iは実数値一様分布}UR(−1,1)に従う乱数，λ^{は整数値一様分布}UZ(1,N)に従 う乱数である。

ABCでは，近傍解xˆを，探索点x^rを基準として，探索点間の差分ベクトルu^randomで生 成する。移動ベクトルvを，目的関数値により，近傍解xˆと探索点xの差分ベクトルか，

零ベクトル0のどちらかを選択する。

以下にABCのアルゴリズムを示す。アルゴリズムの終了条件を評価回数T ≥ T_max（T_max： 最大評価回数）とする。探索点の初期位置を初期配置領域IS= [a, c]^N ⊂ R^{N内に与える。}

【Artificial Bee Colony Algorithmのアルゴリズム】

Step 0:[準備]

探索点数（働き蜂数）m，傍観蜂数mo∈[0,m]⊂ Z^{，規定回数}Limit≥0 (Limit ∈Z)， 最大評価回数T_maxを定め，評価回数をT = 0とする。

Step 1:[初期化]

探索点の初期位置xⁱ（i= 1,· · · ,m）を初期配置領域IS内にランダムに与え，評価 回数T =mとする。停滞回数をs_i = 0とする。

Step 2:[働き蜂による探索]

各探索点xⁱ（i=1,· · · ,m）について，近傍解xˆⁱを生成し，更新する。

Step 2-1:[近傍の生成]

第3章 メタヒューリスティクスの探索構造の解析 45

各探索点xⁱについて，近傍解xˆⁱを

ˆxⁱ_n =

xⁱ_λ+ϕⁱ(x^r_λ− xⁱ_λ), n=λ xⁱ_n, otherwise

より要素ごとに生成する。ただし，r , iは整数値一様分布UZ(1,m)に従う乱 数，ϕ^{iは実数値一様分布}U_R(−1,1)に従う乱数，λ^{は整数値一様分布}U_Z(1,N) に従う乱数である。

Step 2-2:[探索点の更新]

各探索点xⁱ，停滞回数sⁱについて

vⁱ =

xˆⁱ−xⁱ, f (ˆxⁱ)< f (xⁱ) 0, otherwise

sⁱ := 

0, f (ˆxⁱ)< f (xⁱ) sⁱ+1, otherwise

xⁱ :=xⁱ+vⁱ

より更新する。評価回数T := T +mとする。

Step 3:[傍観蜂による探索]

最良探索点x^c−best，各探索点xⁱの適合度 f itⁱ，適合度に基づく選択確率pⁱを

x^c−best =argmin

xⁱ

{f (xⁱ)|i=1,· · · ,m}

f itⁱ = 1

|f (x^c−best)− f (xⁱ)|+1 pⁱ = f itⁱ/

∑m i=1

f itⁱ

より求める。j=1とする。

第3章 メタヒューリスティクスの探索構造の解析 46

Step 3-1:[近傍の生成]

選択確率pⁱ（i= 1,· · · ,m）に基づくルーレット選択により，移動する探索点x^ℓ を選択する。

探索点x^ℓについて，近傍解xˆ^ℓを

ˆx^ℓ_n =

x^ℓ_λ+ϕ^ℓ(x^r_λ− x^ℓ_λ), n= λ x^ℓ_n, otherwise

より要素ごとに生成する。ただし，r , ℓ^{は整数値一様分布}U_Z(1,m)に従う乱 数，ϕ^{ℓは実数値一様分布}UR(−1,1)に従う乱数，λ^{は整数値一様分布}UZ(1,N) に従う乱数である。

Step 3-2:[探索点の更新]

探索点x^ℓ，停滞回数s^ℓについて

v^ℓ =

xˆ^ℓ−x^ℓ, f (ˆx^ℓ)< f (x^ℓ) 0, otherwise

s^ℓ := 

0, f (ˆx^ℓ)< f (x^ℓ) s^ℓ+1, otherwise

x^ℓ :=x^ℓ+v^ℓ

より更新する。評価回数T := T +1とする。

j< m_oならば，j := j+1とし，Step 3-1へ戻る。

Step 4:[斥候蜂による探索]

各探索点について，停滞回数が規定回数を超えた探索点番号の集合を

P = {i|sⁱ ≥ Limit; i=1,· · · ,m}

とする。M = |P|^{とし，探索点}x^h（∀h∈P）を初期配置領域IS内にランダムに更 新し，評価回数T :=T + Mとする。

Step 5:[終了判定]

T ≥T_maxならば，探索を終了する。さもなければ，Step 2へ戻る。

第3章 メタヒューリスティクスの探索構造の解析 47

3.5.3 Artificial Bee Colony Algorithm の探索構造の解析

更新式に従って生成される近傍について重点的に考察する。図3.5に，ABCの近傍生成 について示す。式(3.15)で表されるように，探索点xⁱからランダムの探索点x^rに向かう 差分ベクトルu^randomを活用して，近傍解xˆⁱは乱数による摂動に基づく近傍内に生成され る。このとき，近傍解xˆⁱは，ランダムに選ばれた要素のみに摂動を加えて，それ以外の要 素をxⁱの要素とする。このため，解空間において，ある単一の軸に沿って，摂動が加えら れる。これは，DEの交叉と同様に，摂動が加えられた要素と探索点の要素の組み合わせ で，近傍解xˆⁱが生成される。また，探索点間の差分ベクトルu^randomを用いることで，探 索過程の探索点分布のスケールや探索点の配置状態に適した位置に解を生成することが可 能となる。

ABCは改善移動であるため，探索点xⁱは目的関数値が改善した場合，近傍解xˆⁱへ移動 する。このため，探索点xⁱは式(2.12)のp-best，式(2.14)のc-bestは式(2.13)のg-bestと みなすことができる。つまり，ABCでは各探索点xⁱが降下条件を満たす場合のみ移動を行 い，優れた探索点を次の探索点群とする。その後の近傍の生成では，近傍解xˆⁱは，優れた 探索点群によって，単一の軸に沿った摂動が加えられるため，優れた領域に生成されるこ とが期待できる。これは，「改善移動を行う探索点群によって問題構造を把握し，その情報 を活用した探索を行う」というPOPに基づく探索構造であることを示している。したがっ て，ABCは，降下条件を満たす探索点xⁱの移動，探索点間の差分ベクトルの活用，解同士 の組み合わせによって，優れた近傍を生成することで，探索点群として良い領域に集まる。

第3章 メタヒューリスティクスの探索構造の解析 48

図3.5：Artificial Bee Colony Algorithmの近傍の生成