# Tabu search for Traveling Salesman, 200 cities # this version scores each tour completely from scratch, # which is very inefficient. Each generation takes about # a second on my computer. 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(self, sol): """ computes every neighbor of "sol" formed by picking two cities and reverse the whole block of the tour in between them """ for indices in itertools.combinations(range(1,len(sol)),2): # slicing magic new_points = sol[:indices[0]] + sol[indices[0]:indices[1]+1][::-1] + sol[indices[1]+1:] yield new_points, 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, move in tsp.neighborhood(sol): # if taboo[move] > generation, then this move is still taboo and # we can't do it if taboo[move] > generation: continue # if we can do it, then get its score, and see if it's the best # thing in the neighborhood pl = tsp.score(s) 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