danglingfarpointer's memoization

仕事周りでの気付き、メモ、愚痴などを書いていきます。

AWS: instance, volume, AMI, snapshotの関係

AWS

触り始めたもののちょっと用語がわかりづらかった。整理のためにメモ。

  • instance: VMのこと(EC2 instanceともいう)
  • volume: instanceにアタッチされるストレージ(EBS, EBS volumeともいう)
  • AMI: instanceのバックアップ(Amazon Machine Imageあるいはimageともいう)
  • shapshot: volumeのバックアップ

instanceには複数のvolumeをアタッチできる。逆に、1つのvolumeを複数のinstanceが共有する（同時にアタッチする）ことはできない。

マネージメントコンソールで起動中のinstanceを指定して'Create Image'すると、AMIが作成される。この際、instanceにアタッチされているvolumeも、snapshotとして保存される。

instance --- (Create Image) ---> AMI
└ volume                         └ snapshot

また、コンソールでvolumeを指定して'Create Snapshot'すると、snapshotが作成される。

instance                    
└ volume --- (Create Snapshot) ---> snapshot

Tesseract OCRで数字の認識

人工知能 OS X

オープンソースで最も認識精度が高いと言われている文字認識エンジン、Tesseractで数字を認識してみる。名刺の中の電話番号を認識する、という想定。OSはMac OS X.

画像の準備

名刺っぽいプリントアウトをスマホのカメラで撮影。 画像サイズは2592x1944. 人名や住所などは全くデタラメw

f:id:danglingfarpointer:20150130191230j:plain

tesseractのインストール

tesseractをMacPortsでインストール。

sudo port install tesseract

ソースコード

処理の流れとして、まず二値化を行い、次に文字認識を適用する。文字認識結果の出力とは別に、二値化の結果画像もtifファイルとして保存する。

文字認識では、数字といくつかの記号をホワイトリストとしている。なので、後に見るように、漢字やアルファベットなども無理やり数字として解釈してしまう。

認識結果の一文字ごとに確信度(confidence)が割り当てられる。認識結果を出力する際は、確信度が高いものと低いものを区別して出力する。低いものにはインデントを付けて出力する。

#include <iostream>
#include <cstdlib>
#include <tesseract/baseapi.h>
#include <leptonica/allheaders.h>

using namespace std;
using namespace tesseract;

int main(int argc, char **argv)
{
    if(argc != 3){
        cerr << "USAGE: " << argv[0]
             << " /path/to/image /path/to/bi-output-image" << endl;
        exit(1);
    }

    char* src = argv[1], *bi = argv[2];

    //
    // 入力画像を二値化する
    //
    PIX *pixsrc = pixRead(src);
    PIX *pixgray = pixConvertRGBToLuminance(pixsrc); // グレイスケールに一度変換
    PIX *pixbi = pixCreate(pixgray->w, pixgray->h, 2);
    // 二値化
    pixOtsuAdaptiveThreshold(pixgray, pixgray->w, pixgray->h, 0, 0, 0.1, NULL, &pixbi);
    pixWrite(bi, pixbi, IFF_TIFF);
    // 要らないものをfinalize
    pixDestroy(&pixsrc);
    pixDestroy(&pixgray);

    //
    // 文字認識実行
    //
    TessBaseAPI tess;
    if(tess.Init(NULL, "eng")){
        cerr << "could not initialize tesseract" << endl;
        exit(1);
    }
    tess.SetVariable("save_blob_choices", "T");
    // ホワイトリスト設定
    tess.SetVariable("tessedit_char_whitelist", "0123456789 -:()");
    tess.SetImage(pixbi);
    tess.Recognize(NULL);

    ResultIterator* ri = tess.GetIterator();
    if(ri != 0){
        // 一文字ずつ結果を見ていく
        do {
            const char* symbol = ri->GetUTF8Text(RIL_SYMBOL);
            if(symbol != 0){
                float conf = ri->Confidence(RIL_SYMBOL);
                // 認識結果と確信度を出力
                if(conf < 80) // 確信度が低ければインデントを付与
                    cout << "    \'" << symbol << "\'" 
                         << " confidence: " << conf << endl;
                else
                    cout << "\'" << symbol << "\'" 
                         << " confidence: " << conf << endl;

                // ChoiceIterator ci(*ri);
                // do {
                //     const char* choice = ci.GetUTF8Text();
                //     cout << "\t\t\t" << "\'" << choice << "\': " 
                //          << ci.Confidence() << endl;
                // } while(ci.Next());
            }
            delete[] symbol;
        } while((ri->Next(RIL_SYMBOL)));
    }

    tess.Clear();
    tess.End();
    pixDestroy(&pixbi);

    return 0;
}

