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 Friday, January 15, 2010 9:46 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Thursday, July 22, 2010 8:59 AM
Points: 110, 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.
Post #848396
Posted Friday, January 15, 2010 3:16 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, October 17, 2014 3:53 PM
Points: 100, Visits: 409
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...
Post #848587
Posted Friday, January 15, 2010 3:22 PM


SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Today @ 8:53 AM
Points: 145, Visits: 931
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.
Post #848593
Posted Friday, January 15, 2010 4:01 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Thursday, October 23, 2014 3:13 PM
Points: 6,842, Visits: 13,364
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
Post #848607
Posted Friday, January 15, 2010 4:08 PM


SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Today @ 8:53 AM
Points: 145, Visits: 931
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.
Post #848611
Posted Friday, January 15, 2010 4:45 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Thursday, October 23, 2014 3:13 PM
Points: 6,842, Visits: 13,364
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
Post #848621
Posted Monday, January 18, 2010 6:56 AM
Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Tuesday, September 30, 2014 8:46 AM
Points: 361, Visits: 1,541
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.
Post #849131
Posted Monday, January 18, 2010 7:48 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Friday, October 17, 2014 3:53 PM
Points: 100, Visits: 409
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
Post #849170
Posted Monday, January 18, 2010 7:52 AM
Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Tuesday, September 30, 2014 8:46 AM
Points: 361, Visits: 1,541
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.
Post #849175
Posted Wednesday, January 20, 2010 3:09 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Wednesday, January 20, 2010 3:02 AM
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 :)
Post #850333
« Prev Topic | Next Topic »

Add to briefcase «««12345»»

Permissions Expand / Collapse