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

はじめに

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

マッチ箱の脳(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世代反復)の結果をグラフ化しました。

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

最後に

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

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