300億円欲しい

メジャーリーグのデータ解析します

Rで遺伝的アルゴリズム (その1)

序論

寒いですね。遺伝的アルゴリズムを使いたくなりますね。

しかしMatlab遺伝的アルゴリズムパッケージは有償です。
やっぱMatlabって糞だわ。300億円あったら買うのに。
C言語でゼロから実装しますか。
そんなの面倒でやりたくないです。

お金も頭も使わずに、お手軽に遺伝的アルゴリズムが使いたいのです。

Rで遺伝的アルゴリズム

そこでRです。
Rなら全て """無料""" で遺伝的アルゴリズムのパッケージが使えます。
パッケージに関数を投げるだけです。これは楽。
さすがR。Rは光。一生ついていきます。

Rで遺伝的アルゴリズムを用いた最適化計算をします。
全体の流れは、
遺伝的アルゴリズムパッケージのインストール
・Rスクリプトを書く
・感想
です。

パッケージのインストール

Rの遺伝的アルゴリズムパッケージは用途別にいくつか存在します。
今回は最適パラメータ推定を行うパッケージ「gafit」を利用することにします。

まずはパッケージの導入です。
「gafit」パッケージはCRANのレポジトリにないので自分でダウンロードします。

http://cran.open-source-solution.org/src/contrib/Archive/gafit/

ここからダウンロード。
次に端末を開いて、ダウンロードしたフォルダに移動します。
UbuntuのデフォルトならHome/Downloadsでしょう。そこでRを起動。

cd Downloads
sudo R 

起動したらパッケージのインストールです。
tarファイルの解凍はRが勝手にやってくれます。Rは光。

install.packages("gafit_0.4.1.tar.gz", repos=NULL)

「repos=NULL」が大事。
自分でダウンロードしたパッケージをインストールする場合はこのオプションを付けます。
何も付けないとCRANのレポジトリから探すようになります。

これでパッケージのインストールは終わりです。簡単ですね。

Rスクリプトを書く

最適化計算の実験にはバナナ関数がよく出てきますね。

\[ C(x,y) = (1-x)^2 + 100 (y - x^2)^2 \]

参考文献
http://en.wikipedia.org/wiki/Rosenbrock_function

目的関数をこのバナナ関数にして、最適化計算を行なってみます。

gedit Gafit.R

としてテキストエディタを起動。
下のスクリプトを書き入れます。

##   Gafit.R 

## gafitパッケージを使います。
library(gafit) 

# Banana function で実験します
costfunction <- function(x){
    banana <- (1-x[1])^2 + 100 * (x[2]-x[1]^2)^2
    return(banana)
}

# 関数と変数を定義しておきます。
cost <- expression(costfunction(x))

# gafit()に目的関数と変数の初期値を入れます。
# コスト関数を最小にするような変数を探してくれます。
# 遺伝的アルゴリズムのパラメータは自分で指定できます。
# step はよく分からんです。変数の変化の大きさに対応していると思います。
# maxiter は繰り返しの世代数
# sample  は各世代の人口みたいなものです。変数の数の4倍が推奨されています。

ga_out <- gafit(cost,           # 目的関数
                list(x=c(0,0)),      # 変数の初期値をリストで
                step = 0.1,
                maxiter = 10000,
                sample = 100)
print(ga_out)

これを保存してRを起動。スクリプトを読み込ませます。

> source("Gafit.R")
$x
[1] 0.9983594 0.9964580

attr(,"score")
[1] 9.637703e-06

最適解は$x = (1,1)$, 最適値は0です。
頑張って最適化したので (100サンプル、10000世代)
それなりの解が出ていますね。
サンプル数、世代数を増やせば解は良くなります。


他にも非線形最適化の手法はあります。
例えばnlm関数。これも目的関数と初期値を与えるだけです。

> nlm_out <- nlm(costfunction, c(0,0))
> print(nlm_out)
$minimum
[1] 4.023726e-12

$estimate
[1] 0.999998 0.999996

$gradient
[1] -7.328277e-07  3.605687e-07

$code
[1] 1

$iterations
[1] 26

nlmの方が解がイケています。しかも速いです。

感想

遺伝的アルゴリズムのパッケージ gafit を用いた最適化計算を行いました。
解はイマイチ。時間はかかる。
nlmで解いたほうが速いし上手い結果が得られます。
あまり嬉しくないです。

目的関数の形が簡単だからですかね。
微分できますし、連続ですからね。こんな関数は甘えです。
今回は遺伝的アルゴリズムの使い方だけ確認できました。
前哨戦です。
次回はより実用的で複雑な目的関数を用いることで、
遺伝的アルゴリズムの真価を見せたいと思います。