在 python 中为 2OPT 生成所有邻居

Question

我正在尝试针对无向旅行商问题实施 2opt 优化算法。对于给定的城市：

cities = [[ 72.06557466,   5.73765812],
   [ 94.50272578,  68.95162393],
   [ 58.53952609,  15.12518299],
   [ 94.64599891,  34.65906808],
   [ 62.42311036,  45.8430048 ],
   [ 24.73697454,   4.4159545 ],
   [ 15.71071819,  81.27575127],
   [ 65.65743227,  54.90239983],
   [  5.07828178,  47.34845887],
   [ 88.98592652,  48.14959719]]

我对通用算法的理解是，从随机游开始（在本例中为 10 个节点）：

solution = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我需要为此解决方案生成所有 2opt 邻居（通过删除两条边并引入两条新边）。然后，计算每个这样的相邻解决方案的成本。

def total_length( nodes, solution ):
    objective = distance( solution[-1], solution[0])
    for index in range(0, len(solution)-1):
        objective += distance(solution[index], solution[index+1])
    return objective

其中距离函数是两点之间的欧式距离

然后选择最好的（成本最低的）。比如这个周边游：

new_solution = [6, 8, 7, 9, 0, 1, 2, 3, 4, 5]

在 python 中，对于给定的解决方案，有什么简单的方法可以遍历所有相邻的游览（避免冗余）？

Answer 1

你不需要遍历所有游览（我不确定你所说的"neighboring tours"是什么意思）；您需要遍历现有游览中的所有对边。由于您已将游览存储为一系列节点，因此您只需要遍历节点，例如：

for i in range(0, len(solution)-3):
    for j in range(i+2, len(solution)-1):
        # evaluate 2-opt on edge (solution[i],solution[i+1]) and 
        # edge (solution[j],solution[j+1])

请注意，两条边不能共享一个节点，这就是 j 循环从 i+2 开始的原因。另请注意，当 j = =len(solution)-1.

时，(solution[j],solution[j+1]) 应解释为 (solution[j],solution[0])

在 python 中为 2OPT 生成所有邻居

Generate all neighbors for 2OPT in python

python

algorithm

optimization

mathematical-optimization

traveling-salesman