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
Mike Dougherty
Mike Dougherty
Old Hand
Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)Old Hand (310 reputation)

Group: General Forum Members
Points: 310 Visits: 952
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.
Ben Thul
Ben Thul
SSC-Enthusiastic
SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)

Group: General Forum Members
Points: 170 Visits: 469
If it's a 10x10 grid and the robot gets 200 moves, wouldn't an optimal solution be to traverse the grid in a zig-zag pattern (i.e. left-to-right across row 1, go down to row 2 and traverse it right-to-left, etc), picking up cans as it goes? It certainly has enough moves to do so since the grid only contains 100 squares. Don't get me wrong...I thought the article was interesting, but there seems to be a pretty trivial optimal solution...
Bill Talada
Bill Talada
SSCrazy
SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)

Group: General Forum Members
Points: 2788 Visits: 2125
Ben Thul (1/15/2010)
If it's a 10x10 grid and the robot gets 200 moves, wouldn't an optimal solution be to traverse the grid in a zig-zag pattern (i.e. left-to-right across row 1, go down to row 2 and traverse it right-to-left, etc), picking up cans as it goes? It certainly has enough moves to do so since the grid only contains 100 squares. Don't get me wrong...I thought the article was interesting, but there seems to be a pretty trivial optimal solution...


If t-sql supported arrays, I would have implemented a gnarly shaped maze of walls and partial dividers and the robot would have adapted beautifully. There is nothing in my code that ever tells the robot how to solve the problem. If I implemented an algorithm, it would be rendered useless with each new gnarly shaped maze a robot faced.
LutzM
LutzM
SSC-Insane
SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)

Group: General Forum Members
Points: 22363 Visits: 13559
Bill Talada (1/15/2010)

If t-sql supported arrays, I would have implemented a gnarly shaped maze of walls and partial dividers and the robot would have adapted beautifully.

How would you define a "wall type"?
If I understood the basic concept it should be easy to have either nothing (0), a can (1) or a wall (2) as the possible "status" of a cell.
Instead of the pattern you used you could also have
1120010010
1121101111
0010222222
1110201010
2000100001
2100111100
1111101111
1100100111
0111011122
0110000101
, where 2 would represent a wall.
I don't understand why that can't be done.



Lutz
A pessimist is an optimist with experience.

How to get fast answers to your question
How to post performance related questions
Links for Tally Table , Cross Tabs and Dynamic Cross Tabs , Delimited Split Function
Bill Talada
Bill Talada
SSCrazy
SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)SSCrazy (2.8K reputation)

Group: General Forum Members
Points: 2788 Visits: 2125
To keep the code sample very small, I cut some corners. The code that "looks" at the surroundings of the robot assumes a square border around a 10 x 10 grid. Inserting a 2 into the grid won't help; it will be ignored currently. I would have loved to implement a crazy maze but my objective was to make it easy for people to understand Genetic Algorithms.
LutzM
LutzM
SSC-Insane
SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)SSC-Insane (22K reputation)

Group: General Forum Members
Points: 22363 Visits: 13559
Bill Talada (1/15/2010)
To keep the code sample very small, I cut some corners. The code that "looks" at the surroundings of the robot assumes a square border around a 10 x 10 grid. Inserting a 2 into the grid won't help; it will be ignored currently. I would have loved to implement a crazy maze but my objective was to make it easy for people to understand Genetic Algorithms.


Understood. And I really enjoyed reading your article and playing around with the sample code. Great job!
You made me think of using this base concept in reverse, meaning you'll have a given number of cans (e.g. 20, 30 and 40), a 10x10 box and you need to build a pattern that comes closest to some given rules (e.g. the first 5 rows have to be evenly distributed, rows 6 and 7 need to be aligned left, rows 8 and 9 need to be aligned to the right and row 10 needs to be centered and each "column" should have the same number of cans.) Optimum would be calculated using a similar +/- point system... So, my kids most probably won't like it seing me spend the weekend trying to figure out if there's a basic reverse logic to what you came up with...



Lutz
A pessimist is an optimist with experience.

How to get fast answers to your question
How to post performance related questions
Links for Tally Table , Cross Tabs and Dynamic Cross Tabs , Delimited Split Function
ben.rosato
ben.rosato
Mr or Mrs. 500
Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)

Group: General Forum Members
Points: 545 Visits: 1566
Bill Talada (1/15/2010)
To keep the code sample very small, I cut some corners. The code that "looks" at the surroundings of the robot assumes a square border around a 10 x 10 grid. Inserting a 2 into the grid won't help; it will be ignored currently. I would have loved to implement a crazy maze but my objective was to make it easy for people to understand Genetic Algorithms.



I don't understand why you say it would be ignored. If I put a 2 in there somewhere the robot will see a wall in that direction.

case when @y=0 then '2' else substring(@world, ((@y-1)*10)+@x+1,1)

Down in the movement section

if substring(@RobotsView,2,1)='2'
set @points = @points - 5

That takes off 5 points and it doesn't move. I surely seems like you can put walls in there to me.
Ben Thul
Ben Thul
SSC-Enthusiastic
SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)SSC-Enthusiastic (170 reputation)

Group: General Forum Members
Points: 170 Visits: 469
I think to truly support walls in the middle of the grid, you'd need to change how you encode the maze. I thought of one such encoding using bit masks. Each square has a value v. If v & 0x01 <> 0, there's a can there, v & 0x02 <> 0 means there's a wall to the north, v & 0x04 means a wall to the east, etc. If you're also generating the maze programatically, you have to be careful about not putting cans in a closed area. But that's another issue :-)
ben.rosato
ben.rosato
Mr or Mrs. 500
Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)Mr or Mrs. 500 (545 reputation)

Group: General Forum Members
Points: 545 Visits: 1566
Ben Thul (1/18/2010)
I think to truly support walls in the middle of the grid, you'd need to change how you encode the maze. I thought of one such encoding using bit masks. Each square has a value v. If v & 0x01 <> 0, there's a can there, v & 0x02 <> 0 means there's a wall to the north, v & 0x04 means a wall to the east, etc. If you're also generating the maze programatically, you have to be careful about not putting cans in a closed area. But that's another issue :-)


All I know is if I put a wall of 2's in there and print out @robotview, it will show that the robot does see walls inside the room. In the movement code, if it wants to move that direction but there is a wall there, it loses 5 points.
azatoth
azatoth
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
yeah, that would be nice seeing it in a real world scenario, business case, tough T-SQL process that needs some optimizing (im working on one right now)...
One thing... GA solution to such a problem can be coded in almost all of the languages... what about the comparison of more intuitive choice like C++/C# and T-SQL? I understand if we want the solution right there in DB, T-SQL is an obvious choice, but is it faster? slower? then a for example CLR storeds written in .NET or managed code? was just wondering Smile
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