タブーサーチ — 近傍探索型メタヒューリスティック
- 提唱者
- Fred Glover
- 年
- 1989
- 種類
- Local-search metaheuristic
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
タブーサーチは、1989年にフレッド・グローバーによって導入された近傍探索型メタヒューリスティックであり、タブーリスト(最近訪問した解の短期記憶)を使用して循環を防ぎ、局所的最適解から脱出する。最近の決定を逆転させる移動を明示的に禁止することにより、アルゴリズムは探索空間をより広範囲に探索し、願望基準などの長期記憶構造を通じて、大規模で複雑な組み合わせ問題においても大域的最適解に近づくことを目指す。
手法の背後にある直感
暗闇の中で山岳地帯を進み、最も高い頂を見つけようとしていると想像してください。単純な近傍探索型クライマーは常に上り坂を歩き、到達した最も近い丘で立ち往生します。タブーサーチは最近訪れた場所のメモ帳を持ち歩き、たとえ後戻りが魅力的であっても、それらに戻ることを拒否します。最近の移動に関するこの強制的な健忘症は、探索を行き止まりから未踏の領域へと追い出し、単純な近傍探索では決して到達できないはるかに高い地面を発見することを可能にします。
歴史学
タブーサーチは、ORSA Journal on Computingの画期的な1989年の論文でフレッド・グローバーによって導入され、過去の移動の記憶を利用して近傍探索をガイドする戦略として提示された。基礎的なアイデアは、1997年のグローバーとラグナによるシュプリンガーのモノグラフで統合・拡張され、今日でもこの手法の中心である標準的な短期タブーリスト、願望基準、および長期多様化・集約戦略が確立された。導入以来、タブーサーチはオペレーションズリサーチ、スケジューリング、ロジスティクス、組み合わせ設計に広く応用されており、焼きなまし法や遺伝的アルゴリズムと並んで標準的なベンチマークメタヒューリスティックであり続けている。
使うべき場面
タブーサーチは、厳密法では解けないほど解空間が大きく、問題構造が意味のある近傍の定義を可能にする組み合わせ問題および離散最適化問題に適しています。典型的な応用には、スケジューリング、ルーティング、割り当て、シーケンス問題が含まれます。特に、探索ランドスケープに単純な方法を捕らえる多くの局所的最適解がある場合に効果的です。目的関数が微分可能または連続である必要はありません。近傍定義とタブー期間は、特定の問題に合わせて注意深く調整する必要があります。不適切に選択された近傍、または短すぎる/長すぎるタブー期間は、性能を大幅に低下させる可能性があります。探索が空間を十分に探索するには、少なくとも数百回、理想的には1000回以上の反復が必要です。
限界と注意点
- 性能は近傍定義とタブー期間に敏感であり、不適切な選択は探索を捕らえしたり、タブー仕組みにもかかわらず循環させたりする可能性がある。
- 近傍を十分に探索するには最低反復予算(通常1000回以上)が必要であり、反復回数が少なすぎると単純な近傍探索と同等の結果しか得られない。
- タブーリストは完全な解ではなく移動属性を格納するため、本当に良い移動を誤ってブロックしないように願望基準が必要である。
- 厳密ソルバーとは異なり、タブーサーチは最適性の保証を提供せず、初期解または近傍が確率的である場合、実行ごとに結果の品質が変動する可能性がある。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 勾配情報を必要とせずに、タブー仕組みを通じて局所的最適解から脱出する。
- 組み合わせ問題、混合型問題、さらには連続問題にも適用可能 — 正規性やその他の分布特性を仮定しない。
- 複数の時間スケール(短期タブーリスト、長期多様化/集約)でメモリを組み込み、探索空間の体系的な探索を可能にする。
- 厳密法と比較して、大規模インスタンスでは比較的控えめな計算予算で高品質の解を見つけることが多い。
応用
- ジョブショップおよびフローショップスケジューリング — メイクスパンまたは納期遅延を最小化するための操作シーケンスの最適化。
- 車両ルーティング — 容量および時間窓の制約下での効率的な配送ルートの発見。
- 割り当ておよび設備配置 — コストを最小化するためのタスクの資源への割り当てまたは設備の配置。
- グラフ彩色、ネットワーク設計、および通信 — 離散構造最適化問題の解決。
- 特徴選択およびハイパーパラメータ探索 — 機械学習パイプラインにおける離散構成空間の探索。
使い方
使い方
探索は、ランダムに、または貪欲なヒューリスティックで構築できる初期候補解から開始されます。タブーリストは空の固定長キューとして設定され、これまでに発見された最良の解が記録されます。近傍構造(現在の解から1ステップ離れた解を定義する規則)は、特定の問題に対して意味のある方法で定義される必要があります。
現在の解から、定義された近傍内のすべての移動が生成され、目的関数に対して評価されます。各移動は、シーケンス内の2つの要素を交換したり、バイナリ変数を反転したりするような小さな摂動に対応します。近傍は、意味のある探索を可能にするのに十分豊かでありながら、各反復内で扱える程度に小さい必要があります。
各候補移動はタブーリストと照合されます。移動、またはそれを特徴付ける属性がリストに表示されている場合、それはタブーと分類され、禁止されます。ただし、それが願望基準を満たす場合は例外です。通常、結果の解がこれまでに発見された最良の解よりも優れている場合、タブー状態は上書きされ、移動は許可されます。この願望仕組みは、アルゴリズムに循環防止規律を放棄することなく柔軟性を与えます。
すべての非タブー移動(および願望基準を通過するタブー移動)の中から、最も性能の高い移動が選択され実行されます。たとえ目的値が悪化したとしてもです。この悪化を受け入れる意欲こそが、アルゴリズムが局所的最適解から脱出することを可能にするものであり、単純な丘登りと比較した場合のタブーサーチの決定的な特徴です。
移動が実行された後、タブーリストは、行われたばかりの移動の逆(またはその特徴的な属性)を追加することによって更新され、リストがいっぱいの場合、最も古いエントリが削除され、固定長(タブー期間)が維持されます。新しい解が記録された最良の解よりも優れている場合、最良の解が更新されます。オプションの長期記憶構造は、解の頻度または最近性を追跡して、あまり訪問されていない領域への多様化、または有望な領域の集約をガイドすることができます。
アルゴリズムは、最大反復回数、目標目的値、または改善のない固定反復回数などの停止基準が満たされるまで反復を続けます。探索全体で見つかった最良の解が結果として返されます。適切な反復予算の選択は重要です。反復回数が少なすぎると、十分な近傍探索が妨げられます。
よくある落とし穴
- タブー期間を短すぎると循環が再発し、タブー仕組みの目的が無効になる可能性がある。タブー期間は問題サイズに合わせて調整する必要がある。
- タブー期間を長すぎると探索が過度に制限され、改善が含まれる可能性のある領域をアルゴリズムが再訪できなくなる。
- 約1000回未満の反復を実行すると、探索は近傍を十分に探索していないことになる。計算量が限られている場合は、より少ない反復で有用な結果をより速く生成できる焼きなまし法に切り替える。
- 狭すぎる近傍(例:複雑な構造に対する単一の交換移動のみ)を使用すると、浅い探索につながる。近傍が、解空間のすべての有望な領域を接続するのに十分豊かであることを確認する。
- 願望基準を無視すると、その移動がタブーである場合、大域的最適解へのパスが永久にブロックされる可能性がある。少なくとも標準的な最良解の上書きは常に実装する。
よくある質問
タブーサーチは焼きなまし法とどう違うのですか?
どちらの方法も局所的最適解から脱出するために悪化する移動を受け入れますが、仕組みが異なります。焼きなまし法は、冷却温度パラメータによってガイドされ、確率的に悪い移動を受け入れます。タブーサーチは、最近の移動の明示的な記憶によってガイドされ、決定論的に利用可能な最良の非タブー移動を受け入れます。タブーサーチは、構造化された組み合わせ問題では一般により効果的です。焼きなまし法は、連続またはほぼ連続なランドスケープを持つ問題では調整が容易であり、反復予算が小さい場合(約1000回未満)に好まれます。
タブーリストの長さはどのくらいにすべきですか?
タブー期間 — 移動が禁止される反復回数 — は問題に依存します。一般的に引用される開始点は、問題サイズの平方根に比例するタブー期間ですが、これは経験的に調整する必要があります。短すぎるタブー期間は循環を許容し、長すぎるタブー期間は探索を過度に制限します。適応型またはランダム化されたタブー期間戦略は、この選択への感度を減らすことができます。
タブーサーチは、大域的最適解を見つけることを保証しますか?
いいえ。タブーサーチはメタヒューリスティックであり、最適性の保証を提供しません。効率的に高品質の解を見つけることを目指しますが、結果は近傍構造、タブー期間、反復回数、および初期解に依存します。最適性の保証が必要な場合は、整数計画法などの厳密法が必要ですが、厳密法は大規模インスタンスでは計算的に実行困難になる場合があります。
願望基準とは何ですか、そしてなぜそれが必要なのですか?
願望基準は、特別な条件下で移動のタブー状態を上書きする規則です。最も一般的な基準は次のとおりです。タブー移動を実行すると、これまでに発見された最良の解よりも優れた解が得られる場合、タブー制限は解除され、移動は許可されます。この上書きがないと、パスが最近訪問した移動を通過する場合、タブー仕組みは大域的最適解へのパスを永久にブロックする可能性があります。
関連する手法
参考文献
Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
出版物の文献を開くコピーしました。Glover, F. & Laguna, M. (1997). Tabu Search. Springer.
ISBN:9780792349907コピーしました。