--> __mm__
4月 7, 2013
Shark 3.0をHomebrewで入れる

Sharkという機械学習・最適化ライブラリがある．今実装してみようとして勉強しているCMA-ESという進化戦略アルゴリズムも実装されている，C++のライブラリ．homebrewでも入れられるのだが，バージョンが2.3.4と古く，最新の3を入れたい．（というか2.3.4はエラーが出てインストールできなかった）ということでsvnでソースを落としてきてインストールするFormulaを書いた．

https://gist.github.com/mitmul/5304582

12:28am  |   URL: http://tmblr.co/Z-0xevi27WV3
(リアクション: 1)
  
4月 7, 2013
octaveのインストール on MountainLion

Homebrewを使って入れようとしたら，なぜかやたらと詰まったので，手順をメモ．

普通に入れようとすると…

$brew install octave -v

（-vは詳細なログを排出するオプション） とやると，エラーで止まってしまう．

エラー内容：

Undefined symbols for architecture x86_64:
    "_METIS_NodeComputeSeparator", referenced from:
        _cholmod_metis_bisector in libcholmod.a(cholmod_metis.o)
    "_METIS_NodeND", referenced from:
        _cholmod_metis in libcholmod.a(cholmod_metis.o)
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make[3]: *** [liboctave.la] Error 1
make[2]: *** [all] Error 2
make[1]: *** [all-recursive] Error 1
make: *** [all] Error 2

下準備

まずはgfortranとgccがちゃんと同じバージョンのもので揃っていることを確認．

$brew info gfortran
gfortran: stable 4.8.0 (bottled)
...
$brew info gcc48
gcc48: stable 4.8.0, HEAD

揃ってなかったら一回uninstallしてもう一度installする．

まずはSuiteSparseをダウンロード

$wget http://www.cise.ufl.edu/research/sparse/SuiteSparse/SuiteSparse-4.1.0.tar.gz
$tar xvf SuiteSparse-4.1.0.tar.gz
$cd SuiteSparse

/usr/local以下に入れるとhomebrew的にマズイので，/opt/local以下にインストールするように設定する．また，CHOLMODがMetisを参照してしまうとエラーになるようなので，参照しないようにする．

SuiteSparse_config/SuiteSparse_config_Mac.mk

87: - INSTALL_LIB = /usr/local/lib
87: + INSTALL_LIB = /opt/local/lib
88: - INSTALL_INCLUDE = /usr/local/include
88: + INSTALL_INCLUDE = /opt/local/include
231: - #CHOLMOD_CONFIG = -DNPARTITION
231: + CHOLMOD_CONFIG = -DNPARTITION</pre>

Makefile

5: - include SuiteSparse_config/SuiteSparse_config.mk
5: + include SuiteSparse_config/SuiteSparse_config_Mac.mk

makeしてインストール

$make library
$make install

/opt/local以下にSuiteSparse関連のライブラリ群がきちんと入っていることを確認したら，/usr/local/Library/Formula/octave.rbの39行目を変更してSuiteSparseの依存定義をコメントアウト．

39: - depends_on 'suite-sparse'
39: + #depends_on 'suite-sparse'

保存したら，homebrewでインストールする．

$LDFLAGS=-L/opt/local/lib CPPFLAGS=-I/opt/local/include brew install octave

でoctaveが入る．

12:27am  |   URL: http://tmblr.co/Z-0xevi278BD
(リアクション: 1)
  
3月 31, 2013
実数値遺伝的アルゴリズム

2000年の人工知能学会誌に実数値GAとその応用という解説記事が掲載されている．普通のGA（genetic algorithm＝遺伝的アルゴリズム）は，交叉（子を生成する）を行うために探索する変数をいちいちコード化という作業で01010011のような「遺伝子型」と呼ばれる配列に変換する必要があるが，これを実数値のまま（GAでは「表現型」という）交叉を行う，という手法を実数値遺伝的アルゴリズム（real-coded genetic algorithm）という．

さて，GAを用いて，関数最適化（ある関数が最小値，もしくは最大値をとるときは一体どんなときか？を調べること）を行いたいとする．このとき，関数が連続なら，その決定変数は実数値なので，実数値GAを用いたい．で，上記論文に目を通したので，内容を自分用メモとして以下にまとめておく．

関数最適化の際に考慮すべき一般的な関数最適化問題の性質

  1. 変数の連続性
  2. 変数間の依存関係
    • 依存関係がある場合座標軸と平行でない谷もしくは尾根がある
    • （関数最小化の場合谷が大事，最大化の場合尾根が大事）
  3. 座標系のスケール
    • 軸ごとにものすごくスケールが違う場合，その次元とその他の次元を同程度探索させるのが難しくなるので，定義域の正規化が必要になる
  4. 局所最適解の数
    • ちっさな山（もしくは谷）がいっぱいある関数を多峰性関数という

