Skip to content
検索結果に戻る

ロバストタブーサーチ — 不確実性に対するロバスト性を備えたタブーベースのメタヒューリスティック

提唱者
Glover, F. (Tabu Search); robustness extensions by various authors
年
1989 (TS); robust variant ~2000s
種類
Metaheuristic with robustness mechanism
系統
Simulation / optimization

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

文字サイズ

何をする手法か?

ロバストタブーサーチ(RTS)は、候補解を名目上の目的値だけでなく、不確実性下での性能でも評価することにより、古典的なタブーサーチメタヒューリスティックを拡張したものです。単一シナリオの最良解を求めるのではなく、RTSは複数のシナリオまたは実現にわたる性能の良い解を求め、ピーク最適性を信頼性と引き換えにします。

手法の背後にある直感

古典的なタブーサーチは、最近訪問した移動を禁止し、近傍探索を通じて探索をガイドすることにより、優れた解を見つけます。しかし実際には、現実世界の入力(コスト、需要、移動時間など)は変動します。仮定値の下で最適に見える解は、現実が乖離した場合に性能が悪くなる可能性があります。ロバストタブーサーチは、ロバスト性基準を評価関数に直接組み込みます。各候補解は複数のシナリオ(サンプリングまたは列挙)で評価され、探索は安定した低分散の性能を持つ解を優先します。これにより、事後的な再最適化を必要とせずに、最終的な解はパラメータ変動に対して回復力を持つようになります。

歴史学

タブーサーチは、1989年から1990年にかけてフレッド・グローバーによって導入された、最近逆転した移動を禁止することで局所最適解から脱出するメモリベースのメタヒューリスティックです。ロバストな拡張は、ロバスト最適化への関心の高まりとともに、1990年代後半から2000年代にかけて登場しました。研究者たちは、シナリオベースおよび最悪ケースの評価をTS近傍評価に組み込み、不確実性下での工学および物流問題の実用的なツールとしてロバストタブーサーチを生み出しました。

使うべき場面

主要な入力パラメータが不確実または変動する場合(ルーティング、スケジューリング、割り当て、または需要またはコストの不確実性下でのネットワーク設計問題など)の組み合わせまたは離散最適化問題に直面した場合に、ロバストタブーサーチを使用します。展開後の再最適化のコストが高い場合、または実装前に解の信頼性を証明する必要がある場合に特に適しています。問題が純粋に決定論的である場合(古典的なタブーサーチで十分)、シナリオセットが計算不能なほど大きすぎて効率的にサンプリングできない場合、または問題が滑らかで凸状である場合(勾配ベースのロバスト手法の方が高速で信頼性が高い)は、RTSを避けてください。

限界と注意点

  • 大規模なシナリオセット全体でロバスト性を評価すると、イテレーションあたりの計算コストが|S|倍になり、実行不可能になる可能性があります。
  • ロバスト性の質はシナリオセットの質に大きく依存します。シナリオカバレッジが不十分だと、誤った自信につながる可能性があります。
  • タブーリストのテナーと近傍サイズは、調整が必要な問題固有のハイパーパラメータです。
  • 大域的最適性または解の質の証明を保証しません。

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

強み

  • 事後的なロバスト性チェックを必要とせずに、入力変動に対してロバストな解を見つけます。
  • 困難な組み合わせ問題(スケジューリング、VRP、TSPのバリアント)に対するタブーサーチの強力な経験的性能を継承します。
  • 柔軟なロバスト性基準:ミニマックス、期待値、平均分散、およびパーセンタイルベースの目的をサポートします。
  • 問題の凸性または微分可能性を必要としない — ブラックボックスおよび離散目的にも適用可能。
  • タブーメカニズムは、局所的にロバストだが全体的には平凡な解に閉じ込められるのを防ぎます。

応用

  • 確率的移動時間または顧客需要下でのロバストな車両ルーティング
  • 不確実な処理時間を持つジョブショップおよびフローショップスケジューリング
  • 需要変動下でのネットワーク設計および容量計画
  • 不確実なサプライヤーリードタイムまたはコストを持つサプライチェーン最適化
  • 干渉の不確実性下での通信における周波数割り当て
  • 組み合わせ制約を使用した不確実な資産収益率によるポートフォリオ最適化

使い方

使い方

1

組み合わせ最適化問題または連続最適化問題を定義し、不確実なパラメータ(例:需要、コスト、処理時間)を特定し、妥当な実現を表すシナリオセットSを指定します(分布からのサンプリングまたは離散的な不確実性セットの構築による)。ロバスト性目的を設定します:最悪ケースコストの最小化、期待コストの最小化、または平均と分散の重み付き組み合わせの最小化。

