algorithm - 使用模拟退火的旅行商邻居选择的性能差异

Question

最近我尝试了几种不同的邻居选择算法来解决 Traveling Salesman Problem使用 Simulated Annealing :

1. 交换两个随机城市(例如 abcdefg -> abfdecg)
2. 将路由一分为二并交换两个子路由(例如 ab|cdefg -> cdefgab)
3. 交换两个随机相邻的城市(例如 abcdefg -> abdcefg)
4. 交换两个随机子路由(例如 a|bc|d|ef|g -> aefdbcg)
5. 反转随机子路线(例如 ab|cdef|g -> abfedcg)

事实证明，渐近性能存在巨大差异。 #5 结果是最好的，#2 结果根本不起作用。

为什么 #2 和 #5 有如此巨大的差异？两种算法一次改变两条边。在上面的示例中，#2 更改打破了 bc 并附加了 ga。 #5 将 bc 替换为 bf，并将 fg 替换为 cg。为什么 #2 根本不起作用，而 #5 是 5 个中最好的？

Answer 1

也许我不明白你的问题，但据我所知，TSP 要求在一个闭环中访问所有城市，所以你从哪个城市开始不会改变总距离。您的策略 #2 似乎是一个循环排列，即相同的循环但起点不同，所以难怪它没有任何改进!

策略 #5 效果很好，因为它可能会删除两条交叉边:

a--b f--e           a--b--f--e
|   X   |    -->    |        |
\--g c--d           \--g--c--d

请注意，#5 仅修改 2 条边。您的策略 #4 同时修改 4 条边，因此改进路线的可能性可能非常低。此外，策略#1 是#4 的特例，#3 是#5 的特例。