通过健身功能从人群中选择个体

Question

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

所以,我决定在人口中找到最小和最大适应度值.所以,任何个人都会

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

选择的概率,但我不能只迭代所有这些,掷骰子并在概率成立时选择一个,因为那时我最终得到的不止是n个人.我可以随机播放列表并从前面迭代,直到我获得最多n个人,但这可能会错过列表末尾的好人.

我也可以执行多次传球,直到剩余的人口规模达到n.但是这可能会有利于更好的那些,并且收敛于我提到的天真的选择方法.

有任何建议,或参考这样的选择过程？如果您可以参考,我可以阅读相关的统计方法.

谢谢.

Answer 1

使用轮盘赌选择.基本思路是你相对于概率大小指定轮盘赌的区域:

然后你只需旋转它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黑客,您会发现使用更多Rubyism时代码可能会更短,但我希望算法尽可能清晰.