Choosing individuals from a population, by a fitness function

Question

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.

Answer 1

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.