ビルド

g++ -o tess tess.cpp -O2 -I/opt/local/include -L/opt/local/lib -llept -ltesseract

実行

第一引数に入力画像を、第二引数に保存する二値化画像のファイル名を与える。結果は以下のとおり。

$ ./tess cap.jpg cap.tif
    '3' confidence: 55.7878
    '5' confidence: 48.2515
    '1' confidence: 74.4947
    '2' confidence: 74.8571
    '9' confidence: 65.7379
    '4' confidence: 50.08
    '0' confidence: 13.8199
    '3' confidence: 66.5101
    '0' confidence: 22.5098
    '0' confidence: 6.99005
'0' confidence: 91.9207
'8' confidence: 93.2891
'5' confidence: 91.6527
'-' confidence: 94.7043
'0' confidence: 90.4132
'0' confidence: 91.5067
'3' confidence: 95.2874
'2' confidence: 92.9869
    '1' confidence: 64.2396
    '0' confidence: 49.9588
    '5' confidence: 69.2291
    '0' confidence: 16.5115
    '5' confidence: 54.0336
    '1' confidence: 63.1991
    '5' confidence: 52.3447
    '3' confidence: 56.4374
    '1' confidence: 74.0782
    '0' confidence: 44.8059
    '0' confidence: 51.2802
    '5' confidence: 56.8292
    '5' confidence: 50.2101
    '0' confidence: 58.1238
    '0' confidence: 23.41
    '0' confidence: 51.4877
    '5' confidence: 67.2946
    '0' confidence: 29.2511
    '0' confidence: 41.8625
    '0' confidence: 45.2179
    '1' confidence: 73.9682
'7' confidence: 93.7799
'-' confidence: 96.4489
'1' confidence: 88.6481
'4' confidence: 91.9315
'-' confidence: 93.9458
'9' confidence: 90.9804
    '0' confidence: 20.1172
    '1' confidence: 69.0272
':' confidence: 95.3482
'0' confidence: 88.9497
'1' confidence: 94.7421
'5' confidence: 91.4299
'4' confidence: 93.6259
'-' confidence: 96.483
'9' confidence: 90.8426
'7' confidence: 94.9449
'-' confidence: 90.6047
'4' confidence: 91.5667
'8' confidence: 90.4304
'9' confidence: 88.8301
'8' confidence: 94.6282
    '0' confidence: 69.7327
    '0' confidence: 64.6164
    '1' confidence: 70.6974
    '0' confidence: 67.1356
    '0' confidence: 56.4117
':' confidence: 92.6204
    '1' confidence: 70.3545
    '(' confidence: 79.365
    '3' confidence: 73.291
    '0' confidence: 28.9734
    '5' confidence: 70.0992
    '0' confidence: 57.6477
    '0' confidence: 30.6046
    '0' confidence: 74.5287
'5' confidence: 82.144
    '0' confidence: 74.3088
    '0' confidence: 72.9004
    '0' confidence: 50.3754
    '6' confidence: 51.6748
    '0' confidence: 76.4664
    '0' confidence: 16.0721
    '0' confidence: 76.0345
    '6' confidence: 68.1494
    '0' confidence: 19.3069
    '1' confidence: 64.2986
    '0' confidence: 1.06659
    '0' confidence: 75.0809

