January 14, 2010 at 9:21 am
Bill Talada (1/14/2010)
If you run the included "DecipherDNA" script and do a "select *" at the bottom of it, you will see all 243 possible views numbered. These are the 243 rules hidden in the math formula as a sort of virtual table. The robot's dna strand is 243 characters long and matches up to these 243 views.
Ooops I got ya. It's just showing what it does if it is sitting on a can right now. Thanks. This is really cool.
January 14, 2010 at 10:46 am
.
January 14, 2010 at 10:57 am
jeremiah.thomas (1/14/2010)
I think i am with Valued member. how do we read the grid that decipherDNA creates?here is a short example of the grid:
n s e w c a
0 0 0 0 1 4
0 0 0 1 1 4
0 0 0 2 1 4
0 0 1 0 1 4
0 0 1 1 1 1
0 0 1 2 1 3
0 0 2 0 1 4
0 0 2 1 1 1
0 1 0 0 1 3
Ok, I have it figured out now. That first line is not what the robot did first. It's what it would do if it encountered that situation, (no can north,south,east,west but it's current location had a can. It would pick it up as indicated by the last digit "4". What you need to do is take it's starting location of 0,0 and determine what the robot would see at that location. It sees 2 1 1 2 1 (that's wall north and west, can south, east and current location.) Now find that in the results of the DecipherDNA script. Oh, first remove the WHERE CLAUSE on the last line. select * from @rules is what you want.
January 14, 2010 at 11:04 am
thank you very much that makes alot of sense now.
January 14, 2010 at 12:04 pm
"awesome" - you did an excellent job of making genetic algorithms approachable
I would like to implement this kind of problem solver to our real world situation. What I would love to see next is a deconstruction of a non-toy example that could be solved by GA. I realize that's meta-programming, but if you could express a guide to fitting problems with GA solutions it would be extremely valuable. (even if it's only a "How to approach..." on determining genes or fitness scoring for a specific environment)
I was expecting "A Genetic Algorthm Sample in T-SQL" to use more declarative programming than a procedural approach. Do you think it is possible to construct your example as a selection from a cross product of genetics? I'm imagining a recursive CTE to manage iterations limited by a generational average score below the previous generational average. If you think it's not possible (or simply unfeasibly difficult) does that fact indicate that GA solutions are perhaps ill-suited for modelling in SQL ?
thanks for giving me something interesting to think about today. 🙂
January 14, 2010 at 1:09 pm
Great article!
Just out of curiosity, I took a child that achieved a perfect score and ran its DNA through the scoring procedure a few more times. To my surprise, the results were all over the map (ranging from -335 to 490). This led me to try removing the robot's ability to make random moves. Because the robots now perform consistently, no top score in any generation was lower than the generations that came before it, which was not the case in the original example.
Thanks for making my brain work today!
January 14, 2010 at 1:57 pm
Very "effen" cool! Kind of makes me think of my roomba vacuum lol. I was wondering about the effectiveness of a "random" move as well. Also, for example, if you have a wall at center and east, how can you have anything to the north? Are there more rules that cant happen?
I added this for a graphical representation of the Decipher Rules Results (@rules table), made it easier to follow the rules...(oh yeah, you have to view in results to text 😉 )
declare @crlf char(2)
set @crlf = char(13) + char(10)
select ' ' +
case n
when 0 then ' O '
when 1 then ' X '
when 2 then '!!!'
end
+ ' ' + @crlf +
case w
when 0 then ' O '
when 1 then ' X '
when 2 then '!!!'
end
+
case c
when 0 then ' O '
when 1 then ' X '
when 2 then '!!!'
end
+
case e
when 0 then ' O '
when 1 then ' X '
when 2 then '!!!'
end
+ ' = ' +
case a
when 0 then 'Go North'
when 1 then 'Go South'
when 2 then 'Go East'
when 3 then 'Go West'
when 4 then 'Pick up'
when 5 then 'Move Random'
end
+ @crlf + ' ' +
case s
when 0 then ' O '
when 1 then ' X '
when 2 then ' _ '
end
+ ' ' + @crlf + '-----------------------' + @crlf
from @rules
order by n, w, c, e, s, a
January 14, 2010 at 2:57 pm
I found it extremely humorous to change the "evolution" to "devolution" by changing max to min, creating some of the dumbest children in the world! ...the interesting thing is that it takes very little time for it to learn to get the worst score every time lol....just dont pick up soda cans!
January 14, 2010 at 6:17 pm
This is awesome. This could keep me busy for quite some time. Amazing that you were able to do it so quickly. Nice article.
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
January 14, 2010 at 10:04 pm
Has anyone noticed that you only need 162 genes instead of 243?
The current room can never have the value of wall, so the possible permutations are 2 * 3 * 3 *3 * 3 = 162.
Also, I decided to randomly switch which parent contributes to the top. So that in each generation roughly half of the children have tops from k1 and have from k2.
January 14, 2010 at 10:50 pm
For anyone who's interested - I recently worked with Bill to take his original T-SQL code and translate it into a C# Silverlight web application with a GUI that displays the robot's moves so you can actually see it working.
You can find the application by clicking the following link:
http://www.BradLinard.com/GenAlgSim
You'll need to have Silverlight installed for it to run.
It may still need a minor bug or two worked out, but it's still a cool, functional, GUI representation of the T-SQL algorithm.
January 15, 2010 at 2:07 am
I like the concept of this. It's essentially an "intelligent trial and error" approach.
If you can lock down the random actions, and add a bit of intelligence here and there, you could start generating some good solutions.
January 15, 2010 at 4:16 am
I found this quite an interesting example of a genetic algorithm. I had so far just seen them in theory, and the one time I tried to implement performance was too slow to be practical. I had never thought of implementing this in T-Sql, but it shows you can do a lot with it.
I was wondering 2 things though:
- wouldn't a C# implementation be much faster? (if I can spare a few hours I might actually try)
- I may have missed something, but I didn't quite understand what the use is of random moves. Wouldn't that influence the rest of the route, and more importantly make the fitness function non-deterministic?
January 15, 2010 at 6:40 am
Thanks for Sharing the website Brad! I find it useful to see how the robot learns and improves as generations pass. Although even higher generation can get themselves driving in circles 😉
January 15, 2010 at 9:35 am
auke-947144 (1/15/2010)
I was wondering 2 things though:- wouldn't a C# implementation be much faster? (if I can spare a few hours I might actually try)
- I may have missed something, but I didn't quite understand what the use is of random moves. Wouldn't that influence the rest of the route, and more importantly make the fitness function non-deterministic?
I have been tinkering with it in c# and of course it is extremely fast.
I think the random moves was part of the initial challenge. And yes it gives a solution that can score differently in two different passes. Taking the random move out gives a solution that works consistently.
Viewing 15 posts - 16 through 30 (of 41 total)
You must be logged in to reply to this topic. Login to reply