0

我正在研究 VB.NET 中对称 TSP 的遗传算法。我想知道执行选择程序的正确方法是什么。似乎至少有两种不同的可能性:

1)

-create a "reproduction pool" of size R by using SELECTION(pop) function
-do offspring creation cycle
-randomly (uniformly) select two parents from that pool for each offspring 
 that needs to be created in each iteration

2)

-do offspring creation cycle
-use modified SELECTION(pop) function that will return two different parents from pop
-perform crossover to produce a child

额外问题:选择两个父母后,有可能产生两个不同的后代(如果交叉算子是不可交换的):CROSS(p1, p2) 和 CROSS(p2, p1)。我应该立即插入两个后代还是一个接一个地生产它们?这会有所作为吗?

目前我正在一一生产它们,因为我认为它会给人群带来更多的差异。

4

2 回答 2

1

这取决于编码。

您可以考虑当前人口中最适合的两个个体。

或者您可以使用轮盘赌选择(Google it)将每个个体与繁殖率相关联,这是通常的方式。

于 2013-05-28T19:09:45.820 回答
1

在遗传算法中,您不使用单独的复制池,而是从总体中采样(|N| 直到您有 2*|N| 父母从中创建 |N| 孩子)。如果您的复制池 R 的大小为 2*|N| 并且您从该池中随机抽样,这本质上是相同的行为,但是您需要更多随机数并且计算成本更高(取决于您的 RNG)。请注意,没有必要关心获得两个不同的父母。自己交配的父母将产生一个与父母相同的孩子(如果交叉是幂等的)。这类似于使用交叉概率。如果您在结构上比较它们,那么检查两个父母是否不同可能会非常昂贵。你也可以通过适应度来比较它们,但通常你可以有相同质量的非常不同的解决方案。

关于你的第二个问题:我想说这并不重要。出于简单的原因,我会选择只返回一个孩子:采用两个解决方案并返回一个解决方案的方法比返回一组解决方案的方法更容易处理。我想说的是,只有在您可以创建两个不同的解决方案的情况下,返回两者才有意义。这是二进制或实值编码的情况。但是,对于排列,您无法保证此属性,并且无论如何都会在交叉中丢失一些遗传信息。

于 2013-06-01T18:55:36.377 回答