この記事について
前回までは群知能（PSO・ACO）を見てきました。今回は系統の違う 進化戦略（Evolution Strategy） である、CMA-ES（Covariance Matrix Adaptation Evolution Strategy） です。
CMA-ES は「連続最適化のメタヒューリスティクスとして、実務でまず試すべき本命」と言ってよい手法です。ハイパーパラメータ調整や制御・シミュレーション最適化などで広く使われ、ベンチマークでも常に上位に来ます。少し数式は多めですが、「探索する楕円を自分で学習する」 というアイデア一本でなんとなくの概要は理解できます。
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | メタヒューリスティクスとは？／探索の地図 |
| ① | 粒子群最適化（PSO） |
| ② | 蟻コロニー最適化（ACO） |
| ③（本記事） | CMA-ES |
| ④ | 遺伝的アルゴリズム（GA） |
| ⑤ | Cuckoo Search |
| ⑥〜⑪ | Grey Wolf / Harris Hawks / Moth-Flame / Grasshopper / Golden Jackal / Manta Ray |
| ⑫ | まとめ：メタファー系の正体と使い分け |
CMA-ESとは
2001年に Nikolaus Hansen と Andreas Ostermeier が提案しました。「進化」を名乗りますが、生物のメタファーは控えめで、中身はかなり統計的・数学的です。
N. Hansen and A. Ostermeier, "Completely derandomized self-adaptation in evolution strategies,"
Evolutionary Computation, vol. 9, no. 2, pp. 159-195, 2001.
基本の流れは「多変量正規分布から解をサンプリングし、良かった解の方へ分布を動かす」だけです。
① 平均 m を中心に、共分散 C・ステップ幅 σ の正規分布から λ 個の解をサンプリング
② 評価して良い上位 μ 個を選ぶ
③ その μ 個を使って、平均 m・共分散 C・ステップ幅 σ を更新
④ ①に戻る
PSO が「粒子の集団」を直接動かしたのに対し、CMA-ES が動かすのはサンプリング分布そのもの（楕円の中心・形・大きさ）です。ここが最大の違いです。
核心：探索の「楕円」を3つに分けて学習する
CMA-ES がサンプリングに使う正規分布 $\mathcal{N}(m, \sigma^2 C)$ は、図にすると楕円です。CMA-ES はこの楕円の3要素を別々に適応させます。
x_k \sim \underbrace{m}_{\text{中心}} + \underbrace{\sigma}_{\text{大きさ}} \cdot \mathcal{N}(0,\ \underbrace{C}_{\text{形・向き}})
| 要素 | 記号 | 役割 | 適応の仕方 |
|---|---|---|---|
| 平均（中心） | $m$ | 楕円の中心。現在の「最有力地点」 | 良かった上位解の重み付き平均へ移動 |
| 共分散（形・向き） | $C$ | 楕円の縦横比と傾き。どの方向に伸ばして探すか | 良い解が並んだ方向に楕円を伸ばす |
| ステップ幅（大きさ） | $\sigma$ | 楕円全体のスケール。探索の歩幅 | 連続して同じ方向に進めれば大きく、行き戻りが多ければ小さく |
直感的には、CMA-ES は 「良い解が見つかる方向に楕円を伸ばし、その方向へ大股で進む」 ことを毎世代やっています。谷が斜めに走っていても、共分散 $C$ がその傾きを学習して楕円を斜めに傾けてくれるので、効率よく谷を下れるわけです。
ステップ幅 σ の適応（進化パス）
3要素の中でも、ステップ幅 $\sigma$ の適応は CMA-ES の肝です。進化パスという「過去の移動の累積ベクトル」を見て、
- 平均がずっと同じ向きに進み続けている → まだ遠い → $\sigma$ を大きく（大股に）
- 平均が行ったり来たりしている → もう近い → $\sigma$ を小さく（慎重に）
と調整します。「最近の進み方の一貫性」で歩幅を決める、というのは部屋でなくしたスマホを探すような感覚と似ていて、よくできているなと思います。
数式の全体（重み係数 $c_c, c_\sigma, c_1, c_\mu$ など）は標準実装に譲りますが、やりたいことは「楕円の中心・形・大きさを、良かった解の履歴から学習する」だけだと押さえておけば十分です。
Python実装
標準的な (μ/μ_w, λ)-CMA-ES を実装します。少し長いですが、コメントの①〜③が上の擬似コードに対応しています。
import numpy as np
def cma_es(func, x0, sigma0=2.0, max_iter=120, seed=0, lam=None):
rng = np.random.default_rng(seed)
N = len(x0)
xmean = np.array(x0, dtype=float)
sigma = sigma0
# --- 選択に関するパラメータ ---
if lam is None:
lam = 4 + int(3 * np.log(N)) # 個体数 λ
mu = lam // 2 # 親個体数 μ
weights = np.log(mu + 0.5) - np.log(np.arange(1, mu + 1))
weights /= weights.sum() # 上位ほど大きい重み
mueff = 1.0 / np.sum(weights ** 2)
# --- 適応の学習率（論文の標準設定）---
cc = (4 + mueff / N) / (N + 4 + 2 * mueff / N)
cs = (mueff + 2) / (N + mueff + 5)
c1 = 2 / ((N + 1.3) ** 2 + mueff)
cmu = min(1 - c1, 2 * (mueff - 2 + 1 / mueff) / ((N + 2) ** 2 + mueff))
damps = 1 + 2 * max(0, np.sqrt((mueff - 1) / (N + 1)) - 1) + cs
pc = np.zeros(N); ps = np.zeros(N) # 進化パス
B = np.eye(N); Dm = np.ones(N); C = np.eye(N)
invsqrtC = np.eye(N)
chiN = N ** 0.5 * (1 - 1 / (4 * N) + 1 / (21 * N ** 2))
counteval = 0; eigeneval = 0
history = []
for it in range(max_iter):
# ① 正規分布からサンプリング： x = m + σ·C^{1/2}·z
Z = rng.standard_normal((lam, N))
Y = (B @ (Dm[:, None] * Z.T)).T
Xpop = xmean + sigma * Y
counteval += lam
fitness = np.array([func(x) for x in Xpop])
idx = np.argsort(fitness) # ② 評価して上位を選ぶ
history.append(fitness[idx[0]])
# ③-a 平均の更新（上位 μ 個の重み付き平均）
xold = xmean.copy()
xmean = weights @ Xpop[idx[:mu]]
# ③-b 進化パスの更新
ps = (1 - cs) * ps + np.sqrt(cs * (2 - cs) * mueff) * invsqrtC @ (xmean - xold) / sigma
hsig = (np.linalg.norm(ps) / np.sqrt(1 - (1 - cs) ** (2 * counteval / lam)) / chiN
< 1.4 + 2 / (N + 1))
pc = (1 - cc) * pc + hsig * np.sqrt(cc * (2 - cc) * mueff) * (xmean - xold) / sigma
# ③-c 共分散行列の更新（rank-1 + rank-μ）
artmp = (Xpop[idx[:mu]] - xold) / sigma
C = ((1 - c1 - cmu) * C
+ c1 * (np.outer(pc, pc) + (1 - hsig) * cc * (2 - cc) * C)
+ cmu * (artmp.T * weights) @ artmp)
# ③-d ステップ幅の更新
sigma *= np.exp((cs / damps) * (np.linalg.norm(ps) / chiN - 1))
# 共分散行列の固有分解（C^{1/2} を作るため、たまに実行）
if counteval - eigeneval > lam / (c1 + cmu) / N / 10:
eigeneval = counteval
C = np.triu(C) + np.triu(C, 1).T
eigval, B = np.linalg.eigh(C)
Dm = np.sqrt(np.maximum(eigval, 1e-20))
invsqrtC = B @ np.diag(1 / Dm) @ B.T
return xmean, func(xmean), history
⓪の Rastrigin 関数を、初期点 $(4,4)$・初期ステップ幅 $\sigma=2$ で動かします。
xbest, fbest, history = cma_es(rastrigin, x0=[4.0, 4.0], seed=1)
print(f'CMA-ES 最良解 x = [{xbest[0]:.4f}, {xbest[1]:.4f}]')
print(f'CMA-ES 最良値 f = {fbest:.6f}')
print(f'初期世代の最良値 f = {history[0]:.4f} → 最終 f = {history[-1]:.6f}')
CMA-ES 最良解 x = [0.9950, -1.9899]
CMA-ES 最良値 f = 4.974790
初期世代の最良値 f = 41.0305 → 最終 f = 4.974790
…おや、$f \approx 4.97$ で止まってしまいました。大域最適 $f=0$ ではなく、近くの局所最適にハマっています。実はこれ、CMA-ES の重要な性質を表しているので、隠さず掘り下げます。
探索分布が収束していく様子
白い楕円が、各世代のサンプリング分布です。最初は大きく広がっていた楕円が、世代を追うごとに縮みながら1点へ収束していくのがわかります。
- 0〜10世代：楕円が大きく、広い範囲をサンプリング（探索フェーズ）
- 30〜60世代：良い領域を見つけて楕円が縮む（ステップ幅 $\sigma$ が小さくなる）
- 119世代：1点に収束。ただし収束先は大域最適（赤い星）ではなく、手近な局所最適
収束曲線でも、$f \approx 5$ で頭打ちになっている様子が見えます。
局所最適にハマったときの対処：集団サイズを上げる
これは CMA-ES の弱点ではなく、「CMA-ES は基本的に局所最適化器であり、多峰性関数には工夫が要る」 という性質です。① の PSO が群れの多様性で大域最適を引けたのに対し、CMA-ES は分布を1つしか持たないため、近くの谷に素直に収束してしまうわけです。
対処の定番は 集団サイズ $\lambda$ を大きくすることです。サンプリング数が増えれば、遠くの良い谷を引き当てる確率が上がります。$\lambda=50$ にして、乱数シードを変えて5回試します。
for s in range(5):
xb, fb, _ = cma_es(rastrigin, x0=[4.0, 4.0], seed=s, lam=50)
print(f'seed={s}: 最良値 f = {fb:.6f} x = [{xb[0]:.4f}, {xb[1]:.4f}]')
seed=0: 最良値 f = 0.994959 x = [0.9950, -0.0000]
seed=1: 最良値 f = 0.000000 x = [-0.0000, 0.0000]
seed=2: 最良値 f = 0.000000 x = [0.0000, 0.0000]
seed=3: 最良値 f = 0.000000 x = [0.0000, -0.0000]
seed=4: 最良値 f = 0.000000 x = [0.0000, 0.0000]
5回中4回が大域最適 $f=0$ に到達しました。実務向けの IPOP-CMA-ES は、この発想をさらに進めて「収束したら集団サイズを倍にして再スタート」を自動で繰り返し、多峰性関数にも強くしたものです。
他手法との比較
| CMA-ES | PSO（①） | GA（④） | |
|---|---|---|---|
| 動かす対象 | サンプリング分布（楕円の中心・形・大きさ） | 粒子の集団 | 染色体の集団 |
| 変数間の相関 | 共分散行列 $C$ で自動学習（斜めの谷に強い） | 考慮しない | 基本は考慮しない |
| パラメータ調整 | ほぼ不要（初期点と $\sigma$ だけ） | $w, c_1, c_2$ を要調整 | 多い |
| 多峰性への弱さ | 弱い（要リスタート） | 比較的強い | 比較的強い |
| 得意 | 中次元・連続・滑らかでない関数 | 連続全般 | 離散・順列も可 |
CMA-ES の決定的な強みは、共分散行列が変数間の相関（谷の傾き）を自動で学習することと、ユーザーがほとんどパラメータを触らなくていいことです。「とりあえず連続最適化で何か強いやつを」というとき、まず CMA-ES を試すのは理にかなっています。
まとめ
- CMA-ES は、多変量正規分布（楕円）からサンプリングし、良い解の方へ分布を更新する手法
- 動かすのは粒子ではなく、サンプリング分布の中心 $m$・形 $C$・大きさ $\sigma$ の3要素
- 共分散行列 $C$ が変数間の相関を学習するので、斜めに走る谷でも効率よく下れる
- パラメータ調整がほぼ不要で、連続最適化の実務で本命級
- 一方で基本は局所最適化器。多峰性には集団サイズ増やリスタート（IPOP-CMA-ES）が有効
- ⓪の No Free Lunch のとおり、問題（多峰性）によっては素直にハマってしまう
次回は進化計算のもう一方の柱、遺伝的アルゴリズム（GA） を改めて連続最適化の視点から扱います（TSP 版は配送最適化入門⑥を参照）。
参考にした記事や本、論文等
- N. Hansen and A. Ostermeier, "Completely derandomized self-adaptation in evolution strategies," Evolutionary Computation, vol. 9, no. 2, pp. 159-195, 2001.
- N. Hansen, "The CMA Evolution Strategy: A Tutorial," arXiv:1604.00772, 2016.
- A. Auger and N. Hansen, "A restart CMA evolution strategy with increasing population size (IPOP-CMA-ES)," Proc. IEEE CEC, pp. 1769-1776, 2005.