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.終了条件
- 発生する作業
非終端記号、終端記号の決定
適合度の計算式の策定
各アルゴリズムの作成
メインループの作成