CMA-ES

Covariance Matrix Adaptation Evolution Strategy。 多変量正規分布 $𝒩(m,{\sigma }^{2}C)$ から候補を引き、 評価の良かった候補の方向へ分布そのものを寄せていく 進化戦略。

Hansen と Ostermeier が 2001 年に提案し、連続変数の ブラックボックス最適化では 現在も標準的な比較対象として使われている。

何が新しかったのか#

それ以前の進化戦略も分布の広がり（ステップサイズ）は 適応させていた。CMA-ES は共分散行列 $C$ そのものを適応させる。 これにより分布が細長く傾いた楕円になれるので、 変数どうしが絡み合った細長い谷でも谷筋に沿って進める。

言い換えると、CMA-ES は探索の途中で問題の座標系を学習している。 悪条件（条件数の大きい）問題に強いのはこのため。

3 つの部品#

部品	役割
分布からの生成	どこを調べるかを決める
共分散行列適応	どの方向へ広く探すかを学ぶ
ステップサイズ適応	全体をどれだけ大きく動かすかを決める

方向と大きさを別々に扱うのが要点で、そのどちらにも 進化パスという 「最近どちらへ進んできたか」の記憶が使われる。

使いどころと限界#

向く場面

• 目的関数が微分できない、あるいは式が分からない
• 次元が数十〜数百程度
• 変数間に強い相関があり、悪条件

向かない場面

• 次元が非常に大きい。$C$ は $n\times n$ なので、 記憶量が $𝒪(n^2)$、更新が $𝒪(n^2)$ かかる （対角に限る sep-CMA-ES などの変種で緩和する）
• 評価が極めて高価。数百回しか許されないなら ベイズ最適化の方が向く

参考文献#

• Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016.（実装まで踏み込んだ標準的な解説） https://arxiv.org/abs/1604.00772
• Nikolaus Hansen, Andreas Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9(2), 2001.（CMA-ES の原論文） https://doi.org/10.1162/106365601750190398
• CMA-ES 公式サイトと参照実装 pycma https://github.com/CMA-ES/pycma