Simulated annealing is a computational algorithm for optimization. It mimics the physical process of thermal annealing in which a metal is heated and then slowly cooled to settle into a highly ordered crystal structure. The application and removal of heat allows the atoms to move around freely and then gradually release energy to the cooling bath. The atoms naturally settle toward the state with the least potential energy as they fall into low energy positions and cannot get back out.
For common metals, the lowest energy state is already known. But the method is useful for other problems where the best state is not known and exhaustively searching all possible states is impractical. The method is applied by modeling the problem as a physical system with structure, energy, and temperature. The steps for solving a problem with simulated annealing include:
A common example of a problem that can be solved with simulated annealing is the traveling salesman problem. A salesman wants to visit several cities. He can visit them in any order he likes, but it would be most profitable if he could minimize the total length of the trip to save on fuel. Clearly it's best to avoid criss-crossing his territory, but the exact order to visit the cities is difficult to guess. For a tour of twenty cities, there are 20! (factorial) = 2,432,902,008,176,640,000 possible itineraries to check!
Casting the problem in the language of simulated annealing, an ordered list of cities describes the "state" of the system. With a table of coordinates the length of a tour can be calculated to serve as the "energy". Switching the position of two cities in the list constitutes a "move" that could change the list into a better order. And the "temperature" is a number having the same units of distance as the "energy" and comparable magnitude to the distances encountered. Since simulated annealing is a method of trial and error, the duration should be long enough for many trials to overcome many errors. A suitable duration might be several thousand trials multiplied by the length of the list.
The traveling salesman problem is in fact easily solved with simulated annealing. A computer can find a nearly optimal solution in just a few hundred thousand trials rather than searching all the quintillions of possibilities. Many other problems can be solved with the method, but it is tedious, inefficient, and error-prone to reprogram it for each new problem.
Therefore I am sharing my own Python code for simulated annealing. Features include:
Download the module anneal.py. If you find it useful please send me a note at wagnerr@umich.edu. If you find a bug please let me know. And if you have an improvement please share it!
A test program is included for solving a traveling salesman problem:
from anneal import *
# List latitude and longitude (degrees) for the twenty largest U.S. cities
cities = { 'New York City': (40.72,74.00), 'Los Angeles': (34.05,118.25),
'Chicago': (41.88,87.63), 'Houston': (29.77,95.38),
'Phoenix': (33.45,112.07), 'Philadelphia': (39.95,75.17),
'San Antonio': (29.53,98.47), 'Dallas': (32.78,96.80),
'San Diego': (32.78,117.15), 'San Jose': (37.30,121.87),
'Detroit': (42.33,83.05), 'San Francisco': (37.78,122.42),
'Jacksonville': (30.32,81.70), 'Indianapolis': (39.78,86.15),
'Austin': (30.27,97.77), 'Columbus': (39.98,82.98),
'Fort Worth': (32.75,97.33), 'Charlotte': (35.23,80.85),
'Memphis': (35.12,89.97), 'Baltimore': (39.28,76.62) }
def distance(a, b):
"""Calculates distance between two latitude-longitude coordinates."""
R = 3963 # radius of Earth (miles)
lat1, lon1 = math.radians(a[0]), math.radians(a[1])
lat2, lon2 = math.radians(b[0]), math.radians(b[1])
return math.acos( math.sin(lat1)*math.sin(lat2) +
math.cos(lat1)*math.cos(lat2)*math.cos(lon1-lon2) ) * R
def route_move(state):
"""Swaps two cities in the route."""
a = random.randint( 0, len(state)-1 )
b = random.randint( 0, len(state)-1 )
state[a], state[b] = state[b], state[a]
def route_energy(state):
"""Calculates the length of the route."""
e = 0
for i in range(len(state)):
e += distance( cities[state[i-1]], cities[state[i]] )
return e
# Start with the cities listed in random order
state = cities.keys()
random.shuffle(state)
# Minimize the distance to be traveled by simulated annealing with a
# manually chosen temperature schedule
annealer = Annealer(route_energy, route_move)
state, e = annealer.anneal(state, 10000000, 0.01, 18000*len(state), 9)
while state[0] != 'New York City':
state = state[1:] + state[:1] # rotate NYC to start
print "%i mile route:" % route_energy(state)
for city in state:
print "\t", city
# Minimize the distance to be traveled by simulated annealing with an
# automatically chosen temperature schedule
state, e = annealer.auto(state, 4)
while state[0] != 'New York City':
state = state[1:] + state[:1] # rotate NYC to start
print "%i mile route:" % route_energy(state)
for city in state:
print "\t", city
And produces the following output:
Temperature Energy Accept Improve Elapsed Remaining
10000000.00 27175.65 0:00:00
1000000.00 25460.48 99.98% 47.42% 0:00:10 0:01:16
100000.00 21708.42 99.77% 47.23% 0:00:19 0:01:06
10000.00 20864.90 97.82% 46.42% 0:00:28 0:00:56
1000.00 12854.42 79.69% 37.05% 0:00:37 0:00:47
100.00 7516.23 26.07% 10.73% 0:00:47 0:00:38
10.00 6801.84 7.03% 1.00% 0:00:56 0:00:28
1.00 6801.84 5.11% 0.02% 0:01:06 0:00:19
0.10 6801.84 4.86% 0.00% 0:01:16 0:00:09
0.01 6801.84 4.88% 0.00% 0:01:25 0:00:00
6801 mile route:
New York City
Philadelphia
Baltimore
Charlotte
Jacksonville
Memphis
Dallas
Fort Worth
Houston
Austin
San Antonio
Phoenix
San Diego
Los Angeles
San Jose
San Francisco
Chicago
Indianapolis
Columbus
Detroit
Attempting automatic simulated anneal...
Exploring temperature landscape:
Temperature Energy Accept Improve Elapsed
5700.00 22158.45 90.70% 43.25% 0:00:01
8600.00 19680.32 94.15% 45.80% 0:00:01
13000.00 27935.33 95.80% 45.30% 0:00:02
20000.00 25076.94 97.65% 46.60% 0:00:02
30000.00 25242.76 98.65% 47.00% 0:00:03
20000.00 21482.89 97.65% 45.40% 0:00:03
13000.00 22935.96 96.20% 45.25% 0:00:04
8700.00 20202.33 93.85% 44.40% 0:00:04
5800.00 23347.61 90.25% 42.80% 0:00:05
3900.00 17967.47 86.70% 41.25% 0:00:05
2600.00 22419.11 79.70% 36.65% 0:00:05
1700.00 13579.92 67.75% 31.85% 0:00:06
1100.00 18004.05 55.90% 24.45% 0:00:06
730.00 12137.98 45.70% 20.80% 0:00:07
490.00 10116.87 37.25% 15.80% 0:00:07
330.00 12417.96 24.10% 9.90% 0:00:08
220.00 8050.44 19.00% 7.00% 0:00:08
150.00 7742.21 14.80% 5.05% 0:00:09
100.00 7632.33 11.25% 3.20% 0:00:09
67.00 7372.04 10.65% 2.65% 0:00:10
45.00 7368.54 7.05% 1.30% 0:00:10
30.00 7275.41 6.55% 1.00% 0:00:10
20.00 7292.25 6.35% 0.65% 0:00:11
13.00 7231.36 5.70% 0.50% 0:00:11
8.70 7212.61 6.00% 0.15% 0:00:12
5.80 7212.61 5.80% 0.10% 0:00:12
3.90 7212.61 4.85% 0.00% 0:00:13
Annealing from 30000.00 to 3.90 over 1100000 steps:
Temperature Energy Accept Improve Elapsed Remaining
30000.00 7212.61 0:00:00
19178.67 18419.26 97.74% 46.29% 0:00:12 0:03:56
12260.71 23620.11 96.50% 45.88% 0:00:25 0:03:43
7838.14 26141.24 94.61% 44.86% 0:00:37 0:03:30
5010.83 17343.26 91.47% 43.25% 0:00:50 0:03:18
3203.37 20819.35 86.69% 40.98% 0:01:02 0:03:06
2047.88 21147.77 79.11% 37.03% 0:01:14 0:02:54
1309.19 13040.22 67.95% 31.49% 0:01:27 0:02:42
836.95 15584.89 55.69% 25.44% 0:01:40 0:02:30
535.05 9509.70 40.92% 18.07% 0:01:53 0:02:18
342.05 9488.45 28.66% 11.73% 0:02:05 0:02:05
218.67 9733.59 21.05% 8.07% 0:02:18 0:01:53
139.79 7186.61 14.95% 5.10% 0:02:31 0:01:40
89.37 6858.93 11.83% 3.39% 0:02:43 0:01:28
57.13 6866.74 8.94% 1.95% 0:02:56 0:01:15
36.52 6920.17 7.36% 1.23% 0:03:08 0:01:03
23.35 6843.20 6.56% 0.74% 0:03:21 0:00:50
14.93 6819.20 5.81% 0.37% 0:03:33 0:00:38
9.54 6801.84 5.28% 0.15% 0:03:46 0:00:25
6.10 6801.84 5.26% 0.08% 0:03:58 0:00:13
3.90 6801.84 5.07% 0.01% 0:04:10 0:00:00
6801 mile route:
New York City
Detroit
Columbus
Indianapolis
Chicago
San Francisco
San Jose
Los Angeles
San Diego
Phoenix
San Antonio
Austin
Houston
Fort Worth
Dallas
Memphis
Jacksonville
Charlotte
Baltimore
Philadelphia
|
|
Richard Wagner ( wagnerr@umich.edu ) 2 Sep 09 |