CMA-ESのソースを表示

'''CMA-ES''' ([[共分散行列]]適応[[進化戦略]]、Covariance Matrix Adaptation Evolution Strategy の略) は、連続[[最適化問題]]の[[アルゴリズム]]。目的関数 <math>f: \mathbb{R}^n \to \mathbb{R}</math> の最小値を探す。目的関数の[[導関数]]は不要。100次元程度<ref>[https://www.lri.fr/~hansen/gecco2013-CMA-ES-tutorial.pdf Tutorial CMA-ES — Evolution Strategies and Covariance Matrix Adaptation]</ref>以下のノイズも乗っている目的関数を想定している。[[1996年]]に Nikolaus Hansen と Andreas Ostermeier が発表し<ref>{{cite journal
 |first=Nikolaus
 |last=Hansen
 |first2=Andreas
 |last2=Ostermeier
 |title=Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation
 |journal=Proceedings of the 1996 IEEE International Conference on Evolutionary Computation
 |pages=312-317
 |year=1996
 |publisher=IEEE
 |doi=10.1109/ICEC.1996.542381
 |url=https://www.lri.fr/~hansen/CMAES.pdf
}}</ref><ref>{{cite journal
 |first=Nikolaus
 |last=Hansen
 |first2=Andreas
 |last2=Ostermeier
 |title=Completely derandomized self-adaptation in evolution strategies
 |journal=Evolutionary Computation
 |volume=9
 |number=2
 |pages=159-195
 |year=2001
 |publisher=MIT Press
 |doi=10.1162/106365601750190398
 |url=https://www.lri.fr/~hansen/cmaartic.pdf
}}</ref>、その後も改良が続けられている。

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

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

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

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

目的関数の定義域の各次元のスケーリングは0〜10などに[[線形変換]]や[[指数関数]]などを使って揃える必要がある<ref name="srccode">[https://www.lri.fr/~hansen/cmaes_inmatlab.html CMA Evolution Strategy Source Code]</ref>。また、ライブラリには定義域が有界の時にその範囲内に収めるための関数も提供されている<ref>[https://github.com/beniz/libcmaes/wiki/Defining-and-using-bounds-on-parameters Defining and using bounds on parameters · beniz/libcmaes Wiki]</ref>。

C++版の libcmaes では導関数を利用して高速化を図ることもできる<ref>[https://github.com/beniz/libcmaes/wiki/Using-a-user-defined-gradient-function Using a user defined gradient function · beniz/libcmaes Wiki]</ref>。

n次元の時、反復1回分の計算量は <math>O(n^2)</math> だが、変数間の依存関係を調べることを諦め、共分散行列の更新を対角要素だけに限定することで計算量を <math>O(n)</math> に減らすことができる<ref>[https://github.com/beniz/libcmaes/wiki/Practical-hints Practical hints · beniz/libcmaes Wiki]</ref>。C言語版は diagonalCovarianceMatrix オプションで指定し、libcmaes はアルゴリズムを sepacmaes に指定することでその動作をする。

== 実装 ==
以下の[[プログラミング言語]]での実装が公開されている<ref name="srccode"/>。
* [[C言語]]
* [[C++]]
* [[Fortran]]
* [[Java]] - [[Apache Commons Math]] でも使用されている
* [[MATLAB]], [[Octave]]
* [[Python]]
* [[R言語]]
* [[Scilab]]

== 関連項目 ==
* [[進化戦略]] (ES)

== 参照 ==
{{reflist}}

== 外部リンク ==
* {{official|https://www.lri.fr/~hansen/cmaesintro.html}}

{{DEFAULTSORT:CMAES}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:進化的アルゴリズム]]
[[Category:確率的最適化]]
[[Category:数学に関する記事]]