genetic-algorithm - 旅行推销员的启发式方法

Question

我正在研究进化优化，在这个项目中，我需要针对旅行商问题的启发式方法。在这种情况下，遗传算法，我们应用小的突变，并希望在未来的某个地方事情会变得更好。因此，我正在寻找简单的启发式方法来转换可能导致改进的解决方案。

感谢您的任何建议

Answer 1

我想推荐的一个参考是R's TSP package。（即使您不使用 R，也请仔细研究一下。） 他们在 TSP 上的小插图非常出色，并且有许多基于动态编程的技巧，您可以尝试改进您的 GA 实现。

小插曲的第 2.4 节特别讨论了您可以合并的Tour 构建启发式方法。从中引用：

最近邻算法：遵循一个非常简单的贪心程序：该算法从包含随机选择的城市的旅游开始，然后总是将最近的尚未访问的城市添加到旅游中的最后一个城市。当所有城市都在游览时，算法停止。

该算法的一个扩展是以每个城市为起点重复该算法，然后返回找到的最佳游览。这种启发式称为重复最近邻。

插入算法。从包含任意城市的游览开始，然后在每个步骤中选择一个尚未参加游览的城市。将该城市插入到两个连续城市i 和j 之间的现有旅游中，从而使插入成本（即，旅游长度的增加）最小化。当所有城市都在游览时，算法停止。

最近的插入在每一步中，都会选择城市 k 作为距离游览中的城市最近的城市。

最远插入在每一步中，都会选择城市 k 作为距离旅行中任何城市最远的城市。

最便宜的插入在每一步中都会选择城市 k，以使插入新城市的成本最小。

您可以在小插图中找到更多细节和其他技术。

Answer 2

我认为您正在寻找旅行改进启发式，我可以为您建议Lin-Kernighan算法。但是这个算法对你来说可能太难了。因此，您可以研究2-opt或 3-opt 算法。