この記事について
前回（③）は CMA-ES を扱いました。今回は進化計算のもう一方の柱、遺伝的アルゴリズム（GA：Genetic Algorithm） です。
実は GA は配送最適化入門シリーズ⑥でも登場しています。ただしあちらは TSP（順列）向けで、OX・PMX という順列専用の交叉を使いました。今回は連続最適化のための 実数値GAとして、SBX交叉と多項式突然変異という実数ベクトル向けの演算子を扱います。同じ GA でも、解の表現が変わると交叉のやり方がガラッと変わる、というのが面白いところです。
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | メタヒューリスティクスとは？／探索の地図 |
| ① | 粒子群最適化（PSO） |
| ② | 蟻コロニー最適化（ACO） |
| ③ | CMA-ES |
| ④（本記事） | 遺伝的アルゴリズム（GA） |
| ⑤ | Cuckoo Search |
| ⑥ | Grey Wolf Optimizer（GWO） |
| ⑦ | Harris Hawks Optimization（HHO） |
| ⑧ | Moth-Flame Optimization（MFO） |
| ⑨ | Grasshopper Optimization（GOA） |
| ⑩ | Golden Jackal Optimization（GJO） |
| ⑪ | Manta Ray Foraging（MRFO） |
| ⑫ | まとめ：メタファー系の正体と使い分け |
GAとは
1975年に John Holland が体系化した、生物の進化（自然選択）を模した最適化手法です。
J. H. Holland, "Adaptation in Natural and Artificial Systems," University of Michigan Press, 1975.
基本のサイクルは配送⑥と同じです。
① 初期集団（個体の集まり）をランダムに生成
② 評価（各個体の目的関数値を計算）
③ 選択（良い個体を親に選ぶ）
④ 交叉（2つの親を組み合わせて子を作る）
⑤ 突然変異（一部をランダムに変化）
⑥ ②に戻って繰り返す
問題は ③〜⑤を実数ベクトルでどう実装するかです。TSP では「都市の順列」を切り貼りしましたが、$x \in \mathbb{R}^n$ のような連続変数では別の演算子が要ります。
核心：SBX交叉と多項式突然変異
SBX交叉（Simulated Binary Crossover）
実数値GAで最もよく使われる交叉です。2つの親 $p_1, p_2$ から、親の近くに子を作りつつ、たまに遠くにも飛ばすよう設計されています。
\begin{aligned}
c_1 &= \tfrac{1}{2}\big[(1+\beta)\,p_1 + (1-\beta)\,p_2\big] \\
c_2 &= \tfrac{1}{2}\big[(1-\beta)\,p_1 + (1+\beta)\,p_2\big]
\end{aligned}
ここで $\beta$（広がり係数）は乱数 $u \sim U[0,1]$ から作ります。
\beta = \begin{cases}
(2u)^{\frac{1}{\eta_c+1}} & (u \le 0.5) \\[4pt]
\left(\dfrac{1}{2(1-u)}\right)^{\frac{1}{\eta_c+1}} & (u > 0.5)
\end{cases}
- $\beta \approx 1$ なら子は親とほぼ同じ（活用）、$\beta$ が大きいと子は親から離れる（探索）
- $\eta_c$（分布指数）が大きいほど子は親の近くに集まる。$\eta_c=15$ あたりが定番
多項式突然変異（Polynomial Mutation）
各遺伝子を確率 $p_m$ で、変数の範囲 $[\text{lb}, \text{ub}]$ に応じて少しずらします。
x' = x + \delta\,(\text{ub}-\text{lb}),\qquad
\delta = \begin{cases}
(2d)^{\frac{1}{\eta_m+1}} - 1 & (d < 0.5)\\[4pt]
1 - (2(1-d))^{\frac{1}{\eta_m+1}} & (d \ge 0.5)
\end{cases}
$\eta_m$ が大きいほど小さな変異になります。⓪の枠組みでは SBX＝既存解の組換え（活用寄り）、突然変異＝ランダムな揺さぶり（探索） という役割分担です。
Python実装
トーナメント選択＋SBX＋多項式突然変異＋エリート保存の構成です。
import numpy as np
def real_ga(func, dim, lb, ub, n_agents=30, n_iter=500, seed=0,
pc=0.9, eta_c=15, eta_m=20):
rng = np.random.default_rng(seed)
pm = 1.0 / dim # 遺伝子あたりの変異確率
X = rng.uniform(lb, ub, (n_agents, dim))
fit = np.array([func(x) for x in X])
best_i = np.argmin(fit)
best_x, best_f = X[best_i].copy(), fit[best_i]
history = []
def tournament(): # ③ トーナメント選択
a, b = rng.integers(n_agents, size=2)
return X[a] if fit[a] < fit[b] else X[b]
for t in range(n_iter):
new = []
while len(new) < n_agents:
p1, p2 = tournament(), tournament()
c1, c2 = p1.copy(), p2.copy()
if rng.random() < pc: # ④ SBX交叉
u = rng.random(dim)
bq = np.where(u <= 0.5, (2 * u) ** (1 / (eta_c + 1)),
(1 / (2 * (1 - u))) ** (1 / (eta_c + 1)))
c1 = 0.5 * ((1 + bq) * p1 + (1 - bq) * p2)
c2 = 0.5 * ((1 - bq) * p1 + (1 + bq) * p2)
for c in (c1, c2): # ⑤ 多項式突然変異
m = rng.random(dim) < pm
d = rng.random(dim)
dq = np.where(d < 0.5, (2 * d) ** (1 / (eta_m + 1)) - 1,
1 - (2 * (1 - d)) ** (1 / (eta_m + 1)))
c[m] = c[m] + dq[m] * (ub - lb)
new.append(np.clip(c, lb, ub))
new = np.array(new[:n_agents])
nfit = np.array([func(x) for x in new])
worst = np.argmax(nfit) # エリート保存
if best_f < nfit[worst]:
new[worst], nfit[worst] = best_x, best_f
X, fit = new, nfit
bi = np.argmin(fit)
if fit[bi] < best_f:
best_f, best_x = fit[bi], X[bi].copy()
history.append(best_f)
return best_x, best_f, history
⓪の Rastrigin（2次元）で動かします。
_, best_f, history = real_ga(rastrigin, dim=2, lb=-5.12, ub=5.12, seed=0)
print(f'GA 最良値 f = {best_f:.6e} （初期 {history[0]:.3f} → 最終 {history[-1]:.3e}）')
GA 最良値 f = 3.917371e-06 （初期 1.702 → 最終 3.917e-06）
収束曲線は次のようになります。
エリート保存があるため最良値は決して悪化せず、階段状に下がっていきます。SBX交叉が「良い親の近く」に子を集めることで、徐々に最適解へ寄っていくわけです。上図を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
plt.figure(figsize=(7, 3.6))
plt.plot(np.maximum(history, 1e-12), color='#e67e22', linewidth=1.7)
plt.yscale('log')
plt.xlabel('反復回数'); plt.ylabel('最良 f（対数軸）')
plt.title('GA の収束曲線（Rastrigin 2D）')
plt.grid(True, alpha=0.3); plt.tight_layout()
plt.savefig('20260801_ga_convergence.png', dpi=150)
10次元・30個体・500反復・10シードで平均すると、最終値は $1.19 \pm 1.34$ でした（⑫で他手法と並べて比較します）。多峰性の Rastrigin 10次元はかなり難しく、古典的GAは「そこそこ良いが完璧ではない」位置づけです。
順列GA（配送⑥）との対応
同じ GA でも、解の表現で演算子が変わります。
| 実数値GA（本記事） | 順列GA（配送⑥） | |
|---|---|---|
| 解の表現 | 実数ベクトル $x \in \mathbb{R}^n$ | 都市の順列 |
| 交叉 | SBX | OX・PMX |
| 突然変異 | 多項式突然変異 | 2都市の入れ替え（スワップ） |
| 適した問題 | 連続最適化（関数最小化・パラメータ調整） | TSP・スケジューリング |
「選択→交叉→突然変異」という骨格は共通で、問題に合わせて交叉・突然変異だけ差し替えるのが GA の汎用性の高さです。
他手法との比較
| GA | PSO（①） | CMA-ES（③） | |
|---|---|---|---|
| 多様性の源 | 交叉＋突然変異 | 群れの分散 | 共分散行列のサンプリング |
| 変数の表現 | 連続・離散・順列など何でも | 連続が得意 | 連続 |
| 連続最適化の強さ | 中程度（要チューニング） | 中程度 | 強い |
| 離散・組合せ | 演算子次第で対応可 | 苦手 | 苦手 |
連続最適化だけなら CMA-ES の方が強いことが多いですが、離散・順列・混合変数も同じ枠組みで扱える柔軟性は GA ならではです。
まとめ
- 実数値GA は「選択→交叉→突然変異」の骨格を、SBX交叉と多項式突然変異で連続変数に対応させたもの
- $\eta_c, \eta_m$（分布指数）が探索と活用のバランスを決める
- 同じ GA でも、表現が変われば交叉が変わる（実数→SBX、順列→OX/PMX）── 配送⑥と対で理解すると見通しが良い
- エリート保存で最良値の悪化を防ぐのが定石
- 連続最適化単体なら CMA-ES に分があるが、何でも扱える汎用性が GA の価値
次回からは2010年代以降に大量に提案された「生物模倣系（メタファー系） 」のメタヒューリスティクスに入ります。まずは Grey Wolf Optimizer（GWO）からです。
参考にした記事や本、論文等
- J. H. Holland, "Adaptation in Natural and Artificial Systems," University of Michigan Press, 1975.
- K. Deb and R. B. Agrawal, "Simulated Binary Crossover for Continuous Search Space," Complex Systems, vol. 9, pp. 115-148, 1995.
- K. Deb and M. Goyal, "A combined genetic adaptive search (GeneAS) for engineering design," Computer Science and Informatics, vol. 26, pp. 30-45, 1996.（多項式突然変異）