CMA-ES
Covariance Matrix Adaptation Evolution Strategy
本セクションでは、単目的の連続最適化で広く使われている CMA-ES を紹介します。
CMA-ES は、単目的の連続最適化のための、確率的で微分不要な最適化アルゴリズムです。 勾配を必要としないため、Grasshopper の定義のように内部で何が起きているか式の形で書き下せない目的関数にも、そのまま適用できます。 進化戦略（Evolution Strategies, ES）のファミリーに属し、以下のような場合に特に効果的です。
- 変数間に相関がある場合（目的関数が分離不可能な場合）
- 次元によってスケールが大きく異なる場合（悪条件な landscape）
NSGA-II のような遺伝的アルゴリズムとは異なり、CMA-ES は交叉を使用しません。 代わりに、多変量正規分布から新しい候補をサンプリングし、過去の探索ステップの成功履歴に基づいてその分布を適応させます。 つまり個体そのものを組み替えるのではなく、個体を生み出す分布のほうを学習していきます。 探索が進むにつれて、サンプリングの範囲が問題の形に沿った向きと大きさに変わっていきます。
CMA-ES の仕組み
CMA-ES による最適化は、STEP2 から STEP4 を繰り返し実行することで行われます。
STEP1: 初期化
以下の 3 つの値が初期化されます。
- 平均
m: 開始点（通常は探索範囲の中心） - ステップサイズ
σ: 探索全体のスケールを制御 - 共分散行列
C = I: 単位行列として開始（等方的で、変数間の相関なし）
この時点では変数間の相関について何もわかっていないので、C
は単位行列から始めます。 相関は STEP4 で観測をもとに学習していきます。
STEP2: サンプリング
λ 個の候補解の集団が、多変量正規分布からサンプリングされます。
x_i ~ m + σ · N(0, C), i = 1, ..., λ各候補は、評価すべき変数値の 1 セットを表します。
STEP3: 選択と平均の更新
候補は目的関数の値によってランク付けされます。 上位 μ 個の候補（μ < λ）が選択され、平均はそれらの候補の重み付き重心として更新されます。
m ← Σ w_i · x_i （上位 μ 個の重み付き平均）平均の更新に使われるのは上位 μ 個だけであり、下位の候補がどれだけ悪い値だったかは次の分布の位置に影響しません。
STEP4: 共分散行列とステップサイズの適応
これが CMA-ES を特徴づけるステップです。
- 共分散行列の更新:
Cは成功したステップの方向と大きさを反映するように適応されます。 反復を重ねるにつれて、Cは変数間の相関を学習し、サンプリングの楕円体を問題の幾何学的構造に合わせて変形させます。 - ステップサイズの更新（σ）: 進捗が着実な場合（探索が一貫して一方向に進む場合）は増加し、振動している場合は減少します。 これにより、実行全体を通じて効率的な探索が維持されます。
探索が振動している場合に σ を下げるのは、行き過ぎた探索幅で同じ場所を往復していると考えられるためです。 このように探索幅そのものを自動で調整することで、あらかじめ適切な探索幅を決めておく必要がなくなります。
STEP2 から STEP4 は、試行回数に達するまで繰り返されます。
動作のイメージ
以下のアニメーションは、サンプリング分布（楕円）が目的関数の等高線に合わせて徐々に回転・拡大縮小していく様子を示しています。
楕円が等高線と同じ向きに傾いていくことで、目的関数が改善する方向に沿って候補が生成されるようになります。
主な特性
| Property | Detail |
|---|---|
| Objective type | 単目的のみ |
| Variable type | 連続 |
| Invariance | 回転不変・スケール不変 |
| Recommended number of variables | 最大 ~100 程度 |
回転不変性とは、座標軸が問題に対してどのように配置されていても、CMA-ES が同等の性能を発揮することを意味します。 これは、軸に沿った探索方向を前提とする手法（独立なランダムサンプリングや QMC サンプリングなど）に対する大きな利点です。
変数の数に上限の目安があるのは、共分散行列が変数の数の 2
乗に比例して大きくなるためです。 たとえば変数が 100 個ある場合、C の成分は 1
万個になり、これらを推定するにはそれだけ多くの評価が必要になります。
なお CMA-ES は単目的にしか対応していないため、多目的の問題では多目的に拡張された MO-CMA-ES を選択してください。
CMA-ES を使うべき場面
- 単目的の連続最適化
- 変数間に相関があるか、landscape が軸に沿っていない場合
- 変数の数が中程度である場合（おおよそ 2〜100）
- ベイズ的手法（TPE、GP）がうまく収束しない場合
派生サンプラー（v1.5.0 で追加）
v1.5.0 以降、これまで 1 つだった CMA-ES サンプラーは 3 つの独立したサンプラーに分割されました。 CMA-ES 内のオプションを切り替えるのではなく、サンプラーの一覧から直接バリアントを選ぶ形になっています。
- Restart CMA-ES は、探索が停滞したところで新しい個体群による再探索を行うサンプラーです。 再起動のたびに個体数を増やす IPOP-CMA-ES 戦略と、大小の個体数で交互に再起動する BIPOP-CMA-ES 戦略のいずれかを選べます。 リスタートを行わない通常の CMA-ES では抜け出せない局所解から逃れやすくなります。 連続変数のみに対応し、単目的・制約なしの問題が対象です。
- CMA-ES with Refinement は、試行回数を 3 つのフェーズに分けて使うサンプラーです。 Sobol 準モンテカルロ法による空間充填的な初期化、CMA-ES による共分散行列の適応、そして最良点周辺を探索する準ランダムなガウス精密化（refinement）の順に進みます。 各フェーズの長さは、設定したトライアル数に応じて自動的にスケーリングされます。 こちらも単目的専用です。
まずは通常の CMA-ES から試し、同じ準最適な点に収束を繰り返す場合は Restart CMA-ES へ、トライアル数の終盤を最良点の磨き込みに使いたい場合は CMA-ES with Refinement へ切り替えるとよいでしょう。