インデントされているのは確信度が80よりも小さい文字。名刺の中の漢字やアルファベットは、ほとんどが80より小さくなっている。逆に、数字の認識はいずれも確信度が高く、実際にすべて成功している。

従って、確信度の高いチャンクを切り出し、電話番号のフォーマットに合致しているものを取り出せば、今回は電話番号を特定できたことになる。

ちなみに以下が二値化された画像。良好に二値化されている。

f:id:danglingfarpointer:20150130193110p:plain

文字認識エンジンTesseract OCRで学習

人工知能

はじめに

Googleの文字認識エンジンTesseract 3.02での学習プロセスの備忘録。OSはMac OS X. jTessBoxEditorという、学習を省力化するツールを使ってみる。

題材として、デジタル時計や電卓のような文字を認識するための学習をする。文字は[0-9]と:に限定。

参考:

フォントの取得

まずは上述したようなフォントがないと始まらない。

http://www.trojanbear.net/s/category/font の7barSPというフォントを使う。

ダウンロードしたら展開し、OS XのFont bookからインストールする。

tesseractのインストール

最初に、tesseractが依存する画像処理ライブラリleptonicaをインストール。

sudo port install leptonica

次に、tesseract 3.02をソースからインストール。まずパッケージの取得。

wget https://tesseract-ocr.googlecode.com/files/tesseract-ocr-3.02.02.tar.gz
tar xzf tesseract-ocr-3.02.02.tar.gz
cd tesseract-ocr

そしてビルド。配置先はホームディレクトリにする。

./configure --prefix=$HOME/tesseract LIBLEPT_HEADERSDIR=/opt/local/include/leptonica
make
make install

最後に、デフォルトの英語辞書をインストール。

wget https://tesseract-ocr.googlecode.com/files/tesseract-ocr-3.02.eng.tar.gz
tar xzf tesseract-ocr-3.02.eng.tar.gz 
cp tesseract-ocr/tessdata/eng.* $HOME/tesseract/share/tessdata/

学習なしで試してみる

ここで試しに、学習なしで、7barSPフォントで15:39と書かれたイメージを認識させてみる。

f:id:danglingfarpointer:20150128211158p:plain

# ImageMagickでイメージを作成
convert -background white -fill black -font 7barSP -size 150x label:15:39 1539.png
# 数値と':'のみをホワイトリストとするための制御ファイル
echo 'tessedit_char_whitelist 0123456789:' > tess.conf
# 実行 -> byeng.txtに結果が出力される
$HOME/tesseract/bin/tesseract 1539.png byeng -l eng tess.conf

結果は以下のとおり。今のところ認識に失敗している。

$ less byeng.txt
35 35

学習 - 辞書の作成

ここから辞書を作成していく。

1. jTessBoxEditorのインストール

jTessBoxEditorを取得・起動する。

wget -O jTessBoxEditor-1.3.zip http://sourceforge.net/projects/vietocr/files/jTessBoxEditor/jTessBoxEditor-1.3.zip/download
unzip jTessBoxEditor-1.3.zip
cd jTessBoxEditor
# 環境変数を設定
export TESSDATA_PREFIX=$HOME/tesseract/share
# 起動
java -Xms128m -Xmx1024m -jar jTessBoxEditor.jar &

起動後に、GUIから、tesseractの実行ファイルの置かれたディレクトリを指定してやれば、とりあえずツール準備は完了。

2. 学習に必要なデータの準備

jTessBoxEditorを使った学習では、以下のファイルを用意する必要があるようだ。

  • tifファイル: 文字データのイメージをtif形式として保存したもの。今回は0123456789:という文字列のイメージを準備
  • boxファイル: tifファイルの中の一文字一文字の座標と大きさを記録したファイル
  • font propertiesファイル: フォントの情報を与えたもの
  • word listファイル: 単語のリスト。今回は空ファイルとする
  • frequent word listファイル: 頻出単語のリスト。今回は空ファイルとする

