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.
January 15, 2010 at 9:46 am
I think the value of random move is for illustrative purposes.
I think the value of "wall at center" also illustrates a full permutation test. That we can observe the impossibility of that situation uses a type of intelligence unavailable to primitive evolution. There are also situations where the number of genes is so high/complexly valued that human involvement to early-prune is unfeasible. It was good to show a full permutation approach because it's shows that impossible solutions are simply irrelevant "junk DNA."
This article inspired me to use GA as a seminar paper topic. I will be attempting to implement a solution finder that will require thousands of genes. Even if my assumptions about populations and genotypes are wrong, it'll be an interesting paper.
Viewing 15 posts - 16 through 30 (of 42 total)
You must be logged in to reply to this topic. Login to reply