タブーサーチ

タブーサーチとは

タブーサーチは、1989年にフレッド・グローバーによって考案されたメタヒューリスティック探索アルゴリズムです。これは、人工知能の概念に基づいた局所探索法を一般化したものであり、遺伝的アルゴリズムや焼きなまし法といった他のメタヒューリスティクスと同様に、最適解を効率的に探索するために用いられます。

探索の仕組み

タブーサーチは、現在の状態の近傍を複数探索し、その中で最も良い状態へ遷移するプロセスを繰り返します。この際、過去に訪れた状態への逆戻りを防ぐために、「タブーリスト」と呼ばれる記憶領域を活用します。タブーリストには、直近の遷移操作が記録されており、リストに載っている操作は一定期間禁止されます。これにより、探索が同じ場所をループすることなく、より広範囲な解空間を探すことが可能になります。

タブーサーチの重要な点は、たとえ一時的に状態が悪化するような遷移であっても、タブーリストにない場合は積極的に受け入れることです。この仕組みが、局所的な最適解に探索が停滞してしまうのを防ぎ、より良い解への到達を可能にします。

アルゴリズムの流れ

1. 初期状態の設定: ランダムに初期状態S0を決定します。
2. 最良状態と現在状態の記録: 最良状態Sbと現在状態Sを準備し、初期状態S0を両方に記録します。
3. 近傍の探索と評価: 現在状態Sの近傍を複数（M個）探索し、その中で最も良い状態をS'とします。この時、S自身は比較対象に含まれないことに注意してください。
4. 状態遷移の判定:
もしS'がSbよりも良い状態であれば、SbとSをS'で更新します。このとき、SからS'への遷移操作がタブーリストに記載されている場合は、その記載をリストの最新位置に移動します。
もしS'がSbよりも悪い状態であれば、SからS'への遷移操作がタブーリストに記載されていないかを確認します。記載されていなければ、その操作をタブーリストに追加し、SをS'で更新します。この際、タブーリストのサイズが上限を超えている場合は、最も古い記載を削除します。
5. 終了条件の確認: 終了条件が満たされるまで、ステップ3と4を繰り返します。最終的に最良状態Sbを解として出力します。

他のメタヒューリスティクスと異なり、タブーサーチでは最良解がアルゴリズム内に必ず保存される点が特徴です。これは、タブーサーチの状態が常に遷移し続けるため、最終状態が必ずしも最良であるとは限らないためです。

パラメータ設定

タブーサーチの性能は、以下のパラメータ設定に大きく左右されます。これらのパラメータ調整は、科学的なアプローチよりも経験的な側面が強いです。

状態近傍: 探索する近傍の定義は非常に重要です。特にタブーサーチでは、複数の近傍が存在することが前提となるため、設定次第で探索が停滞したり、最適解に到達不可能になったりする可能性があります。基本的には、探索グラフ上でほぼ同じエネルギー状態になるような近傍を設定するのが一般的です。例えば、巡回セールスマン問題では、隣接する都市を入れ替えるなどの操作が用いられます。
近傍探索数: 近傍を探索する数Mを大きくすると、解の改善は早くなりますが、局所解に陥りやすくなる傾向があります。一方、Mを小さくすると局所解に陥りにくくなりますが、解の精度が劣る可能性があります。Mを大きくしすぎると、少数の状態が常に選択され、その状態への遷移が全てタブーリストに記載されてしまう場合、探索が停滞します。したがって、常に別の状態へ遷移する可能性を残しておくような範囲でMを設定する必要があります。
タブーリストの記載方法: タブーリストにはSからS'への状態遷移を記載しますが、この際、SとS'の差分を記録します。この差分の記録方法にはいくつかの選択肢があります。例えば、近傍探索がグラフの辺を入れ替える操作の場合、入れ替えた辺が再交換されるのを防ぐか、入れ替えられた辺が再び選ばれるのを防ぐか、両方を防ぐか、いずれかを防ぐかなど、様々な方法が考えられます。タブーリストの制限を厳しくするとループを防ぎやすくなりますが、それが必ずしも最適解の発見に繋がるとは限りません。一つ前の状態からの別の遷移が最適解となる可能性も考慮する必要があります。
タブーリストのサイズ: タブーリストのサイズは、上記のような理由から、あまり大きく設定しないことが推奨されます。特に記載内容が厳しい場合は、リストサイズを小さくした方が良い結果が得られることが多いです。経験的に、多くの問題において、タブーリストのサイズは5から12の値が良いとされており、特に7が推奨されることが多いです。しかし、問題のサイズが大きくなるにつれて、タブーリストのサイズを大きくすることが直感的に正しいと思われるかもしれません。したがって、問題のサイズNまたは√Nをタブーリストのサイズにするという提案もされています。

タブーサーチ