c++ - 遗传算法中未排序的种群应该如何组织轮盘赌选择？

Question

我的问题与这个问题有关： 遗传算法中的轮盘赌选择。人口需要先排序？ 如果我们不对总体进行排序，那么组织轮盘选择的方式是什么？当然，我们现在必须以线性方式搜索。对于这种情况，您是否有任何 C++ 或 Java 代码片段？

Answer 1

种群根本不需要排序——轮盘赌选择的关键是给定个体被选择繁殖的概率与其适应度成正比。

假设您有一个未分类的人口，其适应度如下：

[12, 45, 76, 32, 54, 21]

要执行轮盘赌选择，您只需选择 0 到 240 范围内的随机数（人口适应度的总和）。然后，从列表中的第一个元素开始，减去每个人的适应度，直到随机数小于或等于零。因此，在上述情况下，如果我们随机选择 112，我们会执行以下操作：

Step 1: 112 - 12 = 100. This is > 0, so continue.
Step 2: 100 - 45 = 55.  This is > 0, so continue.
Step 3: 55 - 76 = -21.  This is <= 0, so stop.

因此，我们选择个体#3 进行复制。请注意，这根本不需要对总体进行排序。

因此，在伪代码中，它归结为：

let s = sum of population fitness
let r = random number in range [0, s].
let i = 0.
while r > 0 do:
    r = r - fitness of individual #i
    increment i
select individual #i - 1 for reproduction.

请注意，- 1最后一行中的 是为了抵消在increment i循环的最后一次迭代中完成的（因为即使我们找到了我们想要的个体，它也会增加）。