遺伝的プログラミングの続き

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クラスも用意されてる。

ちなみに、rubyだとクッソ遅くてやっぱ機械学習には向かない言語なのかかもと思った。