This is a Java application that demonstrates the Simulated Annealing algorithm with an attack on the "traveling salesman" problem.
What is simulated annealing?
Simulated annealing is a technique, which was developed to help solve large combinatorial optimization problems. It is based on probabilistic methods that avoid being stuck at local (non-global) minima. It has proven to be a simple but powerful method for large-scale combinatorial optimization.
For practical purposes, simulated annealing has solved the famous traveling salesman problem: find the shortest of N! paths connecting N cities. Simulated annealing finds a very good approximation to the shortest path out of the huge number of all possible paths.
Annealing is nature's trick to find extrema in very complicated situations. Simulated annealing mimics on a computer the natural process by which crystal lattices of glass or metal relax when heated. The molecules of hot glass or metal are free to move about. Temperature is an average of the thermal energy in each molecule of an object. If the temperature drops quickly, these molecules solidify into a complex structure. However, if the temperature drops slowly, they form a highly ordered crystal. The molecules of a crystal solidify into a minimal energy state.
Some real applications simulated annealing:
The algorithm:
In the simulated annealing algorithm, an objective function to be minimized is defined. Here it will be the total path length through a set of points. The distance between each pair of points is equivalent to the "energy" of a molecule. Then, "temperature" is the average of these lengths. Starting from an initial point, the algorithm swaps a pair of points and the total "energy" of the path is calculated. Any downhill step is accepted and the process repeats. An uphill step may be accepted. Thus, the algorithm can escape from local minima. This uphill decision is made by the Metropolis criteria. As the optimization process proceeds, the algorithm closes in on the global minimum.
Since the algorithm makes very few assumptions regarding the objective function, it is quite robust. The degree of robustness can be adjusted by the user using some important parameters:
Pseudo code of basic process:
initialize temperature
for i := 1...ntemps do
temperature := factor * temperature
for j := 1...nlimit do
try swapping a random pair of points
delta := current_cost - trial_cost
if delta > 0 then
make the swap permanent
increment good_swaps
else
p := random number in range [0...1]
m := exp( delta / temperature )
if p < m then // Metropolis criterion
make the swap permanent
increment good_swaps
end if
end if
exit when good_swaps > glimit
end for
end for
The Metropolis[1] criterion attempts to permit small uphill moves while rejecting large uphill moves. This is to prevent the algorithm from becoming stuck in a local minimum. When the first else branch is selected above, a uniformly distributed random number p in the range [0...1] is generated and compared with the Metropolis number:
m = e delta/temperature
Since delta/temperature is negative in the else branch, we are calculating the value of e raised to a negative power so that m will also be in the range [0...1]. The more negative the power, the closer to 0 the value of m. Large negative values of delta and decreasing values for temperature make acceptance of an uphill move less likely.
Benefits of the algorithm:
It can be seen from the pseudocode above that the algorithm is order of nlimit * ntemps while searching though all possible combination for the best path is order of n! . Two test cases have been provided to demonstrate the benefits of this algorithm. The main benefit is that a good approximation to the shortest path can be found in a "reasonable" amount of time. Note that the age of the universe is:
1.5x1010[yr]·365[d/yr]·24[hr/d]·3600[sec/hr] = 4.73x1017[sec]
An exhaustive search of all possible paths through only 36 points would require about
36! = 3.72x1041
comparisons to find the shortest path. This would take more time than the age of the universe.
References
[1] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M. N., Teller, A.H. and Teller, E.; "Equations of State Calculations by Fast Computing Machines;" J. Chemical Physics, vol. 21 (1953); pp.1087-1092
[2] Carlson, Shawn; "The Amateur Scientist - Algorithm of the Gods;" Scientific American; March 1997, pp.121-123
[3] McLaughlin, Michael P.; "Simulated Annealing;" Dr. Dobb's Journal; September 1989; pp. 26-37