from __future__ import print_function
from simanneal import Annealer # the package we use for the annealing (https://github.com/perrygeo/simanneal)
import matplotlib.pyplot as plt
from IPython.display import Image
from collections import defaultdict
import math
import random
Image(filename='aufgabe7.PNG')
def distance(a, b):
return(((((b[0] - a[0] )**2) + ((b[1] - a[1])**2) )**0.5))
def set_random_cities(city_names):
cities = dict()
for val in l_cities:
x,y = random.randrange(20, 100, 1), random.randrange(20, 100, 1)
cities[val] = (x,y)
return(cities)
class TravellingSalesmanProblem(Annealer):
def __init__(self, state, distance_matrix):
self.distance_matrix = distance_matrix
super(TravellingSalesmanProblem, self).__init__(state)
def move(self):
initial_energy = self.energy()
a = random.randint(0, len(self.state) - 1)
b = random.randint(0, len(self.state) - 1)
self.state[a], self.state[b] = self.state[b], self.state[a]
return self.energy() - initial_energy
def energy(self):
e = 0
for i in range(len(self.state)):
e += self.distance_matrix[self.state[i-1]][self.state[i]]
return e
l_cities = ('Graz','Wien','Salzburg','Innsbruck','Bregenz','Klagenfurt','Eisenstadt','Linz','Sankt Poelten')
cities = set_random_cities(l_cities)
init_state = list(cities)
random.shuffle(init_state)
distance_matrix = defaultdict(dict)
for ka, va in cities.items():
for kb, vb in cities.items():
distance_matrix[ka][kb] = 0.0 if kb == ka else distance(va, vb)
tsp = TravellingSalesmanProblem(init_state, distance_matrix)
tsp.set_schedule(tsp.auto(minutes=0.2))
tsp.copy_strategy = "slice"
state, e = tsp.anneal()
while state[0] != 'Graz':
state = state[1:] + state[:1] # rotate NYC to start
print()
print("%i LE route:" % e)
print(" ➞ ".join(state))
Temperature Energy Accept Improve Elapsed Remaining
Temperature Energy Accept Improve Elapsed Remaining
Graz ➞ Klagenfurt ➞ Wien ➞ Innsbruck ➞ Salzburg ➞ Linz ➞ Eisenstadt ➞ Sankt Poelten ➞ Bregenz
##Plotten des Weges
for city in cities:
x = cities.get(city)[0]
y = cities.get(city)[1]
plt.scatter(x,y)
routefx = []
routefy = []
for st in state:
x = cities.get(st)[0]
routefx.append(x)
y = cities.get(st)[1]
routefy.append(y)
plt.plot(routefx,routefy, color ="gray")