From: Daniel Moore <yahivin@...>
Date: 2009-07-15T12:49:41+09:00
Subject: [QUIZ][SUMMARY] Genetic Programming (#212)

--0015175cd620a72bf9046eb6713b
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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

--0015175cd620a72bf9046eb6713b
Content-Type: application/x-gzip; name="212.tar.gz"
Content-Disposition: attachment; filename="212.tar.gz"
Content-Transfer-Encoding: base64
X-Attachment-Id: f_fx5ifil70

H4sICPtQXUoAAzIxMi50YXIA7Vp7c9s2Es/f/BRoPB1LCU2T1MO2UvcuaTLpzeRucmlm7qHTyJAE
SawpkgVJy4rt736/BUCJouw66dXOdI47Y0sGFvvexQKw7/mHTx4YXMBRp0Of3lHHLX8W8MTzfP/I
77itNvA8t9vqPGGdhxaMIE8zLhl7MuFRIMK78e6b/4OCD/+n+WLB5crJLrMH4UEO7rbbd/m/c+R2
K/5veW7rCXMfRJoK/J/7/yceTYRk7/Cxn7I0DvMsiCOWp2LCfphzGQai7w0YZ2EwkggSNo0lm4lI
ZMGY8XAWyyCbL1KG9evhRMYzyReLIJo57J3IQDjj54KIxPE54xnTXEsMe5bFAN8u+zIfrWYCFMea
+8ARfDy/ugb/aybFL3kgBQlzoxaMQ56m7O958AmBzL5jH6UQb0UUZ6tENPq9S7u3siHO+EqCY8N3
mweeezOwGev3Dv6Mz37vud17ZvcOBk1Fj7HXLz++ZKes3z+2mde1me8eu8eE6fs2a3kY7LjH7SNF
o1OgdI87hOIBxTsBWvv4RA+AiA+so5NW+2RgGxYG+r4L1BaWHHsdX+Er+jY78LwTtfxkjdButRRL
LCEux922qzBa+u8TZNRgYOj/9Jd/vxm+f/O3l+8+/guqeK5rJszHREzZNMgikaZriQ5IbyeIfhbj
rOE22SRm11O7cWmv7E/Na1aSfMqeswb7xA6YuODhkJyeNnqXp9+TsU+/XzWbDh9tCAsExgFLg0+C
PduSzFrPW8Wn9aOAc01IjqXgmUBkGSdHfIGYPDO+PnM2X5m4zLA83fK+TWF4EUywZrRi2VwU4Yww
XThbqCo6EaNzjDEuZ/lCRFnaY2eZkAhiHqY2yyME/zBO8HUUFN8hxMe5SGmR0CmTxWwcR2km83Gm
mGZEU4pEAi3KkBFq1GSIWm7UA5eYPBNESmfjHzbNo7HKyOU8GM9ZkK75kPVzWKhMMFU5KDGqtC4r
qXlNeMZtxlO2FGFIn1y7JhFQM1spRdIslliPSaUKhy3YElkeRIqVEtexrI/bJtUKGJsT3bP3cZKH
nIQ/M4uUCMl6GPkfREEW8BAiSOMFTipotxjD0FjCoZ2AP1ShgQnIXSgkyg5xeGGssCZdZVWVLmJn
et0wjoakZhyKMwYO83iiKU+CNAn5KtU651LCfWwk0qywNaO6VNibWOoSttHaicSyYWK06eywQzVy
m5ZVmJBKY4rCpurkjGKfLfmKFJyJjNEmRU7N5IpiKM6z26stab0V2giYn7HFsTgSLJ6yBY9WMEua
BqMQAwnJCXNc8CDkNGJ8bIq9w96HgiO+UQ3GczE+Z0FGvKHqK8lH+VxukoyXNw+S8TUK9Zhk/oCK
zt5vpOz7A4e9/vBeu/EtjcJeYx6yNxeGRL810H6fxnk00R6kjeet0fl9WWciFapdZhXnJoWUDYmw
3KQkN8qdB1QrYIx10iiHU+ivs8dhVIr2VaSIS75IQmU+RZyUU8OU1OlG4TMI0ut9yEPxJppBhjOz
qVG53SC/YE/3rjZ/3rC9K11Q4oS+l2aevtBF8R+IPx6VCwS002vgQZIXloFulMoL+FFS4PTYhnlB
H6wPC6K6bkkIi4rGwxjyU44zio8YVpLGKktheNqbImfqKS0GsZkSKN22eGFIknwSTOhbYW2HjUzs
jOMwRIioFEtLxt84hpKdJwny49aaCEYpyus8Xup6BjqBpABNkB8IKsSszl8qe0Wt3hCXqmpECFyV
W8RskWckweFYIkdMPVf7kCITYaMpZXw5hhz2CpUzJ5Jxtdsx+u6T5JBynScU0QvUWlg4QwLqohpQ
bRbnZPiUL1m2jOFbFD5UHpX5JmVp7TKW50HhuFvKgV3UZ1vphvCElHAuya1NrvOcrLsgke8jCPOg
5KEiBCjEiAKd/CYflJRTPtYWoKIZLxbKSXGoPZmJ8TwKfsmF3sSg7kuMRuQ9CjVk7z4KOYeJRgJu
WfJAqQxVHcdRJBerFExW6wgoZZiZQsfCVkUv10LLcYmfFVqWDj4bq2fPWk20I0c0sWk7YHYenavy
YZoPErcIUzI1puTacanW0HgKbkVT+ukby0Kj3GPzLEt6h4eme3WonQWBmXDw69BC7VujTGSyM93a
TIvIWQbnQSImAVez9NdhqVwORVEurd/e/9P5z+SVI0e/37miDPec/zzX9zbnP/cI5z+/63fq899j
ALX9OO0gFyoHHhqpHnmsnTMPjVROPWpo59yzc9ihsa3jjlpXOfBY1ROPQiqfeWxrYFm35f89ua/y
fo99EFkuI7WDTBEG8RQnIxkv1puG+jILLlCOTHMYpFj2ErV9iTKRjql8oxCMRAbuNu3BaggV1t3Z
gdBlyyk2vHBlbR/BJiLE7Cmjc5o6h6nWko5gMl5eqzpFzb4ASqEmJvp0AqRPzxxeNZnnp6yhsQ/U
rD8oDmT6qCW1ygpZmYFZ2C7TQpyvHZA1PCpQ/S/dAT3IXfDn3//6fqfbovp/5Hn1/e9jAPnfNDoP
9g7wBf7vtFtt8r+PMKj9/whQzf+ix/09m8F7+z+3Y/zfbrndLvzf8dAG1v3fI8AX3bh/9m17Hy0a
tX+Dvrp3bzUH+tJ958b9cW7bH+SmvXrLbqn79erd+ufdq3/Bnfqv3adTN6ca28+/hETyuc2vHYQ1
fDUo7/8PUfsJ7qn/bd87MvW/1fVa9P7bbh+5df1/DCjq+/5EJvuWqfDmev2tvumMpWVe2Fjlhtuy
cPDFl6G6R7bMTZy5MNSl7ekP6uUHVeiK7V0V93Y37OapVdy+FS+SZs6so6ExD8dUx4Q+1b/Yvh9X
N9k7ZP6Hm/bbKcAAi9+69m7uiuqvrG1sLW7eL2Fxsb975/98e3Fp5uDOmWd3zhxWGOU71IoZEkvJ
d8FlQK9LFX3X82GQIc7CqgrFMuBcbq8szawqiwwtRVf1Hp7brPDdQTlpYvv1bnYEoV8mtPWuWrwc
nLIfeTpXQX09xze7iHm6q6GBvvl7AFTTDTTMUNO6KdLsu+8KipYSrHgAGabxQgzpZaAR6fd7MJjh
WzUvSQJ19RM5WbAQ6RVLRTjtJzNnEyEDpv5TgiYsYyniJQV1JMNsLoZ5BBELHGciQgERgunVtZHY
JhWu2Tf4fVMmAfSCBL2LKlk7zTUhelUZjlZDoz/1U9Fga/02QmMSR9mQHBIvqLs5ZZnMxYbenRIb
OtvyEsVrViH5p/UTUo8pz5s/m0YvJdtWCfwrvQehAGqJ1avQcISud9JI0D0mvhIv8RA/314t8fsA
Tdnhje56280BRhK/rPMdFFIP6iZe33UctTTxHOrwmuo/OlKfJn1NNPH1jOMceAPLrAV3lFfDnW2x
T7fY6+etTSiS8OZfEWZpPmqY2rt3dTu9m6f2vRiE0CyZM1lsAtdYk8LWsqjz1GELN1kFSursZoFT
+u+TatCoGCkj0NlFdbcNf2dcdd/K7lOvaTMYE9/8prphhUzD4mX/FDsPvY6a+qGpLOmpsOU4J/rR
MFk4dzjToAL8NWph+CqGt4PhGQwRQoIN3Jb6pSw3a3SRI1WKQF/bPu2XNFRxtaeufeHKqXfD/km7
s3/zn2zvqrSc3Kmjp5pbJcJOtRB4TWeKXRsdA9YpHq8w3CMOhiyxMRQp5rsuBQ4x+trtUA011FBD
DTXUUEMNNdRQQw011FBDDTXUUEMNNdRQQw011FBDDTXUUEMNNdRQwx8G/gszFHZ3AFAAAA==
--0015175cd620a72bf9046eb6713b--