# Tabu search for Traveling Salesman, 200 cities # this version scores a new tour by just subtracting # the two disappearing edges and adding the two new # edges import math import random random.seed(1) import itertools from collections import defaultdict def euclidean_distance(pt1, pt2): return math.sqrt((pt1[0] - pt2[0]) ** 2 + (pt1[1] - pt2[1]) ** 2) class TSP: """ This is a class that represents a traveling salesman problem (not a solution, a whole problem) """ def __init__(self, points): self.points = set(points) def random_solution(self): """ returns a random solution (the point of the TSP in a random order) """ return random.sample(list(self.points), len(self.points)) def random_greedy_solution(self): """ returns a greedy solution starting at a random point """ start_point = random.choice(list(self.points)) solution = [start_point] points_left = set(self.points) points_left.remove(start_point) while len(points_left) > 0: closest = min( points_left, key=lambda p: euclidean_distance(p, solution[-1]) ) solution.append(closest) points_left.remove(closest) return solution def score(self, sol): """ scores a tour, from scratch """ return sum( euclidean_distance(sol[i], sol[i + 1]) for i in range(len(sol) - 1) ) + euclidean_distance(sol[-1], sol[0]) def neighborhood_with_score(self, sol, old_score): """ computes every neighbor of "sol" formed by picking two cities and reverse the whole block of the tour in between them for each new neighbor, it also computes what its score is and returns that """ for indices in itertools.combinations(range(1,len(sol)),2): score_change = 0 new_points = sol[:indices[0]] + sol[indices[0]:indices[1]+1][::-1] + sol[indices[1]+1:] score_change -= euclidean_distance(sol[indices[0]-1], sol[indices[0]]) score_change -= euclidean_distance(sol[indices[1]], sol[(indices[1]+1) % len(sol)]) score_change += euclidean_distance(sol[indices[0]-1], sol[indices[1]]) score_change += euclidean_distance(sol[indices[0]], sol[(indices[1]+1) % len(sol)]) yield new_points, old_score + score_change, indices # form a random TSP problem points = [(random.random(), random.random()) for _ in range(200)] tsp = TSP(points) # track best sol and best score best_sol = None best_score = None # taboo_time = 100 means we won't allow swap the block of cities between i and j # if we've already done that in the last 100 moves taboo_time = 100 # a "defaultdict" is a really use special kind of dictionary that you give a # type, in this case "int", and if you try to access a key that doesn't exist # then it will default to 0 taboo = defaultdict(int) # random start solution sol = tsp.random_solution() generation = 0 # repeat until you get bored while True: generation += 1 # get score of current solution, save if best length = tsp.score(sol) if best_score is None or best_score > length: best_score = length best_sol = sol if generation > 1: print(f"\t\tBest ever score: {best_score}") # set up variables steepest_best_sol = None steepest_best_score = None steepest_move = None # for every possible move (every sol in the neighborhood) for s, pl, move in tsp.neighborhood_with_score(sol, length): # if taboo[move] > generation, then this move is still taboo and # we can't do it. BUT, if it's taboo and its score is still better # than anything we've ever seen before, go anyway if move in taboo and taboo[move] > generation and not pl < best_score: continue # if we can do it, then get its score, and see if it's the best # thing in the neighborhood if steepest_best_score is None or pl < steepest_best_score: steepest_best_sol = s steepest_best_score = pl steepest_move = move # move to the best thing in the neighborhood, and make that move # taboo for a while sol = steepest_best_sol print(f"Gen {generation} -- Cur score: {steepest_best_score}", end="") taboo[steepest_move] = generation + taboo_time