3

我刚开始对遗传算法有所了解,我正在用它来解决旅行商问题。但是,我对应该使用哪些参数感到困惑。让我解释一下参数的含义。

参数:

人口规模

生产的儿童数量

突变数

我确信上述参数取决于我的问题中的城市数量,以及我的交叉突变规范的确切形式。但到底是什么关系?

关于应该使用哪些参数,是否有任何种类或经验法则?任何类型的提示或建议都会很棒。

以下是我为 5 个城市问题所做的详细说明:

1) 我生成了 20 条随机路径,人口 = 20

2) 选出 14 条最佳路径(扔掉 6 条最差路径)

3) 从 14 条最佳路径中随机选择的两条路径创建 2 个突变体

突变数 = 2

(对于突变,我只是随机交换了两个城市的顺序 Ex: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个城市?

先感谢您。

4

1 回答 1

4

你的问题非常有趣和困难,我很遗憾地说没有确切的答案。我写了一本关于遗传算法的书,在它将近 500 页的篇幅中,我一再坚持认为参数取决于你的问题。

关于您的具体示例,让我们分析您的参数。您有 20 个人口,每一代您将产生 6 个不同的孩子。假设您有 50 代,您将分析 314 个解决方案(20 个原始个体加上 49*6)。假设你有 5 个城市,你有 5!=120 个可能的解决方案,所以你使用 GA 比穷举搜索更耗时。

我知道这是一个象征性的问题,并且您关心更大的问题(使用您的示例,15、48 和 500)。尽管如此,经验法则是覆盖搜索空间的一小部分(在 48 和 500 的情况下,这是自动的),以便使用 GA 的良好特性来指导搜索,您可能会得到一个好结果。我建议将高达 0,001% 的搜索空间视为整个执行过程中产生的个体总数(在 500 个城市这样的巨大问题的情况下,它可能仍然太多)。

关于使用的运算符,有很多要说的(在我的书中,有50多页)。因此,我将向您推荐 Larrañaga 等人撰写的一篇不错的评论。尽管它有点旧,但它会为您更好地探索您的问题提供指导。如果您想要更快的参考,请考虑这篇 Wikipedia 文章

我很抱歉打广告,但它不是为了卖书(毕竟,我的书只有葡萄牙语和西班牙语,所以我认为这个列表中的大多数成员都不会购买)。我只是想指出,有很多关于这个主题的文献。如果您需要有趣的阅读(而且您不会说葡萄牙语),我建议您阅读Michaewicz 的书,它提出的观点肯定会帮助您更深入地解决问题。

于 2012-06-14T14:38:12.590 回答