Simulated Annealing Optimization Using C# or Python in Visual Studio Magazine

I wrote an article titled “Simulated Annealing Optimization Using C# or Python” in the December 2021 edition of Microsoft Visual Studio Magazine. See https://visualstudiomagazine.com/articles/2021/12/01/traveling-salesman.aspx.

The goal of a combinatorial optimization problem is to find the best ordering of a set of discrete items. A classic combinatorial optimization challenge is the Traveling Salesman Problem (TSP). The goal of TSP is to find the order in which to visit a set of cities so that the total distance traveled is minimized.

One of the oldest and simplest techniques for solving combinatorial optimization problems is called simulated annealing. The VSM article shows how to implement simulated annealing for the Traveling Salesman Problem using C# or Python.

My article is centered around a concrete example. The demo sets up a synthetic problem where there are 20 cities, labeled 0 through 19. The distance between cities is designed so that the best route starts at city 0 and then visits each city in order. The total distance of the optimal route is 19.0.

The demo sets up a random initial guess of the best route as [ 7, 11, 6 . . 17, 3 ]. After iterating 2500 times, the demo reports the best route found as [ 0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]. The total distance required to visit the cities in this order is 21.5 and so the solution is close to, but not quite as good as, the optimal solution (the order of cities 8 and 9 is reversed).

Expressed as pseudo-code, simulated annealing is:

make a random initial guess
set initial temperature
loop many times
swap two randomly selected elements of the guess
compute error of proposed solution
if proposed solution is better than curr solution then
accept the proposed solution
else if proposed solution is worse then
accept the worse solution anyway with small probability
else
don't accept the proposed solution
end-if
reduce temperature slightly
end-loop
return best solution found

Simulated annealing is a meta-heuristic, meaning it’s a set of general guidelines rather than a rigidly defined algorithm. Therefore, there are many possible designs you can use. A common enhancement to basic simulated annealing is to track every possible solution that’s generated and save the best solution seen. With the demo implementation, it’s possible for the best-seen solution to be replaced by a worse solution.

I did an Internet search and was mildly surprised that I did not find even a single page dedicated to the Traveling Salesman Problem for the cities of Middle Earth from the Lord of The Rings series of novels.

This entry was posted in Machine Learning. Bookmark the permalink.