サンプリングによる探索

分布から引いて、測って、分布を更新するという繰り返し。 探索分布を持つ手法に共通する骨格。

1. x_1, ..., x_λ ~ p_θ        分布から引く
2. f(x_1), ..., f(x_λ)        測る
3. θ ← update(θ, x, f)        分布を更新する

何個引くか#

1 世代の標本数 $\lambda$ は、次の綱引きで決まる。

• 多い … 分布の更新が安定する。並列に評価できる。1 世代が高価
• 少ない … 世代を多く回せる。更新が標本のばらつきに揺さぶられる

CMA-ES の既定値 $\lambda =4+\lfloor 3\ln n\rfloor$ は 次元に対して緩やかにしか増えない。多峰性が強いときは これを増やすのが定石で、IPOP はそれを自動化したもの。

順位を使うか、値を使うか#

更新に目的関数の値そのものを使うか、順位だけを使うかで性質が変わる。

$f$ のスケールが事前に分からないブラックボックスでは、 順位を使う設計の方が頑健になる。

並列化との相性#

同一世代の $\lambda$ 個は互いに独立に評価できる。 評価が高価な問題では、この並列性が実時間を大きく縮める。 勾配降下法のような逐次的な手法と 対照的な利点。

参考文献#

• Jeffrey Larson, Matt Menickelly, Stefan M. Wild. Derivative-free optimization methods. Acta Numerica 28, 2019. https://arxiv.org/abs/1904.11585
• Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016. https://arxiv.org/abs/1604.00772