This example was adapted from https://github.com/perrygeo/simanneal/blob/master/examples/salesman.py, which applies (single) SA to the TSP.
In [1]:
from __future__ import print_function
import math
import random
from pycsa import CoupledAnnealer
try:
xrange
except NameError:
xrange = range
Let's create a set of cities to use for TSP.
In [2]:
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)
}
Now's lets define the function to calculate distances between cities and create a distance matrix.
In [3]:
def distance(a, b):
"""
Helper function to calculate the 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
# Create the distance matrix between the cities.
distance_matrix = {}
for ka, va in cities.items():
distance_matrix[ka] = {}
for kb, vb in cities.items():
if kb == ka:
distance_matrix[ka][kb] = 0.0
else:
distance_matrix[ka][kb] = distance(va, vb)
Next we have to define the target_function, i.e. the cost function to be minimized, and the probe_function, which will randomly update the current state at each annealing process.
In [4]:
def probe(positions, tgen):
"""
Swap two cities in the route.
Note that `tgen` (the generation temperature) is ignored here.
In general, you can use `tgen` to adjust the variance of
the probing jumps as the algorithm progress.
"""
a = random.randint(0, len(positions) - 1)
b = random.randint(0, len(positions) - 1)
positions[a], positions[b] = positions[b], positions[a]
return positions
def target(positions):
"""
Calculates the length of the route.
"""
e = 0
for i in xrange(len(positions)):
e += distance_matrix[positions[i-1]][positions[i]]
return e
Okay let's give it a run!
In [9]:
n_annealers = 10 # the number of coupled annealers
init_state = list(cities.keys())
random.shuffle(init_state)
# Initialize the CSA process.
annealer = CoupledAnnealer(
target,
probe,
initial_state=[init_state] * n_annealers,
steps=100, # You probably want to set this a lot higher, like 10,000
processes=1, # Only use more than 1 process if the target function is costly to compute
n_annealers=n_annealers,
tacc_initial=1000.0,
verbose=1)
# Beging the annealing.
annealer.anneal()
In [10]:
# Get the best result from all `n_annealers`.
energy, state = annealer.get_best()
# Slide the list of cities until NYC is first.
while state[0] != 'New York City':
state = state[1:] + state[:1]
print()
print("%i mile route:" % energy)
for city in state:
print("\t", city)