この記事について
前回の記事では多目的最適化の基礎概念（パレート支配・パレートフロント）を説明しました。
今回は多目的最適化の代表的なアルゴリズムである NSGA-II（Non-dominated Sorting Genetic Algorithm II）を説明していきます。
「遺伝的アルゴリズム」や「進化型アルゴリズム」という言葉は聞いたことあるけど、多目的版がどうなるのかよくわからない、という方の参考になれば幸いです。
多目的最適化入門シリーズの他の記事はこちら。
| 記事 | 内容 |
|---|---|
| ① | 多目的最適化とは？基礎概念 |
| ②（本記事） | NSGA-IIの説明 |
| ③ | MOEA/Dの説明 |
| ④ | ベンチマーク問題の説明 |
NSGA-IIとは
NSGA-IIは2002年にDebら（インド工科大学）が提案した多目的進化アルゴリズムです。
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
多目的最適化アルゴリズムの中でもっとも有名な手法の一つで、20年以上経った今でもベースラインとして広く使われています。
NSGA-IIの特徴を一言で言うと、
「非劣解ランクと混雑距離（Crowding Distance）という2つの指標で解の良さを評価し、集団を進化させる」
アルゴリズムです。これが何を意味するのか、順を追って説明します。
進化的アルゴリズムの基本フロー
まず、遺伝的アルゴリズム（GA）の基本的な流れを確認しておきます。
① 初期集団の生成
② 各個体の評価（目的関数値の計算）
③ 選択（良い個体を親として選ぶ）
④ 交叉・突然変異（新しい個体を生成）
⑤ 次世代集団の形成
⑥ ②に戻って繰り返す（収束するまで）
NSGA-IIはこの基本フローに「多目的最適化向けの評価・選択の仕組み」を組み込んだものです。
非劣解ソート（Non-dominated Sorting）
NSGA-IIの核心は非劣解ソートです。
集団中の解を「どれだけ良い解か」でランク付けするために使います。
ランクの付け方
集団中の全解に対して以下の手順でランクを割り当てます。
ランク1の解の選択：
→ 集団中のどの解にも支配されない解（パレート最適解の近似）がランク1
ランク2の解の選択：
→ ランク1の解を除いた残りの集団で、どの解にも支配されない解がランク2
以降、同じ操作を繰り返す。
def fast_non_dominated_sort(population, objectives):
"""
高速非劣解ソート
population: 解の集合
objectives: 各解の目的関数値リスト [[f1, f2, ...], ...]
戻り値: ランク割り当てリスト
"""
n = len(population)
domination_count = [0] * n # この解を支配する解の数
dominated_set = [[] for _ in range(n)] # この解が支配する解の集合
rank = [0] * n
fronts = [[]]
for i in range(n):
for j in range(n):
if i == j:
continue
# iがjを支配するか判定
if dominates(objectives[i], objectives[j]):
dominated_set[i].append(j)
elif dominates(objectives[j], objectives[i]):
domination_count[i] += 1
if domination_count[i] == 0:
rank[i] = 1
fronts[0].append(i)
# フロントを順次構築
current_front = 0
while fronts[current_front]:
next_front = []
for i in fronts[current_front]:
for j in dominated_set[i]:
domination_count[j] -= 1
if domination_count[j] == 0:
rank[j] = current_front + 2
next_front.append(j)
current_front += 1
fronts.append(next_front)
return rank, fronts[:-1]
def dominates(obj_a, obj_b):
"""aがbを支配するか判定（最小化）"""
better_in_all = all(a <= b for a, b in zip(obj_a, obj_b))
strictly_better_in_one = any(a < b for a, b in zip(obj_a, obj_b))
return better_in_all and strictly_better_in_one
ランク1の解がパレートフロントに最も近い、つまり「良い解」だということになります。
視覚的なイメージ
概念図にすると以下のようになります。ランク1（青）が最も良い解の集合で、ランク2（オレンジ）・ランク3（緑）と原点から遠ざかるにつれてランクが下がっていきます。
混雑距離（Crowding Distance）
非劣解ソートだけだと「ランク1の解がたくさんある場合、どれを残すか？」が決まりません。
そこで登場するのが混雑距離です。
概念
混雑距離は「ある解の周囲にどれだけ密集していないか」を示す指標です。
値が大きい = 周囲に解が少ない（多様性が高い）
値が小さい = 周囲に解が密集している（多様性が低い）
NSGA-IIは多様性を保つために、混雑距離が大きい解を優先して残します。
計算方法
各目的関数ごとに解をソートし、隣接する解との目的関数値の差（正規化済み）を足し合わせます。
def crowding_distance(objectives):
"""
混雑距離の計算
objectives: 同一ランク内の解の目的関数値 [[f1, f2, ...], ...]
"""
n = len(objectives)
if n <= 2:
return [float('inf')] * n
num_objectives = len(objectives[0])
distances = [0.0] * n
for obj_idx in range(num_objectives):
# この目的関数でソート
sorted_indices = sorted(range(n), key=lambda i: objectives[i][obj_idx])
# 端の解は無限大
distances[sorted_indices[0]] = float('inf')
distances[sorted_indices[-1]] = float('inf')
# 目的関数値の範囲（正規化用）
obj_range = (objectives[sorted_indices[-1]][obj_idx]
- objectives[sorted_indices[0]][obj_idx])
if obj_range == 0:
continue
# 各解の混雑距離を加算
for i in range(1, n - 1):
distances[sorted_indices[i]] += (
objectives[sorted_indices[i + 1]][obj_idx]
- objectives[sorted_indices[i - 1]][obj_idx]
) / obj_range
return distances
視覚的なイメージ
- 黄色（端点）：混雑距離 = ∞ で必ず残す
- 赤（密集エリア）：隣接点との囲む矩形が小さい → 混雑距離が小さく不利
- 緑（孤立エリア）：隣接点との囲む矩形が大きい → 混雑距離が大きく優先
端の解と孤立している解を優先することで、解の多様性が保たれます。
NSGA-IIのアルゴリズム全体
NSGA-IIの全体の流れをまとめると以下のようになります。
① 初期集団 P（サイズN）をランダムに生成
② Pを評価（各解の目的関数値を計算）
③ 以下を繰り返す：
a. 交叉・突然変異で子集団 Q（サイズN）を生成
b. P と Q を合体 → R（サイズ2N）
c. R全体に非劣解ソートを適用（ランク1, 2, 3, ... を割り当て）
d. ランクの小さい順に次世代集団 P' にコピー
→ ランク途中で集団がいっぱいになった場合、
そのランク内では混雑距離が大きい解を優先
e. P' を新たな P として、a に戻る
④ 十分な世代数を経たら終了
図で示すと以下のようになります。
世代t:
P(t) [N個]
|
| 交叉・突然変異
↓
Q(t) [N個]
|
P(t) + Q(t) = R [2N個]
|
| 非劣解ソート + 混雑距離
↓
P(t+1) [上位N個を選択]
実装の骨格
def nsga2(problem, pop_size=100, n_generations=200):
"""
NSGA-IIのメインループ
problem: 多目的最適化問題オブジェクト
"""
# ① 初期集団生成・評価
population = problem.initialize(pop_size)
objectives = [problem.evaluate(x) for x in population]
for gen in range(n_generations):
# 子集団の生成
offspring = generate_offspring(population, objectives)
off_objectives = [problem.evaluate(x) for x in offspring]
# 集団を合体
combined = population + offspring
combined_obj = objectives + off_objectives
# 非劣解ソート
ranks, fronts = fast_non_dominated_sort(combined, combined_obj)
# 次世代集団の選択
new_population = []
new_objectives = []
for front in fronts:
if len(new_population) + len(front) <= pop_size:
# フロント全体を追加
for idx in front:
new_population.append(combined[idx])
new_objectives.append(combined_obj[idx])
else:
# 混雑距離で補完
front_obj = [combined_obj[idx] for idx in front]
distances = crowding_distance(front_obj)
sorted_front = sorted(
range(len(front)),
key=lambda i: distances[i],
reverse=True
)
remaining = pop_size - len(new_population)
for i in sorted_front[:remaining]:
new_population.append(combined[front[i]])
new_objectives.append(combined_obj[front[i]])
break
population = new_population
objectives = new_objectives
return population, objectives
NSGA-IIの長所と短所
長所
- シンプルで理解しやすい：非劣解ソートと混雑距離という直感的な概念で構成されている
- 広く使われている：ベースラインとして多くの研究で参照されており、比較しやすい
- 目的関数の数が少ない場合に強い：2〜3目的問題では特に効果的
短所
- 目的数が増えると性能が落ちる：目的が4以上になると「ほとんどの解が非劣解関係になってしまう」という問題が起きます。
- 非劣解ソートの計算コスト：集団サイズ $N$、目的数 $m$ に対して $O(mN^2)$ の計算量がかかります
まとめ
今回はNSGA-IIを説明しました。
- 非劣解ソート：どの解にも支配されない解をランク1として、順次ランクを付けていく
- 混雑距離：解の密集度の逆数で多様性を保つ
- NSGA-IIはシンプルで強力だが、目的数が増えると性能が落ちる
次回はMOEA/Dを説明します。MOEA/DはNSGA-IIとは全く異なるアプローチで多目的問題を解きます。
参考にした記事や本、論文等
- K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.