如何在遗传算法中为非分类群体组织轮盘赌轮选择？

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循环的最后一次迭代中完成的操作(因为即使我们找到了我们想要的个体,它也会随之增加).