Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««12345»»»

A Genetic Algorthm Sample in T-SQL Expand / Collapse
Author
Message
Posted Thursday, January 14, 2010 1:09 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Monday, May 19, 2014 10:48 AM
Points: 11, Visits: 34
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!




Post #847869
Posted Thursday, January 14, 2010 1:57 PM


SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Sunday, December 11, 2011 10:58 AM
Points: 49, Visits: 100
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

Post #847927
Posted Thursday, January 14, 2010 2:57 PM


SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Sunday, December 11, 2011 10:58 AM
Points: 49, Visits: 100
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!
Post #847979
Posted Thursday, January 14, 2010 6:17 PM


SSCoach

SSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoach

Group: General Forum Members
Last Login: Yesterday @ 9:21 AM
Points: 17,977, Visits: 15,981
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
Post #848043
Posted Thursday, January 14, 2010 10:04 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, February 5, 2010 10:27 AM
Points: 6, Visits: 3
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.
Post #848079
Posted Thursday, January 14, 2010 10:50 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Tuesday, March 16, 2010 12:18 PM
Points: 1, Visits: 5
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.

Post #848084
Posted Friday, January 15, 2010 2:07 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Tuesday, November 4, 2014 10:09 AM
Points: 1,388, Visits: 277
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.
Post #848131
Posted Friday, January 15, 2010 4:16 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, November 2, 2012 3:30 AM
Points: 1, Visits: 14
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?
Post #848161
Posted Friday, January 15, 2010 6:40 AM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Monday, May 5, 2014 8:55 AM
Points: 86, Visits: 478
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
Post #848220
Posted Friday, January 15, 2010 9:35 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, February 5, 2010 10:27 AM
Points: 6, Visits: 3
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.
Post #848387
« Prev Topic | Next Topic »

Add to briefcase «««12345»»»

Permissions Expand / Collapse