2

探索中に遭遇する各候補解xについて、すべてのシナリオs∈Sの下でその目的f(x,s)を評価します。ロバスト性尺度R(x)を計算します — 例えば、ミニマックスロバスト性の場合はR(x) = max_{s∈S} f(x,s)、平均分散ロバスト性の場合はR(x) = E[f(x,s)] + λ * Var[f(x,s)]。これは、古典的なタブーサーチで使用される単一の名目評価に取って代わります。

3

現在の解xの近傍N(x)を、すべての実行可能な移動(交換、挿入、逆転など)を適用することにより生成します。タブーリストに現在載っている移動を除き、アスピレーション基準が満たされない限り、各近傍x'のR(x')を評価します。最良のロバスト性値R(x*)を持つ近傍x*を選択します。

4

x*に移動し、適用された移動の逆をテナーt(通常5〜20イテレーション)とともにタブーリストに記録します。タブーリストはサイクリングを防ぎ、探索を促進します。アスピレーション基準 — 例えば、タブー移動が全体で最良のロバスト解を生成する場合にその移動を受け入れるなど — は、タブー制限を上回る場合があります。

5

R(x*)が現在の最良値を改善した場合、最良既知のロバスト解を更新します。最大イテレーション数、経過時間、または所定のステップ数での改善がないなどの停止基準が満たされるまで、イテレーションを続けます。見つかった最良のロバスト解とそのシナリオごとの性能プロファイルを返します。

よくある落とし穴

  • 少なすぎるシナリオを使用すると、真の不確実性を過小評価し、実際には失敗するロバストに見える解を生成します。
  • ロバストタブーサーチと確率的タブーサーチの混同:ロバスト最適化は最悪ケースへの暴露を最小化しますが、確率的TSは期待値を近似するためにサンプリングします — 目的と解釈は異なります。
  • 確率が無視できるほど小さい最悪ケースシナリオにミニマックスロバスト性を適用すると、不必要なコストで過度に保守的な解につながります。
  • アスピレーション基準を無視すると、タブー移動を含むことで大域的にロバストな解を見逃す可能性があります。
  • タブーテナーが高すぎると過度の制限が生じ、低すぎるとサイクリングが発生します — どちらも解の質を低下させます。

よくある質問

ロバストタブーサーチは確率的タブーサーチとどう違うのですか?

確率的タブーサーチは通常、検索手順自体内でランダムサンプリング(例:確率的受容またはランダム近傍サンプリング)を使用して期待値を近似します。ロバストタブーサーチは、定義された不確実性セット上で評価される最悪ケースまたは平均分散性能などのロバスト性基準を明示的に最適化します。ロバストTSの目標は、期待性能だけでなく、シナリオ全体での解の安定性です。

シナリオセットSはどのくらいの大きさであるべきですか?

普遍的な規則はありません。離散的な不確実性セットの場合は、実行可能であればすべての信頼できるシナリオを列挙します。連続分布の場合は、50〜500のサンプリングされたシナリオで十分なカバレッジが得られることがよくあります。ラテン超方格サンプリングなどの分散削減技術は、効率を向上させることができます。最終的なシナリオ数を決定する前に、|S|に対する感度分析が推奨されます。

ロバストタブーサーチは多目的問題に対処できますか?

はい。多目的タブーサーチフレームワークと組み合わせると、ロバスト性は追加の目的または制約になります。 (名目性能、ロバスト性)のパレートフロントを探索でき、リスク許容型とリスク回避型のオプションの間で選択する必要があるステークホルダーに役立つ、最適性と信頼性をトレードオフする一連の解を生成します。

どのロバスト性尺度を選択すべきですか?

ミニマックス(最悪ケース)は、障害が壊滅的であり、低確率の悪い結果でさえ許容できない場合に適切です。期待値はリスク中立の意思決定者に適しています。平均分散は、平均性能と変動性をバランスさせ、工学設計で一般的です。Value-at-Risk(VaR)またはConditional VaRメトリックは、パーセンタイルベースの保証が重要な金融および物流アプリケーションで使用されます。

ロバストタブーサーチは非常に大規模なインスタンスに適していますか?

シナリオ評価コストによります。各f(x,s)評価が安価(ミリ秒)であれば、数百のシナリオに対するロバスト性は、大規模なインスタンスでも実行可能です。各評価にシミュレーションまたは高価なソルバー呼び出しが必要な場合は、積極的なシナリオ削減または代理モデルが必要になります。スレッドまたはマシン全体でのシナリオの並列評価は、一般的な緩和策です。

関連する手法

参考文献

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    DOI 文献を開く
    コピーしました。
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

    出版物の文献を開く
    コピーしました。