为什么在我的遗传算法中添加Crossover会给我带来更糟糕的结果？

Question

我已经实施了遗传算法来解决旅行商问题(TSP).当我只使用变异时,我找到了比添加交叉时更好的解决方案.我知道正常的交叉方法对TSP不起作用,所以我实现了Ordered Crossover和PMX Crossover方法,并且都遭受了糟糕的结果.

以下是我正在使用的其他参数:

突变:单一交换突变或倒置子序列突变(如Tiendil所述),突变率测试在1%和25%之间.

选择:轮盘赌轮选择

健身功能:1 /旅游距离

人口规模:测试100,200,500,我也运行GA 5次,以便我有各种起始种群.

停止条件:2500代

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

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

Answer 1

看起来你的交叉算子在新一代中引入了太多的随机性，因此你正在失去尝试改进糟糕解决方案的计算工作量。想象一下，爬山算法可以将给定的解决方案改进为其邻域的最佳解决方案，但遗传算法只能对几乎随机的总体（解决方案）做出有限的改进。

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