多目的粒子群最適化(MOPSO)
- 提唱者
- Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
- 年
- 2004
- 種類
- Population-based swarm metaheuristic
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
多目的粒子群最適化(MOPSO)は、複数の相反する目的関数を同時に扱うために、オリジナルの粒子群最適化(PSO)を拡張した、群知能メタヒューリスティック手法である。外部パレートアーカイブを維持し、支配に基づく選択を用いて、事前の選好情報なしに候補解の集団を真のパレートフロントへと導く。
手法の背後にある直感
鳥の群れが、一度にすべてを登ることができない異なる高さの複数の丘がある風景の中で餌を求めて集団で探索している様子を想像してください。一方の丘で高度を上げることが、しばしばもう一方の丘で後退することを意味します。MOPSOは、この多次元的なトレードオフ空間に粒子の群れを放ちます。各粒子は自身の非支配的な最良位置を記憶し、これまでに発見された全体的な非支配的な解の外部アーカイブから学習します。個人の記憶、社会的学習、および制御されたランダム性を組み合わせることで、群れは徐々に完全なパレートフロントをマッピングし、単一の妥協点ではなく、効率的なトレードオフの完全なスペクトルを明らかにします。
歴史学
粒子群最適化は、鳥の群れの社会的行動に触発され、1995年にKennedyとEberhartによって導入された。広く採用された最初の多目的拡張であるMOPSOは、2004年にCoello Coello、Pulido、Lechugaによって提案され、外部パレートアーカイブとハイパーキューブベースのリーダー選択を導入した。その後の変種(OMOPSO、dMOPSO、SMPSOなど)は、アーカイブ管理、適応的パラメータ、および制約処理を改良し、MOPSOをNSGA-IIと並ぶ主流のパレートフロント近似アルゴリズムとして確立した。
使うべき場面
2つ以上の相反する目的を持つ連続最適化問題に直面しており、単一の解ではなく完全なパレートフロントを近似する必要がある場合にMOPSOを使用する。工学設計、サプライチェーン、エネルギーシステム、ハイパーパラメータチューニングなど、目的関数の評価が中程度にコストがかかり、決定空間が連続である場合に優れている。組み合わせ問題または混合整数問題にはNSGA-IIまたはNSGA-IIIを、目的関数が滑らかで微分可能である場合は勾配ベースの多目的手法を優先する。目的関数の数が5〜7を超える場合はMOPSOを使用しない。多目的問題(例:NSGA-III、MOEA/D)には、特殊な多目的アルゴリズムが必要である。また、各関数評価が非常に高価な場合(100未満の評価しか利用できない場合)は避ける。その領域では、サロゲート支援手法が好ましい。
限界と注意点
- 性能は慣性重み(w)および加速係数(c1、c2)に敏感である。パラメータ設定が不十分だと、早期収束または過度のドリフトを引き起こす。
- アーカイブ管理とリーダー選択は、追加のハイパーパラメータ(アーカイブサイズ、クラウディング指標)を導入し、これらは問題依存である。
- 収束と多様性の保証は経験的なものであり、数学的なものではない。近似されたパレートフロントは、真のフロントの領域を見逃す可能性がある。
- 支配に基づく選択における次元の呪いのため、5〜7個を超える目的関数を扱うのが難しい。
- 問題固有のエンコーディングと速度クランプの適応なしには、離散的または組み合わせ的な探索空間に直接適用できない。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 単一の実行で完全なパレートフロントを自然に近似し、意思決定者に効率的なトレードオフ解の豊富なセットを提供する。
- 勾配情報が不要なため、微分不可能、ノイズが多い、またはブラックボックスの目的関数に適用可能である。
- 単純な速度-位置更新メカニズムは計算量が少なく、並列実装が容易である。
- 外部パレートアーカイブは、探索中に見つかった最良の解を保持し、高品質な非支配的な点の損失を防ぐ。
- 柔軟なフレームワークは、制約処理、適応的パラメータ制御、および局所探索とのハイブリダイゼーションに対応する。
応用
- 多目的工学設計:構造部品および機械部品における重量、コスト、応力の同時最小化。
- エネルギーシステム:電力網スケジューリングおよび再生可能エネルギー計画におけるコスト、信頼性、排出量の間のパレート最適トレードオフ。
- サプライチェーン管理:マルチエシュロンネットワーク全体でのサービスレベル、在庫コスト、リードタイムの共同最適化。
- 機械学習ハイパーパラメータチューニング:モデル精度と推論時間またはメモリフットプリントのバランスを取る。
- 水資源管理:発電、洪水制御、生態学的流量の競合する目的のための貯水池放流ポリシーの最適化。
- ポートフォリオ最適化:金融資産配分における期待リターン対リスクの効率的フロンティアの近似。
使い方
使い方
決定空間内でランダムな位置と速度を持つN個の粒子の集団を生成する。各粒子についてすべての目的関数を評価し、支配されない初期解すべてを外部パレートアーカイブに格納する。各粒子に、その開始位置に等しい個人最良値(pbest)を割り当てる。
現在の群れ内のすべての粒子について、すべての目的関数の値を計算する。支配比較を適用する:解xが解yを支配するとは、xがすべての目的においてyより劣らず、少なくとも1つの目的において厳密に優れている場合である。新しい位置が保存されている個人最良値を支配する場合、またはそれに対して非支配的である場合に、各粒子のpbestを更新する。
新たに非支配的な解すべてを外部アーカイブに挿入する。新しく追加された解によって支配されるようになったアーカイブメンバーをすべて削除する。アーカイブが容量制限を超えた場合、パレートフロント近似全体にわたる多様性を維持するために、密度ベースのプルーニング戦略(例:ハイパーキューブ・クラウディングまたは最近傍距離)を適用する。
各粒子について、外部アーカイブから全体最良リーダー(gbest)を選択する。リーダーは通常、トーナメントまたはルーレット機構を用いて、クラウディング距離に基づいて、あまり混雑していないアーカイブ領域から選択され、群れが単一領域に早期に収束するのではなく、未開拓のパレートフロントセグメントに引き寄せられるようにする。
PSOの更新ルールを使用して、各粒子の速度と位置を更新する:v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x)。ここで、wは探索/活用バランスを制御する慣性重み、c1およびc2は認知および社会的加速係数、r1、r2は一様乱数である。粒子が実行可能な決定空間内に留まるように、境界処理を適用する。
数式
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)停止基準(最大反復回数、最大関数評価回数、またはパレートフロントの停滞)が満たされるまで、評価–更新アーカイブ–リーダー選択–粒子移動を繰り返す。最終的な外部アーカイブを近似パレート最適集合として返し、意思決定者はその後、好ましいトレードオフ解を選択するために検査する。
よくある落とし穴
- アーカイブ容量を小さすぎると、パレートフロントの多様性を破壊する積極的なプルーニングが発生する。大きすぎると、リーダー選択が遅くなり、メモリコストが増加する。
- 群れ全体に単一の全体最良リーダーを使用すると、早期収束につながる。常に多様性を考慮したリーダー選択メカニズム(例:クラウディング距離トーナメント)を使用する。
- 境界処理を怠ると、粒子が実行可能領域から脱出し、アーカイブを汚染する実行不可能な解が生成される。
- 収束性および多様性指標(例:ハイパーボリューム指標、世代間距離)なしに最終アーカイブのみを報告すると、実行間または手法間の結果を比較することが不可能になる。
- 問題の目的関数が実際に相反していることを検証せずに、MOPSOをブラックボックスオプティマイザーとして扱うこと。目的関数が整合している場合、標準的な単一目的PSOまたは勾配降下法で十分である。
よくある質問
MOPSOはNSGA-IIとどう違うのですか?
どちらも解の集団と支配に基づく選択を用いてパレートフロントを近似しますが、メカニズムが異なります。NSGA-IIは、交差および突然変異演算子を、クラウディング距離ソートを伴う親-子集団の組み合わせに適用します。MOPSOは、個人およびアーカイブベースのリーダーによって導かれる速度ベースの粒子移動を使用します。MOPSOは通常、連続空間では反復あたりの速度が速いです。NSGA-IIは、順列および組み合わせ問題により自然に適しています。
どのくらいのアーカイブサイズを使用すべきですか?
一般的なデフォルトは、2つまたは3つの目的を持つ問題に対して100〜200個の解です。アーカイブサイズが大きいほどパレートフロントのカバレッジは向上しますが、リーダー選択は遅くなります。4つ以上の目的を持つ問題では、アーカイブサイズはパレートフロントの予想される複雑さに応じてスケーリングする必要があります。適応的アーカイブ管理スキームが役立つ場合があります。
MOPSOは制約を処理できますか?
はい、ペナルティ関数、実行可能性ルール(支配比較において実行可能な解を実行不可能な解よりも優先する)、または修復演算子を通じて可能です。Coello Coelloの元の定式化には、実行可能性トーナメントに基づいた単純な制約処理メカニズムが含まれています。
MOPSOは効果的にいくつの目的関数を処理できますか?
MOPSOは2〜4個の目的関数に対してうまく機能します。5〜7個を超える目的関数になると、支配圧力が劇的に弱まり(ほとんどすべての解が相互に非支配的になる)、特殊な多目的オプティマイザー(NSGA-III、MOEA/D、または分解ベースの手法)が標準的なMOPSOを上回ります。
MOPSOの結果を評価するためにどの指標を使用すべきですか?
ハイパーボリューム指標(近似フロントによって支配される目的空間の体積を測定し、値が大きいほど良い)、世代間距離(参照パレートフロントへの近さ)、およびスプレッドまたはデルタ指標(分布の均一性)を報告してください。信頼性の高いベンチマーキングには、複数の独立した実行と統計的比較が必要です。
関連する手法
参考文献
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.
DOI 文献を開くコピーしました。Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.
DOI 文献を開くコピーしました。