为什么在我的遗传算法中添加交叉会给我带来更糟糕的结果？
我已经实现了遗传算法来解决旅行商问题（TSP）。当我仅使用突变时，我找到了比添加交叉更好的解决方案。我知道正常的交叉方法不适用于 TSP，因此我实现了 Ordered交叉和PMX交叉方法，但两者都会遭受不好的结果。
以下是我正在使用的其他参数：
突变：单交换突变或倒置子序列突变（如 Tiendil 此处所述），测试的突变率在 1% 到 25% 之间。
选择：轮盘选择
健身功能：1/游览距离
人群规模：测试过100、200、500，我也跑GA 5次，这样我就有了各种起始人群。
停止条件：2500代
对于26个点的相同数据集，我通常使用具有高突变率的纯突变得到大约500-600距离的结果。添加交叉时，我的结果通常在 800 距离范围内。另一个令人困惑的事情是，我还实现了一个非常简单的爬山算法来解决问题，当我运行 1000 次（比运行 GA 快 5 次）时，我得到的结果约为 410-450 距离，我希望使用 GA 获得更好的结果。
关于为什么当我添加交叉时我的 GA 表现更差，有什么想法吗？为什么它的性能比简单的爬山算法差得多，后者应该陷入局部最大值，因为一旦找到局部最大值就无法进行探索？
I have implemented a Genetic Algorithm to solve the Traveling Salesman Problem (TSP). When I use only mutation, I find better solutions than when I add in crossover. I know that normal crossover methods do not work for TSP, so I implemented both the Ordered Crossover and the PMX Crossover methods, and both suffer from bad results.
Here are the other parameters I'm using:
Mutation: Single Swap Mutation or Inverted Subsequence Mutation (as described by Tiendil here) with mutation rates tested between 1% and 25%.
Selection: Roulette Wheel Selection
Fitness function: 1 / distance of tour
Population size: Tested 100, 200, 500, I also run the GA 5 times so that I have a variety of starting populations.
Stop Condition: 2500 generations
With the same dataset of 26 points, I usually get results of about 500-600 distance using purely mutation with high mutation rates. When adding crossover my results are usually in the 800 distance range. The other confusing thing is that I have also implemented a very simple Hill-Climbing algorithm to solve the problem and when I run that 1000 times (faster than running the GA 5 times) I get results around 410-450 distance, and I would expect to get better results using a GA.
Any ideas as to why my GA performing worse when I add crossover? And why is it performing much worse than a simple Hill-Climb algorithm which should get stuck on local maxima as it has no way of exploring once it finds a local max?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
看起来你的交叉算子在新一代中引入了太多的随机性，因此你正在失去尝试改进糟糕解决方案的计算工作量。想象一下，爬山算法可以将给定的解决方案改进为其邻域的最佳解决方案，但遗传算法只能对几乎随机的总体（解决方案）做出有限的改进。
还值得一提的是，遗传算法并不是解决 TSP 的最佳工具。无论如何，您应该看看一些如何实现它的示例。例如 http://www.lalena.com/AI/Tsp/
It looks like your crossover operator is introducing too much randomness into the new generations, so you are losing your computational effort trying to improve bad solutions. Imagine that the Hill-Climb algorithm can improve a given solution to the best of its neighborhood, but your Genetic Algorithm can only make limited improvements to almost random population (solutions).
It is also worth to say that GA is not the best tool to solve the TSP. Anyway, you should look like at some examples of how to implement it. e.g. http://www.lalena.com/AI/Tsp/
通过轮盘赌选择，你会将坏父母引入其中。如果你想以某种方式权衡选择一些更好的父母，这可能会有所帮助。
请记住，您的大部分人口可能都是不称职的父母。如果你根本不权衡亲本选择，那么你很有可能会一直培育出糟糕的解决方案，从而导致池子溢出。权衡您的选择以更频繁地选择更好的父母，并通过增加随机性使用突变来纠正过于相似的池。
With roulette-wheel selection, you're introducing bad parents into the mix. If you'd like to weight the wheel somehow to choose some better parents, this may help.
Remember, much of your population might be unfit parents. If you're not weighting parent selection at all, there's a good chance you'll be breeding consistently bad solutions that overrun the pool. Weight your selection to choose better parents more frequently, and use mutation to correct a too-similar pool by adding randomness.
您可以尝试将精英主义引入您的选择过程。精英主义意味着在进行任何选择之前，种群中适应度最高的两个个体将被保留并复制到新种群中。精英主义结束后，选拔仍照常进行。这样做意味着无论轮盘赌选择哪一个父母，或者他们在交叉过程中产生什么，两个最好的个体将永远被保留。这可以防止新种群失去适应性，因为它的两个最佳解决方案不会比上一代更差。
You might try introducing elitism into your selection process. Elitism means that the two highest fitness individuals in the population are preserved and copied to the new population before any selection is done. After elitism is completed, selection continues as normal. Doing this means that no matter which parents are selected by the roulette wheel or what they produce during crossover, the two best individuals will always be preserved. This prevents the new population from losing fitness because its two best solutions can't be any worse than the previous generation.
添加交叉后结果较差的原因之一可能是它没有发挥应有的作用——结合了两个人的最佳特征。尝试用低交叉概率可能会吗？人口多样性可能是这里的一个问题。莫里森和德容在他们的著作人口多样性的测量中提出了一种新颖的多样性测量方法。使用该衡量标准，您可以了解人口多样性在几代人的过程中如何变化。看看使用交叉或不使用交叉时会有什么不同。
此外，您的 OX 或 PMX 实现中可能存在一些小错误/遗漏细节。也许你忽略了一些事情？顺便说一句，您可能想尝试边缘重组交叉算子吗？ （Pyevolve 有一个实现）。
One reason for your results being worse when crossover is added because may be it is not doing what it should- combine the best features of two individuals. Try with a low crossover probability may be? Population diversity could be a issue here. Morrison and De Jong in their work Measurement of Population Diversity proposes a novel measure of diversity. Using that measure you can see how your population diversity is changing over the generations. See what difference it makes when you use crossover or don't use crossover.
Also, there could be some minor mistake/missed detail in your OX or PMX implementation. Maybe you have overlooked something? BTW, may be you want to try the Edge Recombination crossover operator? (Pyevolve has an implementation).
为了提出“创新”策略，遗传算法通常使用交叉来结合不同候选解决方案的特性，以便快速探索搜索空间并找到更高适应度的新策略 - 与此完全不同人类智能的内部运作（这就是为什么我们从来没有真正“发明”任何东西，而只是混合我们已经知道的东西的原因）。
通过这样做（随机组合不同的个体），交叉不会保留对称性或顺序，并且当问题高度依赖于某种对称性或染色体中基因的顺序（如在您的特定情况下）时，它确实很可能采用交叉会导致更糟糕的结果。正如您所提到的，众所周知，交叉对于旅行推销员来说并不适用。
值得强调的是，如果没有这种打破对称性的交叉遗传算法，就无法填补进化的“利基”（缺乏对称性通常是必要的）——这就是为什么交叉（在其所有变体中）对于绝大多数人来说本质上是重要的的案例。
In order to come up with 'innovative' strategies genetic algorithms generally use crossover to combine feats of different candidate solutions in order to explore the search space very quickly and find new strategies of higher fitness - not at all unlike the inner workings of human intelligence (this is why it is arguable that we never really 'invent' anything, but merely mix up stuff we already know).
By doing so (randomly combining different individuals) crossover does not preserve symmetry or ordering, and when the problem is highly dependent on symmetry of some sort or on the order of the genes in the chromosome (as in your particular case) it is indeed likely that adopting crossover will lead to worse results. As you mention yourself, it is well known that known that crossover doesn't work for the traveling salesman.
It's worth underlining that without this symmetry breaking feat of crossover genetic algorithms would not be able to fill evolutionary 'niches' (where lack of symmetry is often necessary) - and that's why crossover (in all its variants) is essentially important in a vast majority of cases.