以上のファイルを ~/train に作っていく。

2-1. tifファイルとboxファイル

この2つは、jTessBoxEditorを使って生成する。

  • ツールで、'TIFF/Box Generator'というタブを選択
  • 'Output'にledと入力。3文字であれば基本的になんでもよいはず。今回は、フォントの形状がLEDサインを連想させるので、ledと名付ける
  • フォントとして7barSPを選択。フォントサイズは48ptとした
  • 下のペインに0123456789:と入力。本来は学習の精度を上げるために、もっと多くの単語を入力したほうが良いと思われる
  • 'generate'をクリック

f:id:danglingfarpointer:20150128211526p:plain

すると、led.7barsp.exp0.tifとled.7barsp.exp0.boxが生成される。これらを~/trainに移動する。

試しに、'Box Editor'というタブを開き、生成されたtifファイルを選択すると、一文字一文字がどのようにboxされているかを確認できる。

f:id:danglingfarpointer:20150128211628p:plain

このように自動でboxファイルを作れることが、jTessBoxEditorの一番のメリットか。

2-2. font propertiesファイル

これはコマンドラインから作る。

1列目にフォント名7barspを与える（tif/boxファイル名の中の文字列に対応）。 2列目以降には、そのフォントが、italic, bold, fixed, serif, frakturに相当するか否かを、順に0/1で与える。

cd ~/train
echo '7barsp 0 0 0 0 0' > led.font_properties

2-3. word listファイルとfrequent word listファイル

これらはいずれも空ファイルとする。

cd ~/train
touch led.words_list led.frequent_words_list

3. 学習実行

jTessBoxEditorの'Trainer'タブを開き、'Training Data'で~/trainを、'Language'を'led'に設定する。そして、'Train with Existing Box'を指定して'Run'.

ズラズラとログが表示されるが、成功すれば上記5つ以外のファイルがいくつか生成されている。

最後にファイルを1つにまとめる。ledのあとのドットを忘れない。

cd ~/train
$HOME/tesseract/bin/combine_tessdata led.

これで、目的となるled.traineddataという辞書が生成された。$HOME/tesseract/share/tessdata/に移動すれば完了。

cp -f led.traineddata $HOME/tesseract/share/tessdata/

テスト

$HOME/tesseract/bin/tesseract 1539.png byled -l led # 実行 -> byled.txtに結果が出力される

結果は以下の通り。ちゃんと認識できるようになった！

$ less byled.txt
15:39

ノイズの入ったイメージなどでも試してみたい。

MacPortsでMySQL 5.6

OS X

YosemiteでMacPortsでMySQL 5.6をインストールした時の備忘録。

# インストール
sudo port install mysql56 mysql56-server
 
# 初期化
sudo -u _mysql /opt/local/lib/mysql56/bin/mysql_install_db
 
# 一度立ち上げる(/opt/localに移動しないと失敗)
cd /opt/local ; sudo /opt/local/lib/mysql56/bin/mysqld_safe &
 
# 管理者パスワード設定(コマンドラインでパスワード与えるな的なwaringが出る)
/opt/local/lib/mysql56/bin/mysqladmin -u root password '********'
 
# .bashrcでalias設定
cat >> ~/.bashrc <<EOF
alias mysql_start='sudo -s "cd /opt/local; /opt/local/lib/mysql56/bin/mysqld_safe" &'
alias mysql_stop='/opt/local/lib/mysql56/bin/mysqladmin shutdown -uroot -p'
alias mysql_restart='mysql_stop; mysql_start'
alias mysql='/opt/local/lib/mysql56/bin/mysql'
EOF

Widrow-Hoffの学習規則

人工知能 JavaScript

はじめに

前回、識別境界を求めるためのアルゴリズムとしてパーセプトロンを組んだが、その流れで"Widrow-Hoffの学習規則"を組んでみる。ほぼ勉強の備忘録。。

Widrow-Hoffの学習規則

パーセプトロンと同様、2値のラベルが与えられた多次元データを分類するための境界を 求めるアルゴリズム。

