January 15, 2010 at 9:46 am
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.
January 15, 2010 at 3:16 pm
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...
January 15, 2010 at 3:22 pm
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.
January 15, 2010 at 4:01 pm
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.
January 15, 2010 at 4:08 pm
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.
January 15, 2010 at 4:45 pm
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...
January 18, 2010 at 6:56 am
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.
January 18, 2010 at 7:48 am
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 🙂
January 18, 2010 at 7:52 am
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.
January 20, 2010 at 3:09 am
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 🙂
March 16, 2010 at 12:14 pm
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!
June 29, 2017 at 5:49 am
This is amazing. Thanks Bill.
Viewing 12 posts - 31 through 41 (of 41 total)
You must be logged in to reply to this topic. Login to reply