６．１ 問題設定
６．２ 実験結果
生体系に内在するインテリジェントシステムである免疫系について，工学的応用に関する可能性及びその有効性が議論され始めている．
本稿では，マルチエージェントシステムに対する最適化問題の一例である分業巡回セールスマン問題(n-Traveling Salesman Problem; nTSP)におけるだまし問題を取り上げ，免疫アルゴリズム(Immune Algorithms; IA)の特に記憶機構を重視した効果的な探索についての考察を行なう．
==> 最初に戻る
免疫システムとは, 生体内に侵入する多種多様な未知の抗原に対応するために, 細胞遺伝子の再構築を行なって抗原に対応する抗体を産生し, 抗原を排除する生体監視防衛機構である.工学的応用の一例に森らによってモデル化された免疫アルゴリズム[2]がある。
==> 最初に戻る
コーディングはパス表現を用いる．GAオペレータは，交叉にサブツアー交換交叉[3]を用い，任意の2都市を交換する突然変異を実装している．
免疫アルゴリズムにおいては、適応度、類似度、濃度、期待値の4つの計算尺度を求める必要がある。
nTSPに対するIAを図１に示す．
==> 最初に戻る
nTSPにおけるだまし問題は2重の同心円上に同数の都市が均等に並んだ都市配置である．その内外円の半径比によって2通りの異なる最適解，局所解を持つ．
図２(a)はどちらか一方の円を巡回してから他方を巡回するプラン(c-type)が最適解となる例で，図２(b)は外円と内円を交互に巡回するプラン(o-type)が最適解となる例である．このように異なる最適解，局所解が存在するだまし問題においてはIAの記憶細胞を再利用することにより探索が容易になると考えられる．
==> 最初に戻る
類似の問題を繰り返し解く必要のある場合に，過去の記憶を利用することで効率良く探索を行なうことが可能である．
このような類似問題を図３に示す．同図は，IAによる探索では，問題1において局所解である解が問題2では最適解となる，類似問題の典型的な例である．問題1を探索中に局所解o-typeに収束し始めるとそれらをサプレッサー細胞に記憶することにより，適応度の調整を行ない別の探索点へと移行する(一次免疫応答)．また，問題1の探索中に局所解となっているo-typeを記憶細胞に記憶することにより，問題2における探索が効率的に行なえると考えられる(二次免疫応答)．
==> 最初に戻る
類似問題としてだまし問題を設定し，記憶の再利用により探索が容易になることを確かめる．問題は表１のように設定し，都市配置は出発都市を円の中心に置き，外円と内円上には6都市ずつとした．IAのパラメータは表~\ref{IA-parameter}のように設定した．
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
確認方法は以下のように行なう．
Step1-4の探索の様子を比較する．
以下ではStep1をCempty，Step2をOc，Step3をC'oc，Step3をC'cと表記する．実験では以下の2通りの記憶利用による探索効率を比較する．
==> 最初に戻る
実験結果を図４，図５に示す．図４はそれぞれ，Cempty(同図上)，Oc(同図左中)，C'oc(同図左下)，C'c(同図右下)の探索で得られた最良解とその適応度，世代数を表している．図５は3問題の探索効率を比較しており，縦軸は最適解を1としてスケーリングした適応度，横軸は世代数を表している．
図４より，同じc-typeの問題を続けて解くCase1よりも途中でo-typeの問題を解くCase2の方が適応度，世代数共に良いことが分かる．その理由としては別の問題を解いたため，もしくは解いた問題数が多いために記憶が洗練された可能性があげられる．
以上の結果から，類似問題の探索において過去の記憶を利用することで容易にできると考えられる．
==> 最初に戻る
適応アルゴリズムの一手法である免疫アルゴリズムをnTSPへ適用し，その工学的応用に対する可能性について検討した．類似問題としてだまし問題を取り上げ，探索を容易にできる可能性があることを示した．特に，記憶機構を活用することで，動的環境における類似問題の繰り返し解決を必要とする課題に対して有効に機能すると考えられる．複数の問題解決器を基本とするマルチエージェント系の有効なアルゴリズムとしてのIAの利用が期待される．
==> 最初に戻る
==> 最初に戻る
ホームページ へ戻る