algorithm - 为什么将交叉添加到我的遗传算法中会给我带来更差的结果？

Question

我已经实现了一种遗传算法来解决旅行商问题 (TSP)。当我只使用突变时，我找到了比添加交叉时更好的解决方案。我知道普通的交叉方法对 TSP 不起作用，所以我同时实现了 Ordered Crossover和 PMX Crossover方法，并且都遭受不良结果。

这是我使用的其他参数:

突变:单交换突变或反转子序列突变 (as described by Tiendil here)，突变率测试在 1% 到 25% 之间。

选择:轮盘赌选择

适应度函数:1/游览距离

种群大小:测试了100、200、500，我也跑了5次GA，这样我就有了各种不同的起始种群。

停止条件:2500代

对于相同的 26 个点的数据集，我通常使用具有高突变率的纯突变得到大约 500-600 距离的结果。添加交叉时，我的结果通常在 800 距离范围内。另一个令人困惑的事情是，我还实现了一个非常简单的爬山算法来解决问题，当我运行 1000 次(比运行 GA 5 次更快)时，我得到的结果大约是 410-450 距离，我希望使用 GA 获得更好的结果。

关于添加交叉时为什么我的 GA 表现更差的任何想法？为什么它的性能比简单的 Hill-Climb 算法差得多，后者应该卡在局部最大值上，因为一旦找到局部最大值就无法探索？

Answer 1

看起来您的交叉运算符在新一代中引入了太多随机性，因此您在尝试改进不良解决方案时正在浪费计算精力。想象一下，爬山算法可以将给定的解决方案改进到其邻域的最佳解决方案，但您的遗传算法只能对几乎随机的种群(解决方案)进行有限的改进。

还值得一提的是，GA 并不是解决 TSP 的最佳工具。无论如何，您应该看看如何实现它的一些示例。例如http://www.lalena.com/AI/Tsp/