普通のGAによる関数最適化の手順は

  1. 探索変数空間に探索点（個体）をばらまく
  2. 各個体の適応度（関数の値）を計算する
  3. 子供を生成する（交叉）
  4. 適当な確率で個体を選んでそいつの値をランダムに変更する（突然変異）
  5. 親の個体群と子供の個体群を合わせた集団の中から，個体数を一定に保つために適当に個体を選抜する（淘汰，もしくは単純に選択ともいう）
  6. 2に戻る

詳しくはこことかを参照．

機能分担仮説

GAの手順のうち「交叉」と「淘汰（選択）」について，「機能分担仮説*1」というのが喜多らによって唱えられ，交叉では「個体群として表現された探索領域の情報をできるだけ活用しつつ，新しい探索点を生成すること」（すなわち親集団がもつ平均や分散などの統計値を加味して子の位置を決めること）に専念し，淘汰（選択）では「探索空間内において重点的に探索すべき領域を個体群として示すこと」（すなわちより最適解に近い位置にいる個体だけを残すようにすること）に専念すべきだ，という指針が提案されている．

喜多ら*2が提案した交叉の設計指針

機能分担仮説に基づく少し具体的な実数値GAにおける交叉の設計指針

  1. 統計量の遺伝
    • 子の分布は親の分布の平均値・分散・共分散を継承するようにする
  2. 多様な解の生成
    • 「統計量の遺伝」という拘束条件のもとで，できるだけ多様な解を生成するようにする
  3. ロバスト性の確保
    • 探索をよりロバストにするために，子の分布が指針1を満たす分布よりも若干広いものになるようにする

設計指針1だけだと「親をそのまま子にする」という探索上無意味なことが起こるので，指針2を追加．最適解を含む領域に親の集団が分布していたとしても，選択が不適切に行われることで最適解に向かって個体群が集中化しない場合もある．そのために指針3が必要．ただし，探索のロバスト化と効率化の間にはトレードオフの関係がある．

従来の交叉

  • ビットストリング上の交叉
    • ビットストリングというのは0100111のような形で表現された遺伝子型のことをいう．（Gray表現が用いられることもある．）
    • 遺伝子型空間の位相構造（距離の定義のされ方）は表現型空間のそれとは大きく違う
    • 遺伝子型は離散的な表現になるので連続性が全く考慮されない
    • そのせいで子集団が親集団の「分布」を引き継げない＝設計指針1を満たさない
  • Gray表現上の交叉
    • Gray表現では隣接する数のハミング距離が1になるようになってるので位相構造の差異という観点においてはビットストリングよりはまし
    • でも隣り合わない数については保証の限りではない
    • やはり設計指針1を満たさない

コード化なんかしたらいいことないよ，という話．

実数ベクトル上の交叉

この論文以前にも実数ベクトル上の交叉は提案されていて，以下の2つがある．

  • 成分ごとに独立に値を生成するタイプ
    • 成分ごと（変数の各次元の値ごと）に独立に子のベクトルの要素を決定していく
    • 独立に決定してしまうと共分散は無条件に0（関連性なし）に近づいてしまう（設計指針1に反する）
  • 親の線形結合により生成するタイプ
    • 両親の内分点を子とするものは分布を必ず縮小させてしまう
    • 両親を結ぶ直線上の中点や外挿点に子を生成する場合はその限りではないが設計指針2にある「多様性」はあまり担保されない

いくつかある過去の実数ベクトルの交叉手法の中でもBLX-α*3と呼ばれるものは突然変異なしでもいい感じに動くが変数間に依存関係があるとからっきしだめであることが分かっている*4*5

  • BLX-αの交叉手順
    1. 2つの親個体{\bf x}^1, {\bf x}^2を選ぶ
    2. 子個体{\bf x}^cの各成分x_i^cを区間\left[X_i^2,X_i^2\right]から一様乱数で成分ごとに独立に決定する．区間は以下のようにして決める．
      • X_i^1={\rm min}(x_i^1,x_i^2)-\alpha d_i（両親の第i成分のうち小さい方をさらに\alpha d_iで小さくしたもの）
      • X_i^2={\rm max}(x_i^1,x_i^2)+\alpha d_i（両親の第i成分のうち大きい方をさらに\alpha d_iで大きくしたもの）
      • d_i = |x_i^1 - x_i^2|（第i成分における両親の差）

