Re: [QUIZ] Genetic Programming (#212)

< ^ > P N |<>|^_>< --- | ~ ...Help
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> ## Genetic Programming (#212)
>
> Buon giorno Rubyists,
>
> Let's say that we have a table of outputs for an unknown function, and
> we want to find out what that function is. One possible method of
> finding a solution is to use genetic programming[1]. In genetic
> programming we begin with a random population of programs, then rank
> them according to how well they meet the solution criteria. The top
> ranked programs are then modified to create a new generation of
> programs. The new generation is ranked by how well the solve the
> problem in the same way and the process repeats until, hopefully,
> we'll have evolved a strong solution.

Some time ago, I ran across DRP, Directed Ruby Programming[1], and
thought that might be something to look at later; I thought this quiz
might be a bit of a chance.  (Though I only barely scratched the surface
of the library's documentation.)  First, here are some sample functions
my programs generated (fitness: function):

89416: 4312 + y * 7 * y * x
82779: ((x * 4 * (93 + y * 6 + x + 9 - x)) - 3) * y / 8 - 62 + 1 * x - 3
       - 80 + 1395 + 0 / 870 + y * 6 + y - y - ((y)) - x - y + y - 16
       - 657 + 880 - 7 * (6 / 6) * (y / 1) - 870 + 19 + y * y * (y) - y
       - (62935) / (((x - x) - y / 1 * y / y) - x) - ((y + 4 - y + y * y
       + x)) + 6 - x * 6 * (((8 + 6 / 2563 * (y) + x / 9871671)) - y - 7
       - x - x - 8) - 3361 + 9 - (43) / 675670 - y - x - 45 + 8 + (y / 1)
       - 870 + 19 + y * y * (y) - y + y * x * (6 / 6) + 870 + 19 + y + x
       * x - ((((10)))) - 8 + y - (x)
17387: x + (y) * 5 * y * y - ((x + y)) / 65 / y / y + y + 2 / (y * x +
       95381 - x + x) - y * 0 / 50 * x * ((x)) * 7 - x * 4 + 4 * 9 * 6 *
       y - 0 * (((y + x + x))) * (x + y) * (y + 78 * ((x / y * (y + 22 -
       9) - ((x + y) - 684) - x - y - x + ((7 + y * ((785 / 4 - x * 8)) +
       (8 - 4) + 8 / 7 + x + x))) / 4) - (8 - 9 * x - 0) * x + 2) * 91 *
       76 * x + 220 + x * 4 - 2 * ((x)) * (y) * 4 - y * ((x / (y * 34 + y
       + 4 - x * 8)) + 24) + y * 1 - (y) * (((y + x + x)))
8570:  5 * y * + + y * y - 29
8424:  y * + 5 * + y * y + - x
8360:  5 * y * y * y / y * y - x / - - - y
8346:  5 * y * y * y - - - 1 + x - x
8338:  y * ((5 * y)) * ((y))
8102:  (8) - y + 60 + y * y * 5 * y
8056:  47 + 5 * y * y * y
7288:  988 + 5 * y * y * y - y * y / y + 0 * 894 / 2 - x * x / - + 1 - - 7
3948:  y * 5 * (y + (y) * y - x)

Following the first example in drp's INTRO file, I created a simple class
to generate random initial functions:

require 'drp'

class ProgramGenerator
  extend DRP::RuleEngine

  begin_rules
    def program
      "Class.new{ #{function} }"
    end

    def function
      "def calculate(x, y); #{expression}; end"
    end

    def expression; "#{expression} #{binaryop} #{expression}"; end
    def expression; "#{atom} #{binaryop} #{expression}"; end
    def expression; "#{expression} #{binaryop} #{atom}"; end
    def expression; "(#{expression})"; end
    def expression; "#{atom}"; end

    def binaryop; "+"; end
    def binaryop; "-"; end
    def binaryop; "*"; end
    def binaryop; "/"; end

    def unaryop; "-"; end

    def atom; "#{variable}"; end
    def atom; "#{literal}"; end

    def variable; "x"; end
    def variable; "y"; end

    def literal; "#{rand(10)}"; end
    def literal; "#{rand(9) + 1}#{literal}"; end
  end_rules
end

irb(main):001:0> require 'program_generator'
=> true
irb(main):002:0> pg = ProgramGenerator.new
...
irb(main):003:0> pg.expression
=> "x"
irb(main):004:0> pg.expression
=> "(y * 4 + 924)"
irb(main):006:0> pg.function
=> "def calculate(x, y); 26 / x + (60 - x) + y; end"
irb(main):007:0> pg.program
=> "Class.new{ def calculate(x, y); 136 * x + 14; end }"

I setup a "magic" hash to store my population of programs and a few
helpful methods:

Programs = Hash.new{|hash, program|
  hash[program] = fitness(program)
}

class <<Programs
  def generate_some_more(n = 100, pg = ProgramGenerator.new)
    n.times{ self[pg.expression] }
    self
  end

  def reject_the_unfit
    self.delete_if{|program, fit| !fit}
  end

  def select_the_best(n = 5)
    self.sort_by_fitness[0, n]
  end

  def sort_by_fitness(dont_randomize = true)
    self.reject_the_unfit
    self.sort_by{|program, fitness| dont_randomize ? fitness : rand(fitness)}
  end
end

irb(main):001:0> Programs
=> {}
irb(main):002:0> Programs.generate_some_more(2)
=> {"y"=>687122, "(x - 4 * x / 31 + (0 * 964 / 65 / y - 8 + 4 + (y * ((y / x *
 54 - (x / ((986 - y + x - 24 + ((6 / 197 / 29 - 287)) / 9 + y * 2 / 2 * 7)) *
 23 - 7) + x - 44 * 659 + (y * 1 - 8 / y / ((5 * x)) - 5) * 7632 / ((y)) / x /
 8856))) / x + x) - ((x))) - 7 - 0 - x"=>nil}
