algorithm - 通过适应度函数从种群中选择个体

Question

我一直在研究一种算法，我需要从大小为 k 的种群中选择 n 个个体，其中 k 远大于 n。所有个体都有适应度值，因此选择应该有利于更高的适应度值。但是，我不想简单地选择最好的n个人，最差的也应该有机会。 (自然选择)

因此，我决定找出种群中的最小和最大适应度值。所以，任何人都会有

p =(当前 - 最小值)/(最大 - 最小值)

被选中的概率，但我不能只是遍历所有的人，掷骰子并在概率成立时选择一个，因为那样我最终会得到超过 n 个人。我可以打乱列表并从前面开始迭代，直到我获得最多 n 个个体，但这可能会错过列表末尾的优秀个体。

我也可以执行不止一次通过，直到剩余种群规模达到 n。但这可能会更倾向于更好的选择，并收敛到我提到的朴素选择方法。

对这样的选择过程有什么建议或引用吗？如果您可以引用，我可以阅读一些相关的统计方法。

谢谢。

Answer 1

使用Roulette-wheel selection .基本思想是根据概率大小分配轮盘赌的区域:

然后您只需旋转它 n 次即可选择您想要的人。

ruby 中的示例实现:

def roulette(population, n)
  probs = population.map { |gene| gene.probability } # TODO: Implement this
  selected = []

  n.times do 
    r, inc = rand * probs.max, 0 # pick a random number and select the  individual 
                     # corresponding to that roulette-wheel area
    population.each_index do |i| 
      if r < (inc += probs[i])
        selected << population[i]
        # make selection not pick sample twice
        population.delete_at i
        probs.delete_at i
        break
      end
    end
  end
  return selected
end

注意:如果您是 Ruby 黑客，您会发现代码可以更短，但我希望算法尽可能清晰。