Skip to content
検索結果に戻る

確率的タブー探索 — メモリを備えたランダム化メタヒューリスティック

提唱者
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
年
1990s
種類
Stochastic metaheuristic optimizer
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

確率的タブー探索(STS)は、古典的なタブー探索を拡張し、近傍探索および移動選択フェーズにランダム性を導入したものです。最近訪問した解を禁止するタブーメモリと、確率的受容またはランダム候補サンプリングを組み合わせることで、STSは局所最適解からより効果的に脱出し、決定論的なTSでは travers できないような険しい解空間を探索します。

手法の背後にある直感

古典的なタブー探索は、サイクリングを防ぐために短期メモリ(タブーリスト)を使用し、常に許可された最良の近傍に移動することで解空間をナビゲートします。しかし実際には、許可された最良の移動でもアルゴリズムが解空間の領域に閉じ込められる可能性があります。確率的タブー探索は、制御されたランダム性を注入します。次の移動は、貪欲に選択するのではなく、候補近傍のセットから確率的に選択され、探索を多様化するためにランダムな摂動が時折導入されます。これにより、TSのメモリ誘導規律は維持され、純粋な決定論的降下法が欠いている探索能力が追加されます。

歴史学

タブー探索は1986年にFred Gloverによって正式に導入され、1989年から1990年にかけて画期的な論文で詳細が説明された。確率的拡張は、大規模問題における決定論的な近傍評価がボトルネックであることが認識された1990年代に出現した。ランダム候補サンプリング、確率的移動受容、ノイズ注入が多様化を改善するために組み込まれ、一般に確率的タブー探索と呼ばれるものにつながった。この技術は、オペレーションズリサーチ、工学設計、機械学習ハイパーパラメータ最適化で広く応用されている。

使うべき場面

決定論的なタブー探索では局所最適解に閉じ込められがちな、険しく多峰性の解空間を持つ組み合わせ問題または連続ブラックボックス最適化問題(例:スケジューリング、ルーティング、特徴選択)を解く際に確率的タブー探索を使用する。特に、完全な近傍評価が計算コストが高く、ランダムなサブサンプリングが必要となる場合に価値がある。問題が凸または単峰性である場合、STSを使用しない — 勾配ベースまたは厳密な方法の方が高速で最適である。大域的最適性を保証する必要がある場合にも避けるべきである。STSは、ヒューリスティックな最良発見解を超える収束保証を提供しない。また、目的関数を完全に評価するコストが低く、網羅的な近傍探索を備えた決定論的なTSが実行可能な場合も避ける。

限界と注意点

  • 大域的最適解を見つける理論的保証はない。解の質はパラメータ設定に大きく依存する。
  • タブー期間と候補リストのサイズは問題固有の調整が必要。不適切な選択は、早期収束または遅い進歩につながる。
  • 確率的な実行は、固定された乱数シードなしでは再現不可能であり、ベンチマークと監査を複雑にする。
  • メモリのオーバーヘッドはタブーリストのサイズとともに増加する。大規模な解空間には、属性ベースのタブー表現が必要。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • メモリと確率的探索を組み合わせることで、決定論的なタブー探索よりも効果的に局所最適解から脱出する。
  • 候補のサブサンプリングにより大規模な近傍構造にスケールし、反復ごとの計算コストを削減する。
  • タブーメモリは、純粋な確率的手法(例:ランダムリスタートヒルクライミング)の一般的な失敗モードであるサイクリングを防ぐ。
  • 柔軟なフレームワーク:強化学習と多様化のバランスをとるために、摂動確率とタブー期間を調整できる。
  • 組み合わせ問題(TSP、スケジューリング)と連続最適化の両方に、わずかな適応で適用可能。

応用

  • 不確実な需要下での車両ルーティングと物流最適化
  • 確率的な処理時間を持つジョブショップおよびオープンスロップスケジューリング
  • 高次元機械学習データセットにおける特徴選択
  • ネットワーク設計とトポロジー最適化
  • 組み合わせ資産選択制約付きポートフォリオ最適化
  • 複雑なシミュレーションモデルのハイパーパラメータチューニング

