Travelling Salesman (black-box optimization)

Pyhopper’s flexibility allows us to implement heuristics for combinatorial optimization problems such as for the Travelling Salesman Problem (TSP) with few lines of code. For instance, the 2-opt heuristic is a well known search algorithm for the TSP:

import numpy as np
import pyhopper
import matplotlib.pyplot as plt

N = 50
cities = np.random.default_rng(123456).uniform(-10, 10, size=(N, 2))

def tsp_objective(solution):
    order = solution["order"]
    p = cities[order]
    cost = np.sum(np.linalg.norm(p[:-1] - p[1:], axis=1))
    cost += np.linalg.norm(p[0] - p[-1])  # make a roundtrip
    return cost

def two_opt(order):
    order = np.copy(order)  # Don't overwrite current best order
    i, j = np.random.default_rng().integers(0, N, 2)
    # Swap city i with city j
    temp = order[i]
    order[i] = order[j]
    order[j] = temp
    return order

search = pyhopper.Search(
    {
        "order": pyhopper.custom(
            seeding_fn=lambda: np.random.default_rng().permutation(N),
            mutation_fn=two_opt,
        )
    }
)
solution = search.run(
    tsp_objective,
    "min",
    runtime="30s",
)
# Let's plot the cities' location
plt.scatter(cities[:, 0], cities[:, 1], marker="o", color="black")

order = solution["order"]
# Arrange cities in solution's ordering and make it a roundtrip
x = [cities[order[i], 0] for i in range(N)] + [cities[order[0], 0]]
y = [cities[order[i], 1] for i in range(N)] + [cities[order[0], 1]]
plt.plot(x, y)
plt.show()