タブーサーチ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

タブーサーチ（タブー探索ともいう）はメタヒューリスティック解法の一つである、1989年にフレッド・グローバー(Fred Glover)により考案された。

[編集] 概要

タブーサーチは同じメタヒューリスティクスの遺伝的アルゴリズムや焼きなまし法が特定の自然現象を模倣した手法であるのに対し、この手法は人工知能の概念に基づいた局所探索法の一般化として認知されている。

この手法は状態の近傍を複数探索しその中で最も良い近傍状態に遷移する、このときタブーリストと呼ばれるキューに状態遷移時の操作を書き込む。このタブーリストに書き込まれている操作は行わないことにより状態がループするのを防ぐことで探索が停滞せずに最適解を探索する。ここで重要なのはタブーリストに載っていない場合は状態が悪くなっても遷移を行うことである。このことにより局所解で探索が停滞するのを防いでいる。

[編集] アルゴリズムの流れ

アルゴリズムの流れを以下に示す。

初期状態 S₀ を決定する（通常はランダム）。
最良状態 S_b と現在状態 S を作成し、とりあえず S₀ を両方に記録しておく。
S の近傍を複数（M 個）選び、その中で最も成績の良い近傍を S' とおく（この比較にS は入らないことに注意）
状態遷移を判定（以下のどちらか）
1. もしS' がS_b より良い値ならS_b =S =S' とする。このときタブーリストにS →S' になる操作が記載されている場合、その部分をタブーリストの一番新しい記載に移動する。
2. もしS' がS_b より悪い値なら、S →S' になる操作がタブーリストに記載さているかどうかを確認する。記載されていないならタブーリストにS →S' となる操作を記載して S =S' とする。このときタブーリストのサイズが上限を越えているなら、一番古い記載を削除する。
終了条件が満たされるまで 3. 以下の操作を繰り返し、最終的にS_b を解として出力する。

この方法は他のメタヒューリスティックと違い最良解は必ず保存することがアルゴリズム内に組み込まれている。この理由はタブーサーチにおける状態は常に遷移し続けている（タブーリストの記載方法しだいでは停滞することもあるが、それはやってはならない操作とされる）ため最終状態が最良状態である可能性が極めて低いからである。

[編集] パラメータ設定

タブーサーチにおいて設定するパラメータは以下の通りである。他のメタヒューリスティック同様パラメータの調整は科学というよりは技能的なものである。

[編集] 状態近傍

焼きなまし法と同様にタブーサーチにおいて近傍の定義は非常に重要になってくる、特にタブーサーチの場合複数の近傍が存在していることが前提なので設定次第では探索が停滞したり、最適解に到達不可能になる可能性もある。

基本的には探索グラフで表した場合、ほぼ同様のエネルギー状態になるようにおくことが好まれる、巡回セールスマン問題の場合なら隣り合う都市を入れ換えるなどである。

[編集] 近傍探索の数

S の近傍を探索する数 M は多くした場合、非常に解の改善が早くなる一方、局所解に陥りやすくなる。逆に M 小さくした場合局所解には陥りにくくなるが解の精度は大きく劣る可能性がある。ただし M を大きくしすぎると少数の状態が常に採択され、その状態への遷移が全てタブーリストに記載されている場合は探索が停滞してしまうので、常に別状態へ遷移する可能性は残しておくような範囲で設定しなければならない。

[編集] タブーリストの記載方法

タブーリストにはS →S' となる状態を記載する、この記載方法は単純にS の中身を記載するのではなくS とS' の差分を記載することになるが、この場合いくつかの方法が考えられる。例えば近傍探索がグラフの辺を入れ換えるような操作の場合、入れ換えた辺が交換されるのを防ぐか、入れ換えられた辺がまた選ばれるのを防ぐか、両方起こるのを防ぐか、どちらかが起こるのを防ぐかなどである。厳しくした方がループを防ぎやすくなるが、ループを防ぐことが最適解の到達に役立つとは必ずしもいえない、例えば一つ前の状態の別の遷移が最適解であることなどがあるためである。