如何改进TSP的遗传算法？

Question

这是我的遗传算法，一步一步：

1. 随机生成两个初始种群，并从两个种群中选择最适合的旅游。

2. 执行一个有序的交叉，它从第一个fit巡更中随机选择一个部分，然后从第二个开始依次填充其余部分。

3. 通过随机交换两个城市来改变这条线路，如果旅游线路的质量仅为初始人口中前10%旅游线路的1.3倍（我刚刚通过归纳法，挑选出了一些糟糕的旅游线路），我很想改变这种情况，但想不出更好的办法。在

   • 突变是从几个突变的群体中选择的。在

4. 返回生成的巡演。

然而，这种突变几乎总是更糟，如果不是和杂交一样的话。在

我非常感谢你的帮助。谢谢！在

Answer 1

遗传算法的一个问题是过快地缩小搜索空间并达到局部最大解。您需要确保您没有以任何方式领导您的解决方案，除了在选择/健身功能。所以当你说

why would you take a good solution and then perform a function that will most likely make it a worse solution

，原因是你想要一个机会让解决方案后退一步，它可能需要在变得更好之前变得更糟。所以你真的应该从你的遗传算子中去掉任何判断逻辑，把这留给选择过程。在

另外，交叉和变异应该被视为两种不同的方式来产生一个孩子个体，你应该使用其中之一。实际上，这意味着你有机会进行单亲或双亲间的杂交。通常情况下，突变率只有5%，而使用交叉产生另95%。在

杂交会从父母双方（孩子是镜像）那里得到遗传信息，所以一个孩子比父母差，另一个好（或者两者都一样）。所以从这个意义上讲，如果有变化，你总会得到一个更好的个人。在

另一方面，变异并不能保证一个更好的个体，但是它的存在是为了引入新的数据，帮助遗传算法从局部极大值场景中转移出来。如果突变不能改善个体并使其变得更糟，那么无论如何，它被选为养育孩子的机会就更小了（也就是说，你不需要在变异算子中使用这种逻辑）。在

you select the best one to mutate

严格来说，这不是真的，优秀的个人应该有更高的机会被选中。在这里有一个微妙的区别，坏的人也可能被选为父母。同样，这有助于降低达到局部极大值解的机会。这也意味着，一代人中最优秀的人可能（而且通常确实）变得更糟。为了解决这个问题，我们通常实行“精英主义”，即最好的个体总是被复制到下一代（在它没有进行任何操作的情况下）。在

如果我能评论一下你使用的是哪种遗传算子，那也是有益的。在我的经验中，我发现循环交叉和反转突变工作得很好。在