遗传算法轮盘赌选择

Question

我在理解算法方面遇到了问题。以下是网上最流行的算法。

for all members of population
  sum += fitness of this individual
end for

for all members of population
  probability = sum of probabilities + (fitness / sum)
  sum of probabilities += probability
end for

loop until new population is full
  do this twice
    number = Random between 0 and 1
       for all members of population
          if number > probability but less than next probability 
             then you have been selected
       end for
      end
  create offspring
end loop


for all members of population
  probability = sum of probabilities + (fitness / sum)
  sum of probabilities += probability
end for

^^^这段内容让我感到困惑。在个体所处的群体中，“概率总和”和“概率”是什么意思？这些像是个体一开始就拥有的价值观吗？

- user1013905

Answer 1

那是一段非常混淆的代码。

在第二个代码块中，probability是附加到每个群体成员的变量，而sum of probabilities是整个群体的全局变量。

现在，轮盘赌隐喻所说的是，整个群体可以被表示为一个轮盘赌，每个群体成员都有一个与其相对适应度成比例的轮盘赌片。该代码正在执行该隐喻背后的脏活--成员不再是轮子上的楔形，而是由线段[0,1]上的比例间隔表示概率的惯用方式。

为此，你技术上需要两个数字，每个成员都需要一个起始和一个结束。但第一个成员的起始值将为0；第二个成员的起始值将为第一个成员的结束值；等等，直到最后一个成员，其结束值为1。

这段代码的作用是这样的。 概率之和 一开始为0，第一次循环时，概率 是您直觉认为的那样。它标记了第一个成员的结束点。然后更新了“概率之和”。第二次循环，“概率”是您直觉认为的那样...通过“概率之和”进行了偏移。如此往复。

因此，第一个循环将适应度值相加，作为归一化的前奏。您所询问的第二个循环是将这些归一化的概率归一化并排列在单位间隔中。第三个（最复杂的）循环是选择两个随机数，将它们与人口的两个成员匹配，并进行交配。（请注意，假设这些成员以某种类似于数组的格式存在，以便您可以按顺序检查它们的端点是否与您已经滚动的随机数相匹配。）

- Novak

Answer 2

关键在于

probability = sum of probabilities + (fitness / sum)

并且

if number > probability but less than next probability 
         then you have been selected

概率是评估个体产生后代的机会大小，即在轮盘上占据的比例。 概率总和是轮盘的总大小。 每个个体的概率都是其适应度函数。

我在尝试理解算法时发现this link很有帮助。

- S.L. Barth

---

那么为什么算法要将每个种群成员的概率总和添加到(fitness/sum)中，以获取概率...概率应该只是(fitness/sum)对吧？ - user1013905