Rory - 3 months ago 6x
Python Question

# Fitness proportionate selection (roulette wheel selection) in Python

I have a list of objects (Chromosome) which have an attribute fitness (chromosome.fitness is between 0 and 1)

Given a list of such objects, how can I implement a function which returns a single chromosome whose chance of being selected is proportional to its fitness? That is, a chromosome with fitness 0.8 is twice as likely to be selected as one with fitness 0.4.

I've found a few Python and pseudocode implementations, but they are too complex for this requirement: the function needs only a list of chromosomes. Chromosomes store their own fitness as an internal variable.

The implementation I already wrote was before I decided to allow chromosomes to store their own fitness, so was a lot more complicated and involved zipping lists and things.

----------------------------EDIT----------------------------

Thanks Lattyware. The following function seems to work.

``````def selectOne(self, population):
max     = sum([c.fitness for c in population])
pick    = random.uniform(0, max)
current = 0
for chromosome in population:
current += chromosome.fitness
if current > pick:
return chromosome
``````

There is a very simple way to select a weighted random choice from a dictionary:

``````def weighted_random_choice(choices):
max = sum(choices.values())
pick = random.uniform(0, max)
current = 0
for key, value in choices.items():
current += value
if current > pick:
return key
``````

If you don't have a dictionary at hand, you could modify this to suit your class (as you haven't given more details of it, or generate a dictionary:

``````choices = {chromosome: chromosome.fitness for chromosome in chromosomes}
``````

Presuming that fitness is an attribute.

Here is an example of the function modified to take an iterable of chromosomes, again, making the same presumption.

``````def weighted_random_choice(chromosomes):
max = sum(chromosome.fitness for chromosome in chromosomes)
pick = random.uniform(0, max)
current = 0
for chromosome in chromosomes:
current += chromosome.fitness
if current > pick:
return chromosome
``````