SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


A Genetic Algorthm Sample in T-SQL


A Genetic Algorthm Sample in T-SQL

Author
Message
pjancicka
pjancicka
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 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!



JeremyG
JeremyG
Valued Member
Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)

Group: General Forum Members
Points: 65 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 Wink )



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


JeremyG
JeremyG
Valued Member
Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)Valued Member (65 reputation)

Group: General Forum Members
Points: 65 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!
SQLRNNR
SQLRNNR
SSC-Dedicated
SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)SSC-Dedicated (32K reputation)

Group: General Forum Members
Points: 32619 Visits: 18558
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

aql
aql
Forum Newbie
Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)

Group: General Forum Members
Points: 8 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.
brad.linard
brad.linard
Forum Newbie
Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)

Group: General Forum Members
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.
SQLTuna
SQLTuna
UDP Broadcaster
UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)UDP Broadcaster (1.4K reputation)

Group: General Forum Members
Points: 1440 Visits: 328
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.
auke-947144
auke-947144
Forum Newbie
Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)

Group: General Forum Members
Points: 1 Visits: 15
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?
Pieter-423357
Pieter-423357
SSC-Enthusiastic
SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)SSC-Enthusiastic (183 reputation)

Group: General Forum Members
Points: 183 Visits: 577
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 ;-)
aql
aql
Forum Newbie
Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)Forum Newbie (8 reputation)

Group: General Forum Members
Points: 8 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.
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search