A while ago I put together a genetic algorithm with Ruby that does some cool stuff. I was disappointed with my previous GAs- you provide it the phrase and it evolves it. That’s really boring. And useless. I wanted to produce a GA that would tell you something you didn’t already know.
So I wrote this pathfinder. You have a map, which has points/nodes like A, B, C and so on. And there are paths between some of the points, and paths have lengths. A-B has a length of 2, B-C has a length of 7. And so on. I wrote a GA that generates random “routes” and calculates the fitness based on the length of the route and whether or not it begins where the user asks it to and ends where the user asks it to.
The real key here was the mutation function. It wasn’t enough to change existing genes. It also had to insert random genes/nodes at the beginning, end, or in the middle. Now that I’m thinking about it, it probably should’ve been able to delete a gene, too, but I didn’t think of that at the time. Having a very flexible mutation function allowed for more random routes to be generated.
Previous GAs that I have written stop running when the best fitness is 0. Here, there won’t ever be a fitness of 0. The GA can only do the best it can, which may or may not be the best answer. Which is, I think, a much more accurate simulation.
Here is the map file that I used, which is kinda hard to understand so I’ll explain it here. Each line has a from node, a to node, and a length of the path between them. I put things like “A B 2″ and “B A 2″ because I wanted the path between A and B to be two-way. You could make this path one way by removing one of these lines. Of course, all of this would make more sense if I had a pretty picture to show you the map, but I don’t. Running the program
looks like this:
From: a
To: g
Population size: 128
How many generations: 250
@ 0: Best path is AD (10002)
@ 25: Best path is ABEG (6)
And here is the source if you’re interested in seeing/running that.
