NSGA-II (Non-dominated Sorting Genetic Algorithm II)による多目的最適化とその応用

はじめに

現実の意思決定問題では、複数の目標（目的関数）を同時に最適化する必要がしばしばあります。このような多目的最適化問題では、「最適解」は一意ではなく、トレードオフの集合（パレート最適解集合）が存在します。パレート最適性とは、ある解について他のいかなる解も全ての目的で優れていない場合を指し、パレート最適解の集合はパレートフロントと呼ばれます 。形式的には、最小化問題を考えると、解$x_1$が解$x_2$を支配(dominate)するとは、「すべての目的$i$について$f_i(x_1) \leq f_i(x_2)$が成り立ち、かつ少なくとも1つの目的$j$について$f_j(x_1) < f_j(x_2)$が成り立つ」ことと定義できます 。パレート最適解とは他のいかなる解にも支配されない解のことであり、パレートフロント上の点は互いに優劣がつけられません。古典的な最適化手法（例：スカラー化による重み付け和法や目標値に基づく手法）では、多目的問題を単一目的に帰着させ、一度にパレートフロント上の1点のみを求めます。したがってフロント全体を得るにはパラメータを変えて問題を繰り返し解く必要があります。一方、進化的アルゴリズム(EA)は集団ベースの手法であり、一度の実行で複数のパレート解を同時に探索可能であるため、近年多目的最適化への応用が注目されています。本記事では、多目的最適化における代表的な進化計算手法であるNSGA-II (非支配ソート遺伝的アルゴリズム)の理論的背景を数学的に詳述し、金融工学におけるポートフォリオ最適化への応用について解説します。特に、NSGA-IIのアルゴリズム原理（非支配ソート、エリート戦略、混雑距離など）と、従来のMarkowitzの平均-分散モデルとの比較を通じて、NSGA-IIがどのようにEfficient frontierを求めるかを示します。

多目的最適化とパレートフロントの概念

図1: 2目的最適化におけるパレートフロントの概念。 赤線で示された部分がパレートフロント（Efficient frontier）であり、点AおよびBは互いに支配関係がなくフロント上にある。灰色の点Cは、AおよびBによって支配されているためパレート最適ではない。

図1に示すように、多目的最適化では解空間に多数の解候補が存在し、それらの中から他に支配されない解（非支配解）だけがパレートフロントとして残ります。パレートフロント上の点は、ある目的をこれ以上改善しようとすると別の目的が悪化するというトレードオフの関係にあります。例えば、図1では目的$f_1$と$f_2$を考え、点Cは緑の点Aおよび黄色の点Bによってそれぞれ一部の目的で劣っている（支配されている）ため非効率ですが、AとBは互いに優劣が付けられずフロント上に位置しています。このようなパレートフロントを求めることが多目的最適化の目標となります。

進化的手法は、このパレートフロントを効率よく探索するアプローチとして有力です。遺伝的アルゴリズム(GA)に代表される進化計算では、集団と呼ばれる複数の解（個体）を同時に扱い、世代を重ねて解を進化（改善）させます。各個体は解の符号化（遺伝子）を持ち、適合度（目的関数値）に応じた選択、解を組み合わせる交叉、ランダムな突然変異といった遺伝的操作を繰り返すことで探索を行います。多目的GA（MOEA）はこの過程で個体の非支配性（他個体に支配されていないか）を評価基準に組み込み、集団全体で多様なパレート解を得る工夫がなされています。次節では、数あるMOEAの中でも広く用いられているNSGA-IIアルゴリズムの仕組みを詳しく見ていきます。

NSGA-IIのアルゴリズムと理論的背景

NSGA-II (Non-dominated Sorting Genetic Algorithm II)は、K. Debらによって2002年に提案されたエリート主義型の多目的進化的アルゴリズムです。その前身であるNSGA（第一世代の非支配ソートGA）が抱えていた課題（非支配ソートの計算量、エリート保存の欠如、多様性維持のためのパラメータ設定）を克服するために考案されました 。NSGA-IIの特徴は以下の3点にまとめられます。

• 高速な非支配ソート: 個体を非支配ソートによりランク付けする際の計算量が改良され、従来$O(MN^3)$だった処理が$O(MN^2)$に高速化されています（$M$は目的数、$N$は集団サイズ）。これにより大規模集団でも効率よくパレートフロントを計算できます。

• エリート保存戦略（Elitism）: 現世代の優良解が次世代で失われないよう、親集団と子集団を統合した中から優れた個体を生き残らせる戦略を導入しています。具体的には各世代$t$において、親集団$P_t$（サイズ$N$）とその交叉・突然変異によって生成された子集団$Q_t$（サイズ$N$）をまず結合し、サイズ$2N$の合同集団$R_t = P_t \cup Q_t$を形成します。この$R_t$に対して非支配ソートを行い、パレートランクごとのフロント$F_1, F_2, \dots$を得ます。次世代の親集団$P_{t+1}$は、まずランクの低いフロントから順に可能な限り全集団に追加していき（優先順位は$F_1$が最高）、容量$N$を超過しそうになったところでストップします。最後に、入りきらない最終フロント$F_k$内の個体については混雑距離によるソートを行い、解空間内でより疎な（周囲に他の解が少ない）個体を優先的に選抜して$N$枠を埋めます。このようにして、パレート最良の個体群が保持・多様化されながら世代交代が行われます。

