Multi-objective Tabu Search (MOTS) — パレート最適解のためのメタヒューリスティクス
- 提唱者
- Hansen, M. P.; building on Glover (1989) Tabu Search
- 年
- 1997
- 種類
- Metaheuristic multi-objective optimization
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Multi-objective Tabu Search (MOTS) は、互いに競合する2つ以上の目的関数を同時に最適化するために、古典的な Tabu Search の枠組みを拡張したメタヒューリスティックアルゴリズムである。単一の最適解ではなく、パレートフロンティア(ある目的関数を改善しようとすると別の目的関数が悪化するような解の集合)の近似を求めるため、工学、物流、オペレーションズリサーチにおける複雑な組み合わせ最適化問題や連続最適化問題に適している。
手法の背後にある直感
複数の目的関数が互いに矛盾するような、起伏の多い地形を探索することを想像してほしい。MOTS は、近傍解へと移動し、循環を避けるために最近訪れた場所の短期記憶リスト(タブーリスト)を保持し、これまでに発見された非劣解のアーカイブを維持することで、この空間をナビゲートする。定期的に、戦略的な多様化により探索をパレートフロンティアの未踏領域に押し出し、有望な領域の活用と全体的な探索のバランスを取る。
歴史学
Multi-objective Tabu Search は、1989年に Fred Glover によって導入された単一目的 Tabu Search を拡張したものである。パレートアーカイブと多目的アスピレーション基準を含む最初の体系的な MOTS 定式化は、1997年の MCDM 会議で M. P. Hansen によって発表された。その後、Gandibleux、Teghem らによる組み合わせ問題向けの変種が形式化され、MOTS は以来、進化的多目的アルゴリズムに対する競争力のある代替手段として、スケジューリング、物流、工学設計に応用されている。
使うべき場面
2つ以上の競合する目的関数(例:コスト対品質、時間対リスク)を持つ組み合わせ問題または混合整数問題に直面しており、厳密解法が計算上実行不可能である場合に MOTS を使用する。網羅的な列挙には探索空間が大きすぎるスケジューリング、車両ルーティング、ネットワーク設計、ポートフォリオ選択問題に優れている。近傍構造が意味を持ち、移動演算子を明確に定義できる場合は、純粋なランダム探索よりも MOTS を優先する。MOTS を使用しない場合:単一目的の問題(通常の Tabu Search で十分)、パレートフロンティアを厳密に列挙できる場合、勾配情報が利用可能で地形が凸状の場合(代わりに数理計画法を使用)、またはリアルタイムの意思決定で確率的変動なしの決定的で再現可能な出力が必要な場合。
限界と注意点
- タブーリストの長さ、近傍の定義、多様化戦略に性能が大きく依存するため、慎重なパラメータ調整が必要である。
- 真のパレートフロンティアへの収束保証はなく、解の質は実行時間と問題構造に依存する。
- 近傍が大きい場合や目的関数評価がコスト高な場合、反復ごとの計算コストが高い。
- パレートアーカイブの維持と更新は、目的関数の数とアーカイブサイズが増加するにつれてコスト高になる可能性がある。
- タブーメカニズムの逐次的なメモリベースの性質により、並列実装は簡単ではない。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- タブーリストにより最近の解の再訪を回避し、複雑な地形での循環リスクを低減する。
- アスピレーション基準により、例外的な改善につながる移動が可能な場合にタブー制限を上書きでき、記憶と柔軟性のバランスを取る。
- 勾配情報を必要としないため、非微分可能、離散的、またはブラックボックスの目的関数に適用可能である。
- 単一の実行でパレートフロンティア全体の近似を生成し、多基準意思決定をサポートする。
- 柔軟な近傍および移動演算子の設計により、問題固有のカスタマイズが可能である。
- 多様化メカニズムにより、局所最適解からの脱出と、より良いパレートフロンティアのカバレッジを可能にする。
応用
- 多目的車両ルーティングおよび物流スケジューリング(コストと配送時間を同時に最小化)
- 二目的プロジェクトスケジューリング:先行制約下でのメイクスパンとリソースコストの最小化
- ポートフォリオ最適化:複数資産クラスにわたる期待リターンとリスクのバランス
- ネットワーク設計:設置コストを最小化しつつ信頼性またはスループットを最大化
- 製造プロセス計画:サイクルタイム、エネルギー使用量、品質指標を共同で最適化
- 環境管理:経済的産出と汚染または生態学的影響のバランス
使い方
使い方
1つ以上の開始解(ランダムに生成されたもの、またはヒューリスティックに構築されたもの)で探索を初期化する。固定長 L の空のタブーリストを設定し、開始個体群から非劣解でパレートアーカイブを初期化する。
現在の解 s の近傍 N(s) を、移動演算子(交換、挿入、摂動)を適用して生成する。すべての近傍解を各目的関数で評価し、進行のための候補を特定する。
タブーフィルタを適用する:最近傍の移動がタブーリストにある場合、それらを排除する。ただし、その近傍解がアスピレーション基準を満たす場合は除く。アスピレーション基準とは、通常、その近傍解が現在のアーカイブメンバーすべてを劣らせるか、少なくとも1つの目的関数で既知の最良値を改善することである。これにより、循環を防ぎ、探索を強制する。
タブーではない最良の近傍解(またはアスピレーション基準の勝者)を次の現在の解として選択する。新しい解が非劣であれば、パレートアーカイブを更新する。新しいエントリによって劣るアーカイブメンバーがあれば削除する。
探索が停滞した場合に多様化戦略を適用する:長期記憶頻度は、まれに訪れる領域を特定する。エリートアーカイブ解からの再開、またはランダムに摂動された解からの再開により、パレートフロンティアのカバレッジを拡張する。
最大反復回数、関数評価回数、または経過 CPU 時間などの停止基準が満たされるまで、近傍生成、フィルタリング、アーカイブのステップを繰り返す。近似されたパレート最適フロンティアとしてパレートアーカイブを返す。
よくある落とし穴
- タブーリストを短すぎると循環を引き起こし、長すぎると探索を過度に制限して良い解を見逃すため、経験的な調整が不可欠である。
- 多様化を怠ると、パレートフロンティアの一地域に早期収束し、不十分な近似を生成する。
- 3つを超える目的関数で MOTS を適用すると、アーカイブ管理と多様性維持が計算上負担になるため、性能が低下する。多目的問題には分解ベースの手法を検討すべきである。
- 一般的な移動演算子を問題固有の設計なしに使用すると、調整された実装と比較して解の質が著しく低下する。
- 収束履歴を調べずに最終アーカイブのみを報告すると、早期の停滞を隠蔽する可能性がある。
よくある質問
MOTS は、複数の目的関数がある場合、タブーリストをどのように扱いますか?
タブーリストは解ではなく移動を格納するため、単一目的 Tabu Search と同じように機能する。主な違いは、タブーではない近傍の選択に多目的劣性またはスカラー化関数を使用し、アスピレーション基準は、結果の解が現在のアーカイブメンバーすべてによって劣らない場合にタブー移動を許可するように再定義される点である。
パレートアーカイブとは何ですか?また、どのくらいの大きさであるべきですか?
パレートアーカイブは、探索中に発見されたすべての非劣解を格納する。その最大サイズは通常、メモリと更新コストを管理可能に保つために制限されている(例:100〜500解)。アーカイブがいっぱいの場合、クラウディング距離またはグリッドベースのプルーニングにより、過密な領域の解が削除され、多様性が維持される。
MOTS は多目的問題において NSGA-II とどのように比較されますか?
NSGA-II は、交差と突然変異を伴う個体群ベースの進化アプローチを使用しており、探索初期の全体的な探索に優れている。MOTS は近傍移動とメモリに依存しており、多くの場合、より細かい局所探索品質を提供する。実際には、MOTS は強い近傍構造を持つ組み合わせ問題で優位性を示す傾向があり、NSGA-II は連続問題でより広く使用されている。
通常、いくつの反復が必要ですか?
普遍的な規則はない。一般的な慣行は、反復ではなく関数評価を予算計上することである(通常、問題サイズに応じて10,000〜100,000評価)。解の質とパレートフロンティアの安定性を評価するために、複数の独立した開始を実行する。
MOTS は3つ以上の目的関数を扱えますか?
はい、しかし目的関数の数が増加して3を超える(目的空間における「次元の呪い」)と、有効性が低下する。4つ以上の目的関数の場合、アーカイブサイズが爆発し、多様性維持が困難になるため、分解ベースまたは指標ベースのアプローチがしばしば好まれる。
関連する手法
参考文献
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
出版物の文献を開くコピーしました。Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
DOI 文献を開くコピーしました。