解决 Python 中的旅行商问题的 2-opt 算法

Question

我在 Python 中找不到 2-opt 算法的任何完整实现，因此我试图将缺失的部分添加到找到的代码中 here，我将在下面展示。

def two_opt(route):
     best = route
     improved = True
     while improved:
          improved = False
          for i in range(1, len(route)-2):
               for j in range(i+1, len(route)):
                    if j-i == 1: continue # changes nothing, skip then
                    new_route = route[:]
                    new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
                    if cost(new_route) < cost(best):  # what should cost be?
                         best = new_route
                         improved = True
          route = best
     return best

为了完成这段代码，我制作了一个小程序来从文本文件中提取 long/lat 坐标，并用每个点的成本填充邻接矩阵。完整代码，包括输入坐标和邻接矩阵的示例，可在 Code Review.

上找到

由于我不知道上面代码中的 cost 函数是什么，我的想法是计算出从一点到另一点的所有成本并将其放入邻接矩阵中： adj_matrix .这表示每个点与其他点的距离。

我尝试将我的 cost/adjacency 矩阵传递给函数以使用它，但是我无法根据我的邻接矩阵计算成本。

def main():
    # code to read from file
    # code to append co-ordinates to points and calculate the haversine distance between each point
    route = random.sample(range(10), 10)
    best = two_opt(route, adj_matrix)  # passing my adjacency matrix
    print(best)

ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

另一个 Python 2-opt 问题：

任何关于如何从邻接矩阵找到正确成本的建议都将不胜感激。

Answer 1

首先，一个adjacency matrix is typically a (0, 1)-matrix。你在这里所拥有的被不同地称为 cost、weight 或 distance matrix.

现在回答你的问题。

代价函数可以很简单：

def cost(cost_mat, route):
   return cost_mat[np.roll(route, 1), route].sum()

这里，np.roll() "rotates" 路由一个位置，方便与route一起使用，索引到成本矩阵中。 sum() 只是将各个路段的成本相加以计算路线的总成本。

（如果在某个时候您决定查看非对称 TSP，则需要确保 row/column 顺序与 cost_mat 的构造方式相匹配；对于欧几里得 TSP，这不会这很重要，因为成本矩阵是对称的。）

使用示例：

cost_mat = np.array([
   [0, 1, 2, 3],
   [1, 0, 4, 5],
   [2, 4, 0, 7],
   [3, 5, 7, 0],
])

route = np.array([2, 1, 3, 0])

print(cost(cost_mat, route))

Answer 2

2-opt 删除两条边并创建两条新边（假设成本矩阵是对称的），因此成本函数可以简化为只考虑变化的边。对于大型数组，这比遍历整个路由要快得多。

import numpy as np

def cost_change(cost_mat, n1, n2, n3, n4):
    return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


def two_opt(route, cost_mat):
    best = route
    improved = True
    while improved:
        improved = False
        for i in range(1, len(route) - 2):
            for j in range(i + 1, len(route)):
                if j - i == 1: continue
                if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
                    best[i:j] = best[j - 1:i - 1:-1]
                    improved = True
        route = best
    return best


if __name__ == '__main__':
    nodes = 1000
    init_route = list(range(nodes))
    print(init_route)
    cost_mat = np.random.randint(100, size=(nodes, nodes))
    cost_mat += cost_mat.T
    np.fill_diagonal(cost_mat, 0)
    cost_mat = list(cost_mat)
    best_route = two_opt(init_route, cost_mat)
    print(best_route)

Answer 3

我在 Python 中实现了 2-opt 算法。您可以使用 pip install py2opt 从 PyPi 服务器安装它。您还可以找到它的实现 here。使用此包，您可以计算最短距离（虽然不是全局最小距离）和最佳对应路线。

这是如何在多行中使用此库的示例。

from py2opt.routefinder import RouteFinder

cities_names = ['A', 'B', 'C', 'D']
dist_mat = [[0, 29, 15, 35], [29, 0, 57, 42], [15, 57, 0, 61], [35, 42, 61, 0]]
route_finder = RouteFinder(dist_mat, cities_names, iterations=5)
best_distance, best_route = route_finder.solve()

print(best_distance)
114
print(best_route)
['A', 'C', 'B', 'D']

我在这篇文章中更详细地解释了它：How to Solve the Traveling Salesman Problem — A Comparative Analysis

解决 Python 中的旅行商问题的 2-opt 算法

2-opt algorithm to solve the Travelling Salesman Problem in Python

python

algorithm

traveling-salesman

adjacency-matrix

python-3.x