[QUIZ][SUMMARY] Genetic Programming (#212)

Sander Land's solution used Charlie[1] a library for genetic
algorithms and genetic programming. Let's take a look at Sander's
solution:

    %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) do |f,(x,y,z)|
          f + ( z - eval_genes(:x=>x,:y=>y)).abs
        end - size * SIZE_PENALTY
      end
    end

Here Sander creates a class named `Quiz212`. `Quiz212` extends
TreeGenotype, provided by the Charlie gem. TreeGenotype takes three
arguments: `terminals, unary_ops, binary_ops`. These are used to
construct the tree representing the program. The class also defines a
fitness function which is used to evaluate the programs generated by
TreeGenotype. The data, as well as a size penalty are stored as
constants within the class.

The Charlie gem also provides a `Population` class. The population's
initializer takes a genotype class as a parameter and uses that to
evolve the population. The population also provides an
`evolve_on_console` method that displays the current best program each
generation.

    Population.new(Quiz212).evolve_on_console(200)

Charlie looks like a great way to get started trying out genetic
programming. The TreeGenotype is just one of many possible options
available in the library. Please do check it out.

Brabuhr provided a solution using Directed Ruby Programming[2]. DRP
uses Grammatical Evolution[3] as a foundation for Genetic Programming.
DRP let's you define a grammar to constrain the kinds of programs that
are generated. Here's an example of defining an expression using
`DRP::RuleEngine`:

    def expression; "#{expression} #{binaryop} #{expression}"; end

We can also define a binary operator in a similar way:

    def binaryop; "/"; end

These rules, along with any others that we define, are used by the
rule engine as a grammar to generate candidate programs. brabuhr
collects these generated programs and applies a fitness function to
see how well their output matches the data. These programs are then
sorted and mutated/crossed to create the next generation of programs.
Be sure to take a look at brabuhr's full solution for more details.

This week we saw two interesting options for working with genetic
programming, Charlie, and DRP. Both of these libraries make working
with genetic programming much easier by providing an interface to the
common tools and techniques used.

And now what you've all been waiting for... the mystery function:

    def mystery(x, y)
      3 * x * y + 5 * (y**3) - 7 * x
    end


Thank you Sander and brabuhr for your solutions to this week's quiz!

[1]: http://charlie.rubyforge.org/
[2]: http://drp.rubyforge.org/
[3]: http://en.wikipedia.org/wiki/Grammatical_evolution