パーセプトロンは、与えた学習データが線形識別可能である場合、学習データを正しく分離する境界を必ず返す。一方で、与えたデータが線形識別可能でない場合、アルゴリズムが停止しない。

Widrow-Hoffの学習規則は、与えたデータが線形識別可能でない場合も、誤差をなるべく小さく抑える識別境界を求められる。その代わり、線形識別可能な場合でも、学習データを正しく識別しないことがある。

理論

\({\bf x}_1,\dots,{\bf x}_n\)を学習データ、\(b_1,\dots,b_n\)を各学習データに与えられたラベル（教師信号）とする(\(b_i \in \{-1,+1\}\)). \({\bf w}\)を 線形識別関数の重みベクトル（識別ベクトル）とする。

各学習データ\({\bf x}_i\)について、識別関数による識別結果\({\bf w}^t{\bf x}_i\)と教師信号\(b_i\)の誤差は、以下のようになる。$$\epsilon_i ={\bf w}^t {\bf x}_i - b_i$$

ここで、二乗誤差\(J_i\)を考える。$$J_i = \frac{1}{2}\epsilon_i^2 = \frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2$$

各学習データの二乗誤差\(J_i\)の和\(J\)は以下のようになる。$$J = \sum_i J_i = \sum_i\frac{1}{2}({\bf w}^t {\bf x}_i - b_i)^2 $$

