From: Sander Land <sander.land@...>
Date: 2009-07-08T22:06:12+09:00
Subject: Re: [QUIZ] Genetic Programming (#212)

%w[rubygems charlie].each{|lib| require lib}
class Quiz212 < TreeGenotype([:x,:y,proc{rand(20)-10}],  [:-@], [:+,:*,:-])
  DATA = [[8, 16, 20808]  , [22, 31, 150847],  [5, 16, 20685], [12,
19, 34895], [18, 25, 79349],
          [20, 33, 181525], [31, 1, -119]  , [19, 33, 181433],  [0,
12, 8640], [13, 12, 9017]]
  SIZE_PENALTY = 100
  def fitness
    -DATA.inject(0){|f,(x,y,z)| f + ( z - eval_genes(:x=>x,:y=>y)
).abs } - size * SIZE_PENALTY
  end
end

Population.new(Quiz212).evolve_on_console(200)

The best result I got using size penalty 100 has fitness -2296 and tree:
[:*, [:term, :y], [:+, [:+, [:term, :y], [:term, :x]], [:*, [:*,
[:term, -5], [:term, :y]], [:-@, [:term, :y]]]]]
Which simplifies to 5y^3 + y^2 + xy.

Not including a penalty for size in the fitness function causes bloat.
However, including such a penalty causes it to never find the lower
order terms as the smaller size is considered more important than
slightly better accuracy. This is a well-known problem in GP.


On Fri, Jul 3, 2009 at 8:51 PM, Daniel Moore<yahivin@gmail.com> wrote:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have elapsed from the time this message was
> sent.
>
> 2.  Support Ruby Quiz by submitting ideas and responses
> as often as you can!
> Visit: http://rubyquiz.strd6.com/suggestions
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem
> helps everyone on Ruby Talk follow the discussion.  Please reply to
> the original quiz message, if you can.
>
> RSS Feed: http://rubyquiz.strd6.com/quizzes.rss
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> ## 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.
>
> The modifications made to the programs are based on techniques
> observed in biological evolution: mutation and crossover. In mutation
> a piece of one program is altered randomly, for example `x + 3` could
> become `x + (y - 1)`. The mutation occurs at one node in the parse
> tree and replaces it with a new randomly generated node.
>
> Crossover works in much the same way, except instead of randomly
> altering the node it is taken from another node of another program.
> For example: `x + (y * x)` and `3 - (y + x*x)` could yield something
> like `(y*x) - (y + x*x)`.
>
> In order to mutate our programs it would be nice to work with the
> structure of the code directly. The ParseTree[2] gem provides a way of
> getting an Abstract Syntax Tree[3] to manipulate. The AST represents
> the code as S-expressions[4], arrays containing operators as the first
> argument and the operands as the remaining arguments. If you are
> familiar with LISP then you know that LISP programmers program
> directly in S-expressions. Using S-expressions makes evolution and
> manipulation of the programs much easier, as S-expressions are the
> essence of programs.
>
> When manipulating your ASTs you may need a deep copy to prevent
> unwanted side effects Here is a deep copy idiom that may be useful:
>
>    def deep_copy(tree)
>      Marshal.load(Marshal.dump(tree)
>    end
>
> In order to get the AST back into executable ruby you'll need
> ruby2ruby[5] or something like it. As always, feel encouraged to use
> and share other tools if you feel they are good for the task. Also, if
> you have any questions don't be afraid to ask, there are many people
> on the mailing list who are happy to help!
>
> Here is the table of outputs for the mystery function that we would
> like to evolve an algorithm for:
>    ["x", "y", "result"]
>    [8, 16, 20808]
>    [22, 31, 150847]
>    [5, 16, 20685]
>    [12, 19, 34895]
>    [18, 25, 79349]
>    [20, 33, 181525]
>    [31, 1, -119]
>    [19, 33, 181433]
>    [0, 12, 8640]
>    [13, 12, 9017]
>
> In order to determine how well suited a program is we can use the
> following metric function:
>
>    # Return how far off from the data the given method is
>    # A lower score is better, a score of 0 matches the data perfectly
>    def fitness(program, data)
>      delta = 0
>      data.each do |row|
>        value = program.calculate(row[0], row[1])
>        delta += (value - row[2]).abs
>      end
>      return delta
>    end
>
> Have Fun!
>
> [1]: http://en.wikipedia.org/wiki/Genetic_programming
> [2]: http://rubyforge.org/projects/parsetree/
> [3]: http://en.wikipedia.org/wiki/Abstract_syntax_tree
> [4]: http://en.wikipedia.org/wiki/S-Expression
> [5]: http://seattlerb.rubyforge.org/ruby2ruby/
>
> --
> -Daniel
> http://rubyquiz.strd6.com
>
>