Simulation Solves The Traveling Salesman's Dilemma
“The simple truth behind simulated annealing? Sometimes things really do have to get worse before they can get better.”
For fun today I am sharing this recent article by Todd Schneider entitled “The Traveling Salesman with Simulated Annealing” that highlights some interesting lessons from a computer simulation which he built and shared:
“I built an interactive Shiny application that uses simulated annealing to solve the famous traveling salesman problem. You can play around with it to create and solve your own tours. Here’s an animation of the annealing process finding the shortest path through the 48 state capitals of the contiguous United States:
We start by picking an arbitrary initial tour from the set of all valid tours. From that initial tour we “move around” and check random neighboring tours to see how good they are. There are so many valid tours that we won’t be able to test every possible solution, but a well-designed annealing process eventually reaches a solution that, if it is not the global optimum, is at least good enough. Here’s a step-by-step guide:
- Start with a random tour through the selected cities. Note that it’s probably a very inefficient tour!
- Pick a new candidate tour at random from all neighbors of the existing tour. This candidate tour might be better or worse compared to the existing tour (i.e. shorter or longer)
- If the candidate tour is better than the existing tour, accept it as the new tour
- If the candidate tour is worse than the existing tour, still maybe accept it, according to some probability. The probability of accepting an inferior tour is a function of how much longer the candidate is compared to the current tour, and the temperature of the annealing process. A higher temperature makes you more likely to accept an inferior tour
- Go back to step 2 and repeat many times, lowering the temperature a bit at each iteration, until you get to a low temperature and arrive at your (hopefully global, possibly local) minimum. If you’re not sufficiently satisfied with the result, try the process again, perhaps with a different temperature cooling schedule
The key to the simulated annealing method is in step 4: even if we’re considering a tour that is worse than the tour we already have, we still sometimes accept the worse tour temporarily, because it might be the stepping stone that gets us out of a local minimum and ultimately closer to the global minimum. The temperature is usually pretty high at the beginning of the annealing process, so that initially we’ll accept more tours, even the bad ones. Over time, though, we lower the temperature until we’re only accepting new tours that improve upon our solution.
That’s all well and good, but why do we need the annealing step at all? Why not do the same process with 0 temperature, i.e. accept the new tour if and only if it’s better than the existing tour? It turns out if we follow this naive “hill climbing” strategy, we’re far more likely to get stuck in a local minimum.”
In healthcare simulation, we could possibly use the same mathematical methodology to improve training outcomes and ultimately patient safety by considering that although minor immediate improvements may be better, we need to explore ALL the potential variations to come up with the most efficient systems.
Read the rest of this unique simulation article on ToddwSchneider.com!