ToDo3
いろいろ考えた結果、まずは遺伝的プログラムを何らかの形で
動かすことが重要だと言う結論に至る。高速化するのはその後にする。
「やりたいこと」
- 遺伝的プログラミング(GP)の例を実行させる。
「そのために必要なこと」
- schemeで遺伝的プログラムが可能か調査する。
http://www.geneticprogramming.com/Tutorial/ >できそう
中止 「遺伝的プログラミング (情報科学セミナー)」のCLISPで書かれた実行例をschemeに変換して実行する。 >CLISPのコードが理解できる量ではない。
着手 自分で例を考える
ブール関数の合成:2以上の入力からなる真理値表の結果を出力可能なブール関数を求める。
>ありきたりなのでやめ
発展 任意のリストから解となるリストを出力可能なS式を求める。
>単純だが対話プログラムに発展できる可能性がある。
- GC不要なLispが遺伝的プログラミングを高速に実行するために有用か調査する。
中断 Automatic Memory Management in newLISPを翻訳してのGC不要なメモリ管理が使えるか判断する。
- 仕様書を書く。
中断 外部使用を書く
とりあえずは、GPに必要な関数のみに限定する。
データ構造とアルゴリズムを考える。
Abstract的?
進化的手法の代表例でるGPは現在盛んに研究されいます。
GPを自然言語処理に応用するための基礎技術として
「任意のリスト(アルファベット小文字1文字のみのリスト)から、
解となるリスト(アルファベット小文字1文字のみのリスト)を
出力するプログラム」
を実現するプログラムをGPで実現させようとしています。
このとき、GPも、それで作成されるプログラムも使用する言語に
schemeを選択しました。
ある数列から、解となる別の数列を作るでもいいかもしれません。
単純だけど対話プログラムに発展できる可能性があるかも。
以下に例を示します。
- 解くべき問題の例としては、リスト'(a b c)をリスト'(d e f g)に変換するプログラムを求めます。
- 自然言語処理を例とするなら、「自然 は 大切だ」を「科学 は 人類 の 英知だ」に変換するためのプログラムを遺伝的プログラムで生成することになります。この文章「自然は大切だ」は要素別に並べると「自然」「は」「大切だ」となり、これはリストで表現できます。つまりLispでは'(自然 は 大切だ)になります。
Lispにおけるリストに関する参考資料
Lisp 一夜漬け -- 2.リスト
schemeではnilは存在しません。偽を表す#fと、空リスト()は存在します。
遺伝的アルゴリズム(GP)に関する参考資料
http://mikilab.doshisha.ac.jp/dia/research/report/2004/0802/002/report20040802002.html
http://www.asahi-net.or.jp/~qs7e-kmy/tawagoto/980123/gp.html
http://www.kochi-tech.ac.jp/library/ron/2000/info/1010383.pdf
1.初期集団の木構造の生成(Initialization)
ランダムに集団数の数だけ個体(木構造)を生成させる.2.適合度計算(Evalution)
各個体の適合度を計算する.3.選択(Selection)
適合度の大きな個体に対して一定数のペアを取り出す.4.交叉(Crossover)
親1と親2の交叉点をランダムに選び,それぞれ交叉点に応じた部分木同士で交叉させる.5.突然変異(Mutation)
ランダムに突然変異点を選び,その点に応じた部分木と突然変異木を入れ替える.6.逆位(Inversion)
兄弟木の入れ替え.7.終了判定(Terminal Criterion)
以下のような終了条件がある.
実行すべき最大世代にまで達したとき
目的とする個体が得られたとき
GPの基本要素
GPでは次の5つの基本要素を設計することで,様々な応用問題への適用が可能となる.
1.非終端記号 --- 関数ノード
2.終端記号 ----- 実値
3.適合度 ------- 評価値
4.パラメータ ---- 集団数,交叉率,突然変異率など
5.終了条件
- 発生する作業
非終端記号、終端記号の決定
適合度の計算式の策定
各アルゴリズムの作成
メインループの作成
非終端記号、終端記号の決定
- 終端記号(一般的には関数)
car, cdr, cons, quote, set!, cond, define, eq?, list?
- 終端記号(一般的には変数)
アルファベットの小文字一文字(a〜z)
適合度の計算
ハミング距離を使う。リスト長が一致しない場合は、長いほうに合わせる。
値が0に近いほど適合度が高いと判定する。
レーベンシュタイン距離
というものもある。
1.初期集団の木構造の生成(Initialization)
- ランダムに集団数の数だけ個体(木構造)を生成させる.
- さて、どう書くかな。
まず乱数を発生させる手順(mixiで教えていただきました)
gosh> (use srfi-1) #<undef> gosh> (use srfi-27) #<undef> gosh> (random-integer 100) 81 gosh> (exit) ---- gosh> (require-extension (srfi 1)) #t gosh> (require-extension (srfi 27)) #t gosh> (random-integer 100) 81 gosh> (exit)
上の書き方はgosh特有で、下の書き方はよりポータブルだそうだ。