python - 针对 TSP 问题建议的 GA 运算符？

Question

我正在构建一个遗传算法来解决旅行商问题。不幸的是，我在突变出它们并获得更好的结果之前达到了可以维持一千多代的高峰。在这种情况下，哪些交叉和变异算子通常做得很好？

Answer 1

有序突变和有序交叉（参见这篇文章）。标准的变异和交叉操作通常会导致无效的解决方案（即路线中的重复和/或缺失城市）。

最近有一个类似的问题。

如果您有兴趣比较您的实现的性能，我有一个使用有序交叉和突变实现 TSP 的 Java 小程序。

Answer 2

如果您的问题是峰值仍然存在超过一千代，那么问题可能不在于交叉和变异算子。你可能没有向你的种群引入或保持足够的变异：我会检查交叉、突变和一代到下一代的幸存者的比例，并可能提高突变的比例。

Answer 3

你能澄清一下吗

“不幸的是，我达到了可以维持一千多代的高峰，然后才变异出来并获得更好的结果”？

您可以检查交叉运算符，以确保子染色体中没有重复节点。这些交叉算子中有几个是阶交叉（OX）和边缘交叉算子。

突变可以像简单地交换单个染色体中的两个位置一样简单。

顺便说一句，既然您已经标记了“python”，请看一下Pyevolve，它也有一个 TSP 示例。