はじめに
今回は Nikolaus Hansen 氏の論文 "The CMA Evolution Strategy: A Comparing Review" を紹介します。この論文では、進化型計算の一種である「CMA-ES」を徹底的に比較・レビューし、その有用性を論じています。Sakana-AI さんのモデルマージの中でモデル間の重みと density を最適化していた最適化手法になります。
参考文献:
Nikolaus Hansen, "The CMA Evolution Strategy: A Comparing Review", Studies in Fuzziness and Soft Computing, 2007.
0 数式を見たくない人向けの CMA-ES の簡単な解説
🐣 どうしてもこの記事は数式の嵐になってしまうので…
CMA-ES のやりたいこと
点数（適応度）が割り当てられた実数値ベクトル（個体）の集まり（個体群）があります。この個体群を、より高い点数のベクトルに偏らせた新しい集合に更新したい。そして、その操作を繰り返して最適な解を見つけたいと考えています。
なぜ難しいの？
2 つの変数を持つベクトル $(x, y)$ を考えてみましょう。もし各変数が独立して点数に影響を与えるなら、各変数の最適な値を別々に求めて組み合わせれば簡単に最適解を見つけることができます。つまり、全体の点数が $x$ と $y$ の影響の合計で表せる場合です。
しかし、実際の問題では $x$ と $y$ の間に相互作用があり、変数同士が依存し合っています。このような依存関係は、変数の数が増えるとさらに複雑になり、高得点のベクトルを見つけるのが難しくなります。探索の方向と距離を適切に決めることができれば良い解に近づけますが、複雑な依存関係があるとそれが難しくなります。
方向を決める
変数間の依存性を測る方法として「共分散」があります。共分散が大きいほど、2 つの変数は強く関連しています。自分自身との共分散は特に分散と呼ばれ、これは常に最大の関連性を示します。一方、関連のない変数同士の共分散は0 になります。
🐣 負の値でも関係はありませす。好きの反対は無関心…ですね
CMA-ESでは、全ての変数間の共分散をまとめた「共分散行列」を使って、探索すべき方向を決めます。これにより、変数間の複雑な依存関係を考慮しながら、より良い解が見つかりそうな方向を特定できます。
距離を決める
良い方向がわかっても、どれだけ進むべきか（距離）の調整も重要です。遠くに行き過ぎると良い領域を通り過ぎてしまい、近すぎると探索が非効率になります。CMA-ES では、これまでの探索履歴から「ステップサイズ」と「進化パス」という 2 つの指標を計算し、それらを使って距離を調整します。特に、探索が一方向に順調に進んでいる場合は距離を伸ばし、進んだり戻ったりジグザグしている場合は距離を縮めます。
どんな利点があるの？
共分散行列を用いることで、問題空間がどのように回転していても効率的に探索できます。これは、変数間の依存関係を考慮しない手法にはない特徴です。また、ステップサイズと進化パスによる距離の自動調整により、平坦な領域でも急な変化のある領域でも適切に対応できます。これらの特徴により、CMA-ES はさまざまな最適化問題で高い性能を発揮することができるのです。
1 論文の概要
この論文は、進化戦略（Evolution Strategy, ES）の中でも特に CMA-ES を中心に据えています。CMA-ES は多変量正規分布の共分散行列を適応的に更新するアルゴリズムであり、小さな集団サイズにおいても安定的かつ効率的な探索が可能です。
🐣 多変量正規分布はこんな式だったなぁ
$$
f(\boldsymbol{x}) = \frac{1}{\sqrt{(2\pi)^k |\boldsymbol{\Sigma}|}} \exp\left( -\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\boldsymbol{x} - \boldsymbol{\mu}) \right)
$$
ランダムベクトル（観測値）: 𝒙
次元数（変数の数）: k
分散共分散行列の行列式: |𝚺|
分散共分散行列の逆行列: 𝚺⁻¹
CMA-ES における個体生成
CMA-ES では次世代の個体群は以下の式に基づき生成されます。
生成式:
x_k^{(g+1)} = m^{(g)} + \sigma^{(g)} B^{(g)} D^{(g)} z, \quad z \sim N(0, I)
説明:
- 標準正規分布 $z \sim N(0, I)$ からサンプルを生成。
- 共分散行列 $C = B D^2 B^T$ の固有分解を用いて分布形状を変換。
- $B$: 固有ベクトルを持つ行列（分布の方向）。
- $D$: 固有値の平方根を持つ対角行列（分布の広がり）。
- 分布の平均 $m^{(g)}$ を加え、最終的な個体位置を決定。
これにより、探索分布が問題空間の形状に適応しながら、効率的な探索が可能になります。
主な内容は以下の通りです。
- CMA-ES の基本的な数式モデルとアルゴリズムの解説
- 近年の拡張（例: 大集団サイズでの利用）
- 他の推定分布アルゴリズム（Estimation of Distribution Algorithms, EDA）との比較
補足: 進化型計算としての立ち位置
進化型計算には、組合せ最適化を得意とする遺伝的アルゴリズム (Genetic Algorithm、GA) や、木構造の探索が可能な遺伝的プログラミング (Genetic Programming、GP) があります。これらの手法は主に離散的な問題空間を対象としています。一方、連続値空間を対象とする手法としては、ES (Evolutionary Strategy) や実数値 GA、さらには PSO (Particle Swarm Optimization) や DE (Differential Evolution) などがあります。
一般に、離散的な空間では遺伝子座（各次元や変数に対応する位置）を基準とした交叉演算子が有効に働きますが、連続値空間ではその効果が限定的であることが知られています。このため、ES や PSO では明示的な交叉演算子を採用していません。一方で、実数値 GA のように、ベクトルベースの交叉を活用して連続空間の探索する手法も存在します。
従来の ES では、子個体は主に親個体に対してランダムな摂動（突然変異）を加えることで生成されていました。その突然変異部分を共分散行列を用いた適応的な実装に変えることで探索の効率を大幅に向上させた ES が共分散行列適応 ES (Covariance Matrix Adaptation Evolution Strategy) つまり CMA-ES です。
2 関連研究
CMA-ES は、自己適応型進化戦略の一形態として開発されました。他にも以下のようなアルゴリズムとの関連性が指摘されています。
- EMNA (Estimation of Multivariate Normal Algorithm)
- IDEA (Iterated Density Estimation Evolutionary Algorithm)
これらは CMA-ES と同様、多変量正規分布を用いて分布推定を行いますが、CMA-ES の強みは、探索の頑健性と分布推定の精度にあります。
3 CMA-ES
CMA-ES の中心的な特徴は、探索分布の動的な適応能力にあります。多変量正規分布 $N(m, C)$ を用いて個体群を生成し、適応度の改善方向を基に分布の中心や形状を更新します。以下に主要な手法を説明します。
3.1 共分散行列の推定
探索分布の形状を特徴づける共分散行列 $C$ を各世代ごとに更新し、問題空間に適応します。
更新式
C^{(g+1)} = (1 - c_{cov}) C^{(g)} + c_{cov} \sum_{i=1}^\mu w_i \left(\frac{x_i - m^{(g)}}{\sigma^{(g)}}\right) \left(\frac{x_i - m^{(g)}}{\sigma^{(g)}}\right)^T
説明
- 現世代の共分散行列 $C^{(g)}$ を引き継ぎつつ、次世代の探索方向を反映
- 適応度が高い $\mu$ 個の個体（重み付き $w_i$）の外積 $\left(\frac{x_i - m^{(g)}}{\sigma^{(g)}}\right) \left(\frac{x_i - m^{(g)}}{\sigma^{(g)}}\right)^T$ を用いて、分布の方向性や広がりを更新
- 学習率 $c_{cov}$ により、更新のスムーズさを調整
探索分布が適応度の改善方向に適応し、次世代の個体生成に反映されます。
🐣 過去の広がりを残しつつ、良い結果を基に分布の形を調整して、次の探索に活かすという話です
3.2 集団ベースの共分散行列更新
小さな集団サイズでは、単一世代からの共分散行列の推定は信頼性に欠けます。そこで、過去の世代の情報を活用するために指数平滑化を導入します。
更新式
C^{(g+1)} = (1 - c_{cov})C^{(g)} + \frac{c_{cov}}{\sigma^{(g)^2}} C_{\mu}^{(g+1)}
ここで、$C_{\mu}^{(g+1)}$ は選択された個体からの推定共分散行列です。$c_{cov}$ の設定には以下が一般的です：
c_{cov} = \frac{2}{(n + 2)^2}
説明
この更新により以下を実現します：
- 過去の世代の情報を保持
- 小さな集団サイズでも安定した学習が可能
- 探索の進行に応じて共分散行列を適応
🐣 過去の情報を滑らかに引き継ぎながら、新しいデータを反映して分布の形を安定的に更新する方法です。
3.3 進化パスによる適応
進化パス（Evolution Path）を用いることで、探索分布の方向性を記録し、ステップサイズ $\sigma$ を動的に調整します。
更新式
ステップサイズ $\sigma$ の更新式:
\sigma^{(g+1)} = \sigma^{(g)} \exp\left(\frac{c_\sigma}{d_\sigma} \left(\frac{\|p_\sigma^{(g+1)}\|}{E\|N(0, I)\|} - 1\right)\right)
進化パス $p_\sigma$ の更新式:
p_\sigma^{(g+1)} = (1 - c_\sigma)p_\sigma^{(g)} + \sqrt{c_\sigma (2 - c_\sigma) \mu_{eff}} \frac{m^{(g+1)} - m^{(g)}}{\sigma^{(g)}}
説明
-
進化パス $p_\sigma$ を利用して、中心点の移動が一貫しているかを測定
- 一貫して進んでいる場合は $\sigma$ を拡大し、探索範囲を拡張
- 停滞している場合は $\sigma$ を縮小し、探索精度を向上
- 標準正規分布の期待ノルム $E|N(0, I)|$ を基準とし、動的にステップサイズを調整
これにより、フラットな領域や鋭い谷底での停滞を防ぎ、探索を効率化します。
🐣 進化パスとステップサイズの更新は、探索を「広く進めるべきか」「狭く精密に進めるべきか」を動的に判断するための仕組みです。
3.4 複合的な共分散行列更新
CMA-ES では進化パスによる更新（Rank-1 更新）と集団ベースの更新（Rank-$\mu$ 更新）を統合して共分散行列を更新します。
更新式
C^{(g+1)} = (1 - c_{cov})C^{(g)} + \frac{c_{cov}}{\mu_{cov}} \left(\frac{p_c^{(g+1)}}{\sigma^{(g)}}\right) \left(\frac{p_c^{(g+1)}}{\sigma^{(g)}}\right)^T + c_{cov}\left(1 - \frac{1}{\mu_{cov}}\right) \sum_{i=1}^{\mu} w_i \left(\frac{x_i^{(g+1)} - m^{(g)}}{\sigma^{(g)}}\right) \left(\frac{x_i^{(g+1)} - m^{(g)}}{\sigma^{(g)}}\right)^T
説明
-
Rank-1 更新（進化パス $p_c$ に基づく更新）:
- 探索方向に関する最新の情報を反映
-
Rank-$\mu$ 更新（集団ベースの情報に基づく更新）:
- 複数個体から得られる分布全体の形状情報を反映
- $\mu_{cov}$ により Rank-1 更新と Rank-$\mu$ 更新のバランスを調整
この更新により、CMA-ES は集団サイズや探索問題に柔軟に対応し、高い最適化性能を発揮します。
補足: CMA-ES と Adam
-
方向情報の蓄積:
- 進化パスは、過去の探索方向を記録して一貫性を評価します。
- Adam では勾配の累積（1 次モーメント）を計算し、勾配の平均方向を用いて更新します。
-
スケール調整:
- CMA-ES では進化パスを用いてステップサイズを適応的に変更します。
- Adam は勾配の 2 乗の指数移動平均を追跡し、パラメータ更新時にスケールを調整します。
-
停滞の回避:
- 進化パスは、探索が停滞した場合に探索範囲や分布形状を動的に調整します。
- Adam は、勾配が小さい領域（勾配消失問題）での停滞を防ぐため、学習率を適応的に調整します。
-
違い:
- CMA-ES は適応度（目的関数の評価値）の情報を基に「探索指向」で適応をします。
- Adam は勾配情報を利用し、「勾配指向」で適応をします。局所的な最適解に敏感で、多峰性への直接対応は困難です。
-
共通点:
- どちらも「過去の情報を利用して動的に適応する」という点では共通しています。ただし、CMA-ES は「ブラックボックス最適化」、Adam は「勾配ベース最適化」として設計目的が異なります。
かつては CMA-ES によるニューラルネットワークの重み最適化が試みられていましたが、計算コストの制約から、現在は Adam のような計算効率の高い手法が主流となっています。しかし、計算機パワーの向上と、より複雑な最適化問題への対応の必要性から、CMA-ES の重み最適化への再注目も考えられます。特に、局所解の問題や非常に複雑な損失関数地形を持つ場合において、CMA-ES の探索能力が再評価される可能性があります。
4 数値実験と結果
論文では以下のテスト関数を用いて CMA-ES を評価しています。
- Sphere 関数
- Ellipsoid 関数
- Cigar 関数
結果として、CMA-ES は以下の点で優れた性能を示しました。
- 非線形・非分離問題に対するロバスト性
- 共分散行列の適応的更新による収束速度の向上
捕捉: 他アルゴリズムとの比較
CMA-ES は他の EDA（例えば EMNA）と比較して、分布推定における過剰な収束を回避し、探索多様性を保つ点で優れています。
5 まとめ
CMA-ES は進化的アルゴリズムの中でも特に汎用性が高く、非分離問題や悪条件の最適化問題において優れた性能を発揮します。特に、以下の点が際立っています。
- 多変量正規分布の精密な適応
- ステップサイズの動的調整
- 小規模集団での効率的な探索
CMA-ES の特徴は、共分散行列とステップサイズの動的な適応にあります。これにより、探索方向やスケールを問題空間に合わせて調整し、効率的に最適解へ収束します。この手法は、非線形・非分離の困難な問題においても高い性能を発揮します。
おわりに
CMA-ES は N. Hansen の 2001 年の博士論文でその原型が提案されたそうです。それがいまだに発展し使われ続けているのはすごいですよね。共分散行列を明示的に導入し、進化パスという洗練された概念を用いた設計に感銘を受けました。進化と人工知能のコラボには今後も要チェックですね！ では次の記事でお会いしましょう。