この記事について

前回までは群知能（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.