遺伝的プログラミングを学ぶ
積読されてた「集合知プログラミング」を引っ張りだして読んだ。面白そうなとこから読んでたからまだちょこちょこ抜けはあるけど、機械学習のいろんな手法を分かり易く説明してくれてて楽しく読めた。 その中でも、遺伝的プログラミングの考え方が特に面白く感じた。
遺伝的プログラミングとは?
機械学習によって「プログラム」を構築する手法。ランダムに作られたプログラムの中から、良いものを選んで「突然変異」させたり「交配」させたりしながら進化させていく。
最適化手法の一つである「遺伝アルゴリズム」を「プログラム」自体に適用したものとも言えて、「プログラム」を生成するプログラムを考えようっていうメタな感じが面白い。
実際どうやんの?
ランダムに「プログラム」を作ろうって時、原理的には適当に作った文字列をevalするとかでも良いんだろうけど、そういった方法ではちゃんと動くコードになる確率は限りなく小さい。そこで、通常は「構文木」に着目する。
「構文木」というのは再帰的に評価可能なツリー構造の事で、例えば通常のプログラミング言語においてはコンパイルの際にコードはいったん構文解析によって「構文木」(より正確には抽象構文木)に変換され、その後で実行可能なバイナリの生成が行われる。
このページの図11みたいなイメージを持ってもらえればOK。
この構文木を「遺伝アルゴリズム」で進化させていこうというのが、遺伝的プログラミング。
構文木を作ってみる
より正しくは構文木と一対一で対応する様なツリー構造を、オブジェクトとして表現してみる。
まず、ツリーを構成するノード(および末端のリーフ)として、パラメータに対応するParamLeaf、定数に対応するConstLeaf、そして子ノードに対して適用されて値を返すEvalNodeの3種類を考える。特に、EvalNodeは関数の場合もあればifのような制御構造の場合もある事に注意する。
例えば、rubyでは次の様にParamLeafクラス, ConstLeafクラス, EvalNodeクラスを定義出来る。
1 class ParamLeaf 2 def initialize(index) 3 @index = index 4 end 5 6 def eval(*params) 7 params[@index] 8 end 9 end 10 11 class ConstLeaf 12 def initialize(const) 13 @const = const 14 end 15 16 def eval(*params) 17 @const 18 end 19 end 20 21 class EvalNode 22 def initialize(eval_ploc, *children) 23 @eval_ploc = eval_ploc 24 @children = children 25 end 26 27 def eval(*params) 28 results = @children.map { |e| e.eval(*params) } 29 @eval_ploc.call(*results) 30 end 31 end
これで、例えば次の様にツリー構造を作って、それをevalする事が出来るようになった。
[1] pry(main)> tree = EvalNode.new(lambda { |a, b| a + b }, ConstLeaf.new(1), ConstLeaf.new(2)) => #<EvalNode:0x007fe7f04a4360 @children=[#<ConstLeaf:0x007fe7f04a43b0 @const=1>, #<ConstLeaf:0x007fe7f04a4388 @const=2>], @eval_ploc=#<Proc:0x007fe7f04a43d8@(pry):17 (lambda)>> [2] pry(main)> tree.eval => 3
上記の例では、「1 + 2」というコードに対応する構文木を作った事になる。一部をパーツとして取り替え可能な「データ構造」の形でプログラムを表現した事で、遺伝的アルゴリズムが適用出来る様になった。
ちなみにどうでも良い話だけど、単純な演算ならlambda式では無くsymbolのto_procメソッド使うとちょっとオシャレになる。
tree = EvalNode.new(:+.to_proc, ConstLeaf.new(1), ConstLeaf.new(2))
時間が無くなった
めちゃくちゃ中途半端だけど時間が無くなったので、今日はここまで。続きとしては、構文木を「交配」させたり「突然変異」させたりする方法を定義して、実際に「遺伝的プログラミング」を試してみる予定。
