在python中为2OPT生成所有邻居 [英] Generate all neighbors for 2OPT in python

问题描述

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

I am trying to implement to the 2opt optimization algorithm for the undirected Traveling Salesman Problem. For given cities:

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个节点)开始:

My understanding for the general algorithm is that starting from a random tour (in this example 10 nodes):

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

我需要为此解决方案生成所有2opt邻居(通过删除两个边缘并引入两个新边缘).然后，计算每个此类相邻解决方案的成本.

I need to generate all the 2opt neighbors for this solution (by removing two edges and introducing two new edges). Then, compute the cost for each such neighboring solution.

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

距离函数是两点之间的欧几里得距离.

Where the distance function is the Euclidian distance between the two points.

然后选择最佳(最低成本).例如，此相邻的游览:

Then choosing the best (lowest cost). For example, this neighboring tour:

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

对于给定的解决方案，用python遍历所有相邻游览(避免冗余)的简便方法是什么?

What would be an easy-way in python to iterate over all the neighboring tours (avoiding redundancy) for a given solution?

推荐答案

您不需要遍历所有行程(我不确定您所说的相邻行程"是什么意思)；您需要遍历现有导览中的所有对边.由于您已将游览存储为一系列节点，因此只需要遍历这些节点即可，例如:

You don't need to iterate over all tours (I'm not sure what you mean by "neighboring tours"); you need to iterate over all pairs of edges in the existing tour. Since you have stored the tour as a sequence of nodes, you just need to iterate through the nodes, something like:

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]).

Note that the two edges can't share a node, which is why the j loop starts at i+2. Also note that (solution[j],solution[j+1]) should be interpreted as (solution[j],solution[0]) when j = =len(solution)-1.

这篇关于在python中为2OPT生成所有邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！