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

Question

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

所以，我决定找到种群内的最小和最大适应度值。因此，任何个体都有

p = (current - min) / (max - min)

的概率被选择，但我不能只是迭代所有这些，掷骰子并选择一个如果概率成立的话，因为那样我就结束了超过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 代码可能会更短，但我希望算法尽可能清晰。