The choice of people from the population, a fitness function

Question

I am working on an algorithm where I need to select n individuals from a population of size k, where k is much larger than n. All people have fitness value, so the choice should contribute to higher fitness values. However, I don’t just want to choose the best Russian people, the worst should also have a chance. (Natural selection)

So, I decided to find the minimum and maximum values ​​for fitness among the population. So any person would have

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

the probability of being chosen, but I can’t just go through all of them, roll the dice and choose one if there is a chance, because then I have more than n individuals. I could shuffle the list and repeat it from the front until I get up to n people, but that might miss the great ones at the end of the list.

I could also do more than one pass until the remaining population reaches n. But it may be better for the best, and converges to the naive selection method that I mentioned.

Any suggestion or links to such a selection process? I could read some statistical methods if you can reference them.

Thanks.

Answer 1

Use Roulette Wheel Selection . The basic idea is that you assign the area of ​​the roulette wheel relative to the size of the probability:

Then you simply rotate it n times to select the people you want.

An example 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 can be much shorter with a lot of Rubyisms, however I wanted the algorithm to be as clear as possible.