進化計算の基礎

集団を持ち、評価の良かった個体の情報を使って次の候補を作る。 この繰り返しで解を改善していく枠組み。

用語#

生物からの比喩なので、対応を押さえておくと論文が読みやすい。

用語	実体
個体 (individual)	1 つの解候補 $x\in {ℝ}^n$
集団 (population)	同時に保持する解候補の集まり
世代 (generation)	生成→評価→更新の 1 サイクル
適応度 (fitness)	目的関数値。最小化なら小さいほど良い
選択 (selection)	次に残す個体を選ぶこと

進化戦略の文献では $(\mu ,\lambda )$ や $(\mu +\lambda )$ という記法が出る。 $\lambda$ が 1 世代に生成する子の数、$\mu$ が選び残す親の数。 カンマは子だけから選ぶ（親は必ず捨てる）、プラスは親と子をまとめて選ぶ。 ノイズのある評価では、たまたま良い値を出した親が居座らないカンマ選択が使われる。

なぜ集団を持つのか#

1 点だけを動かす手法は、その点の周りしか知り得ない。集団を持つと、 複数の谷を同時に調べられるうえに、個体どうしの位置関係から 「どちらの方向が有望か」という情報が取り出せる。CMA-ES はこの情報を 共分散行列という形で明示的に蓄える。

弱点#

• 評価回数が多い。1 世代で $\lambda$ 回かかる
• 理論保証が弱い。凸最適化のような収束速度の保証は一般に無い
• ハイパーパラメータが多い手法もある（CMA-ES は既定値がよく調整されており例外的）

参考文献#

• Hans-Georg Beyer, Hans-Paul Schwefel. Evolution strategies — A comprehensive introduction. Natural Computing 1, 2002. https://doi.org/10.1023/A:1015059928466
• Agoston E. Eiben, James E. Smith. Introduction to Evolutionary Computing, 2nd ed. Springer, 2015. https://doi.org/10.1007/978-3-662-44874-8