选择个人从人口，由适应度函数 [英] Choosing individuals from a population, by a fitness function

问题描述

我一直在努力的算法，在那里我需要从规模，其中k为小于n大得多的群体选择n个人。所有个人有一个适应值，所以选择应倾向于更高的适应度。但是，我并不想简单地选择最佳的n个人，更糟糕的人应该有机会也。 （自然选择）

I've been working on an algorithm, where I need to choose n individuals from a population of size k, where k is much bigger than n. All individuals have a fitness value, therefore the selection should favor higher fitness values. However, I don't want to simply choose best n individuals, the worse ones should have a chance also. (Natural selection)

所以，我决定找群内的最小和最大的健身价值。所以，任何个人将有

So, I decided to find the min and max fitness values within population. So, any individual would have

P =（电流 - 分钟）/（最大值 - 最小值）

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

概率来选择，但我不能只是遍历所有的人，掷骰子，并选择一个，如果概率成立，因为当时我结束了N多个人。我可以随机播放列表，并从前面迭代，直到我获得高达n个人，但可能会错过伟大的，以列表的末尾。

probability to be chosen, but I can not just iterate over all of them, roll the dice and choose one if the probability holds, because then I end up with more than n individuals. I could shuffle the list and iterate from front, till I obtain up to n individuals, but that might miss great ones to the end of list.

我还可以进行一个以上的传递，直到剩下的人口规模达到为n。但是，这可能有利于更好的了很多，收敛到我提到的天真选择方法。

I also could perform more than one passes, until the remaining population size reaches to n. But this might favor better ones a lot, and converge to the naive selection method I mentioned.

任何建议或参考这样的选择过程？我可以做相关统计方法的一些阅读，如果你可以将任何

Any suggestion, or references to such a selection process? I could do some reading on relevant statistical methods if you can refer any.

感谢。

推荐答案

使用轮盘赌轮选择。的基本思想是，分配的轮盘赌轮的相对于所述概率的大小的区域：

Use Roulette-wheel selection. The basic idea is that you assign an area of the roulette-wheel relative to the probability size:

然后你只需旋转它 N 次，选择你想要的人。

Then you simply spin it n times to select the individuals you want.

在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的黑客，你看到code可以与更多的Rubyisms要短得多，但我想要的算法要尽可能明确

Note: if you are a Ruby hacker, you see that the code could be much shorter with more Rubyisms, however I wanted the algorithm to be as clear as possible.

这篇关于选择个人从人口，由适应度函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！