使用遗传算法解决TSP问题时的参数

3
我刚开始接触遗传算法,并使用它来解决旅行商问题。然而,我不清楚应该使用哪些参数。让我解释一下我所说的参数。
参数:
种群大小
产生的子代数目
突变数目
我确定上述参数取决于我的问题中有多少个城市,以及我的交叉和突变规范的确切形式。但是它们之间有什么关系呢?
有没有什么经验法则可以确定这些参数?任何提示或建议都将非常棒。
以下是我在5个城市问题上详细做的事情:
1) 我生成了20个随机路径,种群大小=20
2) 选择了14个最佳路径(抛弃了6个最差的路径)
3) 随机从14条最佳路径中选择两条路径创建2个变异体
突变次数=2
(对于突变,我只是随机交换两个城市的顺序 例如:0,1,2,3,4,0 可以变为 0,1,3,2,4,0)
4) 我从8条最佳路径中创建了4个孩子。
子代数=4
(对于交叉,我保留了公共的子路径,其余部分是随机生成的) 例如:父亲1:0,1,2,3,4,0,父亲2:0,2,1,3,4,0 3,4是共同的,所以孩子路径会从3,4开始,其余部分是随机的。孩子路径可能是:0,3,4,1,2,00,2,3,4,1,0 5) 现在我有了2个变异体和4个孩子,我将它们添加到我的14个最佳路径中,现在我有一个由20条路径组成的种群。
6) 重复步骤2),3),4),5)等等。
我纯粹任意设置了我的参数吗?它们可以吗?对于含有15个城市、48个城市或500个城市的问题应该使用哪些参数?谢谢您提前的帮助。
1个回答

4

你的问题非常有趣且难以回答,很抱歉我要说没有确切的答案。我写了一本关于遗传算法的书,在将近500页的内容中,我反复强调参数取决于你的问题。

关于你具体的例子,让我们分析一下你的参数。你有一个由20个个体组成的种群,每一代你会生成6个不同的子代。假设你有50代,那么你将会分析314个解决方案(20个原始个体加上49*6个子代)。考虑到你有5个城市,你有5!=120个可能的解决方案,所以你使用遗传算法比穷举搜索更耗时。

我知道这只是一个小问题,而你关心的是更大的问题(15、48和500,以你的例子为例)。然而,经验法则是要覆盖搜索空间的一小部分(在48和500的情况下,这是自动的),以利用遗传算法的优良特性来引导搜索,你可能会得到一个好的结果。我建议将整个执行过程中生成的个体总数考虑为搜索空间的0.001%(在500个城市的情况下仍可能太多)。

就操作符而言,有很多需要讲述的(在我的书中,超过50页)。因此,我将向你推荐Larrañaga et al写的一篇好的评论。即使它有点陈旧,但它会为您提供更好地探索问题的指导。如果您需要更快速的参考,请考虑这篇维基百科文章
对于广告,我很抱歉,但它并不意味着要销售书籍(毕竟,我的书只有葡萄牙语和西班牙语版本,所以我认为大多数这个列表的成员不会购买它)。我只是想指出有很多关于这个主题的文献资料。如果您需要一本有趣的读物(并且您不会说葡萄牙语),我建议阅读Michaewicz's book,其中提出的观点肯定会帮助您更深入地了解问题。

谢谢您的帮助。您的帖子很有帮助。我现在意识到,我应该问另一个问题,以了解我可以从GA中期望什么。 - Akavall

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接