最適化計算アルゴリズムCMA-ESのライブラリlibcmaesを使ってみる

CMA-ESについて

CMA-ES (Covariance Matrix Adaptation Evolution Strategy) は連続最適化アルゴリズムの一種です。日本語では共分散行列適応進化戦略と呼ばれます。進化戦略に基づいて、目的関数

\displaystyle{
f : \mathbb{R}^n \rightarrow \mathbb{R}
}

を最小化する点
\displaystyle{
\mathbf{x}^{*} = \mathop{\rm arg\,min}\limits_{\mathbf{x}}\, f(\mathbf{x})
}

を計算するために使用されます。特徴としては

  • 導関数を計算する必要がない (derivative-freeである)
  • 多峰性の関数やノイズの乗った目的関数に対してもロバストである
  • 並列性が高い

などが挙げられます。

CMA-ES - Wikipedia

このアルゴリズムは以下の論文で提案されたそうです。

N. Hansen, and A. Ostermeier.
Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation.
Evolutionary Computation '96
https://doi.org/10.1109/ICEC.1996.542381

アルゴリズムの概要

イテレーションで多数のサンプリング点を保持し、これらを進化計算の要領で更新していくことで最適解を発見します。進化計算の観点からは、イテレーションがgenerationに対応し、サンプリング点群がpopulationに対応しています。あるpopulationは前のgenerationのpopulationから計算される共分散行列を元に生成されます。


f:id:yuki-koyama:20170123143440p:plain
二次元の目的関数に対しCMA-ESを適用した様子を表した図。出典:Wikimedia Commons by Sentewolf。

libcmaesについて

CMA-ESを実装したライブラリlibcmaesがEmmanuel Benazera氏によって公開されています。ライセンスはLGPLv3です。C++11で書かれています。Python向けのバインディングもあります。

github.com

Mac OS Xでlibcmaesを動かす

下記のページに従います。

Building libcmaes on Mac OSX · beniz/libcmaes Wiki · GitHub

ます必要な依存ライブラリをbrewでインストールします。

$ brew install automake
$ brew install eigen

続いて下記コマンドを実行します。

$ git clone https://github.com/beniz/libcmaes.git
$ cd libcmaes
$ ./autogen.sh
$ ./configure --with-eigen3-include=/usr/local/include/eigen3 CXXFLAGS="-I/usr/local/include -O3" --prefix=[XXX]
$ make
$ make install

環境を変に汚したくなかったので、ここではconfigureのprefixに適当なパス (上記では [XXX] と表示) を与えました。与えたパスの配下に以下のフォルダが生成されます。

[XXX]/include
[XXX]/lib
[XXX]/bin

あとは通常のライブラリと使用方法は同じです。なおbin以下にはテストコードが含まれています。

使用例

以下のように使います。

// ヘッダファイルの読み込み
#include <libcmaes/cmaes.h>

// 目的関数の定義
libcmaes::FitFunc func = [](const double *x, const int N)
{
    double val = 0.0;
    for (int i = 0; i < N; ++ i)
    {
        val += x[i] * x[i];
    }
    return val;
};

int main(int, char**)
{
    // 探索空間の次元
    const int dimension = 10;

    // 初期解の定義
    const std::vector<double> x0(dimension, 10.0);

    // 初期の分散値
    const double sigma = 0.1;

    // 各generationにおける個体数
    const int lambda = 100;

    // 最適化計算の実行
    libcmaes::CMAParameters<> cmaparams(x0, sigma, lambda);
    libcmaes::CMASolutions cmasols = libcmaes::cmaes<>(func, cmaparams);

    // 結果の表示
    std::cout << cmasols << std::endl;

    // 返り値
    return cmasols.run_status();
}

実行結果は以下の通りです。

best solution => f-value=1.28654e-14 / fevals=13300 / sigma=0.00235696 / iter=133 / elaps=28ms / x=  7.8921e-09  1.60128e-10 -9.10801e-09 -4.36625e-08  2.52471e-08  1.12213e-09  -2.0139e-08 -1.15845e-10  2.67003e-08  9.51658e-08

ここでは10次元の関数を最適化するのに、反復回数として133回、時間として28ms必要だったことを示しています。

なぜCMA-ESか

最近読んだ論文でCMA-ESが使われているのを見て気になったので調べました。Derivative-freeなアルゴリズムは使い易いため、今後の自身の研究でも活躍する機会があるかもしれません。

Jungdam Won and Jehee Lee.
Shadow theatre: discovering human motion from a sequence of silhouettes.
SIGGRAPH 2016.
http://mrl.snu.ac.kr/research/ProjectShadowTheatre/ShadowTheatre.htm
www.youtube.com

Gaurav Bharaj, David I. W. Levin, James Tompkin, Yun Fei, Hanspeter Pfister, Wojciech Matusik, and Changxi Zheng.
Computational Design of Metallophone Contact Sounds.
SIGGRAPH Asia 2015.
http://people.seas.harvard.edu/~gaurav/papers/cdmcs_sa_2015/
www.youtube.com