I just finished a very interesting book called “One Jump Ahead: Challenging Human Supremacy in Checkers.” It was written by Jonathan Schaeffer, the main force behind the creation of Chinook, one of the absolute best checkers playing programs ever created. (You can even play it, but expect to be beaten!)
I ran my Traveling Salesman GA program on a 200-city tour overnight, and unfortunately it didn’t get too far. That was a little disappointing. But, I have some ideas!
I just finished a prototype for what I hope will be a good “fun Java lab” for my students. It’s an implementation of the Traveling Salesman Problem, as “solved” by genetic algorithms. I have it running on a map of 200 locations right now, and it is slowly but surely progressing in the right direction. That’s always encouraging!
It sure beats my artificial-ant simulation where the ants went away from the food! That one still needs some work…
With N locations, there are (N - 1)! / 2 different paths that can be chosen for the salesman to follow. So, for my 200 locations, there are around 2×10^372 different possibilities to be considered. The GAs search a whole lot less options than that (understatement), and they almost certainly won’t find the optimal solution, but at least you can watch them get better over time!
I have half a mind to leave this running overnight, but I’m not sure if my implementation can even cover the search-space completely. There might be a bug that prohibits it from fully exploring the search-space. But, I’ll let it go - see what I find in the morning!
You are currently browsing the archives for the AI & ALife category.
