1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| import numpy as np import math import random from copy import deepcopy import matplotlib.pyplot as plt
class Tsp(object): def __init__(self, city_num, times, steps, init_temperature, simulated_k): self.city_num = city_num self.distance = np.mat(np.zeros((city_num, city_num)), dtype=int) self.init_temperature = init_temperature self.times = times self.steps = steps self.simulated_k = simulated_k
self.x = list(range(self.city_num)) self.y = list(range(self.city_num)) self.now_path = list(range(self.city_num)) self.new_path = list(range(self.city_num)) self.best_path = list(range(self.city_num)) self.now_value = 0 self.new_value = 0 self.best_value = -1 self.path = [int(item)-1 for item in "1 8 38 31 44 18 7 28 6 37 19 27 17 43 30 36 46 33 20 47 21 32 39 48 5 42 24 10 45 35 4 26 2 29 34 41 16 22 3 23 14 25 13 11 12 15 40 9".split()]
self.best_time = -1
def read(self, path): print("Reading data...") with open(path, "r") as file: lines = file.readlines() self.x = [int(line.split()[1]) for line in lines] self.y = [int(line.split()[2]) for line in lines] x = self.x y = self.y for i in range(0, self.city_num): for j in range(0, self.city_num): self.distance[i, j] = round(math.sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))) print(self.distance) print("Read data done.")
def init_path(self): random.shuffle(self.now_path)
def value_of_path(self, path): value = 0 for (index, i) in enumerate(path): value += self.distance[path[index-1], i] return value
def get_neighbor(self): self.new_path = deepcopy(self.now_path) i_1, i_2 = random.randint(0, self.city_num-1), random.randint(0, self.city_num-1) self.new_path[i_1], self.new_path[i_2] = self.new_path[i_2], self.new_path[i_1]
def solve(self): self.init_path() self.now_value = self.value_of_path(self.now_path) print(self.now_value) temperature = self.init_temperature k = 0 for k in range(self.times): print("k: ", k, " now best: ", self.best_value) for n in range(self.steps): self.get_neighbor() self.new_value = self.value_of_path(self.new_path) if self.new_value < self.best_value or self.best_value == -1: self.best_value = self.new_value self.best_path = deepcopy(self.new_path) self.best_time = k print(self.best_value) if self.new_value < self.now_value or math.exp((self.now_value - self.new_value)/temperature)>random.random(): self.now_path = deepcopy(self.new_path) self.now_value = self.new_value temperature *= self.simulated_k
print("best: ", self.best_value)
def test(self): print(self.value_of_path(self.path))
def draw_path(self, path): x = [self.x[i] for i in path] y = [self.y[i] for i in path] x.append(self.x[path[0]]) y.append(self.y[path[0]]) plt.plot(x, y, "-o")
def draw_best(self): self.draw_path(self.path)
def draw(self): self.draw_path(self.best_path)
def show(self): plt.show()
if __name__ == "__main__": tsp = Tsp(48, 1000, 1000, 10000, 0.992) tsp.read("att48.tsp") tsp.solve() tsp.draw_best() tsp.draw() tsp.show()
|