Simulated Annealing and Traveling Salesman Problem

Previously, Graph Theory Basics and Graph Theory Basics with matplotlib Animation, etc. I wrote the article, but I tried a method using "Simulated Annealing" as an approximate solution to the "Traveling Salesman Problem", which is one of the difficult problems that are considered to be NP-hard in graph theory. I tried it.

Traveling salesman problem

"The traveling salesman problem (TSP) is the total travel cost of a traveling circuit that travels through all vertices exactly once and returns to the starting point, given a set of vertices and a travel cost between each vertex. Is a combinatorial optimization problem that seeks the smallest one.

Simulated annealing method

Simulated Annealing (SA) is a method of solving a global optimization problem named after "simulated annealing" in metallurgy. Start the search with a high "temperature" that allows you to escape immediately even if you fall into a local solution, and gradually lower the "temperature" to search for a global optimal solution.

Prefectural office location data of prefectures

Data from Graph Theory Basics and Graph Theory Basics with matplotlib animation As an example, let's solve the traveling salesman problem.

import urllib.request
url = 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/location.txt'
urllib.request.urlretrieve(url, 'location.txt') #Download data
('location.txt', <http.client.HTTPMessage at 0x7f9f4e7685c0>)
import pandas as pd
japan = pd.read_csv('location.txt')
japan
Town Longitude Latitude
0 Sapporo 43.06417 141.34694
1 Aomori 40.82444 140.74000
2 Morioka 39.70361 141.15250
3 Sendai 38.26889 140.87194
4 Akita 39.71861 140.10250
5 Yamagata 38.24056 140.36333
6 Fukushima 37.75000 140.46778
7 Mito 36.34139 140.44667
8 Utsunomiya 36.56583 139.88361
9 Maebashi 36.39111 139.06083
10 Saitama 35.85694 139.64889
11 Chiba 35.60472 140.12333
12 Tokyo 35.68944 139.69167
13 Yokohama 35.44778 139.64250
14 Niigata 37.90222 139.02361
15 Toyama 36.69528 137.21139
16 Kanazawa 36.59444 136.62556
17 Fukui 36.06528 136.22194
18 Kofu 35.66389 138.56833
19 Nagano 36.65139 138.18111
20 Gifu 35.39111 136.72222
21 Shizuoka 34.97694 138.38306
22 Nagoya 35.18028 136.90667
23 Tsu 34.73028 136.50861
24 Otsu 35.00444 135.86833
25 Kyoto 35.02139 135.75556
26 Osaka 34.68639 135.52000
27 Kobe 34.69139 135.18306
28 Nara 34.68528 135.83278
29 Wakayama 34.22611 135.16750
30 Tottori 35.50361 134.23833
31 Matsue 35.47222 133.05056
32 Okayama 34.66167 133.93500
33 Hiroshima 34.39639 132.45944
34 Yamaguchi 34.18583 131.47139
35 Tokushima 34.06583 134.55944
36 Takamatsu 34.34028 134.04333
37 Matsuyama 33.84167 132.76611
38 Kochi 33.55972 133.53111
39 Fukuoka 33.60639 130.41806
40 Saga 33.24944 130.29889
41 Nagasaki 32.74472 129.87361
42 Kumamoto 32.78972 130.74167
43 Oita 33.23806 131.61250
44 Miyazaki 31.91111 131.42389
45 Kagoshima 31.56028 130.55806
46 Naha 26.21250 127.68111

Here is a diagram of the positional relationship between cities.

%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 8))
plt.scatter(japan['Latitude'], japan['Longitude'])
for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
    plt.text(x, y, city, alpha=0.5, size=12)
plt.grid()

output_3_0.png

simanneal package

Install the package simanneal for solving Simulated Annealing.

!pip install simanneal

As an example, this package already has a class for solving the traveling salesman problem, so you can use it as it is.

from simanneal import Annealer
class TravellingSalesmanProblem(Annealer):

    """Test annealer with a travelling salesman problem.
    """

    # pass extra data (the distance matrix) into the constructor
    def __init__(self, state, distance_matrix):
        self.distance_matrix = distance_matrix
        super(TravellingSalesmanProblem, self).__init__(state)  # important!

    def move(self):
        """Swaps two cities in the route."""
        # no efficiency gain, just proof of concept
        # demonstrates returning the delta energy (optional)
        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):
        """Calculates the length of the route."""
        e = 0
        for i in range(len(self.state)):
            e += self.distance_matrix[self.state[i-1]][self.state[i]]
        return e

Distance matrix

