ステップサイズ適応

分布全体の大きさ $\sigma$ を毎世代調整する。 CMA-ES では CSA (Cumulative Step-size Adaptation) と呼ばれる方式を使う。

$$\sigma \leftarrow \sigma \exp \left(\frac{c_{\sigma }}{d_{\sigma }}(\frac{\Vert p_{\sigma }\Vert }{𝔼\Vert 𝒩(0,I)\Vert }-1)\right)$$

判断の理屈#

進化パス $p_{\sigma }$ の長さを、 でたらめに動いたときの期待される長さと比べる。

$\Vert p_{\sigma }\Vert$ の状態	意味	$\sigma$ の扱い
期待値より長い	同じ向きに進み続けている。もっと大股で行ける	大きくする
期待値と同程度	ランダムウォーク並み。ちょうどよい	そのまま
期待値より短い	行ったり来たりしている。行き過ぎ	小さくする

連続する世代の移動が無相関になるステップサイズが最適、という考え方。 相関が正なら小さすぎ、負なら大きすぎ、という判定になっている。

なぜ $\sigma$ を別扱いするのか#

共分散行列の更新は、 学習率が小さいため反応が遅い（$n$ が大きいほど遅い）。 一方でステップサイズは速く動かす必要がある。 最適解に近づいたら急いで縮めないと、いつまでも飛び越えてしまう。

そこで「方向（遅く学ぶ）」と「大きさ（速く学ぶ）」を分離した。 $\sigma$ が指数的に縮められるので、収束段階では $\sigma$ が幾何級数的に小さくなり、線形収束に近い挙動になる。

停止条件としても使える

$\sigma$ が十分小さくなったら、それ以上動く余地が無いということ。 実装では $\sigma$ や $\sigma \sqrt{\max \text{eig}(C)}$ が閾値を 下回ったら停止する、という判定がよく使われる。

参考文献#

• 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