TSP 遗传算法 - 路径表示和相同的游览问题
TSP Genetic Algorithm - path representation and identical tour problem
我们正在实施路径表示，以使用遗传算法解决我们的旅行商问题。然而，我们想知道如何解决这样的问题，即我们的个人可能有相同的旅行，但路径表示将其识别为不同的个人。一个例子：
每个个体组成一个数组，数组中的元素是依次访问过的城市
Individual 1:
[1 2 3 4 5]
Individual 2:
[4 5 1 2 3]
可以看到1和2的游览其实是一样的，只是"starting"位置不同
我们看到了这个问题的一些解决方案，但我们想知道哪个是最好的，或者是否有解决这个问题的最佳实践 literature/experiments/....
解决方案 1
Sort each individual to see if the individuals are identical:
1. pick an individual
2. shift the elements by 1 element to the right (at the end of the array, elements are placed at the beginning of the array)
3. check if this shift now matches an individual
4. if not, repeat steps 3 to 4
解决方案 2
1. At the start if the simulations, choose a fixed starting point of the cities.
2. If the fixed starting point would change (mutation, recombination,...) then
3. Shift the array so that chosen starting point is back on first index.
解决方案 3
1. Use the adjacency representation to check which individuals are identical.
2. Pass this information on to the path representation.
3. This is used to "correct" the individuals.
解决方案 1 和 2 似乎很耗时，尽管 2 可能需要更少的计算时间。解决方案 3 需要不断地从一种表示切换到另一种表示。
然后还有一个问题，在我们的示例中，可以通过两种方式阅读游览：
[1 2 3 4 5]
与
相同
[5 4 3 2 1]
同样，是否有解决此问题的最佳实践？
由于需要遍历每一个城市，return到起点城市，所以直接固定起点就可以了。这完全解决了您的移动等效游览问题。
对于镜像游览的另一个不太重要的问题，您可以首先按成本对个人进行排序（您可能已经这样做了），然后使用简单的回文检查算法检查具有相同成本的任何一对游览。
我们正在实施路径表示，以使用遗传算法解决我们的旅行商问题。然而，我们想知道如何解决这样的问题，即我们的个人可能有相同的旅行，但路径表示将其识别为不同的个人。一个例子：
每个个体组成一个数组，数组中的元素是依次访问过的城市
Individual 1:
[1 2 3 4 5]
Individual 2:
[4 5 1 2 3]
可以看到1和2的游览其实是一样的，只是"starting"位置不同
我们看到了这个问题的一些解决方案，但我们想知道哪个是最好的，或者是否有解决这个问题的最佳实践 literature/experiments/....
解决方案 1
Sort each individual to see if the individuals are identical:
1. pick an individual
2. shift the elements by 1 element to the right (at the end of the array, elements are placed at the beginning of the array)
3. check if this shift now matches an individual
4. if not, repeat steps 3 to 4
解决方案 2
1. At the start if the simulations, choose a fixed starting point of the cities.
2. If the fixed starting point would change (mutation, recombination,...) then
3. Shift the array so that chosen starting point is back on first index.
解决方案 3
1. Use the adjacency representation to check which individuals are identical.
2. Pass this information on to the path representation.
3. This is used to "correct" the individuals.
解决方案 1 和 2 似乎很耗时，尽管 2 可能需要更少的计算时间。解决方案 3 需要不断地从一种表示切换到另一种表示。
然后还有一个问题，在我们的示例中，可以通过两种方式阅读游览：
[1 2 3 4 5]
与
相同[5 4 3 2 1]
同样，是否有解决此问题的最佳实践？
由于需要遍历每一个城市，return到起点城市，所以直接固定起点就可以了。这完全解决了您的移动等效游览问题。
对于镜像游览的另一个不太重要的问题，您可以首先按成本对个人进行排序（您可能已经这样做了），然后使用简单的回文检查算法检查具有相同成本的任何一对游览。