静岡大学ロボットファクトリー活動日誌: 4月 2014

こんにちはKです。遺伝的プログラミングの基礎勉強として実装を目指すべく、展望をまとめてみました。次回制作します。

Santa Fe Trail(人工蟻の探索)問題を遺伝的プログラミングによって解いてみます。この問題は、32×32マスのなかに89個の餌があり、アリがその餌をたどって生きながらえながらすべての餌を集める経路を求めるものです。

さて、この問題の定義を確認します。人口蟻は上下左右の4方向だけ向きを変えられます。動作は、左右90度向きを変えるか、1マスだけ前進できます。また、範囲外にはいけません。人口アリにはセンサーがあり、前方1マスにエアがあるかどうか判断できます。そして、蟻には初期エネルギーがあり、向きを変える、あるいは前進するごとに1減少します。エネルギーが0になるまでにできるだけ多くの餌を見つけられるようにします。

遺伝的プログラミングでは
1. ランダムに遺伝子を生成する
2. 行動を起こし、遺伝子の適合度(誤差)を求める
3. 優秀な遺伝子だけを残したり、遺伝子中のある部分を入れ替えたり(逆位)、他の遺伝子と入れ替えたり(交叉)、突然一部分を適当に置き換えたりする(突然変異)
4. 世代数の上限に達したり、適合度が0となるような遺伝子を解とする。なければ2から繰り返す。
という操作によって解を得ます。解とは関数やアルゴリズムなどであり、遺伝的プログラミングを使って人間では把握できない解を得ます。面白いのは、解が木であるため、言い換えるとプログラムがプログラムを作ることもできるのです。つまり、遺伝的プログラミングによって抽象構文木を出力すれば、これはプログラムを出力していることになります。最も簡単な例は四則演算を出力する例ですが、これにかぎらずfor文やif文だって出力できるのです。ツリーの中身を解釈するのは人間が作るプログラムです。

遺伝子の変更について考えましょう。優秀な遺伝子を残し、優秀でない遺伝子には何らかの変更を加えて残すことを考えます。その比率はパラメータとして与えます。例えば、50個の遺伝子から優秀なものを20個、残り30個は逆位・交叉・突然変異によって変化させ、再び50個から選びます。

餌のパターンもその都度変えるのか、何回かおきに変えるのかなど決めます。その他、どれとどれを交叉させるかとか、割合はどうかとかいろいろパラメータ化します。

適合度を求めるのは問題によっては容易ではありません。ただし、その問題がどうしたら最低限解決とするかパラメータ化するのは比較的簡単です。例えば今回の例では残りの餌の数でいいでしょう。これが小さいほど優秀となります。

続いて実装について考えます。行動とは{ 左回転, 右回転, 前進 }の3通りしかありません。条件判断は{ 前が壁だったら, 前が壁だったら, 前が餌だったら }と考えてみましょう。応用的では、体力がm以上n以下ならなどいろいろ考えられますが、今回は割愛します。このような条件と行動をツリー構造に落とし入れます。このツリー自体がif文となります。

次のようなツリーを考えましょう。A => { x, y }のいみは、Aならばxをする。そうでなければyをするという意味と定義します。実際、ツリーは2分木である必要はありません。今回は条件と行動のみを考え、複雑な行動は考えないものとします。

A => { x, B => { y, z } }

これはAならばxをする。そうでなく、Bならばyをする。そうでなければzをするという意味のツリーです。

このツリー構造はこのままif文となります。そしてA, Bなどは条件に相当します。演算の場合はAやBが+とか-とかの記号になります。このへんはコンパイラと同じ構文解析でもよくある表現、すなわち抽象構文木となります。頑張ればfor文や関数も実現できます。

さて、このツリーとは別に

A => { C => { w, D => { u, v } }, v }

のようなツリーがあるとします。この2つを交叉するとは、適当な部分をそれぞれランダムに選択し、それぞれを入れ替えることです。例えばA=>Bと、A=>C=>wを入れ替えたとします。

A => { x, w }
A => { C => { B => { y, z }, D => { u, v } }, v }

こうなって新たなツリーが生まれました。逆位とは、条件の結果を入れ替えることです。適当な条件を選んで、{}の中を入れ替えます。例えばA=>Cを選んだとしたら、

A => { C => { D => { u, v }, w }, v }

となります。最後に突然変異とは、ツリー中の適当な要素を適当な要素に置換することを言います。

