6

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

所以，我决定在人口中找到最小和最大适应度值。所以，任何人都会有

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

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

我还可以执行多次传递，直到剩余的人口规模达到 n。但这可能会更偏爱更好的选择，并收敛到我提到的朴素选择方法。

有任何建议或对此类选择过程的参考吗？如果您可以参考，我可以阅读相关的统计方法。

谢谢。

4

1 回答 1

6

使用轮盘选择。基本思想是您根据概率大小分配轮盘赌的区域：

轮盘赌

然后，您只需旋转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 黑客，你会发现代码可以用更多的 Rubyisms 来缩短，但是我希望算法尽可能清晰。

于 2011-03-09T09:40:32.237 回答