GABCアルゴリズムの拡張とその実験的評価

全文

(1)情報処理学会第 74 回全国大会. 1B-2. アルゴリズムの拡張とその実験的評価近藤久 Ý 茨城大学工学部知能システム工学科 Ý. はじめに近年，単純な知能のみを有する個体が群れを成すことによって非常に高度な知能が創発される群知能（ .

(2) ）が注目され活発な研究が行われている．代表的な群知能のひとつとして（

(3)

(4) ）アルゴリズム（以後，と略記）がある．は蜜蜂の採餌行動を模倣することによって最適化問題を解く．文献においての性能はや

(5) （

(6) ）と互角かそれ以上であることが示されている．最近，等は

(7) の更新式に基づき群れ全体の最良解を用いての解探索を誘導するように改良した（）を提案した．本稿では，の更なる性能改善のための拡張を提案する．具体的には群れが探索した現時点の最良解の適応度が，ある条件のもとでこれまでの群れ全体の最良解の適応度よりも低くなった場合，最低適応度を持つ解とこれまでの最良解を置換する．この置換によってよりも性能が改善されることを実験を通して確認した．. . と . 自然界においては，一般に餌場から蜜を集める種類，追従蜂（の蜜蜂がいる．収穫蜂（））と偵察蜂（

(8) ）である．では，収穫蜂の数をとすると追従蜂の数もであり，巣を構成する蜜蜂の総数（コロニーサイズ）はとなる．餌場（候補解）の数は収穫蜂の数と同数である．の枠組を図 ½ に示す．. 停止条件を満たさない . 収穫蜂フェーズ：各解の更新を行う．追従蜂フェーズ：各解の適応度に基づいて解を選択し，その解の更新を行う偵察蜂フェーズ：設定された回数の間に一度も更新されなかった解のつをランダムに生成した新たな解と置換する．. . . . . . . . ここで，はランダムに選択される．（ただし）はランダムに選択された以外の解である．は区間中の乱数である．との適応度を比較し，もしが優れていればと置き換える．さもなくば，の試行カウンタを増やす．対象問題が目的関数の値を最小とするの値を求める最小化問題ならば，適応度は次の評価関数により求められる．.

(9). . . . . . . . . 追従蜂フェーズでは，収穫蜂によって更新された解の適応度に基づいた確率

(10)

(11) を用いて解を選択し，その解に対して収穫蜂と同様の更新処理を行う．収穫蜂フェーズとの違いは追従蜂フェーズでは適応度に基づいて選択された解のみが更新されることである．偵察蜂フェーズでは，収穫蜂フェーズと追従蜂フェーズを通して予め決められた打切り回数（）の間に一度も更新されなかった解をランダムに生成した解に置換する．以後，図の回のループをサイクルと記述する．. . . は

(12) の更新式に基づいて，サイクル

(13) までに群れ全体が発見した最良解（（と略記））を利用し，サイクル

(14) のの解探索を誘導するように改良した手法である．は式の代わりに次の更新式を用いる． . . . . . . . ここで，はの番目の成分，は区間中の乱数であり，は非負の定数である．の場合はと同じである．. . 図. を次元の実数値ベクトル，（または）をベクトル（または）の番目の成分をあらわすとする．収穫蜂フェーズでは解を用いて次の更新式により更新する（とする）．. 提案手法. アルゴリズムの枠組.

(15) Ý

(16)

(17)

(18) ! "#$ "#$ %& '!$ ()*+)* &),$ -$ %& .*/)01**$ 2. は，その性能がよりも優れていることが示されているが，どちらの手法ともの値に大きく依存する．これは知識利用（）と探査（）のバランスを取るパラメータであり，解の近傍を探索する回数を決定する．大きな値の場合は，. 1-255. Copyright 2012 Information Processing Society of Japan. All Rights Reserved..

