多変量正規分布による探索

CMA-ES が候補を引く分布は多変量正規分布。

$$x\sim 𝒩(m,{\sigma }^{2}C)$$

3 つの量が別々の意味を持っている。

記号	意味	更新するもの
$m\in {ℝ}^n$	分布の中心。現在の推定解	上位個体の重み付き平均
$\sigma >0$	全体の大きさ	ステップサイズ適応
$C\in {ℝ}^{n\times n}$	形と向き。正定値対称	共分散行列適応

なぜ正規分布なのか#

平均と共分散だけを決めたとき、エントロピーが最大になる分布が正規分布。 つまり「中心と広がり以外の余計な仮定を置かない」という意味で最も無難な選択になる。

加えて実務上の利点がある。

• 線形変換で閉じている。$C=B{D}^2{B}^{\top }$ と分解できれば、 標準正規から $y=BDz$ で引ける（固有値分解）
• 裾が薄いので、極端に外れた候補が出にくい

楕円として読む#

$C$ の固有ベクトルが楕円の軸の向き、 固有値の平方根が各軸の長さを与える。探索の様子を見るとき、 $C$ の固有値の比（＝条件数）を見ると「分布がどれだけ細長くなったか」が分かる。

悪条件な問題では、この比が ${10}^6$ を超えることも珍しくない。 逆にこの比が大きくなりすぎたら、数値的に危うい兆候でもある。

参考文献#

• 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