A Genetic Algorthm Sample in T-SQL

  • 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.

  • 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...

  • 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.

  • 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[/url]
    How to post performance related questions[/url]
    Links for Tally Table [/url] , Cross Tabs [/url] and Dynamic Cross Tabs [/url], Delimited Split Function[/url]

  • 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.

  • 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[/url]
    How to post performance related questions[/url]
    Links for Tally Table [/url] , Cross Tabs [/url] and Dynamic Cross Tabs [/url], Delimited Split Function[/url]

  • 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.

  • 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 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.

  • 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 🙂

  • I converted this into proper OO C# and it runs great. I was able to get a score of 490. I found that the DNA strand you provided in the TSQL for a score of 480 doesnt work as you would expect because of the random genes. What you have to output is the action path resulting from the DNA strand.

    It is true that if you removed the random gene, you woudl get more consistant results, but if you think about the way that humans are, you would realize that you would be removing the human element form the system. Doing so may or may not be a good thing 😉 I think that modifying this GA code in certain ways would benefit specific requirements and would not fit every solution.

    I've already implemented walls and other items as well as robot memory with some very interesting results.

    GA FTW!

  • This is amazing.  Thanks Bill.

Viewing 12 posts - 31 through 42 (of 42 total)

You must be logged in to reply to this topic. Login to reply