タブーサーチ

タブーサーチ（英: tabu search）やタブー探索とは、1989年にフレッド・グローバー(Fred Glover)により考案された^[1][2][3]メタヒューリスティックの探索アルゴリズムの一つである。

概要

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

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

アルゴリズムの流れ

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

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

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

パラメータ設定

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

状態近傍

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

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

近傍探索の数

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

タブーリストの記載方法

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

タブーリストのサイズ

タブーリストのサイズは上述の記述と同様の理由であまり大きく設定しないことが推奨される、特に記載内容が厳しい場合はタブーリストのサイズは大きくない方が良い結果が得られることが多い。実験的に大体どのような問題に対してもタブーリストは5～12の値が良いとされており特に7とする場合が多い。

しかし、問題のサイズが大きくなればタブーリストのサイズも大きくするのが直感的には正しいように思えるため、問題のサイズ N  あるいは ${\displaystyle {\sqrt {N}}}$をタブーリストのサイズにすることなども提案されている。

関連項目

• メタヒューリスティクス
• 焼きなまし法
• 遺伝的アルゴリズム

参照

1. Glover, Fred (1986). “Future Paths for Integer Programming and Links to Artificial Intelligence”. Computers and Operations Research 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1. 
2. Glover, Fred (1989). “Tabu Search - Part 1”. ORSA Journal on Computing 1 (2): 190–206. doi:10.1287/ijoc.1.3.190. 
3. Glover, Fred (1990). “Tabu Search - Part 2”. ORSA Journal on Computing 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.