CODEWITHSUNDEEP
pythonrandomgenetic-algorithm
Ivy
Ivy

Reputation: 3573

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

Upvotes: 21

Views: 36708

Answers (6)

radekholy24
radekholy24

Reputation: 417

Here is a concise solution that uses only standard library:

import itertools
import random

def choose(population):
    bounds = list(itertools.accumulate(chromosome.fitness for chromosome in population))
    pick = random.random() * bounds[-1]
    return next(chromosome for chromosome, bound in zip(population, bounds) if pick < bound)

Upvotes: 2

cw&#39;
cw&#39;

Reputation: 1161

Use numpy.random.choice:

import numpy.random as npr
def selectOne(self, population):
    max = sum([c.fitness for c in population])
    selection_probs = [c.fitness/max for c in population]
    return population[npr.choice(len(population), p=selection_probs)]

Upvotes: 26

Alireza Alami
Alireza Alami

Reputation: 77

def Indvs_wieght(Indvs): # to comput probality of selecting each Indvs by its fitness
    s=1
    s=sum(i.fitness for i in Indvs)
    wieghts = list()
    for i in range(len(Indvs)) :
        wieghts.append(Indvs[i].fitness/s)
    return wieghts  

def select_parents(indvs,indvs_wieghts,number_of_parents=40): # Roulette Wheel Selection method  #number of selected  parent 
    return np.random.choice(indvs,size=number_of_parents,p=indvs_wieghts)

Upvotes: 2

Abhishek Bhatia
Abhishek Bhatia

Reputation: 9806

from __future__ import division
import numpy as np
import random,pdb
import operator

def roulette_selection(weights):
        '''performs weighted selection or roulette wheel selection on a list
        and returns the index selected from the list'''

        # sort the weights in ascending order
        sorted_indexed_weights = sorted(enumerate(weights), key=operator.itemgetter(1));
        indices, sorted_weights = zip(*sorted_indexed_weights);
        # calculate the cumulative probability
        tot_sum=sum(sorted_weights)
        prob = [x/tot_sum for x in sorted_weights]
        cum_prob=np.cumsum(prob)
        # select a random a number in the range [0,1]
        random_num=random.random()

        for index_value, cum_prob_value in zip(indices,cum_prob):
            if random_num < cum_prob_value:
                return index_value


if __name__ == "__main__":
    weights=[1,2,6,4,3,7,20]
    print (roulette_selection(weights))
    weights=[1,2,2,2,2,2,2]
    print (roulette_selection(weights))

Upvotes: 1

Amber
Amber

Reputation: 526613

import random

def weighted_choice(items):
    total_weight = sum(item.weight for item in items)
    weight_to_target = random.uniform(0, total_weight)
    for item in items:
        weight_to_target -= item.weight
        if weight_to_target <= 0:
            return item

Upvotes: -1

Gareth Latty
Gareth Latty

Reputation: 89007

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

Upvotes: 16

Related Questions