[QUIZ] Genetic Programming (#212)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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