最終的に得られた解 = ツリーを使って実際に様々なテストケースにどれだけ対応できるか確認します。こんかいの例では、様々な餌の配置(例えば1万通り)を試し、どれだけ生き残って探索できるか試します。必要であれば残りの大量も加味した条件をつけるなりして更に強化していきます。

それでは実装をしてみます。その前に基礎的な実装に関する実験を行っておきます。想定する流れは次のとおりです。

1. ツリー構造を操作するモジュールを作る。
2. ツリーの内容に従って判断するありシミュレーターを作る。
3. 2.を用いて評価する関数を作る
4. 1.3.によって評価結果から選択、交叉、逆位、突然変異によって個体を生成する関数を作る。

モジュールに必要な機能は次のとおりです。

1. ツリーのルートとなるノードを設定/取得する
2. ツリーの要素数を取得する
3. ツリーの中のノードを一意に特定する
4. ノードの中のleft, rightを取得/設定する
5. ノードの値を取得/設定する

(実はノードの中のleft, rightは別に2つに限らず、N個にしても構いません。今回は今のところ必要が無いため放置します。実際3この配列にすれば3個固定となりますし、適当なコンテナを用意すれば可変長でN個持てます。)

一番難しいのはツリーの中の要素を一意に特定することでしょう。なぜ必要かというと、ランダムに選択するためです。そして交叉や逆位、突然変異をノードのポインタを入れ替えて実装します。

今回は、ツリー構造、特に2分木です。そして条件は左右にノードを持ちます。行動はノードを持ちません。そこで、すべてのノードはleftかrightを持ち、ノードの種類を表すNODE_TYPEを持ちます。NODE_TYPEは現状の仮定では条件と行動のみです。そしてNODE_TYPEに応じてNODE_VALUEを設けましょう。データ量の関係からポインタにしておきます。

条件である場合、その条件を表すクラスへのポインタを持つこととします。今回はConditionクラスへのポインタを持つとします。条件を実行する場合はインスタンスに対してexecute()を実行することで実現します。Conditionクラスは引数を与えず初期化します。現在の体力と向き、前にあるものだけがわかっているので、これらをexecuteに渡します。TestCaseクラスを渡すことにしましょう。

行動クラス、すなわちActionクラスはexecute()を実行することで行動します。これにもTestCaseクラスを渡してその状態が変化することで行動したとみなします。

これらから、ツリーの内容に従って判断するのは容易です。蟻の1ターンは次のとおりです。(1) ツリーのルートのCnditionクラスのインスタンスを読み出します (2) NODE_TYPEが条件なら、execute(test_case)を実行します。この結果、trueならleftノードへ、falseならrightノードへ移り、NODE_TYPEが行動になるまで再帰的に繰り返します。NODE_TYPEが行動ならexecute(test_case)を実行します。1ターンが終了したら次のターンへ移り、体力がなくなるまで繰り返します。

最終的に残った餌の数で評価し、優秀な遺伝子を選択、すべての遺伝子から交叉、逆位、突然変異をパラメータに従って実行し、再び得られたツリーの内容に従って判断します。

技術的に一番難しいのがツリーの要素を(高速に)一意に特定することですが、とりあえずleftを優先して、深さ優先の全探索によりインデックスを付けることにしましょう。n番目のノードを選択するのにO(n)時間がかかります。すなわち、右端のノードを選択するのに要素数に比例して時間がかかるということです。

木を保ったまま、より効率のよい実装にしたり、よりよい乱択方法を探したりすることで高速化されることでしょう。

ところでConditionクラスに引数を与えて初期化するとはどういうことでしょう? あるいは、Actionクラスに引数を与えて初期化するとはどういうことでしょう? これは、事前の状況を記憶することを遺伝することになります。例えば何らかのフラグfがあったとします。このフラグがどのような意味を持つにせよ、new Condition(f), new Action(f)などで生成し、executeすることでそれらのフラグが変化したとすると、フラグの伝搬ができることとなります。さらに、フラグ操作だけするNODE_TYPEを作ることにより、行動だけでない状況判断や思考を実現できます。

とりあえず次回はツリー構造を表すモジュールの実装とシミュレータ、遺伝的プログラミングの実装をしてみたいと思います。

2014/04/09

遺伝的プログラミングの実装の準備

2014/04/06

ガレキ除去機の部品製作①

新入生の方へ