Choosing individuals from a population, by a fitness function
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 = (current - min) / (max - min)
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.
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.
Thanks开发者_如何转开发.
Use Roulette-wheel selection. The basic idea is that you assign an area of the roulette-wheel relative to the probability size:
Then you simply spin it n
times to select the individuals you want.
Sample implementation in 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
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.
精彩评论