Skip to content
検索結果に戻る

Multi-Objective Simulated Annealing (MOSA)

提唱者
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
年
1992–1998
種類
Metaheuristic / Pareto-based optimizer
系統
Simulation / optimization

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

文字サイズ

何をする手法か?

Multi-Objective Simulated Annealing (MOSA) は、古典的な焼きなまし法メタヒューリスティックを、2つ以上の競合する目的関数を持つ問題に拡張したものである。単一の最適解に収束する代わりに、MOSA は確率的に解空間を探索し、支配されない(パレート最適)解のアーカイブを維持することで、意思決定者に単一の規定された解ではなく、多様なトレードオフフロントを提供する。

手法の背後にある直感

古典的な焼きなまし法は、金属の制御冷却を模倣して局所最適解からの脱出を図る。高温では劣る解を時折受け入れ、温度が低下するにつれて選択性を高める。MOSA は、この同じ確率的脱出メカニズムを複数の目的関数に同時に適用する。候補解が一部の目的を悪化させ、他の目的を改善する場合、支配関係ロジックによってパレートアーカイブに入るかどうかが決定される。冷却スケジュールは徐々にランダム性を低下させ、探索をパレートフロンティアの近くに集中させる。その結果、勾配情報や凸性の仮定を必要とせずに到達された真のパレートフロントの近似が得られる。

歴史学

焼きなまし法は 1983 年に Kirkpatrick らによって導入された。Serafini (1992) は、それを多目的問題に拡張することを正式に提案した最初の一人であった。Czyzak と Jaszkiewicz (1998) は Pareto Simulated Annealing (PSA) を開発し、パレートアーカイブを中心的な出力構造として確立し、今日広く採用されている受け入れ基準の定式化を提供した。MOSA はその後、工学設計、スケジューリング、ロジスティクスに応用されている。

使うべき場面

2つ以上の競合する目的関数と、連続または組み合わせの決定変数を持つ最適化問題に直面している場合、特に目的関数のランドスケープが非凸、多峰性、または勾配フリーの場合に使用する。スケジューリング、ルーティング、工学設計、リソース割り当て問題など、単一の重み付け集約よりも明示的なトレードオフフロントがより有用な問題に適している。不確実性定量化ではなく最適化が必要な場合は、純粋な確率的モンテカルロ法よりも MOSA を優先する。単一目的の問題(古典的な SA で十分)、パレートフロントを正確に見つける必要がある場合(小規模問題では厳密なアルゴリズムの方が良い)、目的関数の数が約5を超える場合(超体積ベースの方法の方がスケールが良い)、または目的関数の評価が呼び出しごとに非常に高価な場合(代理モデルベースの方法が望ましい)には、MOSA を使用しない。

限界と注意点

  • 解の質とパレートフロントのカバレッジは、初期温度、冷却率、近傍演算子の選択に敏感であり、問題固有の調整が必要である。
  • 高品質なパレートフロントへの収束には多くの目的関数評価が必要となる場合があり、高価なブラックボックスシミュレーションでは遅くなる。
  • パレートアーカイブの維持と更新にはオーバーヘッドが伴い、アーカイブが大きくなるとメモリと比較コストが増加する可能性がある。
  • 母集団ベースの方法(例:NSGA-II)とは異なり、基本的な MOSA の単一軌道性質は、パレートフロントの不均一なカバレッジを生じる可能性がある。
  • 理論的な収束保証は無限に遅い冷却スケジュールを必要とするが、これは現実的ではない。有限のスケジュールは最適性の保証を犠牲にする。

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

強み

  • 勾配情報が不要で、非凸、不連続、多峰性の目的関数ランドスケープを扱える。
  • 劣る解の確率的受け入れにより、純粋に貪欲なアプローチを閉じ込める局所的なパレートフロントからの脱出が可能になる。
  • 単一の実行で完全なパレートフロントの多様な近似を生成し、意思決定者に明示的なトレードオフオプションを提供する。
  • 実装が容易であり、冷却スケジュールは探索と活用のバランスを調整するための直感的なパラメータを提供する。
  • 連続および組み合わせ最適化問題の両方に、最小限の再定式化で適用可能である。

応用

  • 多目的ジョブショップおよびフローショップスケジューリング(メイクスパンと遅延時間の同時最小化)
  • コストと信頼性を目的とするネットワーク設計およびルーティング問題
  • 工学設計最適化(例:構造部品の重量と応力の最小化)
  • 期待リターンとリスクのバランスをとるポートフォリオ最適化
  • 経済的および環境的目標が競合する土地利用および空間計画
  • コスト、カバレッジ、サービス品質のバランスをとるヘルスケアリソース配分

