進化パス

世代をまたいで移動方向を溜め込んだベクトル。 evolution path。 CMA-ES には $p_c$ と $p_{\sigma }$ の 2 本ある。

$$p_c\leftarrow (1-c_c)p_c+\sqrt{c_c(2-c_c){\mu }_{\text{eff}}}\frac{m^{(g+1)}-m^{(g)}}{\sigma }$$

指数移動平均の形で、直近の動きを足しつつ古い情報を減衰させている。

符号の情報を救う#

これが進化パスの存在理由。共分散行列の更新は $y{y}^{\top }$ という外積を使うので、 $y$ と $-y$ が同じ寄与になる。1 世代分の情報だけでは向きの符号が失われる。

しかし「毎世代同じ向きに進み続けている」のと 「毎世代逆向きに行ったり来たりしている」のでは、意味が正反対。 前者は谷筋を順調に下っている、後者は行き過ぎて振動している。

進化パスは移動を足し合わせてから外積を取るので、この区別がつく。 同じ向きが続けば $p_c$ は長くなり、往復していれば打ち消し合って短くなる。

2 本の使い分け#

パス	使い道	座標系
$p_c$	共分散行列の rank-one 更新	そのまま
$p_{\sigma }$	ステップサイズの調整	白色化した空間

$p_{\sigma }$ を白色化した空間で測るのは、 「分布の形の影響を除いた上で、進み方が偏っているか」を判定したいから。

正規化係数の意味#

$\sqrt{c_c(2-c_c){\mu }_{\text{eff}}}$ という係数は、 ランダムに動いているときに $p_c$ の分布が $𝒩(0,C)$ になるよう選ばれている。 これにより「今の $p_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