0

我正在尝试使用差分进化解决旅行推销员问题。例如，如果我有向量：

[1, 4, 0, 3, 2, 5], [1, 5, 2, 0, 3, 5], [4, 2, 0, 5, 1, 3]

如何进行交叉和突变？我看到了类似 a+Fx(bc) 的东西，但我不知道如何使用它。

4

2 回答 2

0

我在寻找有关使用进化计算解决 TSP 问题的论文时遇到了这个问题。我一直在从事一个类似的项目，可以提供我编写的代码的修改版本。

对于突变，我们可以交换向量中的两个索引。我假设每个向量代表您将访问的节点顺序。

def swap(lst):

        n = len(lst)
        x = random.randint(0, n)
        y = random.randint(0, n)
        
        # store values to be swapped
        old_x = lst[x]
        old_y = lst[y]

        # do swap
        lst[y] = old_x
        lst[x] = old_y

    return lst

对于 TSP 问题的交叉情况，我们希望在我们的排列中保持值的一般顺序（我们想要一个带有位置偏差的交叉）。通过这样做，我们将以良好的排列保持良好的路径。因此，我认为单点交叉是最好的选择。

def singlePoint(parent1, parent2):

        point = random.randint(1, len(parent1)-2)

        def helper(v1, v2):
            # this is a helper function to save with code duplication

            points = [i1.getPoint(i) for i in range(0, point)]
            
            # add values from right of crossover point in v2
            # that are not already in points
            for i in range(point, len(v2)):
                pt = v2[i]
                if pt not in points:
                    points.append(pt)

            # add values from head of v2 which are not in points
            # this ensures all values are in the vector.
            for i in range(0, point):
                pt = v2[i]
                if pt not in points:
                    points.append(pt)

            return points
        
        # notice how I swap parent1 and parent2 on the second call
        offspring_1 = helper(parent1, parent2)
        offspring_2 = helper(parent2, parent1)

        return offspring_1, offspring_2

我希望这有帮助！即使您的项目已经完成，这也可以派上用场 GA 是解决优化问题的好方法。

于 2021-12-06T18:51:08.750 回答
-1

如果 F=0.6, a=[1, 4, 0, 3, 2, 5], b=[1, 5, 2, 0, 3, 5], c=[4, 2, 0, 5, 1, 3] 然后a+Fx(bc)=[-0.8, 5.8, 1.2, 0, 3.2, 6.2] 然后把数组中最小的数改为0，把数组中第二小的数改为1，以此类推。所以它返回 [0, 4, 2, 1, 3, 5]。这种方法在解决jsp问题时效率低下。

于 2021-07-07T12:27:41.997 回答