設計指針を考慮した実数ベクトル上の交叉

単峰性正規分布交叉（Unimodal Normal Distribution Crossover; UNDX）*6*7
  1. 3つの親を選択する（{\bf x}^1,{\bf x}^2,{\bf x}^3とする)
  2. 親{\bf x}^1,{\bf x}^2の中点を{\bf x}^p = ({\bf x}^1 + {\bf x}^2)/2とする
  3. 親{\bf x}^1,{\bf x}^2の差ベクトルを{\bf d}={\bf x}^1 - {\bf x}^2とする
  4. 親{\bf x}^1,{\bf x}^2を結ぶ直線を主探査直線と呼び，親{\bf x}^3から主探査直線までの距離をDとする
  5. 子 {\bf x}^cを以下の式に従って生成する
    • {\bf x}^c = {\bf x}^p + \xi {\bf d} + \displaystyle \sum_{i=1}^{n-1} \eta _i D e_i
    • \xi \sim N(0, \sigma_\xi^2)，\eta_i \sim N(0,\sigma_\eta^2)
    • {\bf e}_iは主探索直線に直行する部分空間の正規直交基底ベクトル（主探索直線に直交する平面=2次元空間）
      • （ベクトル {\bf x}と直交する部分空間とは，その部分空間に含まれるすべてのベクトルが {\bf x}と直交するようなもののことをいう）
    • \sigma_\xi = 1/2， \sigma_\eta = 0.35/\sqrt{n}，が経験的に良いといわれるパラメータらしい．
    • （ちなみに確率変数 Xがある確率分布 \muに従うときこれを X \sim \muと書く）

要は，ある2つの親の中点から，1つ目の親に向かっていくらか移動し，2つの親を結ぶ直線に垂直な方向にいくらか移動した位置に子を生成する，ということだ．今出てきた2つの「いくらか」はそれぞれ異なる分散を持つ正規乱数によって決まる，というわけである．

多数の親を用いる単峰性正規分布交叉（UNDX-m）*8

UNDXでは基本的には2つの親個体を結ぶ直線の近傍に子個体を生成する．そのため，探索空間上を網目状に覆った形でしか子個体が生成されない*9．そこで，多数の親個体の重心位置を中心として，より多次元に広がる正規分布を使おうというのがUNDX-mらしい．手順は，

  1. 個体群からm+1個の親子体をランダムに選択する（ {\bf x}^1 \dots {\bf x}^{m+1}）
  2. それらの親個体の幾何学的重心を計算する（ {\bf p}とする）
  3. 親個体 {\bf x}^{m+2}を個体群からランダムに選択
  4. 重心から {\bf x}^{k}へ向かうベクトルを {\bf d}^{k}={\bf x}^{k} - {\bf p}としたとき， {\bf d}^{k}(k=1,2,\dots,m+1)のすべてに直交するベクトルを正規化したものと， {\bf d}^{m+2}の内積をDとする．
    • これどうやって計算するねんと思ったら，ここに解説があった．でも”この方法は数学的に証明していないため信頼性はない”とのこと…（えっ
  5. {\bf d}^{k}(k=1,2,\dots,m+1)のすべてに直交する部分空間の正規直交基底を {\bf e}^{k}(k=1,2,\dots,n-m)とする
  6. 子 {\bf x}^cを次式に従って生成
    • {\bf x}^{c \pm} = p \pm \displaystyle \sum_{i=1}^m w_i d^i \pm \sum_{i=1}^{n-m} v_i D e^i
    • w_i, v_iはそれぞれ正規分布 N(0, \sigma_\xi^2),N(0, \sigma_\eta^2)に従う乱数
    • \sigma_\xi=\alpha / \sqrt{m},\alpha = 1，\sigma_\eta=\frac{1}{\sqrt{n-m}} \frac{\sqrt{m+1}}{\sqrt{m+2}} \frac{\sqrt{3}}{\sqrt{2}} \beta, \beta=0.35が推奨値．

UNDX-mはUNDXよりも距離Dを使う副探索空間への依存度が低いので座標系のスケールへの依存性も軽減されているが，0じゃない，という問題が強いて言えばある．（実際この論文の最後に行われている数値実験では座標系のスケールが大きく違うような関数に対しては次にまとめるSPXよりも悪い．）

