CMA-ES

CMA-ES (共分散行列適応進化戦略、Covariance Matrix Adaptation Evolution Strategy の略) は、連続最適化問題のアルゴリズム。目的関数 $f:\mathbb {R} ^{n}\to \mathbb {R}$ の最小値を探す。目的関数の導関数は不要。100次元程度^[1]以下のノイズも乗っている目的関数を想定している。1996年に Nikolaus Hansen と Andreas Ostermeier が発表し^[2]^[3]、その後も改良が続けられている。

概要

ES は進化戦略(evolution strategy)の事で、確率を使用したメタヒューリスティックスの乱択アルゴリズム。多変量正規分布に基づいて新しいサンプルが選ばれる。分布は同じ平均値になるように設定され、突然変異は平均値を変えないように導入される。変数間の依存関係は共分散行列によって扱われる。

CMA は共分散行列適応(covariance matrix adaptation)の事で、分布に基づいて共分散行列を更新する。関数にノイズが多い時にこの手法は有効である。CMAは準ニュートン法の逆ヘッセ行列を使用する方法に似ていて、目的関数を二次関数で近似する。古典的な手法と比べると、目的関数に対する仮定がより少ない。

性能や特徴

多くの進化戦略と比較すると利用者が手作業で指定しないと正常に動作しないパラメータが少ない。

4次元以下の場合、Nelder-Mead法の方が速い場合もあるが、Nelder-Mead法は最小値ではなく極小値に収束することが多い。
ノイズがなく、導関数も既知の場合、準ニュートン法のBFGS法やNEWUOAの方が10倍速い。

目的関数の定義域の各次元のスケーリングは0〜10などに線形変換や指数関数などを使って揃える必要がある^[4]。また、ライブラリには定義域が有界の時にその範囲内に収めるための関数も提供されている^[5]。

C++版の libcmaes では導関数を利用して高速化を図ることもできる^[6]。

n次元の時、反復1回分の計算量は $O(n^{2})$ だが、変数間の依存関係を調べることを諦め、共分散行列の更新を対角要素だけに限定することで計算量を $O(n)$ に減らすことができる^[7]。C言語版は diagonalCovarianceMatrix オプションで指定し、libcmaes はアルゴリズムを sepacmaes に指定することでその動作をする。

実装

以下のプログラミング言語での実装が公開されている^[4]。

参照

^ Tutorial CMA-ES — Evolution Strategies and Covariance Matrix Adaptation
^ Hansen, Nikolaus; Ostermeier, Andreas (1996). “Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation”. Proceedings of the 1996 IEEE International Conference on Evolutionary Computation (IEEE): 312-317. doi:10.1109/ICEC.1996.542381. https://www.lri.fr/~hansen/CMAES.pdf.
^ Hansen, Nikolaus; Ostermeier, Andreas (2001). “Completely derandomized self-adaptation in evolution strategies”. Evolutionary Computation (MIT Press) 9 (2): 159-195. doi:10.1162/106365601750190398. https://www.lri.fr/~hansen/cmaartic.pdf.
^ ^a ^b CMA Evolution Strategy Source Code
^ Defining and using bounds on parameters · beniz/libcmaes Wiki
^ Using a user defined gradient function · beniz/libcmaes Wiki
^ Practical hints · beniz/libcmaes Wiki