Zenn
👾

NSGA-II (Non-dominated Sorting Genetic Algorithm II)

2024/08/28に公開
math
アルゴリズム
tech

はじめに

進化的アルゴリズムの一種であるNSGA-II（非劣ソート遺伝的アルゴリズムII）について詳しく解説します。NSGA-IIは、複数の目的関数を持つ多目的最適化問題を効率的に解くために開発された強力な手法です。

1. 非劣ソート（Non-dominated Sorting）

NSGA-IIの中心的な要素の一つが非劣ソートです。この手法では、解集合を複数の 非劣フロント（Pareto fronts） に分類します。これにより、各解が他の解に対してどれだけ優れているかを判定します。

  • 解 x_i が他の解 x_j に対して 優越する（dominate） 条件は：

    \forall k \in \{1, 2, \dots, M\}, \quad f_k(x_i) \leq f_k(x_j) \quad \text{かつ} \quad \exists k \in \{1, 2, \dots, M\}, \quad f_k(x_i) < f_k(x_j)

    ここで、M は目的関数の数、f_k(x) は目的関数 k に対する評価値です。

  • 非劣フロントの各階層（ランク）を計算し、同じランクの解を一つのフロントに分類します。このプロセスにより、解集合をランク付けし、探索の指針とします。

2. クラウディング距離の計算（Crowding Distance Calculation）

クラウディング距離は、解の多様性を確保するための指標で、各解が目的空間でどれだけ孤立しているかを示します。これにより、各フロント内の解が均等に分布するように調整されます。

  • 各目的関数について、解を評価値の昇順にソートします。

  • 境界の解（各目的関数で最小値または最大値を持つ解）には無限大のクラウディング距離を与えます：

    d_i = \infty \quad \text{（境界の解に対して）}

  • 他の解については、次の式で計算します：

    d_i = \sum_{k=1}^{M} \left( \frac{f_k(x_{i+1}) - f_k(x_{i-1})}{f_k^\text{max} - f_k^\text{min}} \right)

    ここで、f_k^\text{max} と f_k^\text{min} は目的関数 k の最大値と最小値です。

3. 選択（Selection）

選択は、解のランクとクラウディング距離に基づいて行われます。

  • ランクの低い解（より優れた非劣フロントに属する解）が優先されます。
  • 同じランクの解が複数ある場合、クラウディング距離が大きい解（より孤立した解）が優先されます。

これにより、優れた解を保持しつつ、解の多様性を維持します。

4. 交叉（Crossover）と突然変異（Mutation）

新しい世代の解を生成するために、交叉と突然変異が用いられます。

  • 交叉: シミュレーテッド・バイナリ交叉（Simulated Binary Crossover, SBX）が一般的に使用されます。これは親個体の値に近い子個体を生成する手法です。
  • 突然変異: 多項式突然変異（Polynomial Mutation）が用いられます。各変数に対して、小さなランダム変動を与えることで解の多様性を高めます。

5. 収束性の指標

アルゴリズムの性能を評価するために、以下の収束性指標が用いられます。

  • IGD（Inverted Generational Distance）:

    \text{IGD} = \frac{1}{|\mathcal{P}^*|} \sum_{x^* \in \mathcal{P}^*} \min_{x \in \mathcal{P}} d(x, x^*)

    ここで、\mathcal{P}^* は理想的なParetoフロント、\mathcal{P} は得られた解集合、d(x, x^*) は解 x と x^* の間の距離です。

  • GD（Generational Distance）:

    \text{GD} = \frac{1}{|\mathcal{P}|} \sum_{x \in \mathcal{P}} \min_{x^* \in \mathcal{P}^*} d(x, x^*)

    これは得られた解集合が真のParetoフロントにどれだけ近いかを測る指標です。

  • HV（Hypervolume）:

    \text{HV} = \int_{\mathcal{R}} \chi(x) \, dx

    ここで、\mathcal{R} は参照点によって定義された領域、\chi(x) はその領域内にある解を示す指示関数です。

6. NSGA-IIの長所と短所

長所

  1. 効率的な多目的最適化: NSGA-IIは複数の目的関数を同時に最適化でき、エリート保存戦略により優れた解を次世代に引き継ぎます。

  2. 解の多様性の維持: クラウディング距離を活用して、Paretoフロント全体に解を均等に分布させ、意思決定者に多様な選択肢を提供します。

  3. 計算効率の向上: NSGA-IIは非劣ソートの計算効率を高めており、計算コストをO(MN^2)に抑えています。

  4. 広範な普及とサポート: NSGA-IIは多くの研究やアプリケーションで広く使用されており、豊富なリソースが利用可能です。

短所

  1. 大規模問題での計算コスト: 集団サイズや目的関数の数が大きくなると、計算量が増加し、計算時間が長くなる傾向があります。

  2. 高次元目的空間での課題: 目的関数の数が多い高次元問題では、非劣解が増加し、解の選択やクラウディング距離の計算が難しくなります。

  3. 局所最適解への収束リスク: 他の進化的アルゴリズムと同様に、適切なパラメータ設定がなされない場合、局所最適解に陥る可能性があります。

7. NSGA-IIで特によく使われる手法

  1. シミュレーテッド・バイナリ交叉（Simulated Binary Crossover, SBX）

    • 概要: 2つの親個体から子個体を生成し、親の値に近い子を生成する交叉法です。

  2. 多項式突然変異（Polynomial Mutation）

    • 概要: 各変数に対して、現在の値を中心とした分布に基づき新しい値を生成する突然変異手法です。

  3. 制約処理手法

    • 概要: 制約違反の程度を評価基準に組み込み、非劣ソート時に考慮する方法です。

  4. 適応的交叉・突然変異率

    • 概要: 世代や集団の多様性に応じて、交叉率や突然変異率を動的に調整します。

  5. アーカイブ戦略

    • 概要: 発見された非劣解を別のアーカイブに保存し、優れた解を保持します。

結論

NSGA-IIは、多目的最適化問題を解決するための強力なアルゴリズムです。非劣ソート、クラウディング距離、エリート保存戦略などを組み合わせることで、解の多様性を維持しつつ、効率的かつ効果的に最適化を進めることができます。適切な手法と組み合わせることで、さまざまな複雑な最適化問題に適用可能です。

Discussion