为什么在我的遗传算法中添加交叉功能会给我带来更糟糕的结果? [英] Why does adding Crossover to my Genetic Algorithm gives me worse results?

问题描述

我已经实施了遗传算法来解决旅行商问题(TSP).当我只使用突变时，与添加分频器相比，我会找到更好的解决方案.我知道正常的分频方法不适用于TSP，因此我同时实现了订购分频器和 PMX分频器方法，并且都遭受不良结果.

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%.

选择:轮盘选择

健身功能:1/游览距离

人口规模:经过100、200、500的测试，我还运行了5次GA，因此我有多种初始人口.

Population size: Tested 100, 200, 500, I also run the GA 5 times so that I have a variety of starting populations.

停止条件:2500代

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

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.

关于为什么我添加分频器后我的Google Analytics(分析)效果更差的任何想法?而且为什么它的性能比简单的Hill-Climb算法差得多，后者只能卡在局部最大值上，因为一旦找到局部最大值，就无法进行探索了.

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?

推荐答案

通过轮盘赌选择，您正在将坏父母引入其中.如果您想通过某种方式加倍选择合适的父母，这可能会有所帮助.

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.

这篇关于为什么在我的遗传算法中添加交叉功能会给我带来更糟糕的结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！