• 混雑距離に基づく多様性維持: 他の個体とどれだけ離れているかを定量化する混雑距離(crowding distance)を各個体に算出し、集団内の解の多様性を確保します 。混雑距離$d_i$は各目的関数空間で隣接する解との距離の和で定義されます。例えばフロント$F$内の解を各目的$m$について昇順に並べたとき、両端の解の混雑距離を無限大に設定し（境界の解は常に残すため）、中間の解$j$については隣接する解$j+1$および$j-1$との目的値差分で計算します。

  $$d_j \;=\; \sum_{m=1}^{M} \frac{f_m(j+1) - f_m(j-1)}{f_m^{\max} - f_m^{\min}}\,,$$

  ここで$f_m(k)$は解$k$の目的$m$の評価値、$f_m^{\max}, f_m^{\min}$はそのフロント内での目的$m$の最大値・最小値です。この式から、周囲に極端な解がいない個体ほど$d_j$が大きくなり、結果的に混雑距離の大きな個体が選好されます。NSGA-IIでは混雑トーナメント選択も導入されており、親個体の選択時には2個体間でまずパレートランクを比較し、ランクが低い（優越する）方を選択します。ランクが同じ場合は混雑距離がより大きい方を選ぶことで、解の多様性を保ちながら選択圧をかけます 。この手法により、ユーザがパラメータを調整せずとも集団内の分散が維持される（前世代のNSGAで必要だったシェアリングパラメータ$\sigma$を不要化）という利点があります。

以上をまとめると、NSGA-IIのアルゴリズム手順は以下のようになります。

1. 初期集団$P_0$（サイズ$N$の個体群）をランダムに生成し、世代$t=0$とする。
2. 各個体の目的関数を評価し、集団$P_t$内で非支配ソートを実施してパレートランクを付与する（ランク1が最良の非支配フロント）。加えて各個体の混雑距離$d_i$を計算する。
3. 選択: 混雑トーナメント選択により、次世代の親候補となる個体を$P_t$から選抜する（ランク優先・距離サブ優先）。
4. 交叉・突然変異: 選抜された個体ペアから交叉によって新たな子個体を生成し、さらに突然変異を適用して子集団$Q_t$（サイズ$N$）を構成する。
5. エリート保存による世代交代: 親集団$P_t$と子集団$Q_t$を統合した$R_t = P_t \cup Q_t$に対し非支配ソートを行い、ランクごとに次世代集団$P_{t+1}$（サイズ$N$）を埋める。途中のフロントで枠が埋まらない場合は、そのフロント内で混雑距離の大きい個体から選抜して$P_{t+1}$を完成させる。
6. 終了条件（予め決めた最大世代数や収束指標の閾値など）を満たしていなければ$t := t+1$とし、ステップ2以降を繰り返す。満たした場合は$P_t$に含まれる非支配解集合を出力する。

以上のようにNSGA-IIは、適応度評価と非支配ソートに基づいて解集合全体でパレートフロントの近似解を進化的に生成します。その高速化と多様性確保の工夫により、様々な分野の多目的最適化問題で成功を収めており、現在でも最も広く用いられる手法の一つです。次節では、このNSGA-IIを金融分野のポートフォリオ最適化問題に応用する方法と、その利点について説明します。

ポートフォリオ最適化へのNSGA-IIの応用

ポートフォリオ最適化とは、複数の資産に資金を配分することでリスクとリターンのバランスを最適化する問題です。古典的にはMarkowitzの平均-分散モデル（モダンポートフォリオ理論）が広く知られており、これは期待リターン（平均）を最大化しつつリスク（分散）を最小化することを目的とします 。形式的には、資産$i=1,\dots,n$への投資比率を決める重みベクトル$\mathbf{w}=(w_1,\dots,w_n)$に対し、各資産の期待収益率を$\mu_i$、リスク指標として分散共分散行列を$\Sigma=(\sigma_{ij})$とすると、ポートフォリオの期待リターンと分散はそれぞれ次式で与えられます。

• 期待リターン: $\mu_p(\mathbf{w}) = \sum_{i=1}^n w_i \mu_i$
• リスク（分散）: $\sigma_p^2(\mathbf{w}) = \mathbf{w}^T \Sigma\, \mathbf{w}$