irb(main):003:0> Programs.select_the_best(1)
=> [["y", 687122]]

And wrapped that in a loop to generate/mutate a bunch of functions:

pm = ProgramMutator.new

1000.times do
  Programs.generate_some_more.
           sort_by_fitness(true).
           each_cons(2).
           each do |(p1, f1), (p2, f2)|
    new_program = case rand(10)
      when 3..9 then pm.cross_breed(p1, p2)
      when    2 then pm.mutate(p2)
      when    1 then pm.mutate(p1)
      else           ProgramGenerator.new.expression
      end
    new_fitness = Programs[new_program]
    #puts "#{f1} X #{f2}\t#{new_fitness}"
  end

  program, fitness = Programs.select_the_best(1).flatten
  puts "Best: #{fitness}\t#{program[0..60]}"
end

> ruby1.9 -rubygems 212.rb
Best: 569018	28298
Best: 494580	3170 * x - y
Best: 494580	3170 * x - y
Best: 494580	3170 * x - y
Best: 357554	(4257 * y - 1)
Best: 357554	(4257 * y - 1)
Best: 357554	(4257 * y - 1)
Best: 357554	(4257 * y - 1)
Best: 212330	(y) * - 142 / - 25 * y * x
Best: 212330	(y) * - 142 / - 25 * y * x
Best: 187980	0 / y - - 8 * 25 * y * x
Best: 173870	248 * y * (x)
Best: 104800	26 - 2 + x * 7 * y * (y)
Best: 104800	26 - 2 + x * 7 * y * (y)
Best: 104800	26 - 2 + x * 7 * y * (y)
Best: 92312	8526 - x + y * + 8 * y * x
^C

That leaves the ProgramMutator class:

class ProgramMutator
  def cross_breed(p1, p2)
    #...
  end

  def mutate(program)
    #...
  end
end

The machine I'm using today doesn't have ParseTree ("ParseTree doesn't work
with ruby 1.9.0 (LoadError)").  So, I was just doing string manipulations.
I don't know which functions produced which of the results from above, but
a few samples:

  def cross_breed(p1, p2)
    p1 + %{w + - * /}[rand(4)] + p2
  end

  def cross_breed(p1, p2)
    s1 = p1[0..rand(p1.size)]
    s2 = p2[rand(p2.size)..-1]

    s1 + %w{ + - * / }[rand(4)] + s2
  end

  def mutate(program)
    program.gsub(
      "#{%w{ + - * / }[rand(4)]}",
      "#{%w{ + - * / }[rand(4)]}"
    )
  end

[1] http://drp.rubyforge.org/