# 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