我已经实施了遗传算法来解决旅行商问题（TSP）。当我只使用突变时，我会找到比添加交叉时更好的解决方案。我知道普通的交叉方法不适用于 TSP，所以我同时实现了有序交叉和PMX 交叉方法，但结果都不好。
以下是我正在使用的其他参数：
突变：单交换突变或反向子序列突变（如 Tiendil 所述），突变率测试在 1% 和 25% 之间。
选择：轮盘赌选择
健身功能：1/行程距离
人口规模：测试了 100、200、500，我也运行了 GA 5 次，这样我就有了各种起始人口。
停止条件：2500代
对于相同的 26 点数据集，我通常使用具有高突变率的纯突变得到大约 500-600 距离的结果。添加交叉时，我的结果通常在 800 距离范围内。另一个令人困惑的事情是，我还实现了一个非常简单的爬山算法来解决这个问题，当我运行 1000 次（比运行 GA 5 次更快）我得到大约 410-450 距离的结果，我希望使用 GA 获得更好的结果。
关于为什么我添加交叉时我的 GA 表现更差的任何想法？为什么它的性能比简单的爬山算法差得多，因为一旦找到局部最大值就无法探索，它应该卡在局部最大值上？
看起来您的交叉算子在新一代中引入了过多的随机性，因此您正在失去试图改进不良解决方案的计算工作。想象一下，爬山算法可以将给定的解决方案改进为最好的邻域，但您的遗传算法只能对几乎随机的群体（解决方案）做出有限的改进。
值得一提的是，GA 并不是解决 TSP 的最佳工具。无论如何，您应该看一些如何实现它的示例。例如http://www.lalena.com/AI/Tsp/
通过轮盘赌选择，您将把坏父母引入其中。如果您想以某种方式权衡轮子以选择一些更好的父母，这可能会有所帮助。
请记住，您的大部分人口可能是不称职的父母。如果您根本没有考虑父母选择的权重，那么您很有可能会不断培育出超出池的不良解决方案。对您的选择进行加权以更频繁地选择更好的父母，并通过添加随机性来使用突变来纠正过于相似的池。
您可以尝试将精英主义引入您的选择过程。精英主义意味着在进行任何选择之前，保留种群中适应度最高的两个个体并将其复制到新种群中。精英主义完成后，选择继续正常进行。这样做意味着，无论轮盘赌选择了哪个父母，或者他们在交叉过程中产生了什么，都将始终保留两个最好的个体。这可以防止新人口失去健康，因为它的两个最佳解决方案不会比上一代更差。
添加交叉时结果更差的一个原因可能是它没有做它应该做的 - 结合两个人的最佳特征。尝试用低交叉概率可能是？人口多样性可能是这里的一个问题。莫里森和德容在他们的《人口多样性测量》一书中提出了一种新的多样性测量方法。使用该衡量标准，您可以看到您的人口多样性如何在几代人中发生变化。看看当你使用交叉或不使用交叉时它有什么不同。
此外，您的 OX 或 PMX 实施中可能存在一些小错误/遗漏的细节。也许你忽略了什么？顺便说一句，您可能想尝试边缘重组交叉算子吗？（Pyevolve有一个实现）。
为了提出“创新”策略，遗传算法通常使用交叉来组合不同候选解决方案的特长，以便快速探索搜索空间并找到更高适应度的新策略——这与人类智能的内部运作完全不同（这就是为什么我们从来没有真正“发明”过任何东西，而只是把我们已经知道的东西混在一起是有争议的）。
通过这样做（随机组合不同的个体）交叉不会保持对称性或顺序，并且当问题高度依赖于某种对称性或染色体中基因的顺序（如在您的特定情况下）时，确实很可能采用交叉将导致更糟糕的结果。正如您提到自己的那样，众所周知，交叉对旅行推销员不起作用。
值得强调的是，如果没有交叉遗传算法的这种打破对称性的壮举，将无法填补进化的“壁龛”（通常需要缺乏对称性）——这就是为什么交叉（在所有变体中）在绝大多数情况下本质上很重要的案例。