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

Question

我的问题与这个有关: Roulette-wheel selection in Genetic algorithm. Population needs to be sorted first?如果我们不对人口进行排序，那么组织轮盘赌选择的方式是什么？当然，我们现在必须以线性方式搜索。对于这种情况，您有任何 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(因为即使我们已经找到我们想要的个体，它无论如何都会增加)。