Genetic algorithms and the Traveling Salesman Problem

Cool Little Toy of the Day: An applet that solves the Traveling Salesman Problem.

The TSP is a classic in AI. You’re a salesman that has to find the shortest path to visit each city in an area. (Apparently you’re allowed to cut across fields in this implementation.)

This approach uses a genetic algorithm, where ‘agents’ try finding a path, and the most successful agents spawn ‘children’ that do the same job but just a little different from the parent.

Give them 300 cities and watch as generation after generation struggles to optimise!

Genetic algorithms are a great model of evolution in action. When I programmed an evolutionary system for a dialogue agent, the most interesting part was evolutionary convergence: how the successful organisms in a population converged on an optimal answer, and thus resembled each other.

Compare it to this description:

There is a certain species of aquatic snail that has to put up with a parasite that bores into its shell and can kill it. So should the snail grow a thicker shell, to reduce the risk of being parasitised? Not necessarily, because being heavier means it’s more difficult to escape predators. So should the snail grow a thinner shell? Maybe, but that means it’s more exposed to the risk of being smashed against a rock and killed by a wave. So a thicker shell is in order? Well yes, unless this reduces its fertility by diverting calcium from its reproductive organs. If we sat down and tried to work out the optimum shell thickness, we would find it nightmarishly difficult. However, natural selection just does it all automatically: a snail with a shell of thickness X will be exposed to certain dangers during its lifetime, and will run a certain risk of dying. No matter how complicated the risks, there will likely be a single optimum shell thickness, and natural selection will home the snail in on this.

That’s it. Just pump out a population of individuals and let natural selection converge. Perhaps a tad wasteful, but very effective.

There are implications for belief systems as well. Many religions were created in the fertile 1800s, and most of them have broken up. Those that have survived are the ones that have made all the right moves. And successful religions resemble each other; that’s why all religions say things like ‘Be good to people’ and ‘Don’t kill or steal.’ These belief systems, by appearing in a population and being modified gradually, have converged upon a moral system that is more or less optimal for humans in a world such as ours. They represent thousands of years of human experience. If there’s a reason to respect religious beliefs, this is it.

This genetic algorithm thing can really change the way you see your life and other people. We’re all evolutionary agents in the world. How are you doing?