進化計算
集団を持ち、良かった個体に寄せながら次の候補を作る枠組み。勾配が無くても回るので、微分できない目的関数やノイズのある評価で使われる。
生物の進化になぞらえた最適化手法の総称。解の集団を保持し、 評価の良かったものを残して次の世代を作ることを繰り返す。
共通の骨格#
名前は色々あるが、やっていることは次の 3 つの繰り返しに落ちる。
- 生成 — いまの情報から候補を複数作る
- 評価 — それぞれの目的関数値を測る
- 更新 — 良かったものに寄せて、次の生成の仕方を変える
勾配を一切使わないので、目的関数が微分できなくても、式が分からなくても、 値にノイズが乗っていても回る。代わりに評価回数は多く必要になる。
何が違うのか#
手法の違いは、ほぼ「次の候補をどう作るか」に集約される。
| 手法 | 次の候補の作り方 |
|---|---|
| 遺伝的アルゴリズム | 良い個体どうしを交叉させ、一部を突然変異させる |
| 進化戦略 | 親に正規分布のノイズを足す。分布の形自体も適応させる |
| 差分進化 | 集団内の 2 個体の差ベクトルを第 3 の個体に足す |
| CMA-ES | 多変量正規分布から引く。その共分散行列を成功方向に合わせる |
このうち連続変数の問題で標準的な比較対象になっているのが 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
- Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016. https://arxiv.org/abs/1604.00772