(19) 情報処理学会第 74 回全国大会. 適応度の低い解も高い解も場合によっては同じ回数の近傍探索を行うこととなり非効率的である．小さな値の場合は見込みのありそうな解の近傍探索回数が少なすぎて最良解を発見出来ない．この値を越えた解は偵察蜂フェーズでランダムに生成された解と置換される．ランダムに生成された解は通常は適応度が低く，次々と偵察蜂フェーズで今までの探索解が置き換えられてしまうと群れ全体の多様性は保証されるがこれまでの探索結果を利用出来なくなってしまう．提案手法では，サイクル

(20) で偵察蜂フェーズによるランダム解への置換があった場合に，次のサイクル

(21) における収穫蜂フェーズと追従蜂フェーズ終了段階での最良解の適応度がの適応度より低い場合に限り最低適応度の解とを置換することにした．これは過去に収穫した質の高い餌場に一定期間をおいて再度戻ってみることに相当する．この操作を再訪問フェーズと呼ぶことにする．再訪問フェーズを取り入れることによって，早期に改善見込みの少ない解を捨て，に戻ってみることによって，その近傍探索と他の解の近傍探索にを利用した解の改善を試みることが出来る．再訪問フェーズを取り入れたをと呼ぶことにする．. . . . . . . . . . . . . . . . $ . . . . アルゴリズムのパラメータは文献と同様にコロニーサイズ )（収穫蜂，追従蜂），繰り返し回数とし，各々回の実験を行った．の値の変化に対する関数値（平均値）の変化を図 ¾ に示す（片対数となっていることに注意）* 図より，どちらの関数においてもの性能が優れていることがわかる．関数では +，関数ではのときに，それぞれ最小値となった．関数ではの変化に対して関数値の変化があまりないが，関数では大きく変化していることがわかる．のときにおける回の実験の中で関数が最小値（ ) ）になった回と同じ乱数シードを用いた場合のサイクル

(22) におけるでの関数値の変化を図 ¿ に示す．では関数値は

(23) . 10-1 10-2 10-3 10-4 0. ABC GABC GABC+. 50. 100 Climit. 150. 200. 3 % -& 関数. 101 10-4 10-9 10-140. ABC GABC GABC+. 20. 40 Climit. 60. 80. % 3 関数. 図関数値（平均値）の変化. f2（Rastrigin 関数）. 101 10-4 10-9 10-140. 実験結果. ，及びを実現し，関数値最小化実験を行った． !"#$% 関数（式，次の初期範囲，最小解元，），& '#(! 関数（，，式，次元，の初期範囲，最小，，）のつの実験結果解について述べる（その他の関数については大会当日に述べる）．. 100. f2（Rastrigin関数，平均値）. f1（Rosenbrock関数，平均値）. 101. 図. ABC GABC GABC+. 1000

(24) . 2000 3000 サイクル(t). 4000. 5000. 関数のでの値の変化. 過ぎまでゆっくりと降下してる．

(25) ,+ で最小値（ -）となり収束した．とは

(26) 過ぎまで同じ振舞を示しながら降下し，では

(27) で最小値（）となり収束した．では，その後も関数値は降下し，

(28) +-- で最小値（ ) ）となった．. まとめと今後の課題本稿では，アルゴリズムの拡張とその実験結果について述べた．本拡張手法の考えは非常に単純であるが実験を通してその有効性を示した．今後の課題として，さらなる実験比較とと最低適応度解の置換タイミングの検討などが挙げられる．. 参考文献. 1-256. 4*5 !$ 2# "%$ 3# #6 , -$ 7 8%+99*# 4+5 % $ #6

(29) % ! % , ) - : $ "-! '!$ !$ ;&!$ ;-- 3 );39/+991# 4.5 % $ # &$ #6

(30) , Æ- - - : 6 <- % - !

(31) $ 2# % : $ = # .>$ # .$ #(1>)(?*+99?# 4(5 % $ #

(32) &!$ #6

(33) - ! <) - % - ! $

(34) 7- ) $ = # +*($ *$ #*90)*.++99># 415 @$ # , $ #6 %) <- % - ! - - : $

(35) 7- $ = # +*?$ ?$ #.*//) .*?.+9*9# Copyright 2012 Information Processing Society of Japan. All Rights Reserved..

(36)