« Return to Thread: [QUIZ] Genetic Programming (#212)
Re: [QUIZ] Genetic Programming (#212)
by Sander Land
::
Rate this Message:
%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@...> 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
>
>
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@...> 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
>
>
« Return to Thread: [QUIZ] Genetic Programming (#212)
| Free embeddable forum powered by Nabble | Forum Help |