典型的な最適化問題の定式化では、「期待リターンを最大化し、同時にリスクを最小化する」という多目的最適化となります。ただし単一目的最適化に帰着させる場合、例えば「所与の目標リターン$\mu_0$を達成しつつ分散$\sigma_p^2$を最小化する」あるいは「$\mu_p - \lambda\,\sigma_p^2$を最大化する（$\lambda$はリスク許容度）」といったスカラー化問題に変換し、パラメータ$\mu_0$や$\lambda$を変化させることで効率的フロント（Efficient frontier）と呼ばれるパレート最適ポートフォリオ集合を求めます 。Efficient frontier上のポートフォリオは、それ以上リスクを下げるとリターンも低下し、それ以上リターンを上げるとリスクも増大するため、いずれも他の組合せでは「改善できない」組合せとなっています 。Markowitzの理論では、このフロント上のポートフォリオ群から投資家のリスク許容度に応じた最適点を選択します。

上記のポートフォリオ問題はまさに二目的の最適化問題であり、NSGA-IIによってEfficient frontierを直接近似することが可能です。NSGA-IIを適用するには、個体の遺伝子符号化として資産配分比率$\mathbf{w}$を表現します（例: 遺伝子を長さ$n$の実数配列とし各要素が資産ウェイトに対応）。適用上は予算制約$\sum_{i} w_i = 1$や空売り禁止などの制約条件を満たすよう初期集団を生成し、進化操作でもこれら制約を維持またはペナルティ法で誘導します。目的関数は「期待リターンを最大化」「分散を最小化」の二つであり、NSGA-IIはこれら二目的についてパレート最適な配分$\mathbf{w}$の集合を探索します。具体的には、適合度評価で各個体$\mathbf{w}$に対し$(f_1, f_2) = (-\mu_p(\mathbf{w}),\,\sigma_p^2(\mathbf{w}))$の値を与え、非支配ソートによって他のポートフォリオに劣らない解を選び出します。こうして世代を重ねることで、集団全体のリスク・リターン特性は徐々に洗練され、Efficient frontierへの収束が図られます。実際の研究でも、NSGA-IIによりごく少数世代で真のEfficient frontier上の解が含まれるところまで収束することが報告されています 。

図2: NSGA-IIによって得られたポートフォリオ集団のリスク–リターン平面上の分布（緑点：集団内のポートフォリオ、赤点：非支配の解として選抜されたEfficient frontier）。横軸はリスク（標準偏差）、縦軸は期待リターンを示す。

図2は、NSGA-IIで進化させたポートフォリオ集団をリスク–リターン空間にプロットした一例です。世代が進むにつれて集団内の点（緑色）は左上方向（低リスク・高リターン）へ引き寄せられ、やがて赤色で示したパレート最適フロントに個体が集まっていく様子が確認できます。Efficient frontier上の各ポートフォリオは、古典的なMarkowitzモデルで計算されるフロント解と一致するだけでなく、もし追加の制約（例えば資産数の上限=カーディナリティ制約や個別資産への投資比率の上下限、取引コストなど）を課した場合でも、NSGA-IIはそれら制約下のパレート最適解を近似的に求めることができます 。一方でMarkowitzの平均-分散法をそのまま適用すると、これら離散的・組合せ的な制約が入った問題は数理的に複雑になり、厳密解の計算が困難になることが知られています（NP困難な組合せ最適化に帰着します）。NSGA-IIをはじめとする進化的手法は厳密解を保証しないものの、現実的な制約条件を柔軟に扱え、近似解でも十分な解の多様性を提供できる点で実用上有用です。特にポートフォリオ問題では、Efficient frontierという全体像を一度の計算で得られるため、投資家はリスク–リターンのトレードオフを把握しながら自らの許容度に応じたポートフォリオを選択できます 。これは単一解しか得られない最適化と比べ大きな利点です。

おわりに

本記事では、NSGA-II（Non-dominated Sorting Genetic Algorithm II）の理論的背景とアルゴリズム詳細を、数式を交えて解説しました。NSGA-IIは、多目的最適化においてパレート最適解の集合を一度に効率よく探索するための強力な手法であり、その高速な非支配ソート、エリート保存戦略、混雑距離による多様性維持機構によって広く採用されています。また応用例として、金融におけるポートフォリオ最適化問題にNSGA-IIを適用し、従来のMarkowitzモデルでは逐次的に求めていたEfficient frontierを進化計算によって直接近似できることを示しました。NSGA-IIは現実の複雑な制約条件下でも適用可能であり、学術研究のみならず実務においても多目的最適化の有用なツールとなり得ます。

参考文献:

1. Kalyanmoy Deb et al., “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evolutionary Computation 2002 (A fast and elitist multiobjective genetic algorithm: NSGA-II - Evolutionary Computation, IEEE Transactions on) .
2. “On NSGA-II and NSGA-III in Portfolio Management,” IEEE/CAA J. of Automatica Sinica, vol. 32, no. 3, 2022 (On NSGA-II and NSGA-III in Portfolio Management).