Geeky Reflections -- Simulated Annealing
When I was an undergrad, my interest was in interfacing microcomputers with mechanical devices. Most of what we did would be labelled "robotics" today, or at least proto-robotics (e.g. ripping the ultrasonic rangefinder out of a Polaroid camera, putting it on a stepper motor, and trying to paint a radar image of the room on a computer screen).
In doing this, we were playing around with S-100 bus computers (PC's were a bit in the future at that point) and I got interested in brute force approaches to solving the traveling salesman problem. The way this is done is to establish some random points in x,y space and then connect them with a random path and measure the length of that path. The initial random path is obviously going to be a terrible solution. So you have the computer randomly flip flop two segments, and then you see if the resulting total distance is reduced. If it is, then you keep the change and try another.
This will lead to a much shorter path, but often will not lead to the optimally shortest path. The reason is that the result can get stuck in a local minimum that is not the optimum. Essentially, to break out of this, you have to allow the solution to get worse first before it can get better.
The approach I was playing with was called simulated annealing. Everything I said above is the same in this approach, but sometimes you let the program accept flip-flopped segments that yield a worse (ie longer) rather than better path. The allowed amount worse is governed by a "temperature" that is slowly lowered. Initially, at high temperatures, the solution can jump into most any solution, better or worse. But as the "temperature" is lowered, the allowed amount of jumping into worse solutions is reduced. Essentially, the system is much, much more likely than the previous approach to settle closer to the actual optimum. This is roughly an analog of how annealing works in metals. The code is ridiculously simple. I don't remember it being much more than 100 lines in Pascal.
Anyway, if you lived through the above without falling asleep, the payoff is this site. After 30 years of pretty much never thinking about simulated annealing again, I found Todd Schneider's blog which has a great visual overview of solving the travelling salesman problem with simulated annealing. If you really want to visually see it work, go to the customizable examples at the bottom and set the iterations per map draw for about 100. Then watch. It really does look a bit like a large excited molecule slowly cooling. Here is an example below but check out his site.