The distance matrix can be calculated like this using scipy, for example.

import numpy as np
from scipy.spatial import distance

mat = japan[['Latitude', 'Longitude']].values
dist_mat = distance.cdist(mat, mat, metric='euclidean') #Euclidean distance

In order to use it with simanneal, it seems that it has to be formatted like this.

distance_matrix = {}
for i, town in enumerate(japan['Town']):
    if town not in distance_matrix.keys():
        distance_matrix[town] = {}
    for j, town2 in enumerate(japan['Town']):
        distance_matrix[town][town2] = dist_mat[i][j]

Initial set

Arrange the cities in a random order and call it the "initial circuit".

import random
init_state = list(japan['Town'])
random.shuffle(init_state)

Set it in a class that solves the traveling salesman problem.

tsp = TravellingSalesmanProblem(init_state, distance_matrix)

Start calculation

tsp.set_schedule(tsp.auto(minutes=0.2))
tsp.copy_strategy = "slice"
state, e = tsp.anneal()

Calculation result

The circuit has been output.

state
['Otsu',
 'Kyoto',
 'Nara',
 'Osaka',
 'Kobe',
 'Tottori',
 'Matsue',
 'Hiroshima',
 'Yamaguchi',
 'Fukuoka',
 'Saga',
 'Nagasaki',
 'Naha',
 'Kagoshima',
 'Miyazaki',
 'Kumamoto',
 'Oita',
 'Matsuyama',
 'Kochi',
 'Okayama',
 'Takamatsu',
 'Tokushima',
 'Wakayama',
 'Tsu',
 'Gifu',
 'Nagoya',
 'Shizuoka',
 'Kofu',
 'Maebashi',
 'Niigata',
 'Akita',
 'Aomori',
 'Sapporo',
 'Morioka',
 'Sendai',
 'Yamagata',
 'Fukushima',
 'Utsunomiya',
 'Mito',
 'Chiba',
 'Yokohama',
 'Tokyo',
 'Saitama',
 'Nagano',
 'Toyama',
 'Kanazawa',
 'Fukui']

Circuit from the specified city

Make the obtained circuit, for example, a circuit starting from Tokyo.

while state[0] != 'Tokyo':
        state = state[1:] + state[:1]  # rotate NYC to start

print()
print("%i mile route:" % e)
print(" ➞  ".join(state))
56 mile route:
Tokyo ➞  Saitama ➞  Nagano ➞  Toyama ➞  Kanazawa ➞  Fukui ➞  Otsu ➞  Kyoto ➞  Nara ➞  Osaka ➞  Kobe ➞  Tottori ➞  Matsue ➞  Hiroshima ➞  Yamaguchi ➞  Fukuoka ➞  Saga ➞  Nagasaki ➞  Naha ➞  Kagoshima ➞  Miyazaki ➞  Kumamoto ➞  Oita ➞  Matsuyama ➞  Kochi ➞  Okayama ➞  Takamatsu ➞  Tokushima ➞  Wakayama ➞  Tsu ➞  Gifu ➞  Nagoya ➞  Shizuoka ➞  Kofu ➞  Maebashi ➞  Niigata ➞  Akita ➞  Aomori ➞  Sapporo ➞  Morioka ➞  Sendai ➞  Yamagata ➞  Fukushima ➞  Utsunomiya ➞  Mito ➞  Chiba ➞  Yokohama

Illustrated

plt.figure(figsize=(10, 10))
Xs = []
Ys = []
for i in range(len(state)):
    Xs.append(list(japan[japan['Town'] == state[i]].iloc[:, 2])[0])
    Ys.append(list(japan[japan['Town'] == state[i]].iloc[:, 1])[0])

plt.plot(Xs, Ys)
for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
    plt.text(x, y, city, alpha=0.5, size=12)

output_14_0.png

I see. It doesn't seem to be the optimal solution, but it seems that something close to it has been obtained.

Recommended Posts

Simulated Annealing and Traveling Salesman Problem
Solve a simple traveling salesman problem using a Boltzmann machine with simulated annealing
About the traveling salesman problem
About the Ordered Traveling Salesman Problem
I tried paiza's campaign problem. (Traveling salesman problem)
Python: I tried the traveling salesman problem
Solve the traveling salesman problem with OR-Tools
Traveling salesman problem practice collection ③ ~ Non-random map edition ~
I tried to implement the traveling salesman problem
Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)
Solve the Python asymmetric traveling salesman problem with a branch and bound method
Combinatorial optimization-typical problem-traveling salesman problem