Traveling Salesman II
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 have seen a lot of TSP-solvers that use genetic algorithms, and they use crossover during the reproductive phase. Of course, they all say the same thing - “This might result in invalid travel-plans.” Yeah - after crossover, a location might be visited twice, or not at all!
So my first implementation avoided crossover completely, but now I am not sure if that was the best idea. I will have to think about that one some more. I’m still not convinced I need it.
However, there is another issue in my implementation, regarding what kinds of mutations are applied, and where. Right now it is completely random: I apply some number of mutations, each of which consists of swapping two randomly-chosen locations in the travel-plan. This is a very inefficient mutation strategy.
I want to try a more efficient one, where I analyze each travel-plan to see what parts of the genome are “less fit.” That is the beauty of this particular problem; you can look at a particular travel-plan and see which parts of it are good or bad.
I want to bias the probability of mutations so that they occur most frequently on the longer legs of a particular travel-plan, and they occur less frequently on shorter legs of the plan. That should help the system converge more quickly to a better solution, because it will know which parts of the “best solution” aren’t really that good, and therefore need more work.