\(J\)を最小化する\({\bf w}\)を求めることが目的となる。ランダムな\({\bf w}\)を初期値とし、最急降下法で反復的に\({\bf w}\)を更新していく。\({\bf w'}\)は１つ前（更新前）の識別関数である: $${\bf w} = {\bf w'} - \rho\frac{\partial J}{\partial {\bf w}}$$

ここで、$$ \frac{\partial J}{{\partial {\bf w}}} = \sum_i \frac{\partial J_i}{{\partial {\bf w}}} = \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$ となるので、\({\bf w}\)の更新式は以下のとおり。 $${\bf w} = {\bf w'} - \rho \sum_i ({\bf w}^t{\bf x}_i - b_i){\bf x}_i$$

例

線形識別できない例を考える。

labelxy
+1 -2 1
+1 -1 4
+1 1 3
+1 3 3
+1 -1 3
-1 -3 1
-1 0 -1
-1 2 1
-1 3 2
-1 0 3

この例に対してパーセプトロンを適用しても停止しないが、Widrow-Hoffの学習規則であれば停止する。

サンプルのソースコード https://gist.github.com/danglingfarpointer/2d425339ea54d4140668 だと、0.402 * x + 1.713という解を出力した。

f:id:danglingfarpointer:20140915192038p:plain

マッチ箱の脳(AI) -- パーセプトロン

人工知能 JavaScript

はじめに

前回の「マッチ箱の脳(AI)」のネタで、今回は「パーセプトロン」を組んでみることにしました。

パーセプトロンとは

機械学習のアルゴリズムの1つで、ラベル付けされた多次元データを、ラベルごとに分類する境界を求めるアルゴリズムです。

以降は簡単のため、2次元データに対して2値のラベル(-1または+1)が付けられるケースに限定します。

例えば:

label x y
+1 -2 1
+1 -1 4
+1 1 3
+1 3 3
-1 -3 -1
-1 0 -1
-1 2 1
-1 3 2

というデータに対しては、y = 0.5x + 1 が+1のデータと-1のデータを分類する境界となります。このような識別境界を求める手法の1つが、パーセプトロンです。

f:id:danglingfarpointer:20140907010057p:plain

パーセプトロンのアルゴリズム

  1. \(ax + by + c = 0\) という直線を考える。\(a, b, c\)はランダムに初期化
  2. \(a, b, c\)が更新されなくなるまで、以下を行う:
    1. 各訓練データ\((x_i, y_i)\)について、
      1. \(k = ax_i + by_i + c \)を求める
      2. \(k\)が\(+\)だが訓練データのラベルが\(-\)である場合、\(a = a-x_i, b = b-y_i, c -= c-1\)と更新
      3. \(k\)が\(-\)だが訓練データのラベルが\(+\)である場合、\(a = a+x_i, b = b+y_i, c = c+1\)と更新

上記が停止した時、\(ax + by + c = 0\)が識別境界となります。非常にシンプルです。なぜこの更新方法で良いのかについては、ちゃんとした理論があるようですが、正確に理解しているか怪しいので飛ばします- -;)

2次元データが「線形識別可能」、つまり直線により識別できるならば、上記のアルゴリズムは必ず停止し、答えが求まります。

例

上述した例に対してパーセプトロンを適用した結果です。5回の更新で識別境界を求めることが出来ました。ちなみにその境界は、 y = 0.581*x + 0.878.最終的な解に至る過程(cycle 0 -- cycle 4)も記しています（色で区別してるだけなので見難いかも）

f:id:danglingfarpointer:20140907010111p:plain

補足

サンプルのJavaScriptソースコード(Node.js). https://gist.github.com/danglingfarpointer/2fa56b9359ec2e260f6b

マッチ箱の脳(AI) -- 遺伝的アルゴリズム

人工知能 JavaScript

はじめに

「マッチ箱の脳(AI)―使える人工知能のお話」という人工知能系のアルゴリズムを分かりやすく解説したKindle本を買いました。その本に触発され、最近仕事で触っているNode.jsのお勉強も兼ねて、「遺伝的アルゴリズム」を題材にプログラムを組んでみることにしました。

マッチ箱の脳(AI)―使える人工知能のお話

マッチ箱の脳(AI)―使える人工知能のお話

遺伝的アルゴリズム

ざっくり説明すると、以下の手続きです。

  • 解こうとしている問題の解の候補を「遺伝子」として表現した上で、
  • 優秀な遺伝子（適応度の高い遺伝子; 優れた解候補）が生き残るようにしつつ、
  • 遺伝子間の交叉や突然変異を通して、世代（遺伝子の集まり）を反復的に進化させていき、
  • 一定の世代数だけ反復した後、もっとも優れた遺伝子を解とする

まさに遺伝子の自然淘汰や突然変異、遺伝子間の交叉をモチーフにしたアプローチです。

適用先

「マッチ箱の脳(AI)」と同様に、遺伝的アルゴリズムをナップサック問題に適用します。ナップサック問題とは、以下のような問題です。

前提:

  • 値段と重さが決まっているn個の品物がある
  • 所定の重さまでしか品物を入れられないナップサックがある

問:

  • ナップサックに入る範囲で、最も値段が高くなる品物の組み合わせは？

例えば、以下の表のような6個の品物をできるだけ値段が高くなるようにナップサックに入れたい。ただし、ナップサックには100KGしかはいらない。どのような品物の組み合わせがベストか?

id 値段 重さ
1 4500円 40KG
2 6000円 56KG
3 4000円 34KG
4 3000円 28KG
5 3000円 36KG
6 6900円 72KG

この答えは、1と2の組み合わせです。10,500円で96KG < 100KGとなります。

ナップサック問題はNP困難であることが知られています。つまり、品物数nが大きい場合、厳密な解を求めようとすると、現実的な時間では終わりません。

しかし、（厳密な解ではなく）最適に近い解であれば、実際は効率的に求められるようです。そうなってくると、あえて遺伝的アルゴリズムの題材にするのはどうかと思いますが、ここはあくまで本の設定に従います。

遺伝子よる解候補の表現

まずはナップサック問題の解候補をどのように「遺伝子」として表現するか。もちろん遺伝子といっても要は単なるオブジェクト表現です。

n個の品物がある場合、解候補は、それぞれの品物の取捨を表すn個の真偽値で表現できます。例えば上述した例であれば、6個の品物から3番目と5番目を選択した解候補は、以下のような遺伝子で表現できます。

[false, false, true, false, true, false]

適応度の定義

「適応度」とは、遺伝子が解候補としてどの程度優れているかを表す値です。大きい値ほど優れているとします。

ナップサック問題の設定を考えると、選択した品物の値段の合計を適応度と定義するのが適当です。ただし、重さの和がナップサックの容量を超えた場合、解とはなりえないので、適応度は0とします。

例えば上述した例で、3番目と5番目を選択した解候補の適応度は、ナップサックの容量を超えていないので(34KG + 36KG < 100KG), 7000(4000円 + 3000円)となります。また、2番目と3番目と4番目を選択した解候補については、ナップサックの容量を超えてしまったので(56KG + 34KG + 28KG < 118KG), 適応度は0となります。

遺伝子の交叉

新しい遺伝子を生成する1つの方法が、遺伝子間の「交叉」です。交叉により、2つの遺伝子の性質を組み合わせて、新たな遺伝子を2つ生成します。

交叉の方法はいくつかパターンがあるようですが、今回は「2点交叉」というものを用います。これは、2つの遺伝子を同じ2箇所で切断し、中央の部分を入れ替える、というものです。

例: 1番目と2番目の間と4番目と5番目の間を切断し、中央部分を入れ替える。

A: t | f t f | t f -----> t | f f f | t f
     |       |
B: f | f f f | t t -----> f | f t f | t t

遺伝子の突然変異

新しい遺伝子を生成するもう1つの方法が、遺伝子の「突然変異」です。ある遺伝子の性質にランダムに変異を与えることで、「ちょっとだけ違う」遺伝子を生成します。

今回は、以下の処理をしています。

  • まずは遺伝子から真偽値を1つだけランダムに選択して逆転
  • 次に遺伝子の全ての真偽値について、それぞれ3%の確率で逆転

優秀な遺伝子の保持

新しい世代を作る際に、古い世代の優秀な遺伝子をいくつかそのまま残すようにします。

優秀な遺伝子の選択の仕方には、これもまたいくつかのパターンがあるようです。今回は、1つの世代を10遺伝子と固定しています。そこで、そのうち最も優れた2つの遺伝子を残すようにします。

プログラム

以上のような感じで作ったプログラムを、以下を置いています: https://gist.github.com/danglingfarpointer/4333496926a5e6dc8c7b

実行するには

Node.jsの実行環境とパッケージ・マネージャー(npm)が必要です。

それらを準備したら、適当なディレクトリを作り、プログラムをindex.jsというファイルで保存し、npm install underscore(依存ライブラリのインストール)を実行して下さい。

MAC OS Xでの例:

mkdir knapsack
cd knapsack
pbpaste > index.js
npm install underscore

次にナップサック問題の品物を定義するCSVファイルを準備します。1列ごとに、品物の値段と重さを書いていきます。上述の例だと、以下のようになります。

4500, 40
6000, 56
4000, 34
3000, 28
3000, 36
6900, 72

そして実行。CSVファイルのパスとナップサックの容量を与えます。

node index.js /path/to/csv/file 100

実行例

http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html で配布されているベンチマークの中で、10個の品物から成るデータセット(P01)を試してみました。ナップサックの容量が165, 最適解(値段の合計)は309です。

パラメタが良くないせいか実行ごとに結構ばらつくのですが、ある試行(100世代反復)の結果をグラフ化しました。

f:id:danglingfarpointer:20140810210831p:plain

縦軸は品物の値段の合計を表します。赤が最適解(309), 青が世代で一番優れた解候補の適応度、緑が世代の適応度の平均値です。80世代過ぎで最適解(309)に到達。適応度の平均値は50から170あたりを不規則にいったりきたりしています。

最後に

遺伝的アルゴリズムによってナップサック問題を解くプログラムをNode.jsで作りました。パラメタ設定や適応度・交叉・突然変異などの方式がナイーブなので、ばらつきの抑止も含め、よくしたいのであればいろいろ考える必要があります。

「マッチ箱の脳(AI)」の中の他の素材も、Node.jsで書いてみたいと思います。