進化戦略 — 知識ノート

連続変数向けの進化計算。 Evolution Strategy、ES。親に正規分布のノイズを足して子を作り、良かったものを次の親にする。 1960 年代に Rechenberg と Schwefel がベルリン工科大学で始めた。

x_{i} = m + σ z_{i}, z_{i} \sim 𝒩 (0, C)

$m$ … 分布の中心（現在の推定解）
$σ$ … ステップサイズ。どれくらい広く探すか
$C$ … 共分散行列。どの方向へ広く探すか

何を適応させるかで世代が分かれる#

ES の歴史は「分布のどこまでを自動調整するか」の歴史になっている。

適応させるもの	手法
何も（ $σ$ 固定）	素朴な $(1 + 1)$ -ES
$σ$ だけ	1/5 成功則、自己適応 ES
$σ$ と $C$ の対角成分	対角 ES
$σ$ と $C$ 全体	CMA-ES

$C$ 全体を適応させると、変数間の相関を捉えられる。細長い谷を持つ関数で決定的な差になる。

1/5 成功則#

Rechenberg が導いた古典的な指針。子のうち親より良かった割合が 1/5 より高ければ $σ$ を大きく、低ければ小さくする。 成功率が高いのは慎重に進みすぎている（もっと大胆に動ける）、低いのは大きく飛びすぎているという解釈。現代のステップサイズ適応も動機は同じで、判断材料をより洗練させたもの。

参考文献#

Hans-Georg Beyer, Hans-Paul Schwefel. Evolution strategies — A comprehensive introduction. Natural Computing 1, 2002. https://doi.org/10.1023/A:1015059928466
Nikolaus Hansen, Dirk V. Arnold, Anne Auger. Evolution Strategies. In Springer Handbook of Computational Intelligence, 2015. https://doi.org/10.1007/978-3-662-43505-2_44
Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016. https://arxiv.org/abs/1604.00772