使い方

使い方

1

初期解 x0 を生成する(ランダムまたはヒューリスティック)。タブーリスト T を空に設定し、タブー期間 tau、反復上限 I_max、および確率的パラメータ(例:候補リストサイズ k、摂動確率 p_perturb)を定義する。

2

各反復において、すべての近傍を評価するのではなく、完全な近傍 N(x_current) のサブセット N_s をランダムにサンプリングする。これにより、反復ごとのコストが削減され、空間のどの領域が探索されるかについての確率性が導入される。

3

次の解 x_next を N_s から選択する:(a)確率 1-p_perturb で最良の非タブー候補を選択する、または(b)確率 p_perturb で多様化のためにランダムな非タブー候補を選択する。x_next が既知の最良解を改善する場合、期待基準がタブー状態を上書きする可能性がある。

4

現在の解 x_current(または移動属性)をタブーリスト T に追加する。|T| > tau の場合、最も古いエントリを削除する。f(x_next) < f(x_best) の場合、最良の解 x_best を更新する。

5

neighborhood_sampling から tabu_update までを反復し、I_max 反復に達するか、目標目的値が満たされるか、または忍耐ウィンドウで改善が発生しなくなるまで繰り返す。最終解として x_best を返す。

よくある落とし穴

  • タブー期間が短すぎると、タブーリストがあるにもかかわらずサイクリングを許してしまう。長すぎると、有望な領域を不必要にブロックする。
  • 候補リストが小さすぎると(積極的なサブサンプリング)、探索が良い近傍を見逃す可能性がある。
  • 期待基準を無視すると、タブーであるグローバルに改善する移動を受け入れることをアルゴリズムが拒否してしまう。
  • 単一の実行のみを報告し、複数のリスタートやシードを使用しないと、典型的な解の質についての誤解を招く。
  • 確率的タブー探索と焼きなまし法を混同する:どちらも確率的だが、根本的に異なる。STSは明示的なメモリを使用するのに対し、SAはメモリなしで温度ベースの確率的受容を使用する。

よくある質問

確率的タブー探索は焼きなまし法とどのように異なりますか?

どちらも確率的メタヒューリスティックですが、STSは明示的なタブーメモリを使用して最近訪問した移動を禁止し、サイクリングを防ぎます。SAにはメモリがなく、時間とともに減少する確率(温度スケジュール)で悪い解を受け入れます。STSは、移動の再訪が明確な危険である組み合わせ問題では一般的に強力です。

いくつの反復(I_max)を実行すべきですか?

普遍的なルールはありません。一般的な実践は、問題サイズに比例した予算で複数の独立した試行(例:10〜30リスタート)を実行し、最良の結果と平均結果を報告することです。ベンチマークの場合、競合する方法で使用される総関数評価予算に合わせます。

確率的タブー探索は連続変数も扱えますか?

はい、ただし、連続的な近傍(例:現在の解の周りのガウス摂動)と、タブーリストの適切な属性(例:領域または方向)を定義する必要があります。ほとんどのSTS文献は組み合わせ問題を対象としています。連続空間の場合、微分進化またはCMA-ESがより自然な代替手段となることが多いです。

期待基準の役割は何ですか?

期待基準は、受け入れる移動がこれまでに発見された最良の解よりも優れた解をもたらす場合、その移動のタブー状態を上書きします。期待基準がないと、アルゴリズムはタブーであるグローバルに改善する移動を永久に拒否する可能性があり、解の質を著しく制限します。

再現性のために乱数シードを固定すべきですか?

はい、再現性を確保するために研究結果を報告する際にはシードを固定してください。実際には、複数のシードで実行し、統計情報(平均、最良、標準偏差)を報告して、確率的な解空間全体でのアルゴリズムパフォーマンスの信頼できる全体像を提供してください。

関連する手法

参考文献

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    DOI 文献を開く
    コピーしました。
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

    DOI 文献を開く
    コピーしました。