使い方

使い方

1

初期解(ランダムまたはヒューリスティック)を生成し、広範な探索を可能にするのに十分に高い開始温度 T_0 を設定し、見つかった支配されない解をパレートアーカイブに初期化し、停止基準(最大反復回数または最小温度閾値)を定義する。

2

問題構造に適した近傍演算子(例:連続変数に対するスワップ、挿入、またはガウス摂動)を使用して、現在の解を摂動させ、1つ以上の候補近傍解を生成する。

3

候補近傍解のすべての目的関数を評価する。現在の解およびパレートアーカイブ内の解と比較して、それが支配するか、支配されるか、または支配されないかを決定する。支配されない候補はアーカイブに追加され、支配されたアーカイブメンバーは削除される。

4

多目的受け入れ基準を適用する。近傍解が現在の解に対して支配されない場合、それは受け入れられる。支配される場合でも、P = exp(−ΔF / T) の確率で受け入れられる可能性がある。ここで ΔF は目的関数の悪化を集約するもので、局所的なパレートフロントからの脱出を可能にする。

数式
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

冷却スケジュールに従って温度を下げる。一般的には幾何学的冷却:T_{k+1} = α · T_k (α ∈ (0.8, 0.99))。温度が低いほど劣る移動の受け入れが狭まり、パレートフロントの有望な領域の近くでの探索が徐々に強化される。

数式
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

最終的なパレートアーカイブを結果として返す。後処理で蓄積された可能性のある支配された解を枝刈りし、意思決定者による選択のためにパレート最適フロントの離散近似としてアーカイブを提示する。

よくある落とし穴

  • 初期温度を低く設定しすぎるとパレートフロントの局所的な領域に早期収束するため、常に T_0 を調整して初期受け入れ率を約70〜90%にする。
  • 冷却率 α を 1.0 に近づけすぎると実行時間が長くなりすぎる。0 に近づけすぎると、パレートフロントが十分に探索される前に急速に収束する。
  • 受け入れ確率の ΔF を目的関数の差の単純な合計で定義すると、比較不可能な尺度を混合してしまう。集約する前に各目的関数を正規化する。
  • アーカイブから支配された解を定期的に削除することを怠ると、アーカイブが肥大化し、最終的な出力の質が低下する。
  • 単一実行での成功の評価は、確率的な変動を考慮すると誤解を招く。常に複数の独立した実行の結果を集約する。

よくある質問

MOSA は NSGA-II とどのように異なりますか?

NSGA-II は、交差、突然変異、非支配ソートを使用して解のセットを同時に進化させる母集団ベースの進化アルゴリズムです。MOSA は、確率的な移動を使用して一度に1つの解を探索する軌道ベースの方法です。MOSA は実装が簡単で、組み合わせ問題に適していますが、NSGA-II は一般的に連続問題に対してより優れたパレートフロントカバレッジを提供し、より予測可能にスケールします。

初期温度 T_0 はどのように設定すべきですか?

一般的なヒューリスティックは、短い予備段階を実行し、ランダムな近傍移動の約80%が受け入れられるように T_0 を選択することです。これにより、開始時の広範な探索が保証されます。適切な温度スケールは目的関数値の違いの大きさに依存するため、問題固有の調整が推奨されます。

MOSA は 2 つ以上の目的を扱えますか?

はい、ただし目的関数の数が増えるにつれて性能は低下します。パレートアーカイブ管理のコストが増加し、支配されない解の割合が急速に増加するため、受け入れ基準の識別力が低下します。4つまたは5つを超える目的を持つ問題では、一般的に超体積指標ベースまたは分解ベースの方法(例:MOEA/D)が好まれます。

アルゴリズムをいつ停止すればよいかわかりませんか?

一般的な停止基準には、最小温度への到達、最大反復回数予算の枯渇、または指定された反復回数にわたるパレートアーカイブの超体積指標の改善が見られないことなどが含まれます。実際には、異なる反復回数予算での複数の実行にわたるアーカイブの品質を比較することが、収束を診断する信頼性の高い方法です。

MOSA は高価なシミュレーションモデルに適していますか?

一般的には修正なしでは適していません。各反復には少なくとも1回の目的関数評価が必要であり、MOSA は通常、良好なパレートフロント近似のために数千回の反復を必要とします。各評価が高価なシミュレーションを伴う場合、MOSA の代理モデル支援バージョン(メタモデルを使用して目的関数を近似する)が好まれます。

関連する手法

参考文献

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    DOI 文献を開く
    コピーしました。
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

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