遺伝的プログラミングの続き
2週間前に書いてた遺伝的プログラミングの続き。前は、構文木を構成するクラスとしてParamLeaf, ConstLeaf, EvalNodeを定義した。
書いたコード
前のコードにもdisplayメソッドとか付け加えた。後、rubyのオブジェクトはデフォルトではdeepcopyが出来ないので、childrenを持つEvalNodeにはinitialize_copyメソッドを持たせてdeepcopy時にchildのcopyを持たせる処理を書いた。
とりあえず、これがTreeのNode。
1 module GeneticProgramming 2 class Node 3 def display(indent = 0) 4 print "\s" * indent 5 end 6 end 7 8 class ParamLeaf < Node 9 def initialize(index) 10 @index = index 11 end 12 13 def eval(*params) 14 params[@index] 15 end 16 17 def display(indent = 0) 18 super(indent) 19 print "param#{@index}\n" 20 end 21 end 22 23 class ConstLeaf < Node 24 def initialize(const) 25 @const = const 26 end 27 28 def eval(*params) 29 @const 30 end 31 32 def display(indent = 0) 33 super(indent) 34 print "#{@const}\n" 35 end 36 end 37 38 class EvalNode < Node 39 def initialize(func_wrapper, *children) 40 @func_wrapper = func_wrapper 41 @children = children 42 end 43 44 def initialize_copy(obj) 45 @children = obj.children.map { |child| child.dup } 46 end 47 48 attr_accessor :children 49 50 def eval(*params) 51 results = @children.map { |e| e.eval(*params) } 52 @func_wrapper.call(*results) 53 end 54 55 def display(indent = 0) 56 super(indent) 57 print "#{name}\n" 58 @children.each { |child| child.display(indent + 1) } 59 end 60 61 def name 62 @func_wrapper.class.method_defined?(:name) ? @func_wrapper.name : 'no name' 63 end 64 end 65 end
EvalNodeにはprocオブジェクトを渡せるけど、display時に名前とか表示する為にFuncWrapperクラスを作った。後、FuncWrapperオブジェクトとして実際に使用するものを事前にまとめてFuncList moduleにした。
1 module GeneticProgramming 2 module FuncList 3 class FuncWrapper 4 def initialize(func_proc, name, arity = nil) 5 @proc = func_proc 6 @name = name 7 @arity = arity || func_proc.arity 8 end 9 10 attr_reader :name, :arity 11 12 def call(*args) 13 @proc.call(*args) 14 end 15 end 16 17 All = { 18 add: FuncWrapper.new(:+.to_proc, 'add', 2), 19 sub: FuncWrapper.new(:-.to_proc, 'sub', 2), 20 mul: FuncWrapper.new(:*.to_proc, 'mul', 2), 21 if: FuncWrapper.new(lambda { |pred, cons, alter| (pred > 0) ? cons : alter }, 'if', 3), 22 greater: FuncWrapper.new(lambda { |left, right| (left > right) ? 1 : 0 }, '>', 2) 23 } 24 25 def self.[](method_name) 26 All[method_name] 27 end 28 end 29 end
arityメソッドは引数の数を返すメソッドで、+とか*みたいな任意の数をとれるやつは任意の数をとれる形にしようかとも思ったけど、面倒だったのでとりあえず二引数扱いにしてる。FuncList::Allにこちらで事前に生成したFuncWrapperオブジェクトが入れてある。
それから、遺伝的プログラミングで問題を解くSolverクラスを作った。
1 require_relative './func_list' 2 require_relative './node' 3 4 module GeneticProgramming 5 class Solver 6 def initialize(score_obj, max_gen = 500, mutate_rate = 0.1, crossover_rate = 0.1, p_exp = 0.7, p_new = 0.5) 7 @score_obj = score_obj 8 @max_gen = max_gen 9 @mutate_rate = mutate_rate 10 @crossover_rate = crossover_rate 11 @p_exp = p_exp 12 @p_new = p_new 13 end 14 15 def select_index 16 Math.log(Math.log(rand) / Math.log(@p_exp)).to_i 17 end 18 19 def evolve(param_size, pop_size) 20 population = Array.new(pop_size) { |i| make_random_tree(param_size) } 21 scores = [] 22 @max_gen.times do |count| 23 scores = rank_func(population) 24 p scores[0][0] 25 break if scores[0][0] == 0 26 27 population[0] = scores[0][1] 28 population[1] = scores[1][1] 29 (2..pop_size).each do |i| 30 if rand > @p_new 31 tree1 = scores[select_index][1] 32 tree2 = scores[select_index][1] 33 population[i] = mutate(crossover(tree1, tree2, @crossover_rate), param_size, @mutate_rate) 34 else 35 population[i] = make_random_tree(param_size) 36 end 37 end 38 end 39 scores[0][1].display 40 scores[0][1] 41 end 42 43 def rank_func(population) 44 population.map { |tree| [@score_obj.get_score(tree), tree] }.sort_by { |score, tree| score } 45 end 46 47 def make_random_tree(param_size, max_depth = 4, f_prob = 0.5, p_prob = 0.6) 48 if rand < f_prob && max_depth > 0 49 func = FuncList::All.values.sample 50 childs = Array.new(func.arity) { |i| make_random_tree(param_size, max_depth - 1, f_prob, p_prob) } 51 EvalNode.new(func, *childs) 52 elsif rand < p_prob 53 ParamLeaf.new(rand(param_size)) 54 else 55 ConstLeaf.new(rand(10)) 56 end 57 end 58 59 def mutate(tree, param_size, change_prob = 0.1) 60 if rand < change_prob 61 make_random_tree(param_size) 62 else 63 result = tree.dup 64 if tree.class.method_defined?(:children) 65 result.children = tree.children.map { |child| mutate(child, param_size, change_prob) } 66 end 67 result 68 end 69 end 70 71 def crossover(tree1, tree2, swap_prob = 0.7, top = true) 72 if rand < swap_prob && !top 73 tree2.dup 74 else 75 result = tree1.dup 76 if tree1.class.method_defined?(:children) && tree2.class.method_defined?(:children) 77 result.children = tree1.children.map { |child| crossover(child, tree2.children.sample, swap_prob, false) } 78 end 79 result 80 end 81 end 82 end 83 end
これは、
solver = GenericProgramming::Solver.new(score_obj) solver.evolve(2, 500)
みたいな感じで使う。treeを引数としてとるget_obj(tree)メソッドを持つscore_objを渡してinitializeすると、そのscoreを遺伝的プログラミングで改善していって、最終的にscrore:0を返す様なtreeを表示してくれる。
score_objとしては、今回はこちらで用意した関数に対してrandomeに引数与えてデータセットを作って、そのデータセットとのズレの総和をscoreとして返す様なものを作った。
1 require_relative './solve' 2 3 class TestSet 4 def initialize(hidden_proc) 5 @hidden_proc = hidden_proc 6 @test_set = build_test_set 7 end 8 9 def build_test_set 10 [*0..200].map do |i| 11 x = rand(40) 12 y = rand(40) 13 [x, y, @hidden_proc.call(x, y)] 14 end 15 end 16 17 def get_score(tree) 18 @test_set.map { |x, y, test_value| 19 (tree.eval(x, y) - test_value).abs 20 }.reduce(:+) 21 end 22 end 23 24 if __FILE__ == $0 25 test_set = TestSet.new(lambda { |x, y| x ** 2 + 3 * y }) 26 GeneticProgramming::Solver.new(test_set).evolve(2, 500) 27 end
26行目にあるように、こちらで与えた関数でtest_setオブジェクトを作ってる。get_scoreメソッドにtreeを渡してやると、そのtreeがどれだけ良いものになってるかがscoreとして返る。
実際の実行結果はこんな感じになった。最初の数字の並びはscoreの変化で、その後にtree.displayの結果を表示してる。
$ ruby test_set.rb 11018 5594 0 add mul sub if param0 param0 > param0 0 0 param0 add mul param1 if > param1 param1 > param0 param0 2 param1
複雑に見えるけど> param1 param1(必ず0が返る)みたいなバカみたいな事をやってるだけで、ちゃんとx ** 2 + 3 * yにはなってる。こういった自明な部分を 枝刈り してやると、もっと綺麗な解になるらしい。
所感
大体は集合知プログラミングにのってたコードをrubyに置き換えただけだったけど、ちゃんと動いて問題を解くのに使えて楽しかった。
ちょこちょこ心残りはあって、solverは書いてて途中で力つきちゃってevolveが雑な実装になってしまった(ほぼ写経になってしまった)から、後でもうちょいリファクタリングしときたい。「遺伝的プログラミング」に載ってた定義だと引数が多すぎてイラッとしたからinitializeとevolveに分けたけど、特にinitializeの必要は無かったかもしれない。
後、mutate(突然変異)やcrossover(交叉)はTreeのクラスにメソッドとして持たしても良かったかもしれないし、make_random_treeはSolverクラスに入れたけどGeneticProgrammingモジュールの直下にあっても良い気がした。
眠くて辛いので今日はここまで。
追記
所感で書いた点を書き直してgithubにあげた。
south37/genetic_programming · GitHub
param_sizeメソッドとscoreメソッドが定義されたオブジェクトを渡してGeneticProgramming::Solverをinitializeすると、そのscoreを最小化するようなプログラム(構文木)の発見を目指して遺伝的アルゴリズムで探索してくれる。
require './solve.rb' GeneticProgramming::Solver.new(score_obj).evolve(500) # 遺伝的アルゴリズム開始
何らかの学習用のデータセットがあるとして、それをラップする形でscore_objオブジェクトを定義してやれば一応は動くはず。引数の数は任意だけど、score_objはparam_sizeメソッドで引数の数を返さなければならない。
ちゃんと正しい結果を返してくれるのかのテスト用に、こちらで正解の関数を与える事でデータセットを、さらにはそれを元にscore_objを作ってくれるTestSetクラスも用意されてる。