シンプレックス交叉（Simplex Crossover; SPX）*10*11
  1. n+1個の親を {\bf x}^0, \cdots, {\bf x}^nとする
  2. 親の幾何学的重心を {\bf g}=(1/(n+1))\sum_i x^iとする
  3. {\bf c}^0 = {\bf o}, {\bf p}^0 = {\bf g} + \alpha({\bf x}^0 - {\bf g})とする
  4. {\bf c}^k,{\bf p}^kをk=1,…,nについて次式で求める
    • {\bf p}^k = {\bf g} + \alpha( {\bf x}^k - {\bf g})
    • {\bf c}^k = r_{k-1}( {\bf p}^{k-1} - {\bf p}^k + {\bf c}^{k-1})
    • αは正の定数で， \alpha=\sqrt{n+2}とすると分散・共分散行列の保存が行えるらしい． r_kは区間[0, 1]の一様乱数 u(0, 1)を用いて r_k=(u(0,1))^{\frac{1}{k+1}}で定義される．
  5. 子 {\bf x}^cを次のようにして得る
    • {\bf x}^c = {\bf p}^c + {\bf c}^n

SPXはUNDXより多様な子を生成できるらしい．しかし，最適解に向かって個体群を集中化させていくための積極的な策をとっていないので，集団サイズを十分に大きくとったり，世代交代モデル（淘汰の仕方）で工夫をしたりする必要がある．

この3つの手法を数値実験で比較したところ，

  • 座標系のスケールが次元ごとに大きく違う場合は，SPX »»> UNDX-m »> UNDXといった感じ
  • ただしSPXは集団サイズを大きくとる必要があるため計算量が増加する．これを厭わなければSPXが最も高性能

という結論のようだった．

と，ここまでまとめてみてこんなページを見つけた．このページによると

2011年12月の時点で私が知る限り、最強の実数値ＧＡは　CMA-ES　と呼ばれるアルゴリズムです。 以下のサイトにＣやFortran, Javaなど様々な言語で書かれたコードがあります：
http://www.lri.fr/~hansen/

とのこと…．ここでまとめた論文では交叉手法はSPXが良さそうだったので，論文内の数値実験で使われていた世代交代モデル（MGGモデルを多親用に拡張したモデル．たぶんJust Generation Gap=JGGというやつ？）について調べて，SPX+JGGバージョンの実数値GAをRubyで実装してみるかーと思ったが，よりよい手法が既にあるようなので次はCMA-ESをまとめて，実装はそちらで試みることにする．

CMA-ESについてはこちらにまとまっているようす．

*1:喜多,出村: “機能分担仮説に基づくGAの設計指針”, 計測と制御, Vo1.38, No.10, pp.612-617, 1999

*2:喜多,小野,小林:”実数値GAのための正規分布交叉に関する理論的考察”,計測自動制御学会論文集,Vol.35,No.11,pp.1333-1333,1999

*3:Eshleman, L. J. and Schaffer, J. D.: “Real-Coded Genetic Algorithms and Interval-Schemata”, Foundations of Genetic AIgorithms, pp.187-202, 1993

*4:Ono, I., Yamamura, M., Kobayashi, S.: “A Genetic Algorithm with Characteristic Preservation for Function Optimization”, Proc. IIZUKA ‘96, pp.511-514, 1996

*5:Salomon, R. : “Performance Degradation of Genetic Algorithms Under Coordinate Rotation”, Proc. 5th Annual Conf. on Evolutionary Programming, pp.155-161, 1996

*6:Ono, I. and Kobayashi, S.: “A Real-coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Clossover”, Ploc. 7th Int’l Conf. on Genetic Algorithms, pp.246-253, 1997

*7:小野, 小林: “単峰性正規分布交叉 UNDX を用いた実数値 GA による関数最適化”, 人工知能学会誌, Vol.14, No.6, pp.1146-1155, 1999

*8:Kita, H., Ono, I. and Kobayashi, S. : “Multi-parental Extension of the Unimodal Normal Distribution Crossover for Real-coded Genetic AIgorithms, Proc. 1999 Congress on Evolutionary Computation, pp.1581-1587, 1999

*9:http://mikilab.doshisha.ac.jp/dia/research/person/takapy/report/weeklyReport/15-20020924/report/report20020502015.html

*10:樋口, 山村: “実数値GAにおけるシンプレクス交叉の提案”, 第26回知詫システムシンポジウム講演資科, pp.267-272, 1999

*11:Tsutsui S., Yamamura, M. and Higuchi, T. : “Multi-parent Recombination with Simplex Crossover in Real Coded Genetic AIgorithms, Proc. Genetic and Evolutionary Computation Conference (GECCO’99), pp.657-664, 1999

mitmul

    コメントを書く

    3:31pm  |   URL: http://tmblr.co/Z-0xevhX-M6O
    (リアクション: 1)