この記事について
前回⑤では交叉、特にSBX交叉を説明しました。今回は残りの2つのオペレータ、 突然変異（Mutation）と選択（Selection） を説明します。
具体的には以下を扱います。
- 多項式突然変異（Polynomial Mutation）：実数値GAの定番の突然変異
- バイナリトーナメント選択と混雑比較演算子：NSGA-IIが親を選ぶときの仕組み
最後に②のNSGA-IIをオペレータ込みで完成させて、「どのオペレータを外すと何が壊れるか」を実際に測ってみます。突然変異を外したらNSGA-IIが50世代あたりで頭打ちになり、そこから200世代回してもほぼ改善しませんでした。この結果が個人的に一番見てもらいたい結果になります。
多目的最適化入門シリーズの他の記事はこちら。
| 記事 | 内容 |
|---|---|
| ① | 多目的最適化とは？基礎概念 |
| ② | NSGA-IIの説明 |
| ③ | MOEA/Dの説明 |
| ④ | ベンチマーク問題の説明 |
| ⑤ | 交叉（SBX交叉）の説明 |
| ⑥（本記事） | 突然変異と選択の説明 |
なぜ突然変異が必要なのか
⑤で書いたとおり、交叉は「集団がすでに持っている情報を組み替える」操作です。SBXは親の外側にも子を作れますが、それでも親の位置を基準にした操作であることには変わりありません。
集団のすべての個体が $x_5 = 0.7$ 付近に固まってしまったら、交叉だけでは $x_5 = 0.1$ を作るのは絶望的です。この「集団が一度失った多様性を戻せない」問題を防ぐのが突然変異の役割です。
進化計算の教科書だと「突然変異は局所最適からの脱出のため」と説明されることが多いですが、多目的最適化ではそもそも集団が潰れるのを防ぐという側面の方が大きいかなと思っています。
多項式突然変異（Polynomial Mutation）
実数値GAで最もよく使われる突然変異です。SBXと同じくDebらの提案で、設計思想もSBXと対になっています。
K. Deb and M. Goyal, "A combined genetic adaptive search (GeneAS) for engineering design," Computer Science and Informatics, vol. 26, pp. 30-45, 1996.
考え方
変数 $x$ を、定義域 $[\text{lb}, \text{ub}]$ の幅に対する割合 $\delta$ だけずらします。
x' = x + \delta \cdot (\text{ub} - \text{lb}), \qquad \delta \in [-1, 1]
$\delta$ の確率密度を、0の近くが出やすく、たまに大きく飛ぶように設計します。SBXが $\beta = 1$ 付近を厚くしたのと同じ発想ですね。
P(\delta) = \frac{1}{2}(\eta_m + 1)(1 - |\delta|)^{\eta_m}
$\eta_m$ が突然変異側の分布指数です。多項式（polynomial）の形をしているので「多項式突然変異」と呼ばれます。
逆関数法で δ を作る
SBXのときと同じ手順です。$u \sim U[0,1]$ から累積分布を逆に解きます。
$u < 0.5$ のとき（マイナス側）：
u = \int_{-1}^{\delta} \frac{1}{2}(\eta_m+1)(1+t)^{\eta_m}\, dt
= \frac{1}{2}(1+\delta)^{\eta_m+1}
\quad \Longrightarrow \quad
\delta = (2u)^{\frac{1}{\eta_m+1}} - 1
$u \ge 0.5$ のとき（プラス側）：
\delta = 1 - \big(2(1-u)\big)^{\frac{1}{\eta_m+1}}
まとめるとこうなります。
\delta = \begin{cases}
(2u)^{\frac{1}{\eta_m+1}} - 1 & (u < 0.5) \\[8pt]
1 - \big(2(1-u)\big)^{\frac{1}{\eta_m+1}} & (u \ge 0.5)
\end{cases}
ηm の効果を確認する
$|\delta|$ の期待値は計算すると $\dfrac{1}{\eta_m + 2}$ になります。実際にサンプリングして確かめてみます。
import numpy as np
def sample_delta(eta_m, size, rng):
"""逆関数法による変異量deltaのサンプリング"""
u = rng.random(size)
return np.where(u < 0.5,
(2 * u) ** (1 / (eta_m + 1)) - 1,
1 - (2 * (1 - u)) ** (1 / (eta_m + 1)))
rng = np.random.default_rng(0)
for eta_m in (5, 20, 100):
d = sample_delta(eta_m, 100_000, rng)
print(f'eta_m={eta_m:3d}: 平均={d.mean():+.5f}（理論0）, '
f'|delta|の平均={np.abs(d).mean():.5f}（理論{1/(eta_m+2):.5f}）, '
f'最大|delta|={np.abs(d).max():.4f}')
eta_m= 5: 平均=-0.00032（理論0）, |delta|の平均=0.14262（理論0.14286）, 最大|delta|=0.8635
eta_m= 20: 平均=-0.00023（理論0）, |delta|の平均=0.04531（理論0.04545）, 最大|delta|=0.4742
eta_m=100: 平均=+0.00000（理論0）, |delta|の平均=0.00983（理論0.00980）, 最大|delta|=0.1096
理論値とほぼ一致しています。$\eta_m = 20$ なら平均して変数範囲の4.5%だけ動くということですね。ただし最大では47%も動いているので、「基本は小さく、たまに大きく」という設計になっているのがわかります。
分布を図にすると以下のようになります。
- 左：$\eta_m$ を変えたときの $P(\delta)$。$\eta_m$ が大きいほど $\delta = 0$ に鋭く集中します
- 右：サンプリング結果と理論式の比較。こちらもぴったり一致しています
境界処理：クリップすると境界に張り付く
⑤のSBXでも触れましたが、突然変異でも定義域からはみ出す問題があります。$x = 0.02$（範囲 $[0, 1]$）を変異させると、$\delta < -0.02$ になった瞬間に負の値になってしまいます。
素朴には np.clip(x, 0, 1) で丸めればいいのですが、これをやると境界に解が積み上がります。どれくらい積み上がるのか測ってみました。
def pm_simple(x, lb, ub, eta_m, rng):
"""素の多項式突然変異＋クリップ"""
d = sample_delta(eta_m, x.shape, rng)
return np.clip(x + d * (ub - lb), lb, ub)
def pm_bounded(x, lb, ub, eta_m, rng):
"""境界処理つき多項式突然変異（Debの実装）"""
u = rng.random(x.shape)
d1 = (x - lb) / (ub - lb) # 下限までの余裕
d2 = (ub - x) / (ub - lb) # 上限までの余裕
p = 1 / (eta_m + 1)
val_lo = 2 * u + (1 - 2 * u) * (1 - d1) ** (eta_m + 1)
val_hi = 2 * (1 - u) + 2 * (u - 0.5) * (1 - d2) ** (eta_m + 1)
dq = np.where(u <= 0.5, val_lo ** p - 1, 1 - val_hi ** p)
return x + dq * (ub - lb)
x = np.full(300_000, 0.02) # 下限ぎりぎりの変数
y_simple = pm_simple(x, 0.0, 1.0, 20, rng)
y_bounded = pm_bounded(x, 0.0, 1.0, 20, rng)
print(f'クリップ版 : 境界に張り付いた割合={np.mean(y_simple <= 1e-12):.4f}')
print(f'境界処理つき版: 境界に張り付いた割合={np.mean(y_bounded <= 1e-12):.4f}')
クリップ版 : 境界に張り付いた割合=0.3261
境界処理つき版: 境界に張り付いた割合=0.0000
クリップ版では33%の解が $x = 0$ ちょうどに集まってしまいました。分布で見るとこうなります。
- 左（クリップ版）：$x = 0$ に33%が集中し、そこだけ確率密度が突き抜けています
- 右（境界処理つき版）：$x = 0$ 側になだらかに分布し、張り付きがありません
ZDT1やDTLZのように真のパレート最適解が境界にある問題だと、この張り付きは「たまたま当たり」として働いてしまい、アルゴリズムの性能を過大評価する原因になったりします。ベンチマークで比較するときは要注意なポイントです。
境界処理つき版は、乱数 $u \to 0$ のとき変異後の値がちょうど下限 $\text{lb}$ に、$u \to 1$ のときちょうど上限 $\text{ub}$ になるように分布を切り詰めたものです。定義域の外に出る確率がそもそも0なので、丸める必要がないわけですね。⑤の境界処理つきSBXと同じ考え方です。
変異確率は pm = 1/n が定番
もう一つ大事なのが「どの変数を変異させるか」です。実数値GAでは各変数を独立に確率 $p_m$ で変異させ、この $p_m$ には $1/n$（$n$ は変数の数） を使うのが定番です。
1個体あたり期待して1変数だけが変異するという設定と理解すれば良いです。
n = 30
trials = rng.random((200_000, n)) < 1 / n
print(f'1個体あたり変異する変数の数の平均 = {trials.sum(axis=1).mean():.4f}（理論 1）')
print(f'1変数も変異しない個体の割合 = {np.mean(trials.sum(axis=1) == 0):.4f}'
f'（理論 {(1 - 1/n)**n:.4f}）')
1個体あたり変異する変数の数の平均 = 0.9995（理論 1）
1変数も変異しない個体の割合 = 0.3625（理論 0.3617）
1個体あたりの変異する変数の数の期待値はちょうど1で、それでいて36%の個体はまったく変異しません。「交叉で作った良い子をそのまま残す個体」と「1箇所だけ揺さぶる個体」がいい感じに混ざるわけです。なかなかよくできた設定かなと思います。
選択（Selection）：NSGA-IIはどう親を選ぶか
オペレータの3つ目、選択です。NSGA-IIではバイナリトーナメント選択を使います。
① 集団からランダムに2個体を選ぶ
② 良い方を親にする
③ ①②をもう一度やって2人目の親を決める
シンプルなのですが、多目的最適化では「良い方」の定義が問題になります。①で説明したとおり、2つの解がトレードオフの関係にあると優劣がつかないからです。
混雑比較演算子（Crowded-Comparison Operator）
そこでNSGA-IIは、②で説明した非劣解ランクと混雑距離を組み合わせた順序を定義します。これを混雑比較演算子 $\prec_n$ と呼びます。
解 $i$ が解 $j$ より良い（$i \prec_n j$）とは、
(a) $\text{rank}_i < \text{rank}_j$、または
(b) $\text{rank}_i = \text{rank}_j$ かつ $d_i > d_j$（混雑距離が大きい）
つまり 「まずランクで比べる。同ランクなら空いている方を選ぶ」 というルールです。
| 優先順位 | 見るもの | 意味 |
|---|---|---|
| 1番目 | 非劣解ランク | パレートフロントへの収束性 |
| 2番目 | 混雑距離 | 解集合の多様性 |
①で「良い多目的最適化アルゴリズムに求められる性質は収束性と多様性の2つ」と書きましたが、その2つがそのまま優先順位になっているわけです。
def crowded_compare(a, b, rank, cd):
"""混雑比較演算子：aとbのうち良い方のインデックスを返す"""
if rank[a] < rank[b]:
return a
if rank[b] < rank[a]:
return b
return a if cd[a] > cd[b] else b # 同ランクなら混雑距離が大きい方
なお、この $\prec_n$ は次世代を選ぶとき（環境選択）にも使われます。②で説明した「ランクの小さい順にコピーして、あふれたら混雑距離が大きい順」という手順は、まさに $\prec_n$ で2N個体をソートして上位N個を取っているのと同じことです。
MOEA/Dの場合の選択
③のMOEA/Dには、明示的な「選択」のステップがありません。代わりに以下の2つが選択圧の役割を果たしています。
| 仕組み | 対応するもの |
|---|---|
| 親を近傍 $B(i)$ からしか選ばない | 交配選択（似た解どうしを交叉させる） |
| スカラー化関数の値が改善したら置換 | 環境選択（単目的の貪欲な置換） |
⑤で見たように、この「近傍からしか選ばない」がDE演算子の $CR = 1.0$ を成立させている仕掛けでもありました。
ちなみにMOEA/Dの原型では、1つの子解が近傍のすべての解を置き換えられてしまうため、集団が同じ解で埋まる問題がありました。改良版（MOEA/D-DE）では置換できる個数の上限 $n_r$（例：$n_r = 2$）を設けて、これを防いでいます。（個人的にはパラメータが増えるだけなので、近傍の定義をうまくやっていきたいところですが、、、。）
NSGA-IIを完成させる
②で書いた疑似コードに、⑤のSBXと今回の多項式突然変異・トーナメント選択を入れて動くようにします。
まず問題（④で紹介したZDT1、30変数）とIGDの計算です。
import numpy as np
N_VAR = 30
LB, UB = 0.0, 1.0
POP = 100
GEN = 250
def zdt1(X):
"""X: (N, n) -> F: (N, 2)"""
f1 = X[:, 0]
g = 1 + 9 * X[:, 1:].sum(axis=1) / (X.shape[1] - 1)
f2 = g * (1 - np.sqrt(f1 / g))
return np.column_stack([f1, f2])
# 真のパレートフロント f2 = 1 - sqrt(f1)
PF = np.column_stack([np.linspace(0, 1, 500),
1 - np.sqrt(np.linspace(0, 1, 500))])
def igd(F):
"""真のPFの各点から近似解集合への平均最短距離（小さいほど良い）"""
d = np.linalg.norm(PF[:, None, :] - F[None, :, :], axis=2)
return d.min(axis=1).mean()
次に②の非劣解ソートと混雑距離です。②では素直な2重ループで書きましたが、実験で何度も回すのでnumpyでベクトル化しておきます。
def fast_non_dominated_sort(F):
"""ベクトル化した非劣解ソート。フロント（インデックス配列）のリストを返す"""
le = (F[:, None, :] <= F[None, :, :]).all(axis=2)
lt = (F[:, None, :] < F[None, :, :]).any(axis=2)
dom = le & lt # dom[i, j] = i が j を支配
count = dom.sum(axis=0) # 自分を支配する解の数
fronts, remaining = [], np.ones(len(F), dtype=bool)
while remaining.any():
cur = np.where(remaining & (count == 0))[0]
if len(cur) == 0:
break
fronts.append(cur)
remaining[cur] = False
count = count - dom[cur].sum(axis=0)
return fronts
def crowding_distance(F):
n = len(F)
d = np.zeros(n)
if n <= 2:
return np.full(n, np.inf)
for k in range(F.shape[1]):
order = np.argsort(F[:, k])
d[order[0]] = d[order[-1]] = np.inf # 端の解は必ず残す
rng_k = F[order[-1], k] - F[order[0], k]
if rng_k == 0:
continue
d[order[1:-1]] += (F[order[2:], k] - F[order[:-2], k]) / rng_k
return d
そしてメインループです。⑤の sbx と今回の polynomial_mutation を組み込みます。
def polynomial_mutation(x, pm, eta_m, rng):
"""境界処理つき多項式突然変異（確率pmで各変数に適用）"""
y = x.copy()
do = rng.random(N_VAR) < pm
if not do.any():
return y
xi = x[do]
u = rng.random(do.sum())
d1 = (xi - LB) / (UB - LB)
d2 = (UB - xi) / (UB - LB)
p = 1.0 / (eta_m + 1)
val_lo = 2 * u + (1 - 2 * u) * (1 - d1) ** (eta_m + 1)
val_hi = 2 * (1 - u) + 2 * (u - 0.5) * (1 - d2) ** (eta_m + 1)
dq = np.where(u <= 0.5, val_lo ** p - 1, 1 - val_hi ** p)
y[do] = np.clip(xi + dq * (UB - LB), LB, UB)
return y
def nsga2(eta_c=15, eta_m=20, pc=0.9, pm=1.0 / N_VAR,
selection='tournament', seed=0):
rng = np.random.default_rng(seed)
X = rng.uniform(LB, UB, (POP, N_VAR)) # ① 初期集団
F = zdt1(X) # ② 評価
def assign(F_):
"""各個体にランクと混雑距離を割り当てる"""
r, c = np.zeros(len(F_), dtype=int), np.zeros(len(F_))
for i, fr in enumerate(fast_non_dominated_sort(F_)):
r[fr] = i
c[fr] = crowding_distance(F_[fr])
return r, c
rank, cd = assign(F)
history = []
def pick():
"""③ バイナリトーナメント選択（混雑比較演算子）"""
if selection == 'random':
return rng.integers(POP)
a, b = rng.integers(POP, size=2)
if rank[a] < rank[b]:
return a
if rank[b] < rank[a]:
return b
return a if cd[a] > cd[b] else b
for _ in range(GEN):
off = []
while len(off) < POP:
i, j = pick(), pick()
if rng.random() < pc: # ④ 交叉
c1, c2 = sbx(X[i], X[j], eta_c, rng)
else:
c1, c2 = X[i].copy(), X[j].copy()
for c in (c1, c2): # ⑤ 突然変異
off.append(polynomial_mutation(c, pm, eta_m, rng))
Q = np.array(off[:POP])
R = np.vstack([X, Q]) # 親と子を合体（2N個体）
FR = zdt1(R)
# ⑥ 環境選択：ランクの小さい順、あふれたフロントは混雑距離が大きい順
keep = []
for fr in fast_non_dominated_sort(FR):
if len(keep) + len(fr) <= POP:
keep.extend(fr.tolist())
else:
d = crowding_distance(FR[fr])
order = fr[np.argsort(-d)]
keep.extend(order[:POP - len(keep)].tolist())
break
keep = np.array(keep)
X, F = R[keep], FR[keep]
rank, cd = assign(F)
history.append(igd(F[rank == 0]))
return X, F, rank, np.array(history)
動かしてみます。
X, F, rank, hist = nsga2(seed=0)
print(f'初期のIGD = {hist[0]:.4f} → 250世代後のIGD = {hist[-1]:.4f}')
print(f'x2〜x30の平均 = {X[:, 1:].mean():.5f}（真の最適は0）')
初期のIGD = 2.1592 → 250世代後のIGD = 0.0050
x2〜x30の平均 = 0.00031（真の最適は0）
IGDが2.1592から0.0050まで下がり、$x_2 \ldots x_{30}$ もほぼ0になりました。ちゃんとパレートフロントに到達できています。
実験：オペレータを外すと何が壊れるか
ここからが本題です。上のNSGA-IIからオペレータを1つずつ外して、何が起きるかを見ます。集団100・250世代・5シード平均です。
| 設定 | IGD（50世代） | IGD（250世代） | 250世代の標準偏差 | $x_2 \ldots x_{30}$ の平均 | $f_1$ の範囲 | 集団のランク1割合 |
|---|---|---|---|---|---|---|
| 標準（SBX + 多項式突然変異） | 0.1169 | 0.0050 | 0.0001 | 0.0003 | 1.000 | 1.000 |
| 突然変異なし（交叉のみ） | 0.2457 | 0.2090 | 0.0656 | 0.0456 | 1.000 | 1.000 |
| 交叉なし（突然変異のみ） | 1.6135 | 0.4034 | 0.0460 | 0.1006 | 0.912 | 0.508 |
| 選択をランダム化 | 0.1768 | 0.0050 | 0.0001 | 0.0004 | 1.000 | 1.000 |
※「$f_1$ の範囲」は得られた解集合の $f_1$ の最大値−最小値で、1.0に近いほどフロント全体をカバーできている（多様性）ことを示します
※「集団のランク1割合」は集団100個体のうち非劣解ランク1だった割合です
得られたパレートフロントはこうなりました。
IGDの推移で見るとさらにわかりやすいです。
① 突然変異なし：50世代あたりで頭打ちになる
青線を見てください。初見だとそれなりに衝撃的な結果かと思います。 50世代あたりでほぼ横ばい になり、そこから200世代回してもIGDは 0.2457 → 0.2090 と15%しか動いていません。標準設定が同じ250世代で 0.1169 → 0.0050（23分の1）まで下げているのと比べると、事実上止まっていると言っていいかと思います。
図の2枚目を見ると、解はきれいに並んでいるものの真のパレートフロントからまるごと平行移動した位置で止まっています。$x_2 \ldots x_{30}$ の平均が0.0456で固まっているのが原因です。
なぜ止まるかというと、⑤で書いた「交叉は集団にない情報を作れない」がそのまま効くからです。SBXは親の外側に子を作れますが、集団全体が $x_5 \approx 0.05$ に収束してしまえば、そこから作られる子も $x_5 \approx 0.05$ 付近にしかなりません。$x_5 = 0$ へ向かう推進力が消えてしまうわけです。
しかも解の分布（$f_1$ の範囲 = 1.000）も、ランク1割合（1.000）も、標準設定と同じくらい良いという点がいやらしいところです。パレートフロントの形だけ見ると「うまくいってそう」に見えてしまいます。真のフロントが未知の実問題でこれをやると、まず気づけません。。。
5シード間の標準偏差が0.0656（標準設定は0.0001）と桁違いに大きいのも特徴で、どこで止まるかがシード次第というのも読み取れます。再現性という意味でもよくない状態です。
② 交叉なし：進むけど遅すぎる
突然変異だけだと、逆に「止まりはしないがとにかく遅い」という結果になりました（緑線）。250世代かけてIGD 0.4034、まだ収束の途中です。
$p_m = 1/30$ で1変数ずつしか動かさないので、30変数を全部0に持っていくには単純に時間がかかります。集団のランク1割合が0.508しかないのも「まだ集団がバラバラで収束していない」ことを示しています。
交叉＝収束を加速する機能、突然変異＝止まらないようにする機能、という役割分担がはっきり出ました。どちらが欠けても駄目なわけですね。
③ 選択のランダム化：最終的には追いつく
これは予想外でした。トーナメント選択をやめて親を完全ランダムに選ぶようにしても、250世代後のIGDは0.0050で標準設定とまったく同じでした。
差が出たのは収束速度だけです（50世代時点で0.1768 vs 0.1169）。紫線が赤線より緩やかに下がっているのがわかるかと思います。
なぜ影響が小さいかというと、NSGA-IIの選択圧の主役は交配選択ではなく環境選択だからです。表の一番右の列を見てください。標準設定でも集団100個体すべてがランク1（割合1.000）になっています。
つまり、収束が進むと集団はほぼ全員が非劣解になるので、トーナメントで2個体を比べても $\prec_n$ の条件(a)では決着がつかず、条件(b)の混雑距離で決めることになります。これは「収束を進める圧力」ではなく「多様性を保つ圧力」なので、そもそも収束速度への寄与が小さいわけです。
一方で環境選択（2N個体からN個体を選ぶ）は、毎世代確実に半分を切り捨てています。ここが本体だったということですね。
「NSGA-IIの肝は非劣解ソートと混雑距離」と②で書きましたが、それが本当に効いているのは親を選ぶときではなく次世代を選ぶとき、というのがわかったかと思います。
パラメータの目安
分布指数 $\eta_c, \eta_m$ と変異確率も振ってみました。
| 設定 | IGD（50世代） | IGD（250世代） |
|---|---|---|
| $\eta_c = 2$（広く飛ぶ交叉） | 0.1056 | 0.0051 |
| $\eta_c = 15$（標準） | 0.1169 | 0.0050 |
| $\eta_c = 50$（親の近くだけ） | 0.1856 | 0.0052 |
| $\eta_m = 5$（大きな変異） | 0.0874 | 0.0047 |
| $\eta_m = 20$（標準） | 0.1169 | 0.0050 |
| $\eta_m = 100$（小さな変異） | 0.2521 | 0.0055 |
| $p_m = 0.5$（変異させすぎ） | 0.1230 | 0.0326 |
読み取れることをまとめます。
- 分布指数は最終的な精度にはほとんど効かない（250世代後は0.0047〜0.0055の範囲）。効くのは収束速度です
- $\eta$ を大きくする（＝子を親の近くに作る）ほど収束は遅くなります。$\eta_m = 100$ の50世代時点のIGDは $\eta_m = 5$ の約3倍（0.2521 対 0.0874）で、それだけ出遅れています
- ただし $p_m$ を上げすぎると壊れます 。$p_m = 0.5$（1個体あたり15変数が変異）ではIGDが0.0326と6倍悪化しました。せっかく交叉で作った良い解が毎回壊されるからですね
ZDT1は素直な問題なので分布指数の差が出にくいですが、④で説明したような多峰性・欺瞞的なベンチマーク（WFGやDTLZの難しい方）だともっと差が出るはずです。
実務的な出発点としては、以下の定番値でまず動かしてみるのが良いかと思います。
| パラメータ | 定番値 | 意味 |
|---|---|---|
| 交叉率 $p_c$ | 0.9 〜 1.0 | ほぼ毎回交叉する |
| 交叉の分布指数 $\eta_c$ | 15 〜 20 | NSGA-II論文以来の定番 |
| 変異確率 $p_m$ | $1/n$ | 1個体あたり期待1変数 |
| 変異の分布指数 $\eta_m$ | 20 | 変数範囲の4.5%が平均移動量 |
| 集団サイズ $N$ | 100（2目的） | 目的数が増えたら増やす |
まとめ：シリーズ全体の振り返り
今回は突然変異と選択を説明しました。
- 多項式突然変異：$\delta$ の分布を「0付近が厚い多項式」で設計し、逆関数法でサンプリングする。SBXと対の設計
- 境界処理は大事：クリップで済ませると33%の解が境界に張り付く。パレート最適解が境界にある問題では性能を誤解する原因になる
- $p_m = 1/n$ は「1個体あたり期待1変数だけ変異」という設定。36%の個体は無変異のまま残る
- 混雑比較演算子 $\prec_n$：ランク優先、同ランクなら混雑距離。収束性と多様性の優先順位そのもの
- 突然変異を外すとNSGA-IIは50世代あたりで頭打ちになる。しかも解の見た目はきれいなままなので気づきにくい
- 交配選択はNSGA-IIの主役ではない。ランダムにしても最終性能は変わらず、効いていたのは環境選択の方だった
6記事を通して、多目的最適化の全体像は以下のように整理できます。
| フェーズ | 内容 | 記事 |
|---|---|---|
| 問題の理解 | パレート支配・パレートフロント・収束性と多様性 | ① |
| アルゴリズム（支配ベース） | NSGA-II：非劣解ソート・混雑距離 | ② |
| アルゴリズム（分解ベース） | MOEA/D：スカラー化・近傍・正規化 | ③ |
| 評価 | ベンチマーク問題（DTLZ・WFG）・Hypervolume・IGD | ④ |
| 中身の実装（交叉） | SBX交叉・DE演算子 | ⑤ |
| 中身の実装（突然変異・選択） | 多項式突然変異・トーナメント選択 | ⑥ |
これから多目的最適化を実装する方は、まず NSGA-II ＋ SBX($\eta_c=15$) ＋ 多項式突然変異($\eta_m=20$, $p_m=1/n$) という定番の組み合わせで動かしてみて、それから問題の性質に合わせて演算子を差し替えていくのがバランスが良いかと思います。
pymoo や jMetal のようなライブラリを使えば全部入っているのですが、中で何が起きているかを知っておくと、うまくいかないときに「交叉が悪いのか、変異が悪いのか、選択が悪いのか」を切り分けられるようになります。今回外して測ってみて、自分でもかなり整理できた気がします。
説明が不十分なところもあるかとは思いますが、何かご指摘あれば優しくコメントいただけると幸いです笑
参考にした記事や本、論文等
- K. Deb and M. Goyal, "A combined genetic adaptive search (GeneAS) for engineering design," Computer Science and Informatics, vol. 26, pp. 30-45, 1996.
- K. Deb and R. B. Agrawal, "Simulated Binary Crossover for Continuous Search Space," Complex Systems, vol. 9, pp. 115-148, 1995.
- 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.
- H. Li and Q. Zhang, "Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II," IEEE Trans. on Evolutionary Computation, vol. 13, no. 2, pp. 284-302, 2009.
- E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective evolutionary algorithms: Empirical results," Evolutionary Computation, vol. 8, no. 2, pp. 173-195, 2000.
- pymoo: Multi-objective Optimization in Python