多目的遺伝的アルゴリズム(MOGA) — パレート最適解のための進化的探索
- 提唱者
- Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
- 年
- 1984
- 種類
- Population-based evolutionary optimizer
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
多目的遺伝的アルゴリズム(MOGA)は、2つ以上の相反する目的関数を同時に最適化することにより、候補解の集団をパレート最適フロンティアへと進化させる進化的計算手法である。これは、トレードオフを単一のスコアに収束させるのではなく、意思決定者が選択できる非支配解の集合を生成する。
手法の背後にある直感
候補設計の連続世代を育種することを想像してほしい。そこでは、すべての目的において明確に劣っていない解のみが生き残り、繁殖する。多くの世代を経て、集団は達成可能な最良のトレードオフのフロンティアへと収束する――このパレートフロンティア上のどの解も、他の目的を悪化させることなく一つの目的を改善することはできない。MOGAは、古典的な勾配法が失敗するような高次元、非凸、または不連続な探索空間においても、このフロンティアを効率的に探索するために、選択、交叉、突然変異といった遺伝的操作を活用する。
歴史学
多目的遺伝的アルゴリズムは、1984年のSchafferによるVector Evaluated Genetic Algorithm(VEGA)に端を発しており、これは複数の目的を明示的に処理した最初のGAであった。Goldbergの1989年の教科書は、パレートベースのランキングを原則的な適合度割り当て戦略として形式化した。この分野は、FonsecaとFlemingのMOGA(1993年)、SrinivasとDebのNSGA(1994年)、そして分野の標準ベンチマークとなり、最も広く引用されている進化的多目的アルゴリズムであり続けるDebらによる画期的なNSGA-II(2002年)によって急速に成熟した。
使うべき場面
問題が2つ以上の相反する目的を持ち、単一の最適解が存在しない場合にMOGAを使用する――工学設計、サプライチェーン構成、ポートフォリオ最適化、環境計画などが典型的なドメインである。勾配ベースの手法が適用できない非凸、多峰性、またはブラックボックスの目的ランドスケープに適している。単一の明確に定義された目的で十分な場合(標準的なGAまたは数理計画法を使用)、集団評価が計算上実行不可能で代理モデルが利用できない場合、目的が情報損失なしに既知の重み付き和によって正当に集約できる場合、または小さな実行可能集合が網羅的列挙を可能にする場合には使用しない。
限界と注意点
- 計算コストは、集団サイズと関数評価回数に比例して増加する。複雑なシミュレーションの各評価は高価になる可能性がある。
- 真のパレートフロンティアへの収束は保証されない――結果は、ハイパーパラメータの選択(集団サイズ、交叉率、突然変異率)に敏感なヒューリスティック近似である。
- 目的関数の数が3つまたは4つを超えると性能が低下する(多目的最適化にはNSGA-IIIやMOEA/Dなどの特殊なアルゴリズムが必要)。
- 早期収束またはフロンティアのカバレッジ不良を回避するために、遺伝子演算子と多様性維持の慎重な調整が必要である。
- 単一の推奨解を提供しない――パレートフロンティアからの最終的な選択には、依然として価値判断または二次的な決定規則が必要である。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 単一の実行でパレート最適解の多様なセットを生成し、意思決定者に単一の回答ではなく、明示的なトレードオフの選択肢を提供する。
- 勾配や問題固有の数学的構造を必要とせずに、非凸、不連続、多峰性の目的ランドスケープで機能する。
- 本質的に集団ベースであり、コアまたは分散システム全体での並列化が容易である。
- 柔軟なエンコーディングにより、連続変数、整数、バイナリ文字列、および順列を同じフレームワーク内で扱うことができる。
- 成熟したソフトウェアライブラリ(DEAP、pymoo、jMetal)と数十年にわたるベンチマーク証拠によってよくサポートされている。
応用
- 工学設計最適化――構造部品の重量、コスト、応力を同時に最小化する。
- サプライチェーンとロジスティクス――ネットワーク構成全体でコスト、リードタイム、炭素排出量をバランスさせる。
- 環境およびエネルギー政策――コスト、信頼性、排出量の観点から再生可能エネルギーポートフォリオを最適化する。
- 医薬品および化学プロセス設計――反応時間を最小限に抑えながら、収率と純度を最大化する。
- 機械学習ハイパーパラメータチューニング――モデルの精度とトレーニング時間または解釈可能性とのトレードオフ。
- 都市計画および交通――カバレッジ、移動時間、インフラコストの観点からルートネットワークを最適化する。
使い方
使い方
N個の候補解(染色体)の初期集団をランダムに、またはドメインヒューリスティックを用いて生成し、各解を決定変数のベクトルとしてエンコードする。同時に最小化または最大化されるk個の目的関数f1(x), f2(x), ..., fk(x)を定義する。
集団内のすべての個体について、すべてのk個の目的関数を評価する。適合度は、目的関数全体にわたる解の質と、目的空間全体にわたるカバレッジの多様性の両方を反映する。
非支配性によって個体をランク付けする:解xが解yを支配するとは、xがすべての目的において少なくともyと同等に良く、かつ少なくとも一つの目的において厳密に良い場合をいう。非支配フロンティア(パレートフロンティア候補)を特定し、支配されにくい個体に高い選択優先度を割り当てる。クラウディング距離などの多様性指標は、フロンティアの狭い領域へのクラスタリングを防ぐ。
選択(例:トーナメント選択)を適用して、よりランクの高い個体を優遇し、次に交叉を適用してペアの親を組み合わせ、突然変異を適用して多様性を導入する。エリート主義メカニズムは、世代を超えて見つかった最良の非支配解を保持する。
所定の世代数、または収束基準が満たされるまで、適合度評価、ランク付け、繁殖を繰り返す。最終的な非支配集合はパレート最適フロンティアを近似し、意思決定者に最適なトレードオフ解のスペクトルを提示する。
よくある落とし穴
- パレートフロンティア上のすべての解を、最終的なトレードオフ選択を行うためのドメインエキスパートを関与させることなく、等しく有効と見なすと、恣意的または不十分な根拠に基づいた選択につながる可能性がある。
- 小さすぎる集団を使用すると疎で代表性のないフロンティアが生成される。大きすぎる集団は、比例した利益なしに計算量を増加させる。
- 制約処理の無視――実行不可能な解は明示的にペナルティを課すか修復する必要がある。これを怠ると、探索が実行不可能な領域に向かって歪む。
- 4つを超える目的を持つ問題に、多目的アルゴリズムに切り替えずにMOGAを適用すると、ほとんどすべての解が非支配的である、散乱した情報のないフロンティアが生じる。
- 収束診断(世代ごとのハイパーボリューム)なしに最終的なパレートフロンティアのみを報告すると、アルゴリズムが実際に収束したかどうかを評価することが不可能になる。
よくある質問
MOGAは、目的関数の重み付き和を用いた単一目的GAの実行とどのように異なるのか?
重み付き和アプローチは、事前に割り当てられた重みを使用してすべての目的を1つのスカラーに収束させ、それらの重みに依存する単一の解を生成する。MOGAは、事前に重みを指定する必要なしに、非支配解の完全なフロンティアを同時に生成し、意思決定者がトレードオフを検査し、後で選択できるようにする。
パレートフロンティアとは何か、そしてなぜそれが重要なのか?
パレートフロンティアとは、単一の目的を改善すると必ず少なくとも他の目的が悪化するような解の集合である。それは達成可能なトレードオフの完全な像を表す。意思決定者は、このフロンティアを検査して、他の目的をどれだけ犠牲にすれば一つの目的を改善できるかを理解できる。
MOGAは効果的にいくつまでの目的を扱えるか?
NSGA-IIなどの標準的なMOGAバリアントは、2つまたは3つの目的にはうまく機能する。4つを超える目的になると、非支配解の割合が急速に増加し(目的空間における次元の呪い)、パレートフロンティアが大きくなり、選択圧が弱くなる。4つ以上の目的には、多目的アルゴリズム(NSGA-III、MOEA/D、IBEA)が推奨される。
どのような停止基準を使用すべきか?
一般的な基準には、所定の関数評価回数、最大世代数、または successive generations におけるハイパーボリューム指標(現在のパレートフロンティア近似によって支配される目的空間の体積)の収束が含まれる。ハイパーボリュームの成長を監視することが最も原則的なアプローチである。
MOGAは制約を扱えるか?
はい、制約処理技術を通じて可能です。実行不可能な解の適合度を低下させるペナルティ関数、実行可能な解が常に実行不可能な解よりも選択で優位になる実行可能性トーナメント選択、または実行不可能な解を実行可能領域に投影する修復演算子などがあります。選択は収束挙動に影響を与え、慎重に行う必要があります。
関連する手法
参考文献
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
ISBN:9780201157673コピーしました。Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
DOI 文献を開くコピーしました。